简单介绍

最终一致性位于一致性谱系的末端, 比线性一致性(Linearizability), 顺序一致性和因果一致性都要弱;
如果对某一数据项不再有新的更新写入, 那么在经过一段时间后, 所有未来的读取操作都将反映最新的写入结果

  1. 没有时间限制: 系统对收敛到一致状态所需的时间没有界限,;这个时间长短取决于通信模式的可用性(例如, 如果节点长期不通信, 收敛时间就会很长);
  2. 保证最终顺序: EC 仍然要求更新最终以相同的顺序应用到所有副本上,;这通常是通过逻辑时钟等机制来实现的, 允许更新先作为临时更新本地应用, 然后在同步时根据逻辑时间戳进行回滚和重放,;

Bayou 模型 (SOSP 1995)

  • 没有中心化存储: 所有的节点都被视为客户端,;
  • 始终接受更新: 客户端总是接受用户发出的更新操作, 这保证了高可用性和活性;
  • 日志记录: 所有更新都会被记录在本地日志中;
  • 点对点同步: 客户端之间会定期进行 成对(pair-wise) 的更新交换;
  • 临时更新: 更新通常是暂时的(tentative), 可以解决它们之间的冲突;

举例说明最终一致性

假设有一个房间日程安排应用程序(Room scheduler app running on smartphones)

  • 应用场景: 该应用运行在智能手机上, 每个日程条目都有时间(time)和地点(location);
  • 目标: 最终, 所有用户都将知道并同意每个条目;
  • 本地副本: 每个手机上都存有一个本地日程副本, 没有主节点或中心化副本, 系统的状态是所有手机上的集体状态;
  • 间歇性连接: 手机的连接是间歇性的, 可能因为 Wi-Fi 不可用, 蜂窝数据昂贵或蓝牙范围有限等原因;

在这个高可用, 低连接的场景下, Bayou 允许用户继续添加日程条目(更新), 这些条目会在手机连接恢复后, 通过同步最终达成一致

Format Updates and Conflict Resolution

当用户在本地日历副本中添加条目时, 手机会定期成对交换更新;

  • 基本思路: 用户将条目添加到本地日历副本, 手机定期成对交换更新;
  • 冲突信息: 一个更新必须包含足够的信息来解决冲突;
  • 理想情况: 冲突最好是自动解决的;

当检测到冲突时, 系统需要一个 合并过程(merge procedure) 来解决冲突的更新;

  • 解决机制: 合并过程是一个函数, 它根据每个冲突更新的状态来解决它们;
  • 实现方式: 这通常相当于 回滚(rolling back)并重新应用(re-applying) 更新;
    • 回滚是实现 EC 的最核心机制, 类似的思路可以参考 Thomas Anderson 的 SoftUpdate 论文, 里面也是通过软件层回滚来绕开 disk 多次写入的问题;

接着说上面的 Example

在最终一致性系统中, 更新的应用顺序最终必须相同, 否则副本会产生分歧;

  • 冲突示例: 假设有两个请求 A 和 B, 都试图在同一时间(10A)预订同一个房间(4901), 但都提供了备选方案(11A),;
    • A 抢先在本地安排 M1 在 10A, B 抢先在本地安排 M2 在 10A;
    • 当节点 X 与 A 同步, Y 与 B 同步后, X 上 M1 在 10A, Y 上 M2 在 10A;
    • 随后, X 与 B 同步, Y 与 A 同步;
      ▪ X: M1 在 10A, M2 安排在 11A(因为 10A 已被 M1 占用);
      ▪ Y: M2 在 10A, M1 安排在 11A(因为 10A 已被 M2 占用);
    • 结果: 两个副本对 M1 和 M2 的 最终安排时间不同(一个 M1 10A/M2 11A, 另一个 M2 10A/M1 11A), 造成了冲突;
  • 问题所在: 这个例子中的顺序是"先见者先应用"(first-seen, first-applied), 它导致了副本以不同的顺序应用更新, 从而产生冲突;
  • 解决方案: 为了保证最终一致性, 更新必须 最终以相同的顺序应用 到所有副本上;实现这一目标的关键工具是 逻辑时钟(Logical Clock);

