Demers 1987：谣言与反熵怎样维护副本，不是 Dynamo

破除误解#

误解二：流行病算法就是广播，或者就是“随便找一台机器把更新推过去”。 论文把三种策略分开写。直接邮寄从注入点向已知的全体站点发信，及时，但不完全可靠：邮件会因队列溢出或目的地长期不可达而丢，注入点对站点集合的知识也可能不完整。反熵是简单流行病：站点相对于一条更新永远只处在易感或感染，定期与随机同伴对账，直到全体一致；它可靠，但要检查数据库内容，不能跑得太勤。谣言传播是复杂流行病：新更新变成“热谣言”，站点在感染态时与同伴分享，满足停止规则后进入移除——保留更新、不再主动传播。谣言周期可以更密，因为每步消耗更少；代价是有非零概率走不到全体。把三者兑成一句“Gossip”，会把残留、流量与时延三张账单读丢。

误解三：推、拉、推—拉只是实现口味，选哪个都一样。 对反熵，论文用简单确定性模型比较尾巴。设 $p_i$ 为第 $i$ 轮后仍易感的概率。拉：站点仍易感，当且仅当上一轮易感且本轮抽到的同伴也易感，于是 $p$ 小时迅速平方下去。推：站点仍易感，当且仅当上一轮易感且没有任何感染者抽中它；当 $p$ 已经很小、站点很多时，每轮几乎只按 $1-1/n$ 的幂慢慢咬。因此，当反熵被当成直接邮寄或谣言的备份、只剩少数易感者时，拉或推—拉远好于推。对谣言，推在库近乎静止时几乎不再制造空转；拉在更新频繁时更容易碰到非空谣言表，但库静时会持续发出无果请求。这些是纸上的协议类对比，不是一份要人去拧间隔的集群菜谱。

误解四：删除就是少复制一项，或者死亡证书是运维手册里的垃圾回收脚本。 用反熵或谣言维护副本时，本地拿掉一项，缺席并不会像更新那样传开。相反，别处尚未删除的旧副本会被送回来，条目被“复活”。论文用带时间戳的死亡证书代替被删项；旧副本遇见更新的证书则被取消。证书自己也不能永占空间。等全体都收到再删，要靠基于分布式快照的判定，而几百站点的网上几乎总有机器宕数小时甚至数天。他们讨论过固定保留期（文中举例三十天）以及休眠证书。这些句子是发表出来的问题与装置，不是教人如何在活系统上制造复活或清场。

直接邮寄、反熵与谣言：纸上真正分开的三类#

装置从一条极松的一致性目标开始。每个站点保存一份带时间戳的部分函数。客户在任一站点注入更新，打上希望近似格林尼治时间的全局唯一时间戳；较大时间戳覆盖较小者。全体副本只有在更新活动停止、系统静止之后才能完全一致；更新率合理时，任一站点上的大多数信息是新的。葡萄藤邮件与名字系统已经表明这种放松有用。他们明确不走“一份副本可串行化”的事务路径，见 数据库与事务。随机化让他们不能声称“收敛时间正比于网络直径”；能声称的是：若不再有新更新，尚未收敛的概率随时间指数下降。

直接邮寄从注入点列出已知站点，把更新投入邮寄。期望近乎可靠：发送方不等待，队列落在稳定存储上，崩溃不丢队列。它仍会失败。流量按站点数乘站点间平均距离计。葡萄藤把失败补救交给管理员；几十台机器时尚可，放大之后不够。

反熵被葡萄藤设计者提出、却未在葡萄藤里实现，Clearinghouse 几乎原样采用。每个站点定期选一个同伴，双方合作执行 ResolveDifference。推：只把更新的一侧写到落后一侧。拉：只把落后一侧改成更新一侧。推—拉：谁新听谁。简单流行病的经典结论是：从单一感染者出发，期望时间与种群对数成正比。推的精细式子，论文引皮泰尔（Boris Pittel）对谣言传播的分析，写成 $\log_2 n+\ln n+O(1)$。安慰在于：即使邮寄只送到一台机器，反熵也会最终铺开。常态下他们期望反熵只收拾少数漏网者。

整库对账很贵。近乎一致时，大部分比较是浪费。朴素改进是先交换校验和，不一致再比全文；网络一大，一条更新走完全体的时间相对两次更新间隔不再短，校验和会经常吵。更精细的办法是维护近更新表，先对近期项对账再比校验和；时间窗若短于实际传播，会退化得比不用校验和还吵。倒序按时间戳交换直到校验和一致（peel back）流量近乎理想，代价是多一份倒排。

谣言传播把站点分成易感、感染、移除。分享一步不必扫整库：发送方持有感染更新列表，接收方尝试插入，把真正新的加入自己的感染表。难处只在何时把一项从感染表拿掉。文献里常被叫作谣言扩散的那条：听到的人变成感染并继续分享；当一次分享发现对方已经知道，发送方以概率 $1/k$ 失去兴趣、进入移除。确定性模型显示残留易感份额随 $k$ 指数下降：$k=1$ 时约两成听不到，$k=2$ 时约百分之六。变体按是否需要回执分成反馈与盲目，按停止规则分成硬币与计数器。它们大致共享流量—残留关系 $(1-1/n)^{nm}$；仿真表明计数器比反馈更能改善时延。一千站点、反馈加计数器时，$k=1$ 残留约 $0.18$、$k=5$ 约 $0.0012$；盲目加硬币在 $k=1$ 时残留可高到 $0.96$。

