数据库全面知识详细讲解

大约一年前，我在考虑下一个项目应该选择哪个数据库时，发现自己对数据库的区别了解得还不够。我浏览了不同的数据库网站，看到的大多是市场营销和我不理解的词汇。

这时，我决定阅读 Alex Petrov 所著的《Database Internals》和 Martin Kleppmann 所著的《Designing Data-Intensive Applications》这两本书。

这两本书激起了我足够的好奇心，于是我开始编写自己的小型数据库，并将其命名为 dbeel。

这篇文章基本上是对这两本书的简短总结，重点是数据库工程师在洗澡时思考的基本问题。

bashdb
让我们从最简单的数据库程序开始，它只有 2 个 bash 函数（我们称之为 bashdb）：

#!/bin/bash

db_set() {
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

用这两句函数试验操作数据：

$ db_set 500 '{"movie": "Airplane!", "rating": 9}'

$ db_set 111 '{"movie": "Tokio Drift", "rating": 6}'

$ db_get 500
{"movie": "Airplane!", "rating": 9}

你可能会在 bashdb 中发现至少一打的问题。现在，我不会对所有可能存在的问题进行一一列举，在本篇文章中，我将重点讨论以下问题：

• 持久性 - 如果机器在成功执行 db_set 之后崩溃，数据可能会丢失，因为数据没有刷新到磁盘上。
• 原子性 - 如果在调用 db_set 时机器崩溃，数据可能会被部分写入，从而破坏我们的数据。
• 隔离性 - 如果一个进程调用 db_get，而另一个进程在同一项目上同时调用 db_set，则第一个进程可能只读取部分数据，导致结果损坏。
• 性能 - db_get 使用的是 grep，因此搜索会逐行进行，搜索速度为 O(n)，n = 保存的所有项目。

你能自己解决这些问题吗？如果你能，那就太好了，你不需要我，你已经了解数据库了

在下一节中，我们将尝试解决这些问题，让 bashdb 成为我们在生产中可能会用到的真正的数据库（不是真的，请不要使用，使用 PostgreSQL 就可以了）。

改进 bashdb 以实现 ACID
在我们开始之前，要知道这些问题大多不是我自己想出来的，它们是名为 ACID 的缩写的一部分，几乎所有数据库都在努力保证这一点：

• 原子性（Atomicity）--不要与多线程的原子性定义混淆（原子性更类似于隔离性），如果在写入过程中发生故障，数据库会撤销或完全中止事务，就像写入从未开始一样，不会留下部分写入的数据，那么事务就被视为原子性的。
• 一致性--这其实并不属于作为数据库事务属性的 ACID，因为它是应用程序的属性。
• 隔离 - 在并发访问相同数据时不会出现竞赛条件。有多种隔离级别，我们稍后将讨论其中的一些。
• 耐久性 - 谈到数据库，首先想到的就是耐久性。它应该永远存储您写入的数据，即使在猴子拔掉电源插头的情况下也是如此。

但是，如何才能让 bashdb 成为 ACID 呢？

我们可以从耐久性入手，因为通过在 db_set 中写入后立即运行 sync，让 bashdb 变得耐久是很容易的：

db_set() {
    echo "$1,$2" >> database && sync -d database
}

耐久性
写入系统调用会将缓冲区写入文件，但谁说它会写入磁盘？

你写入的缓冲区可能会在写入非易失性内存的途中进入任何缓存。例如，内核会将缓冲区存储在页面缓存中，每一页都标记为脏页，这意味着内核会在未来某个时候将缓冲区刷新到磁盘上。

更糟的是，磁盘设备或管理磁盘的设备（例如 RAID 系统）可能也有写缓存。

那么，如何告诉中间的所有系统将所有脏页面刷新到磁盘上呢？
为此，我们有了 fsync / fdatasync，让我们看看它有什么用：

$ man 2 fsync

...

fsync() 会传输（"刷新"）文件描述符 fd 所引用文件的所有已修改内核数据（即已修改的缓冲缓存页）
文件描述符 fd 调用的文件的所有已修改内核数据（即已修改的缓冲缓存页）传输（"刷新"）到磁盘设备（或其他永久存储设备
设备），这样即使系统崩溃或重启，也能检索到所有更改的信息。
这包括写入或刷新磁盘缓存（如果存在）。
调用会阻塞，直到设备报告传输已完成。

...

fdatasync() 类似 fsync()，但不会刷新已修改的元数据，除非该元数据本身
以便正确处理后续数据检索。

...

简而言之，fdatasync 会刷新我们写入的脏的原始缓冲区。fsync 还会刷新文件的元数据，如 mtime，但我们并不关心这些元数据。

同步程序基本上就像在所有脏页面上运行 fsync，除非参数中指定了特定文件。它有一个 -d 标志，可以让我们调用 fdatasync 代替 fsync。

添加同步功能的最大缺点是性能较差。通常，同步甚至比写入本身还要慢。不过，至少我们现在是持久的了。

关于 fsync 的一个简短但重要的说明。当 fsync() 返回成功时，它表示 "自上次 fsync 以来的所有写入都已命中磁盘"，而你可能以为它表示 "自上次 SUCCESSFUL fsync 以来的所有写入都已命中磁盘"。PostgreSQL 最近（2018 年）才了解到这一点，这导致他们修改了同步行为，从重试 fsync 直到返回成功，改为在 fsync 失败时直接慌乱。这一事件一石激起千层浪，被命名为 fsyncgate。你可以在这里了解更多有关 fsync 失败的信息。

亲爱的 MongoDB 用户，要知道默认情况下每 100 毫秒同步一次写入，这意味着它不是 100% 持久的。

隔离
在 bashdb 中实现多进程隔离的最简单方法就是在读写存储文件前添加一个锁。

linux 中有一个叫做 flock 的程序，它可以锁定文件，你甚至可以给它加上 -s 标志，指定你不会修改文件，这意味着所有指定 -s 的调用者都可以同时读取文件。

flock 只需调用 flock 系统调用

有了这么棒的程序，bashdb 可以保证隔离，下面是代码：

db_set() {
    (
        flock 9 && echo "$1,$2" >> database && sync -d database
    ) 9>database.lock
}

db_get() {
    (
        flock -s 9 && grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
    ) 9>database.lock
}

最大的缺点是，现在只要我们向数据库中写入内容，就会锁定整个数据库。

剩下的就是原子性和改进算法，使其不再是 O(n)。

坏消息
很抱歉，这是我使用 bashdb 所能达到的极限，我找不到一种简单的方法来确保 bash ☹️ 中的原子性。

我的意思是，你也许可以用 mv 来实现这个功能，我把它作为一个练习留给你。

即使可行，我们还是需要解决 O(n) 的问题。

在开始 bashdb 之旅之前，我知道我们不可能在不到 10 行的 bash 中轻松解决所有这些问题，但通过尝试，希望你已经开始感受到数据库工程师所面临的问题。

存储引擎
让我们从数据库的第一个重要组件--存储引擎开始。

存储引擎的目的是为向持久存储读写数据提供一个抽象，其主要目标是快速，即请求的吞吐量大、延迟时间短。

但是，是什么让软件变得缓慢呢？

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD              150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD      1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

如果 L1 缓存的引用时间和心跳一样长（约半秒），那么从固态硬盘顺序读取 1 MB 将需要约 12 天，而从磁盘顺序读取 1 MB 将需要约 8 个月。

这就是为什么存储引擎的主要限制是磁盘本身，因此所有的设计都尽量减少磁盘 I/O 和磁盘寻道。有些设计甚至放弃了磁盘，转而使用固态硬盘（虽然价格要贵很多）。

存储引擎设计通常包括

• 在磁盘上存储项目的底层数据结构。
• ACID 事务。
• 对于 ACID 并不重要的特定用例，有些人可能会跳过这一点，以获得更好的性能。
• 一些缓存--以避免每次都从磁盘读取。
• 大多数使用缓冲 I/O，让操作系统为我们进行缓存。
• API 层--SQL/文档/图/...

可变的意思是，将数据写入文件后，数据可以在以后被覆盖，而不可变的意思是，将数据写入文件后，数据只能被再次读取。

可变 B 树
为了实现随着数据量的增加而保持良好性能的目标，我们使用的数据结构应能在最多对数时间内搜索到一个项目，而不是像 bashdb 那样需要线性时间。

你可能熟悉的一种简单数据结构是 BST（二叉搜索树），它可以在 O(log n) 时间内完成查找。

BST 的问题在于节点之间的距离是随机的，这意味着在遍历树时读取一个节点后，下一个节点很可能就在磁盘上很远的地方。为了最大限度地减少磁盘 I/O 和寻道，从磁盘读取的每一页都应尽可能从内存中读取，而不进入磁盘。

我们正在寻找的特性被称为 "空间局部性"，而 BST 最著名的 "空间局部性 "变体之一就是 B 树。

B 树是对 BST 的概括，允许节点有两个以上的子节点。它们看起来是这样的

                 ------------------------------------
                  |     7     |     16     |    |    |
                  ------------------------------------
                 /            |             \
-----------------     ----------------       -----------------
| 1 | 2 | 5 | 6 |     | 9 | 12 |  |  |       | 18 | 21 |  |  |
-----------------     ----------------       -----------------

以伪 python 代码提供搜索算法：

def get(node, key):
    for i, child in enumerate(node.children):
        if not child:
            return None

        if child.key == key:
            # Found it!
            return child.value

        if child.key > key:
            return get(node.nodes[i], key)

    return get(node.nodes[-1], key)

每次从磁盘读取页面（通常为 4KB 或 8KB）时，我们都会从内存和各种 CPU 缓存中依次遍历多个节点，尽量减少读取时浪费的字节数。

请记住，从内存和 CPU 缓存读取数据的速度要比磁盘快几个数量级，实际上快得多，因此相比之下，磁盘读取基本上是免费的。

我知道你们中有些人在读这篇文章时会想："为什么不进行二进制搜索，而要用线性方式呢？"我想对你们说，请再看看延迟比较表中的 L1 / L2 缓存引用时间。此外，由于采用了 SIMD、指令流水线和预取技术，现代 CPU 在对顺序存储器进行操作时会并行执行多个操作。读取顺序存储器在性能方面的优势会让你大吃一惊。

B 树的另一个变种是更进一步的 B+ 树，在这种树中，最后的叶子节点保存的是值，所有其他节点保存的只是键，因此从磁盘获取一个页面需要比较的键就更多了。

为了优化空间，B 树有时需要回收空间，因为在树上进行类似操作会造成数据碎片：

• 大值更新--将一个值更新为一个更大的值，可能会覆盖下一个节点的数据，因此树会将项目重新定位到不同的位置，从而在原始页面上留下一个 "洞"。
• 小值更新 - 将一个值更新为一个较小的值，会在末尾留下一个 "洞"。
• 删除--删除会在删除值原来所在的位置留下一个 "洞"。

B 树最常用作索引（PostgreSQL 默认创建 B 树索引）或所有数据的底层数据结构（我曾看到有人戏称 DynamoDB 为 "分布式 B 树"）。

不可变的 LSM 树
正如我们在延迟比较数据表中看到的，磁盘寻道的成本非常高，这也是顺序写入不可变数据结构的想法如此流行的原因。

其原理是，如果只向文件追加数据，磁盘指针就不需要向下一个要写入数据的位置移动那么多。事实证明，这对写入量大的工作负载非常有益。

这种只进行追加的数据结构被称为日志结构化合并树（Log Structured Merge tree）或简称 LSM 树，它为 RocksDB、Cassandra 和我个人最喜欢的 ScyllaDB 等大量现代数据库存储引擎提供了动力。

LSM 树的一般概念是将写入的数据缓冲到内存中的数据结构，最好是易于以排序方式迭代的数据结构（例如 AVL 树/红黑树/Skip List），一旦达到一定的容量，就将其排序刷新到一个称为排序字符串表（Sorted String Table）或 SSTable 的新文件中。SSTable 存储排序数据，让我们可以利用二进制搜索和稀疏索引来降低磁盘 I/O 量。

为了保持数据的持久性，当数据被写入内存时，其操作会被存储在前置日志（Write-Ahead Log 或 WAL）中，程序启动时会读取前置日志，将状态重置为关闭/崩溃前的状态。

删除也与写入相同，只是保存一个墓碑，而不是一个值。墓碑会在后面详述的压缩过程中被删除。

从 LSM 树中读取数据时，首先要在内存中的数据结构中搜索所提供键的项目，如果没有找到，就会遍历磁盘上的所有 SSTables（从最新的到最旧的）来搜索该项目。

你可能已经知道，随着写入的数据越来越多，要查找特定键的项目所需的 SSTables 也会越来越多，即使每个文件都进行了排序，但查看大量小文件的速度要比查看一个包含所有项目的大文件慢（查找时间复杂度：log(num_files * table_size) < num_files * log(table_size)）。这也是 LSM 树除了需要去除墓碑外，还需要进行压缩的另一个原因。

换句话说：压缩会将几个小的 SSTable 合并成一个大的 SSTable，在此过程中会移除所有墓碑，通常作为后台进程运行。

压缩可以使用二进制堆/优先级队列来实现，类似于这样：

def compact(sstables, output_sstable): 
    pop() 的结果是键值最小的项目。
    heap = heapq.heapify([(sstable.next(), sstable) for sstable in sstables])

    while (item, sstable) := heap.pop()
        if not item.is_tombstone():
            output_sstable.write(item)

        if item := sstable.next():
            # 为使代码简洁，试想推送一个存在键的项目
            在堆中，删除时间戳较小的项目，
            导致最后写入获胜。
            heap.push((item, sstable))

rust 代码：click here.

为了优化 LSM 树，你应该决定何时压缩以及压缩哪些 sstable 文件。例如，RocksDB 实现了分级压缩（Leveled Compaction），即新刷新的 sstable 位于第 0 级，一旦在某一级创建了 N 个配置的文件，这些文件就会被压缩，新文件则会被提升到下一级。

移除墓碑时一定要小心谨慎，以免造成数据复活。一个项目可能会被移除，然后在压缩时与另一个包含该项目文件一起复活，即使写入发生在删除之前，也无法知道是否在之前的压缩中被删除了。RocksDB 会一直保留墓碑，直到对文件进行压缩，使其晋升到最后一级。

Bloom 过滤器
LSM 树可以通过 Bloom 过滤器进一步优化。

Bloom 过滤器是一种概率集合数据结构，可以让你高效地检查一个项目是否不存在于集合中。检查项目是否存在于集合中的结果要么是 false，即项目肯定不在集合中；要么是 true，即项目可能在集合中，这就是它被称为概率数据结构的原因。

美中不足的是，包含 n 个项目的 Bloom 过滤器集合的空间复杂度为 O(log n)，而包含 n 个项目的普通集合的空间复杂度为 O(n)。

它们是如何工作的？答案就是哈希函数！在插入时，它们会对插入的密钥运行多个不同的散列函数，然后取结果并将 1 储存在相应的位（result % number_of_bits）中。

# Bloom 过滤器的位图，大小为 8（比特）。
bloom = [0, 0, 0, 0, 0, 0, 0, 0]

# 插入密钥 - 首先运行 2 个哈希函数。
Hash1(key1) = 100
Hash2(key1) = 55

# 然后计算相应的比特。
bits = [100 % 8, 55 % 8] = [4, 7]

# 在相应位上置 1。
bloom[4] = 1
bloom[7] = 1

# 插入后应该是这样的
[0, 0, 0, 0, 1, 0, 0, 1]

现在到了激动人心的部分--检查！

bloom = [0, 0, 0, 0, 1, 0, 0, 1]

# 要检查密钥，只需运行 2 个哈希函数，找到相应的
位，就像插入时一样：
Hash1(key2) = 34
Hash2(key2) = 35

bits = [34 % 8, 35 % 8] = [2, 3]

# 然后检查所有相应的位是否都为 1，如果为 1，则该项目
# 可能存在于集合中，否则肯定不存在。
result = [bloom[2], bloom[3]] = [0, 0] = false

# key2 从未被插入到集合中，否则这些完全相同的位
都会被设置为 1。

想想为什么即使所有校验位都是 1，也不能保证之前插入的键完全相同。

Bloom 过滤器的一个好处是，你可以通过为位图分配更多内存和添加更多散列函数，来控制确定项目不存在于集合中的几率。甚至还有相关的计算器。

LSM 树可以为每个 SSTable 存储一个 Bloom 过滤器，如果其 Bloom 过滤器验证了 SSTable 中不存在某个项目，则跳过在 SSTable 中的搜索。否则，即使项目不一定存在于 SSTable 中，我们也会正常搜索 SSTable。

提前书写日志
还记得 ACID 吗？让我们简单谈谈存储引擎如何实现 ACID 事务。

原子性和耐久性是数据是否始终正确的属性，即使在电源关闭机器时也是如此。

最常用的方法是将所有事务操作记录到一个名为 "前写日志"（Write-Ahead Log / WAL）的特殊文件中（我们在 "LSM 树 "部分简要介绍了这一点），以便在突然崩溃的情况下存活下来。

当数据库进程启动时，它会读取 WAL 文件并重建数据状态，跳过所有没有提交日志的事务，从而实现原子性。

此外，只要写请求的数据在用户收到响应之前被写入并刷新到 WAL 文件中，那么数据在启动时就会被 100% 读取，这意味着也实现了耐久性。

WAL 基本上是一种事务事件的事件源 eventsourcing 。

隔离
要实现隔离，您可以

• 使用悲观锁 - 阻止访问当前正在写入的数据。
• 使用乐观锁--更新数据副本，然后只提交事务中未被修改的数据，如果被修改，则在新数据上重试。也称为乐观并发控制。
• 读取数据副本 - MVCC（多版本并发控制）是一种常用的方法，用于避免阻塞用户请求。在 MVCC 中，当数据发生变化时，不是锁定和覆盖数据，而是创建一个新版本的数据，供新请求读取。一旦没有读取旧数据的读取器，就可以安全地删除旧数据。有了 MVCC，每个用户都能在特定时间看到数据库的快照。

ANSI/ISO 标准 SQL 92 包括在一个事务中读取数据，而另一个事务可能已经更新了该数据的 3 种不同结果：

• 脏读 - 当一个事务检索到一条已被另一个尚未提交的事务更新的记录时，就会发生脏读。

BEGIN;
SELECT age FROM users WHERE id = 1;
-- retrieves 20


                                        BEGIN;
                                        UPDATE users SET age = 21 WHERE id = 1;
                                        -- no commit here


SELECT age FROM users WHERE id = 1;
-- retrieves in 21
COMMIT;

• 不可重复读取 - 当一个事务两次检索一条记录，而该记录又被中间提交的另一个事务更新时，就会发生不可重复读取。

BEGIN;
SELECT age FROM users WHERE id = 1;
-- retrieves 20


                                        BEGIN;
                                        UPDATE users SET age = 21 WHERE id = 1;
                                        COMMIT;


SELECT age FROM users WHERE id = 1;
-- retrieves 21
COMMIT;

• 幻读 - 当一个事务两次检索一组记录，而在这两次检索之间提交的另一个事务向这组记录中插入或删除了新记录时，就会发生幻读。

BEGIN;
SELECT name FROM users WHERE age > 17;
-- retrieves Alice and Bob
    

                                        BEGIN;
                                        INSERT INTO users VALUES (3, 'Carol', 26);
                                        COMMIT;


SELECT name FROM users WHERE age > 17;
-- retrieves Alice, Bob and Carol
COMMIT;

例如，在特定事务中，您的应用程序可能不需要保证没有脏读，因此可以选择不同的隔离级别来提高性能，因为要达到更高的隔离级别，通常会牺牲性能。

以下是 ANSI/SQL 92 标准从高到低定义的隔离级别（较高的级别至少能保证较低级别所能保证的一切）：

• 可序列化 - 最高隔离级别。读取总是返回已提交的数据，包括基于范围的多行写入（避免幽灵读取）。
• 可重复读取 - 可接受幽灵读取。
• 已提交读取 - 可接受非重复读取。
• 未提交读取 - 最低隔离级别。可接受脏读。

ANSI/SQL 92 标准隔离级别经常被批评为不完整。例如，许多 MVCC 实现提供的是快照隔离，而不是可序列化隔离（关于两者的区别，请阅读提供的维基百科链接）。如果您想了解有关 MVCC 的更多信息，我建议您阅读有关 HyPer 的内容，这是一种快速可序列化的 MVCC 算法。

因此，总结本篇文章的存储引擎部分，编写存储引擎要解决的基本问题是：如何在存储/检索数据的同时，以最高效的方式保证某些 ACID 事务。

分布式系统
分布式系统应该是最后的手段，引入分布式系统会增加系统的复杂性，我们很快就会知道这一点。当非分布式解决方案已经足够时，请避免使用分布式系统。

在分布式系统中，一台你甚至不知道存在的计算机的故障会导致你自己的计算机无法使用。~莱斯利-兰波特

需要在多台计算机上分发数据的常见用例如下：

• 可用性 - 如果运行数据库的机器因某种原因崩溃或与用户断开连接，我们可能仍希望让用户使用应用程序。通过分发数据，当一台机器出现故障时，您只需将请求指向另一台持有 "冗余 "数据的机器即可。
• 横向扩展 - 传统上，当应用程序需要为超过其处理能力的用户请求提供服务时，我们会升级机器的资源（更快/更多的磁盘、内存、CPU）。这就是所谓的纵向扩展。这可能会变得非常昂贵，而且对于某些工作负载来说，根本不存在与所需资源量相匹配的硬件。此外，除了流量高峰期（想象一下黑色星期五的 Shopify），大多数情况下您并不需要所有这些资源。另一种策略称为 "横向扩展"，即在通过网络连接的多台独立机器上运行，看似作为一台机器工作。

听起来像做梦一样，对吗？分布式会有什么问题呢？

嗯，你现在已经引入了操作复杂性（部署/等......），更重要的是分区/网络分区，它因被称为 CAP 定理中的 P 而臭名昭著。

CAP 定理指出，一个系统只能保证以下 3 项中的 2 项：

• 一致性 - 读取会收到最新的写入。
• 可用性 - 所有请求都能成功，无论失败与否。
• 分区容忍度 - 尽管节点间的信息丢失或延迟，系统仍能继续运行。

现在想象一下，一个数据库在两台通过电缆连接的机器上运行，这两台机器的 CPU、内存和磁盘各不相同。当向其中一台机器发出的请求因故失败时，系统可以选择执行以下操作之一：

• 取消请求，从而牺牲可用性以换取一致性。
• 只允许在工作的机器上继续请求，这意味着另一台机器现在会有不一致的数据（从它那里读取的数据不会返回最近写入的数据），从而为了可用性而牺牲了一致性。当系统做到这一点时，它就被称为最终一致性。

我非常喜欢打破常规思维，牺牲一些增加软件复杂性的东西（比如亚马逊购物车的一致性），换取更简单的人性化解决方案，比如用户获得退款。举例来说，软件的复杂性可能比退款预算更昂贵。

要实现可用性，仅有多个节点将所有数据整合在一起是不够的，还必须有数据冗余，换句话说，一个节点存储的每个项目必须至少有另外一个节点存储该项目副本。这些节点通常称为副本，复制数据的过程称为复制。

分配更多的复制节点意味着系统的可用性更高，但缺点也显而易见，那就是需要更多的资源来存储所有这些副本。

数据副本并不需要 "整体 "存储，它们可以使用一种叫做擦除编码的技术分割并分散到多个节点上，这种技术还具有一些有趣的延迟特性（顺便说一句，brooker 的博客对于学习分布式系统来说简直太神奇了）。

一致的哈希
既然有了多个节点，就需要某种负载平衡/数据分区方法。当收到存储数据的请求时，如何确定哪个节点接收请求？

你可以采用最简单的解决方案，即除了数据外，还总是简单地获取一个主键（某个 ID），对该键进行散列，然后将结果与可用节点的数量相乘，类似于这样的方法：

def get_owning_node(nodes, key):
    return nodes[hash(key) % len(nodes)] 

这种模数法运行良好，直到节点从群集中添加或删除。一旦发生这种情况，计算就会返回不同的结果，因为可用节点的数量发生了变化，这意味着同一个密钥会选择不同的节点。为了适应这种情况，每个节点都可以迁移本应存在于不同节点上的密钥，但这样一来，几乎所有的项目都要迁移，代价非常高昂。

一些数据库（如 Dynamo 和 Cassandra）使用的一种降低节点添加/移除时需要迁移的项目数量的方法是一致性散列。

一致性散列创建了一个节点环而不是一个数组，将每个节点的名称散列放在环上。然后，每个请求的密钥都会像之前一样进行散列，但我们不会进行调制运算，而是取名称的哈希值大于或等于请求密钥哈希值的环中第一个节点：

假设节点排序，第一个节点的哈希值最小。
def get_owning_node(nodes, key):
    if len(nodes) == 0:
        return None

    key_hash = hash(key)

    for node in nodes:
        if node.hash >= key_hash:
            return node

    return nodes[0]

为了便于直观地解释，请想象一个从 0 到 99 的环形结构，其中包含名称为 "半"、"四分之一 "和 "零 "的节点，它们的哈希值分别为 50、25 和 0：

   zero
 /      \
|     quarter 
 \      /
   half

假设用户现在想设置一个键为 "four-fifths"、哈希值为 80 的项目。名称哈希值大于或等于 80 的第一个节点是 "half"（哈希值为 50），因此它就是接收请求的节点！

选择副本非常简单，当一个项目被设定存储在一个特定的节点上时，逆时针绕环一周，下一个节点将存储该项目副本。在我们的示例中，"零 "是 "半 "拥有的所有项目的副本节点，因此当 "半 "死亡，请求将被路由到 "零 "时，"零 "可以为这些请求提供服务，从而保持系统的可用性。这种方法有时被称为无领导复制（Leaderless Replication），被 Cassandra 等 "Dynamo "风格的数据库所采用。

另一种方法是选择一个领导节点和复制节点，这就是领导者选举（Leader Election）。

现在，向集群添加节点时会发生什么？让我们添加一个名为 "three-quarters"、哈希值为 75 的节点，"four-fifths "项目应迁移到新的 "three-quarters "节点，因为对它的新请求现在将指向它。

这种迁移过程的成本要比之前的模数解决方案低得多。需要迁移的键的数量平均等于 num_keys / num_nodes。

一个很酷的技巧是引入虚拟节点的概念，即在环中添加一个节点的多个实例，以降低某些节点比其他节点拥有更多项目的几率（在我们的例子中，"一半 "节点平均存储的项目数是其他节点的两倍）。您可以生成虚拟节点名称，例如在节点名称后添加一个索引作为后缀（"half-0"、"half-1 "等），然后哈希值将在环上产生一个完全不同的位置。

无领导复制
在无领导设置中，你可以获得惊人的可用性，同时牺牲一致性。如果写入请求的所有节点宕机，数据将被写入副本，而一旦所有节点恢复运行，读取请求将读取过时的数据。

当特定请求需要一致性时，读取请求可以并行发送到多个副本节点和拥有节点。客户端将选择最新的数据。写请求通常会并行发送到所有副本节点，但只等待其中一些节点的确认。通过选择读取请求的数量和写入请求确认的数量，可以调整请求级别的一致性。

要知道一个请求是否一致，只需验证 R + W > N/2 + 1 即可，其中：

• N - 持有数据副本的节点数。
• W - 必须确认写入才能成功的节点数。
• R - 必须响应读取操作才能成功的节点数。

向多数节点（W 或 R 等于 N/2 + 1）发送请求称为法定人数。

选择正确的读取作为最新写入的读取称为冲突解决，这并不是一项简单的任务，你可能认为只需比较时间戳并选择最大的时间戳就足够了，但在分布式系统中使用时间是不可靠的。

但这并不妨碍 Cassandra 使用时间戳。

每台机器都有自己的硬件时钟，由于时钟并不完全准确（通常是石英晶体振荡器），因此会发生漂移。使用 NTP（网络时间协议）对时钟进行同步，即服务器从 GPS 接收器等更精确的时间源返回时间，但这并不足以提供精确的结果，因为 NTP 请求是通过网络（另一个分布式系统）发出的，我们无法确切知道在收到响应之前会经过多少时间。

实际上，谷歌的 Spanner 通过使用特殊的高精度时间硬件实现了与时钟的一致性，其 API 公开了每个时间戳的时间范围不确定性。您可以在这里阅读更多相关信息。

但是，如果时钟如此不可靠，我们还怎么知道哪个值是正确的呢？

有些系统（例如 Dynamo）尝试使用版本矢量（Version Vectors）来部分解决这个问题，即为项目的每个版本附加一个（节点、计数器）对，这样就能找到不同版本之间的因果关系。通过查找值的版本（计数器较高），可以移除值的某些版本，从而使问题更容易解决。

举例说明冲突是多么容易发生。最后，我们只剩下 {v2, v3} 作为同一个键的冲突值。我删除 v1 的原因是为了说明，通过使用版本矢量（Version Vectors）等工具，可以安全地删除值的版本，从而最大限度地减少冲突。要了解有关版本矢量及其实现的更多信息，我推荐阅读《点状版本矢量》。

我们也可以简单地让应用程序决定如何处理冲突，返回所请求项目的所有冲突值。应用程序可能比数据库更了解数据，为什么不让它来解决冲突呢？例如，Riak KV 就是这样做的。

我经常考虑的一个想法是，甚至可以允许用户将冲突解决逻辑编译成 WASM 模块，并将其上传到数据库，这样当冲突发生时，数据库就会解决冲突，而不再依赖应用程序。

在一个最终一致的系统中，有许多不同的想法可以减少冲突，它们通常都属于反熵的范畴。

反熵
下面举例说明一些最流行的反熵机制：

读取修复 - 客户端（通过冲突解决）从多个节点的读取请求中选择 "最新 "值后，会将该值发回当前未存储该值的所有节点，从而修复这些节点。

Hinted Handoff - 当一个写入请求无法到达其中一个目标节点时，将其作为 "提示 "发送到其他节点。一旦该目标节点再次可用，就将保存的 "提示 "发送给它。在法定人数写入中，这种机制也被称为 "Sloppy Quorum"，它能为法定人数请求提供更好的可用性。

梅克尔Merkle树 - 由于读修复只能修复查询到的数据，因此很多数据在很长时间内仍可能不一致。节点可以选择通过相互对话启动同步过程，并查看数据差异。当数据量很大时，这样做的成本非常高（O(n)）。为了让同步算法更快（O(log n)），我们可以引入梅克尔树。梅克尔树将数据范围的哈希值存储在最低的叶节点中，父叶节点是其子叶节点 2 个哈希值的组合，这样就形成了一个直到树根的哈希值层次结构。同步过程开始时，一个节点将梅克尔树的根节点与另一个节点的梅克尔树进行比较，如果哈希值相同，则表示它们拥有完全相同的数据。如果哈希值不同，则会以同样的方式检查叶子哈希值，直到找到不一致的数据为止。

Gossip 传播 - 通过模仿人类传播流言或疾病的方式，以简单可靠的方式向集群中的所有节点发送广播事件。您可以将事件消息发送到指定数量的随机选择的节点（称为 "扇出"），当这些节点收到消息后，它们会重复这一过程，并将消息发送到另一组随机选择的 N 个节点。为了避免在集群中永远重复消息，节点在看到一定数量的流言消息后就会停止广播。要了解数据是如何通过Gossip 收敛的，请访问模拟器！作为一种优化，Gossip 信息通常使用 UDP 发送，因为这种机制非常可靠。

结论
关于数据库的话题还有很多，比如在 linux 中使用 O_DIRECT、实现自己的页面缓存、分布式系统中的故障检测、共识算法（如 raft）、分布式事务、领导者选举等等，几乎无穷无尽。

希望我的介绍能激起你的好奇心，让你进一步探索数据库的世界，或者为你提供一些工具，让你更好地了解在下一个项目中选择哪种数据库。