Motivation
- 可扩展性要求: 随着数据量增加, 要求增加新的设备存放数据. 一种做法就是将数据库按Key拆分, 分布在不同机器上, 每个机器负责一定Key范围内的数据. 而手动实现拆分繁琐, 容易出现问题. 所以需要一种架构支持拆分.
- 容错性: 数据库保存在成百上千的普通机器上, 因此非常容易出现问题. 为了保证高可用性, 必须实现容错.
Architecture
基于 Zookeeper 和 Paxos.
将数据库按Key拆分. 如Key为0-500, 可拆分为0-199, 200-399, 400-500三个范围, 分别包含对应的行.
使用3副本, 每个副本分别存放在不同机器上, 存放一个范围的多个机器称为一个 cohort. 一个 cohort 中有一个机器作为 Leader, 其他机器作为此 cohort 的 Follower. 不同范围的数据可以保存在同一机器上, 因此一个机器可以属于多个 cohort. 因此一个机器可能在某个 cohort 中是 Leader, 在另一个 cohort 中是 Follower.
用 log sequence number(LSN) 来唯一标识 cohort 中的日志, LSN 随日志单调递增.
一般情况下每个请求都是针对一行数据.
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 同步, 就可以开始响应客户端的写操作.