《unique索引优化实践》由会员分享，可在线阅读，更多相关《unique索引优化实践（7页珍藏版）》请在金锄头文库上搜索。
1、Unique 索引优化实践胡月军(一浪)Unique 索引，有时也称 Primary Key 索引，顾名思义就是对于这个索引字段每个 doc 的值都是唯一的，如各种 id 字段：product id，customer id, campaign id 和 bidword id 等。这种类型的索引一般用来进行高效的查询，最典型的应用场景就是进行附表 join 查询，即对主表中查到的每一个 doc，都在附表中查询其对应的附表 doc 信息。所以，对这种类型的索引进行优化会对整体查询性能有很好的提升，特别是在主表查询的结果很多的情况下。本文主要总结一下对于这种类型索引的优化实践，包括全量和实时增量的情
2、况。我们知道，在全量建索引时，在内存中一般用开链的哈希表来存储 Token 的 Hash 值及其倒排链的信息。假设有 N 个不同的 tokens，那么这个 hash 数组的大小一般是取第一个大于N*(5/3)的质数 P。结构如下图所示：图 1: 全量索引在内存中的开链哈希表结构图当一个段的索引建完以后，这个内存中的 Hash 表里面的 tokens 的哈希值及包含其倒排链和 occ 链等元信息的 keyword terms 一般被转成如下的三种数据结构之一存在文件中：1. Closed Hash Table2. Skip List3. Tiered Dictionary这几种数据结构的目的都是
3、为了在查询时先 mmap 了这些文件以后，能对于一个给定的query keyword，快速根据其哈希值找到其对应的 keyword term，进而定位到相应的倒排链和 occ 链等信息。不同的数据结构在不同的场景（数据特点）下对于内存空间的使用以及查询性能的影响也是不同的。下面先简要分析一下以上这几种常用数据结构的特点，然后再谈谈对于 Unique 类型的索引所采用的优化数据结构。为了便于分析，假设我们有 100 万个不同的 Tokens，每个 Token 的 Hash 值需用 8 个 bytes表示(uint64_t)。Tokens 对应的 keyword terms 100 万个，同时在一
4、般情况下，每个 keyword term 的第一个元素就是其对应的 token 的 hash 值。在内存中建索引的时候 ,这个开链 hash表数组的大小 P 取大于 N*(5/3)的第一个质数，即 3145739。Closed Hash Table(闭链哈希表)提到哈希表，不少人想到就是快，时间复杂度为 O(1), 其实未必如此，这个在后面的优化讨论中再深入。对于闭链 hash,其大小一般也是取第一个大于 N*(5/3)的质数 P 来申请空间，所以空间占用一般会比较大。对于以上例子，即 N=100 万，那么这个 Hash 数组大小为 P，为原始 keyword terms 大小的 3.15 倍
5、。闭链 Hash 表事实上就是环形数组，如下图所示：图 2: 闭链 Hash 表结构图当查询一个 token 倒排链等信息的时候，首先计算其 hash 值，比如 H，然后用 H 模 P 得到一个值作为下标，然后看这个闭链 hash 数组在这个下标下的元素是否是空值，如果为空（对于上图来说，就是元素的 hash 值为 0） ，则直接返回表示没有查到；若不为空，则看看这个元素的 hash 值是否和查询值相等，若相等则找到返回，若不等则继续跟这个元素的后面元素依次进行比较，最后要么找到，要么碰到一个空元素说明没有查找到。Skip List(跳表)跳表，顾名思义，是能在查找的时候能快速跳过很多元素，然
6、后在一个相对小的范围内搜索给定的一个 query keyword 的 hash 值对应的 keyword term 信息。跳表的实现原理是：1. 首先确定用一个小的数组, 就叫做跳表数组吧，来存储跳表信息，这个数组的 size 一般取为 keyword terms 个数 N 的 1/64 (假设此值为 M)，或者稍微大点，数组中每个元素的大小为 4 个字节(uint32_t) 。2. 然后，将 keyword terms 按 token 的 hash 值从小到大排好序存储在一个数组中，假设这个数组叫 K，同时根据最大和最小的两个 token 的 hash 值将所有的 hash 值值域均分成 M
7、 个区间。3. 让跳表数组的第 i 个元素存储 hash 值的第 i 个区间里面的最小的一个 hash 值对应的keyword term 在数组 K 中的下标值（哈，这句话有点绕） ， 若 hash 值第 i 个区间里面没有值，则存一个无效的下标值-1.所以一个跳表的结构如下图所示：图 3: 跳表结构图在查询的时候，执行如下步骤：1. 先计算出 query keyword 的 Hash 值 H，然后用(H-Hmin)/Step 得到 skip list 数组中的下标i。2. 查看下标 i 里面的元素值是否为-1 ，若为-1，则说明没有查到直接返回，若不为 -1，就记录此元素值，假设为 j；然后
8、继续在 skip list 数组中查找 i 下标以后的元素中第一个不为-1 的元素值，若找到则记录此元素值为 k，如找不到则将 k 值设为 N，即 keyword terms 数组的最后一个元素下标位置+1 。3. 最后在 keyword terms 数组 K 的j,k位置中二分查询 hash 值为 H 的 keyword item。注意由于按 Hash 值的值域进行分段跳跃，所以每个哈希值区间里面的元素个数是很可能是分布不均的，故每次二分查找的区间大小是不固定的。Tiered Dictionary(分层词典)Tiered dictionary 的思路是分层查询定位。即，先二分查找一个小词典定
9、位到一个大致的小范围，然后再在小范围内再继续搜索 keyword term。实现的原理是：1. 先将所有的 keyword terms 按它们的 hash 值从小打大排序后存储在一个数组中。2. 将上面的数组分成若干个 blocks，每个 block 包含相同个数的 keyword terms，记做 B个(比如说 B 就取 128 个)，当然最后一个 block 的元素个数可能少于 B 个。3. 将上面每个 block 的最后一个 keyword item 元素的 hash 值抽出来依次保存在另外一个小的字典数组中。所以，序列化好的 tiered dictionary 结构图如下：图 4: T
10、iered dictionary 结构图那么对于任一个查询词，假设 hash 值为 H，查找其对应的 keyword term 就比较简单了：1. 先在字典数组中找到第一个大于或等于 H 的元素下标，若无此下标，即字典数组中的都有元素的 hash 值都小于 H，那么说明没有查到结果，直接返回；否则，可以根据此下标定位到这个元素在 keyword terms 数组中所属于的 block。2. 在 1 确定的 block 中二分查找 H 对应的 keyword term。相对于 skip list，tiered dictionary 的查询比较稳定，因为它可以保证第二次搜索总是在一个元素较少的 b
11、lock 中查询，而 skip list 无法做到这一点，这个前面提到过；但是 skip list 有时候可以在第一步查 skip list 小数组的时候就可以确定这个元素不存在，而 tiered dictionary一般情况下做不到这点。全量 Unique 索引优化像很多数据结构的算法一样，在内存空间使用和查找时间之间往往需要一个权衡，Unique索引的优化也是这样，当然我们的目标还是在尽可能的在占用较少内存的情况下，使得查询速度更快。不同于一般的字段索引，一次查询只查询一次，用在附表 Join 时候的 Unique 索引在一次查询中可能会被查询上万次(每个主表的 doc 结果都需要进行一次
12、附表 Unique 索引查询)，这就决定了查询速度是 Unique 索引实现的第一目标。我们看到，不管是 skip list 还是 tiered dictionary，大部分时候都需要二分查找，特别是有时候对于不在里面的元素，二分查找比较的次数反而更多，这就决定了对于 Unique 索引如用这两种数据结构，在线查询的性能是很不高的，虽然它们俩是比较省内存的。当然，我们最想达到的目标就是只比较一次，或者很有限几次就能确定一个 hash 值是否在一个段的某个 unique 索引中。我们很显然会想到哈希表，比如实现简单的闭链哈希表。的确，有些搜索引擎的索引也是这么做的。但是，对于闭链哈希表的实现，这
13、里面有一个大坑！对于 hash table 的实现，我们知道关键是 hash function，记做 H。好的 H(x)的计算结果要分布均匀(uniform distributed)、冲突少(less collisions)。但对于闭链 hash table 的实现，除了冲突少，H 还有一个非常重要的要求，那就是 H(x)的结果集要避免簇拥在一起( avoid clustering)，即要避免 H(x)计算得到的数组下标是连在一起的，否则会发生非常悲惨的后果。这个其实不难理解，因为对于线性 hash 函数来说，闭链 hash 表在查找的时候若发生冲突，是依次向后比较查找，要么找到相应元素，要么
14、碰到空元素没有找到返回。所以如果有大片的结果连在一起，如果查找的元素不在里面，同时又发生了冲突，查找到第一个空元素有时候需要比较很多次。这种情况很容易发生，比如在 bidword id 很多是相连在一起的情况，同时我们又采用简单取模的方式来计算 hash 数组存储下标。当然，我们可以修改哈希函数来避免簇拥，这个我们增量索引优化的时候会采用。对于全量，为了在内存使用和查询效率上取得平衡，我们可以采用开链哈希表的方式来解决，其实实现也不复杂。最简单的实现，就是将内存中的 hash table 里面的 conflicting hash nodes list 一条一条的序列化，内存中的主索引数组的元素
15、分布情况不变，同时将 conflicting nodes 直接链在原hash 主数组的后面。不过，为了链式存储，序列化好的每个 keyword item 里面会增加一个next 指针和是否是每条链的最后一个节点的标记。存储好的结果如下图所示：图 5: 开链 Hash 表结构图显然，有了这样的开链 hash 表结构，我们就可以保证每次都能在有限比较次数内确定一个hash 值是否在索引中，而且最多比较次数就是最长的冲突链的长度。同时，我们知道一般用来建 Unique 索引的字段值基本上都是以加一的方式递增的，所以当哈希函数取为 H(x) = x % P（P 是一个较大质数） ，冲突显然是很少的。此
16、外，在查询没有冲突的情况下，只需要比较一次就可以确定一个 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用来表示当有
