Tiered Dictionary(分层词典)

　　Tiered dictionary的思路是分层查询定位。即，先二分查找一个小词典定位到一个大致的小范围，然后再在小范围内再继续搜索keyword term。实现的原理是：

　　1.先将所有的keyword terms按它们的hash值从小打大排序后存储在一个数组中。

　　2.将上面的数组分成若干个blocks，每个block包含相同个数的keyword terms，记做B个(比如说B就取128个)，当然最后一个block的元素个数可能少于B个。

　　3.将上面每个block的最后一个keyword item元素的hash值抽出来依次保存在另外一个小的字典数组中。

　　所以，序列化好的tiered dictionary结构图如下：

▲Tiered dictionary结构图

　　那么对于任一个查询词，假设hash值为H，查找其对应的keyword term就比较简单了：

　　1.先在字典数组中找到第一个大于或等于H的元素下标，若无此下标，即字典数组中的都有元素的hash值都小于H，那么说明没有查到结果，直接返回;否则，可以根据此下标定位到这个元素在keyword terms数组中所属于的block。

　　2.在1确定的block中二分查找H对应的keyword term。

　　相对于skip list，tiered dictionary的查询比较稳定，因为它可以保证第二次搜索总是在一个元素较少的block中查询，而skip list无法做到这一点，这个前面提到过;但是skip list有时候可以在第一步查skip list小数组的时候就可以确定这个元素不存在，而tiered dictionary一般情况下做不到这点。

　　全量Unique索引优化

　　像很多数据结构的算法一样，在内存空间使用和查找时间之间往往需要一个权衡，Unique索引的优化也是这样，当然我们的目标还是在尽可能的在占用较少内存的情况下，使得查询速度更快。

　　不同于一般的字段索引，一次查询只查询一次，用在附表Join时候的Unique索引在一次查询中可能会被查询上万次(每个主表的doc结果都需要进行一次附表Unique索引查询)，这就决定了查询速度是Unique索引实现的第一目标。我们看到，不管是skip list还是tiered dictionary，大部分时候都需要二分查找，特别是有时候对于不在里面的元素，二分查找比较的次数反而更多，这就决定了对于Unique索引如用这两种数据结构，在线查询的性能是很不高的，虽然它们俩是比较省内存的。

　　当然，我们最想达到的目标就是只比较一次，或者很有限几次就能确定一个hash值是否在一个段的某个unique索引中。我们很显然会想到哈希表，比如实现简单的闭链哈希表。的确，有些搜索引擎的索引也是这么做的。但是，对于闭链哈希表的实现，这里面有一个大坑!

　　对于hash table的实现，我们知道关键是hash function，记做H。好的H(x)的计算结果要分布均匀(uniform distributed)、冲突少(less collisions)。但对于闭链hash table的实现，除了冲突少，H还有一个非常重要的要求，那就是H(x)的结果集要避免簇拥在一起(avoid clustering)，即要避免H(x)计算得到的数组下标是连在一起的，否则会发生非常悲惨的后果。这个其实不难理解，因为对于线性hash函数来说，闭链hash表在查找的时候若发生冲突，是依次向后比较查找，要么找到相应元素，要么碰到空元素没有找到返回。所以如果有大片的结果连在一起，如果查找的元素不在里面，同时又发生了冲突，查找到第一个空元素有时候需要比较很多次。这种情况很容易发生，比如在bidword id很多是相连在一起的情况，同时我们又采用简单取模的方式来计算hash数组存储下标。

　　当然，我们可以修改哈希函数来避免簇拥，这个我们增量索引优化的时候会采用。对于全量，为了在内存使用和查询效率上取得平衡，我们可以采用开链哈希表的方式来解决，其实实现也不复杂。

　　最简单的实现，就是将内存中的hash table里面的conflicting hash nodes list一条一条的序列化，内存中的主索引数组的元素分布情况不变，同时将conflicting nodes直接链在原hash主数组的后面。不过，为了链式存储，序列化好的每个keyword item里面会增加一个next指针和是否是每条链的最后一个节点的标记。存储好的结果如下图所示：

