Fundamentals
Storage and Retrieval

作为一个开发者，我们可能不会从零开始实现一个数据库，但是我们需要知道如何为我们的应用合适地选择一个存储引擎(store engine) 为了能调试好一个存储引擎，我们需要大致了解存储引擎的内部原理，他们是如何工作的。

尤其是针对事务型和分析型这两种工作负载，不同的存储引擎有着非常大的优化差异。

接着我们介绍两种常见的数据库，traditional relational databases 和 NoSQL databases。以及两类存储引擎: log-structured storage engine and page-oriented storage engines such as B-tree.

最简单的一个存储引擎

假设我们设计一种 key-value 存储引擎，每次输入一个 key-value pair，我们就将其存储在一个文件中，key-value pair 之间用逗号分隔，每个 pair 占一行

123,{"a":"1"}
234,{"b":"2"}
234,{"b":"3"}

这种存储结构在数据量少的时候性能是非常好的，当数据量非常大时，我们必须从头到尾扫描整个文件，查找该key出现的位置，这样的时间复杂度是O(n)。为了高效找到数据库中特定key的位置，我们需要不同的数据结构：索引。 索引的核心思想就是保留其中的一些元数据metadata,使其充当坐标帮助我们快速定位到数据的位置。 索引是从主数据派生出来的附加结构，很多数据库允许你添加删除索引，但是主数据不会受到影响，它只会影响查询性能 维护索引会对写入产生额外开销，因为每次写入都要更新索引。 存储系统中一个重要的权衡就是精心选择索引，它会加快读取速度，但是会减慢写入速度。 通常数据库不会默认添加索引，需要你自己手动添加索引

Hash Indexes 哈希索引

我们从最简单的key-value数据的索引开始 我们的策略是在内存中保存一个哈希表hash table, 每个key对应数据文件中的key，每个value对应数据文件中的字节偏移量byte offset. 我们假设为一个视频网站提供视频观看量存储服务，key是视频id，value是观看量，

in-memery
{
    cat: 0,
    dog: 1
}

data file
cat, 100
dog, 200

在这种工作负载中，写入非常多，但是很多都是重复的key 我们不断的追加日志到文件中，如何避免磁盘空间不足？ 一个好的解决方案就是将日志分成一定大小的段，当一个段写满后，我们将其压缩成一个更小的段，这样我们就可以删除旧的段，释放磁盘空间。 此外由于压缩可以是段很小，所以我们可以同时压缩多个段合并在一起，这样可以减少磁盘的读写次数，提高性能。 合并压缩过程中，发生的读写如何处理？ 段在写入之后永远不会被修改，因此合并后的段可以写到新文件。 合并和压缩过程可以在后台执行，这个过程中的读写请求还是由旧的文件处理 合并压缩完成后，我们将读写请求切换到新文件，然后删除旧文件。

每个段都有自己的内存中哈希表，为了找到键的值，我们先检查最新段的哈希表，然后检查旧的段，以此类推。 因为合并过程段会保持的比较小，所以不会查询很多哈希表

一些细节问题

  • 文件格式：csv格式不是最佳格式，二进制格式更好，因为它更紧凑，更容易解析
  • 删除记录：如果要删除键和对应的值，我们需要在文件中添加一条特殊的删除记录，当日志合并时，删除记录告诉合并过程删除旧的记录
  • 崩溃恢复：？
  • 部分写入：数据库可能在写入一半时崩溃，我们可以使用checksum来检测和抛弃损坏的数据
  • 并发控制：由于写入是严格按照顺序添加到日志中的，所以常见的实现选择是只有一个写入线程。数据文件段是追加时的，且不可改变，所以他们可以被多个线程同时读

追加式日志看起来比较浪费，为什么不在更新的时候直接更新旧数据？但这样的设计有以下好处：

  • 顺序写入比随机写入更快，由于追加日志和合并日志是顺序写入的，他会比随机写入快，尤其是在磁盘上，在ssd上也有好处
  • 并发控制和崩溃恢复更简单，因为我们只需要处理追加操作，而不需要处理更新操作
  • 合并旧段可避免数据文件随着时间的推移而变得碎片化的问题。

但是hash table index 也有限制，局限性：

  • 因为hash table index在内存中，如果你有非常多的key，那么你的内存可能会不够。
  • 范围查询，比如查找所有key在某个范围内的值，hash table index不适合这种查询，你需要查询所有的key

SSTables and LSM-Trees

Each log-structured storage segment is a sequence of key-value pairs. If we require that the sequence of key-value pairs is sorted by key, we call this formated Sorted String Table (SSTable). We also require that each key appears once within each merged segment file.

