论文中使用了两组key的数据进行性能对比测试。 一组是由YCSB输出的64bit的整数, 另一组是由字符串组成的电子邮件地址,,其中整数的key有50M个,电子邮件地址组成的key有25M个。相关细节如下:
1. FPR对比
首先对比了SuRF不同模式和布隆过滤器在FPR上的对比:
一般情况,在point query下,SuRF比bloom filter还是要差一些。从该图的中间部分可以看出,随着SuRF-Hash的hash后缀的bit位数的增加,它对range query起不到任何作用。该图的右侧的Mixed query说明,随着后缀的长度的增加,SuRF-Real对Point和Range query都可以增强作用,所以它下降的最快,而 SuRF-Hash只对Point query起作用,所以它的后缀增加到一定后,只是将Point query的FPR降低了,但是Range query的FPR不会变化,而在整数和Email的实验中SuRF-Real和SuRF-Mixed的变化趋势不同,是因为在整数中后缀添加一个bit,这个 值变化很大,区分度高,但是相对于字符串,特别是邮箱,后缀添加一个bit,即便是一个字节,区分度可能不高(比如ttttttx@cs.cmu.ed和tttttts@cs.cmu.ed)
2. 性能对比
SuRF的不同模式和bloom filter的吞吐对比,吞吐实际上指的是查询速度。
可以看出无论是Point,Range,还是Mixed Query下,SuRF的三种模式吞吐量差别不大,而且在做Point Query时,布隆过滤器的吞吐量还是相对高的。
应用场景测试
作者对RocksDB的过滤器做了些改动,提出了四种场景的RocksDB的测试案例
(1)no filter
(2)Bloom filter (14 bits per key)
(3)SuRF-Hash (4 bit suffix per key)
(4)SuRF-Real (4 bit suffix per key)
实验的数据集是100G,查询的key是随机产生的。作者首先做的是性能对比
上图左侧表示的是Point query的性能对比,可以看出添加布隆过滤器后,查询时涉及的磁盘IO最少,它的吞吐量最大;图中右侧表示Range query的性能对比,此时SuRF的两种变体就有一些性能上的提升。
接下来作者为了更大程度的显示SuRF的优势,于是做一组关于在range query时,故意设置一些查询语句返回为空时的性能对比试验。并逐渐增加这些查询语句在所有查询语句的比例。
从图中可以看出随着查询中查询结果为空的比例不断增多,SuRF的性能就会不断的提升,而带布隆过滤器的SuRF的性能始终没有任何变化。
总结
文中的SuRF是一种即支持Point query又支持Range query的过滤器结构
如果具体应用中针对Point query的FPR的要求很高,布隆过滤器则比SuRF更好。但是如果查询中出现empty result的情况很多的话,且关注性能的提升时,可以使用SuRF结构。