前言

大多数应用程序是通过一层一层叠加数据模型来构建的，如果某一层使用到了大量的数据，那么就需要一个数据系统来进行管理。

怎么理解上面这句话呢，在一整个应用系统中，一条数据可能由不同的数据模型来表示，例如：

  • 在前端，数据以 JSON Object 的形式存在于内存之中，而其可能来源于 API 服务提供的 JSON 格式的一串字符；
  • 这个 API 服务可能是用 Go 实现的，这条数据在构建为 JSON 字符串之前，可能在内存中以 Go Struct 的形式存在；
  • API 服务可能是从 Redis 的响应中获取的数据，因此这条数据可能以 RESP（Redis 通信协议）规定的格式存在过，从 Redis 发送到 API 服务；
  • Redis 能提供这条数据，说明这条数据在 Redis 的内存中以某种数据结构存在过；
  • Redis 可能会将数据备份到硬盘，因此这条数据可能在硬盘上以某种格式存在过；
  • 硬盘上，这条数据以某种磁场、电流的形式存在过；

那么为什么会存在这么多数据模型的转换呢？🧐

因为每一层的需求都不一样。通常来说，数据在内存中的数据模型较为直接，但是也需要根据内存的特性进行优化（对齐）；在硬盘中，可能要考虑空间利用率；在服务与服务的通讯中（协议），可能要考虑编解码性能、数据大小甚至是可阅读性；在 Redis/MySQL 等数据库中，要考虑数据的检索查找性能。

也就是说，在日常的编程过程中，无时无刻不在跟数据模型打交道，但是得益于前人的优秀设计与各种框架（各种语言内存模型与通信协议的规定），以及自身经验与最佳实践的指导，可能在无意间就选择了较优的形式来进行实现，通常情况不需要进行较为底层的数据模型的设计与选择。

但是一些应用的功能就是保存、处理和检索大量数据，例如上文提到的 Redis、MySQL 等数据库，如果想要满足需求（通用、性能与数据安全等），则需要对数据模型进行仔细地审查与设计。

针对这样的数据密集型应用系统，前人们有了许多的求索与探讨。

显然，你可以为每一种数据单独设计数据模型进行优化，但这是不现实的，因为数据格式多样多变，数据系统作为应用系统的底层，承载着各种各样的数据，无法对每种数据进行专门的优化，但是对某一类数据进行优化是可能的，这个类可大可小，表现了不同程度的通用性。

一、目标：通用

通用意味着我们需要从数据中总结出一套模式，还需要设计从这套模式中进行查询的方法。

1.1 通用模型设计

1.1.1 层次模型

层次模型将所有数据表示为嵌套在记录中的记录（树）。显然，这种结构天然很好的支持了一对多的关系，但是对于多对一和多对多的关系，则没有明确的设计，因此实际使用时，要么将数据复制多份，要么留下一个引用进行手动处理（无法自动联结）；这些方式都会导致数据维护的困难。

围绕多对多关系的处理困境，出现了关系模型与网络模型。

1.1.2 网络模型

网络模型又被称为 CODASYL 模型，是层次模型的推广。层次模型作为树结构，每个节点最多只会有一个父节点；网络模型为了更好的支持多对多关系，将其推广，每个节点允许拥有多个父节点。每次插入新节点时，相关的父节点就进行了更新，天然进行了联结，形成了新的关系结构。

为了实现这种灵活的数据关系，各个节点之间的关系变为了引用（指针）；由于过于灵活，数据访问的唯一方法是选择一条始于根目录的路径，并沿着相关链接依次访问，而这条链条也被称为访问路径。如果想要从根节点开始查询某个数据，那么需要进行大量复杂的遍历，十分低效，因此在新增相关的一组数据时，需要记录访问路径以便于后续从这些数据上检索，这使得每次查询都需要手动设定访问路径以进行优化，否则几乎不可用。

同时，在维护数据时更是十分困难，一个节点可能有多个父节点指向它，对该节点的操作会引起大量变动。

1.1.3 关系模型与关系数据库

关系模型直接否定了层次模型的嵌套结构：关系（表）只是元组（行）的集合，因此关系模型能通过元组天然表示一对一的关系，通过扩展外键（联结）实现一对多、多对一与多对多。联结关系（外键）作为额外扩展功能，由关系数据库实现。在如此简洁的结构之下，查询优化器诞生了，它用于查询顺序以及索引使用的自动选择，相当于自动构建出一条优化过后的访问路径，这也是通用性的一种表现。同样的，通用也增添了复杂，由于查询操作多种多样，查询优化器变得十分庞大且复杂；但总体来说这种方式兼具了通用和性能，成为了当下的主流选择。

1.1.4 文档模型与文档数据库

关系数据库中，一对一关系能够天然直接表示，但是常见的一对多关系稍微有点别扭。在表和元组的关系下，一对多需要对父进行复制或者联结（或者说在不对等的关系中，需要对少的一方进行复制或者联结）。因此层次模型因为能天然表示一对一和一对多关系，还是在一些领域有一定的优势的，特别是在本身就是嵌套结构的文档数据领域。

为了保留嵌套结构的同时实现多对一和一对多，文档数据库参考了关系数据库的实现，采用了“外键”的概念，称之为“文档引用”；这种引用的联结需要额外的操作来实现，因为其并未在结构中实际存在。

1.1.5 图状数据模型

前文提到的模型在面对海量的多对多关系时仍然会力不从心，但是这种场景在现实中却是常见的，因此图状数据模型作为针对这一类数据的优化产物出现了。图由顶点和边组成，能够天然的表示多对多关系，在模式上更加的自由。具体有属性图模型和三元存储模型等类型。

