浅析日志结构的存储引擎(2)-SSTable和LSM-Tree

深藏阁楼爱情的钟 2023-07-12 03:55 12阅读 0赞

基于上一篇文章，我们已经知道了[日志结构的存储引擎-bitcask][-bitcask]的基本原理。在这个基础上，继续讨论SSTable(Sorted String Table)。

回顾一下bitcask的key-value，它在段文件中是无序的，假设按key排序，并且要求每个key在每个段中只能出现一次，排好序再写入到段文件中，这种格式的段文件称之为SSTable。

一、SSTable比bitcask有什么优点？

1，由于key在一个段中只出现一次且有序，可以使用类似合并排序的方式，在段文件合并时，即使文件大于可用内存也可简单高效合并。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70][]

2，在文件中查找特定key时，不再需要在内存中保存所有key的索引，假设正在查找key-handiwork，且不知道该key在段文件中的准确偏移量。但是知道key-handbag和key-handsome的偏移量，考虑到key是有序的，只需要从handbag扫描到handsome，假设key存在，就能找到。这是稀疏索引的一种设计思路。通常对于段文件中的每几千字节，只需要一个key就足够了。如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70 1][]

二、如何构建和维护SSTable？

1，当写入时，在内存中维护平衡树结构，用于key-value排序，当这个树内存大于某个阈值(通常为几M)时，将其作为SSTable文件写入磁盘。由于树已经维护了按key排序的key-value对，写磁盘可以很高效。当SSTable写入磁盘的同时，写入可以继续添加到一个新的内存表。

2，为避免数据库崩溃时，最近写入到内存但还没落地到磁盘的数据丢失，在数据写入内存表前，先在日志文件中追加写该数据，每当内存表写入段文件时，该日志文件就可以被丢弃。否则就用该文件恢复崩溃时丢失的数据。

3，为了处理读请求，首先尝试从内存读取，然后从最新的段文件读到最旧的段文件。当一个key不存在时，这种扫描算法就很慢。为了优化这种访问，维护一个额外的布隆过滤器，如果key不存在布隆过滤器中，那么key肯定不存在。

4，同样类似bitcask，后台进程周期性合并段文件。

三，基于合并和压缩排序文件原理的存储引擎，通常都被称为LSM-Tree。如leveldb、RocksDB都是基于LSM-Tree的思想实现。受到了google的bigtable论文的启发。

参考《数据密集型应用系统设计》

原文出自：[https://blog.csdn.net/daiyudong2020/article/details/104706867][https_blog.csdn.net_daiyudong2020_article_details_104706867]

End；

[-bitcask]: https://blog.csdn.net/daiyudong2020/article/details/104687575
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306233415936.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200306233331349.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA=,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_daiyudong2020_article_details_104706867]: https://blog.csdn.net/daiyudong2020/article/details/104706867