共计 2411 个字符，预计需要花费 7 分钟才能阅读完成。
[TOC]
一、大幅度制约存储介质吞吐量的起因
首先抛出论断。无论任何存储介质（不论是机械硬盘还是 SSD，抑或是内存）的程序访问速度都远远高出随机拜访的速度。
二、传统数据库的实现机制
传统数据库，比方 Mysql 应用的 b + 树索引，对读敌对。但容易造成随机写。比方新插入一个值到数据库，首先咱们要读取 b + 树，判断新插入的值放在树的什么地位，其次在特定的地位写入新值，并做一系列调整，决裂，使之满足 b + 树的个性。这不可避免的造成了磁盘的随机拜访，大数据量的插入速度很慢。当然这也合乎历史发展趋势，早起的 IT 行业，数据量和数据增长速度无限，只有领有良好的查问性能，即可满足需要。
但随着硬件性能的晋升，业务状态的变动，现今的互联网零碎，往往面临着数据的大量、高速产生。如何放慢存储速度，成了要害。于是 LSM Tree 应运而生。
三、LSM Tree 的历史由来
LSM Tree 的最早概念，诞生于 1996 年 google 的“BigTable”论文。后世多种数据库产品对 LSM Tree 的具体实现，都有一些小的差别。采纳 LSM Tree 作为存储构造的数据库有，Google 的 LevelDB, Facebook 的 RockDB(RockDB 来源于 LevelDB), Cassandra,HBase 等。
四、进步写吞吐量的思路
既然程序写比起随机写速度更快。那得想方法将数据程序写。
4.1 一种形式是数据来后，间接程序落盘
这领有很高的写速度。然而当咱们想要查寻一个数据的时候，因为存储下的数据自身是无序的（写的值自身无法控制程序），无奈应用任何算法进行优化，只能挨个查问，读取速度是很慢的。
4.2 另一种形式，是保障落盘的数据是程序写入的同时，还保障这些数据是有序的
而申请写入的数据自身是无序且不可预测的，如何保障落盘的数据是有序的呢？这就须要利用内存访问速度比硬盘快的原理。将写入的申请，先在内存中缓存起来，按肯定的有序构造组织，达到一定量后，再写入硬盘，从而使得硬盘程序写入了有序的数据。进步数据的写入速度同时，不便了后续基于有序数据的查找(有序的数据结构，能够通过二分查找等算法进行进行疾速查问，具体查找算法，得看是哪种有序构造)
五、LSM Tree 结构图
LSM tree 即利用了上述第二种形式。具体结构图如下：
5.1 写入时，为什么要先写一份 log
为了避免写入的数据，在断电时失落。所以先程序写一份 log 到硬盘，不便数据恢复。
5.2 什么是 MemTable
写入数据的内存缓存，MemTable 中存储的是有序的数据。什么才是有序的数据结构？不同的实现可能不雷同。LevelDB 应用的是 SkipList。Hbase 应用的是 B Tree。
5.3 什么是 ImmutableMemTable
MemTable 中的数据随时在减少，当其减少到一定量后，将其变为不可变数据，ImmutableMemTable。新生成一份 MemTable 用于后续的数据写入。ImmutableMemTable 中的数据，将被写入到硬盘中的 SSTable.
5.4 什么是 SSTable
SSTable 全称 Sorted String Table。实际上就是被写入数据的有序存储文件，所以叫 sorted.
SSTable 文件有 DataBlock,IndexBlock,BitSet(不同的实现，有可能没有)
- DataBlock 一个 SSTable 蕴含多个数据块，数据按 KeyValue 的模式有序组织。
- IndexBlock 记录每个数据块中最大的那个 Key 的 Offset
- BitSet 应用 Bloom Filter 来将一个 Key 映射到 BitSet 中
数据的有序组织、IndexBlock、BitSet。这些数据结构，都是为了进步数据读取时的速度。那数据是如何进行读取的呢？
5.5 如何进行数据读取
读取的大略流程如下
因为 SSTable 是程序创立，所以最新的 SSTable 中蕴含了最新的值。再查找 SSTable 时，顺次查找最新的 SSTable。
每一个 SSTable 的查问流程如下
布隆表达式的原理是以极小的数据容量，去存储大量数据存在的可能性。所以如果通过 BitSet 的布隆表达式查问该 Key 存在时，只是一个实践存在可能，接下来要通过 IndexBlock 真正进行查问。而如果布隆表达式在 BitSet 中没有找到，那就是真的没有，能够疾速跳过，进入下一个 SSTable 查找。布隆表达式的使用，可能大大提高查找效率。
5.6 如何进行数据的删除和更新
为了保证数据的程序写，所有 SSTable 都不会因为删除和更新而在原数据所在位置进行更改。在更新时，仅仅插入一个最新的值去写到新的 SSTable 中。在删除时，仍然是插入一个基于该 Key 的删除标记，写入最新的 SSTable 中。因为查找某个 Key 是基于工夫新鲜度，反向顺次查找 SSTable，所以读取某个 Key 始终读的是最新的值。
5.7 SSTable 的合并
随着与日俱增，SSTable 的文件数会增多，导致查找时性能降落。同时因为数据的更新或删除。让老的 SSTable 中数据的有效性升高，太多的过期数据占用 SSTable，同样会升高查问效率。所以个别数据库引擎，定期都会有一个 SSTable 的合并操作。移除过期数据，将多个小 SSTable 合并成大的 SSTable。
5.8 最近读取的 SSTable IndexBlock 缓存
在大内存的条件下，局部数据库还会将最近读取的 SSTable 索引，缓存至内存。这进一步减速了查找的过程。
六、参考文献
http://www.benstopford.com/20…
http://www.cnblogs.com/haippy…
https://blog.csdn.net/u014774…
https://en.wikipedia.org/wiki…
https://www.igvita.com/2012/0…
欢送关注我的集体公众号 ” 东南偏北 UP”，记录代码人生，行业思考，科技评论