1.1.6 关系数据库与文档数据库的对比

关系数据库的基础结构很简单（元组），而文档数据库的基础结构为树；在文档数据库中，一对多关系表现为整体，而在关系数据库中则被拆分为多个元组，因此文档数据库因其局部性而具有更好的性能。在实际使用中，关系模型更多的是对现实模型的拆解，展示出其通用性；如果实际数据更符合文档模型，那么使用文档数据库会更加简洁；如果实际数据关系更加复杂（大量的多对多），那么使用图数据库会更加简洁。

  1. 文档模型的灵活优势：由于文档模型中数据结构通常十分灵活，因此文档数据库通常不限制数据的具体模式，又被称之为“无模式”，但显然模式是存在的，只是交给了应用层处理，被称之为读时模式；与之对应的关系数据库则限制写入时数据的模式，要求其符合规则，又被称之为写时模式。
  2. 数据局部性的优劣：文档模型与层次模型类似，基础结构为树，在读取时则以树为单位，因此相关联的数据会被同时读取，如果要访问文档内大部分内容的话，则具有较强的局部性优势；但如果只是读取或者修改文档中的一小部分的话，就有点得不偿失，表现为劣势。如果修改后文档大小发生变化（主要是文档增大后），那么文档树甚至不能覆盖保存回原位置，而是需要重新分配。

1.1.7 关系数据库与文档数据库的融合

最简单的例子便是关系数据库的元组中支持 XML、JSON 等文档数据结构。

1.2 通用查询设计

数据库数据模型的设计十分重要，但是考虑到数据库的主要功能之一：查询，设计出一种通用的查询方法也是至关重要的。与一般的程序调用 lib 不同，数据库存储着大量不同的模式，为了在这些模式上实现通用的查询等操作，数据库的接口必须十分灵活，这促使了数据查询语言的出现。

  1. 命令式：网络模型（CODASYL）在前文中提到，每次查询需要设定访问路径，这个设定便是通过命令式查询语言实现的，这要求用户需要自行组织具体的查询逻辑；
  2. 声明式：关系数据库所使用的声明式查询语言（SQL 或关系代数）只需制定所需的数据模式、条件以及转换规则，查询优化器会组织具体的查询逻辑步骤，这意味着只要不断优化查询优化器，无需对查询语句修改即可实现性能提升。而且随着多核处理器的出现以及大尺度上集群的出现，声明式更适合查询优化器生成并行查询的逻辑操作，大大提高查询效率，可以说是适应了时代的潮流。
  3. MapReduce：是一种混合命令与声明的查询方式，通过将命令式的纯函数代码片段复用，适应了集群分布执行的环境，可以作为 SQL 等声明式查询语言具体执行时的基础操作。

图状数据模型中，声明式和命令式查询语言都有。

1.3 模型的实现

数据库，即采用了这些数据模型的数据系统，主要功能就是存储和查询。由于数据库作为专门存储和检索数据的系统，常常存储着远超系统内存大小的数据，为了同时管理内存和硬盘中的数据，引入了存储引擎的概念；就算以内存数据库著称的 Redis 等系统，为了数据安全通常也会启用持久化备份，同样需要管理内存和硬盘中的数据。

数据库的核心，或者说存储引擎的核心是数据结构，我们以最简单的 kv 数据库为例，一步步探讨存储引擎的设计。

$$O(n)$$

我们把这个硬盘文件称之为段文件，显然对于拥有大量数据的数据库来说，这是不可接受的；因此还必须引入索引的概念，即帮助定位数据的元数据。显然写入文件尾部这一操作已经是数据写入的最简操作了，任何额外的元数据构建或者说索引的引入，都会降低写入性能。在这一简易场景下，最简单的索引便是 HashMap，也称之为哈希索引。在这里我们拥有了追加写段文件与哈希索引，分别存在于硬盘和内存中，结合起来完成数据的管理。

1.3.1 追加写段文件 + 哈希索引

追加写段文件在添加数据时具有极好的性能，因为其基础操作是最简单的往文件尾添加数据；虽然会有许多旧值存在，但是通过扫描段文件能很轻易地实现段文件的整理和压缩，保留每个 key 最新的值，只需在后台定期压缩即可。考虑到单文件过大带来的问题，追加写段文件能很轻易地在文件大小达到阈值后进行分段，只需要写入新文件即可；对于这些段文件的压缩和合并可以定时在后台完成。

在内存的 HashMap 中记录硬盘上每个 key 的偏移值，这样查询能在 O(1) 完成；这个 HashMap 能够通过扫描段文件构建，或者是构建完成后保存在硬盘中，重启后读取构建。如果进行了分段，那么每一段都有其对应的 HashMap，在查找时只需要根据段的新旧顺序，从新往旧搜索即可。

两者的配合可以实现数据量较小情况下的高性能数据库。但由于哈希索引的设计问题，导致

  1. 系统内存需要能够容纳所有的 key;
  2. 由于段文件无序，区间查询时只能通过哈希索引在段文件中跳来跳去读取，拼凑出区间结果，效率很低。

1.3.2 有序段文件 SSTABLE + 哈希索引

为了解决前文提到的问题，很容易想到将段文件设计为有序的，相对应的有两大好处：

  1. 系统内存中只需记录部分 key 的位置，当查询某个 key 时，只要能找到其可能所在的区间就可以了；
  2. 段内数据有序，可以按顺序直接读出区间值。

