分布式数据库（二）

小注

极客时间 - 分布式数据库 30 讲

全局时钟

分布式数据库的很多设计都和时间有关，更确切地说是和全局时钟有关。

常见授时方案

区分授时机制抓住三个要素就可以：

1. 时间源：单个还是多个。
2. 使用的时钟类型：物理时钟还是混合逻辑时钟。
3. 授时点：一个还是多个。

根据排列组合，一共产生了 8 种可能性，其中 NTP（Network Time Protocol）误差大，也不能保证单调递增，所以就没有单独使用 NTP 的产品；还有一些方案在实践中则是不适用的（N / A）。因此常见的方案主要只有 4 类：

TrueTime

Spanner 采用的方案是 TrueTime。它的时间源是 GPS 和原子钟，所以属于多时间源和物理时钟，同时它也采用了多点授时机制，就是说集群内有多个时间服务器都可以提供授时服务。

TrueTime 作为全局时钟的一种实现形式，是 Google 通过 GPS 和原子钟两种方式混合提供的授时机制，误差可以控制在 7 毫秒以内。例如，A、B 两个进程先后调用 TrueTime 服务，各自拿到一个时间区间，如果在其中随机选择，则可能出现 B 的时间早于 A 的时间。不只是 TrueTime，任何物理时钟都会存在时钟偏移甚至回拨。

它也有两个显著的优势：首先是高可靠高性能，多时间源和多授时点实现了完全的去中心化设计，不存在单点；其次是支持全球化部署，客户端与时间服务器的距离也是可控的，不会因为两者通讯延迟过长导致时钟失效。

HLC

CockroachDB 和 YugabyteDB 也是以高性能高可靠和全球化部署为目标，不过 Truetime 是 Google 的独门绝技，它依赖于特定硬件设备的思路，不适用于开源软件。所以，它们使用了混合逻辑时钟（Hybrid Logical Clock，HLC），同样是多时间源、多点授时，但时钟采用了物理时钟与逻辑时钟混合的方式。HLC 在实现机制上也是蛮复杂的，而且和 TrueTime 同样有整体性的时间误差。

TSO

其他的分布式数据库大多选择了单时间源、单点授时的方式，承担这个功能的组件在 NewSQL 风格架构中往往被称为 TSO（Timestamp Oracle），而在 PGXC 风格架构中被称为全局事务管理器（Golobal Transcation Manager，GTM）。这就是说一个单点递增的时间戳和全局事务号基本是等效的。这种授时机制的最大优点就是实现简便，如果能够保证时钟单调递增，还可以简化事务冲突时的设计。但缺点也很明显，集群不能大范围部署，同时性能也有上限。TiDB、OceanBase、GoldenDB 和 TBase 等选择了这个方向。

STP

最后，还有一些小众的方案，比如巨杉的 STP(SequoiaDB Time Protoco)。它采用了单时间源、多点授时的方式，优缺点介于 HLC 和 TSO 之间。

中心化授时：TSO（TiDB）

最早提出 TSO 的，大概是 Google 的论文 "Large-scale Incremental Processing Using Distributed Transactions and Notifications"。这篇论文主要是介绍分布式存储系统 Percolator 的实现机制，其中提到通过一台 Oracle 为集群提供集中授时服务，称为 Timestamp Oracle。所以，后来的很多分布式系统也用它的缩写来命名自己的单点授时机制，比如 TiDB 和 Yahoo 的 Omid。

考虑到 TiDB 的使用更广泛些，这里主要介绍 TiDB 的实现方式。

TiDB 的全局时钟是一个数值，它由两部分构成，其中高位是物理时间，也就是操作系统的毫秒时间；低位是逻辑时间，是一个 18 位的数值。那么从存储空间看，1 毫秒最多可以产生 262,144 个时间戳（2^18），这已经是一个很大的数字了，一般来说足够使用了。

单点授时首先要解决的肯定是单点故障问题。TiDB 中提供授时服务的节点被称为 Placement Driver，简称 PD。多个 PD 节点构成一个 Raft 组，这样通过共识算法可以保证在主节点宕机后马上选出新主，在短时间内恢复授时服务。

那问题来了，如何保证新主产生的时间戳一定大于旧主呢？那就必须将旧主的时间戳存储起来，存储也必须是高可靠的，所以 TiDB 使用了 etcd。但是，每产生一个时间戳都要保存吗？显然不行，那样时间戳的产生速度直接与磁盘 I / O 能力相关，会存在瓶颈的。

