Chapter 7

Log-Structured Storage

当会计师需要去修改他的记录时，他不会删除已经有的记录，而是会创建一条心的正确的记录。在季度报告发布时，他会包含许多的小更改，用来修正签一份报告信息。为了得到底线，你需要遍历记录并计算出他们的总和。

类似的，不可变的存储数据结构不允许对现有的文件进行修改：表只会进行一次写入并且永远不会再进行修改，做为替代，他会将一个新的记录添加到文件的末端，为了得到最终的值 (或推断是否缺失)，需要获取多个文件的信息来重建这些记录。与此对比，可变的存储数据结构会直接在磁盘原本的位置上进行修改。

不可变数据结构通常会用在函数式编程语言、而且因为他们所具有的安全特征，他们会会越来越流行：在创建后不可变数据结构就不会产生变更，对他的引用可以并发的进行访问，以及因为他是不可以修改的，这点可以保证他的完整性。

在更高的层面，这严格的描述了数据在存储数据结构的内部及外部的差异。在内部，不可变文件可以存在多个副本，更新的那份会覆盖较旧的那份，在可变文件中通常只会持有最新的一个副本。在访问时不可变文件会被处理，多余的副本会被整合，并且最新的结果才会返回给客户端。

跟讨论这个主题的树跟论文一样，我们使用 B-Tree 作为可变数据结构的例子，使用 Log-Structured Merge Trees (LSM Trees) 来作为不可变数据结构的例子。不可变的 LSM Tree 使用只附加的存储及会进行合并整合，B-Tree 定位磁盘中的数据记录，并根据他的偏移量更新对应的页。

就地更新的存储数据结构优化了读取的性能：在定位到磁盘中的数据后，对应的记录就可以直接返回给客户端了。但这是使用写入的性能作为代价的：为了就地更新磁盘中的数据记录，他首先要定位到他在磁盘中的具体位置，换句话说，只附加的存储是为写入性能做了优化的，写入不需要定位磁盘中的具体数据记录并进行重写。但是这同时造成了读取上的开销，因为在读取时需要获取数据记录的多个版本并对其进行整合。

到现在为止，我们大部分时间都在讨论可变的存储数据结构，不可变的存储也在 copy-on-write B-Tree、FD-Tree 跟 Bw-Tree 中有提到，当还有很多种其他的方式来实现不可变数据机构。

因为 B-Tree 的结构跟构造方式，大部分的读取、写入跟维护产生的 I/O 操作都是随机的。每个写入操作首先需要定位到数据记录所在的页才能在稍后对其进行修改。B-Tree 需要节点在分裂跟合并时为已经写入的记录进行重新分配。在一段时间后， B-Tree 的页会需要进行维护，页都是固定大小的，在创建时会预留空间来支持后续的写入操作。另一个问题是，就算我们只对页的一个 Cell 进行修改，也需要重写整个页。

有一些其他的方式可以减轻这些问题，让一些 I/O 操作变成顺序的，避免在修改时重写页。其中一个方式是使用不可变的数据机构。在本章，我们会集中讨论 LSM-Trees：如何构建、具有什么属性、与 B-Tree 的区别。