我爱编程

数据存储--SSTables与LSM-Trees

2017-12-24  本文已影响143人  MontyOak

之前说过,在日志形式的数据存储中,数据(这里指数据键值对)都是按写入的先后顺序排列存储的。
现在,按照数据键排序来存储数据。这样似乎对于写入操作的速度会有影响(必然会有排序处理的过程,和数据重新写入的过程),但它本身的一些优势让我们决定使用这种数据存储形式。
这种形式叫做排序字符串表(Sorted String Table,简称SSTable)。相比简单的日志结构存储,SSTable有很多优点:

  1. 数据片合并操作简单高效,类似于归并排序。按顺序从各个待合并的数据片中读取数据,依次比较键的大小。这样可以得到一个新的完整数据片。当存在同一键在不同片中的情况时(一般是更新操作或者删除操作),以时间戳偏大的数据片中数据为准。

    数据片合并操作
  2. 在进行按键查询操作时,不再需要在内存中维护整个数据的完整索引,只需要维护一些节点数据的索引即可(比如每隔十万条数据记录一个索引)。


    SSTable中索引示例
  3. 类似上图灰色部分,可以将相邻几条数据压缩一起存入磁盘中,这样可以加快磁盘写入,节省带宽。

既然SSTable有这么多优点,那下面就简单说一下它的实现细节。
在内存中维护一个排序结构并不难:红黑树AVL都是非常著名的平衡排序结构。可以满足按任意顺序插入,按序读取的需求。
一个SSTable的存储可以按照以下方法来实现:

  1. 当收到一个写入请求时,将要写入的数据加入到在内存中的排序树中(比如说一棵红黑树),这个内存中的树通常叫做memtable
  2. 随着不断接受写入请求,memtable的文件大小越来越大,当超过某个阈值时(通常是几兆大小),将memtable内的数据(此时红黑树中的数据是排序的)写入到磁盘中。通常这些写入磁盘的数据片都是按写入的时间戳组织排序。完成写入操作之后,重新初始化一个新的memtable
  3. 当收到一个读请求时,先去当前memtable中查找相关数据,如果没有找到,再按时间戳逆序去磁盘上的数据片中查找。
  4. 定期运行数据片的合并操作,来减少数据片的数量和由于更新、删除操作产生的冗余数据。

上面几点可以实现出一个看起来不错的数据存储。问题在于,一旦数据库实例宕机,最近一段时间内的写入(在memtable中的部分)将会永久丢失。为了防止memtable中的数据丢失,可以维护一个数据操作日志,记录memtable中的数据逻辑操作,这个日志在memtable写入到磁盘数据片之后就可以删除另起新日志了。
SSTable实际上也是LevelDBRocksDB中的数据存储(相似的用法还出现在CassandraHBase等BigTable系的数据库中)。
这种数据存储形式也被叫做LSM-Tree(Log-Structured Merge-Tree)。它的基本操作就是合并压缩排序数据片。

还有一些细节需要提一下。对于数据片中实际不存在的数据,查询操作往往需要对所有数据片中相关键扫描之后才能确定不存在。对于这种情况,可以考虑使用布隆过滤器来减少无谓的查找操作。关于数据片的压缩操作,也有size-tiered和leveled-tiered两种。(区别)。LevelDBRocksDB选择的是leveled-tiered压缩,而HBase选择了size-tiered压缩,Cassandra则对两种方法都支持。

上一篇下一篇

猜你喜欢

热点阅读