如何解决性能问题呢？TiDB 采用预申请时间窗口的方式，用一张图来表示这个过程：

当前 PD（主节点）的系统时间是 103 毫秒，PD 向 etcd 申请了一个『可分配时间窗口』。要知道时间窗口的跨度是可以通过参数指定的，系统的默认配置是 3 毫秒，示例采用了默认配置，所以这个窗口的起点是 PD 当前时间 103，时间窗口的终点就在 106 毫秒处。写入 etcd 成功后，PD 将得到一个从 103 到 106 的『可分配时间窗口』，在这个时间窗口内 PD 可以使用系统的物理时间作为高位，拼接自己在内存中累加的逻辑时间，对外分配时间戳。

上述设计意味着，所有 PD 已分配时间戳的高位，也就是物理时间，永远小于 etcd 存储的最大值。那么，如果 PD 主节点宕机，新主就可以读取 etcd 中存储的最大值，在此基础上申请新的『可分配时间窗口』，这样新主分配的时间戳肯定会大于旧主了。

此外，为了降低通讯开销，每个客户端一次可以申请多个时间戳，时间戳数量作为参数，由客户端传给 PD。但要注意的是，一旦在客户端缓存，多个客户端之间时钟就不再是严格单调递增的，这也是追求性能需要付出的代价。

分布式授时：HLC（CockroachDB）

HLC 作为一种纯软的实现方式，更加灵活，在 CockroachDB、YugabyteDB 和很多分布式存储系统得到了广泛使用。

HLC 不只是字面上的意思， TiDB 的 TSO 也混合了物理时钟与逻辑时钟，但两者截然不同。HLC 代表了一种计时机制，它的首次提出是在论文 "Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases" 中，CockroachDB 和 YugabyteDB 的设计灵感都来自于这篇论文。下面结合图片介绍一下这个机制：

假如有 ABCD 四个节点，方框是节点上发生的事件，方框内的三个数字依次是节点的本地物理时间（简称本地时间，Pt）、HLC 的高位（简称 L 值）和 HLC 的低位（简称 C 值）。

A 节点的本地时间初始值为 10，其他节点的本地时间初始值都是 0。四个节点的第一个事件都是在节点刚启动的一刻发生的。首先看 A1，它的 HLC 应该是 (10,0)，其中高位直接取本地时间，低位从 0 开始。同理，其他事件的 HLC 都是 (0,0)。

事件 D2 发生时，首先取上一个事件 D1 的 L 值和本地时间比较。L 值等于 0，本地时间已经递增变为 1，取最大值，那么用本地时间作为 D2 的 L 值。高位变更了，低位要归零，所以 D2 的 HLC 就是 (1,0)。

如果看懂了 D2 的计时逻辑就会发现，D1 其实是一样的，只不过 D1 没有上一个事件的 L 值，只能用 0 代替，是一种特殊情况。

如果节点间有调用关系，计时逻辑会更复杂一点。我们看事件 B2，要先判断 B2 的 L 值，就有三个备选：

1. 本节点上前一个时间 B1 的 L 值。
2. 当前本地时间。
3. 调用事件 A1 的 L 值，A1 的 HLC 是随着函数调用传给 B 节点的。

这三个值分别是 0、1 和 10。按照规则取最大值，所以 B2 的 L 值是 10，也就是 A1 的 L 值，而 C 值就在 A1 的 C 值上加 1，最终 B2 的 HLC 就是 (10,1)。

B3 事件发生时，发现当前本地时间比 B2 的 L 值还要小，所以沿用了 B2 的 L 值，而 C 值是在 B2 的 C 值上加一，最终 B3 的 HLC 就是 (10,2)。

在 HLC 机制下，每个节点会使用本地时钟作为参照，但不受到时钟回拨的影响，可以保证单调递增。本质上，HLC 还是 Lamport 逻辑时钟的变体，所以对于不同节点上没有调用关系的两个事件，是无法精确判断先后关系的。比如，上面例子中的 C2 和 D2 有同样的 HLC，但从上帝视角看，C2 是早于 D2 发生的，因为两个节点的本地时钟有差异，就没有体现这种先后关系。HLC 是一种松耦合的设计，所以不会去校正节点的本地时钟，本地时钟是否准确，还要靠 NTP 或类似的协议来保证。

