本系列文章是对 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 理论提出 Consistency、Availability 和 Partition tolerance 三者最多只能同时满足两项。
比如 Dynamo 这样的系统，使用最终一致性模型来提供高可用性和分区容忍性。Dynamo 是一个 AP 系统，牺牲了 Consistency。
Spinnaker 使用基于 Paxos 的协议来实现日志提交和故障恢复。Paxos 确保了系统在大多数节点存活的情况下可以运作。Spinnaker 是一个 CA 系统，用于单一的 datacenter，并使用另外的 replication strategy 来保证跨 datacenter 的容错性。
Related work
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 recovery 和 catch 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
选举算法如下图：
Dynamo
Introduction
一个系统的可靠性和可扩展性取决于如何管理应用状态。Amazon 采用一种高度去中心化，松耦合，由数百个服务组成的面向服务架构。在这种环境中尤其需要一个高可用的存储技术。
Dynamo 被设计用于管理服务状态，要求具备非常高的可靠性，而且需要严格控制可用性、一致性、成本效益和性能的之间的权衡。
Amazon 服务平台中许多服务只需要主键访问数据存储。通常关系数据库模式会导致效率低下，且可扩展性和可用性也有限。Dynamo 提供了一个简单且唯一的主键接口，以满足这些应用的要求。
Dynamo 综合一些著名的技术来实现可伸缩性和可用性：使用一致性哈希划分和复制数据，一致性由对象版本来实现。更新时副本之间的一致性是由类似仲裁（quorum-like）的技术和去中心化的副本同步协议来保证。Dynamo 采用了基于 gossip 的分布式故障检测和 membership protocol。
System Assumptions and Requirements
Dynamo 的目标应用程序是通过较弱的一致性（ACID中的“C”）来达到高可用性。Dynamo 不提供任何数据隔离（ACID中的“I”）保证，只允许单一主键更新。
Design Considerations
对于容易出现服务器和网络故障的系统，可使用乐观复制来提高系统的可用性，数据变化允许在后台发送到副本，同时容忍网络断开。这种做法带来的挑战是如何检测和协调由此引发的冲突。协调的过程引入了两个问题：何时协调以及谁负责协调。Dynamo 被设计成最终一致性（eventually consistent）的数据存储，所有的更新操作最终会分发到所有副本。
一个重要的设计考虑的因素是何时去协调更新操作冲突，例如是在读还是写过程中协调冲突。许多传统 data store 在写的过程中协调冲突，从而保持读的复杂度相对简单。另一方面，Dynamo 的目标是“永远可写”。对于 Amazon 许多服务来讲，拒绝客户的更新操作可能导致糟糕的客户体验。这迫使我们将协调冲突的复杂性推给“读”，以确保“写”永远不会拒绝。
其他重要的设计原则：
-
增量的可扩展性（Incremental scalability）
Dynamo 需要能够水平扩展一台存储主机，而对系统操作者和系统本身的影响很小。
-
对称性（Symmetry）
每个 Dynamo 节点应该有一样的责任，不应该存在有区别或具备特殊的角色或额外的责任的节点。根据我们的经验，对称性(symmetry)简化了系统的配置和维护。
-
去中心化（Decentralization）
是对对称性的延伸，设计应采用有利于去中心化而不是集中控制的技术。
-
异质性（Heterogeneity）
系统必须能够利用其运行所在的基础设施的异质性。例如，负载的分配必须与各个独立的服务器的能力成比例。这样就可以一次只增加一个高处理能力的节点，而无需一次升级所有的主机。
Partitioning Algorithm
Dynamo 的关键设计要求之一是增量可扩展性，这需要一个机制来将数据动态划分到系统中的节点上。Dynamo 的分区方案依赖于一致哈希。一致性哈希的主要优点是节点的新增或减少只影响其最直接的邻居，而对其他节点没影响。
基本的一致性哈希算法存在一些不足：
- 环上的节点随机分配位置导致数据和负载的不均匀分布
- 基本算法无法满足节点性能的异质性（Heterogeneity）
为了解决这些问题，Dynamo 引入虚拟节点：每个节点被分配到环上多点，而不是只映射到环上的一个单点。系统中每个节点对多个虚拟节点负责。
使用虚拟节点具有以下优点：
- 如果一个节点不可用，这个节点的负载将均匀地分散给其余的可用节点
- 当一个节点再次可用，或者是新添加到系统中，the newly available node accepts a roughly equivalent amount of load from each of the other available nodes.
- 一个节点负责的虚拟节点数目由其处理能力来决定（heterogeneity）
Replication
每个键 K 被分配到一个协调器节点。协调器节点负责其管辖范围内的数据的复制。除了在本地存储每个 key 外，协调器节点也将 key 复制到环上顺时针方向的 N-1 后继节点。系统中每个节点负责环上的从其自己到第 N 个前继节点间的区域。
负责存储一个特定的键的节点列表被称为首选列表。
Data Versioning
Dynamo 提供最终一致性，允许更新操作异步地传播到所有副本。put 调用可能在更新操作被所有的副本执行之前就返回给调用者，这会导致在随后的 get 操作可能会返回一个不是最新的对象。
Dynamo 将每次数据修改的结果当作一个全新且不可修改的数据版本。它允许同一时间存在多个版本的对象。大多数情况，新版本包括了老的版本，系统自己可以决定权威版本（语法协调 syntactic reconciliation）。然而，在出现失败且伴随并发更新操作的时候，可能导致对象的版本冲突。在这种情况下，系统无法协调，需要由客户端必须执行协调，将多个分支演化后的数据折叠成一个合并的版本（语义协调 semantic reconciliation）。
Dynamo 使用矢量时钟来捕捉同一对象不同版本的因果关系。矢量时钟实际上是一系列（节点，计数器）对。一个矢量时钟和每个对象的每个版本相关联。通过审查向量时钟，可以判断一个对象的两个版本是平行或因果顺序。如果第一个时钟对象上的计数器小于或等于第二个时钟对象上的所有节点，那么第一个是第二个的祖先，可以被忽略。否则这两个变化是冲突的，需要协调。
在 Dynamo 中，当客户端更新一个对象时必须指定它正要更新哪个版本，这通过从早期的读操作中获得的上下文对象来指定。它包含了向量时钟信息。当处理一个读请求，如果 Dynamo 访问到多个不能语法协调的分支，它将返回处于分支叶子的所有对象。
Execution of get () and put () operations
处理读或写操作的节点被称为协调员。通常，这是首选列表中前 N 个节点中的第一个。如果请求是通过 load balancer 收到，访问 key 的请求可能被路由到环上任一节点。在这种情况下，如果该节点不是请求的 key 的首选列表中前 N 个节点之一，该节点将请求转发到首选列表前 N 个中的第一个节点。
为了保持副本的一致性，Dynamo 使用的一致性协议类似于仲裁（Quorum NRW 模型）。该协议有两个关键配置值：R 和 W。R is the minimum number of nodes that must participate in a successful read operation. W is the minimum number of nodes that must participate in a successful write operation. N 则是数据的副本数量。设定 R 和 W，使得 R + W > N，即读操作副本加上写操作副本必须大于数据的副本量。在此模型中，一个 get 或者 put 操作延时是由最慢的 R 或 W 副本决定的。因此 R 和 W 通常配置为小于 Ｎ，以减小时延。
当收到对 key 的 put 请求时，协调员为新版本生成向量时钟并写入本地，然后将新版本（带上向量时钟）发送给首选列表中的前 Ｎ 个可达节点。如果至少 Ｗ-1 个节点返回了响应，那么这个写操作被认为是成功的。
同样，对于 get 请求，协调员从首选列表中前 Ｎ 个可达节点处请求该 key 所有版本的数据，然后等待 Ｒ 个响应，然后返回结果给客户端。如果协调员收到多个版本的数据，它返回所有它认为没有因果关系的版本。
Handling Failures: Hinted Handoff
Dynamo 如果使用传统的仲裁方式，在服务器故障和网络分裂的情况下将不可用。因此 Dynamo 使用了“马虎仲裁”机制，所有的读，写操作是由首选列表上的前 N 个健康的节点执行的，它们可能不总是在散列环上遇到的那前 N 个节点。
举个例子，如果写操作过程中节点 A 暂时挂掉或不可达，本来发往 A 的副本现在被发送到节点 D。发送到 D 的副本将在其原数据中表明 A 节点才是该副本的预期接收者。接收到的暗示副本将被保存在单独的本地存储中定期扫描。在检测到了 A 已经复苏，D 会尝试发送副本到 A。一旦传送成功，D 可将数据从本地存储中删除，不会降低系统中的副本总数。
数据中心有可能因为断电、冷却装置故障、网络故障或自然灾害发生故障。Dynamo 将每个对象跨多个数据中心地进行复制。从本质上讲，每个个 key 的首选列表的分布在多个数据中心。这些数据中心通过高速网络连接。这种跨多个数据中心的复制方案使我们能够处理整个数据中心故障。
Handling permanent failures: Replica synchronization
Dynamo 实现了反熵（anti-entropy 或副本同步）协议来保持副本同步。
为了更快地检测副本之间的不一致性并减少传输的数据量，Dynamo 使用 MerkleTree。MerkleTree 是一个哈希树，其叶子是各个 key 的哈希值，父节点为其各自孩子节点的哈希。MerkleTree 的主要优点是树的每个分支可以独立地检查。另外，MerkleTree 有助于减少为检查副本间不一致而传输的数据的大小。如果两树的根哈希值相等，那么树的叶节点值也相等，该节点不需要同步。
Membership and Failure Detection
去中心化的故障检测协议使用一个简单的 Gossip 式的协议，使系统中的每个节点可以了解其他节点加入或离开。详细可以参考论文《On scalable and efficient distributed failure detectors》
Ensuring Uniform Load distribution
随着时间和负载分布的影响，Dynamo 的划分方案也逐渐演化：
-
策略 1：每个节点随机分配 T 个 token ，且基于 token 值进行分割
使用这一策略会出现以下问题。首先，当新的节点加入系统时，它需要从其他节点上“窃取”其负责的 key ranges。然而，这些需要移交key ranges 给新节点的节点必须扫描他们的本地持久化存储。第二，当一个节点加入/离开系统，许多节点的 key range 发生变化，MertkleTree 需要重新计算，在生产系统上，这不是一个简单的操作。最后，由于 key range 的随机性，没有简单的办法为整个 key space 做快照，这使得归档过程变得复杂。在这个方案中，归档整个 key space 需要分别检索每个节点的 key，这是非常低效的。
这个策略的根本问题是，数据划分和数据安置交织在一起。
-
策略 2：每个节点随机分配 T 个 token，每个分区同等大小
在此策略中，哈希空间被划分为 Q 个同样大小的分区/范围，每个节点随机分配 T 个 token。通常设置 Q 使得 Q » N 且 Q » S * T，其中 S 为系统的节点个数。在这一策略中，token 只是用来构造映射函数，该函数将哈希空间的值映射到一个有序列的节点列表，而不决定分区。A partition is placed on the first N unique nodes that are encountered while walking the consistent hashing ring clockwise from the end of the partition.
-
策略 3：每个节点分配 Q/S 个 token，每个分区同等大小
Each node is assigned Q/S tokens where S is the number of nodes in the system. When a node leaves the system, its tokens are randomly distributed to the remaining nodes such that these properties are preserved. Similarly, when a node joins the system it “steals” tokens from nodes in the system in a way that preserves these properties.
相对于策略 1，策略 3 达到更好的效率，每个节点需要维持的信息的大小降低了三个数量级。虽然存储不是一个主要问题，但节点间周期地gossip 成员信息，因此尽可能简化信息。除此之外，策略 3 更易于部署，理由如下：
-
更快的 bootstrapping/recovery
由于分区范围是固定的，它们可以保存在单独的文件，这意味着转移分区仅需要简单地转移文件。
-
易于归档
对数据集定期归档是 Amazon 存储服务的强制性要求。策略 3 归档整个数据集很简单，因为分区的文件可以被分别归档。相反，策略1 中 token 是随机选取的，归档存储的数据需要分别检索各个节点的 key，这通常是低效和缓慢的。