逻辑时钟 (Logical Clocks)

我们在很早的 Lamport Clock 的时候就提到过逻辑时钟; LC 保证保留因果关系 (causality), 即捕获"外部世界"的预期, 并允许系统任意排序所有其他事件, 用 FV 的方法可以形式化地表示如下:

  • Happens-Before ( →\rightarrow ) 规则:
    • 进程 P 中较早的事件 →\rightarrow 较晚的事件;
    • P 发出的发送事件 →\rightarrow Q 中对应的接收事件;
  • 时间戳: 每个事件(更新)都被关联一个时间戳, 该时间戳必须是其紧前事件时间戳的最大值加 1;
  • 全局排序: 每个更新都关联一个全局有序的时间戳: (本地时间戳 T, 始发节点 ID),;
    • 如果本地时间戳 不同, 它们决定了顺序;
    • 如果时间戳 相同, 则通过始发节点 ID 来 break tie;

如何用 LC 解决这里的一致性问题

使用逻辑时钟可以确保所有副本最终以相同的顺序应用更新, 即使它们在不同时间收到更新:

  • 重新应用示例: 回到之前的冲突示例, 如果更新 M1 的时间戳为 ⟨770,A⟩, M2 的时间戳为 ⟨701,B⟩;
    • 由于 ⟨701,B⟩ 在全局排序上先于 ⟨770,A⟩;
    • 当节点 X(本地已应用 ⟨770,A⟩)学习到 ⟨701,B⟩ 时, 它发现 M2 应该先应用;
    • X 必须 撤销 M1 的临时更新, 应用 M2(在 10A), 然后重新应用 M1(此时 M1 由于冲突, 会应用到备选的 11A),;
    • 最终, 所有节点都会以 ⟨701,B⟩ →\rightarrow ⟨770,A⟩ 的顺序处理更新, 从而达成一致的结果(M2 10A, M1 11A);
  • 判断标准: 当系统知道没有比 T 更早的更新存在时, 该更新就成为最终更新;
    • 然而, 这种确定性可能需要很长时间, 因为它取决于所有节点(特别是那些连接不稳定的节点)的通信模式;
    • 为了解决这个问题, 可以引入一个 主副本(Primary) 来确定最终顺序, 并使 用向量时钟(Vector Clocks) 来提供更大的灵活性;

应用的小问题

这时候 Noble 想要问: “这样的逻辑时钟有没有可能会出现两个线程导致的崩溃程序可能? 比如一个节点创建 activity A 在另一个线程 delete A 之后?” 不过好消息是, 这个删除线程要能知道有 A 就需要等待 A 被创建, 这里的因果关系约束要求第二个线程一定要在 A 创建之后才能发出请求, 删除必然晚于 A 的创建

Log 的处理逻辑

Bayou 这类最终一致性系统中的更新日志具有以下关键特性:

  • 日志的构成
    • 本地副本 的所有更新(all updates from the local replica);
    • 一些其他的更新, 这些是通过同步 从其他节点学到的;
  • 日志的传播路径, 通过同步学到的更新包括:
    • 那些直接与本地副本同步过的副本 R 所产生的更新;
    • 那些与 R 交流过的副本 S 所产生的更新;
    • 那些与 S 交流过的副本 T 所产生的更新, 依此类推(间接传播);
  • 一个日志是它 所知的所有副本记录的交错(interleaving of records), 这些记录是直接或间接从所有已知副本那里学到的;
  • Prefix Property:
    • 对于日志中的任何一个副本 R, 本地副本所知的 R 的更新, 必须是 R 本地更新日志的一个前缀(prefix);
    • 本地副本可能不知道 R **“较晚”(“later”)**的更新, 但它知道 R **所有"较早"(“earlier”)**的更新;
  • 为了实现最终一致性, 日志必须满足以下隐含要求:
    • 存储更新: 更新必须被存储在日志中;
    • 本地立即应用: 更新一旦已知, 就必须尽快在本地应用;
    • 可回滚和重应用: 日志中的每个更新都必须能够被回滚(rolled back)重新应用(re-applied);
    • 冲突解决: 必须有一个**合并过程(merge procedure)**来解决冲突的更新;
    • 日志截断/垃圾回收: 日志只能被截断(垃圾回收)到最早的临时更新之前(即在更新被确定为"最终"之前, 它不能被清除);