多层级中心化授时：STP（巨杉）

巨杉采用了单时间源、多点授时机制，它有自己的全局时间协议，称为 STP（Serial Time Protocol），是内部逻辑时间同步的协议，并不依赖于 NTP 协议。下面是 STP 体系下各角色节点的关系：

STP 是独立于分布式数据库的授时方案，该体系下的各角色节点与巨杉的其他角色节点共用机器，但没有必然的联系。

STP 下的所有角色统称为 STP Node，具体分为两类：

1. STP Server：多个 STP Server 构成 STP Server 组，组内根据协议进行选主，主节点被称为 Primary，对外提供服务。
2. STP Client：按照固定的时间间隔，从 Primary Server 同步时间。

巨杉数据库的其他角色节点，如编目节点（CATALOG）、协调节点（COORD）和数据节点（DATA）等，都从本地的 STP Node 节点获得时间。

STP 与 TSO 一样都是单时间源，但通过增加更多的授时点，避免了单点性能瓶颈，而负副作用是多点授时就会造成全局性的时间误差，因此和 HLC 一样需要做针对性设计。

小结

1. 分布式数据库有多种授时机制，它们的区别主要看三个维度。一，是单时间源还是多时间源；二，时间源采用的是物理时钟还是混合逻辑时钟；三，授时点是一个还是多个。
2. TrueTime 是多时间源、多授时点方案，虽然仍存在时间误差的问题，但实现了高可靠高性能，能够支持 Spanner 做到全球化部署，是一种非常强悍的设计方案。TrueTime 是 GPS 加原子钟的整合方案，可以看作为一种物理时钟，它完全独立于 Spanner 的授时服务，不需要 Spanner 做专门的设计。
3. HLC 同样是多时间源、多授时点，由于是纯软方案，所以具有更好的通用性。CockroachDB 和 YugabyteDB 都采用了这种方案，也都具备全球化部署能力。HLC 的设计基础是 Lamport 逻辑时钟，对 NTP 的时间偏移有一定的依赖。
4. TSO 是典型的单时间源、单点授时方案，实现简便，所以成为多数分布式数据库的选择。如果 TSO 能够做到单调递增，会简化读写冲突时候的处理过程，但缺点是集群部署范围受到极大的限制。
5. 还有一些小众的方案，比如巨杉的 STP，也试图在寻求新的平衡点。

分片机制

分片就是解决性能和存储这两个问题的关键设计，甚至不仅是分布式数据库，在所有分布式存储系统中，分片这种设计都是广泛存在的。

什么是分片

分片在不同系统中有各自的别名，Spanner 和 YugabyteDB 中被称为 Tablet，在 HBase 和 TiDB 中被称为 Region，在 CockraochDB 中被称为 Range。无论叫什么，概念都是一样的，分片是一种水平切分数据表的方式，它是数据记录的集合，也是数据表的组成单位。

分布式数据库的分片与单体数据库的分区非常相似，区别在于：分区虽然可以将数据表按照策略切分成多个数据文件，但这些文件仍然存储在单节点上；而分片则可以进一步根据特定规则将切分好的文件分布到多个节点上，从而实现更强大的存储和计算能力。

分片机制通常有两点值得关注：

1. 分片策略：主要有 Hash（哈希）和 Range（范围）两种。可能还有 Key 和 List，其实 Key 和 List 可以看作是 Hash 和 Range 的特殊情况，机制类似。
2. 分片的调度机制：分为静态与动态两种。静态意味着分片在节点上的分布基本是固定的，即使移动也需要人工的介入；动态则是指通过调度管理器基于算法在各节点之间自动地移动分片。

分片机制的两个要点与提到的两种架构风格对应如下：

从表格中可以看出，PGXC 只支持静态的 Hash 分片和 Range 分片，实现机制较为简单。

PGXC

Hash 分片

Hash 分片，就是按照数据记录中指定关键字的 Hash 值将数据记录映射到不同的分片中。下图来表示 Hash 分片的过程：

图中的表格部分显示了一个社交网站的记录表，包括主键、用户 ID、分享内容和分享时间等字段。假设以用户 ID 作为关键字进行分片，系统会通过一个 Hash 函数计算用户 ID 的 Hash 值而后取模，分配到对应的分片。模为 4 的原因是系统一共有四个节点，每个节点作为一个分片。

