简介
传统数据库已无法满足大规模数据的需求。传统的解决方案是分片，事务只能局限在一个分片节点。且通常需要人工维护。分片的方式会有成百上千个节点，节点数量多导致小概率事件变成大概率事件。因此需要实现高可用性和错误容忍。一个解决方案是使用同步备份策略（一个主多从，写数据需要从机确认后才能返回写成功）。然而这种策略在有些场景下会失去一致性。
1. 传统策略的问题
1.1 传统同步备份的问题
传统的两路同步备份思路，
同步一主机一从机，写确认需要从机确认。如果从机宕机，主机继续提供服务；如果主机宕机，则从机一定处于最新的状态，因此可以由从机继续提供服务。
使得这种模式出现不一致的场景：
- 主机接受命令m1， 从机接受命令m1
- 从机失败，主机继续工作
- 主机接受命令m2
- 在主机将m2复制到从机之前，主机宕机，同时从机恢复
- 此时只有一台机器处于宕机状态（主机），但由于主机已经接受的命令没有
拷贝到从机，从机不能接受命令。
同步一主两从，假定有三个节点A，B，C
假定有以下命令序列[1,2,3], 三个节点状态按如下顺序变化
1 1 1 (A，B，C均正常服务)
2 2 1（A， B正常，C宕机）
3 2 1 （A正常，B宕机，C恢复，命令未完成复制）
3 2 1 （A宕机，B恢复，C恢复）此时无法接受命令，虽然只有一个节点处于宕机状态。
多机一致性的问题研究了近30年，Paxos协议家族目前被认为是唯一保证了正确性的协议，它能保证在有2F+1个节点时，能够容忍F个节点宕机（少数）。然而，Paxos算法还没有被应用在数据库的复制中，因为通常认为它太复杂并且很慢。(本文发表于2011年，貌似阿里的oceanbase中是使用Paxos协议来实现数据库备份)。
1.2 强一致性 vs 最终一致性
强一致性是指所有副本都对应用表现的完全一致。然而根据CAP理论，强一致性跟可用性和网络分区容忍不能共存。
数据库系统如Dynamo使用了最终一致性模型，客户端可能会看到多个不同旧版本的数据，作为结果，客户端需要自己处理好冲突检查。我们所熟悉的数据库ACID事务并不被支持。
尽管有些系统可以接受最终一致性，但是大部分应用仍然需要强一致性的保障。并且需要有一定的事务支持。
在单数据中心中，网络分区现象很少见。因此选择CA可能比选择AP+最终一致性更合适。
1.3 Spinnaker
基于key的range partitioning
3路副本
带事务的get-put,可选强一致或time-line一致性（取舍：提高性能，允许可能返回旧版本数据）
使用Paxos确保大多数节点存活时的可用性
在CAP中选择CA
2. 相关工作
2.1 两阶段提交
2PC允许每一个参与者都是一个独立的资源管理器
缺陷：
一个节点失败会导致全局失败
每一个事务都需要2PC会导致性能很差
2PC有coordinator角色，当coordinator宕机时会阻塞。3PC是非阻塞的，但是因为性能差很少再实践中使用。
3 数据模型和API
数据模型
类似多版本关系数据库。表+行。每个column有对应的verison
table + row["key"]["column"]["version"]
客户端API
get(key, column, consistent=strong/timeline)
put(key, colname, colvalue)
delete(key, colname)
conditionalPut(key, colname, value, v)
conditionalDelete(key, colname, v)
4 架构
基于key range分片，每个分片默认3个副本分布在不同的节点
4.1 节点架构
每个节点包含多个组件，且每个组件都是线程安全的。
每一条log由LSN唯一标志
commit queue位于内存，log只有在多数节点确认时才能提交，在此期间它们存储在commit queue中。
committed log存储结构：memtable + SSTable(GFS)
4.2 Zookeeper
提供错误容忍，分布式协调服务
5 副本协议
每个分片有一个Leader，两个Follower
协议有两个阶段：Leader选举阶段和投票提交阶段，Leader提议Follower投票。在没有出现错误的情况下（服务器宕机，网络分片等），Leader不需要改变，只需要执行投票阶段。
当客户端需要写数据时，总是会被路由到Leader（只有一个节点写数据）。
Leader将写命令Append到commit queue中。持久化到硬盘。
Leader发起提议，
Follower接收到提议，持久化log，将命令放到commit queue。返回ACK
Leader接收到多数人的ACK，此时可以确认commit->将命令应用到memtable。
Leader阶段性的发送异步的commit message给follower，follower相应的将写命令应用到memtable。
强一致性读需要从Leader读，timeline 一致性读可以从副本中读取。
6. 恢复
6.1 Follower恢复
Follower恢复有两个阶段。
- Local Recovery
- Catch Up
在Local Recovery阶段，Follower能从checkpoint开始，一直应用到f.cmt来恢复memtable的状态。f.cmt之后的log可能没有被Leader commit，这些log在catch up阶段恢复。如果Follower因为磁盘错误丢失了所有的数据，那么Follower直接进入Catch Up阶段。
在Catch Up阶段，Follower告诉Leader它的f.cmt的值，Leader将Follower缺的f.cmt之后的所有log发回Follower。在catch up的最终阶段，Leader会临时的阻塞写操作，从而确保Follower能完整的catch up。
在实践中，Leader由于会执行log压缩，从而有些Follower需要的log记录已经不能获得。此时的处理是直接将合适的SSTable发送给Follower，并从SSTable记录开始恢复。
当选出新的Leader的时候，f.cmt之后的有些记录可能并没有被Leader Apply，因此这些记录需要丢弃。那么是否可以直接截断f.cmt之后的log呢？答案是不能。
原因是这些log可能属于不同的分片。
6.2 Leader 接管
新Leader选举时会确保新的Leader包含了所有的旧Leader已经commit的log。这一点会在第七节介绍。
旧Leader恢复时需要执行Follower恢复流程。
新Leader需要为旧Leader发送那些已经被commit但是commit message还没有
发送的commit的commit message。使用如下算法。
7 Leader选举
Leader选举会在一个分片的Leader出错时发生。
Leader选举必须达成共识只有一个Leader。
Leader选举必须保证选举出来的Leader必须拥有所有的已经commit的log。
7.1 Zookeeper 数据模型和API简介
Zookeeper的数据模型类似文件系统中的目录树。每一个节点由其路径标志。
举个例子 /a/b/c。每一个znode节点可以设置关联数据。
客户端可以创建或删除znode节点。
znode节点可以是持久化的节点或临时节点。当客户端断开链接时，Zookeeper会自动删除临时节点，而持久化的节点需要客户端显式删除。znode可以包含一个连续属性，从而允许唯一性，单调性的需求。
znode提供了watcher，客户端可以监听znode或者其children的事件。
7.2 Leader选举协议
每一个Spinner的节点都包含了一个Zookeeper的客户端，用于实现Leader的选举。
r代表分片的范围（比如图2中的[1, 199]）
选举r分片所需的信息会存储的Zookeeper的/r目录
首先清除所有的前一次选举的状态信息
然后，每一个节点都宣称自己是备选人(candidate)，使用自己的n.lst，创建在/r/candidates目录下。
然后给目录/r/candidates设置一个watcher，一旦目录信息发生变化通知分片节点。
当大多数节点的信息出现在此目录时。即可选出新Leader，选举规则是哪个的n.lst最大就选哪个。
然后新Leader将其host信息写入/r/leader,并执行Leader 接管算法。
使用临时的节点可以应对新选出来的Leader潜在的可能出错。
最终，所有的Follower从/r/leader中读取leader信息。
这个算法是可以保证
- 所有节点对Leader达成共识
- 新的Leader拥有所有旧的Leader已经commit的log
第一条很显然。
第二条依赖的就是两个多数人的集合必然有交集。旧Leader已经commit的log必然在新Leader的candidate目录中必然至少有一个包含了旧Leader所有的commit log。而选择的新Leader拥有最大的lst，因此新Leader log要么就是至少的那一个，要么比至少的那一个还要长。于是可以得出结论新的Leader必然包含了所有已经commit的log。
8 可用性和持久性保障
对于三路复制。
写操作至少需要两个节点存活。
强一致读需要重定向到Leader节点，也至少需要两个节点存活。
timeline一致性允许读到旧数据，只要有一个节点存活即可。
