wiredtiger LSM trees bloom filter 设计原理

作者:神秘网友 发布时间:2020-09-07 10:25:28

wiredtiger LSM trees bloom filter 设计原理

wiredtiger LSM trees bloom filter 设计原理

最近在做的调研中,其中包括了mongodb wiredtiger LSM trees bloom filter 部分,秉承着好记性不如烂笔头的原则, 做个简单的记录,不保证完全正确,欢迎讨论交流。

bloom filter 来源

wiredtiger 也提供了LSM trees 的结构作为持久化存储, 当in-memory tree 大小达到阈值后, 新的in-memory tree会被创建, 旧的in-memory tree会被刷到磁盘。LSM trees 天然支持更快写操作,然而对读操作就不怎么友好了。所以为了增加读性能,bloom filter诞生了。相当于在每个物理存储的 tree 前面加了一个filter, 更快速的定位到key 是否存在这个物理块中。

hash & bitmap

bloom filter 是一个bitmap。
一个key 被k个hash 函数计算以后产生 k个bit, 在bitmap中置这k个bit 为1, 盗图展示如下:
wiredtiger LSM trees bloom filter 设计原理
读key的时候, 所有k bit =1 的情况下, key存在。有任何一个bit=0的情况下, key不存在。 这个bitmap 也是一个持久化存储的file, 体量小,耗io少,而且查找快, 能大大提供读性能。

问题

然而这个设计对删除数据就不怎么友好了,继续盗图看下:
wiredtiger LSM trees bloom filter 设计原理
因为每个bit是跟其他key有关联的, 将其中一个bit置为0 的话,也会影响其他的呢。那如何解决呢? 我找到的资料中提供了万能的引用计数法:
wiredtiger LSM trees bloom filter 设计原理
看下是不是很耗空间,本来一个bit就够了,现在就是4个字节都要担心有没有溢出的问题。 所以wiredtiger 是这么用的, delete 操作会产生一个empty value, 而不是在每条记录追加一个delete 标志, 但这样的话查找一个已经的delete的数据就会和正常的数据消耗的一致。在没看过代码的情况下,目前官网放出来的资料就是这么做的。

合并

跟其他LSM trees设计一样,wiredtiger也会合并文件,主要为了缩小空间使用和加快read 操作。 合并文件也会对bloom filter 进行一个OR的操作。这两个操作可以并行进行。另外合并后对旧文件的删除也是使用引用计数的方式,只有计数为0才会删除,所以也不会锁操作的行为。

wiredtiger LSM trees bloom filter 设计原理相关教程

  1. LSM303DLHC
  2. Java集合框架(Set与MapHashSet与HashMapTreeSet与TreeMap)
  3. Java集合框架16-TreeSet
  4. Java中利用Collections、HashMap、TreeSet混合使用Demo
  5. CF #420 B. Okabe and Banana Trees
  6. Codeforces 821 B. Okabe and Banana Trees
  7. Van Emde Boas Trees
  8. Codeforces 821B-Okabe and Banana Trees