因为 Hash 计算会过滤掉数据原有的业务特性，所以可以保证数据非常均匀地分布到多个分片上，这是 Hash 分片最大的优势，而且它的实现也很简洁。但示例中采用的分片方法直接用节点数作为模，如果系统节点数量变动，模也随之改变，数据就要重新 Hash 计算，从而带来大规模的数据迁移。显然，这种方式对于扩展性是非常不友好的。

一致性 Hash 可以提升系统的扩展性，该算法首次提出是在论文 "Consistent Hashing and Random Trees : Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" 当中。

要在工业实践中应用一致性 Hash 算法，首先会引入虚拟节点，每个虚拟节点就是一个分片。为了便于说明，在这个案例中将分片数量设定为 16。但实际上，因为分片数量决定了集群的最大规模，所以它通常会远大于初始集群节点数。

16 个分片构成了整个 Hash 空间，数据记录的主键和节点都要通过 Hash 函数映射到这个空间。这个 Hash 空间是一个 Hash 环。换一种方式画图，可以看得更清楚些。

节点和数据都通过 Hash 函数映射到 Hash 环上，数据按照顺时针找到最近的节点。

当新增一台服务器，即节点 E 时，受影响的数据仅仅是新服务器到其环空间中前一台服务器（即沿着逆时针方向的第一台服务器）之间数据。结合示例，只有小红分享的消息从节点 B 被移动到节点 E，其他节点的数据保持不变。此后，节点 B 只存储 Hash 值 6 和 7 的消息，节点 E 存储 Hash 值 4 和 5 的消息。

Hash 函数的优点是数据可以较为均匀地分配到各节点，并发写入性能更好。

本质上，Hash 分片是一种静态分片方式，必须在设计之初约定分片的最大规模。同时，因为 Hash 函数已经过滤掉了业务属性，也很难解决访问业务热点问题。所谓业务热点，就是由于局部的业务活跃度较高，形成系统访问上的热点。这种情况普遍存在于各类应用中，比如电商网站的某个商品卖得比较好，或者外卖网站的某个饭店接单比较多，或者某个银行网点的客户业务量比较大等等。

Range 静态分片

与 Hash 分片不同，Range 分片的特点恰恰是能够加入对于业务的预估。例如，用『Location』作为关键字进行分片时，不是以统一的行政级别为标准。因为注册地在北京、上海的用户更多，所以这两个区域可以按照区县设置分片，而海外用户较少，可以按国家设置为分片。这样，分片间的数据更加平衡。

但是，这种方式依然是静态的，如果海外业务迅速增长，服务海外用户的分片将承担更大的压力，可能导致性能下降，用户体验不佳。

相对 Hash 分片，Range 分片的适用范围更加广泛。其中一个非常重要的原因是，Range 分片可以更高效地扫描数据记录，而 Hash 分片由于数据被打散，扫描操作的 I/O 开销更大。但是，PGXC 的 Range 分片受限于单体数据库的实现机制，很难随数据变动和负载变化而调整。

虽然有些 PGXC 同时支持两种分片方式，但 Hash 分片仍是主流，比如 GoldenDB 默认使用 Hash 分片，而 TBase 仅支持 Hash 分片。

NewSQL

总体上，NewSQL 也是支持 Hash 和 Range 两种分片方式的。具体就产品来说，CockroachDB 和 YugabyteDB 同时支持两种方式，TiDB 仅支持 Range 分片。

NewSQL 数据库的 Hash 分片也是静态的，所以与 PGXC 差别不大，这里就不再赘述，着重讲述下 Range 动态分片。

Range 动态分片

NewSQL 的 Range 分片，多数是用主键作为关键字来分片的，当然主键可以是系统自动生成的，也可以是用户指定的。既然提供了用户指定主键的方式，那么理论上可以通过设定主键的产生规则，控制数据流向哪个分片。但是，主键必须保证唯一性，甚至是单调递增的，导致这种控制就会比较复杂，使用成本较高。所以，基本可以认为，分片是一个系统自动处理的过程，用户是感知不到的。这样做的好处显然是提升了系统的易用性。

将 NewSQL 的 Range 分片称为动态分片，主要有两个原因：

1、分片可以自动完成分裂与合并：当单个分片的数据量超过设定值时，分片可以一分为二，这样就可以保证每个分片的数据量较为均衡。多个数据量较少的分片，会在一定的周期内被合并为一个分片。

