SSTable 与 LSM 引擎

SSTable 与 LSM 引擎

​ 假设我们需要设计一个K-V数据库,为了提升 K-V 数据库的写性能,要尽量避免对磁盘上的内容做随机写,所以对已经持久化在磁盘上的 K-V 不做原地更改,当这个 Key 对应的 Value 发生更新或者删除时,我们仍然继续向磁盘新增一条数据,在读取时同一个 Key 以最后的数据记录为准。

​ 这样的确带来数据写性能的提升,但在查询时,我们需要遍历所有的磁盘数据,然后才知道这个 Key 对应的最后一条数据,因此,我们提出也许可以在内存中维护一个索引结构,HashTable 这样的即可,HashTable 存储着 Key 和 Value 在磁盘中最新数据的位置。

​ 但这又带来一个问题,我们需要对所有的 Key 都保存索引,这就使得整个数据库不能保存太多的 Key,而且磁盘中 Key 的旧数据拜拜浪费了存储空间。因此,又提出一个改进,可以在内存中维护一个 MemTable,MemTable 是按照 Key 排好序的数据结构,当数据写入时,首先写入 MemTable,等到 MemTable 的大小超过限值时,将之写入磁盘文件,而且此后这个文件中的数据将不会再被更新,这个有序的、不可变的文件就被称为 SSTable(Sort String Table,因为最开始 Key、Value 均以二进制字符串形式存储),由于 SSTable 的有序性,对于每个 SSTable 维护的可以是一个稀疏索引,例如,k1 不在索引中,但发现索引中有 k0 和 k3,这时读取这两个地址中间的数据就能找到 k1 对应的 Value。同时,由于 MemTable 的存在,对于 一个Key 在短时间内频繁的变更,只用写最后一次的结果即可。为了减少磁盘中的过期数据,在后台会对 SSTable 进行合并,得益于 SSTable 本身的有序性,我们可以将两个大于可用内存的 SSTable 合成一个新的 SSTable,使用归并排序即可,丢弃这两个 SSTable 中已被覆盖或删除的数据。得益于 SSTable 的不变性,读取 SSTable 时不用加锁,提高了并发读的性能。最早这里的索引结构被命名为 LSM-Tree(Log-Structured Merge-Tree),所以 基于合井和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎。

​ 上述方案还有问题,当数据库故障时,那些写入 MemTable 但还没来得及刷写到磁盘中的文件将丢失,为了避免这个问题,设立一个单独的追加写日志文件,在写入 MemTable 之前先写入该日志文件,称为 WAL(Write-Ahead Log),故障恢复时从WAL 恢复 MemTable,由于 WAL 只是用来恢复 MemTable 的(这不会经常发生),所以写入 WAL 的数据不需要排序,直接写即可,同时 WAL 是一个追加写文件,其写入速度可以比得上对内存的随机写,所以 WAL 不会对数据库的写入性能产生产生大的影响。另外一个可以优化的点是:当读请求的是一个不存在的 Key 时,需要遍历 MemTable 和所有的 SSTable 才能发现这个 Key 不存在,所以通常使用布隆过滤器来提前判断所请求的 Key 是否存在。

参考资料

- [1] 数据密集型应用系统设计(Designing Data-Intensive Applications)

上一篇:2021SC@SDUSC HBase(十四)项目代码分析——WAL生命周期


下一篇:PostgreSQL如何管理无用的WAL文件