2013年三月

Unix/Linux设计思想学习笔记之一

三 30th

由admin发表在[...] | 154 浏览

没有评论

最近在看《Unix/Linux设计思想》这本书，有些地方读起来很容易，但是真正理解还需要细细品味，以后就把书中提到的一些准则简单记录下，主要是为了加深理解，今天主要记录下Unix哲学的概述。

Unix哲学概述：

(1) 小即是美。相对于同类庞然大物，小巧的事物有着无可比拟的优势，其中一点就是它们能够以独特有效的方式结合其他小事物，这和软件工程中提到的“模块化”的思想基本是一致的。

(2) 让每个程序只做好一件事情。通过集中精力应对单一任务，程序可以减少冗余代码，从而避免过高的资源开销、不必要的复杂性和缺乏灵活性。

(3) 尽快建立原型。大多数人都认同“建立原型”（prototyping）是任何项目的一个重要组成部分。在Unix环境中，它是达成完美设计的主要工具。

(4) 舍高效率而取移植性。当Unix作为第一个可移植性系统而开创先河时，它曾掀起过轩然大波。今天，可移植性早被视作为现代软件设计中一个理所当然的特性。

(5) 使用纯文本文件来存储数据。可以看到在类Unix的系统中，所有的配置文件都是使用文本数据直接存储，一方面用户可以直接修改配置，另一方面也是为移植性考虑的。

(6) 充分利用软件的杠杆效应。很多程序员对可重用代码模块的重要性只有一些肤浅的认识。代码重用能帮助人们充分利用软件的杠杆效应。一些Unix程序员正是遵循这个强大的理念，在相对较短的时间内编写出大量应用程序。

(7) 使用shell脚步来提高杠杆效应和可移植性。shell脚步在软件设计中可谓是一把双刃剑，它可以加强软件的可重用性和可移植性。无论什么时候，只要有可能，编写shell脚本来替代C语言程序都不失为一个良好的选择。

(8) 避免强制的用户界面

(9) 让每个程序都成为过滤器(filter)。所有软件程序共有的最基本特性就是，它们只修改而从不创造数据。因此，基于软件的过滤器本质，人们应该把它们编写成执行过滤器任务的程序，管道就是Unix这一个特性的非常好代表。



google sparse hash set/map

三 19th

由admin发表在[...] | 1,666 浏览

没有评论

google开源了hashtables的包，包括两个部分：

  • sparse, 比较节省空间space-efficient;
  • dense, 高效的查询效率 time-efficient;

同时接口兼容SCI的hash_map和hash_set, 并且提供了序列化的功能，非常赞~

下面是其官方的性能测试数据：可以看到sparse_hash_map比stl::map和hash_map节省2/3的空间，而dense_hash_map具备较高的查询，删除, insert性能，可以根据具体的应用

来使用不同的数据结构。

下载地址：http://code.google.com/p/sparsehash/

doc : http://google-sparsehash.googlecode.com/svn/trunk/doc/

SPARSE_HASH_MAP:
map_grow                  665 ns
map_predict/grow          303 ns
map_replace               177 ns
map_fetch                 117 ns
map_remove                192 ns
memory used in map_grow    84.3956 Mbytes

DENSE_HASH_MAP:
map_grow                   84 ns
map_predict/grow           22 ns
map_replace                18 ns
map_fetch                  13 ns
map_remove                 23 ns
memory used in map_grow   256.0000 Mbytes

STANDARD HASH_MAP:
map_grow                  162 ns
map_predict/grow          107 ns
map_replace                44 ns
map_fetch                  22 ns
map_remove                124 ns
memory used in map_grow   204.1643 Mbytes

STANDARD MAP:
map_grow                  297 ns
map_predict/grow          282 ns
map_replace               113 ns
map_fetch                 113 ns
map_remove                238 ns
memory used in map_grow   236.8081 Mbytes


google早期的索引结构介绍

三 1st

由admin发表在[...] | 556 浏览

没有评论

最近一直在做索引压缩方面的事情，无意中看到了Jeff Dean大牛分享的google早期的索引结构，对于我们这种刚刚起步的搜索公司，还是很有启发意义的，收获还是比较大，所以就简单记录下。

1. 索引压缩常用的压缩算法

淘宝的一篇技术blog分享了一些比较常用的压缩算法：

  • varint (变长压缩)： 字节对齐，压缩比不高
  • group varint: 变长压缩的变形，比varint的解压速率高很多，这里有它的实现
  • Gamma:  对比较小的数字压缩比会比较高，将数值分为两个部分： 一元编码（num_bits）+二进制编码
  • Simple9 + simple16: 对于32bit的空间进行组织，可存储多个数值
  • PForDelta + NewPForDelta: 比较新的压缩算法，压缩比和解压缩比都比较高效，适合于docid_delta的压缩

关于这些算法的相关介绍可以看下www.wikipedia.org，或者搜下对应的paper.

2. Google的索引结构

索引结构

可以看到，对于token的doclist是以Block的方式进行组织的，如果doclist比较长，还会使用skip table来快速查找；

Block的组织方式：

a. block header:  使用变长存储与上一个block的delta, 并存储block 实际的存储长度（可能是作为验证）

b. 第二行使用Gamma来压缩编码类型及在block中出现的docs的数目（因为这些数值都比较小）

c. 使用Rice压缩对应docld delta, 其实这里可以使用比较新的压缩算法PFDelta，更高效一些

d. 使用Gamma来压缩对应token在doc中出现的frequence, 即hit的数目

e. 使用length-limit Huffman 来存储Hit Attribute信息，这里主要是利用Attribute的重复的比例会很高，也就是说大部分hit  attribute

都会是相同的，所以用到了Huffman压缩，然后对length进行了限制

f: positions用Huffman-Int 来压缩位置信息，由于position分布不确定性很多，对position的压缩一直是业界的难题，压缩比不会很高。

Huffman-Int : 类似于Gamma压缩，但是对于一元编码部分，使用了Huffman code.

优化

这里其实可以将doclist和hit 信息进行分离存储，因为只有在打分的时候才会用到hit的相关信息，访问次数会比较少，而doclist就会访问比较频繁

可以对其进行Cache，这样Cache命中率会更高一些