显然，不能只规定说段文件有序就行了，需要思考 🤔 如何维护其有序的状态：

  1. 显然不能直接往段文件尾部追加写了，这样无法维持其有序的状态，所以必须在内存中缓存一部分的数据，我们称之为内存表，当其达到一定的量后再排序写入段文件（或者从一开始就使用有序数据结构来管理，例如红黑树，避免写前排序），这样产生的段文件就都是有序的了；
  2. 如果系统崩溃，那么内存中缓存的部分数据会丢失，因此还是要将其持久化到硬盘，以便于恢复；显然，可以使用前文中追加写段文件的形式来持久化这部分数据，由于我们已经规定段文件有序，那么这个“追加写段文件”我们便另外称之为“追加写日志”，不参与查询和合并操作，只用于故障恢复；
  3. 对于段文件的压缩，有序后反而更简单了，不必将两个段文件完全读入内存便可以完成合并压缩工作，因此这部分不受影响；
  4. 还有一点细节，当内存数据写入有序段文件后，这部分的追加写日志便失去了作用，可以丢弃了。

要注意的是，上述过程中所有写入硬盘的操作都是顺序写，因此写性能极高。

这部分所提到的段文件的维护方式，正是 LevelDB 和 RocksDB 所使用的；而前文提到的直接追加写的方式，则是 Bitcask 所使用的。

基于合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎；其中 LSM 表示 Log-Structured Merge，原因是这些有序段文件实际上是追加写的日志文件演变而来，且基于这些文件的压缩合并。这个结构也被称为 LSM-Tree（日志结构的合并树），原因是实践过程中，有序段文件的合并并不是随意进行的，我们将最基础零碎的段文件不断合并后，会形成一系列经历过一次合并的段文件，而这些段文件还能进行合并，依此类推，是存在层级结构的，这样便形成了树；我们可以针对不同层级采取不同的压缩策略。

1.3.3 B-Tree

前文提到的 LSM 存储引擎虽然简单好用，但是仍有其缺陷：

  1. 其后台进行的合并压缩操作会占据一定的硬盘读写带宽，如果数据量巨大，合并压缩操作完全占据了磁盘的读写带宽，那么数据库便无法对外提供服务；
  2. 就算没有全部占据，合并压缩操作也会对服务请求的处理产生影响，造成随机的响应延迟，有点类似于带有 GC 机制的语言的缺点；
  3. 其次，不同的段文件中可能包含 key 新旧时期不同的值，为事务语义的实现增添了不少风险；
  4. 读取性能较弱，虽然用布隆过滤器可以避免许多不必要的查找操作，但是搜索范围可能涉及多个段文件的读取；
  5. 二级索引实现困难。

关于索引与存储引擎，显然存储引擎为了实现高效的查找功能，在存储设计时一定会有对应的索引设计，就如上文中的哈希索引一样，在 kv 数据库中表现为 key 的索引；在关系数据库中表现为主键的索引（必定有一个这样的索引）。在这个主索引之外，通常还需要创建二级索引，以加速非主键上的查询操作。

有没有响应时间稳定，读取性能更好，二级索引简单的存储引擎选择呢 🤔？那就是老牌的 B-Tree 了。

B-Tree 把数据库分解成固定大小的块或页，页是内部读写的最小单元，与磁盘的块排列设计相匹配；每个页面都可以用其在磁盘上的位置进行标识，相当于磁盘上的指针。其中一个页作为 B-Tree 的根，所有的查询操作都从这里开始。

页中包含键和其他页的引用，每个引用代表着一个连续范围内的键，相邻引用之间的键可以指示这些范围的边界，这些数据都是有序存放的，便于二分查找。B-Tree 中一页所包含的引用数称为分支因子，实际中这个因子会收到页大小等因素的影响，会达到几百。

在 B-Tree 中更新某个 key 时，首先要找到其值所在的叶子页，然后将其修改后覆盖整个叶子页；如果添加某个 key 时，其值应在的叶子页已满，那么就需要进行分裂操作。分裂操作意味着原来指向叶子页的引用也将变成两个，因此会涉及到父页、原叶子页与两个新叶子页的处理；如果删除某个 key 后仍然要使 B-Tree 保持平衡，那么需要更多额外的操作。

平衡状态下，具有 n 个键的 B-Tree 总是具有 O(logn)的深度，具有优秀的查询性能。但如同上文介绍的 B-Tree 的更新、新建和删除操作中对页的操作，当涉及到多个页的更新，甚至是单页的覆盖时，磁盘无法同时完成这些操作，因此这些操作并非原子化，可能在操作中途中止，导致数据的一致性损坏。同 LSM-Tree 一样，可以使用 WAL（Write-Ahead Log）来记录相关操作，该日志用于将 B-Tree 恢复到最近一致的状态；同样的，多线程访问 B-Tree 时也会出现问题，因此要进行并发控制。

B-Tree 的优化
  1. 由于 B-Tree 下操作的基本单位是页，而页在覆盖过程中出问题就导致数据损坏，因此可以使用写时覆盖方案：被修改的页并不原地覆盖，而是被写入别的位置，这样仅需修改父页的指针即可，我们可以在确认被修改的页写入完毕后最后才修改指针，因此这期间并不影响其他数据的访问。
  2. 页的大小是固定的，我们希望能尽量提高页空间的利用率，以保存更多的键和引用，提高树的分支因子，进而减少层数。由于节点中键是有序排列的，中间的键其实可以只使用缩略信息，并不影响键的查找。
  3. 相邻子页存放在相邻位置，但是会很难维护
  4. 额外指针连接相邻的叶子页

