共计 6101 个字符，预计需要花费 16 分钟才能阅读完成。
作者 | XY
导读
漏斗优化是检索系统不变的话题，过来一年来，广告漏斗优化一改来日做“加法”，而通过简化漏斗，晋升全零碎一致性。如百度这样宏大的广告库规模、高流量规模以及简单的业务规定，要做到极简的漏斗档次，须要最高效的策略设计和最极致的工程实现。本文重点介绍了百度 Geeker 们在倒排数据结构上如何“抠细节”达到倒排召回无截断，对大家做高性能零碎也将有所启发。
全文 6162 字，预计浏览工夫 16 分钟。
01 业务背景 – 全零碎 Limitless
大家都分明，广告漏斗包含召回、粗排、精排这三局部，现实中的漏斗上宽下窄很规整，而事实中因为种种原因，漏斗曾经略显飘逸了，这种不一致性会带来很多业务持续倒退的复杂度。咱们心愿达到：模型统一，精简漏斗，全零碎 Limitless。
咱们对 Limitless 的意识：细节处见真章，挑战软件工程性能极限，方能漏斗近似无截断。
明天想跟大家聊聊『BS Limitless』我的项目里咱们怎么抠细节的，整个我的项目其实挑战很大，网络、计算和存储方方面面都波及到，一篇短文很难讲透，因而我决定选一个数据结构 - 倒排表，让大家感触到『极致』优化。
02 技术背景 – 倒排表
先介绍一下优化前的倒排表，它的组成比拟经典特点，HashMap<keysign, SkipList>。一次检索 pv 依据触发的 N 个词（keysign）扫描拉链（SkipList），广告业务投放特点人造会有长链、超长链，为此链表须要有序，做过漏斗的同学晓得，在倒排阶段排序能用的信息其实是很少的，这也阐明了扫描 Limitless 对业务的高价值。
这样一个小小的数据结构承当了各方的要求，1、读性能决定无限工夫能放出多大量，2、实时插入决定客户投放能不能立刻失效，3、单库规模微小，内存损耗要低。对工程的合理要求，的确是 既要 … 又要 … 还要 …。在 Limitless 的大背景下，咱们 要显著晋升 1 达到 scan limitless，然而不能侵害到 2 和 3 。
回过头来看，这么简略的数据结构，Limitless 的瓶颈到底是什么？大家回顾一下计算机体系结构的内容。cpu 并不间接访存，而通过层层缓存达到内存，存储档次越低，它的容量越大但提早越高，mem 和 L2、L1 之间有量级差距[1]。List 这种数据结构显然不足空间局部性。
缓存不亲和的 List 比照缓存敌对的 Array，在扫描上到底有多差呢？咱们做了如下的评测，其中横轴代表链长或数组长度，纵轴是均匀到单条元素的扫描耗时，后果是 10+ 差距。换成数组 Array，也是不行的，客户要求实时失效，为了低效拷贝损耗须要 O(2N)的增长速度，内存老本要求也不能满足。
03 计划 – HybridIndexTable
咱们针对业务的特点和 Limitless 的要求进行极致设计和优化，推出了新一代的内存数据结构 HybridIndexTable，简称 HIT。降级后的 倒排表：
1、用 HashMap 索引 keysign，
2、短链采纳间断存储，长链则是一棵叶子间断存储的前缀树，前缀树则参考了业界AdaptiveRadixTree，简称 ART，
3、短链和叶子的）间断存储都采纳了自研的RowContainer，简称 RC。
在简短的数据结构之外，还要和大家分享两个要害细节：
1、Key 序路由兜底超长链有序，
2、RC 间无序，以 RC 为单位扫描。
HIT 这样的数据结构有如下三点劣势，恰到好处地满足了后面的三个要求。
- 读取性能高，间断存储 + 前缀树升高 cachemiss，线程平安做法 reader-friendly，还有面向负载的优化；
- 更新时效性高，间断存储但 append-only/mark-delete；
- 内存损耗少，利用了大量的自适应算法。
HIT 上线后拿到了十分可观的业务收益，Limitless 的路线上 技术就是生产力！
04 HIT 缘起，内存索引 ModernCPU 的摸索
内存索引畛域已在面向 Modern Cpu 深耕，ModernCpu 因为 Cpu 运行得很快，使得缓存一致性的影响、访存的影响成为高性能的瓶颈。内存索引在 2000s 也有些 阶段性的标记成绩，包含 FAST[4]，它是面向体系结构的数据结构设计的典型，无论是思维还是成绩十分实用于静态数据；CSBtree[2][3]，它提出数据结构上通过 KV 拆散，使得一次访存能比拟多个 Key，同时还提出了 SMO 的无锁解法；还有 ART 前缀树[5]。有序索引中 BTree 居多，咱们为何留神到了前缀树呢？
链表类型的缓存生效产生在每次拜访下一个节点，缓存生效复杂度 O(n)。排序树类型的缓存生效产生在拜访下一层节点，缓存生效复杂度 O(lgn)。而对于前缀树来说，缓存生效只和 键长 k(len)/ 扇出 s(pan) 无关，缓存生效复杂度 O(k/s)。如下图 [5]，假如 k 是键长的 bit 数，随着存储数据量上涨 2^(k/8)、2^(k/4)、…，齐全均衡树高一直减少，别离是 k /8、k/4、…，而对于一颗前缀树，树高对于给定的 span 是恒定的，如针对 span= 8 和 4，树高别离是 k /8、k/4。 前缀树更加缓存敌对。
这里简略介绍下前缀树，英文是 Trie、Prefix tree 或 Digit tree，左图是维基百科的实例，这是个典型的没有任何优化的前缀树，一方面，只有单分叉的状况下也多分出一级，比方 inn；另一方面，因为在分支节点须要调配 2 ^ s * pointer 的内存，对于理论扇出极少的场景，内存损耗十分大。
RadixTree 是一种通过合并前缀（PathCompression）优化内存的前缀树。合并前缀是指压缩掉仅有一个孩子的分支节点，这样存在的节点或者是叶子节点，或者是有分叉的分支节点。名字中的 radix=2^span，它在 radix= 2 的状况下，也叫做 Patricia tree[6]。Linux PageCache 页面缓存用的是 RadixTree，以太坊币 ETH 的外围数据结构是 Merkle Patricia tree。两头图是依照 RadixTree 从新组织的。
即使有合并前缀，因为大部分扇出是填不满，节约了空间。比方下面例子的 RadixTree(radix = 256, s=8)，那么即使在第一级只有 t、A、i，也须要多调配 253 * 8 ~ 1Kbytes。调整 radix(span = lg(radix))是一种内存优化形式，但这进步了树高减少了缓存生效 [5]。2013 年，A(daptive)R(adix)T(ree)[6] 用自适应的节点类型来解决问题，用适宜数据分布的最紧凑的节点示意，而不是固定的 Node256。论文中 InnerNode 分为 Node4、Node16、Node80 和 Node256 这四种，依照理论须要的分叉数抉择，通过类摊派算法 (Amortization Alg) 复杂度分析方法，可证实实践上这棵树内存复杂度是 O(52N)，其中 N 是存储数据量。ART 论文提供了一种形式，在进步扇出升高树高的同时，还能大幅度降低内存开销。依照 ART 从新组织下面例子中的 RadixTree，如图所示。
05 HIT 优化，RC 实现 ShortList+LongList Leaf 的自适应
咱们定义 RC\_x 为不超过 x 个元素的间断存储空间，反对 Append-Only 和 Mark-Delete 操作，单元素额定老本不超过 8byte。接下来看 RC 的设计要点。
既然 RC 被设计为只反对 Append-Only/Mark-Delete 批改的数据类型，为此元数据需有 cursor 和 valids。同时针对不同容量的 RC，为了管制实践上单条数据损耗不超过 8byte，须要别离设计和实现，咱们不心愿引入继承 virtual 指针的内存开销，采纳依据 type 散发的实现计划。
RC1 元数据 8byte，可轻松包容 cursor 和 valids，那么下一阶的 RC\_x，x 是几呢？依照摊派分析方法，RC\_x 至多有 2 个元素，也就是 16byte 的估算，在调配前还是要先看选型，RC\_x 须要变长因而元数据还有留进去 8byte 给 dataptr，这样的话，valids 不能采纳 std::bitset<N>，因为 bitset 的实现至多须要一个字也就是 8byte。valids 和 cursor 用 bit field 的形式来做调配看上去还是比拟富余的，寄存 58 个数据元素都没问题，实际上思考到零碎分配器的特点，咱们并没有这样做。
支流的零碎分配器大部分是 slab-based，在理论利用时，除过实践单条数据损耗，还须要思考因内存池带来的对齐损耗。一方面，RC1 所在的链约占整体的 80%，这样海量的小对象适宜用内存池来治理，为防止检索时候多一次内存池地址转化，咱们把 vaddr 存储在元数据中，开释时再应用。另一方面，分散式地调配 N*sizeof(data)，会造成每类 slab 的外部非充沛应用，为此 RC16+ 采取了 Array of data\_array 的组织形式。
RC 设计有不少实现细节，包含什么时候一次性多申请多少空间，管制内存老本和操作效率。工夫关系就不多介绍了。
06 LeafCompaction 优化稠密
前缀树在缓存生效方面优于 BTree，ART 进一步地采纳自适应节点类型，既能减少扇出优化缓存拜访，又能管制内存损耗。然而理论利用中，ART 依然受到 key 值散布稠密的影响，这体现为在局部子树扇出很小很深（较 Node256），树高无奈全面升高，从而影响点查的缓存。HOT[7]提出一种自适应动静 span 晋升均匀扇出，进而升高树高的办法，具体来说，定义节点最大扇出 k，寻找一种树的划分，在每个划分的分支节点数不大于 k - 1 的前提下，沿着叶子到根的划分数的最大值取最小，这样的实际效果就是对于稠密段的 span 足够大，对于密集段的 span 足够小，整体扇出迫近最大扇出 k。如中图所示。
对于 ART+ 指标的连续性利用场景来说，仅仅晋升扇出升高树高是不够的，咱们发现存在扇出很高，但扇出后叶子数据很稠密，同时总数据量也不高，这显然影响了扫描性能。咱们提出叶子合并（LeafCompaction），它包含断定器和操作算法。给定一个分支节点，如果它被断定为合并，则用一个叶子节点替换它，该叶子节点的前缀同该树的前缀，内容是该树的数据，后续插入 / 删除过程听从叶子的操作形式；如果它被断定为不变，则放弃。给定一个叶子节点，如果它被断定为决裂，则用一颗树替换它，该树的前缀同该叶子的前缀，内容通过 BulkLoad 的形式生成，如果它被断定为不变，则放弃。断定器的默认算法根据子树均匀和总数，节点压缩率高达 90%。如图所示。
理论评测成果，均匀到单条数据的扫描性能，稠密场景下 LC 版本优于一般版本一倍。
07 RCU 面向读者实现读写平安
个别应用深度优化的细粒度锁来爱护倒排数据结构的并行操作，但锁竞争带来的性能抖动，齐全抹杀了访存优化，咱们必须摸索出一种无锁 (lock-free) 平安模式。提到无锁 lock-free，大家都感觉是 CAS，其实一方面 CAS 不是银弹，CAS 常见的写法是 whileloop 直到胜利，如果有 10 个线程都在高速批改一个链表尾巴，这时候 CAS 只是说把陷入内核省掉了，然而还是要不停地重做，这并不能齐全开释并行的能力，最好能从业务上打散。另一方面，CAS 也有问题，多核下 CPU cache coherence protocol 总线仲裁，导致毁坏流水线。
Read-Copy-Update 是 Linux 内核中的一种同步机制，被用来升高读者侧的锁开销，同时提供平安的写机制，具体地来说，多个读者（reader）并行地拜访临界资源，写者（writer）在更新临界资源（critical resource）时候，拷贝一份正本作为批改根底，批改后原子性替换掉。当所有读者开释了这个临界资源后（Grace peroid），再开释资源（reclaimer）。
Linux 还须要较简单的机制：
1、探测静止状态 Quiescent Status，当所有 CPU 都经验过至多一次静止状态时，才认为 Grace peroid 完结；
2、多写者间同步，防止失落批改。
对于检索服务来说，它有上面 3 个特点，这些特点大幅度地升高了咱们的设计复杂度：
1、单写者，咱们可能有其余的筹备线程并行做更重的筹备工作，但只有 Reload 单线程负责物料更新；
2、非事务，检索线程召回的多条数据间没有严格束缚；
3、读者持有工夫无限，检索线程有严格的超时要求。这些特点大幅度地升高了咱们的设计复杂度。
08 LearnedIndex 面向 Workload 自适应
最初，我再介绍下进行中的工作 L2I。方才都是对单链的优化缓存生效，已有不错的成果，但从更宏观全局的视角来看，咱们零碎还有可开掘空间：一方面，广告投放人造导致存在较多超短链，另一方面，须要扫描过程跨表查问做各类过滤逻辑等等。这些已不单单是数据分布的问题，而是在线流量和客户投放的匹配，须要用更智能的伎俩来解决。
行业外面，JeffDean&TimK 联结发表了 Learned Index[8]引入 RMI、CDF 的模型，后续 TimK 团队又有动态化、多维索引、sagedb 等多种方向的倒退，实质是构建面向负载的半自动化寻优零碎。咱们既要引入负载特色，但因为扫描过程很轻量，不能做过重的预测，同时作为对客户有承诺的商业系统，不能产生谬误。借鉴 L2I 的思维，咱们还做了两个事件，一方面、通过触发进口离线计算共现关系，用来合并超短链、短链，用上 HIT 的高性能的间断扫描能力；另一方面，取熵最大的组合 <pid,cid>，提取到倒排表的 bit 位，确定不过 1，否则为 0，对于后者 fallback 到点查计算。
——END——
参考资料：
[1] Software Engineering Advice from Building Large-Scale Distributed Systems, 2002
[2] Cache conscious indexing for decision-support in main memory,1999
[3] Making B+-trees cache conscious in main memory,2000
[4] FAST: fast architecture sensitive tree search on modern CPUs and GPUs,2010
[5] The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases,2013
[6] PATRICIA –Practical Algorithm To Retrieve Information Coded in Alphanumeric,1968
[7] HOT: A height optimized trie index for main-memory database systems, 2018
[8] The Case for Learned Index Structures, 2018
举荐浏览：
为什么 OpenCV 计算的视频 FPS 是错的
百度 Android 直播秒开体验优化
iOS SIGKILL 信号量解体抓取以及优化实际
如何在几百万 qps 的网关服务中实现灵便调度策略
深入浅出 DDD 编程
百度 APP iOS 端内存优化实际 - 内存管控计划