根据消息的数量来自动分片，我们可以得到 R1、R2、R3 三个分片。

分片也会被均衡地调度到各个节点上，节点间的数据量也保持总体平衡。

2、可以根据访问压力调度分片：系统之所以尽量维持分片之间，以及节点间的数据量均衡，存储的原因外，还可以更大概率地将访问压力分散到各个节点上。但是，有少量的数据可能会成为访问热点，就是上面提到的业务热点，从而打破这种均衡。比如，A 和 B 都是娱乐明星，有很多粉丝关注她们分享的内容，其访问量远超过普通人。这时候，系统会根据负载情况，将 R2 和 R3 分别调度到不同的节点，来均衡访问压力。

存储均衡 和 访问压力均衡，是 NewSQL 分片调度机制普遍具备的两项能力。此外，还有两项能力在 "Spanner" 论文中被提及，但在其他产品中没有看到工程化实现。

第一是减少分布式事务。对分布式数据库来说，有一个不争的事实，那就是分布式事务的开销永远不会小于单节点本地事务的开销。因此，所有分布式数据库都试图通过减少分布式事务来提升性能。

Spanner 在 Tablet，也就是 Range 分片，之下增加了目录（Directory），作为数据调度的最小单位，它的调度范围是可以跨 Tablet 的。通过调度 Directory 可以将频繁参与同样事务的数据，转移到同一个 Tablet 下，从而将分布式事务转换为本地事务。

第二是缩短服务延时。对于全球化部署的分布式数据库，数据可能存储在相距很远的多个数据中心，如果用户需要访问远端机房的数据，操作延时就比较长，这受制于数据传输速度。而 Spanner 可以将 Directory 调度到靠近用户的数据中心，缩短数据传输时间。当然，这里的调度对象都是数据的主副本，跨中心的数据副本仍然存在，负责保证系统整体的高可靠性。

Directory 虽然带来新的特性，但显然也削弱了分片的原有功能，分片内的记录不再连续，扫描要付出更大成本。而减少分布式事务和靠近客户端位置这本身就是不能兼顾的，再加上存储和访问压力，分片调度机制要在四个目标间进行更复杂的权衡。

分片与高可靠的关系

高可靠是分布式数据库的重要特性，分片是数据记录的最小组织单位，也必须是高可靠的。

NewSQL 与 PGXC 的区别在于，对于 NewSQL 来说，分片是高可靠的最小单元；而对于 PGXC，分片的高可靠要依附于节点的高可靠。

NewSQL 的实现方式是复制组（Group）。在产品层面，通常由一个主副本和若干个副本组成，通过 Raft 或 Paxos 等共识算法完成数据同步，称为 Raft Group 或 Paxos Group，所以我们简称这种方式为 Group。因为不相关的数据记录会被并发操作，所以同一时刻有多个 Group 在工作。因此，NewSQL 通常支持 Multi Raft Group 或者 Multi Paxos Group。

每个 Group 是独立运行的，只是共享相同的网络和节点资源，所以不同复制组的主副本是可以分布在不同节点的。

PGXC 的最小高可靠单元由一个主节点和多个备节点组成，借用 TDSQL 中的术语，将其称为 Set。一个 PGXC 是由多个 Set 组成。Set 的主备节点间复制，多数采用半同步复制，平衡可靠性和性能。这意味着，所有分片的主副本必须运行在 Set 的主节点上。

从架构设计角度看，Group 比 Set 更具优势，原因主要有两个方面。首先，Group 的高可靠单元更小，出现故障时影响的范围就更小，系统整体的可靠性就更高。其次，在主机房范围内，Group 的主副本可以在所有节点上运行，资源可以得到最大化使用，而 Set 模式下，占大多数的备节点是不提供有效服务的，资源白白浪费掉。

小结

