浅析日志结构的存储引擎(1)-bitcask

谁借莪１个温暖的怀抱￠ 2023-07-11 13:59 83阅读 0赞

这系列文章主要是讲key-value结构的存储引擎，比如bitcask、sstable、LSM-tree等。不涉及内存型的key-value，比如redis。

一、数据写入与查找

对于数据写入磁盘，最简单最快的方式就是顺序写入磁盘，用简单追加日志文件的方式(Append)，就达到了性能的最高效。假设我们把key-value在文件中的offset也记录下来，那么我们就能从磁盘中查找到这对key-value。

二、数据查找的速度

假设我们先不考虑key-value的更新，数据写完磁盘后，用哈希表的形式把key-value的offset放到内存，大家都知道哈希表（hash map）的查找时间复杂度是O(1)，这时只需要一次磁盘寻址，就可以把value从磁盘加载到内存。如果那部分数据文件已经在文件系统缓存中，则读取根本不需要任何的磁盘I/O。结构如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70][]

三、如何解决key更新的问题

上面已经讲过，key-value用追加日志文件的方式写入，当更新一对key-value时，就会追加写入一对新的key-value，而旧版的key-value不会被覆盖。如何解决读到最新的数据？这个也很好解决，只要保证读取时，从最新写入的文件偏移量中读取即可。但是同样的key，更新值使用追加的方式，又会带来新的问题（假设key是电影名，value是播放次数，100万次播放，就会产生100万条记录，其中只有1条是有效记录，旧的版本都是废弃的），这就会带来磁盘空间快速消耗的问题。

四、数据压缩和查找

一个好的解决方案是将日志文件分解成一定大小的段，当文件达到一定大小时就关闭它，并将后续写入到新的段文件中。然后在这些段上执行数据合并压缩，压缩是指丢弃重复的键，并且只保留每个键最新值，压缩可以在后台线程处理。如下图，"new"这个key写了5次，合并后只保留了最新值1082：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70 1][]

也可以将多个段合并成一个段，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70 2][]

每个段都有自己的内存哈希表，用来保存全部的key和value偏移量。为了找到key的值，首先检查最新的段的hash map，如果键不存在，检查第二新的段，以此类推。

五、局限性

1，由于key需要全部放内存，当key越多，需要的内存资源越多。

2，不支持区间查询，查找指定范围的一批数据，需要全盘扫描。

3，进程重启后，内存中的key就会丢失，需要重新加载。可以把哈希表提前备份到磁盘，这样可以避免进程重启时，需要全量扫描数据重建索引。

六、小结

以上就是bitcask的基本设计思想

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

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

end

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhaXl1ZG9uZzIwMjA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306002324592.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/2020030600445471.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 2]: https://img-blog.csdnimg.cn/20200306004613649.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_104687575]: https://blog.csdn.net/daiyudong2020/article/details/104687575