学大数据必懂系列之SSTable

Google SSTable文件格式被用于BIgTable内部数据，SStable是一种不可变的、排序的、持久化的key_value Map，其中key和value都是任意字节的字符串。提供了找寻特定Key值对应的value的操作，以及找寻给定范围内所有key_value的操作。每一个SStale包括一系列的block(一般block大小是64Kb，这个值是可以配置的)，在SST的末尾还有一个“block index”，用于定位每一个block(相当于索引)，是key_offset(偏移量)的索引。

Sorted Strings Table(SSTable)是HBase、 Cassandra等一些NoSQL数据库使用的一种持久文件格式，用于获取存储在memtables中的内存数据，对其进行排序以实现快速访问，并将其存储在磁盘上的一组持久的、有序的、不可变的文件中。不可变意味着sstable永远不会被修改。它们稍后被合并到新的sstable中，或者在数据更新时被删除。

其中Key和value都可以是任意的byte字符串。使用Key来查找Value，或通过给定Key范围遍历所有的Key/Value对。每个SSTable包含一系列的Block（一般Block大小为64KB，但是它是可配置的），在SSTable的末尾是Block索引，用于定位Block，这些索引在SSTable打开时被加载到内存中，在查找时首先从内存中的索引二分查找找到Block，然后通过一次磁盘寻找即可读取到相应的Block。还有一种方案是将这个SSTable加载到内存中，从而在查找和扫描中不需要读取磁盘

SSTable和LSM-Tree

在 学大数据必懂系列之LSM-Tree 文章中，我们讲到LSM-Tree是一种能够将批量随机写，转换为顺序写的数据结构，其实本质就是不断产生SSTree结构的Log文件，然后不断Merge以提高文件效率的，它是一种分层的组织数据的结构，具体到实现上就是一些按照逻辑分层的有序文件

一言概述的话 ：LSM-Tree的树节点可以分为两种，保存在内存中的称之为MemTable, 保存在磁盘上的称之为SSTable

在学大数据必懂技术之LSM-Tree文章中，我们也提到LSM-Tree是应用与写多读少的场景，对于大数据量的写入性能很好，但是损耗了一些数据读取的性能，那么SSTable的数据结构就是作为一个解决方案来处理这种读取效率低的问题。

1. 磁盘上的 SSTable 索引需要永远加载在内存里

2. 所有写操作，直接写 MemTable （写文件缓存，即内存，保证随机写入速度）

3. 读数据的时候先从 MemTable 检索，然后再从 SSTable 的索引中检索；

4. MemTable 周期性 flush 到磁盘中；

5. 磁盘上的 SSTable 会定期合并

6.落盘的数据不可变更，更新和删除操作并不是真正的物理修改和删除，只是增加版本号

SSTable和LSM-Tree: 更新和删除

在内存中写操作是经常发生的，写操作是直接写入MemTable，当MemTable达到一定的size，就flush到disk内成为一个不可变(immutable)的SSTable。与此同时，我们会保持(maintain)所有SSTable的index在内存中，这样在对给定的key进行搜索的时候，我们首先在MemTable内进行检索，再在每一层的SSTale之间再进行搜索，到这里就介绍了LSMTree存储引擎是如何提高读写效率的了，那对于更新与删除操作呢？

对于更新操作，因为SSTable是不可变的，因此更新与删除操作只发生在内存的MemTable内，如果要对SSTable内的数据进行更新只需要重新写进去一个新的就可以了，因为对于SSTable的访问是顺序的，所以新内容的存在会覆盖旧内容，也就是顺序访问到需要的值的时候就会退出，以下的旧值不被访问到。对于删除操作，也是在MemTable内插入一个“墓碑”标志加值，代表这个值被删除了，然后访问的时候会提前访问到墓碑标志而得知该值已经被删除了

SSTable 压缩和合并

随着数据的不断写入和更新，将创建更多不可变的SSTable文件。每层SSTable的文件到达一定条件之后进行合并操作（hbase.hregion.memstore.flush.size），然后放置到更高层，因此，可以在磁盘上的不同SSTable文件中找到具有不同版本数据的相同记录。系统了解这些记录中的哪些是最新的，并且仅使用最新版本响应查询请求。然而，如果没有某种方法来删除过时的数据，SSTable计数和存储的数据量将非常高，磁盘将被填满。

压缩是一个使用现有SSTables中的数据写入一个全新文件的过程。此过程将消除过时记录的重复数据，并仅将同一密钥的最新更改写入不同的SSTable，从而写入新的SSTALE文件。删除的行（由称为“墓碑”的标记指示）或整个删除的列也会被清除，并且该过程会为压缩的SSTable文件创建新的索引。

SSTable在HBase中的应用

这块可以参考 学大数据必懂系列之LSM-Tree

如上面的架构图设计，把 HBase 套用到 LSM-Tree和SSTable中的话，Memstore 就是上边的 Memtable，SSTables就是上面的HFiles ，除此之外，HBase 也和上边对比有一些区别。

下面给出一些HBase在使用LSM-Tree和SSTable中的一些参数优化：

• hbase.hregion.memstore.flush.size 单个 memstore 在刷新到磁盘之前允许达到的大小。
• hbase.hregion.memstore.block.multiplier 临时允许 memstore 增长到最大大小乘以该因子。
• hbase.regionserver.global.memstore.lowerLimit 在强制刷新某些 memstore 之前，JVM 对聚合 memstore 大小的全局限制（以堆的百分比为单位）。
• hbase.regionserver.global.memstore.upperLimit JVM memstore 在写入被阻塞之前的大小限制 （以堆的百分比为单位）
• hbase.hstore.compactionThreshold 当存储达到这么多 HFile 时，HBase 将开始压缩 HFile
• hbase.hstore.blockingStoreFiles HBase 不允许进一步刷新，直到压缩将 HFile 的数量至少减少到此值。这意味着现在 memstore 需要缓冲所有写入，因此如果压缩无法跟上，最终会成为阻塞客户端。
• hbase.hstore.compaction.max 单个次要压缩将考虑的最大 HFile 数。
• hbase.hregion.majorcompaction 定时 - 主要 - 压缩之间的时间间隔。即使没有发生任何更改，HBase 也会以此频率触发压缩。
• hbase.hstore.blockingWaitTime 客户端被阻止的最长时间。在此时间之后，将再次允许写入。

参考链接：

https://cloud.google.com/bigtable/docs/overview

https://www.scylladb.com/glossary/sstable/

https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

https://en.wikipedia.org/wiki/Log-structured_merge-tree

​