分布式基础概念

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$。

image.png

比如偏移每秒是十万分之一,$\delta$ 为1毫秒(俩台机器差距不超过1毫秒),就得每50秒同步一次。

同步算法:cristian算法,需要建设来回的延时相等。

image.png

这里依赖时间不能倒流,客户端的时钟快了不能直接往回拨。否则会出现后发生的事情时间戳反而更小。应该直接让时钟走慢一点。

另一种是berkeley算法。它不要求有准确的时间源。目标只是让大家一致。时间守护进程主动询问每台机器的时间。算出平均值,再告诉每台机器应该调整多少。

image.png

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

互联网上实际使用的是NTP算法。

image.png

这里T2是收到请求的时间,T3是发回请求的时间。它们是为了算出服务器处理请求花了多少时间。从而从总时间里剥离出来,求出真实的网络往返延迟。

互斥

分布式算法Ricart-Agrawala。把时间戳,进程号的请求发给所有其他线程,等所有人回OK。收到请求的分三种情况。

  1. 自己不想进:直接回 OK。
  2. 自己正在临界区:不回复,把请求放入队列,等自己退出临界区后再回 OK。
  3. 自己也想进(但还没进):比较双方请求的 (时间戳, 进程号)。

    • 如果请求方更小(时间戳更早,或时间戳相同但进程号更小):立即回 OK。
    • 如果自己更小:不回 OK,把请求排队,等自己用完临界区后再补发 OK。

这个算法没有单点故障,但是变成了n个故障点:任何一个进程崩溃不回复,大家都卡住。

还有一种算法是令牌环算法,把进程排成一个逻辑环。令牌沿着环传递,拿到令牌才能进临界区。不想进就直接向下传。它不会饿死,但是令牌可能丢失。而且很难判断令牌是丢了还是有人用的太久。

一致性

一致性定义

Bully 算法本身并不解决共识问题,它只是一个领导者选举算法,核心目标是选出一个节点作为协调者,而非让集群中的所有节点对某个值达成一致。也有脑裂问题。

bully(欺负)算法。一般约定选编号最大的那个。也就是大的欺负小的。

进程P发现协调者没有相应,就发起选举,向所有编号比自己大的进程发election消息。没人回答P就获胜变为协调者。如果有编号更大的进程回了OK,P的任务就结束了,由那个进程接手,继续向比它更大的进程发起选举。最后获胜的进程和所有进程发coordinator消息,宣布自己上任。

一致性从强到弱分别为

  • 严格一致性:任何读,都读取到绝对时间上最近一次写的结果,把读写看作在指定时间瞬时发生,写立即对所有进程可见。
时间事件
10 msA 发起 write(x=1)
12 msB 发起 read(x)
15 msB 收到 0
20 msA 收到写成功
21 msC 发起 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 之前)。

顺序一致性会出现这种情况

  1. A 写入 x=1,收到成功响应。
  2. A 告诉 B:“我写成功了。”
  3. 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之后再写,这次写,一定作用在它读到的那个值,或者更新的值上。比如恢复帖子,必须出现在原帖之后。

我们可以通过读集合与写集合实现。每个操作有全局唯一标识。访问副本之前先检查这个副本是不是包含了集合里的那些写操作。没有就先同步或者换一个副本。

容错

image.png

Last modification:November 17, 2026
如果觉得我的文章对你有用,请随意赞赏