原文：http://blog.sina.com.cn/s/blog_628cc2b70102x1o5.html

概念一：LSM树

1.1 LSM大致介绍

传统RDBMS数据库使用B+树结构，它的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。

HBase使用LSM（Log-Structured Merge Tree日志结构合并树）树，用于为那些长期具有很高记录更新（插入或删除）频率的文件提供低成本的索引机制。LSM-Tree通过使用某种算法对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式联合使用一个基于内存的组件和一个或多个磁盘组件。

与传统访问方式（比如B+树）相比，该算法大大减少了磁盘磁臂的移动次数，同时还会提高那些使用传统访问方式进行插入时，磁盘磁臂开销（寻道+转动）远大于存储空间花费的情况的性价比。但是，对于那些需要立即响应的查找操作来说，某些情况下，它也会损失一些IO效率，因此LSM-Tree最适用于那些索引插入比查找操作更常见的情况。比如，对于历史记录表和日志文件来说，就属于这种情况。

1.2 B+树与LSM-Tree树本质区别

他们本质不同点在于他们使用现代硬盘的方式，尤其是磁盘。从磁盘使用方面讲，有两种不同的数据库范式：一种是寻道，另一种是传输。RDBMS是寻道型，它需要随机读写数据。LSM-Tree则属于传输型，它会顺序读写数据。

LSM-Tree工作在磁盘传输速率的级别上，因为它会使用日志文件和一个内存存储结构把随机写操作转换为顺序写。读操作与写操作是独立的，这样这两种操作之间就不会产生竞争。

概念二：底层持久化

2.1 存储的工作原理

一个新的客户端为找到某个特定的行键首先需要连接ZooKeeper Qurom。它会从Zookeeper检索持有-ROOT-Region的服务器名。通过这个信息，它询问拥有-ROOT-Region的RegionServer，得到持有对应行键的.META. 表Region的服务器名。这两个操作的结果都会被缓存下来，因此只需要查找一次。最后，它就可以查询.META. 服务器，然后检索包含给定行键的Region所在的服务器。

一旦它知道了给定的行键所处的位置，比如，在哪个Region里，它也会缓存该信息，同时直接连接持有该Region的HRegionServer。现在，客户端就有了去哪里获取行的完整信息而不需要再去查询.META.服务器。

2.2 Flush机制

Flush命令会将内存数据写入存储文件否则我们必须等着它直到超过配置的flush大小才会将数据插入存储文件中。

概念三： Region切分与合并

3.1 Region切分

当一个Region内的存储文件超过hbase.hregion.max.filesize时，该Region就需要split为两个。该过程完成迅速，因为系统只是简单地为新Region创建两个引用文件，每个只持有原始Region一半的内容。

（1）RegionServer通过在父Region内创建切分目录来完成。之后，它会关闭该Region，这样它就不再接受任何请求。

（2）然后RegionServer开始准备生成新的Region，通过在切分目录内设置必要的文件结构来完成。

（3）现在两个子Region已经就绪，同时将会被同一个服务器并行打开。现在需要更新.META.表，将这两个Region作为可用Region对待，同时会启动对这两个Region的合并。

（4）原始Region最终会被清除，意味着它会从.META.表中删除，磁盘上它的所有文件也会被删除。最后，Master会收到关于该split的通知，通过负载平衡等将这些新的Region移动到其他服务器上。

3.2 合并

存储文件处于严密的监控之下，这样后台进程就可以保证他们完全处于控制中。MemStore的flush操作会逐步增加磁盘上的文件数目。当数目足够多的时候，合并进程会将它们合并成规模更少但是更大的文件。

概念四：日志

为了避免产生过多的小文件，RegionServer在未收集到足够数据flush到磁盘之前，会一直把它保存在内存中。为解决这个问题HBase采用WAL策略：每次更新之前，将数据写写到一个日志中，只有当写入成功后才通过客户端该操作成功。

4.1 概要流程

类似Mysql中的bin-log，WAL会记录下针对数据的所有变更，在内存产生问题时，可以通过日志回放，恢复到服务器宕机之前的状态。

首先，客户端发起数据更新动作，每个更新操作都会被包装为一个KeyValue对象，然后通过RPC调用发送出去，该调用到达具有对应Region的某个HRegionServer。

其次，KeyValue对象到达后，会被发送到指定的行键所对应的HRegion。数据会先写入WAL，然后存入相应的MemStore中。

最终，当MemStore达到一定大小后，或者过了特定时间段后，数据就会异步地持久化到文件系统中。在此期间都存储在内存中。WAL可以保证数据不会丢失。

4.2 日志一致性

日志流数据的持久化过程具体如何实现，是否存在数据丢失的问题？为了能够让日志的读取可以读到服务器crash时刻最后写入的那个位置，或者尽可能接近该位置，这就需要一个feature:append支持。HBase目前会检测底层的Hadoop库是否支持synFs()或者hflush()。这是linux级别的，作用是当系统异常时commit buffer cache to disk。

-----------------------------------------------------------------------------------------------------------------------

附：LSM树由来、设计思想以及应用到HBase的索引

https://www.cnblogs.com/yanghuahui/p/3483754.html

讲LSM树之前，需要提下三种基本的存储引擎，这样才能清楚LSM树的由来：

• 哈希存储引擎 是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是your Mr.Right
• B树存储引擎是B树（关于B树的由来，数据结构以及应用场景可以看之前一篇博文）的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。
• LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。

通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并磁盘中历史数据和内存中最近修改操作，所以写入性能大大提升，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：

• 因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog
• MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成了DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

关于LSM Tree，对于最简单的二层LSM Tree而言，内存中的数据和磁盘你中的数据merge操作，如下图

图来自lsm论文

lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。

hbase在实现中，是把整个内存在一定阈值后，flush到disk中，形成一个file，这个file的存储也就是一个小的B+树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，所以hbase这么整体内存flush，而不是和磁盘中的小树merge update，这个设计也就能讲通了。内存flush到磁盘上的小树，定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。