idea's blog

在单机编程时代, 每一项数据只有唯一的一份, 对数据的修改也是 in-place 的. 但是, 在并发编程领域, 包括分布式系统, 数据多版本(Multi Version, Versioning)是核心.

我们先从单机编程的内存操作出发. 对于内存的操作, 都是原地(in-place)更新的. 对象和内存空间强绑定, 当更新对象时, 是将对象的内存空间擦除然后用新数据写覆盖. 到了多线程编程时代, 就引入了锁机制, 因为擦除和写操作过程不是原子性的, 可能擦除到一半时, 就被其它线程读取了, 因此要加锁.

单机的硬盘操作, 基本也是借鉴内存操作, 也是对象和硬盘空间强绑定. 至少大部分程序员的思想是这样的, 这样比较直观. 跟内存操作一样, in-place 也遇到了操作的原子性挑战. 内存本来就是易失的(掉电后丢失), 但硬盘不一样, 数据需要持久化(掉电不丢失), 即使靠加锁解决了访问原子性问题, 但解决不了数据丢失问题. 所以, 硬盘操作是最先引入多版本技术的. 当需要修改某个对象时, 在另外的地方保存对象的新数据, 然后在另外的地方原子性地修改指向新数据的"指针". 事实上, 指针的修改也是多版本的, 不是 in-place 的, 后面会细说.
Continue reading »

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

以银行转账为例子.

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

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

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

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

全球分布式数据库因为地理距离较远(上万公里), 网络通信延迟一般在 100ms 级别, 所以只能采取异步复制的方案. 采取异步复制方案, 那就决定了最终数据被复制的时效性无法得到保证, 例如正常情况仅仅比网络延迟多几毫秒(100ms+). 但坏情况时, 例如, 因为网络线路不好, 数据可能要花费数秒甚至数分钟才能同步. 这就导致了非常恼人的用户体验.

考虑这样的场景:

某网络游戏平台的用户 A 在中国, 而用户 B 是他曾经的邻居, 目前在美国. 某日, 用户 A 将游戏中的道具转给了用户 B, A 在游戏中看到了明确的操作成功的提示, 而且刷新也确认道具已经转交.

A 在私下用微信告知了这个操作, 然后让 B 在游戏中查看自己的道具背包.

该游戏平台在中国有一个数据库, 在美国也有一个数据库, 两地的数据库是异步复制(最终一致性)的. 因为游戏平台自己的网络线路问题, 这个操作的数据一直没有同步到美国. 但是, 微信所使用的网络线路没有问题, B 收到了 A 的微信消息.

B 在美国不断地刷新, 一直看不到道具, 这让他非常疑惑. 明明 A 说道具已经转交了呀, 而且还发截图了.

这就是经典的异步复制(最终一致性)导致的问题. 要怎么解决呢? 有很多方案, 但是, 正如”没有银弹”一样, 每一种方案都有缺陷. 我们一种一种地分析.

Continue reading »

Paxos 算法本身非常狭窄, 只解决共识问题, 如果只在这个领域封装一个 libpaxos 没有必要, 没有太大的使用场景. 如果要封装一个 Paxos 库, 几乎就是要重新发明(实现) Raft. 但 "Paxos" 这个词比较唬门外汉, 所以咱们就说"开发一个 Paxos 库"吧.

正如计算机领域解决问题的经典思路, 一个 Paxos 库应该拆分成三五个模块: 共识模块, 排序模块, 应用模块, 重传模块.

共识模块: 使用本节点所知的下一个未使用的日志序号, 执行 Paxos 算法的两阶段. 如果一条日志(对应一个序号)达成共识, 将日志传递给日志排序模块. 这个模块要记录所有已达成共识的序号, 当然, 不一定要离散地记录每一个序号, 可以优化成记录离散的 range, 最终只有一个 range. 维护这些 range, leetcode 上有一些题目有涉及, 有成熟可用的代码.

排序模块: 接受共识模块传递过来地已达成共识的日志, 按序号进行排序(因为是乱序达成共识). 然后连续地推进 commitIndex. 将 committed 的日志, 按连续的顺序发给日志应用模块.

