Masutangu

长风破浪会有时 直挂云帆济沧海

也許我這一生 始終在追逐那顆九號球


MIT 6.824 学习笔记(三)

本系列文章是对 MIT 6.824 课程的学习笔记。

Spinnaker

Introduction

Spinnaker is an experimental datastore that is designed to run on a large cluster of commodity servers in a single datacenter. This paper describes Spinnaker’s Paxos-based replication protocol. The use of Paxos ensures that a data partition in Spinnaker will be available for reads and writes as long a majority of its replicas are alive.

实现持续可用性的一个解决方案是主从复制,但主从复制存在以下缺陷:

在上图的例子中,主从节点都从 LSN=10 开始(a),之后 slave 节点挂了(b),master 节点继续接收写请求,一直到 LSN=20。之后 master 节点也挂了(c),之后 slave 节点恢复(d),然而,在此时 slave 节点不能接收任何读写请求因为它缺失了 LSN=11 到LSN=20 之间的记录。如果要避免这种情况,只有在任意节点挂掉的时候,都阻塞写请求。但这样就降低了整个系统的 availability。

分布式系统中,一致性模型描述了如何使不同的 relicas 保持同步强一致性保证了所有的 replicas 都是一致的,但要实现强一致性需要牺牲 availability 或网络分区容忍性。CAP 理论提出 ConsistencyAvailabilityPartition tolerance 三者最多只能同时满足两项。

比如 Dynamo 这样的系统,使用最终一致性模型来提供高可用性和分区容忍性。Dynamo 是一个 AP 系统,牺牲了 Consistency。

Spinnaker 使用基于 Paxos 的协议来实现日志提交和故障恢复。Paxos 确保了系统在大多数节点存活的情况下可以运作。Spinnaker 是一个 CA 系统,用于单一的 datacenter,并使用另外的 replication strategy 来保证跨 datacenter 的容错性。

Two-phase commit (2PC) 是保持 replicas 一致的一种方式。但 2PC 更偏向于将每个 participant 当作一个独立的资源管理者,而不仅仅是 replica。使用 2PC 来实现 replication 有些 overkill,并且还有不少缺陷。首先单一节点失败会导致系统 abort。其次每个 transaction 都发起 2PC 会导致极差的性能。每次 2PC 都需要两次磁盘强制写和传输两条信息的时延。最后,2PC 在 coordinator 挂掉时无法运作。

Amazon 的 Dynamo 通过分布式时钟来解决最终一致性的问题。

Google 的 Bigtable 提供了强一致性,和 spinnaker 不同的是,Bigtable 依赖 GFS 来存储数据和日志,还有实现 replication。这样每个 transaction 的 workload 就加重了(需要和 gfs 的 master 交互)。

Architecture

Like Bigtable and PNUTS, Spinnaker distributes the rows of a table across its cluster using range partitioning. Each node is assigned a base key range, which is replicated on the next N − 1 nodes (N = 3 by default).

Each group of nodes involved in replicating a key range is denoted as a cohort. Note that cohorts overlap.

每个日志由一个 LSN 唯一的标记。Commit queue 是在内存的数据结构,用于存放 pending writes。写操作只有在接收到大多数 cohort 的 ack 之后才能提交。在此之前都存放在 commit queue 中。

已经提交的写操作存于 memtable 中,并被定期刷到被称为 SSTable 的 immutable disk structure。SSTable 会被定期合并以提升读性能并删除不需要的数据。

The replication protocol

提交一个写操作需要三次日志强制写和四条信息交互,不过大多数操作都是重叠的(可以并行)。

Recovery

Follower 的恢复需要两个阶段:local recoverycatch up。定义 f.cmt 表示 follower 的最后一个提交日志的 LSN,f.lst 表示 follower 的最后一个日志的 LSN。Local recovery 阶段,follower 从最近一次 checkpoint 开始重新执行日志直到 f.cmt,之后进入 catch up 阶段。Catch up 阶段,follower 通知 leader 自己的 f.cmt,leader 回复 f.cmt 之后所有的 commit writes。Leader 将会阻塞所有新的写请求直到 follower 已经跟上。

当 leader 挂掉,新的 leader 将被选举,并且会确保新的 leader 会包含所有已提交的写操作。在老的 leader 挂掉时,有可能其提交的写操作在某些 followers 还处于 pending 的状态。新 leader 将使用下图的算法,继续提交所有 unresolved 写操作。

Leader election

选举算法如下图:

更早的文章

MIT 6.824 学习笔记(二)

本系列文章是对 MIT 6.824 课程的学习笔记。RaftIntroductionRaft 是用于管理复制日志的一致性算法。为了方便理解,Raft 将一致性算法分解为几个关键模块:Leader 选举、日志复制和安全性,同时通过更强的一致性来减少需要考虑的状态。一致性算法允许一组机器像一个整体一样工作,即使其中一些机器挂掉。一致性算法在构建大规模可信赖系统中扮演重要的角色。Raft 和许多一致性算法类似,但他也有自己的新特性: Strong leader Raft 使用比其...…

读书笔记继续阅读