1. 分片是分布式数据库的关键设计，以此实现多节点的存储和访问能力。
2. 分片机制的两个要点是分片策略和调度机制，分片策略包括 Hash 和 Range 两种，调度机制则分为静态和动态。
3. PGXC 使用单体数据库作为数据节点，往往只实现了静态分片。它的分片策略支持 Hash 和 Range 两种，其中 Hash 一般是指一致性 Hash，可以最大程度规避节点扩缩带来的影响。Hash 分片写性能出众，但查询性能差，Range 则相反。
4. NewSQL 的默认分片策略通常是 Range 分片。分片调度机制为了实现存储平衡和访问压力平衡的目标，会将分片动态调度到各个节点。Spanner 的设计又将在分片下拓展了 Directory，通过对 Directory 的调度实现减少分布式事务和缩短延时的目标，但在其他分布式数据库中尚未看到对应的实现。
5. NewSQL 架构下，分片采用 Paxos 或 Raft 算法可以构成复制组，这种复制机制相比 PGXC 的主备节点复制，提供了更高的可靠性，资源使用也更加高效。

数据复制

数据复制典型的算法就是 Paxos 和 Raft。其中比较重要的两个点就是分片元数据的存储和数据复制的效率。

分片元数据的存储

在任何一个分布式存储系统中，收到客户端请求后，承担路由功能的节点首先要访问分片元数据（简称元数据），确定分片对应的节点，然后才能访问真正的数据。这里说的元数据，一般会包括分片的数据范围、数据量、读写流量和分片副本处于哪些物理节点，以及副本状态等信息。

从存储的角度看，元数据也是数据，但特别之处在于每一个请求都要访问它，所以元数据的存储很容易成为整个系统的性能瓶颈和高可靠性的短板。如果系统支持动态分片，那么分片要自动地分拆、合并，还会在节点间来回移动。这样，元数据就处在不断变化中，又带来了多副本一致性（Consensus）的问题。

以下是不同产品存储元数据的具体：

静态分片

最简单的情况是静态分片。可以忽略元数据变动的问题，只要把元数据复制多份放在对应的工作节点上就可以了，这样同时兼顾了性能和高可靠。TBase 大致就是这个思路，直接将元数据存储在协调节点上。即使协调节点是工作节点，随着集群规模扩展，会导致元数据副本过多，但由于哈希分片基本上就是静态分片，也就不用考虑多副本一致性的问题。

但如果要更新分片信息，这种方式显然不适合，因为副本数量过多，数据同步的代价太大了。所以对于动态分片，通常是不会在有工作负载的节点上存放元数据的。

所以解决方法一般是专门给元数据搞一个小规模的集群，用 Paxos 协议复制数据。这样保证了高可靠，数据同步的成本也比较低。TiDB 大致就是这个思路，但具体的实现方式会更巧妙一些。

TiDB：无服务状态

在 TiDB 架构中，TiKV 节点是实际存储分片数据的节点，而元数据则由 Placement Driver 节点管理。Placement Driver 这个名称来自 Spanner 中对应节点角色，简称为 PD。

在 PD 与 TiKV 的通讯过程中，PD 完全是被动的一方。TiKV 节点定期主动向 PD 报送心跳，分片的元数据信息也就随着心跳一起报送，而 PD 会将分片调度指令放在心跳的返回信息中。等到 TiKV 下次报送心跳时，PD 就能了解到调度的执行情况。

由于每次 TiKV 的心跳中包含了全量的分片元数据，PD 甚至可以不落盘任何分片元数据，完全做成一个无状态服务。这样的好处是，PD 宕机后选举出的新主根本不用处理与旧主的状态衔接，在一个心跳周期后就可以工作了。当然，在具体实现上，PD 仍然会做部分信息的持久化，这可以认为是一种缓存。

通讯过程大致如下：

三个 TiKV 节点每次上报心跳时，由主副本（Leader）提供该分片的元数据，这样 PD 可以获得全量且没有冗余的信息。

虽然无状态服务有很大的优势，但 PD 仍然是一个单点，也就是说这个方案还是一个中心化的设计思路，可能存在性能方面的问题。

CockroachDB：去中心化

CockroachDB 的解决方案是使用 Gossip 协议。不采用 Paxos 协议的原因是 Paxos 协议本质上是一种广播机制，也就是由一个中心节点向其他节点发送消息。当节点数量较多时，通讯成本就很高。

CockroachDB 采用了 P2P 架构，每个节点都要保存完整的元数据，这样节点规模就非常大，当然也就不适用广播机制。而 Gossip 协议的原理是谣言传播机制，每一次谣言都在几个人的小范围内传播，但最终会成为众人皆知的谣言。这种方式达成的数据一致性是 “最终一致性”，即执行数据更新操作后，经过一定的时间，集群内各个节点所存储的数据最终会达成一致。

