设计数据密集型

存储和检索

OLTP 索引

一个简单的思想就是使用一张哈希表来保存每个数据的 offset，但是这样存在着更新困难的问题：

• 如果不更新已经删除的 key，那么就会持续占用磁盘
• 如果更新已经删除的 key，那么就会占用大量时间重新扫描文件系统，来重新构建哈希表

此外，还需要占用额外的空间来保存这张哈希表，否则如果掉电等意外发生，那么也必须扫描整个文件系统来重新构建这张哈希表。同时，这样不会能支持范围检索，如果数据量过大，还必须解决哈希冲突。

SSTable（sorted string table）

The Google SSTable file format is used internally to store Bigtable data. An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings. Operations are provided to look up the value associated with a specified key, and to iterate over all key/value pairs in a specified key range. Internally, each SSTable contains a sequence of blocks (typically each block is 64KB in size, but this is configurable). A block index (stored at the end of the SSTable) is used to locate blocks; the index is loaded into memory when the SSTable is opened. A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk. Optionally, an SSTable can be completely mapped into memory, which allows us to perform lookups and scans without touching disk.

SSTable 是 Bigtable 内部用于数据的文件格式，它的格式为文件本身就是一个排序的、不可变的、持久的 Key/Value 对 Map，其中 Key 和 value 都可以是任意的 byte 字符串。使用 Key 来查找 Value，或通过给定Key范围遍历所有的Key/Value对。每个SSTable包含一系列的Block（一般Block大小为64KB，但是它是可配置的），在SSTable的末尾是Block索引，用于定位Block，这些索引在SSTable打开时被加载到内存中，在查找时首先从内存中的索引二分查找找到Block，然后一次磁盘寻道即可读取到相应的Block。还有一种方案是将这个SSTable加载到内存中，从而在查找和扫描中不需要读取磁盘。

• data block: 用来存储key value数据对；
• filter block: 用来存储一些过滤器相关的数据（布隆过滤器）
• meta Index block: 用来存储filter block的索引信息（索引信息指在该sstable文件中的偏移量以及数据长度）；
• index block：index block中用来存储每个data block的索引信息；
• footer: 用来存储meta index block及index block的索引信息；

如果数据量特别多，会导致读取旧数据特别慢，因此可以借助布隆过滤器进行快速判断。布隆过滤器本质上通过多个哈希函数对元素进行哈希，将元素映射到一个位图（bit array）的多个位置。如果所有相关位置的位都被标记为 1，那么可以认为该元素可能存在于数据库中。如果有任意一个位置的位为 0，则可以确定该元素不在数据库中。但是布隆过滤器可能会存在误报的情况

构建

由于 SSTable 是有序且不变的，如果每次插入一次数据都要在磁盘中进行一次昂贵的排序，因此可以通过日志结构的方法解决这个问题，整个流程比较简单：

首先写入数据到内存中，在内存通过有序数据结构（红黑树，跳表，字典树），当达到某个阈值就会写到磁盘中。需要注意的是，此时是通过追加的方式进行写入，而不是覆盖原有数据。

这里有一个 memtable 的概念，本质就是一个内存表

读取

首先在内存表和最新的磁盘段中，如果没有，则往旧的一段寻找，直到全部找完。

为什么会出旧的一段，因为 SSTable 是不变的，新的数据不会该改变原来的段，只会进行追加。因此旧的数据段中也可能包含有效数据。

合并

另外考虑一个问题，sstable 中内存中的数据块为 [1, 3, 5, 7, 9]，磁盘中的数据块为 [2, 4, 6, 8, 10]。现在，将内存中的数据块写入到磁盘，这样是怎样保证有序的。

合并段的方法是类似为归并排序：后台并排开始读取输入文件，查看每个文件中的第一个键，将最低的键（根据排序顺序）复制到输出文件，然后重复。如果同一个键出现在多个输入文件中，只保留较新的值。这会产生一个新的合并段文件，也按键排序，每个键只有一个值，并且它使用最少的内存，因为我们可以一次遍历一个键的 SSTable。

每次合并操作会根据合并后的数据更新索引块，确保查询时能够通过新的索引块快速定位数据的位置。旧的索引块会被清除。

压实

除了合并之后，还有一个概念和操作与之类似。压实是对 sstable 文件进一步的操作，会对数据库进行进一步的优化。包括去重和删除过时数据，减少碎片，用来提升索引效率。主要包括以下两种策略：

1. 分层压实（Size-tiered compaction）：较新和较小的 SSTable 依次合并到较旧和较大的 SSTable 中。包含较旧数据的 SSTable 可能变得非常大，合并它们需要大量的临时磁盘空间。这种策略的优点是它可以处理非常高的写入吞吐量。
2. 分级压实（Leveled compaction）：键范围被分成较小的 SSTable，较旧的数据被移动到单独的”级别”中，这允许压实更增量地进行，并且比分层策略使用更少的磁盘空间。这种策略对于读取比分层压实更有效，因为存储引擎需要读取更少的 SSTable 来检查它们是否包含该键。

删除一个键值的时候会往数据文件中追加一个特殊标注 tombstone，合并时会自动删除这个键值。

日志

为了确保数据库崩溃时内存表中的数据不会丢失，存储引擎在磁盘上保留一个单独的日志，每次写入都会立即追加到该日志中。此日志不按键排序，但这无关紧要，因为它的唯一目的是在崩溃后恢复内存表。每次内存表被写出到 SSTable 后，日志的相应部分就可以丢弃。

该算法最初于 1996 年以 日志结构合并树（Log-Structured Merge-Tree）或 LSM 树（LSM-Tree）10 的名称发布，建立在早期日志结构文件系统工作的基础上 11。因此，基于合并和压实排序文件原理的存储引擎通常被称为 LSM 存储引擎。