关于 B-Tree，可以学习 SQLite 的实现，简单易懂，有些课程甚至教你如何实现自己的 SQLite，例如：Build your own SQLite。

1.3.4 数据仓库的优化

与我们常见的强调交互性的事务处理不同，还有一种数据系统是用来大量数据分析的，并不太强调交互性，提交的任务几个小时甚至几天处理完成都可以。针对这样的超大数据分析场景，也有一些常见的优化策略。

典型的数据仓库中，表的列十分之宽，而且每次进行分析时，经常都是把整列所有的数据都拉出来进行处理，因此出现了列式存储和列压缩的概念：

  1. 列式存储将一列的所有数据存放在一起，特别适合整列查询较多的场景；
  2. 使用列式存储后，便很容易使用列压缩来降低磁盘吞吐量的要求，原因是一列中，通常会有大量重复数据；

二、目标：可用

前文简单介绍了数据系统的一些底层通用设计，但是仅仅考虑这些单机底层的问题还不够，因为现实中数据太过珍贵，作为一个数据系统，无法容忍数据丢失的出现；因此在讨论完数据系统的底层细节后，还要从更宏观的角度来设计以保证其可用性。数据系统的可用性更是一个复杂的主题，原因是计算机硬件和网络的不稳定性带来了无法忽视的问题和挑战。

“当一个不可能出错的事物出错了，通常也就意味着不可修复” ——Douglas Adams，《基本无害》（1992）

这意味着要提升数据系统的可用性和健壮性，不能想当然的认为其某部分是不可能出错的，而是要慎重考虑各部分出错后的备案和处理方式。

2.1 数据复制

当一个数据系统部署在单节点上后，出现的第一个问题便是：这个节点挂掉了怎么办 😨？ 很自然的便能想到“备份”这一方案；在多台机器上保存相同的数据副本，这便是复制，也便产生了分布式数据系统。

你可以仅仅把备份当作是备份，以提高可用性：当节点挂掉后切换到备份节点提供服务；你也可以让备份平时也发挥点作用，对外提供服务，以提高整体的读吞吐量；你还可以精心挑选备份节点的物理位置，让它们为用户提供更低延迟的服务。

在数据不会发生改变的场景下，上述讨论就已经很完美了，但是现实情况不一样，数据系统在不断的更新数据，这才是复制的挑战所在。

显然，数据系统在不断更新数据的时候，我们要以某个或者某些节点的数据为准，其他节点“复制”这些节点的数据，因此天然区分出了主节点与从节点。按照主节点数量的不同，我们可以分出这几类复制方式：主从复制、多主节点复制和无主节点复制。

2.1.1 主从复制

主从复制是从单节点扩展出备份节点后天然形成的复制模式，为了保证每个节点上的数据保持一致，我们可以想象，为了保证数据的一致，任何一个写入更改操作，无论经过了什么操作处理流程，最终终将在每个节点上执行。

在主从复制中，主节点负责接受写操作，并将其转发给各个从节点，这样便让所有节点都能接受到相同的写操作；对于读操作而言，由于其并不会对数据进行更改，因此从主从节点上读都是可以的。

这个转发的过程，也就是写操作何时在各个节点上执行，也有不同的策略选择，这便是同步复制和异步复制。从名称上就能看出，同步复制需要等待写操作在各个节点上执行完毕后，用户的写操作才算是完全结束，如果有任何一个节点失败（失去状态同步），那么操作就算是失败；异步复制则是主节点完成写操作，便视为用户的写操作完成，而从节点能否接收执行写操作，用户不管，由分布式数据系统来尽量保证这一点。

可以想象，同步复制需要每个节点都完成操作，但只要有一个节点故障便会操作失败，当节点数量很多时，操作的失败率便指数级上升；异步复制只需考虑主节点，因此不管节点数量有多少，都不会影响异步复制情况下操作的执行。

异步复制看起来和实际用起来性能却是很好，但是与同步复制相比缺少了一个保证：同步复制保证写操作完成后，所有节点的状态都是最新的，可以随便读；但是异步复制只能保证主节点是最新的，需要等待一段由无数因素影响的时间后，节点的状态才能都更新到最新。当然，聪明的你一定能想到，中庸之道，综合这两种方式，在系统中存在同时存在同步节点和异步节点，在同步和异步的优缺点之间 lerp 一下，找到合适自己的设定。

要注意的是，在异步复制中，由于那个虚无缥缈的更新延迟时间的存在，主节点故障会导致数据丢失，这是在很多情况下都决不允许的，但是现代分布式数据系统对性能的要求很高，无法割舍异步复制带来的吞吐性能，因此只能在此基础上打各种补丁，尽量避免数据丢失的发生。

接下来要考虑的是节点故障后该怎么处理，由于系统中只存在两类节点，因此我们分别进行探讨。

从节点失效

从节点只是起到一个备份作用，而且从节点往往不止一个，所以如果只是从节点失效，那还是挺让人放心的，并不会影响系统的可用性；从节点只需要根据自身已持久化的数据被日志，对比主节点的日志，便能同步缺失的各种操作，一旦同步完毕便能够正常提供服务了。

主节点失效

