Content #

在 Basic Paxos 中，有提议者（Proposer）、接受者（Acceptor）、学习者（Learner）三种角色，他们之间的关系如下：

看着是不是有些复杂，其实并不难理解：

1. 提议者（Proposer）：提议一个值，用于投票表决。为了方便演示，你可以把图 1 中的客户端 1 和 2 看作是提议者。但在绝大多数场景中，集群中收到客户端请求的节点，才是提议者（图 1 这个架构，是为了方便演示算法原理）。这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑，就可以像使用数据库一样访问后端的数据。

2. 接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值，比如 A、 B、C 三个节点。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。

讲到这儿，你可能会有疑惑：前面不是说接收客户端请求的节点是提议者吗？这里怎么又是接受者呢？这是因为一个节点（或进程）可以身兼多个角色。想象一下，一个 3 节点的集群，1 个节点收到了请求，那么该节点将作为提议者发起二阶段提交，然后这个节点和另外 2 个节点一起作为接受者进行共识协商，就像下图的样子：

1. 学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份。

其实，这三种角色，在本质上代表的是三种功能：

1. 提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；

2. 接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；

3. 学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。

因为一个完整的算法过程是由这三种角色对应的功能组成的，所以理解这三种角色，是你理解 Basic Paxos 如何就提议的值达成共识的基础。

Viewpoints #

From #

05 | Paxos算法（一）：如何在多个节点间确定某变量的值？

Links #

Content #

栈的线性基地址为0x00007C00，段界限为0xFFFE，粒度为4KB，并设置栈指针寄存器ESP的初始值为0：

mov eax,0x0020 ;0000 0000 0010 0000 加载下标为4的段描述符
mov ss,eax
xor esp,esp    ;ESP <- 0

因粒度为4KB，实际使用的段界限为： 0xFFFFE * 0x1000 + 0xFFF = 0xFFFFEFFF ESP的最大值是0xFFFFFFFF，因此，操作该段时，处理器的检查规则是：

0xFFFFF000 <= (ESP - 操作数长度) <= 0xFFFFFFFF

其中，0xFFFFF000 = 0xFFFFEFFF + 1

该栈最低端的有效物理地址是： 0x00007C00 + 0xFFFFF000 = 0x00006C00 最高端的有效物理地址是： 0x00007C00 + 0xFFFFFFFF = 0x00007BFF 栈空间的大小是4KB。

当第一次压栈时： push ecx 先减ESP，再访问栈，此时ESP的值为： 0 - 4 = 0xFFFFFFFC

From #

Links #

Content #

物理时钟的难点首先是要做到足够高的精度，其次是在使用时如何处理时钟误差，学术一点的说法叫做时钟的置信区间。

逻辑时钟实际上是混合逻辑时钟，还是会引入物理时钟作为参考，但主要通过逻辑控制来保证时钟的单调递增。

是不是可以不用物理时钟？

对于多时间源是不行的，因为这样会造成不相关事件的时钟偏差太大，也就是偏序拼接的全序失真太大。如果是单时间源的混合逻辑时钟，它的好处是不用处理误差，简化了其他模块的设计。而 HLC 这样多时间源的混合逻辑时钟，则依然有时钟误差的问题。

时间对于分布式数据库的影响是什么？

时间在很多分布式系统都是存在的，比如 HBase 对于各节点的时钟偏移也是有限制，只不过它的容忍度更高，可以达到几十秒。而在分布式数据库中与时间有关的功能主要体现在事务并发控制，比如 MVCC、读写冲突。

Viewpoints #

From #

08 | 基础篇大串讲：重难点回顾+思考题答疑+知识全景图

Links #

Content #

Paxos 和 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 没有响应，但仍然得到了大多数节点的成功响应，所以也返回客户端提交成功。

Content #

CockroachDB 的解决方案是使用 Gossip 协议。你是不是想问，为什么不用 Paxos 协议呢？

这是因为 Paxos 协议本质上是一种广播机制，也就是由一个中心节点向其他节点发送消息。当节点数量较多时，通讯成本就很高。

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

看到这，你可能有点晕。我们在第 2 讲就说过分布式数据库是强一致性的，现在搞了个最终一致性的元数据，能行吗？

