1。业务背景-大家都知道整个系统是无限的。广告漏斗包括召回、粗选、精选三部分。理想的漏斗在顶部和底部非常规则。由于种种原因，漏斗变得有点浮动，这种不一致会给业务的继续发展带来很多复杂性。我们希望实现：一致的模型、精简的漏斗和全系统的无限。我们对Limitless的理解：细节中见真情，挑战软件工程性能极限，让漏斗逼近不截断。今天想和大家聊一聊我们是如何在《BSLimitless》这个项目中挖出细节的。整个项目其实是非常具有挑战性的，涉及到网络、计算、存储的方方面面。很难在一篇短文中解释清楚，所以我决定选择数据结构。-倒转表格，让大家感受“极致”的优化。2.技术背景-发帖列表先介绍一下优化前的发帖列表。它的构成比较经典，HashMap。检索pv根据触发的N个词（keysign）扫描拉链（SkipList）。广告业务投放的特点自然会有长链和超长链。因此，链表需要有序。做过漏斗的同学都知道，在reversestage其实可供排序的信息很少，这也说明了scanningLimitless对业务的高价值。这么小的数据结构就承载了各方的需求。1、读性能决定了在有限的时间内能释放多少。2.实时插入决定了客户的部署是否可以立即生效。3、单体数据库体积庞大，内存消耗低。工程的合理要求确实是both...and...and....在Limitless的背景下，我们需要大幅提升1来实现scanlimitless，而不是damage2和3。回过头来看，什么是Limitless的瓶颈是这么简单的数据结构？让我们回顾一下计算机体系结构的内容。CPU不直接访问内存，而是通过层层缓存到达内存。存储级别越低，其容量越大，但延迟也越高。mem、L2和L1之间存在一个数量级的差距[1]。List的数据结构明显缺乏空间局部性。缓存不兼容列表和缓存友好数组之间的扫描有多糟糕？我们做了如下测评，其中横轴代表链长或阵列长度，纵轴代表扫描到单个元素的平均时间，结果差距10+。用数组替换它也是不可接受的。客户要求实时效果，低效拷贝丢失需要O(2N)的增长率，无法满足内存成本需求。3.解决方案——HybridIndexTable我们针对业务特点和Limitless的需求进行了设计和优化，推出了新一代内存数据结构HybridIndexTable，简称HIT。升级倒排表：使用HashMap索引keysign，短链连续存储，长链是树叶连续存储的前缀树。前缀树是指业界的AdaptiveRadixTree，简称ART，shortchainandleaf)continuousstorage都是使用自研的RowContainer，简称RC。除了短小的数据结构，我想跟大家分享两个关键的细节：keysequence是有序的，底层的超长链是有序的，RC是无序的，以单元为单位进行扫描钢筋混凝土。像HIT这样的数据结构有以下三个优点，刚好满足前三个要求。高读性能，连续存储+前缀树减少cachemiss，线程安全方式对读者友好，面向负载优化；更新时效性高，连续存储但只能追加/标记删除；记忆损失少，大量应用自适应算法。HIT上线后，取得了可观的商业效益。无限之路上的技术就是生产力！4.HIT的起源，内存索引的探索ModernCPU内存索引领域为ModernCPU深耕。由于ModernCpu运行速度非常快，缓存一致性和内存访问的影响成为了高性能的瓶颈。In-memoryindexing在2000年代也有一些阶段性的成果，包括FAST[4]，这是典型的面向架构的数据结构设计，无论在思想还是成果上都非常适合静态数据；CSBtree[2][3]，其中提出数据结构用KV分隔，这样可以在一次内存访问中比较多个key。同时提出了SMO的无锁解决方案；还有ART前缀树[5]。大部分是有序索引中的BTree，为什么会注意到前缀树呢？每次访问下一个节点都会发生链表类型的缓存失效，缓存失效复杂度为O(n)。排序树类型的缓存失效发生在访问下一层节点时，缓存失效复杂度为O(lgn)。对于前缀树，缓存失效只与key长度k(len)/fan-outs(pan)有关，缓存失效复杂度为O(k/s)。如下图[5]所示，假设k为密钥长度的位数，随着存储数据量增加2^(k/8),2^(k/4),...，完全平衡树的高度继续增加，分别为k/8，k/4，...，而对于前缀树，对于给定的span，树高是恒定的，例如对于span=8和4，树高分别为k/8和k/4。前缀树对缓存更友好。这里简单介绍一下前缀树。英文是Trie，PrefixtreeorDigittree。左图是维基百科的例子。这是一个没有任何优化的典型前缀树。级，如客栈；另一方面，由于分支节点需要分配2^s*指针的内存，对于实际扇出很少的场景来说，内存损失非常大。RadixTree是一种前缀树，通过合并前缀（PathCompression）来优化内存。合并前缀是指压缩只有一个子节点的分支节点，使得现有节点要么是叶子节点，要么是有叉子的分支节点。名字中的radix=2^span，在radix=2的情况下也叫Patriciatree[6]。LinuxPageCache使用RadixTree进行页面缓存，以太币ETH的核心数据结构是MerklePatricia树。中间的图是根据RadixTree重新组织的。即使有合并前缀，空间也会被浪费，因为大部分扇出都没有被??填充。比如上例中的RadixTree(radix=256,s=8)，即使第一层只有t、A、i，也需要多分配253*8~1Kbytes。调整基数（span=lg(radix)）是一种内存优化方法，但这会增加树的高度并增加缓存失效[5]。2013年，A(daptive)R(adix)T(ree)[6]使用自适应节点类型来解决这个问题，使用最紧凑的适合数据分布的节点表示，而不是固定的Node256。论文中将InnerNode分为四种：Node4、Node16、Node80、Node256。根据实际需要的fork数，可以证明这棵树的内存复杂度为O(52N)，其中N为存储数据量。ART论文提供了一种在增加扇出和降低树高的同时大大减少内存开销的方法。按照ART对上例中的RadixTree进行重组，如图。5、HIT优化，RC实现ShortList+LongListLeaf的适配我们定义RC_x为不超过x个元素的连续存储空间，支持Append-Only和Mark-Delete操作，单个元素的额外开销不超过8字节。接下来看看RC的设计要点。由于RC旨在仅支持由Append-Only/Mark-Delete修改的数据类型，因此此元数据需要游标和有效值。同时，对于不同容量的RC，为了在理论上控制单个数据条目的丢失不超过8个字节，需要单独设计实现。我们不想引入继承虚指针的内存开销，采用按类型分配的实现方案。RC1元数据是8个字节，可以轻松容纳cursor和valids，那么下一层的RC_x，x是什么？按照分摊分析的方法，RC_x至少有2个元素，即16字节的预算。分配之前，还是需要看一下选择。RC_x需要更长，所以还剩下8个字节给dataptr用于元数据。在这种情况下，valids不能使用std::bitset，因为bitset的实现至少需要一个word，也就是8byte。看来valids和cursor用位域的方式分配还是比较够用的，存58个数据元素是没问题的。事实上，考虑到系统分配器的特点，我们并没有这样做。大多数主流系统分配器都是基于平板的。在实际应用中，除了理论上的单条数据丢失外，还需要考虑内存池带来的对齐丢失。一方面，RC1所在的链约占整体的80%，因此大量的小对象适合由内存池管理。为了避免在检索时内存池地址多一次转换，我们将vaddr存放在metadata中，释放时使用。另一方面，N*sizeof(data)的分布式分配，会造成各类型slab内部使用不足。为此，RC16+采用了data_array的Array的组织方式。RC设计有很多实现细节，包括何时申请更多的空间，控制内存成本和运行效率。时间关系我就不多介绍了。6.LeafCompaction优化的稀疏前缀树在缓存失效方面优于BTree。ART进一步采用自适应节点类型，不仅可以增加扇出来优化缓存访问，还可以控制内存丢失。然而在实际应用中，ART仍然受到键值稀疏分布的影响。这说明部分子树的扇出很小很深（对比Node256），树高无法完全降低，从而影响了枚举的缓存。HOT[7]提出了一种自适应动态跨度的方法来增加平均扇出，然后降低树的高度。具体来说，定义节点的最大扇出k，找到一个树的划分。每个部门的分支节点数量不同。在大于k-1的前提下，沿叶子到根的分区数最大值为最小值。这样做的实际效果是稀疏段的跨度足够大，密集段的跨度足够小，整体扇出接近最大扇出k。如中图所示。对于ART+目标的持续应用场景，仅仅增加扇出和降低树高是不够的。我们发现扇出很高，但是扇出后叶子数据很稀疏，总数据量也不高，明显影响扫描性能。我们提出了LeafCompaction，它包括一个决策器和一个操作算法。给定一个分支节点，如果确定要合并，则将其替换为叶子节点，叶子节点的前缀与树的前缀相同，内容为树的数据，后续插入/删除过程遵循叶子的操作模式；如果判断不变，则保留。给定一个叶子节点，如果判断它被分裂了，就用前缀与叶子相同的树替换它。内容由BulkLoad生成，如果判断没有变化，则保留。decider的默认算法是基于子树的平均数和总数，节点压缩率高达90%。如图所示。实际评测结果表明，单条数据的平均扫描性能，LC版本在稀疏场景下是普通版本的两倍。7、RCU为读者实现读写安全。一般采用深度优化的细粒度锁来保护倒排数据结构的并行操作。但是锁竞争带来的性能抖动完全抹杀了内存访问优化。锁（无锁）安全模式。说到无锁，大家都认为是CAS。事实上，一方面，CAS并不是灵丹妙药。CAS的常用写法是while循环，直到成功。如果有10个线程在高速修改一个链表的尾部，这时候CAS只是说把Falling放到kernel里省了，但还是要不断重做。这样并没有完全释放并行能力，最好还是从业务上拆分开来。另一方面，CAS也有问题。多核下的CPU缓存一致性协议总线仲裁导致流水线被破坏。Read-Copy-Update是Linux内核中的一种同步机制。它用于减少读取端的锁开销并提供安全的写入机制。具体来说，多个读者（readers）并行访问临界资源，写更新临界资源时，写者（writer）复制一份副本作为修改的依据，修改后自动替换。当所有读者都释放了这个临界资源（Graceperiod），再释放资源（reclaimer）。Linux还需要更复杂的机制：QuiescentStatusdetection。当所有CPU都经历过至少一种静止状态时，Graceperiod被认为结束；同步多个编写器以避免丢失修改。对于检索服务，它有以下三个特点，大大降低了我们设计的复杂度：对于单个writer，我们可能有其他准备线程并行做更重的准备工作，但只有Reload单线程负责素材更新;非事务性，对检索线程召回的多条数据没有严格的限制；读者持有时间有限，检索线程有严格的超时要求。这些特性大大降低了我们设计的复杂性。8.LearnedIndex适配Workload最后介绍下正在进行的工作L2I。刚才单链的优化缓存失效，取得了不错的效果，但是从更宏观和全局的角度来看，我们的系统还有探索的空间：一方面是超短链多了自然造成的通过广告，另一方面，扫描过程中需要跨表查询做各种过滤逻辑等等。这些不仅仅是数据分发的问题，而是在线流量与客户投放的匹配，需要通过更智能的手段来解决。在业界，JeffDean&TimK联合发布了引入RMI和CDF模型的LearnedIndex[8]。TimK团队跟进了动态、多维索引、sagedb等开发方向。其实质是构建一个面向负载的半自动优化系统。我们需要引入负载特性，但是因为扫描过程很轻，所以我们不能做重的预测。同时，作为一个对客户有承诺的商业系统，我们不能出错。借鉴了L2I的思想，我们也做了两件事。一方面，通过触发出口离线计算同现关系，用于合并超短链和短链，利用HIT高性能的连续扫描能力；另一方面，取熵最大的组合，提取postinglist的bit。判断不大于1，否则为0。对于后者，回退到point-check计算。参考资料：[1]SoftwareEngineeringAdvicefromBuildingLarge-ScaleDistributedSystems,2002[2]Cacheconsciousindexingfordecision-supportinmainmemory,1999[3]MakingB+-treescacheconsciousinmainmemory,2000[4]FAST:fastarchitecturesensitivetreesearchonmodernCPUsandGPUs,2010[5]TheAdaptiveRadixTree:ARTfulIndexingforMain-MemoryDatabases,2013[6]PATRICIA--PracticalAlgorithmToRetrieveInformationCodedinAlphanumeric，1968[7]HOT：主内存数据库系统的高度优化trie索引，2018[8]学习索引结构案例，2018
