资源预览内容
第1页 / 共7页
第2页 / 共7页
第3页 / 共7页
第4页 / 共7页
第5页 / 共7页
第6页 / 共7页
第7页 / 共7页
亲,该文档总共7页全部预览完了,如果喜欢就下载吧!
资源描述
Unique 索引优化实践胡月军(一浪)Unique 索引,有时也称 Primary Key 索引,顾名思义就是对于这个索引字段每个 doc 的值都是唯一的,如各种 id 字段:product id,customer id, campaign id 和 bidword id 等。这种类型的索引一般用来进行高效的查询,最典型的应用场景就是进行附表 join 查询,即对主表中查到的每一个 doc,都在附表中查询其对应的附表 doc 信息。所以,对这种类型的索引进行优化会对整体查询性能有很好的提升,特别是在主表查询的结果很多的情况下。本文主要总结一下对于这种类型索引的优化实践,包括全量和实时增量的情况。我们知道,在全量建索引时,在内存中一般用开链的哈希表来存储 Token 的 Hash 值及其倒排链的信息。假设有 N 个不同的 tokens,那么这个 hash 数组的大小一般是取第一个大于N*(5/3)的质数 P。结构如下图所示:图 1: 全量索引在内存中的开链哈希表结构图当一个段的索引建完以后,这个内存中的 Hash 表里面的 tokens 的哈希值及包含其倒排链和 occ 链等元信息的 keyword terms 一般被转成如下的三种数据结构之一存在文件中:1. Closed Hash Table2. Skip List3. Tiered Dictionary这几种数据结构的目的都是为了在查询时先 mmap 了这些文件以后,能对于一个给定的query keyword,快速根据其哈希值找到其对应的 keyword term,进而定位到相应的倒排链和 occ 链等信息。不同的数据结构在不同的场景(数据特点)下对于内存空间的使用以及查询性能的影响也是不同的。下面先简要分析一下以上这几种常用数据结构的特点,然后再谈谈对于 Unique 类型的索引所采用的优化数据结构。为了便于分析,假设我们有 100 万个不同的 Tokens,每个 Token 的 Hash 值需用 8 个 bytes表示(uint64_t)。Tokens 对应的 keyword terms 100 万个,同时在一般情况下,每个 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 倍。闭链 Hash 表事实上就是环形数组,如下图所示:图 2: 闭链 Hash 表结构图当查询一个 token 倒排链等信息的时候,首先计算其 hash 值,比如 H,然后用 H 模 P 得到一个值作为下标,然后看这个闭链 hash 数组在这个下标下的元素是否是空值,如果为空(对于上图来说,就是元素的 hash 值为 0) ,则直接返回表示没有查到;若不为空,则看看这个元素的 hash 值是否和查询值相等,若相等则找到返回,若不等则继续跟这个元素的后面元素依次进行比较,最后要么找到,要么碰到一个空元素说明没有查找到。Skip List(跳表)跳表,顾名思义,是能在查找的时候能快速跳过很多元素,然后在一个相对小的范围内搜索给定的一个 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 个区间。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;然后继续在 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 的思路是分层查询定位。即,先二分查找一个小词典定位到一个大致的小范围,然后再在小范围内再继续搜索 keyword term。实现的原理是:1. 先将所有的 keyword terms 按它们的 hash 值从小打大排序后存储在一个数组中。2. 将上面的数组分成若干个 blocks,每个 block 包含相同个数的 keyword terms,记做 B个(比如说 B 就取 128 个),当然最后一个 block 的元素个数可能少于 B 个。3. 将上面每个 block 的最后一个 keyword item 元素的 hash 值抽出来依次保存在另外一个小的字典数组中。所以,序列化好的 tiered dictionary 结构图如下:图 4: 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 指针和是否是每条链的最后一个节点的标记。存储好的结果如下图所示:图 5: 开链 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用来表示当有
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号