SSTables 相较于带有哈希索引的日志段有以下几个主要优势：

  1. 合并段文件简单且高效：即使文件比可用内存大，合并仍然可以顺利进行。类似归并排序算法，读取输入文件的首个键值，复制最小的键到输出文件，重复这个过程直到完成合并。此操作生成一个新的合并段文件，按键排序。如果相同的键出现在多个输入段中，由于每个段代表一段时间内的所有数据，因此只需保留最新段的值，丢弃旧段的值。
  2. 不需要在内存中保存所有键的索引：由于段文件是按键排序的，你只需要知道部分键的偏移量。例如，如果知道键 "handbag" 和 "handsome" 的偏移量，就可以通过它们之间的偏移量来定位可能存在的 "handiwork" 键。这样，内存中的索引可以很稀疏，因为几千字节的段文件可以快速扫描。
  3. 压缩块以减少I/O带宽：由于读取请求通常需要扫描一系列键值对，因此可以将这些记录分组并在写入磁盘前压缩。内存索引指向压缩块的起始位置，压缩不仅节省了磁盘空间，还减少了I/O带宽的使用。

构建和维护 SSTables 的过程如下：

虽然数据需要按键排序，但写入操作可以是任意顺序。将数据按键排序存储在磁盘上是可行的，但在内存中维护排序结构更容易。可以使用红黑树或 AVL 树等平衡树结构，这些结构允许任意顺序插入键并按顺序读取。

存储引擎的工作流程为：

  1. 当写入操作发生时，将其添加到内存中的平衡树数据结构（例如红黑树），该结构称为 memtable。 当 memtable 的大小超过设定的阈值（通常为几兆字节）时，将其写入磁盘生成一个 SSTable 文件。这很高效，因为 memtable 中的键值对已经按键排序。新的 SSTable 文件成为数据库中最新的段。在写入 SSTable 的同时，写入操作可以继续添加到新的 memtable 实例中。
  2. 对于读取请求，首先在 memtable 中查找键，然后在最新的磁盘段中查找，再逐步查找更旧的段。
  3. 定期在后台运行合并和压缩过程，以合并段文件并删除被覆盖或删除的值。

该方案运行良好，但有一个问题：如果数据库崩溃，尚未写入磁盘的最新写入（保存在 memtable 中）将丢失。为了解决这个问题，可以在磁盘上保留一个单独的日志，所有写入操作会立即追加到该日志中。该日志不按排序存储，主要用于数据库崩溃后恢复 memtable。每次将 memtable 写入 SSTable 后，相关的日志就可以被丢弃。

性能优化

LSM-tree算法在查询数据库中不存在的key时可能会非常慢，因为你需要先检查内存表，然后检查磁盘表，然后检查更旧的磁盘表，以此类推。 为了优化这种问题，存储引擎通常会使用额外的bloom filter来快速检查key是否存在于磁盘表中。

在确定如何对 SSTables 进行压缩和合并时，也有不同的策略。最常见的选项是 按大小分层的压缩 和 分级压缩。在按大小分层的压缩中，较新且较小的 SSTables 会依次合并到较旧且较大的 SSTables 中。而在分级压缩中，键范围被拆分为较小的 SSTables，旧数据被移入不同的“级别”，这使得压缩过程更为渐进，并减少了磁盘空间的占用。

尽管其中有许多细微差别，LSM-tree 的基本思想——保持一系列 SSTables 并在后台合并它们——简单且有效。即使数据集远大于可用内存，它仍能良好运行。由于数据是按键排序存储的，可以高效地执行范围查询，同时由于磁盘写入是顺序的，LSM-tree 可以支持非常高的写入吞吐量。

B-tree

日志结构索引（log-structured index)我们已经讨论了很多，但是它们并不是最常见的索引，最广泛使用的索引是B-tree 和SSTable一样，B-tree按key排序键值对， B-trees keeps key-value pairs sorted by key, which allows efficient key-value lookup and range queries.

日志结构索引将数据库分解成大小可变的段，但是B-tree将数据库分解成固定大小的块，每个块称为一个页page。每个页通常是4KB或8KB，这样可以很好的利用现代计算机的内存分配和磁盘读写。 Each page can be identified using an address or location, which allows one page to refer to another—similar to a pointer, but on disk instead of in memory。

One page is designated as the root of the B-tree; whenever you want to look up a key in the index, you start here. The page contains several keys and references to child pages. Each child is responsible for a continuous range of keys, and the keys between the references indicate where the boundaries between those ranges lie.

Eventually we get down to a page containing individual keys (a leaf page), which either contains the value for each key inline or contains references to the pages where the values can be found.

If you want to update the value for an existing key in a B-tree, you search for the leaf page containing that key, change the value in that page, and write the page back to disk (any references to that page remain valid).

If you want to add a new key, you need to find the page whose range encompasses the new key and add it to that page.

If there isn’t enough free space in the page to accommodate the new key, it is split into two half-full pages, and the parent page is updated to account for the new subdivision of key ranges.