CockroachDB 真的是基于“最终一致性”的元数据实现了强一致性的分布式数据库。

过程图如下：

1. 节点 A 接到客户端的 SQL 请求，要查询数据表 T1 的记录，根据主键范围确定记录可能在分片 R1 上，而本地元数据显示 R1 存储在节点 B 上。
2. 节点 A 向节点 B 发送请求。很不幸，节点 A 的元数据已经过时，R1 已经重新分配到节点 C。
3. 此时节点 B 会回复给节点 A 一个非常重要的信息，R1 存储在节点 C。
4. 节点 A 得到该信息后，向节点 C 再次发起查询请求，这次运气很好 R1 确实在节点 C。
5. 节点 A 收到节点 C 返回的 R1。
6. 节点 A 向客户端返回 R1 上的记录，同时会更新本地元数据。

可以看到，CockroachDB 在寻址过程中会不断地更新分片元数据，促成各节点元数据达成一致。

复制协议的选择和数据副本数量有很大关系：如果副本少，参与节点少，可以采用广播方式，也就是 Paxos、Raft 等协议；如果副本多，节点多，那就更适合采用 Gossip 协议。

复制效率

具体来说就是 Raft 与 Paxos 在效率上的差异，以及 Raft 的一些优化手段。在分布式数据库中，采用 Paxos 协议的比较少，知名产品就只有 OceanBase，下面的差异分析会基于 Raft 展开。

Raft 的性能缺陷

顺序投票是影响 Raft 算法复制效率的一个关键因素。

完整的 Raft 日志复制过程如下：

1. Leader 收到客户端的请求。
2. Leader 将请求内容（即 Log Entry）追加（Append）到本地的 Log。
3. Leader 将 Log Entry 发送给其他的 Follower。
4. Leader 等待 Follower 的结果，如果大多数节点提交了这个 Log，那么这个 Log Entry 就是 Committed Entry，Leader 就可以将它应用（Apply）到本地的状态机。
5. Leader 返回客户端提交成功。
6. Leader 继续处理下一次请求。

以上是单个事务的运行情况。那么，当多事务并行操作时，又是什么样子的呢？过程如下图：

设定这个 Raft 组由 5 个节点组成，T1 到 T5 是先后发生的 5 个事务操作，被发送到这个 Raft 组。

事务 T1 的操作是将 X 置为 1，5 个节点都 Append 成功，Leader 节点 Apply 到本地状态机，并返回客户端提交成功。事务 T2 执行时，虽然有一个 Follower 没有响应，但仍然得到了大多数节点的成功响应，所以也返回客户端提交成功。

现在，轮到 T3 事务执行，没有得到超过半数的响应，这时 Leader 必须等待一个明确的失败信号，比如通讯超时，才能结束这次操作。因为有顺序投票的规则，T3 会阻塞后续事务的进行。T4 事务被阻塞是合理的，因为它和 T3 操作的是同一个数据项，但是 T5 要操作的数据项与 T3 无关，也被阻塞，显然这不是最优的并发控制策略。

同样的情况也会发生在 Follower 节点上，第一个 Follower 节点可能由于网络原因没有收到 T2 事务的日志，即使它先收到 T3 的日志，也不会执行 Append 操作，因为这样会使日志出现空洞。

Raft 的顺序投票是一种设计上的权衡，虽然性能有些影响，但是节点间日志比对会非常简单。在两个节点上，只要找到一条日志是一致的，那么在这条日志之前的所有日志就都是一致的。这使得选举出的 Leader 与 Follower 同步数据非常便捷，开放 Follower 读操作也更加容易。要知道，我说的可是保证一致性的 Follower 读操作，它可以有效分流读操作的访问压力。

Raft 的性能优化方法（TiDB）

在真正的工程实现中，Raft 主副本也不是挨个处理请求，还是有一些优化手段的。TiDB 的官方文档对 Raft 优化说得比较完整，这里引用过来，着重介绍下它的四个优化点：