这里我先告诉你结论，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 在寻址过程中会不断地更新分片元数据，促成各节点元数据达成一致。

Content #

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

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

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

我将这个通讯过程画了下来，希望帮助你理解。

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

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

Viewpoints #

From #

07 | 数据复制：为什么有时候Paxos不是最佳选择？

Links #

Content #

该算法首次提出是在论文“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 函数已经过滤掉了业务属性，也很难解决访问业务热点问题。所谓业务热点，就是由于局部的业务活跃度较高，形成系统访问上的热点。这种情况普遍存在于各类应用中，比如电商网站的某个商品卖得比较好，或者外卖网站的某个饭店接单比较多，或者某个银行网点的客户业务量比较大等等。

Content #

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

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

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

Viewpoints #

From #

06 | 分片机制：为什么说Range是更好的分片策略？

Links #

Content #

实际上，到底使用 ASIC 这样的专用芯片，还是采用 FPGA 这样可编程的通用硬件，核心的决策因素还是成本。不过这个成本，不只是单个芯片的生产制造成本，还要考虑总体拥有成本（Total Cost of Ownership），也就是说，除了生产成本之外，我们要把研发成本也算进去。如果我们只制造了一片芯片，那么成本就是“这枚芯片的成本 + 为了这枚芯片建的生产线的成本 + 芯片的研发成本”，而不只是“芯片的原材料沙子的成本 + 生产的电费”。

单个 ASIC 的生产制造成本比 FPGA 低，ASIC 的能耗也比能实现同样功能的 FPGA 要低。能耗低，意味着长时间运行这些芯片，所用的电力成本也更低。

但是，ASIC 有一笔很高的 NRE（Non-Recuring Engineering Cost，一次性工程费用）成本。这个成本，就是 ASIC 实际“研发”的成本。只有需要大量生产 ASIC 芯片的时候，我们才能摊薄这份研发成本。

其实，在我们的日常软件开发过程中，也需要做同样的决策。很多我们需要的功能，可能在市面上已经有开源的软件可以实现。我们可以在开源的软件之上做配置或者开发插件，也可以选择自己从头开始写代码。

在开源软件或者是买来的商业软件上启动，往往能很快让产品上线。如果从头开始写代码，往往会有一笔不地的 NRE 成本，也就是研发成本。但是通常我们自己写的代码，能够 100% 贴近我们的业务需求，后续随着业务需求的改造成本会更低。如果要大规模部署很多服务器的话，服务器的成本会更低。学会从 TCO 和 NRE 的成本去衡量做决策，也是每一个架构师的必修课。

Viewpoints #

From #

32 | FPGA和ASIC：计算机体系结构的黄金时代

Links #

Content #

在实现 CPU 的功能的时候，我们需要完成各种各样的电路逻辑。在 FPGA 里，这些基本的电路逻辑，不是采用布线连接的方式进行的，而是预先根据我们在软件里面设计的逻辑电路，算出对应的真值表，然后直接存到一个叫作 LUT（Look-Up Table，查找表）的电路里面。这个 LUT 呢，其实就是一块存储空间，里面存储了“特定的输入信号下，对应输出 0 还是 1”。

如果还没理解，你可以想一下这个问题。假如现在我们要实现一个函数，这个函数需要返回斐波那契数列的第 N 项，并且限制这个 N 不会超过 100。该怎么解决这个问题呢？

斐波那契数列的通项公式是 f(N) = f(N-1) + f(N-2) 。所以，我们的第一种办法，自然是写一个程序，从第 1 项开始算。但其实还有一种办法，就是我们预先用程序算好斐波那契数量前 100 项，然后把它预先放到一个数组里面。这个数组就像 [1, 1, 2, 3, 5…] 这样。当要计算第 N 项的时候呢，我们并不是去计算得到结果，而是直接查找这个数组里面的第 N 项。

这里面的关键就在于，这个查表的办法，不只能够提供斐波那契数列。如果我们要有一个获得 N 的 5 次方的函数，一样可以先计算好，放在表里面进行查询。这个“查表”的方法，其实就是 FPGA 通过 LUT 来实现各种组合逻辑的办法。

Viewpoints #

From #

32 | FPGA和ASIC：计算机体系结构的黄金时代

Links #