0x00 背景介绍
LSM tree 拥极高的写入速度，得益于该模式下，大量随机写入转化为顺序写入。相对于B族树，LSM 更能进一步榨干SSD磁盘的读写带宽，如果使用 SSD/HDD 混合使用情况下，还可以避免大量 HDD 的随机 IO。根据文章 深入浅出分析LSM树（日志结构合并树） 中的介绍，LSM 并没有一种特定的实现方式，不要理解为他就一定是论文里面那样，它更像是一种范式：
“磁盘顺序写” + “多个树(状数据结构)” + “冷热（新老）数据分级” + “定期归并” + “非原地更新”这几种特性统一在一起的思想
从文件系统角度来看，overlayfs 的 upper 和 lower 这样一种形式，在结构上与 LSM tree 酷似，如果能定期针对 upper 打 Snapshot，然后创建新的 upper，合并下层的 lowers，那么 overlayfs 也可以做成 LSM-Tree 的版本。
不过通常 LSM-tree 总是在 KV 领域大放光彩，最早的实现例如：RocksDB、LevelDB，以及后来者 Badger 等，有一些针对 Compaction，kv 分离，大 value 优化等。
上方文章给出了 LSM 树的定义：
- LSM树是一个横跨内存和磁盘的，包含多颗"子树"的一个森林。
- LSM树分为Level 0，Level 1，Level 2 … Level n 多颗子树，其中只有Level 0在内存中，其余Level 1-n在磁盘中。
- 内存中的Level 0子树一般采用排序树（红黑树/AVL树）、跳表或者TreeMap等这类有序的数据结构，方便后续顺序写磁盘。
- 磁盘中的Level 1-n 子树，本质是数据排好序后顺序写到磁盘上的文件，只是叫做树而已。
- 每一层的子树都有一个阈值大小，达到阈值后会进行合并，合并结果写入下一层。
- 只有内存中数据允许原地更新，磁盘上数据的变更只允许追加写，不做原地更新。
我仔细思考了一下，我对它的定义可以再稍微修改一下，不再描述为内存和磁盘，而是描述为：较快的介质和较慢的介质，所以我将整个 LSM Tree 的定义调整为如下：LSM tree 是一种横跨几种速度，容量不同的介质的数据索引和IO的pattern……，剩下的定义和上方的一样。
0x01 LSM tree 与分布式架构
最近转组到一个数据组，开始接触一些诸如分布式系统，Linux IO等相关的一些知识，学习组内一套基于 LSM tree 为核心的分布式存储架构的设计。大部分现有的 LSM tree 的系统通常都作为单机引擎，提供极高 RW 性能。
我司因为业务特殊，无法使用公有云，开源的对象存储也不够用。内部维护了一个几十 PB 的一个分布式对象存储，整体架构是基于 LSM-tree 的，部署横跨 nvme，hdd 等不同速度容量的介质，个人认为设计的非常优雅，在此给大家介绍一下系统的设计。
0x02 L0
了解 LSM tree 的同学知道，L0就是内存层，通常是使用跳表、红黑树这种数据结构，总的来说 L0 通常是容量较小，速度较快的介质。
在对象存储提供中，我们无法通过 WAL+memtable 暂存用户的数据，因为用户的对象的 Size 通常都比较大，而且无需保证顺序（我们内部不实现 mvcc）。因此我们的 L0 不是 memtable，二十一套全闪的小型缓存，大约占整个系统的 1% 左右。
庞大的对象存储系统，大部分系统都使用 HDD 作为存储介质，如果这时有 NVME 这种介质，那么相对来说他一定能作为 L0 存在。
这套系统的 L0 使用了一个磁盘上的全闪 NVME 存储，raft + boltdb 三副本实现索引的一致性，三副本的数据按照容错域放置在不同的三台机器上的Object Store中，因为是全闪 ObjectStore + MultiRaft，可以支持极高的带宽的写入。
ObjectStore NVME 数据的写入几乎不会成为瓶颈。Raft 的 Apply 和 Commit 等后期可能成为瓶颈，需要合理的对数据进行分片，让索引的 IOPS 在可控范围内。https://github.com/dashjay/supreme-blob-storage，本人根据实现思想，进行了一个版本的简单实现，大概就是 raft（index）+ object store（fs base），实现非常简单。
分析他的架构后期可能出现：索引与数据同盘可能导致，数据的大量写入时拖慢索引的小 IO（埋个坑，之前排查过一次三星盘大量 64K 的 IO 把 4K 的 IO 的延迟拖慢到 10 毫秒这个数量级的分析。）
0x03 L>1
学习过 LSM tree 的同学知道，L1层以上通常都是在磁盘上，存储的格式是一种类似 SST（sorted string table），是一种能够在磁盘上支持：get, list 操作的数据结构。
（to be continued）