1. 批操作：Leader 缓存多个客户端请求，然后将这一批日志批量发送给 Follower。Batch 的好处是减少的通讯成本。
2. 流水线：Leader 本地增加一个变量（称为 NextIndex），每次发送一个 Batch 后，更新 NextIndex 记录下一个 Batch 的位置，然后不等待 Follower 返回，马上发送下一个 Batch。如果网络出现问题，Leader 重新调整 NextIndex，再次发送 Batch。当然，这个优化策略的前提是网络基本稳定。
3. 并行追加日志（Append Log Parallelly）：Leader 将 Batch 发送给 Follower 的同时，并发执行本地的 Append 操作。因为 Append 是磁盘操作，开销相对较大，而标准流程中 Follower 与 Leader 的 Append 是先后执行的，当然耗时更长。改为并行就可以减少部分开销。当然，这时 Committed Entry 的判断规则也要调整。在并行操作下，即使 Leader 没有 Append 成功，只要有半数以上的 Follower 节点 Append 成功，那就依然可以视为一个 Committed Entry，Entry 可以被 Apply。
4. 异步应用日志（Asynchronous Apply）：Apply 并不是提交成功的必要条件，任何处于 Committed 状态的 Log Entry 都确保是不会丢失的。Apply 仅仅是为了保证状态能够在下次被正确地读取到，但多数情况下，提交的数据不会马上就被读取。因此，Apply 是可以转为异步执行的，同时读操作配合改造。

其实，Raft 算法的这四项优化并不是 TiDB 独有的，CockroachDB 和一些 Raft 库也做了类似的优化。比如，SOFA-JRaft 也实现了 Batch 和 Pipeline 优化。

etcd 是最早的、生产级的 Raft 协议开源实现，TiDB 和 CockroachDB 都借鉴了它的设计。甚至可以说，它们选择 Raft 就是因为 etcd 提供了可靠的工程实现，而 Paxos 则没有同样可靠的工程实现。既然是开源，为啥不直接用呢？因为 etcd 是单 Raft 组，写入性能受限。所以，TiDB 和 CockroachDB 都改造成多个 Raft 组，这个设计被称为 Multi Raft，所有采用 Raft 协议的分布式数据库都是 Multi Raft。这种设计，可以让多组并行，一定程度上规避了 Raft 的性能缺陷。

同时，Raft 组的大小，也就是分片的大小也很重要，越小的分片，事务阻塞的概率就越低。TiDB 的默认分片大小是 96M，CockroachDB 的分片不超过 512M。那么，TiDB 的分片更小，就是更好的设计吗？也未必，因为分片过小又会增加扫描操作的成本，这又是另一个权衡点了。

小结

1. 分片元数据的存储是分布式数据库的关键设计，要满足性能和高可靠两方面的要求。静态分片相对简单，可以直接通过多副本分散部署的方式实现。
2. 动态分片，满足高可靠的同时还要考虑元数据的多副本一致性，必须选择合适的复制协议。如果搭建独立的、小规模元数据集群，则可以使用 Paxos 或 Raft 等协议，传播特点是广播。如果元数据存在工作节点上，数量较多则可以考虑 Gossip 协议，传播特点是谣言传播。虽然 Gossip 是最终一致性，但通过一些寻址过程中的巧妙设计，也可以满足分布式数据的强一致性要求。
3. Paxos 和 Raft 是广泛使用的复制协议，也称为共识算法，都是通过投票方式动态选主，可以保证高可靠和多副本的一致性。Raft 算法有“顺序投票”的约束，可能出现不必要的阻塞，带来额外的损耗，性能略差于 Paxos。但是，etcd 提供了优秀的工程实现，促进了 Raft 更广泛的使用，而 etcd 的出现又有 Raft 算法易于理解的内因。
4. 分布式数据库产品都对 Raft 做了一定的优化，另外采用 Multi Raft 设计实现多组并行，再通过控制分片大小，降低事务阻塞概率，提升整体性能。

加餐：Raft 由于顺序投票的限制，在复制效率上比 Paxos 稍差。但是因为 Raft 有高质量的开源实现项目 etcd；而 Paxos 因为算法复杂没有稳定的开源能实现，所有 TiDB 和 CockroachDB 还是选择了 Raft 协议。同时，TiDB 和 CockroachDB 采用了 Multi Raft 的方式，让多分片并行处理提升性能。两者在 Raft 协议实现上也进行了若干改进。这些改进思路很有普适性，一些独立的 Raft 项目也同样实现了，比如 SOFA-JRaft。

学习资料

Daniel Peng and Frank Dabek: Large-scale Incremental Processing Using Distributed Transactions and Notifications

Sandeep S. Kulkarni et al.: Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases