Amazon云计算AWS之[1]基础存储架构Dynamo

Dynamo概况

• 面向服务的Amazon平台基本架构
• 为了保证其稳定性，Amazon的系统采用完全的分布式、去中心化的架构
• 作为底层存储架构的Dynamo也同样采用无中心的模式
• Dynamo只支持简单的键/值（key/value）方式的数据存储，不支持复杂的查询
• Dynamo中存储的是数据值的原始形式，即按位存储，并不解析数据的具体内容，使得Dynamo几乎可以存储所有类型的数据
  

Dynamo架构的主要技术

主要问题及解决方案

• Dynamo在设计时被定位为一个基于分布式存储架构的，高可靠、高可用且具有良好容错性的系统。
• Dynamo设计时面临的主要问题及所采取的解决方案

Dynamo的存储节点

• Dynamo中的存储节点呈无中心的环状分布。
  
  
• 通常，coordinator 是 preference list 上的第一个节点

数据均衡分布的问题

• Dynamo采用分布式的数据存储架构，均衡的数据分布可以保证负载平衡和系统良好的扩展性。 所以，如何在各个节点上数据的均衡性是影响Dynamo性能的关键问题。

• Dynamo中使用改进后的一致性哈希算法，并在此基础上进行数据备份，以提高系统的可用性。

一致性哈希算法

• 一致性哈希算法是目前主流的分布式哈希表（Distributed Hash Table，DHT）协议之一，于1997年由麻省理工学院提出。
• 一致性哈希算法通过修正简单哈希算法，解决了网络中的热点问题，使得DHT（分布式哈希表）可以真正地应用于P2P环境中。
• 对于系统中的每个设备节点，为其分配一个随机的标记，这些标记可以构成一个哈希环。
• 在存储数据时，计算出数据中键的哈希值，将其存放到哈希环顺时针方向上第一个标记大于或等于键的哈希值的设备节点上。
• 一致性哈希算法除了能够保证哈希运算结果充分分散到整个环上外，还能保证在添加或删除设备节点时只会影响到其在哈希环中的后继设备节点，而不会对其他设备节点产生影响。
  
  
• 一致性哈希算法可以大大降低在添加或删除节点时引起的节点间的数据传输开销

改进一致性哈希算法

• 一致性哈希算法在设备节点数量较少的情况下，有可能造成环上节点分布的不均匀；并且没有考虑哈希环上不同设备节点的性能差异。

• Dynamo中引入虚拟节点的概念。
  
• Dynamo中引入了虚拟节点的概念。每个虚拟节点都隶属于某一个实际的物理节点，一个物理节点根据其性能的差异被分为一个或多个虚拟节点。 各个虚拟节点的能力基本相当，并随机分布在哈希环上。
• 数据对象先按照其键的哈希值被分配到某个虚拟节点上，并存储在该虚拟节点所对应的物理节点中。

---

• 为进一步提高数据分布的均衡性。Dynamo将整个哈希环划分成Q等份，每个等份称为一个数据分区（Partition）。
• 在存储数据时，每个数据会被先分配到某个数据分区，再根据负责该数据分区的虚拟节点，最终确定其所存储的物理节点。
• 假设系统中有$S$个虚拟节点，且$Q>>S$，则每个虚拟节点负责的数据分区数为$V=Q/S$。

• 数据分区的好处

1. 减小数据分布不均衡的可能性
2. 添加或删除设备节点时引起较小的数据传输

数据备份

• 为提高数据的可用性，Dynamo中在存储每个数据对象时，保存其多个副本作为冗余备份。假设每个数据对象保存在系统中的副本数为N（通常为3），考虑到存在节点失效的情况，preference list中节点的个数大于N，并且为实际的物理节点。
• 在Dynamo中，每个数据的副本备份存储在哈希环顺时针方向上该数据所在虚拟节点的后继节点中。 某个数据对象的键为k，其数据存储在虚拟节点A中，则其数据副本将按顺时针方向存储在虚拟节点B、C上。

• 数据备份在存储数据的同时进行，会使每次写操作的延时变长。Dynamo中对写操作进行了优化，保证一个副本必须写入硬盘，其他副本只要写入节点的内存即返回写成功。
• 每个虚拟节点上实际存储了分配给它以及分配它的前N-1个前驱虚拟节点的数据。

数据冲突问题

• Dynamo选择通过牺牲一致性来保证系统的可靠性和可用性，没有采用强一致性模型而采用最终一致性模型。
• 由于Dynamo中可能出现同一个数据被多个节点同时更新的情况，且无法保证数据副本的更新顺序，这有可能会导致数据冲突。
• Dynamo中采用向量时钟技术（Vector Clock）解决数据冲突问题。
• Dynamo中的向量时钟通过$[node,counter]$来表示，node表示操作节点；counter是其对应的计数器，初始值为$0$节点每进行一次更新操作则计数器加 $1$

