论文研读之Spinnaker

阳光穿透心脏的1/2处 2022-10-02 14:52 229阅读 0赞

论文：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 ##

### 写请求的处理 ###

1.  处理写请求W时, 请求首先被导向请求写的数据所属的cohort的Leader, Leader首先在日志中记录此请求, 然后, 在将日志写到磁盘的同时, 将W附加到commit queue的末尾, 并发送propose message 到它的Follower.
2.  Follower收到写请求时, 记录对应日志到磁盘, 在将W附加到commit queue末尾, 然后向Leader返回ack.
3.  由于使用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同步, 就可以开始响应客户端的写操作.

转载于:https://www.cnblogs.com/yang-wen/p/10583860.html