分布式基础概念
RPC
终止方式
客户发出请求之后自己崩溃了,服务器上的计算就成了没人要的孤儿。处理办法有再生,消灭,温和再生四种。
消灭 (Extermination)
最直接的方法。客户端在发起调用前,将请求记录在持久化日志中。当客户端重启后,根据日志通知服务器终止那些未收到回复的孤儿计算。它的优点是精确,但维护日志会带来额外开销,且对网络分区等情况处理能力有限。
再生 (Reincarnation)
基于“纪元”的机制。客户端将时间划分为递增的纪元号。重启后,客户端广播新纪元。服务器收到新纪元广播后,会终止所有属于旧纪元的远程计算。这种方式简单,但比较“粗暴”,可能会错误地杀死一些仍在正常运行的调用。
做崩溃前发起的某些RPC调用可能仍然有意义。
温和再生 (Gentle Reincarnation)
是对“再生”的优化。服务器收到新纪元广播后,不会立刻杀死所有旧计算,而是先尝试联系这些计算的所有者(客户端)。只有确认客户端确实无法联系时,才终止计算。这减少了误杀,但增加了定位客户端的开销。
过期 (Expiration)
基于时间限制。每个RPC调用都分配一个固定的最长执行时间。如果服务器在截止时间前未完成,就假定该调用已失效并将其终止。客户端重启后,只需等待一个足够长的时间(大于最大执行时限),就能确保所有孤儿都已消失。这依赖时钟同步,且时限的设定需要在及时性和避免误杀之间权衡。
通信模式
异步通信是发出去就不管了,继续去干别的事情。
同步通信是,不回复就一直等待。
持久persistence是消息具有存储特性,不会因为发送方或者接收方的宕机而丢失。
瞬时Instantaneous:消息存在时间很短,如果瞬间没法送到,或者接收方没来得及处理,消息就丢了,不保证送达。
| 维度 | 异步 (Async) | 同步 (Sync) |
|---|---|---|
| 持久 (可靠存储) | 电子邮件 / 消息队列 (发完就走,消息存着慢慢处理) | 等消息存入队列才返回 (必须确认存盘/入队才放行) |
| 瞬时 (不保证可靠) | UDP 数据报 / 异步 RPC (发出去就走,不管对方收没收到) | 普通 RPC (发出去必须等到应答,中间不能断) |
MPI message passing interface。是一种用于分布式内存系统的并行编程标准或规范。在MPI模型中,各个进程拥有独立的内存空间,彼此无法直接读取对方的数据。因此,必须通过显式地发送和接收消息来交换数据、共享信息。MPI定义的是接口的语法和语义(比如函数名、参数含义),确保代码具有可移植性。只要你的程序遵循MPI标准,就可以在提供MPI库的任何系统上编译运行。常见的具体实现有 Open MPI、Intel MPI、MPICH 等。
MPI的应用领域非常垂直,几乎只活跃在高性能计算和科学计算的圈子里,大部分日常工程用不到它。
MPI是为分布式内存的超级计算机设计的,典型场景是:一个机器有几千上万个CPU核心,分布在几十上百个节点上,大家要一起计算一个巨型数学问题。
MPI 是 C/Fortran(科学计算的老牌语言) 级别的 API,需要手动管理进程、内存缓冲区、通信域(Communicator)。工程中如果真用到了并行计算,通常也不会直接写 MPI 代码,而是用已经封装好 MPI 的上层框架。
时间
你的电脑主板上,确实有石英晶体振荡器。它利用石英的压电效应产生非常稳定的高频振荡,为计算机的各种电路提供精准的节拍信号。此外,主板上还有一个由独立电池供电的“实时时钟”电路,它同样依赖石英晶体,负责在电脑关机后继续计时,让你下次开机时系统时间依然大致准确。
石英钟虽然比机械钟准得多,但它并非完美。石英晶体的振荡频率会受温度变化、元件老化等因素影响,产生微小的漂移。如果电脑只依赖自带的石英钟,时间久了就会出现误差。
时钟有个指标叫做最大偏移率。理想的时钟每秒走一秒。实际的时钟每秒的误差不超过$\rho$,俩台时钟朝相反的方向飘,每秒最多拉开2$\rho$。

比如偏移每秒是十万分之一,$\delta$ 为1毫秒(俩台机器差距不超过1毫秒),就得每50秒同步一次。
同步算法:cristian算法,需要建设来回的延时相等。

这里依赖时间不能倒流,客户端的时钟快了不能直接往回拨。否则会出现后发生的事情时间戳反而更小。应该直接让时钟走慢一点。
另一种是berkeley算法。它不要求有准确的时间源。目标只是让大家一致。时间守护进程主动询问每台机器的时间。算出平均值,再告诉每台机器应该调整多少。

这个算法由 Gusella 和 Zatti 在 1989 年提出,最初是为了 Berkeley UNIX 的分布式系统运行而设计的内部同步方案。它与我们之前讨论的 NTP 有本质区别:NTP 的目标是让客户端对齐到绝对的真实时间;而 Berkeley 算法的目标仅仅是让一组机器彼此之间保持一致,它们共同维护一个“平均时间”作为标准。
互联网上实际使用的是NTP算法。