在主从复制中，主节点负责所有的写操作，一旦主节点失效，便意味着系统无法对外提供正常的服务了，因此主节点失效的处理至关重要。

  1. 尽快发现失效：由于节点们可能位于不同的物理位置，又都是相对独立的在运行，因此节点是否失效，保底的检测机制只能是超时。而超时时间的设定也有很大的影响，如果设置过长，那么恢复时间也会变长；如果设置过短，很有可能导致节点误认为失效，出现频繁失效切换。
  2. 尽快切换主节点：原来的主节点挂掉了，我们又希望系统能尽快重新上线，那么不可能指望原主节点修复故障、重新启动，只能是立马决定换一个可用的节点作为主节点。这个切换的过程涉及到新主节点的选举，以及如何让其他节点知道主节点切换了；这些可以是问题也可以不是问题，比如，你可以手动选择节点，手动更新其它节点的配置，但显然这会引入最不可靠的“人”进入系统，因此需要一套称为共识的机制，来自动完成这一操作，关于共识会在后文深入探讨。

就算如此，主节点失效还是很危险的，原因是超时并不意味着原主节点真的停止了任何工作，异常情况下原主节点很有可能不知道自己出问题了，就像是精神病患者不认为自己有精神病一样，这样很可能出现双主节点同时工作产生冲突的情况，因此我们需要让系统内所有节点统一决定原主节点是否已经失效，如果一致认为原主节点失效，那么就算原主节点工作正常，也将被当作精神病处理，忽略它的任何请求，这个问题也等同于一个创建一个共识。

复制没有完美的解决方案，只能在众多参数中，例如副本一致性、持久性、可用性以及延迟等，寻求最适合最平衡的那个点；这同样也是其它分布式系统问题解决方案的核心：取舍。

异步复制的问题

异步复制由于其同步延迟的存在，就算节点都工作正常，也会有各种各样的问题，下面简单介绍几种常见问题：

  1. 单调读一致性：当用户多次读取同一数据时，由于节点状态有新有旧，很有可能第一次读到新数据而第二次却读到了旧数据，这就不满足单调读一致性；
  2. 读写一致性：当用户写完数据尝试读取时，由于有的节点状态还没更新，可能读到旧的数据，导致用户观察到了“数据丢失”，这就不满足读写一致性；

解决方法也很直观，针对单调读一致性，需要让用户多次读取时都读取同一个节点，这个可以通过用户标识来唯一指定读节点来解决；针对读写一致性，可以让用户写后只从主节点读取数据；

还有出现在分片情况下的特殊问题：前缀一致读。由于还未介绍分片，因此这里只简单介绍一下：不同用户的因果相关的两个操作被分在了两个分片上，那么它们被查询时，由于异步复制延迟的存在，并没有先后关系，导致因果关系混乱。

使用最终一致性系统时，首先就要思考复制延迟增加到几分钟甚至几小时时造成的影响，如果不可接受那就需要采取措施提供一个更强的一致性保证。

2.1.2 多主复制

由于主从复制中，主节点承担了太过重要的角色，一旦主节点失效，那么等同于系统失效，因此我们自然地进行扩展，想到将主节点配制成多个，分担写操作的工作。显然，系统内节点的状态还是要统一的，因此每个主节点也会接收其他主节点的写操作，就像是从节点一样。

显然，多主节点的设计使得写操作的同步变得十分复杂，通常来说在一个数据中心内使用多节点没有太多意义，也并没有解决太多的问题，所以我们一般只在以下几种情况内使用多主复制：

  1. 多数据中心：由于物理的限制，主节点可能与从节点距离非常远，造成通信消耗极大，整个系统的效率急剧降低；
  2. 离线客户端：网络断开后还需要能够正常使用，因此需要在本地配置一个主节点（本地数据库）来接受写操作，在联网时就相当于有多主的问题需要处理；
  3. 协作编辑：例如 Google Docs 等文档应用，都是允许多个用户同时进行编辑的，每个用户都有着像“主节点”一样的写权限，先修改本地，然后同步给其它节点。

显然，从上面列出的场景可以看出，多主复制的主要挑战是解决冲突（显然，多主复制的复杂情况下更不可能使用同步复制了，因此我们讨论都是基于异步复制）。

写冲突

这是多主复制中最常见的情况，例如两个用户“同时”从两个不同的主节点更新了数据库中的某一条记录，当这两个主节点想要将修改同步时，便产生了冲突，究竟该怎么处理，或者说采用哪一条？

避免冲突

在逻辑上这两条是完全平等的，我们需要制定规则，强行分出先后优先级。🤔 或者说，我们可以先发制人，解决提出问题的人：我们可以尽量避免冲突。

写冲突产生的条件是两个主节点接收并处理了同一条记录的写操作，那么我们让特定数据的写操作只发生在指定主节点上，这样将数据的写操作划分分配给不同主节点后，便不会产生冲突了。

可喜可贺，但是我们仍需考虑这种方案故障下的情况，例如用户想要写某条数据，但是他与指定的主节点网络连接不上，但是与其它主节点连接正常，难道我们要拒绝为用户提供服务吗？当然可以拒绝，但是可能更好的方案是 在这种特殊情况下我们可以让其它主节点接手一定的工作，唯一的代价是可能会有写冲突产生。

收敛于一致状态

当然，除了数据写操作分工方案可能出现故障外，还有一些情形是这种方案无法使用的，例如前文提到的协作编辑、离线客户端等，它们的本地主节点是大概率编辑同一条数据的，写冲突是无法避免的。在这种情况下，我们希望 根据有限的信息进行写操作的前后人为排序，而且人为排序一定是稳定的，这意味着无论哪个节点遇到这样的冲突，拿到相同的信息后，做出的判断都是一致的，这被称为收敛于一致状态。

