Understanding Dynamo

[读论文] Amazon Dynamo
今天这篇是经典的key-value数据库Amazon Dynamo，原文链接如下
https://www.allthingsdistributed ... dynamo-sosp2007.pdf


网上的中文论文或导读：
https://www.cnblogs.com/liangmou/p/7786345.html

https://blog.csdn.net/u013613428/article/details/59484498


================

设计考量：高可写（业务需求），replication（fault tolerance），conflict resolution由client来决定，对称性和去中心化（方便maintenance），Heterogeneity（针对不同能力的server assign不同的work load）。

Partitioning：
1. Consistent Hash
2. Virtual nodes for each server，这里论文里没有看到关于Heterogeneity的实现，不知道是不是看漏了。不过可以想象是通过能力强的server assign更多virtual node来实现。
3. 每一段key range replicate到N个virtual nodes。
4. 对整个key range先分bucket，然后在bucket range上进行consistent hashing，这样为了方便merkle tree的更新（后面再提）。

高可写：
1. Quorum机制：W + R > N 保证一致性，在任意replica上写，用vector lock记录version，读数据时进行reconsiliation；N越大越不怕data center failure，W越小越可写，R越小越可读，只要W+R>N则为强一致。
2. Sloppy Quorum and hinted handoff：对于transient failure，写操作会写到之后的其他node上保证W数量，这些node会记录他们是帮谁写的，一旦发现之前failure的node重新上线，就写回去。

去中心化：
1. gossip协议，能够传播partition的信息，node状态，merkle tree。
2. Merkle Tree，每个节点，对于自己存储的每一段key range，建立merkle tree，通过与另外一个replica比较一段range的hash值来决定是否需要sync，而不需要传播和比较所有值。
3. Merkle Tree的特点使得我们需要Partition 3的操作：先把key range分bucket。否则一旦有新的node加入进来，在转移data的同时，我们需要扫描data，重新进行hash的计算，因为data partitioning和merkle tree的key range partitioning并不一致。而如果我们通过分bucket让他们保持一致，则只需要把merkle tree的一部分子树转移到另一个节点上，并重新计算一下向上的根结点的hash就可以了。

可复用知识点：
1. Consistent Hash - virtual nodes - bucketed key range
2. Quorum - 可定制的WRN对应不同需求
3. 通过Merkle Tree比较数据
4. 通过gossip 协议 去中心化的维持node状


http://www.raychase.net/2396

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写了一篇文章简单翻译了一下，我就不再赘述，大致上抱怨的问题包括：

1. 一致性方面，Dynamo没有办法保证避免脏读；
2. Quorum机制中只是R+W>N在遇到节点不可用的时候，并不能保证强一致性；
3. Hinted Handoff机制在跨IDC的情况下，会因为异地传输开销而性能低下；
4. 灾难恢复方面，某一个IDC挂掉的时候，没人可以计算到底丢了多少数据；
5. 论文里面一些自相矛盾的地方，一个是对节点对等的描述，一个是对最终一致的描述；
6. Dynamo给用户造成了误导，以为一直是在CAP的C和A中必须做一个取舍，其实单节点中心就可以同时做到CA；
7. 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设计上的一些问题，特别是对于一致性和分区容忍性上面精彩的吐槽，推荐阅读。

http://ying.ninja/?p=843

Dynamo: Amazon’s Highly Available Key-value Store

1. System Assumptions and Requirements in this case

   1. High write availability (this is based on their use cases like shopping carts, user should be able to update the shopping carts anytime). So the design is also writable and resolve conflicts when read.
   2. Query model is simple read and write operations to a data item which is uniquely identified by unique keys. No need for relational schemas. (Which is also based on the observation of some Amazon’s services.)
   3. ACID(Atomicity, Consistency, Isolation, Durability) are not strictly followed since it targets applications that tolerant weaker consistency, which is called eventually consistency.

2. Design Considerations

   1. When to resolve update conflicts? Read or Write?
      1. Since it focus on high write availability, so it pushes conflict resolution to reads (which unlike many traditional DBs which execute conflict resolution during writes and has simple policy for reads)
   2. Who to resolve the conflicts? The data store or application?
      1. The application is responsible to resolve conflict updates. Since data store only has simple police like “last write wins” to resolve conflicts while application has more knowledge of each different situations and could have different strategy to resolve conflicts.
   3. Incremental scalability
      1. Add/Delete one node at a time without having a huge impact on both read/writes of the system.
   4. Symmetry
      1. No outstanding nodes. Each node should have the same responsibilities as its peers.

http://blog.ddup.us/2011/11/07/amazon-dynamo/
http://jsensarma.com/blog/?p=64
Stale Reads are bad. We should do our utmost to not have them if they can be avoided.
Unbounded Stale Reads are pure evil and unacceptable. Even under disaster scenarios – applications expect finite/bounded data loss. In most cases – admins will prefer to bring down a service (or parts of it) rather than take unbounded data loss/corruption.
Network Partitions within a data center can (and are) avoided by redundant network connectivity (they are usually intolerable). Designing for partition tolerance within a data center does not make sense.
Centralization does not mean low availability. Very high availability central services can be built – although scalability can be a concern.
The notion of Symmetry as a deployment and design principle does not model well the asymmetry that is inherent in hardware configurations and networking
Consistency, high availability and scalability are simultaneously achievable in a data center environment (that does not have partitions). BigTable+GFS, HBase+HDFS (perhaps even an Oracle RAC database) are good examples of such systems. Strong Consistency means that these systems do not suffer from stale reads
Dynamo’s read/write protocols can cause stale reads even when deployed inside a single data center
No bound can be put on the degree of staleness of such reads (which is, of course, why the system is described as eventually consistent).
When deployed across data centers, there is no way in Dynamo to track how many pending updates have not been reflected globally. When trying to recover from a disaster (by potentially changing quorum votes) – the admin will have no knowledge of just how much data has been lost (and will be possibly corrupted forever).