Distributed System 5: Bayou Algorithm

分布式一致性

怎么在弱网情况下保证事件一致性，弱网指的是，只能时不时连接一下

Bayou算法

Bayou 是 1990 年代中期由 Xerox PARC 提出的一个早期分布式协作数据库系统（由 Terry、Demers、Pajankar 等人设计），它是后来 eventual consistency 和 CRDT 等思想的先驱之一。
它最初是为了移动设备和断网协作编辑场景设计的——在当时笔记本、PDA 之间网络很不稳定，但用户仍希望多个节点能共享、更新同一份数据。

Bayou 的目标是：

在没有中心协调者、网络不可靠甚至分区的情况下，让每个副本都可以独立地读写数据，并最终达成一致。

它实现的是一种 弱一致性 / 最终一致性（eventual consistency） 模型，通过「乐观复制 + update 日志传播 + 应用级冲突解决」来实现。

Bayou 是分布式系统史上非常有启发意义的项目：

• 它在 1995 年就探索了离线协作 + 最终一致性 + 冲突解决函数；
• 其思想影响了后来的 Amazon Dynamo、CouchDB、Riak、CRDT、Conflict-free Replicated Datatypes 等；
• 可以认为是「从强一致性数据库到现代 NoSQL 的过渡性原型」。

Intelligence that can identify and resolve conflicts

• More like users’ updates: read database, think, change request to eliminate conflict
• Must ensure all nodes resolve conflicts in the same way to keep replicas consistent

开会冲突：

节点X会走A，节点Y会走B

解决冲突的idea：全局日志文件

大家只要按照全局日志文件执行就可以了（github）

全局日志 example

马上更新！

idea：所有的一致性是临时的一致性，只有联网了，才能最终同步

⚙️ 系统机制

1. 每个节点都是可读写副本

所有副本都维护一份完整的数据库拷贝。
每个副本都可以本地执行 write 操作，即使当前离线。更新会被记录成一条 update log entry。

2. Update 日志的传播

节点恢复网络连接后，会将自己的更新日志与其他副本进行 anti-entropy（反熵同步），即：

• 按时间戳或版本号比较日志；

• 互相发送缺失的更新；

• 应用新的更新到本地数据库。

3. Tentative 和 Committed 更新

Bayou 的一个关键特性是区分：

• Tentative（暂定）更新：在本地执行但尚未被所有副本确认；

• Committed（已提交）更新：通过某种全局顺序（由“primary replica”决定）确定执行顺序后，才算最终确认。

每个副本都执行相同顺序的 committed 更新，因此最终收敛。

4. Conflict Resolution（冲突解决）

由于更新可能并发、乱序，Bayou 让应用层提供冲突解决函数（conflict resolution procedure）：

• 每条更新都携带一段可执行逻辑，用于检测并解决冲突；

• 例如两个用户修改相同字段时，可以合并、覆盖或提示用户手动解决。