在 LSM 存储引擎中，段文件是一次性写入的（通过写出内存表或合并一些现有段），此后它是不可变的。段的合并和压实可以在后台线程中完成，当它进行时，我们仍然可以使用旧的段文件继续提供读取服务。当合并过程完成时，我们将读取请求切换到使用新的合并段而不是旧段，然后可以删除旧的段文件。

参考部分

1. https://leveldb-handbook.readthedocs.io/zh/latest/sstable.html
2. https://ddia.vonng.com/ch4/

B 树 / B+ 树

其他内容可以看文章

B 树 vs LSM

LSM 树主要适用为写入型应用，B 树读取较快更适合读取，当然可以混合这两种方式，取其优势。

读取性能

• 正常查询：在 B 树中，由于 B 树层级很小，因此读取效率非常高。LSM 可以借助布隆过滤器减少实际磁盘 IO 操作数，因此操作效率都非常高。（使用布隆过滤器后，查询某个键时，首先会通过布隆过滤器检查它是否存在于某个 SSTable 文件 中。如果布隆过滤器表明该键不在文件中，系统就跳过该文件，避免进行磁盘 I/O 操作。这样，不必要的磁盘读取操作 得以减少。）
• 范围查询: 范围查询在 B 树上简单而快速，因为它们可以使用树的排序结构。在 LSM 存储上，范围查询也可以利用 SSTable 排序，但它们需要并行扫描所有段并组合结果。布隆过滤器对范围查询没有帮助（因为你需要计算范围内每个可能键的哈希，这是不切实际的），使得范围查询在 LSM 方法中比点查询更昂贵。

写入性能

B 树主要是随机写入，LSM 主要是顺序写入。相比较而言，LSM 效率较高。

B 树可能会随着时间的推移变得 碎片化：例如，如果删除了大量键，数据库文件可能包含许多 B 树不再使用的页。对 B 树的后续添加可以使用这些空闲页，但它们不能轻易地返回给操作系统，因为它们在文件的中间，所以它们仍然占用文件系统上的空间。

碎片化在 LSM 树中不太成问题，因为压实过程无论如何都会定期重写数据文件，而且 SSTable 没有未使用空间的页。此外，SSTable 中的键值对块可以更好地压缩，因此通常比 B 树在磁盘上产生更小的文件。被覆盖的键和值继续消耗空间，直到它们被压实删除，但使用分级压实时，这种开销相当低。分层压实（参见 “压实策略”）使用更多的磁盘空间，特别是在压实期间临时使用。

写放大

• LSM 树：通常具有较低的写放大，因为它避免了写入整个页，并且可以通过压缩减少写入的总量。较低的写放大有助于延缓 SSD 的磨损，适用于写入密集型的工作负载。
• B 树：写放大较高，因为每次写入可能涉及到整个页的写入，尤其是在进行修改时。较高的写放大会导致更快的 SSD 磨损。

多列索引和二级索引

• 聚簇索引：实际数据（行、文档、顶点）直接存储在索引结构中。
• 覆盖索引：在索引中存储表的 某些 列，除了在堆上或主键聚簇索引中存储完整行。

OLAP 索引（TODO）

暂时省略。。。。

分布式系统

复制

出于性能和可靠性考虑，我们通常希望在多台机器上保留数据的副本。当数据足够小且可以存储在单台机器上时，直接存储即可；如果数据量过大，我们则需要采用**分片（Sharding）**技术，将数据分割成多个部分存储在不同的机器上。同时，数据副本（Replication）用于保证数据的高可用性和容错性。

数据复制有几种常见的模式：单主（Master-Slave）复制、多主（Master-Master）复制和无主（Peer-to-Peer）复制。在单主模式下，只有一个主节点接受写操作，其他节点为从节点；而多主模式允许多个主节点进行写操作，数据在主节点之间同步；无主模式中，所有节点是对等的，每个节点都能进行读写操作。
由于数据会随着时间变化，我们需要保证多个副本之间的数据同步。在此过程中，必须考虑数据一致性、性能和容错能力之间的权衡。例如，同步复制可以保证一致性，但会降低性能；而异步复制提高性能，但可能会导致副本之间的数据延迟。

在分布式系统中，还需要考虑失败回滚、事务等机制来保证系统的稳定性和一致性。比如，当主节点发生故障时，是否能够自动切换到备用节点并保证事务不会丢失。同时，系统的设计还需要兼顾CAP 定理中的一致性、可用性和分区容忍性，确保在极端情况下的正确性和可用性。

单主复制

在一个多副本的集群中，会选出一个领导者出来（或者称为 主库/源），接受所有的写入和部分读取操作。其余的称为追随者（只读副本，从库，热备），只接受读取操作和来自领导者的指令。下图是单主复制将所有写入定向到指定的领导者，该领导者向追随者发送变更流。

同步复制和异步复制

如果是异步复制，如果恰巧在领导者指令更新之前，客户端读取从库的数据，那么就会读到过期数据。但是，如果是同步复制，如果存在分区或者高网络延迟，那么就会狠狠拉低整个系统的性能。

因此绝大部分的系统都是异步复制，为了保证数据的一致性，一般不会等到所有的跟随者都返回 ack，而是达到大多数就会判断成功，然后执行下一步操作。当然，如果数据刚到领导者，领导之就因为某种原因故障并且客户端没有重试，那么就会导致数据丢失。

一般来说系统都是奇数，并且个数 >= 3，所以大多数为 2

如果当新的机器或者消息十分落后的机器重新上线，领导者会发送类似快照的数据过来，帮助过时的机器快速同步消息。较为落后的机器可以接受来自领导者的指令来进行同步。

追赶恢复

