Fork me on GitHub

百度广告倒排服务极致优化

百度技术 稿

导读

漏斗优化是检索系统不变的话题,过去一年来,广告漏斗优化一改往日做“加法”,而通过简化漏斗,提升全系统一致性。如百度这样庞大的广告库规模、高流量规模以及复杂的业务规则,要做到极简的漏斗层次,需要最高效的策略设计和最极致的工程实现。本文重点介绍了百度Geeker们在倒排数据结构上如何“抠细节”达到倒排召回无截断,对大家做高性能系统也将有所启发。

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,因为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%。如图所示。

image.png

实际评测效果,平均到单条数据的扫描性能,稀疏场景下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、读者持有时间有限,检索线程有严格的超时要求。这些特点大幅度地降低了我们的设计复杂度。

GEEK TALK

08 LearnedIndex面向Workload自适应

图片

最后,我再介绍下进行中的工作L2I。刚才都是对单链的优化缓存失效,已有不错的效果,但从更宏观全局的视角来看,我们系统还有可挖掘空间:一方面,广告投放天然导致存在较多超短链,另一方面,需要扫描过程跨表查询做各类过滤逻辑等等。这些已不单单是数据分布的问题,而是在线流量和客户投放的匹配,需要用更智能的手段来解决。

行业里面,JeffDean&TimK 联合发表了Learned Index[8]引入RMI、CDF的模型,后续TimK团队又有动态化、多维索引、sagedb等多种方向的发展,本质是构建面向负载的半自动化寻优系统。我们既要引入负载特征,但由于扫描过程很轻量,不能做过重的预测,同时作为对客户有承诺的商业系统,不能产生错误。借鉴L2I的思想,我们还做了两个事情,一方面、通过触发出口离线计算共现关系,用来合并超短链、短链,用上HIT的高性能的连续扫描能力;另一方面,取熵最大的组合<pid,cid>,提取到倒排表的bit位,确定不过1,否则为0,对于后者 fallback到点查计算。

参考资料:

[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


本文地址:https://www.6aiq.com/article/1671014333248
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出