论文：Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore
Motivation
可扩展性: 随着数据量增加, 要求增加新的设备存放数据. 一种做法就是将数据库 按Key拆分, 分布在不同机器上, 每个机器负责一定Key范围内的数据. 而手动实现拆分繁琐, 容易出现问题. 所以需要一种架构支持拆分.
容错性: 数据库保存在成百上千的普通机器上, 因此非常容易出现问题. 为了保证高可用性, 必须实现容错.
Architecture
- 基于Zookeeper, Paxos.
- 将数据库按Key拆分. 如Key为0-500, 可拆分为0-199, 200-399, 400-500三个范围, 分别包含对应的行.
- 使用3副本, 每个副本分别存放在不同机器上, 存放一个范围的多个机器称为一个cohort.
- 不同范围的数据可以保存在同一机器上, 因此一个机器可以属于多个cohort.
- log sequence number(LSN): 用于唯一标识cohort中的日志, 随日志单调递增.
- 一般情况下每个请求都是针对一行数据.
Replication Protocol
写请求的处理
- 处理写请求W时, 请求首先被导向请求写的数据所属的cohort的Leader, Leader首先在日志中记录此请求, 然后, 在将日志写到磁盘的同时, 将W附加到commit queue的末尾, 并发送propose message 到它的Follower.
- Follower收到写请求时, 记录对应日志到磁盘, 在将W附加到commit queue末尾, 然后向Leader返回ack.
- 由于使用3副本, Leader只要收到一个ack就可以保证大多数的要求. 所以, 当收到一个ack时, Leader将W应用到memtable, 并commit W. 最后回复请求, 表明写请求执行成功. Leader周期性地向Follower发送包含一个LSN值的commit message, 通知Follower将小于等于此LSN 的log都commit. 节点记录最后提交的日志的LSN, 记为last committed LSN, 保存到磁盘中.
读请求的处理
读数据时, 可以通过参数指明是strong consistency还是timeline consistency. 前者将向Leader 请求数据, 后者可以向Follower请求数据, 以减小Leader的负载, 但是可能会读到旧数据.
Leader选举
通过Zookeeper实现, 同一cohort的每个机器在相同目录下创建文件, 文件包含了自己的最后一个日志的 LSN, 记为n.lst. 选择n.lst最大的节点作为Leader.
Recovery
Follower Recovery
记 f.cmt 和 f.lst 分别代表节点日志中已commit的最后一个LSN和已保存的最后一个LSN. Follower恢复分为两个阶段: local recovery 节点从最近的checkpoint重放小于等于f.cmt的日志, 节点便恢复到f.cmt对应的状态. catch up 节点向Leader发送f.cmt, Leader就可以确定节点的状态, 并向其发送f.cmt之后的日志记录.
Leader Takeover
当Leader节点发生错误时, 需要选举出新的Leader. 新的Leader必须包含所有之前的Leader已经commit 的log. 选举策略如上所述. 但是可能存在这样的情况, 上一个leader fail后, 可能已经commit了部分write操作, 但是消息没有被其他follower接收到. 因此产生新的leader后, 它就要查看follower的最后commit的写操作是否落后于自己, 如果是, 就再次发送该写消息, 并通知folower commit. 当存在follower已经与leader同步, 就可以开始响应客户端的写操作.