因为各种原因，如网络延迟，或者网络中断等其他原因导致追随者与领导者的连接中断，追赶者可以根据领导者的日志快速恢复数据。

但是，领导者的日志并不能无限的增长，需要某种方式进行压缩，比如生成快照，或者进行日志压缩。如果此时追随者落后太多，内存中的日志已经不能满足了，那么就可以直接发送快照过来进行快速恢复。

故障转移

如果领导者发生故障，那么需要选举出一个新的领导者来接管这个集群，完成数据的消费，这个过程为领导者选举或者故障转移。

故障转移可以通过手动配置：

1. 确定领导者已失效。 可能会出现许多问题：崩溃、停电、网络故障等。没有万无一失的方法能准确判断发生了什么，所以大多数系统只是依赖超时：节点之间会频繁来回发送消息，如果某个节点在一段时间内（例如 30 秒）没有响应，就认为它已经失效。（如果是计划维护而主动下线领导者，则不适用。）
2. 选择新的领导者。 这可以通过选举过程完成（由剩余副本中的多数选出领导者），也可以由预先设定的控制器节点任命。最适合担任领导者的通常是那个拥有旧领导者最新数据变更的副本（以尽量减少数据丢失）。让所有节点就新领导者达成一致是一个共识问题，我们会在 第 10 章 详细讨论。
3. 将系统重新配置为使用新的领导者。 客户端现在需要把写请求发送到新领导者。如果旧领导者恢复，它可能仍然以为自己是领导者，并不知道其他副本已经让它下台。系统需要确保旧领导者降级为追随者，并识别新的领导者。

但是领导者选择并不是轻松的，容易出现数据不一致的情况，甚至可能出现脑裂的情况（这是不可以被接受的）。

复制日志

复制日志有以下几种方法：

• 基于语句的复制：以 sql 为例子，领导者会讲每个 sql 语句转发给追随者，追随者将解析并且执行。
  • 非确定语句，如 random，now 不可用，但是可以通过确定值来满足。
  • 自增列如果依赖现有数据，这是不可取的。
  • 具有副作用的语句（例如，触发器、存储过程、用户定义的函数）可能会导致每个副本上发生不同的副作用，除非副作用是绝对确定的。
• 预写日志（WAL）传输：每个修改首先写入 WAL，以便在崩溃后可以将树恢复到一致状态。由于 WAL 包含将索引和堆恢复到一致状态所需的所有信息，我们可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘外，领导者还通过网络将其发送给其追随者。当追随者处理此日志时，它构建了与领导者上找到的完全相同的文件副本。
• 逻辑（基于行）日志复制：具体内容为
  • 对于插入的行，日志包含所有列的新值。
  • 对于删除的行，日志包含足够的信息来唯一标识被删除的行。通常这将是主键，但如果表上没有主键，则需要记录所有列的旧值。
  • 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

复制延迟问题

在这种 读扩展 架构中，你可以通过添加更多追随者来简单地增加服务只读请求的容量。然而，这种方法只有在使用异步复制时才现实可行——如果你试图同步复制到所有追随者，单个节点故障或网络中断将使整个系统无法写入。而且你拥有的节点越多，其中一个节点宕机的可能性就越大，因此完全同步的配置将非常不可靠。

不幸的是，如果应用程序从 异步 追随者读取，如果追随者已落后，它可能会看到过时的信息。这导致数据库中出现明显的不一致：如果你同时在领导者和追随者上运行相同的查询，你可能会得到不同的结果，因为并非所有写入都已反映在追随者中。这种不一致只是一种临时状态——如果你停止向数据库写入并等待一段时间，追随者最终将赶上并与领导者保持一致。因此，这种效果被称为 最终一致性。

写后读一致性

如果用户提交了数据，那么正常状态时写后就能立即看到提交的数据，但是按照复制延迟问题，那么很有可能出现写后读取不一致的问题。

比如在这张图里面，用户写入一组数据给 leader，然后读取数据。由于网络延迟的原因，写入消息还没有到达 follower2，但是此时查询的请求到达了，导致读取不到写入之后的数据。

因此，此时需要写后读一致性，保证用户在写入数据之后可以正确的读取到数据。具体操作的话有以下几种：

• 当读取用户可能已修改的内容时，从领导者或同步更新的追随者读取；否则，从异步更新的追随者读取。
• 当应用程序大多数东西都可以被用户编辑，那么很多都会通过领导者进行，那么多个机器就没有意义。
  • 可以通过跟踪上次更新的时间，使其更新一分钟之后都从领导者读取。
  • 监控追随者上的复制延迟，并防止在落后领导者超过一分钟的任何追随者上进行查询。
• 客户端记住最近写入的时间戳，从机器上读取的信息必须比这个时间戳新，否则则会换一台服务器读取。

如果需要支持多设备登陆，那么就需要将元数据集中化处理；如果存在多个集群，使用不同网络，可能路由到不同地区（云服务提供商通常会在同一地区部署多个数据中心）。

单调读

我们需要保证数据是在时间上是单调的。

当不同的 follower 数据不一致的时候，首先读取到拥有最新数据 follower，然后在读到有落后的数据的 follower，就仿佛出现了时间倒退的假象。

实现单调读的方法是确保每个用户始终从同一个副本进行读取，不同的用户可以从不同的副本读取。然而，如果读取副本失败，那么需要重新将查询分配到另一个副本。

一致前缀读

这是分片（分区）数据库的问题，如果某些分片的复制比其他分片慢，观察者可能会在看到问题之前看到答案。

一种解决方案是确保任何因果相关的写入都写入同一分片——但在某些应用程序中，这无法有效完成。

多主复制

单主复制有一个主要缺点：所有写入都必须通过一个领导者。如果由于任何原因无法连接到领导者，例如你和领导者之间的网络中断，你就无法写入数据库。

