2021-04-16

分布式系统中的先后顺序问题 – 逻辑时钟, 原子钟和停止等待

Views: 1103 | Add Comments

分布式系统中的一致性问题, 本质就是操作的先后顺序问题. 先后顺序, 纯朴的理解就是时间的先后, 也即时钟的先后. 众所周知, 时钟受许多因素影响, 例如观察者, 时钟源(钟表, 系统时间), 时钟同步等等, 单纯依赖时钟的读数来区分先后顺序, 会造成许多的问题.

以银行转账为例子.

在一个虚拟的银行系统中, 用户直接修改离自己最近的银行的数据库, 而数据库本身会自动地将修改同步到其它地点.

中国的用户 A 在中国的数据库里修改了自己账户的余额, 扣减 100 元, 同时修改了用户 B 在中国的数据库里的余额, 加上 100 元.

接着, 用户 A 私下告诉在美国的用户 B, 说我已经给你转账了 100 元. B 直接读取美国的数据库. 如果 B 发现自己的账户增加了 100 元, 那么我们就说, 两地的数据库组成的系统, 其行为符合强一致性.

我们知道, 数据库同步有延迟, B 有可能第一次查看的时候没有发现转账. 我们如何控制 B 的行为, 保证他一定会看到这次转账呢?

方案一: 停止等待

我们根据经验, 数据库同步一般会在1s内完成, 我们让 B 等等一分钟之后再去查看. 概率上会发现, 但不是 100%.

方案二: 时钟对比

用户 B 询问 A 在什么时间点转账的. 用户 A 回答说他在 10:00 操作的. 于是, B 查看数据库的修改记录, 发现数据库的最后一条操作日志是 9:50, 于是, 他等了一会, 继续查看, 直到数据库的最后一条操作日志等于或者大于 10:00.

这个方案有点问题, 用户 A 看表的时候, 他自己的表可能不对, 比如慢了, 实际的操作时间是 10:05, 这样会造成 B 误判. B 查看发现有一条操作日志是 10:01, 但这条操作日志是别人的, 不是 A 的, 所以, 他会发现自己的账号没有增加 100 元, 因此他认为数据是不一致的.

如果用户 A 用原子时钟, 而不是廉价的手表, 表的时间就不会那么慢, 也许可以减少误会.

方案三: 逻辑时钟

数据库对每一次修改进行编号, 编号总是递增, 然后将转账编号告诉 A, A 再将转账编号告诉 B, B 就盯着编号找操作日志.

逻辑时钟有问题, 需要对操作进行编号, 要编号, 就要对操作进行排队, 也即串行化.

方案四: 原子时钟+停止等待

原子时钟比较精确, 操作日志采取原子时钟作为转账编号, B 检查编号时, 在听来的时间基础上再加上几十毫秒来覆盖误差. 例如, A 说他是 10:00 操作的, 那么 B 检查操作记录按 10:00 + 20ms 来算, 一旦符合, 转账记录肯定已经同步到位.

这就是 Google 的分布式数据库使用原子钟的原理.

总结

分布式数据库的一致性问题, 本质是操作的先后顺序问题.

Related posts:

  1. 数据通信与传输协议基础
  2. 什么是 Paxos 的日志空洞?
  3. 我所理解的分布式系统
  4. Paxos和Raft读优化 – Quorum Read 和 Read Index
  5. 分布式一致性协议-Raft和Paxos
Posted by ideawu at 2021-04-16 21:47:25

Leave a Comment