▲开链Hash表结构图

　　显然，有了这样的开链hash表结构，我们就可以保证每次都能在有限比较次数内确定一个hash值是否在索引中，而且最多比较次数就是最长的冲突链的长度。同时，我们知道一般用来建Unique索引的字段值基本上都是以加一的方式递增的，所以当哈希函数取为H(x) = x % P(P是一个较大质数)，冲突显然是很少的。此外，在查询没有冲突的情况下，只需要比较一次就可以确定一个hash值是否在索引中;即使在比较查找发现有冲突的时候，大的内存跳跃查找也至多一次，因为除了第一个冲突节点，后面都所有其它的冲突节点都是存储在一起的，所以查询上具有较好的内存访问局部性，对CPU cache利用比较友好，从而查询性能比较好。

　　测试和线上效果证明，对于P4P广告bidword域的bid_adid Unique索引，当用以上的开链hash表存储结构替代原来的skip list实现时，查询性能提升3倍左右。

　　此外，在基本保持查询性能优化效果不变的情况下，我们还可以对以上开链hash表存储结构进行优化，从而占用更少的内存空间。

　　我们发现主hash数组里面的每个空元素也占用了一个keyword item的空间大小，但其实它们唯一的作用就是表明这个位置为空，所以我们可以用一个每个元素大小为32位(uint32_t)的数组来表明hash结果信息，其中1个bit用来表明此位置是否有hash结果，另外31个bit用来表示当有hash结果的时候，对应hash节点链在keyword items数组中的开始下标。这样就可以将整个keyword items按每条hash冲突链存储在一起了，next指针也不需要了，只需要用一个bit来标识其是否是hash冲突链的最后一个节点就可以了，一般这个flag可以从32位的doc id上面取一位来标识。故，改进后的存储结构为：

▲内存使用优化后的开链Hash表结构图

　　对于前面提到的那个例子，即有100万个tokens，每个Unique索引的keyword item保存token的哈希值和doc id，且有20万的hash结果是冲突的。那么，上面改进后的索引结构使用的内存空间约是原来的46%，节省了一半以上的内存空间。

　　【注： (3145739*4 + 1000000*12)/((3145739+200000)*16) = 45.9%; 16是因为原来的keyword item多需要额外4个bytes的next成员】

　　实时增量Unique索引优化

　　以上谈论的是对全量Unique索引的优化，实时增量索引是在内存中一条doc一条doc构建起来的，它不可能像全量时那样有一个完整的内存哈希表可以进行序列化存储。但是由于一个segment的总共doc数组数目是固定的，同时又是Unique索引，所以我们一般用闭链哈希表来存储实时增量的unique索引。

　　但我们前面提到过，闭链哈希表的实现有一点要非常小心，那就是哈希函数H在保存冲突少的同时也应该避免哈希结果的slots簇拥在一起。其实也就是让空元素能够均匀的分布在哈希数组中，这样即使在查询碰到哈希冲突的时候，也能够很快完成比较退出，即要么找到相应元素完成查找，要么很快就能碰到空元素表示查找不到退出。

　　怎么样才能避免哈希结果集簇拥在一起了呢?一个简单有效的办法为：

　　1.首先将闭链Hash数组扩大几部，比如说3倍，即3P大小。

　　2.将线性哈希函数H(x) = x % P修改为：H(x) = 3 * ( x % P)。

　　3.当发生冲突的时候，依次+1探测去找空的slots进行存储。

　　所以，修改后的实时增量段的Unique索引的存储结构为：

▲避免簇拥的闭链Hash表结构图

　　显然，修改后的算法占用了更多的内存空间。但由于是实时增量段，这些段的doc数据量一般比较小，而且会被定期合并生成和全量时候一样的索引结构，所以多一点内存空间影响不是太大。但对于查询性能的提升是非常大的，据测试和线上效果观测，经过这样的修改，查询性能提升10倍以上。