异步复制/同步复制

假设你有两个领导者，A 和 B，你正在尝试写入 A。如果写入从 A 同步复制到 B，并且两个节点之间的网络中断，你就无法写入 A 直到网络恢复。同步多主复制因此给你一个非常类似于单主复制的模型，即如果你让 B 成为领导者，A 只是将任何写入请求转发给 B 执行。

多主复制拓扑

多主复制的三个示例拓扑如下图：

• Circular topology:每个节点从一个节点接收写入并将这些写入（加上其自己的任何写入）转发到另一个节点。
• Star topology:一个指定的根节点将写入转发到所有其他节点。
• All-to-all topology:其中每个领导者将其写入发送到每个其他领导者。

在环形和星形拓扑中，写入可能需要通过几个节点才能到达所有副本。因此，节点需要转发它们从其他节点接收的数据变更。为了防止无限复制循环，每个节点都被赋予一个唯一标识符，并且在复制日志中，每个写入都用它经过的所有节点的标识符标记。当节点接收到用其自己的标识符标记的数据变更时，该数据变更将被忽略，因为节点知道它已经被处理过了。

并且如果某个关键节点发生故障，可能会中断其他节点的复制消息流，导致无法通信。如果某个节点发生如网络阻塞的情况，可能会导致消息提前达到其他节点，比如消息顺序为 1，2，3 到达数据顺序为 3，1，2。如果存在有因果关系，比如说 2 必须在 1 的基础上。

sequenceDiagram
leader -->> leader: val = 0
leader -->> follower1: msg1: insert into val += 10
leader -->> follower2: msg2: insert into val -= 10
leader -->> follower2: msg1: insert into val += 10
leader -->> follower1: msg2: insert into val -= 10

这时候对于 follower 1 是正确的，对于 follower2 是错误的。

同步引擎和本地优先软件 / 实时协作、离线优先和本地优先应用（TODO）

• 同步引擎：同步引擎是一个软件库或机制，允许多个设备之间同步数据。它通过将本地副本和远程服务器之间的数据传输移至后台来工作。当设备离线时，它会记录用户的更改，并在设备重新连接网络时将这些更改同步到其他设备或服务器。
  • 日历应用程序：离线可以继续操作，联网可以接着同步所有消息。
  • 优点：
    • 本地拥有数据可以加快渲染，提升响应速度。
    • 允许用户在离线时继续工作，离线可以当作超长延迟的情况。
    • 与在应用程序代码中执行显式服务调用相比，同步引擎简化了前端应用程序的编程模型。（例如，如果更新服务器上的数据的请求失败，用户界面需要以某种方式反映该错误。同步引擎允许应用程序对本地数据执行读写，这几乎从不失败，导致更具声明性的编程风格）
    • 同步引擎和响应式编程结合，可以加快实时响应。
  • 缺点：
    • 不适用于数据量大的应用场景，因为同步引擎需要将数据保存到本地。
• 本地优先软件：本地优先软件是指即使所有在线服务都关闭，软件依然可以继续工作。
  • Git：Git 是一个分布式版本控制系统，你可以在本地创建、提交、查看和管理代码（即使没有网络连接）。当网络恢复时，你可以将本地更改推送到远程仓库，其他开发者也可以从远程仓库拉取更新。Git 不依赖实时的服务器响应，因此被称为“本地优先软件”。
• 实时协作：实时协作应用允许多人同时编辑同一文档或图形，并实时查看其他人的更改。这些应用通常会使用同步引擎来确保数据在多个设备之间实时同步，即便设备不总是在线。
  • Google Dos
  • 在线文档
  • Figma

多主复制方案

• 处理写入冲突：不同的领导者并发写入可能会导致写入冲突
  • 冲突避免：避免多个领导者分别写入同一个客户端的消息，确保同一个用户写入只能由一个领导者管理。
  • 最后写入胜利（丢弃并发写入）：永远使用最新的数据，丢弃过时的数据，确保数据是一致的。
  • 手动冲突解决：通过类似 Git 的版本管理方式，手动解决冲突。
  • 自动冲突解决：自处将并发写入合并为一致状态，确保所有副本数据收敛到一致的状态。
    • 无冲突复制数据类型（CRDT）:大多数 CRDT 为每个字符提供唯一的、不可变的 ID，并使用这些 ID 来确定插入/删除的位置，而不是索引。例如，在 图 6-11 中，我们将 ID 1A 分配给”i”，ID 2A 分配给”c”等。插入感叹号时，我们生成一个包含新字符的 ID（4B）和我们想要在其后插入的现有字符的 ID（3A）的操作。要在字符串的开头插入，我们将”nil”作为前面的字符 ID。在同一位置的并发插入按字符的 ID 排序。这确保副本收敛而不执行任何转换。
    • 操作变换（OT）:我们记录插入或删除字符的索引：“n”插入在索引 0，”!“插入在索引 3。接下来，副本交换它们的操作。在 0 处插入”n”可以按原样应用，但如果在 3 处插入”!“应用于状态”nice”，我们将得到”nic!e”，这是不正确的。因此，我们需要转换每个操作的索引以考虑已经应用的并发操作；在这种情况下，”!“的插入被转换为索引 4 以考虑在较早索引处插入”n”。

无主复制

在亚马逊于 2007 年将其用于其内部 Dynamo 系统后，它再次成为数据库的时尚架构。Riak、Cassandra 和 ScyllaDB 是受 Dynamo 启发的具有无主复制模型的开源数据存储，因此这种数据库也被称为 Dynamo 风格。

无主复制保证数据一致的方法是读写都是发送多个请求：

• 写入：例如现在有3个服务器，现在同时像所有服务器发送请求，当收到2个请求就直接返回 ok
• 读取：读取多个节点，返回最新值。需要时间戳和版本号来进行区分。