把复杂流行病与反熵叠起来，是论文给出的工程句式。复杂流行病可以极快、极省地铺开，但仍有非零概率在仍有易感者时感染者归零，系统停在“有人知道、有人不知道”的稳定态。偶尔跑反熵作备份，才能以概率一保证每条更新最终到达或被更新的值取代。若反熵发现缺失后用直接邮寄再分发，初传若大约送到一半，下一轮可变成 $O(n^2)$ 封信；Clearinghouse 曾实现再分发，后因代价关掉。换成谣言再点燃，已知面已经很大时热谣言会很快熄灭。这是协议类的比较，不是一份要人去制造半网分区的实验步骤。

空间分布是第三张图。均匀随机选同伴会在链路上堆出相当流量。他们在 Xerox 公司网的真实拓扑上分析并仿真：让选择偏向近处服务器，反熵与谣言都能收敛得几乎与均匀一样快，同时降低每条链路的平均与峰值流量。装上公司网之后的那份反熵，带来了可感知的性能改善。论文同时声明：大规模复制本身昂贵，能靠层次分解或缓存避开就该避开。

GFS 用单主记住块在哪，客户端先问主再跟 chunkserver 说话。Chord 与 Kademlia 把键映射到负责节点，本页假定副本集合已知，要对齐的是已写入的值。CRDT 问合并是否上确界；本页的时间戳覆盖是“后来者赢”，不是结合交换幂等的数据类型。分布式系统 总览里已经出现最终一致与流言这些词；本页停在 1987 年印出的三类随机维护，以及删除为什么必须变成一种更新。

死亡证书要取消的是复活，不是一项本地删除#

删除比插入难，因为缺席不是一种会自己走的值。死亡证书携带时间戳，传播时遇见更旧的数据项就把它取消。证书留得够久，旧副本会被收干净。然后必须决定证书自己何时消失，否则它们最终占满站点。等快照证明全体收到，在数百站点、且总有人宕机数小时到数天的经验里，协议完不成。固定保留期省事，但阈值之后仍可能复活。休眠证书把阈值在空间上拉长：创建时随机写下若干保留站点；在第一阈值内全体保留；过了之后多数丢掉，名单上的站点改留休眠副本；再过第二阈值，休眠副本也丢。若旧值撞上休眠副本，证书被唤醒再走一轮。论文把唤醒比作免疫反应，唤醒的证书像抗体。这是类比，不是一份生物学操作。

休眠副本会因机器永久失效而丢失；持有某份休眠副本的全部服务器都失效的概率写成 $2^{-r}$。同等空间下可维护的历史有 $O(n)$ 量级改善，按他们当时的系统可从约三十天拉到数年。装置并不无限可扩：新证书走到全体的期望时间随 $n$ 增长，第一阈值若不跟着长，唤醒会越来越勤。反熵把该期望写成 $O(\log n)$，足够大的网上证书空间最终必须随对数增长。

用反熵分发时，休眠证书通常不该在对账里当普通项传播；一旦撞上过时数据项，必须激活。把证书的普通时间戳改成当前时钟是错的：网上可能存在时间戳夹在原删除与新戳之间的合法恢复写入，会被误杀。论文因此为每份证书存第二枚激活时间戳。取消数据项仍看普通时间戳；是否休眠、如何传播看激活时间戳。激活时只拨动激活戳，保留原来的删除戳。概念证据到此为止。如何在集群里列出保留站点、阈值拧到哪一天，不在本页对象里。

论文量到了什么，以及它没有量到的东西#

它量到并分析了残留、流量与两类时延。残留是感染者归零时仍易感的份额。流量先按站点间更新条数计平均 $m$，再把度量细化到链路上。$t_{\mathrm{ave}}$ 是注入到各站点收到的平均时延；$t_{\mathrm{last}}$ 是本轮流行病中最后一个收到者的时延。一千站点的仿真表把 $k$、残留、$m$ 与这两类时延写在一起。空间部分用公司网真实拓扑。现场经验是：关掉再邮寄、换上考虑空间的反熵之后，高复制域加给邮件、文件传输和名字查找的压力下降。

它证明了什么。它证明：简单流行病在经典混合模型里会感染全体，期望轮数随对数走。它证明：当反熵只收拾少数漏网者时，拉的尾巴比推干净。它证明：谣言的残留可以靠加大 $k$ 压到任意小，但不能靠谣言单独把失败概率写成零。它证明：删除必须被编码成一种会传播的值，否则旧副本会复活；休眠证书用空间换更长的历史，但第一阈值必须盖住传播时间。

