为了进一步了解原生分布式数据库的工作机制，笔者重点研究了它的存储引擎LSM树，今天就把所学所得分享一下。
LSM树：Log-Structured-Merge-Tree，中文名称叫日志合并树。
关键字：
Log：日志 Structured：有结构的(废话) Merge：合并 Tree：树（勉强吧）
出现背景
传统集中式数据库使用的数据结构B+树，每次写不仅要执行写请求写入的记录，还要对B+树执行必要的元数据更新，涉及到B+树中节点的移动/拆分/合并。每次写入B+树结构时，都是磁盘的随机IO写操作。
为什么不建议对表创建较多的索引，因为每个索引都是一棵B+树，每次写入都需要维护所有的B+树。
在面对海量数据读写的场景下，随机写的性能瓶颈愈发明显。
在大数据这个领域，谷歌发布了大名鼎鼎的"三驾马车"的论文，分别是GFS(2003年)，MapReduce（2004年），BigTable（2006年），给大数据领域带来了无数的灵感，LSM树就来自于 “BigTable” 的论文。
LSM树的特性
LSM树一种分层、有序、面向内存+磁盘的数据结构，核心思想是磁盘批量的顺序写速度要远比随机写性能高出很多。
LSM树将数据存储限制为只能进行追加操作，而数据存储只是一个包含完全有序的键值对的"日志"，排序顺序由键决定。
LSM的论文中，将LSM树解释为一种抽象数据结构，同时还解释了使用分层存储架构的动机。日志结构一词是指数据的结构是一个接一个的，就像一个只能追加的日志。
LSM树首先将大量写入缓存在内存，当积攒到一定程度后，将它们批量写入文件中，一次 I/O 可以进行多条数据的写入，充分利用每一次 I/O。
LSM树整体上不是一个单一的数据结构，而是结合了多个数据结构，利用了存储层次结构中不同存储设备的响应时间。由于只进行追加，它在提供高写入率的同时，还能通过在内存中维护的索引提供低成本读。与执行in-place更新的基于B+树的存储引擎相比，LSM树有in-place更新，这有助于避免随机I/O。
行业应用
分布式数据库
如Hbase、Apache Cassandra、LevelDB、RocksDB、ClickHouse MergeTree 等等。这些 NoSQL 数据库都是使用LSM树来处理大规模的分布式数据存储和查询，以提供高吞吐量和低延迟的数据访问。
国内知名的分布式数据库Oceanbase、Tidb（基于RocksDB）也是使用LSM树。
几乎所有NoSQL数据库都使用LSM树的变体作为底层存储引擎，因为它可以实现快速写入吞吐量和主键快速查找。
日志存储
由于LSM树对写入操作具有高效的支持，它在日志存储场景中表现出色。例如，用于处理日志数据的系统，如ELK（Elasticsearch, Logstash, Kibana）使用LSM树来快速地写入和检索大量的日志事件。
分布式文件系统
一些分布式文件系统，如Hadoop的HDFS和Google的GFS，使用LSM-Tree来管理文件系统的元数据，例如文件和目录信息。这样可以提供高效的元数据访问和更新操作。
时间序列数据
由于LSM树对写入操作的高效支持和时间序列数据的特性相符，它在时间序列数据存储和分析中被广泛使用。这包括物联网（IoT）应用、日志分析、金融数据等领域。
LSM树的组成部分
现代 LSM树 包含了三个部分：MemTable、Immutable MemTable、SSTable，前两个位于内存，最后一个位于磁盘中。
MemTable
MemTable 是 LSM树在内存中的数据结构，只用于保存最新的数据，按照 Key 有序地组织这些数据。
存在内存中的数据会因为断电丢失据的可靠，这一点和传统集中式数据库是一样的，也是必须的。
WAL 即事务的所有修改在提交之前要先写入 log 文件中，当有新数据写入时，首先将数据记录在 WAL Log 中，用作故障恢复，然后将数据写入内存的 MemTable 中。
Hbase 和 RocksDB 均默认使用 SkipList 作为 MemTable的数据结构。
Immutable MemTable
当 MemTable 达到一定大小后，会转化为 Immutable MemTable。Immutable MemTable 是将 MemTable 转为磁盘上的 SSTable 的一种中间状态。在转化过程中，写操作由新的 MemTable 处理，过程中不阻塞数据更新操作。
SSTable
SSTable (Sorted String Table) 是 LSM 树在磁盘中持久化存储的数据结构，它是一个有序的键值对文件。
后台线程会将 Immutable MemTable 写入到磁盘中形成一个新的 SSTable 文件，并随后销毁 Immutable MemTable。
LSM树不会修改已存在的 SSTable, LSM 在修改数据时会直接在 MemTable 中写入新版本的数据，并等待 MemTable 落盘形成新的 SSTable。
因此，虽然在同一个 SSTable 中 key 不会重复，但是不同的 SSTable 中仍会存在相同的 Key，这会带来冗余存储的问题。对于某个 Key，除了最新的记录，其他记录都是冗余无用的，所以对SSTable进行合并和压缩（**Compact） ，来清除冗余的记录。
LSM树的增删改查
我们以RocksDB为例
写操作（增删改）
LSM树的数据更新是日志式的，修改数据时直接追加一条新记录（为被修改数据创建一个新版本），而使用B+树的传统集中式数据库则需要找到数据在磁盘上的位置，并在原地进行修改。
LSM树的写入就是写入一个键值对，写入时会直接将键值对写入到内存中的MemTable, 当写入时会直接将键值对写入到内存中的MemTable。（无论是新建还是更新，本质上都是新建）
LSM的删除也是为数据打上一个墓碑标志，并不会做我们通常理解上的delete操作。
先写WAL（Write Ahead Log）预写日志，再写入内存MemTable。
写入数据量到达大小限制时，MemTable转变成immutable MemTable（不可变）
immutable MemTable是写到磁盘SST文件的一个中间状态，避免直接写磁盘，减少IO等待。
重启开一个新的MemTable。
将immutable MemTable刷到磁盘上形成SST文件，该immutable MemTable销毁。
WAL中数据都持久化到SST file之后，会被删除。
每一层都会切分成多个SST文件，每个SST文件都是键值对文件。达到一定阈值后，向下一层做Compact。
为什么需要定期做Compact？
用于去除相同key的多条记录。当我们对一个key进行多次update/delete时，RocksDB会产生多条记录。
虽然定期合并可以有效的清除无效数据，缩短读取路径提升查询效率，提高磁盘利用空间，但Compaction操作是非常消耗CPU和磁盘IO的。
查操作
因为最新的数据总是先写入 MemTable，所以在读取数据时首先要读取 MemTable，然后从新到旧搜索 SSTable，找到的第一个版本就是该 Key 的最新版本。
根据局部性原理，刚写入的数据很有可能被马上读取。因此， MemTable 在充当写缓存之外也是一个有效的读缓存。
为了提高读取效率，SSTable 通常配有 BloomFilter（布隆过滤器） 和索引来快速判断其中是否包含某个 Key 以及快速定位它的位置。
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否存在于一个集合中。布隆过滤器的优势在于它的查询速度非常快，占用的存储空间远小于其他传统数据结构。
因为读取过程中需要查询多个 SSTable 文件，因此理论上 LSM 树的读取效率低于使用 B+树的传统集中式数据库。
LSM树的优缺点
可以看到LSM树将增、删、改这三种操作都转化为内存insert + 磁盘顺序写，通过这种方式得到了无与伦比的写吞吐量。 LSM树的查询能力则相对被弱化，相比于B+树的最多3~4次磁盘IO，LSM树则要从Level 0一路查询Level n，极端情况下等于做了全表扫描。
优点
具有较高的写入性能和压缩存储，适用于写多读少或写入速度较快的场景。通过将写入操作集中在内存和顺序写的日志文件中，可以获得较高的写入吞吐量。查询可以通过内存缓存和有序的SSTable文件，进行快速定位和检索键值对。
缺点
读放大。如读取操作可能需要扫描多个 SSTable文件，导致查询性能不如B-tree 等结构稳定。此外，合并操作可能会引起较长的停顿时间，影响读写性能，对于实时性要求较高的系统可能会有影响。
对比B+树
在LSM树上进行一次数据更新不需要磁盘访问，在内存即可完成，速度远快于B+树。当数据访问以写操作为主，而读操作则集中在最近写入的数据上时，使用LSM树可以极大程度地减少磁盘的访问次数，加快访问速度。
LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。
极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。
重新出发再看LSM
总结下LSM树的设计原则：
先内存再磁盘 内存原地更新 磁盘追加更新 归并保留新值
前面介绍了LSM的分层结构和常见操作，我们来思考一个问题，为什么要这么设计。
首先，追加式更新的内存或磁盘操作，意味着顺序写入，执行效率比较高。这是LSM核心出发点。
其次，引入内存MemTable，作为读和写的缓冲，因为直接读写磁盘效率会比较差。但内存中不可能无限制的放所有数据，所以在内存中的数据必须有一个大小限制，超出限制的数据需要写入磁盘文件（SSTable）。
为什么SSTable会有多层？
先放结论：为了将I/O的开销最小化。
追加式的操作导致一个数据存在多个版本，既无效占用了大量磁盘空间，还有导致查询需要遍历太多数据，影响查询效率，所以要做合并和压缩，把这些冗余数据都舍弃掉。
假设只有一个SSTable，因为MemTable在不断写入，查询操作也一直在扫描，完全没法做Compact。
上述的问题在分层的结构下可以得到很好的缓解，本质上来说就是将一次性的大量I/O开销分摊到了多层当中，并且在在多层的这些I/O也不是完全同步的。这样一来某个时刻下的I/O开销会小很多，相应带来write stall写停顿的延迟与次数也会有所减少。
写在最后
希望这篇文章能让初次接触原生分布式数据库的同学能够了解它最基本的有别于传统数据库（包括分布式）的特性。
后面如有机会，我们再研究不同分布式数据库的具体实现和特点。