This algorithm ensures that the tree remains balanced: a B-tree with n keys always has a depth of O(log n). Most databases can fit into a B-tree that is three or four levels deep, so you don’t need to follow many page references to find the page you are look‐ ing for.

使B-tree可靠

B树的基本写操作是用新数据覆盖磁盘上的页面，这意味着页面的物理位置不变，所有对该页面的引用仍然有效。这与日志结构索引（如LSM树）形成鲜明对比，后者只会在文件中追加数据，从不修改文件。对于磁盘上的页面覆盖操作，机械硬盘需要移动磁头等待合适的扇区，SSD则需要擦除并重写较大的存储块。

此外，有时多个页面需要同时更新，例如当插入操作导致页面过满时，需要将页面拆分，并同时更新父页面的引用。这种操作存在风险，因为如果数据库在部分页面写入后崩溃，可能会导致索引损坏。为了应对崩溃，B树通常会在磁盘上包含一个预写日志（WAL），所有的B树修改都需要先写入这个追加日志，再应用到树的页面上。

崩溃后，日志可以用于恢复B树的一致性。此外，更新页面时需要小心的并发控制，以防多个线程访问时看到不一致的状态，通常通过轻量锁（latches）来保护数据结构。而日志结构的索引方法则更加简单，因为合并操作在后台完成，不影响查询，并且通过原子方式交换新旧段。

B-tree optimizations

Many optimizations have been developed over the years. To mention just a few:

  • use a copy-on-write scheme [21]. A modified page is written to a different location, and a new version of the parent pages in the tree is created, pointing at the new location. This approach is also useful for concurrency control.
  • 我们可以通过不存储整个键而是将其缩写来节省页面空间。
  • Many B- tree implementations therefore try to lay out the tree so that leaf pages appear in sequential order on disk.
  • Additional pointers have been added to the tree. For example, each leaf page may have references to its sibling pages to the left and right, which allows scanning keys in order without jumping back to parent pages.
  • B-tree variants such as fractal trees [22] borrow some log-structured ideas to reduce disk seeks

B-trees and LSM-trees compared

As a rule of thumb, LSM-trees are typically faster for writes, whereas B-trees are thought to be faster for reads [23]. Reads are typically slower on LSM-trees because they have to check several different data structures and SSTables at different stages of compaction.

A B-tree index must write every piece of data at least twice: once to the write-ahead log, and once to the tree page itself.

There is also overhead from having to write an entire page at a time, even if only a few bytes in that page changed.

Advantages of LSM-trees

LSM-trees are typically able to sustain higher write throughput than B- trees, partly because they sometimes have lower write amplification (although this depends on the storage engine configuration and workload), and partly because they sequentially write compact SSTable files rather than having to overwrite several pages in the tree

LSM-trees can be compressed better, and thus often produce smaller files on disk than B-trees. B-tree storage engines leave some disk space unused due to fragmenta‐ tion

Downsides of LSM-trees

在压缩阶段会影响读写性能，虽然存储引擎尝试使用渐进式压缩来减轻这个问题，但是磁盘读写资源有限，当发生一个大的压缩操作时，可能会影响读写性能。 日志结构存储引擎反应时间会有变化，但是b-tree会有更加稳定的反应时间。

压缩的另一个问题出现在高写入吞吐量时：磁盘的有限写入带宽需要在初始写入（将内存表记录并刷新到磁盘）和在后台运行的压缩线程之间共享。写入空数据库时，初始写入可以使用整个磁盘带宽，但数据库越大，压缩所需的磁盘带宽就越大。

如果写入吞吐量很高，并且压缩配置不周，则压缩可能无法跟上传入写入的速率。在这种情况下，磁盘上未合并的段数会不断增加，直到磁盘空间用完，读取也会变慢，因为它们需要检查更多段文件。通常，即使压缩无法跟上，基于 SSTable 的存储引擎也不会限制传入写入的速率，因此您需要进行显式监控以检测这种情况

B 树的一个优点是每个键都只存在于索引中的一个位置，而日志结构化存储引擎可能在不同的段中拥有相同键的多个副本。这一方面使 B 树在想要提供强大事务语义的数据库中具有吸引力：在许多关系数据库中，事务隔离是使用键范围上的锁来实现的，而在 B 树索引中，这些锁可以直接附加到树

B 树在数据库架构中根深蒂固，并为许多工作负载提供始终如一的良好性能，因此它们不太可能很快消失。在新的数据存储中，日志结构化索引越来越受欢迎。没有快速简便的规则来确定哪种类型的存储引擎更适合您的用例，因此值得进行实证测试。

其他索引结构

  • Storing values within the index
  • Multi-column indexes
  • Full-text search and fuzzy indexes
  • Keeping everything in memory
Consistent HashingACID vs BASE Properties in Database