Amazon Dynamo 是分布式的 key-value 系统，最近阅读了 Dynamo 最初的论文 《Dynamo: Amazon's Highly Available Key-value Store》，本文想聊一聊它的去中心化（decentralization）。既有阅读相关材料后对其实现的理解，也有自己的思考，其中如有不正确言论欢迎指出。
中心节点
通常，我们见到的分布式存储结构都是具备中心（总控）节点的，比如 Google File System（GFS），包括了中心的 Master 和数据节点 Chunck Server；再比如 HDFS，包括了中心的 Name Node 和数据节点 Data Node。下面就以这两者为例来说明设置中心节点遇到的问题和解决。
中心节点通常包含了存储单元的分布信息，存储内容的元信息，“ 一致性” 是分布式系统的核心内容，而在处理一致性问题上，引入中心节点可以带来莫大的好处，但是，也容易引发问题：
- 单点故障：这个问题的解决主要靠热备，比如 GFS 就靠 Shadow Master。而 HDFS 情况比较复杂，在 Hadoop 2.0 以前靠的是 Secondary NameNode，它不是真正的 HA（High Availability），它只是阶段性的合并 edits 和 fsimage，以缩短集群启动的时间，因此在 Name Node 出问题的时候，它既不能保证立即提供服务，也不能保证数据的完整性；现在 HDFS 为保证 Name Node 的 HA，做法就很多了，包括了（1）shared image 或者是（2）data replication 的方法，这篇文章有系统的介绍。
（上图来自《HDFS HA: 高可靠性分布式存储系统解决方案的历史演进》）
- 扩展性，我们可以按照这样的思路来解决这个问题：
- 中心节点包括了两个基本职责，一个是文件系统的维护，它需要知道每个数据节点上的哪块空间存放了哪些数据；还有一个是对于数据请求的调度。这两个是可以拆开来的。
- 把单 Master 变成 Multi-master，Master 之间可以用不同的方式实现数据同步，这个方法的好处在于 Master 的水平扩展变得容易，问题还是在于一致性，如果不同的 Master 要操纵同一个数据节点上同一片数据，需要有专门的方式来处理冲突。
- 对于元文件信息量较大时会比较麻烦，比如 HDFS 上都是小文件，文件数量众多，存储效率低（这是 HDFS 不适宜的一个使用例子，在这篇文章里面我提到过），Name Node 的内存消耗大。要么就不要这么用，GFS 就比较适用于存放大文件；要么就从存储架构上解决，软件系统一个通用的办法是引入新的一个层，比如在 Name Node 和 Data Node 之间引入一个区域自治的层，这一层每一个节点分别自治管理一部分 Data Node，而都从属于 Name Node。
有趣的是，整个互联网就可以看做是一个巨大的分布式系统，经过了实践检验，我们可以认为它的的确确是去中心化的，但它也并不是每个维度都“ 去中心”，比如域名服务器，顶级域名服务器就是一个中心节点。因此如果仅仅是为了分布式，而粗暴地把中心节点去掉不是明智的，当然，Dynamo 做了尝试，下面我列出了一些去掉中心节点后带来的问题，和它的解决办法。
Dynamo 的去中心化
在上面提到了的 Dynamo 2007 年的论文中，就直白地强调了去中心化是 Dynamo 设计的一条重要原则：
Decentralization: An extension of symmetry, the design should favor decentralized peer-to-peer techniques over centralized control. In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.
Dynamo 的设计者已经意识到了中心化系统带来的问题，包括服务中断，因此要尽可能避免。其它还包括的设计原则有：
- Incremental scalability，增量扩展，减少对系统的影响；
- Symmetry，对称性，节点之间都是对等的；
- Heterogeneity，多相性（不知道怎么翻译更好），系统的扩展性可以按不同的比例落实到不同类型和能力的硬件上面去。
下图来自该论文，列出了遇到的问题和解决问题采用的技术，这是 Dynamo 设计的核心，而其中的大部分问题都是和去中心化相关的：
下面逐条叙述：
Partioning
采用一致性 Hash（Consistent Hashing）来解决节点增加和水平扩展的问题，带来的好处和设计原则中的增量扩展是一致的。它本身已经不是一个新话题了，介绍它的材料互联网上有很多，在此不赘述。Dynamo 的实现上有两点特别需要指出：
- 每一台物理设备都根据不同的能力折合成不同数量的虚拟节点数目；
- 每份数据都被映射到整个 hash 环上面的多个节点，从而形成 replication，保证可用性。
High availablity for writes
采用向量时钟（Vector Clock）来处理一致性问题，向量时钟实际上是一个 (node,counter) 对的列表，如下图：
D1 写入，发生在节点 Sx，形成向量时钟 [Sx,1]，Sx 又发生一次写，于是 counter 增加 1，变成了 [Sx,2]，之后基于它发生了 D3 和 D4 两次写入，于是出现了两个版本，([Sx,2],[Sy,1]) 和 ([Sx,2],[Sz,1])，在 D5 的时候协调，协调成 Sy 先于 Sz 发生，counter 再加 1。这里的协调有两种方式：
- last write wins，依赖于节点时钟，但是时钟之间无法做到绝对一致
- 客户端来决定
Handling temporary failures
Sloppy Quorum：草率的法定人数（这个不知道如何翻译），这里有一个有名的 NWR 机制，其中：
- N 表示复制的数据备份数量，
- W 表示同步确认成功的写操作的副本数（剩下 N-W 的写操作是异步进行的），
- R 表示同步确认成功的读操作的副本数（每次读通过比较前面提到的向量时钟/版本号来确定有效的副本）。
当 W+R>N 的时候，可以保证强一致性，对于这个定理，分类举例说明如下：
- 如果 W<R，例如 W=1，R=2，N=2，那么两份数据拷贝中，有一份同步写（有效数据），一份异步写（可能暂时无效），而有两份同步读，所以肯定能读到一份有效的数据；
- 如果 W=R，例如 W=1，R=1，N=1，这是最简单的“ 单库模式”，没有异步写；
- 如果 W>R，例如 W=2，R=1，N=2，两份写入都是同步写，因此读任意一份数据都是有效的。
通过协调 N、W、R 之间的值，就可以在一致性和可用性之间做 tradeoff（CAP 理论中 P 是无法牺牲的，而 C 和 A 是可以取舍的），因为 W 或 R 是同步的，因此基本上 W 或 R 的值越大，Availability 就越差。
Hinted Handoff：暗示的转交，如果写操作过程中节点 A 暂时不可用，可以自动将
该节点上的副本转交到别的节点去，这是为了保证副本总数不减少。而这个转交的数据会设置一个暗示的标记，等到节点 A 恢复了，会被重新转交回 A。
Recovering from permanent failures
使用 Merkle Tree 的反熵（anti-entropy）。Merkle 是这样一种数据结构，非叶子节点提供了多层 Hash 的功能：
反熵协议是用来帮助副本之间的同步的，使用 Merkle 的主要优点是每个分支可以独立地检查，而不需要下载整个树或整个数据集。
Membership and failure detection
基于 Gossip 的成员协议（membership protocol）和故障检测。Gossip 协议本身就是为了去中心化而设计的，虽然无法保证在某个时刻所有节点状态一致，但可以保证在某个最终的时刻一致。成员协议用于在 hash 环上增加或减去节点。
关于 Dynamo 的吐槽
对于 Dynamo 的去中心化，实在是功过兼备，毕竟引入了上面介绍的一堆复杂的机制，尤其对于数据的一致性问题，更是争议不小。使用一个 Master 节点，丢失了中心化，但是一致性的问题就容易解决得多，系统也会更简单；退一步说，如果要去中心化，但是使用 Paxos 这样的协议，来选举一个“Master” 出来，那也能比较简洁地保证一致性。但是 Dynamo 最后的实现，让用户来解决冲突的做法（有时候用户也没法确定该用哪个版本），确实有些别扭；而采用绝对时间来解决冲突的方法，则是在机制上有天生的缺陷（时间无法做到绝对同步）。
网上曾经有一篇很火的吐槽 《Dynamo: A flawed architecture – Part 1》，抱怨了一些 Dynamo 的问题，新浪的 Tim Yang 写了一篇文章简单翻译了一下，我就不再赘述，大致上抱怨的问题包括：
- 一致性方面，Dynamo 没有办法保证避免脏读；
- Quorum 机制中只是 R+W>N 在遇到节点不可用的时候，并不能保证强一致性；
- Hinted Handoff 机制在跨 IDC 的情况下，会因为异地传输开销而性能低下；
- 灾难恢复方面，某一个 IDC 挂掉的时候，没人可以计算到底丢了多少数据；
- 论文里面一些自相矛盾的地方，一个是对节点对等的描述，一个是对最终一致的描述；
- Dynamo 给用户造成了误导，以为一直是在 CAP 的 C 和 A 中必须做一个取舍，其实单节点中心就可以同时做到 CA；
- Dynamo 宣称去中心化，但是并没有完全做到，比如交换机故障造成网络分片的时候，服务就不可用了。
这篇文章的标题写着 part 1，只可惜 part 2 没有出现。这篇文章引起了不少争议，作者后来自己写了一篇 《Dynamo – Part I: a followup and re-rebuttals》来回应，文章结尾总结了一下他对 Dynamo 的观点：
- 尽量去避免脏读；
- 不受控的脏读任何时候都不可接受，即便在灾难发生的时候—— 就算数据丢失也比它要好得多，大多数情况下，管理员会关闭部分或者全部的服务，而不是去用丢失或者损坏的数据来响应用户
- 一个数据中心内的网络分片要避免，在一个数据中心内考虑 P（partition tolerance）是不合理的；
- 中心化并不意味着低 Availability，高可用的服务是可能的，虽然说 scalability 可能会成为问题；
- 开发设计的对称性并不能很好适应硬件和网络的非对称性；
- 数据中心一致性、高可用性和扩展性是可以同时达到的，只要在一个数据中心里面（也就是说 P 被放弃的时候），BigTable+GFS，HBase+HDFS，甚至 Oracle RAC 都是很好的例子；
- Dynamo 的读写即便在一个数据中心内也会引起脏读；
- 谁也不知道脏读避免的时间边界在哪里；
- 跨数据中心的情况下，没法跟踪有多少数据待更新，而灾难恢复的时候，也没法知道有多少数据丢失。
淘宝日照博客中的一篇文章，也谈到了 Dynamo 设计上的一些问题，特别是对于一致性和分区容忍性上面精彩的吐槽，推荐阅读。
文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》
如今 amazon 还在用 dynamo 么，传言已经废弃多年？