简介： 本文钻研了一种新的过滤器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...本文为阿里云原创内容，未经容许不得转载。