应用模块: 接受日志排序模块的输出, 用独立的线程将日志发送给状态机(apply). 状态机 Apply 完成每一条日志之后, 更新 appliedIndex.

重传模块: 已经达成共识的日志, 不一定能全部被共识模块收到. 这时, 需要日志重传模块从其它节点拉取缺失的日志, 传递给日志排序模块.

以上各个模块, 组成这样的工作链条:

     +--- 重传模块 --+
    /                \
@--+----- 共识模块 ---- 排序模块 ---- 应用模块

如果从一条日志的生命周期的角度分析, 这个工作链条代表着日志的生命周期.

具体的实现编写代码的时候, 每一个模块肯定要对输入进行校验. 例如, 已经达成过共识的日志, 共识模块不再接受(leetcode 上面有判断一个整数是否落在 range 列表中的题). 小于等于 commmitIndex 的日志要被排序模块丢弃, 等等.

还有优化方面的考虑, 特别是重传模块, 最好借鉴 TCP 流量控制算法. 本质上来说, 整个 Paxos 库其实是在实现并裁剪 TCP 协议. 这里 Paxos 库要用拉取重传, 如果是 Raft 的话, 是推送方(leader)主动重传.

分布式系统要义

多副本(Replica)

• 高可靠(数据)
• 高可用(系统)
• 高性能(系统)
  • 读性能
  • 写性能(降低)

分区(Sharding)

• 突破单机物理限制
  • 多副本: 容量 = MIN(replica)
  • 分区: 容量 = SUM(replica)
• 提高读和写性能
• 提高存储容量

弹性

• 增加减少副本数量
• 合并分裂分区

协作

• 多副本协作
• 多分区协作
• 无协作不分布式

常见的伪分布式

• 无分区(争议)
  • 只有多副本算不算分布式?
• 无协作
  • 全世界独立运行的 MySQL 组成了一个分布式关系数据库集群吗?
  • 有人说 World Wide Web 是一个分布式系统
• 客户端自己分布式就是伪分布式
  • DBA 部署了2个独立的 Redis, 宣称是分布式 Redis 集群, 但要求业务部门自己把数据写到不同的实例…
  • DBA 部署了4个独立的 Redis, 除了要求业务部门自己拆分数据, 还要求业务部门自己写两个副本…
• 真分布式和伪分布式之间有模糊地带

很多人从客户端并发的角度去讨论一致性, 这其实是一个错误的方向. 并不是说客户端与一致性无关, 相反, 客户端正是要求一致性的需求者.

一致性协议不负责客户端的并发协调. 例如抢红包, 防超卖, 秒杀这类业务需求, 不是 Paxos/Raft 能解决的.

首先, 我们需要定义先后, 何为"先", 何为"后"?

      q1          r1          q2          r2
------+-----------+-----------+-----------+-----

如图, q 是指客户端发起请求的时间点, r 是指客户端收到响应的时间点, 两个请求用 1, 2 来表示. 很显然, 两个请求的先后顺序没有争论.

如果是并发呢? 先后就变得让人迷惑了.

      q1          r1 
------+-----------+-----------
         q2          r2
---------+-----------+-----------

你说, 哪个请求先哪个请求后? 一般认为, 请求 1 先于请求 2. 这个一般也不会有争论.

接着, 是最让人迷惑的地方了.

      q1          r1 
------+-----------+-----------
         q2    r2
---------+-----+-----------

你说, 请求 1 在先还是请求 2 在先? 争论不休吧? 所以, 讨论一个一致性的系统, 必须要求观察者的行为是瞬时的, 不能是并发的.

观察者(客户端)当然可以并发, 但是, 如果客户端自己都不能分清先后的话, 去预期系统(服务端)的执行结果是没有意义的.

一个强一致性的系统(服务端)当然可以处理并发请求, 而且请求的处理也不是瞬时, 这没关系. 我们讨论的是服务器在并发处理这些请求时的一致性可预期的行为, 而不是从客户端的角度看客户端并发时的系统的行为, 这里一定要注意.

事实上, 一个一致性的系统, 只关注行为完成时点的先后的关系, 并不关注行为的发起是什么先后顺序. 所以, 请求到达服务器的时间先后关系没有任何意义.

一致性, 讨论的是完成时, 不关心发起时.