下面举例几种收敛于一致状态的处理方式：

  1. 以某种方式将这些冲突值合并或者保留，例如按照字母排序然后拼接在一起。本质是保留信息，交给用户或者是后续再处理；
  2. 给写入操作分配唯一 ID，根据唯一 ID 判断顺序，将最高优先级的操作写入，其它丢弃；显然会造成数据丢失；
  3. 给节点或者说副本分配唯一 ID，根据副本 ID 判断顺序，将高优先级的操作写入，其它丢弃；显然也会造成数据丢失。

这里的数据丢失可以这样理解：由于写冲突是不同的用户在修改相同的数据，那么如果用户的操作被丢弃，那么他想要修改的值甚至不会在数据库中出现，在他看来就好像他的操作丢失了一样（事实也确实是丢失了）。

有人可能会疑问 🤔，那他在编辑记录里也看不到自己的操作吗？显然不能，因为他的写操作都未在数据库上执行，更无法保存在编辑记录中了。那有没有可能将冲突操作排序后，按照顺序都执行一次呢？这个想法很好，只可惜现实情况是：

  1. 首先在冲突产生之前，这些操作已经在各自的节点上执行过一次了，如果想要按照顺序执行一遍，还需要撤销之前的操作；
  2. 其次由于异步复制，等收集完所有的冲突操作后再整体排完序是不可能的。同一个位置的冲突可能表现为，冲突解决后，过一段时间又在同一个位置收到了一个冲突的写操作（可能网络延迟导致晚点了），需要再次与保存的写操作进行冲突解决。这也是要使用收敛于一致状态的处理方式的原因，每个节点解决冲突的顺序是不一样的，但是要保证解决完结果都保持一致。

在冲突处理上，实际上都是人为规定的解决方案，有人会说严格按照时间戳来判断不就行了，但是在分布式系统中各个节点的时间戳都是有偏差的，没有准确的全局时钟存在。因此各个方案并无高低之分，重要的是冲突解决的结果符合业务的需求。因此许多数据库提供自定义冲突解决的方案，当写入或者读取时执行冲突解决代码。

前文提到的冲突是很直观的直接对同一条数据修改造成的冲突，实际上同时对不同的数据也可能造成冲突，这种冲突是逻辑上的，破坏了数据中隐含逻辑关系的。例如：两位员工都有一个休假标识，规定这两位不能同时处于休假状态；某天他们同时申请休假，按照程序都检查了另一位的休假状态，于是放心地在不同的主节点上执行了休假操作，操作也没有任何冲突产生，但是结果就是二人都处于了休假状态。

自动冲突解决

前文提到了数据库提供了自定义冲突解决方案，只需提供冲突解决代码即可；但是这个代码可不是那么容易就能写好的，因此有前人研究了一些比较完善的适合冲突解决的数据结构或者算法，给出了更加严谨和通用的解决方案：

  1. 无冲突的复制数据类型（Conflict-free Replicated Datatypes，CRDT）
  2. 可合并的持久数据结构（Mergeable persistent data）
  3. 操作转换（Operational transformation）

感兴趣可以自行深入了解。

拓扑结构

前文有提到多主复制架构中，主节点还要接收其它主节点发来的写操作，说明这些主节点间存在着可能的多种联系路径，这便是多主复制主节点的拓扑结构。

很容易想到，如果某个主节点只能从另一个特定的主节点到达，那么一旦那个主节点出现故障，这个主节点便无法完成状态同步了。按照节点间访问路径的多少，大致可以分为以下三种常见的拓扑结构：

  1. 环形拓扑
  2. 星形拓扑
  3. 全链接拓扑

显然访问路径越多，对于节点的故障容忍能力就越好；但是当访问路径有很多时，路径速度有快有慢，很有可能后发生的操作会先于之前的操作到达，如果这两个操作间有因果关系，那么便会产生错误。为了让操作消息正确有序，可以使用版本向量，这将在后文详细讲解。

2.1.3 无主复制

说是无主，实际上是全主，意味着所有副本都可以接受来自客户端的写请求，我们目前把无主数据库称之为 Dynamo 风格数据库。每次进行写操作时，要么客户端直接将请求发送给多个副本，要么客户端将请求发送给协调者节点，由协调者决定发送给哪些副本。

显然，当客户端可以将写请求发送给每一个副本并完成时，这个数据库能提供其正常的服务；但是当客户端只能发送给部分副本，或者说部分副本失效时，该如何处理呢？当然，这里的处理分为两个部分，一是某些副本数据较旧，读到旧数据怎么办；二是数据较旧的副本，该如何保持状态同步。

  1. 副本状态不一致读问题：为了解决这一问题，我们可以想到，客户端既然可以将写请求发送给各个副本，那么读请求也不必拘泥于某个副本，而是并行的读，然后取最新的一个值；显然，这需要每个值都有一个版本号。
  2. 旧副本状态同步：从问题 1 的解决方案可以看出，在并行读的时候是能够察觉到某些节点的状态落后的，因此可以使用读修复，在并行读后更新那些落后的副本；如果读操作很少，那么就不能只依靠客户端的读操作来同步了，我们可以在后台运行一些进程专门用于对比缺少的数据来进行复制，这被称为反熵过程。
读写 quorum

前文提到客户端自己或者通过协调者将写请求发送到多个副本，那么这些写请求是否成功该如何判断呢？假设需要所有副本都成功，那么显然回到了同步复制的问题，一旦节点数量达到一定数量，写操作就很难成功了；从前文我们还知道，部分副本就算没有更新到最新的状态，我们通过并发读还是能获取正确的数据，这就意味着并发读使得写操作有了一定的容错。

推广到一般情况：如果有 n 个副本，写入需要 w 个节点确认，读取必须至少查询 r 个节点，则只要 w+r>n，读取的节点中一定会包含最新值。满足这些 r、w 值的读写操作称为仲裁读和仲裁写，也被称为严格法定票数。

为什么被称之为“严格”呢？我们知道并发读使得写操作有了一定的容错，而一般情况并没有限制读发生在哪些节点上；如果我们从 n 中取子集 n’，且确保读写都发生在 n’ 内，那么只要满足 w’+r’>n’，还是能起到同样的效果的。

反之，就算满足了 w+r>n，也不一定就能读到最新值：例如在一些边界条件下，两个写操作同时发生，导致其中一个写操作在冲突处理中被丢弃，读便会发现数据丢失；如果读写同时进行，那么写操作可能还未进行完，导致读去旧值。由于现实情况的复杂性，Dynamo 风格的数据库通常不追求一定能读取到最新值，而是针对最终一致性场景进行的优化，因此在配置参数 w、r 时，应当其作为概率保证而不是绝对保证。

sloppy quorum

前文提到我们设定 n 或者其子集 n’，只要满足 w+r>n 都能够实现相同的效果，因此我们无需使用所有节点，我们总假设 n 为全部节点的某个确定的子集。但是由于读写操作是独立的，我们无法将其分组，只能规定在一定时间内，读写操作都在 n 节点上进行才能持续保证 w+r>n 的条件。

实际情况是多变的，可能出现客户端无法访问全部 n 中节点的情况，是否为这样的客户端提供服务，便成为了一种选择。如果为这种情况提供服务，那么我们称之为宽松的 quorum：写入和读取仍然需要 w+r>n，但是写入和读取的节点不一定在 n 中；当网络恢复后，临时接受请求的节点需要把收到的写请求转发给 n 中的节点，这被称之为回传；在回传完成之前，读操作无法保证都能读取到新值。

冲突处理

与多主复制类似，无主复制中也会产生写冲突，原因是一旦支持写并发，那么说明写之间的顺序是不确定的。与多主复制类似可以采用最后写入者获胜（last write wins, LWW）：

按照一定的规则对并发写操作进行排序，然后保留最新的那一个，这被称之为最后写入者获胜，这里的“最后”不一定是时间上的最后，只是表达了一种顺序的概念；显然，同多主复制一样，也会导致数据丢失。要确保 LWW 安全无副作用的唯一方法是：只写入一次然后写入值视为不变，这样就避免了对同一个主键的并发（覆盖）写，实际中可以对每个写操作都使用其 UUID 作为主键，只是在查询时同一个 key 会查询到多个数据，需要进行处理。

并发与并发检测

前文提到的冲突是发生在写并发的场景下，假如两个操作属于并发关系，才需要考虑冲突解决；否则，两个操作有先有后，后操作是可以安全覆盖前操作的；为此我们必须考虑并发检测。我们定义，如果两个操作不需要意识到对方，那么它们是并发操作。通过区分前后与并发关系，我们可以使用比 LWW 更好的方法，来避免数据丢失：

  1. 每个主键都有一个写入时递增的版本号，值可能有多个最新版本，对应并发写操作；
  2. 写前必须要发起读，且读会提供所有最新版本的值；
  3. 写时必须提供之前读到的版本号；且写的响应可以与读一致，这样可以减少一次读操作，实现连续写；
  4. 数据库收到写操作时，由于其带有版本号，因此可以覆盖该版本号或更低版本的所有值。

这样通过版本控制，并发写不会导致数据丢失，但是多个版本的最新数据仍需考虑如何处理，这里可以提供自定义的解决方式，例如最常见的操作便是合并；也可以和多主复制一样，使用一些专门的数据结构来执行自动合并。

版本矢量

前文提到每个主键都有一个写入时递增的版本号，在多副本的情况下，每个副本的同一个主键的版本号情况可能是不同的，因此我们收集所有副本的版本号信息，集合称之为版本矢量；通过版本矢量，来决定是否覆盖或者保留。

2.2 数据分区

介绍完了数据复制，我们可以想象数据被复制成为了多个副本以保证数据的安全性和系统的可用性，但在实际中数据的量可能十分庞大，超出了单个节点的最大容量，或者单个节点无法承担这些数据的写入和读取请求，我们必须考虑把一份数据拆分存放，这便是数据分区，也就是前文提到的数据分片。

在完成数据分区后，每个分区就可以运用前文提到的各种技术，进行数据复制了，分区之间具有一定的独立性，可以看作是完整的小型数据库；但是不可避免的，一些操作会同时涉及到多个数据分区，我们在后面会进行详细的探讨。

2.2.1 键值数据的分区

面临海量的键值数据，该怎么进行分区呢？或者说分区的目标是什么呢？

无论是数据量太大因此单节点无法承受还是因为读写操作单节点无法承受而进行分区，都是因单节点到达瓶颈产生的选择，因此在分区后我们希望尽量避免单节点瓶颈，这就要求分区的结果一定要均匀。

基于关键字区间分区

我们规定关键字的顺序后，便能按照顺序手动划分成许多区间，然后按照这些区间进行数据分区，显然这种分区方式很灵活，因为区间设定可以手动也可以自动，但这要求管理员或者数据库对这类型的数据有一定了解，才能够划分均匀。

基于关键字哈希值分区

通过使用一个好的哈希函数，可以让各个关键字哈希后在值域上均匀分布，此时在值域上进行分区便能比直接基于关键字区间分区更加均匀；但问题是哈希分区后，相邻的键被分配到了不同的分区，区间查询无法连续进行了。有些数据库如果启用了哈希分片，那么在区间查询时便把请求一次性发送到所有的分区；而有些数据库则干脆不支持关键字上的区间查询。

为此，有些数据库采取折中的策略，可以将多列组成复合主键，并将较少执行区间查询的列用作哈希关键字进行分区，这样便不会影响常见的分区查询操作。

负载倾斜与热点

数据的均匀并不意味着负载的均匀，原因是某些数据可能会被高频率访问；如果要解决热点问题，最简单的方法就是在热点关键字后加上随机数，这样关键字变动会使得这个关键字的数据被划分到不同分区，以减轻节点压力，这需要读取操作时同时读取这一批关键字合并才能得到结果。

2.2.2 分区与二级索引

前文提到的键值数据分区，暗示讨论的情况是数据只有主键索引的情况；如果引入二级索引，情况会变得复杂起来。但是二级索引是十分重要的，在以查询业务为主的数据库中，对查询的加速离不开二级索引。因此我们以文档数据库这类以查询为主的数据库为例，探讨二级索引的分区。

二级索引带来的主要挑战是它们不能规整地映射到分区中，我们要考虑二级索引如何在分区之中存放。有两种主要的方法来支持对二级索引进行分区：

基于文档的二级索引分区

二级索引通常使用倒排索引实现，这意味着二级索引记录着其 key 出现在哪些文档中，具体表现为每个索引条目对应一个文档列表。我们在每个分区中独立为其包含的文档建立二级索引，这就意味着不同分区的二级索引是独立的，因此也被称为本地索引；当进行查询操作时，需要同时查询所有分区的二级索引，汇总后才能得到最终结果，这会导致显著的读延迟放大。

基于词条的二级索引分区

我们可以对所有文档建立二级索引列表，然后对列表进行分区，存储在不同的节点上，这也被称之为全局索引；这意味着每个分区上存储的二级索引与那个分区上存储的文档没有什么关联。其优势是每个二级索引词条存储的都是完整的文档列表，只需查询一次即可；但文档更新时，由于其涉及到的二级索引位于各个分区，因此会引入显著的写放大。因此现有的数据库都不支持同步更新词条分区的二级索引。

2.2.3 分区的再平衡

分区并不是一劳永逸的，随着时间的推移，平均总会变得不平均，因此分区的再平衡是在使用前就要考虑到的工作。

考虑到数据量的庞大，我们希望分区再平衡时移动的数据越少越好。对此我们主要有以下三种处理方式：

固定数量的分区

分区数量虽然固定，但是我们可以在一开始划分较多的分区，并且让一个节点负担多个分区；这样当节点压力过大时，我们不重新分区，而是把现有分区抽取部分转移到新节点上，以减轻节点的平均压力。显然，一开始决定的分区数量十分重要，过多的分区会导致额外管理开销过大；过少的分区会使得后续的再平衡困难。

动态分区

当分区数据量增长超过阈值后，便会拆分为两个小分区；当分区数据量缩小到某个阈值以下，也可以合并成一个较大的分区。拆分后的小分区可以将其中一个交由别的节点进行管理。

按节点比例分区

固定数量的分区和动态分区中，分区数量与节点数量没有任何关系，一个是固定数量而一个是按照策略分裂合并。对此，引入了节点数量作为参数的新方式，使分区数量与集群节点数成正比关系：

当一个新节点加入集群时，它随机选择固定数量的分区进行分裂，然后拿走一半的数据进行管理。

这个方案要求使用哈希分区，原因是如果是按照关键字分区，取走的区间很有可能都位于集中的几个节点之上。

最后，再平衡是一个很昂贵的操作，我们通常希望数据系统给出一个方案，由人工确认后再执行，可以有效防止各种意外。例如：你也不想正在用户访问高点时进行分区吧。

2.2.4 分区的请求路由

前面介绍了很多分区相关的知识，但是从客户端的角度来看，分区后该怎么找到数据的位置呢，更何况还有可能发生再平衡，数据分区的关系还会发生变化。这其实属于一类典型的服务发现问题，主要有如下方案：

  1. 允许客户端链接任意节点，由分区节点转发请求；
  2. 请求路由层，路由层感知分区状态；
  3. 客户端感知分区状态。

无论是分区节点处理、路由层处理还是客户端处理，都需要其感知分区状态，也就是维护一份映射表，这要求其感知分区与节点对应关系以及变化；更糟糕的是，节点、路由层实例和客户端往往都不止一个，要让他们有统一的分区状态视图。

显然，涉及到多节点统一，就离不开共识；除了内置共识算法处理外，还可以通过 ZooKeeper 等独立协调服务（外挂的共识服务）来进行管理。

由于共识部分内容较为独立且庞大，可以参考我写的：分布式系统设计思路总览。

2.2.5 并行查询优化

由于分区后相当于有多个独立运行的小数据库，为了充分运用其性能，可以将复杂的查询分解成许多执行阶段和分区，在不同的节点上执行。

结语

至此，关于数据系统的通用性与可用性的简单探讨便结束了。考虑到事务虽然基础，但其实是数据库为了减轻应用层心智负担而承担的功能，而且内容较多，因此单独在后续文章中详细介绍：数据系统事务的简单探讨；同样的，共识也是很大的一个独立领域，因此在分布式系统设计思路总览这篇文章中作为重点进行详细介绍。