但是怎么实现数据一致性呢？
- 读修复：一次性读取多个副本的值，然后获取最新的值，并且将最新的值写到陈旧值副本。
- 提示移交：如果一个副本不可用，另一个副本可能会以 提示 的形式代表其存储写入。当应该接收这些写入的副本恢复时，存储提示的副本将它们发送到恢复的副本，然后删除提示。
- 反熵：一个后台进程定期查找副本之间数据的差异，并将任何缺失的数据从一个副本复制到另一个。与基于领导者的复制中的复制日志不同，这个 反熵进程 不以任何特定顺序复制写入，并且在复制数据之前可能会有显著的延迟。

读写仲裁

一般地说，如果有 n 个副本，每次写入必须由 w 个节点确认才能被认为成功，并且我们必须为每次读取查询至少 r 个节点。（在我们的例子中，n = 3，w = 2，r = 2。）只要 w + r > n，我们在读取时期望获得最新值，因为我们读取的 r 个节点中至少有一个必须是最新的。遵守这些 r 和 w 值的读取和写入称为 仲裁 读取和写入 50。你可以将 r 和 w 视为读取或写入有效所需的最小投票数。

在 Dynamo 风格的数据库中，参数 n、w 和 r 通常是可配置的。常见的选择是使 n 为奇数（通常为 3 或 5），并设置 w = r = (n + 1) / 2（向上舍入）。然而，你可以根据需要更改数字。例如，写入很少而读取很多的工作负载可能受益于设置 w = n 和 r = 1。这使读取更快，但缺点是仅一个失败的节点就会导致所有数据库写入失败。

存在边缘情况：

• 携带新值的节点失败，数据从旧值副本恢复，导致还没达到仲裁条件就已经失败
• rebalance （分片部分）过程中，可能 shard 还没有完全迁移，导致旧副本和新副本处于中间状态，从而破坏数据一致性
• 取和写入并发情况，导致数据不一致。

sequenceDiagram
    Actor U as User
    participant N as Network
    participant R1 as Replica1
    participant R2 as Replica2
    participant R3 as Replica3

    U ->> N: Set Replica1/2/3 val = 100
    U ->> N: Get Replica1/2/3 val

    U ->> R1: Get val
    R1 -->> U: val = 50
    U ->> R2: Get val
    R2 -->> U: val = 50

    Par  "Network latency"
        N ->> R1: Set R1 val = 100
        N ->> R2: Set R2 val = 100
        N ->> R3: Set R3 val = 100
    end

    U ->> R3: Get val = 100
    R3 -->> U: val = 100

分片

分片的具体含义是将数据进行切割，然后放置到不同的物理机上。切割之后的块叫做分片（shards）或者称为分区（partitions）。分片是对系统进行水平拓展的主要方式之一，将数据分散到多个节点上，并且能提高系统整体的吞吐量，但是相对而言，借助分片会提高系统整体的复杂度。并且，分片适合于键值存储，如果不了解分区见的位置，需要依次访问所有机器，拉低系统效率。并且，执行事务操作需要引入分布式事务。

根据一种理论，该术语源于在线角色扮演游戏《网络创世纪》（Ultima Online），其中一块魔法水晶被打碎成碎片，每个碎片都折射出游戏世界的副本 3。分片 一词因此用来指一组并行游戏服务器中的一个，后来被引入数据库。另一种理论是 分片 最初是 高可用复制数据系统（System for Highly Available Replicated Data）的缩写——据说是 1980 年代的一个数据库，其细节已经失传。

分片划分

如果分片划分不均匀，会出现倾斜的现象，比如所有热数据都放在一台机器上，那么海量请求就有可能压垮这台机器，因此怎么对数据进行划分非常重要。

按键的范围进行划分

按键范围分片是指为每个分片分配连续的分区键范围。分片内部通常基于 B 树、SSTable 等有序结构存储数据，因此能够高效支持范围查询。但由于键分布可能不均匀，容易产生数据倾斜与热分片问题，从而导致部分节点负载过高。

1. 哈希取模节点数：hash(key) % N, N 为节点数。但是如果节点数发生变化，需要移动大量数据。
2. 固定数量的分片：hash(key) % N, N 为固定数。但是如何选择 N 的取值就是一个很难的问题，如果过大调度和查询就会变的复杂，过小数据过于集中。
3. 哈希范围分片：hash(key)，将哈希值映射到一个连续的哈希空间（如 0∼2^32−1），再将该空间划分为多个连续区间，每个区间对应一个分片节点。hash 不均匀会导致数据倾斜。
4. 一致性哈希算法：是一种将数据和节点映射到同一哈希空间的分片方法，使得在节点增减时只需迁移少量数据，从而实现高扩展性的分布式存储机制。

请求路由

主要是以下几种方法：

1. 允许客户端连接任何节点（例如，通过循环负载均衡器）。如果该节点恰好拥有请求适用的分片，它可以直接处理请求；否则，它将请求转发到适当的节点，接收回复，并将回复传递给客户端。（无状态）
2. 首先将客户端的所有请求发送到路由层，该层确定应该处理每个请求的节点并相应地转发它。这个路由层本身不处理任何请求；它只充当分片感知的负载均衡器。（有状态，zookeeper，etcd内有机制检测节点状态变化）
3. 要求客户端知道分片和分片到节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而无需任何中介。（客户端有状态）

二级索引（TODO）

储存的方式主要有两种：

1. 本地二级索引：其中二级索引与主键和值存储在同一个分片中。这意味着写入时只需要更新一个分片，但二级索引的查找需要从所有分片读取。
2. 全局二级索引：它们基于索引值单独分片。二级索引中的条目可能引用来自主键所有分片的记录。写入记录时，可能需要更新多个二级索引分片；但读取倒排列表时，可以由单个分片提供（获取实际记录仍需从多个分片读取）。