---

常用的解决冲突的方案有两种：

1. 通过客户端由用户来解决；
2. 系统自动选择时间戳最近的版本

• 由于集群内的各个节点并不能严格保证时钟同步，所以不能完全保证最终版本的准确性。
• 向量时钟的数量是有限制的，当超过限制时将会根据时间戳删除最早的向量时钟
  

1. 客户端请求写入一个新对象。节点$S_x$处理对$key$的写：序列号递增，并创建数据的向量时钟，在该节点上生成对象D1和向量时钟$[(S_x,1)]$。

2. 客户端更新该对象。假设由同样的节点即$S_x$处理这个请求，由于该节点有$D_1$和向量时钟$[(S_x,1)]$，则更新该对象后在该节点上生成对象$D_2$和向量时钟$[(S_x,2)]$，$D_2$继承自$D_1$，即$D_2$覆写$D_1$，计数器增$1$，但其它节点此时可能是$D_1$，也可能是$D_2$(取决于网络和节点状态)

3. 假设同一客户端更新该对象但被不同的服务器处理。节点$S_y$处理这个请求，则更新该对象后在该节点上生成对象$D_3$和向量时钟$[(S_x,2),(S_y,1)]$。

4. 假设另一客户端读取到$D_2$并尝试更新它但被另一个不同的服务器处理。节点$S_z$处理了这个请求，则更新该对象后在该节点上生成对象$D_4$和向量时钟$[(S_x,2),(S_z,1)]$。

5. 节点数据版本回收。现在有4个版本的数据存在并在各个节点之间传递了，当节点收到$D_3$或$D_4$时，会根据向量时钟将#D_1#和#D_2#回收掉，因为其是$D_3$和$D_4$的祖先。但是收到$D_3$和$D_4$的节点，根据向量时钟发现它们之间是并行关系，则保留二者，并在客户端get时将二者都提交给客户端由其来协调并合并版本。

   • 假设客户端读取数据，则会获取到$D_3$和$D_4$，根据两者的向量时钟，会合并为$D_5$和向量时钟$[(S_x,2),(S_y,1),(S_z,1)]$，节点$S_x$协调写操作，并更新对象和向量时钟。

成员资格及错误检测

• 由于Dynamo采用了无中心的架构，每个成员节点都需要保存其他节点的路由信息。为保证每个节点都能拥有最新的成员节点信息，Dynamo中采用了一种类似于Gossip（闲聊）协议的技术，每个节点间隔固定时间（1秒）从其他节点中任意选择一个与之通信。
• 通信连接成功后，双方交换各自保存的系统中节点的负载、路由等信息。
  
• Dynamo中还通过Gossip来实现错误检测。任何节点向其他节点发起通信后，如果对方没有回应，则认为对方节点失效，并选择别的节点进行通信。发起通信的节点定期向失效节点发出消息，如果对方有回应，则可以重新建立通信。

---

• 为避免新加入的节点之间不能及时发现其他节点的存在，Dynamo中设置一些种子节点（Seed Node）。种子节点和所有的节点都有联系。当新节点加入时，它扮演一个中介的角色，使新加入节点之间互相感知。
  
• 假如一新节点加入节点总数为$N$的系统，并以最优的方式进行传播（即每次通信的两个节点都是第一次交换新节点信息），那么将新节点信息传遍整个系统需要的时间复杂度为$logn$。
• 自底向上每一层代表一次随机通信。第一层节点1将信息交换给节点2；第二层节点1和2同时开始随机选择其他节点交换信息，比如节点1向节点3发送信息，节点2向节点4发送信息；以此类推，直到N个节点全部传遍。
• 整个过程形成一个倒的二叉树，树高为$logn$。显然，当N的值很大时，传播时间会变长，因此，Dynamo中的节点数不能太多。
• 根据Amazon的实际经验，当节点数N在数千时，Dynamo的效率是非常高的；但当节点数$N$增加到数万后，效率就会急剧下降。为此，Amazon采用了分层Dynamo结构来解决该问题$[1，40]$。
  

容错机制

临时故障处理机制

• 为处理机器假死等临时失效的节点，Dynamo中采用了一种带有监听的数据回传机制。
• 当虚拟节点A失效后，会将数据临时存放在节点D的临时空间中，并在节点A重新可用后，由节点D将数据回传给节点A。

• 节点D是preference list里的最后一个节点。

• 每个节点对应的都有一个自己作为coordinator的preference list
  

永久性故障处理机制

• 节点失效超过设定时间仍不能重用，认定为永久性故障。此时，Dynamo需要从其他数据副本进行数据同步

• Dynamo采用Merkle哈希树技术来加快检测和减少数据传输量。