前缀的特性 Prefix

由于每个节点可以看作是多个已经交流过的节点的 log 的合并结果 (Interleaving of Records), 那么我们如何判断两个节点之间发生操作的早晚?

前缀要求: 对于日志中的任何一个副本 R, 本地副本 A 所知道的 R 的更新集, 必须是 R 本地更新日志的一个前缀; 这意味着, 一旦一个节点 A 了解了副本 R 的某个更新, 它也必须知道 R 在该更新之前发布的所有更新; 正是基于日志的前缀特性, Bayou 系统能够高效地进行同步, 避免交换整个庞大的日志; 这种机制常被称为 版本向量(Version Vector)

Failed Replicas

好消息是在 eventual consistency 的语境下, failed replica 并不会造成整个系统的阻塞, 但是问题是可能会导致一个操作不被认为是 finalized, 从而无法被垃圾回收掉, 最终导致日志无限增长;

Primary 解决 failure node 机制

为了解决同步时间过长和日志截断被阻塞的问题, 可以引入一个主副本(Primary);

  1. 主副本的角色和特性
  • 定义: 主副本是 仅凭约定(by convention) 确立的, 而非基于共识协议;
  • 作用: 它负责对更新的顺序做出最终决定, 并通知其他副本哪些更新已经最终确定(finalized);
  • 理想属性: 主副本应该是被管理(managed)较高(但不必完美)的可用性和良好的网络连接;
  • 效果: 主副本成为通信的枢纽(nexus of communication), 这将缩短收敛时间;
  1. 提交更新的过程 (Committing Updates)
    在每个副本上, 数据分为两部分: 稳定状态(stable state), 临时更新日志(log of tentative updates);
  • 主副本分配顺序号: 在同步时, 主副本会为那些 “safe” 的更新分配一个序列号(sequence number);
  • 客户端应用: 客户端会将这些"安全"的更新应用到它们的稳定状态中, 并随后 剪除(prune) 日志的相应部分;

并发操作的抉择

pb 在决定更新的最终顺序时, 必须尊重因果关系(causality), 也就是通过 Lamport 时钟来实现; 但是对于没有 causality 的事情, primary 可以任意排序两个具有相同时间戳的事件, 例如 ⟨5,A⟩ 和 ⟨5,D⟩(因为它们是并发的);

  • 过于保守: 然而, Lamport 时钟存在一个问题: 如果两个事件具有因果关系, 它们一定是有序的; 但如果两个事件是有序的, 它们不一定具有因果关系;这种保守性使得 Lamport 时钟对那些实际上是并发的事件进行了不必要的排序, 从而限制了主副本的排序灵活性;

为了解决这个问题, 可以使用 向量时钟(Vector Clocks) 来捕获更精细的因果关系;

向量时钟 (Vector Clocks)

向量时钟机制是对 Lamport 时钟的改进, 它能够精确地捕捉因果关系, 从而使主副本能够对更多的事件进行任意排序;

向量时钟的结构和语义

每个 event (ee) 都有一个 vec V(e)=[c1,c2,⋯ ,cn]V(e) = [c_1, c_2, \cdots, c_n] 来标记, 其中 n 是 replica 的数量;
向量中的每一个元素 cic_i 表示 replica ii 在 event ee 发生时的本地计数器值;
初始状态下所以有 replica 的向量时钟都被初始化为零向量 [0,0,⋯ ,0][0, 0, \cdots, 0];