事务

ACID

1. 原子性：操作为原子化的，要么全部成功，要么全部失败
2. 一致性：事务前后，数据必须满足约束
3. 隔离性：事务操作之间会不干扰
4. 持久性：一旦事务成功提交，它写入的任何数据都不会被遗忘

数据库隔离级别

1. 读未提交：脏读，幻读，不可重复读
2. 读已提交：幻读，不可重复读
3. 可重复读：幻读
4. 可串行化

读已提交和可重复读都是通过 MVCC 实现的，通过快照读机制实现，只是快照创建时机不同。

丢失更新

如果应用程序从数据库读取某个值，修改它，然后写回修改后的值（读-修改-写循环），就会出现丢失更新问题。如果两个事务并发执行此操作，其中一个修改可能会丢失，因为第二个写入不包括第一个修改。（我们有时说后面的写入覆盖了前面的写入。）这种模式出现在各种不同的场景中：

• 递增计数器或更新账户余额（需要读取当前值，计算新值，并写回更新的值）
• 对复杂值进行本地更改，例如，向 JSON 文档中的列表添加元素（需要解析文档，进行更改，并写回修改后的文档）
• 两个用户同时编辑 wiki 页面，每个用户通过将整个页面内容发送到服务器来保存他们的更改，覆盖数据库中当前的任何内容

1. 原子操作
2. 显式加锁操作
3. 自动检测更新：如果事务管理器检测到丢失的更新，则中止事务并强制它重试其读-修改-写循环。
4. 条件写入（CAS）/ 乐观锁

可串行化

实施串行化的条件这本书列出了下面四条：

• 每个事务必须小而快，因为只需要一个缓慢的事务就可以阻止所有事务处理。
• 它最适合活动数据集可以适合内存的情况。很少访问的数据可能会移到磁盘，但如果需要在单线程事务中访问，系统会变得非常慢。
• 写入吞吐量必须足够低，可以在单个 CPU 核心上处理，否则事务需要分片而不需要跨分片协调。
• 跨分片事务是可能的，但它们的吞吐量很难扩展。

2PL 锁定

我对此的一个简单理解就是，只能存在同一类锁：

• 当只有写锁的时候就不能有读锁
• 只有读锁的时候就不能有写锁
• 两类锁进行切换的时候必须等待之前一类锁全部完成对应任务之后才能切换

显然，这种锁的效率肯定不会太高。因为存在互相等待的机制，如果一个锁存在有长尾效率，势必会阻塞整个流程。

谓词锁

这个锁对此的理解就是锁定的某个数据集合（逻辑条件）。

update table_name set amount=0
    where amount < 0

如果对此上谓词锁，那么就会锁定 amount < 0 这个范围，每次查询或者插入的的时候都会进行判断。

但是，如果说这个条件的效率非常低，比如什么模糊搜索之类的，那么会极大的拉低效率。

间隙锁

间隙锁还有个比较好理解的名称叫做 索引范围锁，也就是说，这是锁定某个范围之内的锁。

以书中的例子为例，在预定系统中，你可以锁定下午两点 - 下午五点某些房间，防止由于其他事务导致出现一个房间被两个不同的用户预定。

这提供了对幻读和写偏差的有效保护。索引范围锁不如谓词锁精确（它们可能锁定比严格维护可串行化所需的更大范围的对象），但由于它们的开销要低得多，它们是一个很好的折衷。

小结

我很在意为什么谓词锁和间隙锁都是放在 2PL 阶段之下。

这部分内容主要是在防止幻读，也就是一个事务改变另一个事务的搜索查询结果。 2PL 相当于制定了一个规则：

所有锁必须先加完，再统一释放，用阶段性规则保证事务可串行化。

上述两个锁都是按照这个方法实现。

可串行化隔离（SSI）

可串行化快照隔离（SSI）的算法提供完全可串行化，与快照隔离相比只有很小的性能损失。

悲观并发控制与乐观并发控制

悲观并发控制：如果任何事情可能出错（如另一个事务持有的锁所示），最好等到情况再次安全后再做任何事情。它就像互斥，用于保护多线程编程中的数据结构。

串行执行在某种意义上是悲观到极端：它本质上相当于每个事务在事务期间对整个数据库（或数据库的一个分片）具有独占锁。我们通过使每个事务执行得非常快来补偿悲观主义，因此它只需要短时间持有”锁”。

乐观并发控制技术:当事务想要提交时，数据库会检查是否发生了任何不好的事情（即，是否违反了隔离）；如果是，事务将被中止并必须重试。只允许可串行执行的事务提交。如果存在高争用（许多事务尝试访问相同的对象），它的性能很差，因为这会导致大部分事务需要中止。如果系统已经接近其最大吞吐量，重试事务的额外事务负载可能会使性能变差。

陈旧值

• 基于过时前提的决策：写偏差中出现错误的原因 事务从数据库读取一些数据，检查查询结果，并根据它看到的结果决定采取某些行动（写入数据库）。那么是否有什么办法可以防止这种情况？
  • 检测陈旧的 MVCC 对象版本的读取（未提交的写入发生在读取之前）
  • 检测影响先前读取的写入（写入发生在读取之后），这句话简单一点就是别的事务影响到你的数据了。

分布式问题

1. 网络故障：
   • 物理故障（网线被断、网络接口异常）
   • 超时
   • 网络拥塞
   • 网络分区
2. 时钟不可靠：仅仅依靠本地时钟可能会出现逻辑错误、时间回退，或者时间不准确
3. 进程暂停
   • 比如有多个虚拟设备需要共享 CPU 那么就会出现进程被挂起
   • GC 的时候可能将所有的进程挂起
