Using Paxos to Build a Scalable,
文章先是指出因为要SCALE，所以SHARDING，分片必不可少。为了保证可以线性分片一般事务就这能在单个节点上去做。同时做了分片，运维和负载均衡是个头疼的事。最近，可以智能SHARDING和负载均衡的设计出来，他们使用了基于KEY的HASH和区域分割来把不同数据发往不同的节点。
除了可扩展性，可用性又是一个问题。一个经典的解决可用性的架构是MASTER-SLAVE 复制策略。但是也存在局限。
在传统的2路同步复制的方案下，有个经典的CASE。就是MASTER和SLAVE在LSN为10的时候还好的。然后SLAVE挂了。MASTER已经到了LSN20，这个时候MASTER挂了，SLAVE活了。那么SLAVE没法去同步数据，如果MASTER永远不恢复，那么LSN 11 - 20的数据就都丢了。
image.png
下面就引入3路复制，也就是PAXOS FAMILY 协议.Paxos解决了一个普遍的问题，即在2F +1个副本的状态下达成共识，同时容忍多达F个故障。 但是，Paxos尚未用于数据库复制，因为通常认为它太复杂且太慢。
一致性的问题
像Dynamo 这样的系统使用最终一致性为跨数据中心复制提供高可用性和分区容限。 在CAP术语中，Dynamo是AP系统的一个示例。 最终的一致性可能导致故障，网络分区或写入冲突。
复制会发散，应用程序可能会看到同一数据项的多个版本。 因此，必须准备好应用程序自己进行冲突检测和解决。 不支持熟悉的ACID事务隔离保证。
虽然一小部分具有极端可用性要求的应用程序可能能够容忍最终一致性，我们认为大多数应用程序都需要更强的一致性保证和对事务的某种支持。
在很少有网络分区的单个数据中心内，选择强大的一致性和可用性是一个更好的设计选择，即在CAP中选择CA。Spinnaker就是这么选择的。
Spinnaker具有基于键的范围分区，三向复制和事务性获取API，并可以选择读取时强一致性或时间线一致性。 时间线一致性允许返回可能过时的数据，以换取更好的性能。 对于复制，Spinnaker使用基于Paxos的协议，该协议与其提交日志和恢复处理 集成在一起。
使用Paxos可以确保只要包含副本的大部分节点都处于活动状态，就可以将数据分区用于读取和写入。 用CAP术语来说，Spinnaker是CA系统的一个示例。 它是为单个数据中心设计的，并假定为跨数据中心容错使用了不同的复制策略
2.3 和Dynamo, Bigtable, PNUTS比较
Dynamo 是一个可扩展的KEY-VALUE存储，采用最终一致性。利用向量时钟来解决冲突。通过后台反熵的算法。像读修复和MERKLE TREE。Spinnaker比Dynamo简单，因为他只依赖PAXOS，且不用冲突处理。
BIG TABLE是一个提供强一致和单操作事务的数据库。但依赖于GFS，对事务的负载不友好。也没有热备份，如果一个节点挂了。所有这个节点的数据都不可访问。
YAHOO的PUNT支持时间线一致性，但是它主要是解决跨数据中心的复制，并且依赖于一个中心化的消息订阅服务组件称为YAHOO MESSAGE BROKER来去做复制。
SPINNAKER API
image.png
Spinnaker 集群架构
首先，Spinnaker 作为 KV 数据库系统，会把数据按照它们的 Key 进行基于值域的分片，每个分片独立进行备份，常规的 Spinnaker 部署配置通常会把数据分片备份 3 片以上。尽管可以设定更高的备份因子，后续讨论将假设只配置为备份 3 份。
image
每个数据分片都会有与其相关联的值域（如 [0,199]），持有该数据分片的备份的节点共同组成一个 Cohort（备份组）：例如，上图中，节点 A、B、C 就共同组成了分片 [0,199] 的 Cohort。
每个 Cohort 都会有自己的 Leader，其他成员则作为 Follower。在存储数据时，Leader 首先会以先写日志的形式记录此次数据修改操作，并由 Paxos 对这部分日志备份至 Cohort 的其他成员。已完成提交的操作记录则会采用类似 Bigtable 的形式进行数据写入：数据首先会被写入到 Memtable，待 Memtable 的大小达到一定阈值后再被写出到 SSTable 中。
除外，Spinnaker 还使用了 ZooKeeper 来进行集群协调。ZooKeeper 为 Spinnaker 提供了存储元数据和检测节点失效的有效解决方案，也极大地简化了 Spinnaker 的设计。
4.1 节点架构
Spinnaker中的每个节点都包含多个组件，如图3所示。所有组件都是线程安全的，从而允许多个线程支持节点上3个键范围中的每个键。 共享的预写日志允许使用专用的日志记录设备来提高性能。 每个日志记录由一个LSN唯一标识。 为了共享相同的日志，节点上的每个同类群组都使用其自己的逻辑LSN。 提交队列是一种主要内存数据结构，用于跟踪挂起的写入。 只有在队列中收到足够数量的确认后，才提交写入。 同时，它们存储在提交队列中。
提交的写入将放置在内存表中，该内存表会定期排序并刷新到称为SSTable的不可变磁盘结构中。 SSTable通过键和列名进行索引，以实现高效访问。 在后台，将较小的SSTable合并为较大的SSTable，以垃圾收集已删除的行并提高读取性能。
image.png
Spinnaker 日志备份协议
如上一节所属，在 Spinnaker 运行时，每一组 Cohort 都会有自己独立的 Leader，其他 Cohort 成员作为 Follower，客户端的写操作请求会被路由到 Cohort 的 Leader，由 Leader 与其他 Follower 完成日志备份共识后再写入数据变动并响应客户端。
数据写入
在稳定状态下，Spinnaker 的一次数据写入的步骤如下：
image.png
- Spinnaker 将客户端发来的写入请求 W 路由到受影响数据分片对应 Cohort 的 Leader 处
- Leader 为写入请求 W生成对应的日志记录并追加到其日志中，而后并发地启动两个操作：
- 将写入请求 W 的日志记录刷入到磁盘中
- 将该日志记录放入自己的提交队列，并开始向 Follower 进行备份
- Follower 接收到 Leader 发来的日志后，也会将其刷入磁盘、放入自己的提交队列，然后响应 Leader
- Leader 收到大多数 Follower 的响应后，就会将写入请求 W应用到自己的 Memtable 上，并响应客户端
除外，Leader 也会周期地与 Follower 进行通信，告知 Follower 当前已提交的操作的序列号，Follower 便可得知先前的日志记录已完成提交，便可将其写入到自己的 Memtable 中。该通信周期被称为 Commit Period（提交周期）。
当客户端发起数据读取请求时，如果启用了强一致性模式，那么请求会被路由到 Leader 上完成，否则就可能会被路由到 Follower 上：正是由于 Commit Period 的存在，被路由到 Follower 上的时间轴一致请求有可能会读取到落后的数据，而落后的程序取决于 Commit Period 的长度。
Follower 恢复
Follwer 的恢复过程可以被分为两个阶段：Local Recovery（本地恢复）和 Catch Up（追数据）。
假设 Follower 已知已提交的最后一条日志记录的序列号为 f.cmt。在 Local Recovery 阶段，Follwer 会先应用其本地存储的已知已提交的日志记录到 f.cmt，为其 Memtable 进行恢复。如果 Follower 的磁盘失效、所有数据都已丢失，那么 Follower 直接进入 Catch Up 阶段。
在 Catch Up 阶段，Follower 会向 Leader 告知其 f.cmt的值，Leader 便会向 Follower 发送 f.cmt后已完成提交的日志记录。
Leader 选举
如上文所述，Spinnaker 主要借助 ZooKeeper 来侦测节点的失效事件。在一个 Cohort 的 Leader 失效时，其他 Follower 就会尝试成为 Leader。借助 ZooKeeper，Spinnaker 的 Leader 选举机制十分简单，只要确保新的 Leader 持有旧 Leader 所有已提交的日志记录即可。
image.png
日志压缩与合并
在实现 Spinnaker 时的一个比较主要的 Engineering Chanllenge 在于如何避免因为过多的磁盘 IO 导致系统的性能底下。
从上文中所描述的 Spinnaker 集群架构可知，每个节点会持有不止一个数据分片，也就是说节点会同时属于多个 Cohort，但每个 Cohort 会独立地进行日志备份和写入。如果每个 Cohort 的日志都写入到独立的文件中，必然会引入大量的磁盘寻址消耗，所以 Spinnaker 会把同一个节点不同 Cohort 的日志写入到同一个文件中，在节点恢复时也可以在一次文件扫描中就完成所有 Cohort 的恢复，只需要在日志层面上区分其所属 Cohort 即可。
尽管如此，由于从 Follower 写入日志到日志实际提交中存在时间差，Follower 恢复时可能会观察到部分已写入磁盘的日志最终并未完成提交，需要将其从日志存储中移除，但考虑到不同 Cohort 的日志都存储在同一个文件中，这样的操作开销很大。为此，Spinnaker 引入了日志的 Logical Truncation（逻辑截断）机制：处于 Cohort 日志列表尾部需要移除的日志记录会被记录到一个 Skipped LSN 列表中，并写入到磁盘内，这样后续进行 Local Recovery 时，Follower 就会知道需要跳过这部分日志。
image.png
除外，使用固态硬盘也能很大程度上避免上述问题。如上文所述，不能在物理上区分不同 Cohort 日志的存储路径的原因在于机械磁盘的磁头寻址时间，而固态硬盘不存在这样的问题，因此在使用固态硬盘时，上述复杂的日志机制就变得没有意义了。在论文的附录 D.4 中讨论了使用固态硬盘的场景及相关的性能基准测试结果，可见使用固态硬盘时 Spinnaker 的写入性能有了 10 倍以上的提升。
上述具体例子
image.png
总结
这次 Spinnaker 的 Case Study 很好地讲述了如何可以利用 Raft/Paxos 来实现一个强一致、高可用且可扩展的数据库系统。尽管 Spinnaker 很大程度上利用了 ZooKeeper 来简化自身的设计，但这部分内容也是可以通过 Raft/Paxos 这种分布式共识协议来实现的。
回答问题
In Spinnaker a leader to responds to a client request after the leader and one follower have written a log record for the request on persistent storage. Why is this sufficient to guarantee strong consistency even after the leader or the one follower fail?
因为已经有2个NODE的COMMIT LOG已经包含了这一条，所以即使任意一个NODE(包含主节点），在余下的2个NODE里必然去最大CMT的人会重新选为主，就可以把这个LOG恢复出来。
FAQ
问：什么是时间线一致性？
答：这是一种宽松的一致性形式，可以以明显的异常行为为代价提供更快的读取速度。 所有副本均以相同顺序应用写操作（客户端将写操作发送给领导者，领导者
选择一个订单并将写入转发到副本）。 允许客户端向任何副本发送读取，并且该副本以其当前拥有的任何数据进行回复。 该副本可能尚未收到来自领导者的最新写入，因此客户端可能会看到陈旧的数据。 如果客户端将读取发送到一个副本，然后再发送到另一个副本，则客户端可能会从第二次读取中获取较旧的数据。 与强一致性不同，时间轴一致性使客户意识到以下事实：存在副本，并且副本可能有所不同。
问：不同一致性级别的权衡是什么？
答：高度一致的系统更容易编程，因为它们的行为类似于非复制系统。 在最终一致的系统之上构建应用程序通常会更加困难，因为程序员必须考虑在非复制系统中无法实现的方案。 另一方面，通常可以从较弱的一致性模型中获得更高的性能。
问：第9.1节说，spinnaker的领导者会回覆强一致的阅读内容，而无需咨询follower。 领导者如何确保自己仍然是领导者，以便它不会回复使用陈旧数据进行的一致读取？
答：不清楚。 可能是领导者从Zookeeper得知不再是领导者，因为某些lease/watch 超时。
问：是否可以用类似Raft的首领选举协议代替Zookeeper的使用？
答：是的，这是非常合理的事情。 我的猜测是，他们需要Zookeeper进行分片分配，然后决定也将其用于领导者选举。
问：图7的第6步似乎表明，最长的候选人将成为下一位领导者。 但是在Raft中，我们发现该规则不起作用，并且Raft必须使用更为详尽的选举限制。 为什么Spinnaker可以安全地使用最长的日志？
答：Spinnaker实际上似乎使用的规则类似于Raft的规则。 图7比较了LSN（对数序列号），附录B表示LSN在高位具有“epoch time”。 epoch time等于Raft的term。 因此，第6步的“man n.lst”实际上可以归结为“最高epoch获胜；如果时期相等，则最长log胜出”。
