最近在研究LSM tree,听闻bitcask在LSM tree各种各样的应用中是一个比较简单的实现,所以就以它为突破口,了解下LSM tree真实世界的实现。
bitcask存储模型由Riak提出,github上有各种语言的实现,本人挑选了一个golang版本的实现来进行研究,源码地址是:git.mills.io/prologic/bitcask,学习过程中我添加了一些注释,有需要的同学可以参考下:github.com/Orlion/bitcask
与LSM tree的基本思想一样,bitcask中所有增删改操作都是追加写磁盘中的datafile,其数据结构如图:
实际文件中是没有换行的,每个entry都是与前一个entry紧密串联在一起的,这里只是为了体现出来一个一个的entry。
datafile由一个一个的entry组成,每个entry的前4个字节存储key的size,第二个8字节存储value的size,然后顺序写入key和value,再写入校验和和过期时间的unix时间戳
datafile写入完成后可以得到新写入项的offset,然后将该key对应的offset与写入的数据项的size写入到内存的索引中,prologic/bitcask
索引使用了art
即Adaptive Radix Tree(自适应前缀树)
作为索引的数据结构,虽然不如hash表查找速度快,但因为是树状结构所以可以支持范围查找。
当datafile写入到一定的大小时会创建一个新的可读可写的datafile,在此之后的新数据会写入到这个新datafile中,老datafile会被设置为只读。因此一个bitcask实例会有多个datafile,所以索引中还必须存储key所在文件的id。
上面提到bitcask中删除修改数据也是顺序写磁盘,那么写入的是什么样的数据呢?
实际上,bitcask中修改数据与写入数据是同一个api,即都是Put(key, value []byte)
,所以修改key也是往datafile中追加写一个新entry,不同是会修改索引中key的指向为最新数据项在文件中的位置。
而删除数据其实就是put(key, []byte{})
即向datafile写入空字节切片,写完之后会删除索引中的key。
get(key)
时会先从内存的索引树中根据key找到key所在的文件id和offset以及size,然后通过mmap
到对应datafile文件中offset处拉取entry,然后根据前12个字节处的key len与value len数据指示解析出key和value,检查下校验和,自此数据检索完成。
由于bitcask中增删改都是追加写文件,不可避免的磁盘占用会越来越多,所以需要在合适的时机执行merge
操作,将old entry和deleted entry从磁盘中清理掉。
bitcask Merge的过程如下:
merge
子目录,以merge目录为工作目录创建merge用的bitcask实例:mdb
上文提到索引是存储在内存中的,这样的话进程重启后索引就需要重新构建,如果数据量多的话,可想而知进程启动得多慢。
所以bitcask中会在以下几个时机将内存中的索引持久化到磁盘中:
创建bitcask实例时,会检查工作目录下的索引文件,如果有索引文件,会将索引文件加载到内存中生成art索引树,然后判断索引文件是否是最新的,即索引文件生成后有没有新数据写入,如果不是最新的还需要从最新的datafile中读取数据到索引中。
如果没有索引文件则会遍历所有的datafile,遍历所有数据来构建索引。
可以看到bitcask的实现还是非常简单(lou)的。put(k, v)
加了全局锁,锁粒度较粗,并发读写性能应该不是很强。merge的过程要遍历所有的datafile,还要创建新文件,所以对系统的IO压力应该也比较大。