学大数据必懂系列之LSM-Tree
LSM-Tree 介绍
LSM树(Log-Structured-Merge-Tree)（日志结构合并树）是一种能够提升磁盘写入速度的数据结构，它通过将大量的磁盘随机写操作，转换为批量顺序写的方式来得到写入性能的提升。但是同时也牺牲了一部分的读性能
LSM-Tree 设计思想
LSM-Tree的设计为一种多层结构、有序数据、针对磁盘存储的一种数据结构，一般在各种Key/Value的数据库中很常用。核心思想就是充分利用磁盘批量顺序写远比随机写高效的特性，同时舍弃部分读效率来换取写效率的大幅提升
一个LSM-Tree是由两个或两个以上的树状组件数据结构组成的，其中一个是驻留在内存中的树，称之为C0树，一个是驻留在磁盘中的树，称之为C1树，除了C0是驻留在内存之外，C1-Ck的树都是驻留在磁盘中的。
在LSM树中，最开始的数据是写入到内存中，也就是C0层的树结构中，当C0树的大小阈值达到了一定大小之后，C0树中的全部或部分数据就会刷入磁盘中的C1树。当然其中还会涉及到容错恢复、合并检查点、旧的C0树子页的清理等等内容，如果感兴趣可以参阅论文：https://www.cs.umb.edu/~poneil/lsmtree.pdf。
数据首先会插入到内存中的树，为了防止数据丢失，写内存的同时需要暂时持久化到磁盘，即输入数据时数据会以完全有序的形式先存储在日志文件（write ahead log (WAL)预写日志）中（对应HBase的MemStore和HLog)。当发生故障时，比如机器关机、进程挂掉、断电等未知风险的时候，会导致内存中数据丢失，通过WAL的机制就可以将数据从日志文件中进行恢复。
LSM-Tree 合并操作
每次持久化到硬盘中是一条独立的线程做的，并且生成单独的文件，因此C1树也不止一个文件，当文件数变多的时候，势必导致每一次查询都会涉及到大量文件的打开，每一次文件的打开都是对 I/O 的消耗。为了控制这种 读放大 的情况出现，LSM Tree 就需要考虑小文件合并的问题。
合并操作会从左至右遍历内存中的叶子节点与磁盘中树的叶子节点进行合并，当合并的数据量达到磁盘的存储页的大小时，会将合并的数据持久化到磁盘。同时更新父亲节点对叶子节点的指针
LSM-Tree性能的衡量因素
几个名词的解释
读放大
过多读取请求。RA 由每个查询的磁盘读取次数计算得出。当数据读取的频率远远超过了数据大小时，从而影响到了读性能，我们称之为读放大，为了减轻读放大，LSM-Tree采用布隆过滤器来避免读取不包括查询键值的SSTable文件
空间放大
磁盘空间使用过多，磁盘使用大于数据实际大小时称之为空间放大。因为空间有限,SA 计算为磁盘上数据库文件的大小与实际数据大小的比率。当使用的磁盘空间大于数据大小时，就会出现高 SA
写放大
过度压缩相同的数据。WA 是通过写入存储的字节数与写入数据库的字节数的比率来计算的。当写入存储的字节数/秒多于实际写入数据库的字节数时，就会出现高 WA
LSM-Tree在HBase中的应用
首先我们来看一下HBase的写入的流程设计：
角色说明 ：
RegionServer——HBase工作节点，它在LSM-Tree形式的HDFS中执行信息块的管理和存储，由RegionServer在幕后用于实际存储数据
从底层来看，HBase的大部分功能都位于对表执行读写操作的区域性服务器中。从技术上讲，每个表都可以作为称为HRegions的独立部分的集合分布在不同的region服务器上。单个region服务器节点可以容纳一个表的多个HRegions。每个HRegion保存一定范围内内存和磁盘空间共享的行，并按键属性排序。这些范围在不同区域之间不相交，因此我们可以依赖它们在整个集群中的顺序行为。单个RegionServer的HRegion包括以下部分:
预写日志(WAL)文件——在进入内存之前，每次写操作都持久化数据的第一个位置。正如我前面提到的，lsm树的第一部分保存在内存中，这意味着它可能会受到一些外部因素的影响，比如示例中的功率损失。将此类操作的日志文件保存在单独的位置将允许轻松地恢复此部分，而不会有任何松动。
Memstore——在内存中保存最新信息的排序集合。它是前面描述的lms树结构第一部分的实际实现。定期执行滚动合并到本地硬盘驱动器上称为HFiles的存储文件
HFile -表示从Memstore接收到的一小段数据，并保存在HDFS中。每个HFile包含经过排序的KeyValues集合和B-Tree+索引，该索引允许在不读取整个文件的情况下查找数据。HBase会定期对这些文件进行合并排序操作，使其符合标准HDFS块的配置大小，避免小文件问题
上图的流程说明：
- HBase客户端在数据写入时，首先会写入到WAL(write ahead log)中，将数据以追加的方式写入到WAL文件的尾部。WAL保存在每个RegionServer中，RegionServer使用它来恢复未提交到磁盘的数据
- 数据一旦写入到WAL之后，然后会将数据复制到MemStore，MemStore其实就是LSM-Tree中的C0树
- 数据被放置到MemStore中之后，客户端接收到确认信息
- 当MemStore达到阈值时，它将被转存或提交数据到HFile中
参考资料
【LSM-Tree论文】https://www.cs.umb.edu/~poneil/lsmtree.pdf
https://www.jianshu.com/p/06f9f7f41fdb