最近看完了杨传辉老师写的《大规模分布式存储系统》一书，发现里面很多知识点和之前看的《大型网站系统与Java中间件》有很多相通之处，也渐渐加深了我对分布式技术的兴趣。但无奈分布式涵盖范围太广了，分布式存储、分布式计算、CAP理论、Paxos算法、什么GFS、Hadoop、Dynamo、BigTable、Spanner等等，不下点功夫还真不能理顺它们之间的内在关系。所以结合两书以及一些优秀博文，总结了分布式存储的知识体系，为以后打下基础而努力。由于初入泥潭，必然有些理解不当的地方，若有大神路过还望不吝指教。
本文更像是读书笔记，是对知识点的一个梳理，无奈越写越多，部分知识只能点到为止，具体内容可以查看原书或维基百科。
单机存储引擎
哈希
哈希存储引擎是哈希表的持久化实现，支持增、删、改，以及随机读取操作，但不支持顺序扫描，对应的存储系统为键值(Key-Value)存储系统，如 Bitcask。它仅支持追加操作，删除也只是通过标识 value 为特殊值，通过定期合并（Compaction）实现垃圾回收。
B 树
B 树存储引擎是 B 树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描，对应的存储系统是关系数据库。关系数据库中通过索引访问数据，在 Mysql InnoDB 中，有一个称为聚集索引的东西，行的数据存于其中，组织成 B+ 树的结构。更多 B 系树的内容可以参考 这里 。
LSM 树
LSM 树(Log Structure Merge Tree)存储引擎采用批量转储技术来避免磁盘随机写入。其思想很朴素，就是将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘。它广泛应用于互联网的后台存储系统， 例如 Google BigTable、 以及 Facebook 开源的 Cassandra系统。
分布式存储的出现
单机存储随着业务的增长会遇到性能与单点故障问题。通常有两种解决方案：
- 数据分布：就是把数据分块存在不同的服务器上（分库分表）。
- 数据复制：让所有的服务器都有相同的数据，提供相当的服务。
这两种方法都能解决性能上的问题，一般结合使用。而对于数据丢失的问题，我们只能通过第二种方法来完成——数据的冗余存储。但是加入更多的机器，会导致事情变得复杂起来，尤其是分布式事务处理，也就是多台服务器之间的数据如何保持一致性，因为原先单机的 ACID 特性在分布式环境下都用不了了。
数据分布
数据分布主要有两种方式：一种是哈希分布，如一致性哈希（Dynamo）；另一种是顺序分布（BigTable）。考虑因素包括读写场景， 即随机还是顺序， 包括如何保证负载均衡从而提高性能等
传统的哈希分布算法简单的将哈希值与服务器个数做除法取模映射。但是当服务器上下线时，数据的重新分布会带来大量的数据迁移。
因此有了 一致性哈希算法 。算法思想如下 :给系统中每个节点分配一个随机 token，这些 token 构成一个哈希环。执行数据存放操作时，先计算 Key(主键)的哈希值，然后存放到顺时针方向第一个大于或者等于该哈希值的 token 所在的节点。一致性哈希的优点在于节点加入 / 删除时只会影响到在哈希环中相邻的节点，而对其他节点没影响。增加节点后能很大程度上避免了数据迁移。为了考虑负载均衡，一般还会引入虚拟节点的技术，即一个物理节点会对应着多个虚拟节点（如 Dynamo）。
数据复制
复制协议有两种：强同步复制，异步复制。 区别在于用户的写请求是否需要同步到备副本才可以返回成功。
一致性和可用性是矛盾的。强同步复制协议保证主备副本之间的一致性，但是当备副本出现故障时会影响系统可用性。异步复制协议的可用性较好，但是一致性得不到保障，主副本出现故障时还有数据丢失的可能。
这两种协议都是将主副本的数据以某种形式（多为操作日志）发送到其他副本，这种复制协议称为基于主副本的复制协议。当然还有基于多个存储节点的复制协议。比如下面会介绍的 Dynamo 系统的 NWR 复制协议。
故障检测
设计分布式系统的前提就是假定服务器时刻肯能发生故障。故障检测主要有心跳和租约两种机制。
- 心跳：假设总控机 A 需要确认工作机 B 是否发生故障，那么总控机 A 每隔一段时间，比如 1 秒，向工作机 B 发送一个心跳包。不足之处是若 A 到 B 网络发生故障，则不能确定是否是 B 不再提供服务。
- 租约：租约机制就是带有超时时间的一种授权。假设机器 A 需要检测机器 B 是否发生故障，机器 A 可以给机器 B 发放租约，机器 B 持有的租约在有效期内才允许提供服务，否则主动停止服务。机器 B 的租约快要到期的时候向机器 A 重新申请租约。租约机制可以解决上述心跳问题的不足。
一致性模型
说起数据一致性，简单说有三种类型（细分会有很多，此处不展开）：
- 弱一致性（Weak）：当你写入一个新值后，读操作在各个数据副本上不保证能读出最新值。比如：某些cache系统，网络游戏其它玩家的数据和你没什么关系。
- 最终一致性（Eventually）：Eventually 是 Weak 的一种特殊情况。当你写入一个新值后，有可能读不出来，但在某个时间窗口之后保证最终能读出来。比如：DNS，电子邮件、Amazon S3，Google搜索引擎这样的系统。
- 强一致性（Strong）：新的数据一旦写入，在任意副本任意时刻都能读到新值。比如：文件系统，RDBMS，Azure Table都是强一致性的。
从这三种一致型的模型上来说，我们可以看到，Weak 和 Eventually 一般来说是异步冗余的，而Strong一般来说是同步冗余的，异步的通常意味着更好的性能，但也意味着更复杂的状态控制。同步意味着简单，但也意味着性能下降。
分布式事务
事务的支持对于业务是非常重要的特性，数据库在单机下的 ACID 事务特性是比较到位的，而一旦进行分库分表后就要面对一致性和可用性的问题了，这就是分布式事务了。
CAP 原理
在分布式环境下需要考虑数据的一致性和性能的问题，我们要了解下 CAP 理论：
- 一致性：所有节点在同一时间具有相同的数据。
- 可用性：保证每个请求不管成功或者失败都有响应。我理解的是系统的性能。
- 分区容忍性：系统中任意信息的丢失或失败不会影响系统的继续运作。我理解的是系统的抗故障能力。
在分布式系统中，对于这三者不能同时满足。这就是 CAP 理论。
简单地说就是：
1）要想让数据避免单点故障，就得写多份数据。
2）写多份的问题会导致数据一致性的问题。
3）数据一致性的问题又会引发性能问题
NWR 模型
NWR是一种在分布式存储系统中用于控制一致性级别的策略，应用于 Amazon Dynamo。NWR 模型将 CAP 的选择权交给了用户，由用户自己选择 CAP 中的哪两个。其中，N 代表 N 个备份，W 代表至少写 W 份才认为成功，R 代表至少要读 R 份才认为成功。
- 如果 W+R>N ，是可以保证强一致性的。因为 W+R > N， 所以 R > N-W，什么意思呢？就是读取的份数必须要大于未成功写的份数，这样至少能读到一份最新值。
- 如果 W+R<=N，则能够保证最终一致性。
- 如果我们要高可写的环境，我们可以配置 W=1 R=N。这个时候只要写任何节点成功就认为成功，但是读的时候必须从所有的节点都读出数据。
- 如果我们要求读的高效率，我们可以配置 W=N R=1。这个时候任何一个节点读成功就认为成功，但是写的时候必须写所有三个节点成功才认为成功。
两阶段提交
英文 Two Phase Commit，也叫 2PC。两阶段提交经常用于分布式事务，是强一致性算法。简要的说就是分两阶段：
第一阶段，主控节点（协调者）询问所有节点（参与者）是否可以提交操作，参与者回应 yes or no。
第二阶段，协调者根据收到的响应，如果所有参与者都回应 yes，则向所有参与者发送“正式提交”的命令。参与者完成后恢复“完成”消息，协调者收集齐各节点的回应后结束这个 Global Transaction。如果有一个拒绝则给所有参与者发送“回滚操作”。参与者回滚成功后回应“回滚完成”，协调者收集各结点的“回滚”回应后，取消这个 Global Transaction。
2PC说白了就是第一阶段做 Vote，第二阶段做决定的一个算法，相对于单库事务来说就是在提交之前多了准备的阶段。但是也存在着问题，其中一个是同步阻塞操作，这个事情必然会非常大地影响性能。另一个主要的问题是在TimeOut上。因此出现了 3PC，主要是将提交过程分为两步，更多描述见 Wikipedia。
Paxos 算法
Google Chubby 的作者 Mike Burrows 说过，“世上只有一种一致性算法，那就是 Paxos”，所有其他一致性算法都是Paxos算法的残次版本。
Paxos是一个分布式选举算法， 最大的用途就是保持多个节点数据的一致性。看了好久的 Paxos 算法还是有些迷糊，这里就不给出具体算法了。感兴趣的可以参看 WikiPedia 以及里面给出的示例。
实际上对于一般的开发人员，我们并不需要了解 Paxos 所有细节及如何实现，只需要知道 Paxos 是一个分布式选举算法就够了。当我们以后遇到相似的问题，知道有这样一个技术，可以正确及优雅地解决技术架构上一些难题就够了。
小结
Paxos 协议和 2PC 协议在分布式系统中所起的作用并不相同。Paxos 协议用于保证同一个数据分片的多个副本之间的数据一致性。当这些副本分布到不同的数据中心时，这个需求尤其强烈。2PC 协议用于保证属于多个数据分片上的操作的原子性。这些数据分片可能分布在不同的服务器上，2PC 协议保证多台服务器上的操作要么全部成功，要么全部失败。可见 Paxos 的学术地位不一般。
Paxos 协议有两种用法:一种用法是用它来实现全局的锁服务或者命名和配置服务，例如 Google Chubby 以及 Apache Zookeeper 还有全局ID。另外一种用法是用它来将用户数据复制到多个数据中心，例如 Google Megastore 以及 Google Spanner。
2PC 协议最大的缺陷在于无法处理协调者宕机问题。如果协调者宕机，那么，2PC协议中的每个参与者可能都不知道事务应该提交还是回滚，整个协议被阻塞，执行过程中申请的资源都无法释放。因此，常见的做法是将 2PC 和 Paxos 协议结合起来，通过2PC 保证多个数据分片上的操作的原子性，通过 Paxos 协议实现同一个数据分片的多个副本之间的一致性。另外，通过 Paxos 协议解决 2PC 协议中协调者宕机问题。当 2PC协议中的协调者出现故障时，通过 Paxos 协议选举出新的协调者继续提供服务。
下图是几种策略原理的比较，来源于：Google App Engine的 co-founder Ryan Barrett在2009年的google i/o上的演讲《Transaction Across DataCenter》（视频）
图中 M/S 是 Master-Slave) 结构，实现简单，但是存在单点故障和数据丢失的问题。M/M 即 Multi-Master，解决了单点故障但是一致性的实现较复杂且存在冲突合并的问题（Vector Clock解决）。从上图我们可以看到，我们基本上来说不可以让所有的项都绿起来，也就是之前说到的著名的CAP理论：一致性，可用性，分区容忍性，你只可能要其中的两个。
分布式系统分类
分布式文件系统
分布式文件系统用于存储 Blob 对象，典型的系统有 Facebook Haystack 以及 Taobao File System(TFS)。分布式文件系统是分布式的基石，通常作为上层系统的底层存储。
总体上看，分布式文件系统存储三种类型的数据 :Blob 对象、定长块以及大文件。在系统实现层面，分布式文件系统内部按照数据块(chunk)来组织数据，每个 chunk 的大小大致相同，每个 chunk 可以包含多个 Blob 对象或者定长块，一个大文件也可以拆分为多个 chunk 。
分布式键值系统
分布式键值系统用于存储关系简单的半结构化数据，它只提供基于主键的 CRUD(Create/Read/Update/Delete)功能。
典型的系统有 Amazon Dynamo 以及 Taobao Tair。从数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统是分布式表格系统的一种简化实现，一般用作缓存，比如淘宝 Tair 以及 Memcache。一致性哈希是分布式键值系统中常用的数据分布技术。
分布式表格系统
分布式表格系统用于存储关系较为复杂的半结构化数据。分布式表格系统以表格为单位组织数据，每个表格包括很多行，通过主键标识一行，支持根据主键的 CRUD 功能以及范围查找功能。
典型的系统包括 Google Bigtable 以及 Megastore，Microsoft Azure Table Storage，Amazon DynamoDB 等。在分布式表格系统中，同一个表格的多个数据行也不要求包含相同类型的列，适合半结构化数据。
分布式数据库
分布式数据库一般是从单机关系数据库扩展而来，用于存储结构化数据。分布式数据库采用二维表格组织数据，提供 SQL 关系查询语言，支持多表关联，嵌套子查询等复杂操作，并提供数据库事务以及并发控制。
典型的系统包括 MySQL 数据库分片(MySQL Sharding)集群，Amazon RDS 以及Microsoft SQL Azure。分布式数据库支持的功能最为丰富，符合用户使用习惯，但可扩展性往往受到限制。当然，这一点并不是绝对的。Google Spanner 的扩展性就达到了全球级，它不仅支持丰富的关系数据库功能，还能扩展到多个数据中心的成千上万台机器。除此之外，阿里巴巴 OceanBase 也是一个支持自动扩展的分布式关系数据库。
摘录
书中有很多对于分布式的观点对我启发很大，将之引用如下。
- “Google的分布式存储系统一步步地从 Bigtable 到 Megastore，再到 Spanner，这也验证了分布式技术和传统关系数据库技术融合的必然性，即底层通过分布式技术实现可扩展性，上层通过关系数据库的模型和接口将系统的功能暴露给用户。” OceanBase 正是看准了这两种技术融合的必然性，才走向了可扩展的关系数据库道路。
“简单就是美。系统开发过程中，如果某个方案很复杂，一般是实践者没有想清楚。”。关于这一点其实很早就听说过，就像贯穿UNIX哲学的KISS原则（Keep It Simple,Stupid），而作者通过开发复杂的分布式存储系统过程中得出这么宝贵经验，是“简单就是美”最好的注解。
中心化 VS 去中心。“主流的分布式系统一般都带有中心节点，这样能够简化设计，而且中心节点只维护少量元数据，一般不会成为性能瓶颈。在实践中 Dynamo 及其开源实现 Cassandra 受到的关注逐渐减少，去中心的设计短期内难以成为主流。”
参考资料
- 杨传辉 :大规模分布式存储系统
- 酷壳：分布式系统的事务处理