这里T2是收到请求的时间,T3是发回请求的时间。它们是为了算出服务器处理请求花了多少时间。从而从总时间里剥离出来,求出真实的网络往返延迟。
互斥
分布式算法Ricart-Agrawala。把时间戳,进程号的请求发给所有其他线程,等所有人回OK。收到请求的分三种情况。
- 自己不想进:直接回 OK。
- 自己正在临界区:不回复,把请求放入队列,等自己退出临界区后再回 OK。
自己也想进(但还没进):比较双方请求的
(时间戳, 进程号)。- 如果请求方更小(时间戳更早,或时间戳相同但进程号更小):立即回 OK。
- 如果自己更小:不回 OK,把请求排队,等自己用完临界区后再补发 OK。
这个算法没有单点故障,但是变成了n个故障点:任何一个进程崩溃不回复,大家都卡住。
还有一种算法是令牌环算法,把进程排成一个逻辑环。令牌沿着环传递,拿到令牌才能进临界区。不想进就直接向下传。它不会饿死,但是令牌可能丢失。而且很难判断令牌是丢了还是有人用的太久。
一致性
一致性定义
Bully 算法本身并不解决共识问题,它只是一个领导者选举算法,核心目标是选出一个节点作为协调者,而非让集群中的所有节点对某个值达成一致。也有脑裂问题。
bully(欺负)算法。一般约定选编号最大的那个。也就是大的欺负小的。
进程P发现协调者没有相应,就发起选举,向所有编号比自己大的进程发election消息。没人回答P就获胜变为协调者。如果有编号更大的进程回了OK,P的任务就结束了,由那个进程接手,继续向比它更大的进程发起选举。最后获胜的进程和所有进程发coordinator消息,宣布自己上任。
一致性从强到弱分别为
- 严格一致性:任何读,都读取到绝对时间上最近一次写的结果,把读写看作在指定时间瞬时发生,写立即对所有进程可见。
| 时间 | 事件 |
|---|---|
| 10 ms | A 发起 write(x=1) |
| 12 ms | B 发起 read(x) |
| 15 ms | B 收到 0 |
| 20 ms | A 收到写成功 |
| 21 ms | C 发起 read(x) |
所以,线性一致性中的“最新”,并不是“谁最后发出了写请求”。它要求已经完成的写,不能被随后开始的读漏掉;并发读写则需要存在一个合法的统一顺序。
因为请求发出、到达 Leader、复制到其他节点,都需要时间。在上例的 10 ms,A 刚发出写请求,其他节点可能还没有收到任何消息,不可能立刻知道 x 已经变成了 1。这种“按请求发生的绝对时刻立即全局可见”的要求,是实际网络通信无法满足的理想化模型;换成其他复制协议也一样。单靠更精确的时钟并不能消除消息传播时间。
基本上只有单机单线程才能做到全局一致性。
- 线性一致性:所有操作像是按某个全局顺序依次执行,且顺序不违反真实时间的先后。
- 顺序一致性和线性一致性都是并发编程中用于定义多线程/多节点操作正确性的强一致性模型,但线性一致性比顺序一致性更严格。两者核心区别在于:线性一致性要求尊重真实的物理时间(real-time)顺序,而顺序一致性只要求存在一个全局合法的逻辑顺序,不关心真实时间上的先后。
假设有两个线程:线程1写入 x=1 后,线程2写入 x=2。
raft保证的就是顺序一致性。
如果系统是线性一致的,且真实时间上 x=1 的写操作在 x=2 之前完成,那么之后任何线程读取 x,都必须读到 2。如果读到了 1,就违反了线性一致性。
如果系统是顺序一致的,只要所有线程都同意“先 x=1,后 x=2”这个顺序,那么即使某个读操作在真实时间上发生在 x=2 之后,它读到 1 也可能是合法的(只要这个读操作在程序顺序上被安排在了 x=2 之前)。
顺序一致性会出现这种情况
- A 写入
x=1,收到成功响应。 - A 告诉 B:“我写成功了。”
- B 读取
x,返回0。
- 因果一致性:有因果关系的写,所有进程必须按相同的顺序看到,并发的写:不同进程可以看到不同的顺序。
因果关系通常通过happens-before(先发生于)关系来定义。比如俩条不同的帖子,不同用户先看到哪一条都是可以的。但是帖子的评论必须比帖子后面才出现。
- 最终一致性:如果很长时间没有更新,副本最终会变得一致。DNS就是这种情况。实现简单性能好。代价是可能读到旧数据。
考虑有俩次因果关系的修改
// 节点 A
set.add("a"); // 完成
// 节点 B
set.contains("a"); // 返回 true
set.add("b"); // 完成
// 此后,节点 C 独立发起读取
set.readAll(); // 可能| 一致性 | C 可能读到什么 | 核心要求 |
|---|---|---|
| 线性一致性 | 只能是 {a,b} | 全局操作顺序必须符合真实时间先后 |
| 顺序一致性 | {}、{a}、{a,b} | 所有操作能排成一个统一顺序,且保留每个节点自己的程序顺序 |
| 因果一致性 | {}、{a}、{a,b} | 有因果依赖的修改必须按依赖关系可见 |
| 最终一致性 | 暂时可以是 {}、{a}、{b}、{a,b} | 停止修改并持续同步后,各副本最终收敛 |
客户端一致性
单调读: 一个进程读到了x的某个值,那么以后再读x,读到的只能是一个值或者更新的值.不会越比越旧.比如在北京看到了10个邮件,上海不能只是8个.
单调写:一个进程对x的写操作,必须在它后续的写操作之前完成.也就是同一个客户的写,必须要做每个副本上按顺序执行。比如打补丁,第二个补丁一定要在第一个补丁之上。
读写一致性:一个进程写完X之后,后面的读取,一定要能读到这个X。
写读一致性:一个进程读了X之后再写,这次写,一定作用在它读到的那个值,或者更新的值上。比如恢复帖子,必须出现在原帖之后。
我们可以通过读集合与写集合实现。每个操作有全局唯一标识。访问副本之前先检查这个副本是不是包含了集合里的那些写操作。没有就先同步或者换一个副本。
容错