4. 死锁：多个机器可能会互相等待资源，比如 2PC 中协调器在 commit point 之后挂了就会触发死锁
5. 请求乱序：由于网络延迟、网络阻塞或重试机制等原因，先发出的请求可能后到达服务端并覆盖后发请求的结果，导致最终状态与用户操作顺序不一致。
6. 拜占庭问题：数据中存在有错误的信息，如果要防止拜占庭错误，需要保证 2/3 的机器是正确的。

一致性共识算法

线形一致性

1. 线性一致性（原子一致性）：基本思想是让系统看起来好像只有一份数据副本，并且对它的所有操作都是原子的。
2. 最终一致性：不管过程如何，只要结果保持一致即可，比如前文阐述的 LLW（最后写入策略）
3. 强一致性：每一个过程都要保持一致

下图可以很好的理解什么是线形一致性，勾起了我对 6.824 lab 的噩梦

其中 read(x) => 4 之后出现 read(x) => 2，就违背了线形一致性，不满足操作原子化的操作。

线性一致性和可串行化：可串行化是事务的隔离属性，要求操作都是按照某种顺序串行执行，保证的事务整体操作；线性一致性是对寄存器（单个对象的读写保证），保证的是“单个操作”的原子性。

相关应用场景：

• 锁定和领导者选举：防止两个节点同时获取租约，或者同时成为 leader
• 约束和唯一性保证：书中举例唯一的用户 id 或者 email，需要保证线性一致性
• 跨通道时序依赖：视频首先要先放到文件存储中，然后再发送到消息代理执行转码指令

要保证线形一致性非常困难，比如之前的几种复制方法：

• 可能线形一致性
  • 单主复制：如果只在主节点上进行读写操作，并且同步到足够的机器上之后，可以保证线形一致性。如果采用异步复制，则故障切换是可能丢失已经准备 commit 的数据，从而破坏线形一致性。如果出现脑裂也会破坏线性一致性。
  • 共识算法：etcd 的 raft 和 zookeeper 的 zab 算法通过一系列方法可以保证写入的线形一致性，但是不能保证整体系统的线形一致性。比如说，读到落后的 follower。
  • 无主复制：保证读写仲裁的情况下，读写操作无法保证全局一致性，因为没有机制能够保证所有机器保证全局顺序。
• 无法保证线形一致性：
  • 多主复制：可以有多个 leader 写入。

要实现线形一致性非常困难，根据 CAP （C 一致性，A 可用性，P 网络分区）理论 CP 和 AP 是不可以兼得的，因此如果实现 CP 系统，那么就会造成非常高的延迟。

ID 生成器和逻辑时钟

• ID 生成：
  • 分片 ID 分配：例如，一个只生成偶数，一个只生成奇数。一般来说，你可以在 ID 中保留一些位来包含分片编号。这些 ID 仍然紧凑，但你失去了排序属性。
  • 预分配 ID 块：节点 A 可能声明从 1 到 1,000 的 ID 块，节点 B 可能声明从 1,001 到 2,000 的块。然后每个节点可以独立地从其块中分发 ID，并在其序列号供应开始不足时从单节点 ID 生成器请求新块。
  • 随机 UUID：你可以使用 通用唯一标识符（UUID），也称为 全局唯一标识符（GUID）。它们的一大优点是可以在任何节点上本地生成，无需通信，但它们需要更多空间（128 位）。
• 时钟时间戳使之唯一：如果你的节点的日历时钟使用 NTP 保持大致正确，你可以通过将该时钟的时间戳放在最高有效位中，并用确保 ID 唯一的额外信息填充剩余位来生成 ID，即使时间戳不是——例如，分片编号和每分片递增序列号，或长随机值。这种方法用于版本 7 UUID、Twitter 的 Snowflake、ULID、Hazelcast 的 Flake ID 生成器、MongoDB ObjectID 和许多类似方案。你可以在应用程序代码或数据库中实现这些 ID 生成器。
• 逻辑时钟：
  • Lamport 时间戳：Lamport 时间戳就是一对（计数器，节点 ID），但是需要额外的存储物理时间用来进行查询指定时间
  • 向量时间戳
• 线形一致的 ID 生成

共识

常见的共识算法，这些都是处理非拜占庭问题的：

• Viewstamped Replication
• paxos
• raft
• zab

共识算法的不可能性：FLP 结果 – 在异步系统模型中，假设确定性算法的前提下**（不能使用任何时钟和超时）**，不能保证共识算法总是终止。如果它可以使用超时来怀疑另一个节点已经崩溃，那么共识就可解。

单值共识

共识的标准表述涉及让多个节点就单个值达成一致。

共识算法需要满足以下属性：

• 安全性
  • 一致同意：没有两个节点决定不同
  • 完整性：如果
  • 有效性
• 活性（事情最后结果是往好的方向进行）
  • 终止：每个未崩溃的节点最终都会决定某个值。（要求节点数都是大于 N/2，如果小于 N/2 就会直接拒绝处理系统请求防止破坏系统一致性）

如果不考虑容错，可以使用一个节点接受读写，让该节点作出所有决定，但是该节点崩溃，那么系统就会直接崩溃。

实际应用场景包括：

• leader 选举
• 抢座

如果需要决定多个值，可以为每个值运行的共识算法创建单独的实例。例如多个位置抢座。

比较并设置作为共识

核心操作为 CAS：检测某个对象的当前值是否等于某个期待值，是则原子更新，不是则保持原有对象并返回错误。

CAS 和共识算法彼此等价。两者可以相互实现。但是，线性一致的读写寄存器不足以解决共识。因为他们读取是分离的，FLP 告诉我们共识不能由异步崩溃停止的模型中的确定性算法决定的。

