共计 9090 个字符，预计需要花费 23 分钟才能阅读完成。
简介：本文钻研了一种新的过滤器 Ribbon Filter，并将其集成到 Lindorm 中作者：箫苏 朝戈 正研 1 前言 Lindorm 是一个低成本高吞吐的多模数据库，目前，Lindorm 是阿里外部数据体量最大，笼罩业务最广的数据库产品。超高的性能和低 RT 始终是 Lindorm 谋求的指标，因而 Lindorm 也在一直地优化和迭代，争取在每个小点上都做到极致。这次，咱们的优化的指标放到了 Lindorm 中的 Bloom Filter 上。
因为 Bloom Filter 只须要占用极小的空间，便能够给出”可能存在“和”必定不存在“的存在性判断，因而能够提前过滤掉许多不必要的数据块，从而节俭了大量的磁盘 IO。在 Lindorm 中 Get 操作就是通过使用低成本高效率的 Bloom Filter 来过滤掉大量有效的数据块的，从而大幅度降低磁盘 IO 次数。Bloom Filter 存储在了 Lindorm 的底层文件 LDFile 中。在长期的生产察看中，咱们发现，Bloom Filter 的空间占用远大于其余 meta 数据。在默认配置的错误率下，基本上 100MB 数据（压缩后），就会产生 1MB 以上的 BloomFilter，也就是 BloomFilter 会占掉 1% 的存储空间。对于磁盘存储空间来说，1% 的耗费并不多，然而，因为 BloomFilter 做为 Lindorm 读链路上的要害链路，通常须要缓存在内存中能力取得更好地性能。内存资源对 Lindorm 来说是十分贵重的资源，对于单机治理上 TB 数据的 Lindorm 节点来说，通常只有几 GB 到几十 GB 的内存来做缓存。依照通常的法则，上 TB 的数据会产生几十 GB 的 Bloom Filter，这些 Bloom Filter 会把缓存占满，导致数据无奈进入缓存，会重大影响用户申请的内存命中率。因而，优化 Bloom Filter 的大小，意味着能够缩小内存占用，让缓存可能加载更多用户数据，从而优化 Lindorm 的读性能。为了优化 BloomFilter, Lindorm 也做了不少尝试，比方引入 SuRF，但咱们发现，在空间占用率上，SuRF 并不比 BloomFilter 有劣势。因而，咱们把眼光转向了 2021 年的一篇论文《Ribbon filter: practically smaller than Bloom and Xor》。这篇论文提出了一种新的 Ribbon Filter，据论文的论断，Ribbon Filter 绝对 Bloom Filter 能够节俭 30% 的空间。这个对咱们来说是一个十分迷人的论断，节俭 30% 空间意味着能够开释 30% 的缓存空间，读申请的内存命中率会有很大一部分晋升。Ribbon Filter 真的有论文中说的那么神奇吗？带来空间节俭的同时，会带来副作用吗？本文将这一全新的 Ribbon Filter 给大家做一个介绍，而后咱们把 Ribbon Filter 引入了 Lindorm 中，并测试了 Ribbon Filter 在理论生产中的实在体现。2 基本原理 2.1 Bloom FilterBloom Filter 是 Bloom 在 1970 年提出的一种概率数据结构[1]，用来疾速测试元素是否是汇合的成员，存在肯定的假阳性率（个别设置为 0.01），不可能有假阴性率，即查问返回“可能存在”或者“肯定不存在”。能够增加元素到汇合中，但不能删除（有改良版本能够实现），增加的元素越多，假阳性率越大。对于给定的假阳性率 e 和元素数量 n，Bloom Filter 有一个最佳的空间大小，使得增加元素过程中，保障逐步变大的假阳性率小于等于 e。Bloom Filter 由一个长度为 n 的 01 数组 array 组成。首先会将 array 数组每个元素初始化设为 0，对于汇合 A 中的每个元素 w，做 k 次哈希，每次哈希值都会对 n 取模失去一个索引，比方第 i 次哈希，索引
，将 array 数组中的对应地位置为 1，最终 array 变成了一个局部元素为 1 的数组。对于待检测元素 w 同样会做 k 次哈希失去 k 个索引，如果数组中对应地位都为 1 则元素 w 可能存在汇合 A 中，否者肯定不存在。2.2 Xor FilterRibbon Filter 是基于 Xor Filter 做的，在介绍 Ribbon Filter 之前，得先理解 Xor Filter。Xor Filter 是 Thomas Mueller Graf 和 Daniel Lemire 在 2020 年提出的[2]，也是用来检测一个元素是不是汇合中的一个成员，相比 Bloom Filter，Xor Filter 外围差别次要是如下：Xor Filter 有固定的三个哈希函数，而 Bloom Filter 哈希函数由假阳性率确定；Xor Filter 采纳 XOR 形式按 slot 匹配，Bloom Filter 应用 AND 形式进行按位匹配；Xor Filter 由一个二维 bit 数组组成，Bloom Filter 是一个一维 bit 数组；Xor Filter 相比 Bloom Filter 最高能节俭 20% 的空间。输出的元素通过多个哈希函数生成的哈希值不会像 Bloom Filter 一样映射到一个 bit 位，而是映射到一个固定长度的 slot，一个 slot 有多个 bit 位，且每个 slot 的 bit 位数雷同。对于待检测元素 w，会通过 k 个哈希函数生成 k 个哈希值别离映射到对应 slot 上，而后对所有的 k 个 slot 中的元素进行异或运算失去后果 r，元素 w 还会通过另外一个独立的哈希函数生成指纹 fingerprint(w)，和 r 作比照，如果雷同则元素 w 可能存在汇合 A 中，否者肯定不存在。
接下来介绍 Xor Filter 的结构原理开始先介绍几个要害变量：B 寄存着的 r -bit 的 Xor Filtern 是参加构建 Xor Filter 的汇合 A 元素数量 k 是哈希函数的个数（固定值 3）m 是 slot 的个数 初始气节 r =5，n=3，k=3，m=9，B 所有元素为 0，元素 x，y，z 别离通过 3 个哈希函数映射到 3 个 slot 上，每一个元素通过一个独立的哈希函数生成指纹 f(x)=11010，f(y)=10000，f(z)=01110，
咱们能够看到 slot7 被元素 z 独享，所以 slot7 可能惟一标识 z，将 slot7 打上标记 z，并去除元素 z 的映射
此时 slot5 能够惟一标识元素 y，将 slot5 打上标记 y，并去除元素 y 的映射
当初只剩下最初一个元素 x，f(x)能够放在 slot1、slot3、slot6 任一地位，这里抉择 slot1，slot3 和 slot6 置为的 5 -bit 0，将 f(x) xor slot2 xor slot3 的后果放在 slot1 中，11010^00000^00000=11010，并回填其它带有标记的 slot，和后面操作一样 y 元素 slot5=f(y) xor slot1 xor slot6=10000^11010^00000=01010，z 元素 slot7=f(z) xor slot2 xor slot5=01110^00000^01010=00100
最终失去了构建好的 Xor Filter，测试的时候，待检测的元素 w 通过 3 个哈希函数失去对应的 slot 索引 h1(w)，h2(w)，h3(w)，以及通过另一个哈希函数失去指纹 f(w)，将指纹与 B(h1(w)) xor B(h2(w)) xor B(h3(w))进行比拟。如若相等，则示意元素 w 可能存在，否者肯定不存在。2.3 Ribbon FilterRibbon Filter 是 Peter C. Dillinger 和 Stefan Walzer 在 2021 年提出的 [3]，Ribbon Filter 主体是 Xor Filter 的实现，在其根底上构建能够高效运算的矩阵，从而利用矩阵自身的高效运算来解决 Xor Filter 构建过程中的反复操作，相比 Bloom Filter，Ribbon Filter 会耗费更多的 CPU，Ribbon Filter 的外围劣势在于节俭空间，所以会针对 Xor Filter 的二维数组的求解过程做计算优化，Ribbon Filter 会将二维数组的求解过程转化成解线性方程组 Ax=b，并利用了基于行列式的高斯消元法，线性代数中求解线程方程组时会用到行列式运算，高斯消元法就是在求解线程方程组的过程中，将一个行列式转化成上三角或者下三角矩阵。相比 Xor Filter，Ribbon Filter 次要差别如下：Ribbon Filter 哈希映射到数组间断的一片索引，而 Xor Filter 仅有的 3 个哈希函数每个都随机映射；Ribbon Filter 构建过程应用高斯消元法，Xor Filter 应用 Peeling 算法；Ribbon Filter 二维 bit 数组应用列式存储，Xor Filter 是行式存储；Ribbon Filter 相比 Bloom Filter 最高能节俭 30% 的空间。让咱们看一下上节 Xor Filter 的元素 w 的查问测试过程，哈希映射用 h(x) 示意，
，
，
，即
= B[2] xor B[4] xor B[7]，那是不是能够示意成
，其中
是元素 w 哈希映射的特征向量，第 2,4,7 位为 1（索引从 0 算起），对应了
，
，
的值，Z 是二维 bit 数组 B 的矩阵模式，
，同时留神
计算过程中加法运算要变成异或 XOR 运算。能够计算出 query(w)=00100，
=
上节 Xor Filter 的构建过程能够用线性方程组示意成：
，二维 bit 数组 B 能够通过求解该方程组失去，方程组的系数矩阵为
，第 1 行对应了元素 x 哈希映射的特征向量，第 2 行 y，第 3 行 z。除了引入矩阵运算，Ribbon Filter 还对二维 bit 数组的存储构造进行了调整，在 Xor Filter 中每个 slot 的 r -bit 间断存储，且保障第 i 个 slot 中所有的 bit 都在第 i + 1 个 slot 的 r -bit 后面，这种称为行式存储构造，而 Ribbon Filter 应用列式存储，保障每 w 个 slot 的第 j 个 bit 都在第 j + 1 个 bit 后面，w 是 Ribbon Filter 哈希映射到的间断索引的宽度，个别 w >>r，如果应用行式存储，查问的时候须要从内存读取所有的 w 个 r -bit，而后做异或计算失去后果并与指纹比照，当初应用列式存储，能够先读取第 1 个 w -bit，做一下异或计算并将后果与指纹的第 1 个 bit 比拟，如果不同则示意查问的元素不在汇合内，间接返回 False，否者持续读取接下来的 w -bit 并反复之前的过程。列式存储带来的益处有：查问过程不必读取所有的 bit，缩小查问工夫；对空间更敌对，拜访 w 个间断内存空间变成了拜访 r 个间断内存空间。个别 w =64，r=7。2.4 性能比照根据 Ribbon Filter 论文的性能比照论断，咱们提取出本文关怀的 Bloom，Xor，Ribbon 三者的性能比照。这里的 key 用的是 long 数据类型，Construct 包含增加 key 和求解方程。Filterfalse positive ratespace overheadns/key，n=10^6，Constructns/key，n=10^6，QueryBlockedBloom1%52.0%1114Xor1/2^8≈0.39%23.0%14815Ribbon1/2^7≈0.78%10.1%8339 从表中能够看出：Ribbon 构建工夫是 BlockedBloom 的 7.5 倍；Ribbon 查问工夫是 BlockedBloom 的 2.8 倍；Ribbon 空间开销是 BlockedBloom 的 72%（(1+10.1%)/(1+52.0%)），节俭了 28%。通过文章中的比照，咱们发现 Ribbon Filter 尽管比 Bloom Filter 节俭了 28% 的空间，但构建工夫和查问工夫都有了一些显著的回升。初看是一个工夫换空间的做法，不过，论文中选用的 Bloom Filter 是 BlockedBloom，这是 2019 年提出的一个基于 Bloom Filter 的优化版本[4]，自身性能就曾经比拟好，而且测试的 Filter hash function 都是针对 long 值的，而 Lindorm 中的 Bloom Filter 是针对 byte 数组做 hash 的，性能体现可能不完全一致。因而，Ribbon Filter 是否能在任何场景下都能 Lindorm 带来性能晋升，须要咱们把 Ribbon Filter 引入 Lindorm 中，在生产环境做一些测试。3. 利用 Ribbon Filter3.1 外围逻辑的实现咱们参考论文中的 Ribbon Filter 应用 Java 进行了实现并集成到 Lindorm 中。论文中有一种空间开销更小的优化版本的 Ribbon Filter，然而它不能保障结构胜利，须要重试，这在 Lindorm 中是不能承受的，Lindorm 中构建过滤器是不能失败的，否则会导致 Flush 或者 Compaction 失败。所以咱们最初选用了宽度 w =64 的 Homogeneous Ribbon Filter。最终的实现有一些工程上的取舍，因而与论文还是存在一些差别：论文中实现的 Ribbon Filter 应用的 key 类型是 long 型，在 Lindorm 中每个 key 是一个 byte 数组；论文中实现的 Ribbon Filter 构建的时候间接提供一个 key 数组，然而在 Lindorm 中 key 是流式的一个个来，并且数量未知；论文中实现的 Ribbon Filter 构建提供 key 数组的大小 n 是已知的，能够通过公式
（错误率 f 已知）失去 Ribbon Filter 的空间大小，然而 Lindorm 中只提供空间大小 bitSize 和错误率 f，key 数量 n 未知，须要反向求出 n；论文中实现的 Ribbon Filter 输入的是一个 long 型数组，然而在 Lindorm 中得是一个 ByteBuffer 能力对立存到文件系统中；论文中实现的 Ribbon Filter 查问过程能够应用类中全副两头变量，然而在 Lindorm 中查问函数是动态的，只有少部分 meta 信息和存有 Ribbon Filter 的数据块能够应用。Ribbon Filter 的构建：Bloom Filter 构建过程只须要增加元素即可，增加完了就构建完了，然而 Ribbon Filter 构建过程还包含求解方程阶段，这个阶段是最耗时的，这个阶段放在哪个中央在什么工夫由谁调用来执行，会不会影响性能是一个大大的问题。目前是放在 Ribbon Filter 的写过程中执行，写之前会先求解方程，性能影响目前还没发现。Ribbon Filter 的查问：Bloom 只须要大量的 meta 信息而后按需加载须要的 Bloom Block，就能够实现查问过程，meta 信息有 VERSION,byteSize,hashCount,hashType,keyCount。Ribbon 不须要 hashCount 字段，其它都要，除此之外还须要 numStarts（哈希映射到的区间下限），upperNumColumns（指纹位数的向上取整），upperStartBlock（批示 floor(r)位的 slot 与 ceil(r)的 slot 的分界），后续引入失败重试机制还得有哈希种子 seed 字段。为了不扭转 meta 信息的长度，只将 hashCount 变成了 slotCount（slot 的数量），都是 int 类型，numStarts = slotCount-63，upperNumColumns = (ribbonBitSize + slotCount – 1) / slotCount，upperStartBlock = upperNumColumns (slotCount >> 6) – (ribbonBitSize >> 6)，这样就完满了，从物理存储层是不太能看出 Bloom meta block 和 Ribbon meta block 的区别的，既没增字段也没减字段也没批改字段类型。3.2 初步测试本次 benchmark 比照的是在 Lindorm 中利用的 Bloom Filter 和 Ribbon Filter。这里的 key 用的是 byte 数组类型，key length 是 byte 数组大小；错误率都为 1%，hash 类型都是 murmur，Construct 包含增加 key 和求解方程。1. Construct，构建 filter，单位是 ns/key, n=10^6，下同。key lengthRibbon,ns/key, n=10^6Bloom,ns/key, n=10^6ratio (Ribbon:Bloom)10109.926136.01280.82%25143.178164.24787.17%50196.083227.89886.04%250334.312467.88471.45%20001375.1652006.23568.54% 能够看到，在 Lindorm 中，随着 Key 长度的增长，构建 Ribbon Filter 的速度反而会更快。2. Query，查问 key lengthRibbon,ns/key, n=10^6Bloom,ns/key, n=10^6ratio (Ribbon:Bloom)1020.82722.13594.09%2538.28544.76485.53%5051.73070.07573.82%250147.951256.86357.60%20001125.7602230.20050.48% 能够看到，在 Lindorm 中，随着 Key 长度的增长，查问 Ribbon Filter 的速度反而更快。3. space load，空间负载跟 key length 无关 key lengthRibbon,bit/key, n=10^6Bloom,bit/key, n=10^6ratio (Ribbon:Bloom)7.2329.58575.45% 从初步测试的后果来看，仿佛测试论断比论文中更好，无论查问速度，构建速度，Ribbon Filter 都比 Bloom Filter 更优。咱们剖析，这是因为 Lindorm 中原来应用的 BloomFilter 是一个没有优化过的原始版本，而且 Bloom Filter 查问时须要屡次执行 hash 函数，而 hash bytes 的耗费比论文中 hash 数字的耗费要大的多，因而 Ribbon Filter 的查问性能并没有论文中说的那么差，反而随着 key 的长度变长，查问的性能要强于原有的 BloomFilter 实现并且差距越来越大。构建 Filter 时的论断也相似，随着 key 长度的回升，RibbonFilter 的构建速度更快，齐全优于 Bloom Filter。但在生产过程中，构建过滤器只占 Lindorm 生产 LDFile 全过程中的很小一部分，基本上不会对 Lindorm 文件的生成速度造成影响。在空间上，雷同的错误率下，Ribbon Filter 的确能比 Bloom Filter 节俭 25% 的空间。基于以上测试论断，咱们感觉应用 Ribbon Filter 代替 Bloom Filter，无论从哪个角度上来说，都是一个不错的抉择。3.3 生产测试咱们把 Ribbon Filter 集成在 Lindorm 宽表引擎中，进行了全链路的压测，压测机器的配置为 4 核 8GB，应用 ESSD 存储，压测工具用的是 ycsb 本次测试的是批量读的吞吐量比照测试和提早比照测试，以及读取过程中的缓存命中率比照测试，以及 major compaction 性能比照测试。读取测试依据 rowKey 的字节数的不同分为四个场景：10bytes，25bytes，50bytes，300bytes。测试表单节点散布，load10 亿行数据，每行数据一个列族，共 5 列，每列 value 20bytes，每行数据大略 0.1kb，表大小 100G 左右，批量读一次 20 行。批量读吞吐量比照
批量读均匀提早比照
读取过程中的缓存命中率比照
单节点 major compaction 性能比照（cpu 打满）
Filter 的 meta 信息比照指标 Bloom FilterRibbon FilterSize（bytes）119930889043968No of Keys99998339999833Max Keys1000149910005000Percentage filled100%100%Number of chunks9269 生产的测试证实了咱们在 3.2 节实践剖析的后果。引入 Ribbon Filter 后，读的吞吐最高有了 18% 的晋升。读 RT 有了最高 15% 的降落。吞吐的晋升和 RT 的降落次要来源于应用 Ribbon Filter 后，过滤器空间的缩小和内存命中率的晋升。并且在不同的 key 大小下，Ribbon Filter 均有好过 Bloom Filter 的体现。在 Compaction 的比照测试中，大家也能够看到，应用 Ribbon Filter 与否对 Compaction 的速度根本没有影响。4 总结本文钻研了一种新的过滤器 Ribbon Filter。咱们依据论文的思路在 Lindorm 中进行了实现。通过测试，咱们发现 Ribbon Filter 可能节俭 25% 的过滤器空间占用，从而在各种条件下晋升 Lindorm 的读性能。Lindorm 将在下一个版本中集成 Ribbon Filter，带给用户极致地性能体验。另外，为了保障 Ribbon Filter 构建不失败，咱们选用了一种空间占用绝对较多的实现，咱们将在 Ribbon Filter 的根底上持续做了一些摸索，保障构建不失败重试的前提下，进一步节俭过滤器的空间。参考文献[1]Burton H. Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (1970), 422–426.[2]Thomas Mueller Graf and Daniel Lemire. 2020. Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters. ACM J. Exp. Algorithmics 25 (2020), 1–16. https://doi.org/10.1145/3376122[3]Dillinger, Peter C. and Stefan Walzer.“Ribbon filter: practically smaller than Bloom and Xor.”ArXiv abs/2103.02515 (2021).[4]Harald Lang, Thomas Neumann, Alfons Kemper, and Peter A. Boncz. 2019. Performance-Optimal Filtering: Bloom overtakes Cuckoo at High-Throughput. Proc. VLDB Endow. 12, 5 (2019), 502–515. 原文链接：http://click.aliyun.com/m/100… 本文为阿里云原创内容，未经容许不得转载。