它没有证明可以把这些装置当成覆盖网查找、线性一致存储或无冲突合并。它没有给出公网毫秒分位数，也没有把连接限制写成可照做的参数表。它没有讨论如何淹没、如何群发、如何写一条自我复制的程序。对象是已发表的副本维护协议类与测量，不是攻击面说明书。1989 年 1 月的帕洛阿尔托 CSL-89-1 技术报告是会议文本的扩充印本；本页仍以 1987 年 PODC 十二页为对象，不把年份提前。

跨域连接#

• 流行病学：德默斯等人明确借用贝利（N. T. J. Bailey）传染病数学里的易感、感染、移除，把反熵写成不会进入移除的简单流行病，把谣言写成会失去兴趣的复杂流行病。公共卫生里的同一套词，要描述的是已存在人群中疾病如何分布与消退；本页要设计的是更新如何走完副本。目标相反：他们乐见更新迅速、完全地“感染”全体站点。类比管的是状态划分与残留，不管病原体，也不把名字服务写成一次暴发演练。
• 传染病建模：谣言那对微分方程把新感染写成易感份额与感染份额的乘积，把失去兴趣写成与“多余分享”成比例的项。残留是感染者归零时的易感份额，不是监测曲线上的报告病例。$k$ 调的是兴趣消退的快慢，从而指数地压低听不到的人；它不是再生数 $R_0$，也不能当成干预开关。模型是条件推演：完全混合、每轮一次配对。公司网的空间偏向近邻，已经离开这组假设，要用拓扑上的仿真另说。
• 概率论：尚未收敛的概率随时间指数下降，是随机化换来的那句可证明的话，不是直径上的确定性发票。推在尾巴上接近每轮乘 $(1-1/n)$；拉在 $p$ 小时按平方收缩。谣言残留与平均每站点消息数之间，推走向 $s=e^{-m}$；拉在计数器加反馈的模型里可以走到双指数那一类更陡的尾巴。休眠证书的 $2^{-r}$ 是保留站点同时永久失效的机会。这些式子都带着混合模型与大 $n$ 近似，不能读成某次夜间维护的实测频率。
• 认识论：没有一个站点被允许声称自己看见了全体副本。直接邮寄依赖“我知道 $S$”这份可能过时的名单；名单错了，更新在注入点就已经缺地址。反熵把证据改成配对比较：我只需要知道同伴与我是否在同一时间戳上，不需要一张中心目录来宣布真相。谣言的移除是关于自身传播意愿的断言，不是关于全局已经一致的断言。死亡证书则是把“此项不存在”做成可被别人核对的公开证据——缺席本身不是证据。把本地内存里的“我已经删了”当成公共知识，正是复活事故的认识论来源。

参考文献#

• Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart & Doug Terry, "Epidemic Algorithms for Replicated Database Maintenance", Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), Vancouver, 1987, pp. 1–12. DOI: 10.1145/41840.41841. —— 本文对象：直接邮寄、反熵（推 / 拉 / 推—拉）、谣言传播，以及死亡证书。
• Alan Demers et al., "Epidemic Algorithms for Replicated Database Maintenance", Xerox PARC Technical Report CSL-89-1, January 1989. —— 会议文本的扩充印本，用以对照死亡证书与空间分布的后来叙述；不是把 1989 年提前写成 1987 年的装置。
• N. T. J. Bailey, The Mathematical Theory of Infectious Diseases and Its Applications, 2nd ed., Griffin, 1975. —— 论文所引流行病学术语与简单/复杂流行病分析的来源。
• Boris Pittel, "On Spreading a Rumor", SIAM Journal on Applied Mathematics 47(1), 1987, pp. 213–223. —— 反熵之推的期望时间式所引。
• Andrew D. Birrell, Roy Levin, Roger M. Needham & Michael D. Schroeder, "Grapevine: An Exercise in Distributed Computing", Communications of the ACM 25(4), 1982, pp. 260–274. —— 直接邮寄与反熵设想的前身现场。
• Derek C. Oppen & Yogen K. Dalal, "The Clearinghouse: A Decentralized Agent for Locating Named Objects in a Distributed Environment", ACM Transactions on Office Information Systems 1(3), 1983, pp. 230–253.

延伸阅读#

• 与 Dynamo 对读：2007 年把流言用于成员、把反熵做成 Merkle 扫尾；本页对象是 1987 年的更新传播与删除证书。
• 与 无冲突复制数据类型、Chord、Kademlia、GFS 对读：合并代数、查找装置与单主元数据各不是本页的协议类。
• Sunil K. Sarin & Nancy A. Lynch, "Discarding Obsolete Information in a Replicated Database System", IEEE Transactions on Software Engineering 13(1), 1987, pp. 39–47. —— 用分布式快照判定证书可删；论文用来对照“等全体收到”在数百站点上完不成。
• Kermack, W. O. & McKendrick, A. G., "A contribution to the mathematical theory of epidemics", Proceedings of the Royal Society A 115, 1927. —— SIR 连续模型的经典来源，用以标明贝利教科书背后的数学传统。