更新规则

  1. 本地事件: 每次更新直接给状态 + 1
  2. 消息接受: 如果是外来的事件, 就需要对收到的 vector [d1,d2,⋯ ,dn][d_1, d_2, \cdots, d_n] 这样的消息进行本地合并:
    • 取最大值: 对于每个元素 ii, 取本地向量和收到的向量的最大值: ci=max(ci,di)c_i = max(c_i, d_i)
    • 本地递增: 然后对本地 replica 的计数器 + 1 (参考 lc 的更近机制本地收到消息可以 + 1 版本)

VC 语义

  • Happens-Before: 如果 a 发生在 b 前面 (V(a) < V(b)), 则 a →\rightarrow b; 这里的小于(<) 是指向量的每个元素都小于等于另一个向量的对应元素, 并且至少有一个元素严格小于;
  • 并发(Concurrent): 如果 V(a) 和 V(b) 之间没有包含关系, 则 a 和 b 是并发的 (a || b); 这里的没有包含关系是指存在某些元素 cic_i 满足 ci>dic_i > d_i, 也存在某些元素 cjc_j 满足 cj<djc_j < d_j;

细在哪?

VC 相当于对每个 replica 维护了一个 Lamport 时钟, 这样就可以更精细地捕捉因果关系; 而 LC 是全局维护了一个共同的时钟, 并且会因此对很多并不是 causality 的事件也进行了不必要的排序

合并的 Re-Ordering

primary 的自由度: 因为这些事件是并发的(即它们之间没有因果链连接), 所以主副本可以 任意排序(arbitrarily order) p自由排序这两个节点更新流, 主要是为了全局统一的顺序

Amazon S3 Cloud Storage Service

GIT: 真正的 ec 一致性系统

始终可用 (GIT Is Always Available)

  • 本地副本: 用户可以克隆一个本地副本, 然后可以随时在本地进行操作;
  • 提交成功: 所有的提交 (commits) 总能成功, 并且(在不干预的情况下)所有提交都会被永久记录在日志中;
  • 同步机制: Git 允许在任意两对副本之间进行同步;
  • 中央存储约定: 将 GitHub 用作"中央"存储是出于约定俗成, 而非技术强制, 虽然这样做可以使生活变得更简单;

Git 对可用性的保证是其最终一致性模型的直接体现;

Git 的同步与合并 (GIT Synchronization)

Git 在同步(例如拉取或合并)时, 需要处理潜在的并发更新:

  • Tracing Causality: Git 合并 (merge) 操作会追踪完整的历史因果关系(complete history);
  • 并发合并: 对于 不并发(not concurrent)的更新, 它们会被直接应用;而对于并发(concurrent) 的更新, Git 会根据文件类型进行合并处理,;
    • 非文本文件: 如果文件不是文本文件, 则整个文件会被标记为冲突(conflict), 需要手动干预来解决,;
    • 文本文件: 对于文本文件, Git 使用逐行(line-by-line)三方差异比较(three-way diff);
      • 不重叠(non-overlapping)的更改会被应用;
      • 重叠(overlapping)的更改则被保留下来, 等待手动解决(manual resolution),;

Git 的一致性(Syntactic vs. Semantic)

Git 提供的一致性是句法一致性(syntactic consistency), 但不总是语义一致性(semantic consistency);

  • 句法一致性(Syntax): 关注形式, 结构, 语法等; Git 能够确保 文件结构和格式正确地合并;
  • 语义一致性(Semantics): 关注意义; Git 无法理解代码的真正含义和逻辑目的;

潜在问题: 如果发生的更改在源文件中处于不同位置, 但在逻辑上是彼此不一致的, Git 仍然会愉快地将它们合并起来;

  • 不太可能造成大问题的情况: 例如, 名称更改通常会被编译器捕获;
  • 可能造成严重后果的情况: 例如, 有人给一个函数添加了一个前提条件(precondition), 而现有调用者符合这个条件, 但新编辑的调用者却不符合; Git 会合并这些更改, 但代码的逻辑一致性被破坏了;