这里我对此的理解有些模糊，感觉应该是氛围两种情况的 CAS 会比较清楚。
- CPU 层面的 CAS，也就是可以在本地机器上的 CPU 指令，用来协调不同的进程
- 分布式 CAS，单机上的 CAS 被抽象出来，使用一个抽象的共享寄存器用来保存提议值（zookeeper、etcd）

共享日志作为共识

共享日志包括一下两个操作：

• 可以将请求将值添加到日志中
• 可以读取日志中的条目

需要满足以下的属性：

• 最终追加：如果节点请求将某个值添加到日志中，并且节点不会崩溃，那么就可以读取到该值
• 可靠交付：没有日志丢失：如果一个节点读取到某日志，那么在其他未崩溃的节点也必须读取到该日志条目
• 仅追加：日志不可以被修改，只能往后追加。
• 一致性：所有节点的顺序和内容必须一致。
• 有效性：如果节点读取包含某个值的日志条目，那么某个节点先前请求将该值添加到日志中。（系统不能凭空捏造值，只能通过请求添加）

共享日志形式上为成为：全序广播、原子广播或全序组播协议。

基本实现流程：

1. 你为每个未来的日志条目在日志中都有一个槽，并且你为每个这样的槽运行共识算法的单独实例，以决定该条目中应该包含什么值。
2. 当节点想要向日志添加值时，它为尚未决定的槽之一提议该值。
3. 当共识算法为其中一个槽做出决定，并且所有先前的槽都已经决定时，则决定的值作为新的日志条目追加，并且已经决定的任何连续槽也将其决定的值追加到日志中。
4. 如果提议的值未被某个槽选择，想要添加它的节点会通过为稍后的槽提议它来重试。

这表明共识等价于全序广播和共享日志。没有故障切换的单主复制不满足活性要求，因为如果主节点崩溃，它将停止传递消息。像往常一样，挑战在于安全地自动执行故障切换。

获取并增加作为共识

核心思想可以使用获取并增加操作实现这样的 ID 生成器，该操作原子地递增计数器并返回久的计数器值。

作者在这里提出一个证明，如果已经有了获取并增加的一个操作，是否可以实现共识问题？答案是不能

1. 如果获胜者胜利后，在发送消息之前就崩溃了，其他节点将会被挂起，无法决定任何值。
2. 获取并增加只能解决共识数为二的节点的共识问题。CAS和共享日志的共识数为无穷大。（在并发系统中提供一个全局唯一的执行顺序，用于排队、排序和资源分配，但不能直接用于做一致性决策。）

原子提交作为共识

原子提交需要满足以下属性：

• 一致同意：没有两个节点决定不同的结果。
• 完整性（不可撤销性）：一旦决策生效就不能改变和更改。
• 有效性：如果节点决定提交，所有节点必须投票提交。如果任何节点终止，节点必须终止投票。（同 2PC）
• 非平凡性：如果所有节点都投票提交，并且没有通信超时，那么所有节点必须提交
• 终止：每个未崩溃的节点最终都会决定提交或者终止。

平凡性：很简单、边界情况、几乎不用思考就成立
非平凡性：需要真正协调、选择和冲突解决的问题。

原子提交和共识是彼此等价的：解释一个共享寄存器，初始为空，每个进程提出建议值，然后尝试写入寄存器（CAS），写入成果的进行发起原子提交并进行投票。成功那么就作为共识值；终止则重新发起新的尝试。

实践

单值共识、CAS、共享日志和原子提交都是彼此等价，可以相互转化为其他方案。但是大部分共识系统采用共享日志，Raft、Viewstamped Replication 和 Zab 直接提供共享日志。Paxos 提供单值共识，但在实践中，大多数使用 Paxos 的系统实际上使称为 Multi-Paxos 的扩展，它也提供共享日志。

单主复制到共识：单主实现共识相对比较简单，但是实现容错就很困难。传统上，具有单主复制的数据库没有解决这个问题：它们将主节点故障切换作为人类管理员必须手动执行的操作，会消耗大量时间。因此出现了自主选主的功能，为了防止脑裂，设置了一个约束较弱的约束

定义了一个 纪元编号（在 Paxos 中称为 投票编号，在 Viewstamped Replication 中称为 视图编号，在 Raft 中称为 任期编号）并保证在每个纪元内，主节点是唯一的。当节点因为在某个超时时间内没有收到主节点的消息而认为当前主节点已死时，它可能会开始投票选举新的主节点。这次选举被赋予一个大于任何先前纪元的新纪元编号。如果两个不同纪元中的两个不同主节点之间存在冲突（也许是因为先前的主节点实际上并没有死），那么具有更高纪元编号的主节点获胜。在主节点被允许将下一个条目追加到共享日志之前，它必须首先检查是否有其他具有更高纪元编号的主节点可能追加不同的条目。它可以通过从一个节点仲裁收集投票来做到这一点，通常（但并非总是）是多数节点。只有在节点不知道任何其他具有更高纪元的主节点时，节点才会投赞成票。因此，我们有两轮投票：一次选择主节点，第二次对主节点提议的下一个要追加到日志的条目进行投票。这两次投票的仲裁必须重叠：如果对提议的投票成功，投票支持它的节点中至少有一个也必须参与了最近成功的主节点选举 85。因此，如果对提议的投票通过而没有透露任何更高编号的纪元，当前主节点可以得出结论，没有选出具有更高纪元编号的主节点，因此它可以安全地将提议的条目追加到日志中.
这两轮投票表面上看起来类似于两阶段提交，但它们是非常不同的协议。在共识算法中，任何节点都可以开始选举，它只需要节点仲裁的响应；在 2PC 中，只有协调器可以请求投票，它需要 每个 参与者的”是”投票才能提交。

在