读书笔记|可靠性，可扩展性，可维护性
基于前面的存储中介绍，每个日志结构存储段都是一系列键值对。这些对按照它们写入的顺序出现，如何需要按照键值对的顺序，就需要 排序字符串表（Sorted String Table），简称 SSTable:键值对的序列按键排序。同时，要求每个键只在每个合并的段文件中出现一次。
SSTable 与散列索引日志段相比，有几个很大的优势：
合并段是简单而高效的，即使文件大于可用内存。方法类似于归并排序。
如果在几个输入段中出现相同的键，该怎么办？系统会保留最近段的值，并丢弃旧段中的值。
为了在文件中找到一个特定的键，你不再需要保存内存中所有键的索引。因为是有序的，可以先查找出键所处的范围，然后就找到这个键所在的偏移量的区间。比如可以从 handbag 和 handsome 的偏移量找到 handiwork 的区间。
构建和维护SSTables
如何让数据首先被按键排序呢？在内存中排序简单的多，比如红黑树、AVL 树；
存储工作的操作步骤：
写入时，将其添加到内存中的平衡树数据结构（例如，红黑树）。这个内存树有时被称为内存表（memtable）。
当内存表大于某个阈值（通常为几兆字节）时，将其作为SSTable文件写入磁盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的SSTable文件成为数据库的最新部分。当SSTable被写入磁盘时，写入可以继续到一个新的内存表实例。
为了提供读取请求，首先尝试在内存表中找到关键字，然后在最近的磁盘段中，然后在下一个较旧的段中找到该关键字。
有时会在后台运行合并和压缩过程以组合段文件并丢弃覆盖或删除的值。
如何解决数据库崩溃，则最近的写入（在内存表中，但尚未写入磁盘）将丢失的问题？
我们可以在磁盘上保存一个单独的日志，每个写入都会立即被附加到磁盘上，该日志不是按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到SSTable时，相应的日志都可以被丢弃。
用 SSTables 制作LSM树
LSM 树：在 LevelDB 和 RocksDB 使用，国内的 TiDB, OceanBase，持久化缓存 Pika
性能优化
当查找数据库中不存在的键时，LSM树算法可能会很慢：您必须检查内存表，然后将这些段一直回到最老的（可能必须从磁盘读取每一个），然后才能确定键不存在。解决办法：布隆过滤器。布隆过滤器是用于近似集合内容的内存高效数据结构，它可以告诉您数据库中是否出现键，从而为不存在的键节省许多不必要的磁盘读取操作。
SSTables 被压缩和合并的顺序和时间 ，大小分层采用高性能压缩算法进行"压实"。
LevelDB和RocksDB使用平坦压缩（LevelDB因此得名）；
HBase 使用大小分层
Cassandra 同时支持。
B树
像SSTables一样，B树保持按键排序的键值对，这允许高效的键值查找和范围查询。不同：
1. 日志结构索引将数据库分解为可变大小的段，通常是几兆字节或更大的大小，并且总是按顺序编写段。
B 树将数据库分解成固定大小的块或页面，传统上大小为4KB，页面是读写的最小单位。
这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。
每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在磁盘而不是在内存中
查找过程：
一个页面会被指定为B树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。
每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。
最后，我们可以看到包含单个键（叶页）的页面，该页面包含每个键的内联值，或者包含对可以找到值的页面的引用。
更新过程：
搜索包含该键的叶页，更改该页中的值，并将该页写回到磁盘原来的位置（对该页的任何引用保持有效）
插入过程：
找到其范围包含新键的页面，并将其添加到该页面。
如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以解释键范围的新分区。
删除过程：
删除一个键（同时保持树平衡), 存在写放大的问题，更新数据，还要维护索引，树平衡。
深度：
该算法确保树保持平衡：具有 n 个键的B树总是具有 O(logn) 的深度。
大多数数据可以放入一个三到四层的 B 树，所以你不需要遵追踪多页面引用来找到你正在查找的页面。
让B树更可靠
B树的基本底层写操作是 用新数据覆盖磁盘上的页面。假定覆盖不改变页面的位置；
日志结构索引（如LSM树）只附加到文件（并最终删除过时的文件），但从不修改文件。
危险操作：
插入数据过大导致页面拆分，则需要编写已拆分的两个页面，并覆盖其父页面以更新对两个子页面的引用。
写损坏:（OS 页面大小和数据库页面大小不一致）如果数据库在仅有一些页面被写入后崩溃，那么最终将导致一个损坏的索引。
预写式日志（WAL）
为了提高数据的安全性，B树会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（redo log））。
这是一个仅追加的文件，每个B树修改都可以应用到树本身的页面上。
当数据库在崩溃后恢复时，这个日志被用来使B树恢复到一致的状态。
并发访问：
更新页面时，如果多个线程要同时访问B树，则需要仔细的并发控制，否则可能会看到树处于不一致的状态。
通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成
LSM 比较简单：在后台完成所有的合并，不干扰查询；通过「原子交换」把旧的分段变为新的分段。
B树优化
LMDB 数据库中使用「写时复制方案 」，而不是不是覆盖页面并维护 WAL 进行崩溃恢复。
修改的页面被写入到不同的位置，并且树中的父页面的新版本被创建，指向新的位置。
保存键的缩略信息，而不是完整的键。
键只用保存一个区间，而不是具体的数值（类似于 B+树）。
可以包含更多的键，减少树的层次。
不方便扫描大部分关键词的范围查找。
a. 许多B树实现尝试布局树，使得叶子页面按顺序出现在磁盘上。但是，随着树的增长，维持这个顺序是很困难的。
b. 相比之下，由于LSM树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在磁盘上彼此靠近。
额外的指针已添加到树中。
例如，每个叶子页面可以在左边和右边具有对其兄弟页面的引用，这允许不跳回父页面就能顺序扫描。
B树的变体如分形树借用一些日志结构的思想来减少磁盘寻道（而且它们与分形无关）。
比较B树和LSM树
通常LSM树的写入速度更快，而B树的读取速度更快。LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。
LSM树的优点
B 树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）
即使在该页面中只有几个字节发生变化，也需要一次修改整个页面的开销。
有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新
写放大
反复压缩和合并SSTables，日志结构索引也会重写数据。
在数据库的生命周期中写入数据库导致对磁盘的多次写入 —— 被称为写放大（write amplification）。
存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。
LSM树通常能够比B树支持更高的写入吞吐量：
它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载）
因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面
这种差异在磁性硬盘驱动器上尤其重要，顺序写入比随机写入快得多。
文件碎片：
LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。
B树存储引擎会由于分割而留下一些未使用的磁盘空间
由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时
LSM树的缺点
日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。B树的行为则相对更具可预测性。
高写入吞吐量：
磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。
写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多。
压缩和读取的速度：
如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。
磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。
键出现的个数：
B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。
有利于事务实现:在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在B树索引中，这些锁可以直接连接到树。
