日志结构化存储

日志结构化存储系统的基础组织是一个日志，即一个只可添加数据输入的序列。每当你有新的数据要写入的时候，你只需要简单的添加它到日志的末尾，而不需要在磁盘中为它寻找一个位置。

提前说明：这些日志就是真实的日志，放在 disk 上的，其中 key-value 可以简单理解成文件中的每个字符串和偏移量。只是即使同样的“abc”字符串，出现在日志的不同位置，也不能理解为相同的 key，明白？！！有一种“哈希映射”的做法，将所有 key 都缓存到内存中，即使大内存的机器也不一定能做到，只适合部分场景，比如 Bitcash存储引擎，适合 value 经常更新的场景。
始终追加写入同一个日志文件并不可取，会耗尽磁盘空间。
解决办法：日志分成特定大小的段，到达该长度时关闭该文件，开始写入新的文件，对旧文件压缩。
1. 压缩意味着key-value 的历史值被抛弃，只保留每个 key 的最新值。
2. 压缩过的段如果 size 小，可以多段合并。此时 compact 和 merge 操作同时进行，技术点上，很类似于 copy on write /不可变类的修改过程 ——使用旧文件满足压缩时刻的读写请求，压缩合并在后台进行，完成后，再将读写请求定位到新文件，并删除旧文件。

下面的 SSTables 和 LSM 树都是日志分段压缩&合并技术基础上演进的。

Sorted String Tables。排序字符串表。放在 disk 上的！！！
在日志分段压缩合并时，使用归并排序的技术，保证key有序。同时需要被合并的各段（即 SSTables）也是有序的才行。
如果合并时，多段存在相同的 key，那么仅保留时间最新的 key 对应的 value 值。
不需要将索引中的所有 key 取到内存中，利用排序特性，可以索引到临近的 key 值，然后再进行扫描。每千字节的段文件只需要一个键就足够了，因为几千字节很快可以被扫描。
因为索引的稀疏性，读操作始终要扫描多个 key-value，所以将这些记录分组压缩到块中，索引的每个条目都指向压缩块的开始处。（有点类似于磁盘上使用的 B 树，但 B 树一般固定大小，约 4KB，此 SSTable 的大小并不固定）

SSTables 的构建和更新

保证 key 有序的办法：磁盘上使用 B 树，内存中使用平衡树（ AVL 或者红黑树等）。使用后可以使用任意顺序插入，然后按序读取。
步骤：
1. 写入时，写到内存中的平衡树中，这种树也称为内存表。
2. 内存表当 size到一定阈值时，作为 SSTable 写入disk。此时发生的写操作，会作用到下一个新的内存表实例中。
3. 读操作时，先查找内存表，否则去最新的磁盘段，否则去旧一些的磁盘段，依此类推。

LSM 树基本思想：保存一系列在后台合并的 SSTables，可以支持非常高的写入吞吐量。

写放大：一种现象，比如一次写库操作，需要写多次磁盘。写放大会导致性能代价，存储引擎写入 disk 的次数越多，可用磁盘带宽内每秒写入次数越少。

许多 B 树尝试布局树，使得叶子页面按顺序出现在 disk 上，但随着树的增长，维持这个顺序是很困难的。LSM 树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在 disk 上彼此靠近。
LSM 树写入更快，读取较慢，因为可能需要查多个 SSTables。B 树读取更快。
B 树的写操作需要①写 redo；②写入树页面，如果发生分裂，要写更多。LSM 树对 SSTable 压缩合并时也会发生写放大，但写放大比 B 树小，支持更高的写入吞吐量，这是因为顺序写入紧凑的 SSTable文件，而不是树中的几个整页面，主要是“顺序写”的优势。
LSM 的查询时间不可预测，B 树可预测。
LSM 的压缩过程对磁盘吞吐量也有影响，如果数据库较大，压缩可能占用过多的磁盘写入带宽。压缩如果赶不上写入速率时，即写入吞吐量较高时，也会拖慢磁盘读取速度。
B 树的一个优点是每个键只存在于索引的一个位置，在需要提供事务支持的业务中，通过键做事务隔离就很合适了。

在 B 树中，基于列的存储时，如果在中间新加一列，这可能不得不重写所有的列文件。通过 LSM 树可以很好地处理这个问题，因为写操作会首先进入内存的存储中，然后添加到一个已排序的数据结构中，在内存中基于行或者列已经不影响速度了。等积累足够的写入数据后，它们会跟磁盘上的列文件合并。