LSM-Tree是什么
LSM-Tree(Log Structured Merge Tree)，一种分层、有序、面向磁盘的数据结构。核心思想是利用磁盘批量的顺序写操作要远比随机写操作性能高出很多。
LSM-Tree存储模型
WAL(Write Ahead Log)
写之前的日志。就是在数据写入之前保存的地方。写入新的数据时，数据先顺序写入到WAL文件中，然后写入到MemTable中。这样的目的是持久化数据，防止内存结构MemTable中数据丢失。当程序意外发生故障，可以从WAL恢复在内存结构MemTable中尚未写入到SSTable的数据。
MemTable
数据会写入到MemTable中，直到内存到达阈值。
Immutable Memtable
内存到达阈值后，会自动转换为Immutable Memtable。Immutable Memtable和Memtable区别就在于，Immutable Memtable只读，这样系统生成新的Memtable可以继续支持数据的写入。而Immutable Memtable可以避免在写入磁盘时阻塞客户端正常的写操作。
SSTable(Sorted String Table)
SSTable就是MemTable中数据在磁盘上的最终有序存储。SSTable通常采用分级的结构，Memtable中的数据达到指定阈值后会写入到Level 0层新的SSTable。当某个Level下的文件数超过一定的值后，会将这个Level下的SSTable文件与高一级的SSTable文件合并，多路归并合并保证合并后的SSTable文件有序，生成一个新的SSTable文件。
LSM-Tree的写入
- 请求到来时，先把数据写入到WAL。
- 然后写入到内存结构MemTable中。
- MemTable超过一定阈值后，转换为Immutable Memtable。系统创建一个新的MemTable继续接受写请求。
- 内存结构Immutable Memtable中的数据写入到硬盘上的SSTable中。
- SSTable体积超过一定的大小会进行合并，合并过程也会清理掉被标记删除的数据。如果SSTable存在多个level，每个level上的数据达到一定大小都会与高一级的进行合并。
LSM-Tree的读取
LSM-Tree的读取效率不高，很多时候会用LSM-Tree与B+树进行比照，B+树作为索引具有高效的读性能 。LSM-Tree读取数据时会按照写入时数据流的顺序尝试读取：
- 首先在内存结构的MemTable和Immutable Memtable中查询。
- 如果没有找到，在SSTable的Level 0开始，依次查找各个level。其中Level 0因为是内存直接写入的，所以数据范围可能存在重叠，要查询多个文件。而其他level的数据有序不重叠，一般只需要查找一个文件即可确定。
- 如果仍旧没有找到，则说明LSM-Tree中不存在这个数据。
LSM-Tree的读取优化
LSM-Tree设计提升了写操作的效率，但是却牺牲了读操作。为了提高读服务的性能，LSM-Tree对读操作进行了优化：
- 压缩：对SSTable分块进行压缩，当每次读取时只需要对某一小块进行解压读取即可。
- 缓存：使用缓存块(Block)缓存。
- 布隆过滤器(Bloom Filter)：过滤掉一部分不存在数据的查询，减少数据的读取。
- 合并：各个level之间数据的合并，清除失效的数据，提高磁盘利用率。
HBase一种LSM-Tree的存储实现
一张HBase表由多个Region组成，一个Region又有多个Store组成。具体可以参考HBase的架构。
HBase中的Store加上Write Ahead Log (WAL)就是基于LSM-Tree的一种具体实现。Store包括三部分MemStore、StoreFile和Blocks。
- WAL就是LSM-Tree模型中的WAL，用于在写入数据时进行持久化备份的。
- MemStore对应MemTable，在内存中缓存写入的数据。在落盘时MemStore会产生一个镜像(snapshot)，相对于Immutable Memtable，被用于写入磁盘。并且使用新的MemStore继续提供数据写入服务。
- StoreFile对应SSTable，存储数据的文件。
- Blocks是区块缓存，对应上面提到的读取优化中的缓存块。
HBase存储架构如图：
HBase读取数据
大体上说：
- 首先从ZooKeeper中读取meta表，找到rowkey所在的Region Server信息。
- 向对应的Region Server请求读取信息。
- Region Server会先从MemStore中寻找，然后从StoreFile中寻找。
meta表存储结构如下图：
Key：存储着Region Key，包括表名字、region开始的第一行的rowkey和region id。
Values：info列族下，存放序列化的HRegionInfo的实例，包含当前region的Region Server的端口，包含当前region的Region Server操作的开始时间。
关于MemStore和StoreFile的读取结构和方式，可以参考上文的LSM-Tree的读取。
