简讲LSM树（Log-Structured Merge Tree）

前言：最近在了解大数据实时分析技术druid,究其原理时发现用到了类LSM树思想以实现高效的数据插入，于是展开了对LSM的了解，了解之后感觉这东西虽然也并没有很特别，但在大数据、分布式架构中的应用还是非常有价值的，下面简单做下分享！

首先需要介绍下三种存储引擎：

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

众所周知，数据库的数据大多存储在磁盘上，而磁盘的访问相对内存的访问来说是一项很耗时的操作，对比如下。因此，提高数据库数据的查找速度的关键点之一便是尽量减少磁盘的访问次数，LSM正是基于这样的思考而设计。

更通俗的讲，LSM树原理就是把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会批量flush到磁盘中独立的文件中以提高IO性能，而为了提高读性能磁盘中的树定期可以做merge操作，合并成一棵大树。

前面提到HBase用到了LSM树思想，下面以其为例简单做下图解：

LSM思想中的两个要点：“拆分小树”、“合并大树”，在HBase中如何体现呢：

• 数据插入不是直接写到磁盘，而是先写入内存MemStore，当达到一定条件后批量将内存flush到HRegion磁盘中（一般是Hadoop DataNode）,这样MemStore就变成了DataNode上的磁盘文件StoreFile
• 为了尽量提供好的读取能力，HRegionServer会定期对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树。
• 另外，HBase为防止内存中未dump到磁盘的数据出现丢失，写内存的同时会写临时HLog到磁盘，这样一旦出了异常，能够通过HLog恢复内存数据。

通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘，不过读取的时候稍微麻烦，需要合并各个磁盘中历史数据和内存中最近修改操作，可见写快读慢特点很明显，所以LSM-tree显然比较适合那些数据插入操作远多于数据更新删除操作与读操作的场景！

可能有人会觉得，读能力应该是大部分系统最应该保证的特性，所以用读换写似乎不是个好买卖，但别急，这么分析一下：内存的速度远超磁盘，甚至可达1000倍以上，读取的性能提升，主要还是依靠内存命中率而非磁盘读的次数，所以可以从这个角度去思考优化。

最后讲讲LSM Tree主要的读优化方式：

• Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你，某一个小树里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小树里。效率得到了提升，但付出的是空间代价。
• compact:即前面已经提到的小树合并为大树，因为等需要的时候去读取多个小树会有性能问题，所以需要有个进程不断地将小树合并到大树上，这样读取的时候就直接读大树就可以了。

 以上内容可能有理解不到位的地方，欢迎指正！