P2P 与分布式存储 / 系统课时

读写仲裁如何保证副本集合相交

读写仲裁如何保证副本集合相交

在三副本存储中,写入只得到两个节点确认,随后再向两个节点读取,究竟能否看到新值?这里用 N、R、W 算出法定集合的最小交集,结合三节点算例与可运行的穷举程序验证条件,并辨认集合相交与线性一致性之间的差距。

学习目标

  • 区分副本总数、读确认数和写确认数,以及一次操作成功的含义。
  • 计算读写与写写集合的最小交集,判断参数组合是否满足仲裁条件。
  • 解释为什么读写集合相交后,系统仍可能返回旧值。

明确 N、R、W 的确认边界

N 是同一对象固定副本集合的成员数;W 是一次写入成功前至少确认该版本的不同副本数;R 是一次读取需要收齐并处理的不同副本响应数。三者均为整数,且满足 1≤R,W≤N1\le R,W\le N。

例如 A、B、C 保存同一对象,采用 N=3、W=2。写入 x=1 时,A 和 B 成功确认后即可向客户端返回,C 仍可能存有 x=0。确认必须来自不同成员;仅发送请求、连上节点或收到超时重试的重复应答,都不能重复计数。

计算读写和写写的相交条件

读集合有 R 个成员,成功写集合有 W 个成员,二者都选自同一个 N 元全集。根据容斥关系,读写最小交集为 max⁡(0,R+W−N)\max(0,R+W-N)。因此,要保证任意成功写集合与任意读集合相交,必须满足 R+W>NR+W>N。

同理,两次写操作各取得 W 个确认,最小交集是 max⁡(0,2W−N)\max(0,2W-N);若要求任意两个写集合相交,还需满足 2W>N2W>N。前者是读写交集条件,后者是写写交集条件,不能互相替代。

以 N=3、R=2、W=2 为例,写集可以是 {A,B},读集可以是 {B,C},共同成员 B 至少有一个。改为 R=1、W=2 后,读取可以只访问 C,与写集 {A,B} 完全不相交。

三副本读写仲裁集合的相交与不相交对比

枚举全部法定集合验证公式

下面的 Python 3.9+ 程序枚举所有读集合及写集合,计算最坏情况下的交集大小。它验证的是固定成员集合的数学性质,不模拟网络延迟、崩溃或版本选择。

python
from itertools import combinations

def min_overlap(n: int, r: int, w: int) -> tuple[int, int]:
    nodes = range(n)
    reads = list(combinations(nodes, r))
    writes = list(combinations(nodes, w))
    # 组合内均为不同成员,同一副本不会重复计数。
    # 分别寻找读写、写写集合的最小交集。
    rw = min(len(set(a) & set(b)) for a in reads for b in writes)
    ww = min(len(set(a) & set(b)) for a in writes for b in writes)
    return rw, ww

for n, r, w in [(3, 2, 2), (3, 1, 2), (5, 3, 3)]:
    rw, ww = min_overlap(n, r, w)
    print(f"N={n}, R={r}, W={w}: 读写最小交集={rw}, 写写最小交集={ww}")

预期输出:

text
N=3, R=2, W=2: 读写最小交集=1, 写写最小交集=1
N=3, R=1, W=2: 读写最小交集=0, 写写最小交集=1
N=5, R=3, W=3: 读写最小交集=1, 写写最小交集=1

输出中的 1 表示任何合法集合组合都至少共享一个副本,不表示所有副本的数据版本相同,也不表示该副本的值必然被读取逻辑选中。

相交为什么不能直接推出线性一致性

继续使用 N=3、R=2、W=2。假设 x=1 已在 A、B 写入并成功返回,C 仍是 x=0。接着读取 B、C,确实与写集合相交,但如果程序采用“最后返回者的值”而选中 C,就会把已完成写入之前的旧值 0 返回给客户端。

写入成功后读取到旧值的时序反例

线性一致性要求已完成写入之后开始的读取看到该写入或时间上更晚的值,并且并发操作可以形成尊重真实时间顺序的原子历史。为达到这一点,还需可靠的版本排序、对并发与未完成写入的处理,以及保证读取结果不倒退的协议;例如具备正确读取机制的共识复制,或使用版本标签和读回写的原子寄存器算法。

根据失联预算选参数并检查前提

如果同一对象的成员集合固定,读取至少要联系到 R 个副本,写入至少要联系到 W 个副本。单次读、写操作最多允许的不可达成员数分别为 N-R 和 N-W;这些是节点数门槛,不保证在任意网络分区下都能继续服务。

N/R/W 读最多容忍失联 写最多容忍失联 集合性质
3/2/2 1 1 读写、写写均必相交
3/1/3 2 0 读写、写写均必相交
3/3/1 0 2 读写必相交,写写可不相交
3/1/2 2 1 读写可不相交,写写必相交

实际落地还要核对确认是否代表对应版本已被可靠保存、读写是否针对同一代副本成员列表,以及是否启用了允许临时替补节点应答的松散仲裁(sloppy quorum)。后两种情况可能使纸面上的 R+W>N 不再意味着实际应答节点相交。仲裁参数给出集合边界,版本与提交协议决定对外可承诺的一致性。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

读写仲裁如何保证副本集合相交

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通