leveldb 的压缩原理

层级压缩

Jx6znO.png

为什么需要压缩

因为 sstable 文件越来越多,会耗尽磁盘空间,并且也会影响查找效率,所以需要压缩和合并 sstable。我们把修改、删除都当作添加操作导致了 sstable 中有大量冗余数据,所以压缩就是保留最新数据,丢弃旧数据。

日志文件

假设用户新增一个键值对,如果我们修改 memtable 后就返回成功给用户,然后系统立刻崩溃重启,用户就会发现新增成功,但是找不到该数据。所以,为了防止系统崩溃时丢失最新数据,在处理用户请求之前,先往日志文件中追加一条记录,再修改 memtable。只要日志文件中有操作记录,即使系统崩溃了,用户数据也不会丢失。(因为重启后,系统可以根据日志文件重新构建一个完整的 memtable

那么每次写操作都要写文件,对性能会不会有影响呢?相比纯内存操作,多了写文件的操作,性能肯定会下降。但是我们获得了持久化的存储,这样的性能代价也是能接受的。而且,往日志文件中追加记录属于顺序写,理论上能达到磁盘I/O的速率,也不会太慢。

Level 0

每处理一个用户请求,日志文件就会多出一条日志记录。随着时间的流逝,日志文件会越来越大,直到超过一个固定大小(默认1MB),

  • memtable 的内容写到一个不可修改的 sstable 文件中(存储在磁盘上)
  • 添加这个新的 sstable* 到 Level-0

当 Level-0 的文件数量达到某个阈值时(当前是4),Level-0 的所有文件将与 Level-1 中(和 Level-0 )重叠的文件合并,生成一系列新的 Level-1 文件(Level-1 中每个文件的大小为2MB)。

Level-0 的特殊之处在于:处于 Level-0 的 sstable 的 key space 可能是互相重叠的。

Level >= 1

Level >= 1 :处于同一层级的 sstable 的 key space 不会重叠。

当 Level-T 的大小超过它的限制时,我们就会在一个后台线程中压缩它。这个压缩线程会从选择 Level-T 的某个文件和 Level-(T+1) 中重叠的所有文件,然后合并它们,生成一系列新的 Level-(T+1) 文件。每个文件大小默认是2MB。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。