Dynamo概况
- 面向服务的Amazon平台基本架构
- 为了保证其稳固性，Amazon的体系采用完全的分布式、去中心化的架构
- 作为底层存储架构的Dynamo也同样采用无中心的模式
- Dynamo只支持简朴的键/值（key/value）方式的数据存储，不支持复杂的查询
- Dynamo中存储的是数据值的原始形式，即按位存储，并不剖析数据的具体内容，使得Dynamo险些可以存储所有类型的数据
Dynamo架构的重要技术
重要问题及解决方案
- Dynamo在设计时被定位为一个基于分布式存储架构的，高可靠、高可用且具有良好容错性的体系。
- Dynamo设计时面对的重要问题及所接纳的解决方案
问题接纳的相干技术数据均衡分布改进的一致性哈希算法数据备份参数可调的弱quorum机制数据冲突处置惩罚向量时钟 (Vector Clock)成员资格及错误检测基于Gossip协议的成员资格和错误检测临时故障处置惩罚Hintedhandoff（数据回传机制）永世故障处置惩罚Merkle哈希树 Dynamo的存储节点
- Dynamo中的存储节点呈无中心的环状分布。
- 通常，coordinator 是 preference list 上的第一个节点
数据均衡分布的问题
- Dynamo采用分布式的数据存储架构，均衡的数据分布可以保证负载均衡和体系良好的扩展性。 所以，如何在各个节点上数据的均衡性是影响Dynamo性能的关键问题。
- Dynamo中使用改进后的一致性哈希算法，并在此基础上进行数据备份，以提高体系的可用性。
一致性哈希算法
- 一致性哈希算法是如今主流的分布式哈希表（Distributed Hash Table，DHT）协议之一，于1997年由麻省理工学院提出。
- 一致性哈希算法通过修正简朴哈希算法，解决了网络中的热点问题，使得DHT（分布式哈希表）可以真正地应用于P2P环境中。
- 对于体系中的每个装备节点，为其分配一个随机的标记，这些标记可以构成一个哈希环。
- 在存储数据时，计算出数据中键的哈希值，将其存放到哈希环顺时针方向上第一个标记大于或即是键的哈希值的装备节点上。
- 一致性哈希算法除了可以大概保证哈希运算结果充实分散到整个环上外，还能保证在添加或删除装备节点时只会影响到其在哈希环中的后继装备节点，而不会对其他装备节点产生影响。
- 一致性哈希算法可以大大低沉在添加或删除节点时引起的节点间的数据传输开销
改进一致性哈希算法
- 一致性哈希算法在装备节点数目较少的环境下，有可能造成环上节点分布的不均匀；并且没有考虑哈希环上不同装备节点的性能差别。
- Dynamo中引入捏造节点的概念。
- Dynamo中引入了捏造节点的概念。每个捏造节点都从属于某一个实际的物理节点，一个物理节点根据其性能的差别被分为一个或多个捏造节点。 各个捏造节点的能力基本相称，并随机分布在哈希环上。
- 数据对象先按照其键的哈希值被分配到某个捏造节点上，并存储在该捏造节点所对应的物理节点中。
- 为进一步提高数据分布的均衡性。Dynamo将整个哈希环分别成Q等份，每个等份称为一个数据分区（Partition）。
- 在存储数据时，每个数据会被先分配到某个数据分区，再根据负责该数据分区的捏造节点，最终确定其所存储的物理节点。
- 假设体系中有 S S S个捏造节点，且 Q > > S Q>>S Q>>S，则每个捏造节点负责的数据分区数为 V = Q / S V=Q/S V=Q/S。
- 减小数据分布不均衡的可能性
- 添加或删除装备节点时引起较小的数据传输
数据备份
- 为提高数据的可用性，Dynamo中在存储每个数据对象时，保存其多个副本作为冗余备份。假设每个数据对象保存在体系中的副本数为N（通常为3），考虑到存在节点失效的环境，preference list中节点的个数大于N，并且为实际的物理节点。
- 在Dynamo中，每个数据的副本备份存储在哈希环顺时针方向上该数据地点捏造节点的后继节点中。 某个数据对象的键为k，其数据存储在捏造节点A中，则其数据副本将按顺时针方向存储在捏造节点B、C上。
- 数据备份在存储数据的同时进行，会使每次写操作的延时变长。Dynamo中对写操作进行了优化，保证一个副本必须写入硬盘，其他副本只要写入节点的内存即返回写乐成。
- 每个捏造节点上实际存储了分配给它以及分配它的前N-1个前驱捏造节点的数据。
数据冲突问题
- Dynamo选择通过牺牲一致性来保证体系的可靠性和可用性，没有采用强一致性模型而采用最终一致性模型。
- 由于Dynamo中可能出现同一个数据被多个节点同时更新的环境，且无法保证数据副本的更新次序，这有可能会导致数据冲突。
- Dynamo中采用向量时钟技术（Vector Clock）解决数据冲突问题。
- Dynamo中的向量时钟通过 [ n o d e , c o u n t e r ] [node, counter] [node,counter]来表示，node表示操作节点；counter是其对应的计数器，初始值为 0 0 0节点每进行一次更新操作则计数器加 1 1 1
常用的解决冲突的方案有两种：
- 通过客户端由用户来解决；
- 体系自动选择时间戳近来的版本
- 由于集群内的各个节点并不能严酷保证时钟同步，所以不能完全保证最终版本的准确性。
- 向量时钟的数目是有限制的，当超过限制时将会根据时间戳删除最早的向量时钟
- 客户端请求写入一个新对象。节点 S x S_x Sx处置惩罚对 k e y key key的写：序列号递增，并创建数据的向量时钟，在该节点上生成对象D1和向量时钟 [ ( S x , 1 ) ] [(S_x, 1)] [(Sx,1)]。
- 客户端更新该对象。假设由同样的节点即 S x S_x Sx处置惩罚这个请求，由于该节点有 D 1 D_1 D1和向量时钟 [ ( S x , 1 ) ] [(S_x, 1)] [(Sx,1)]，则更新该对象后在该节点上生成对象 D 2 D_2 D2和向量时钟 [ ( S x , 2 ) ] [(S_x, 2)] [(Sx,2)]， D 2 D_2 D2继承自 D 1 D_1 D1，即 D 2 D_2 D2覆写 D 1 D_1 D1，计数器增 1 1 1，但其它节点此时可能是 D 1 D_1 D1，也可能是 D 2 D_2 D2(取决于网络和节点状态)
- 假设同一客户端更新该对象但被不同的服务器处置惩罚。节点 S y S_y Sy处置惩罚这个请求，则更新该对象后在该节点上生成对象 D 3 D_3 D3和向量时钟 [ ( S x , 2 ) , ( S y , 1 ) ] [(S_x, 2), (S_y, 1)] [(Sx,2),(Sy,1)]。
- 假设另一客户端读取到 D 2 D_2 D2并尝试更新它但被另一个不同的服务器处置惩罚。节点 S z S_z Sz处置惩罚了这个请求，则更新该对象后在该节点上生成对象 D 4 D_4 D4和向量时钟 [ ( S x , 2 ) , ( S z , 1 ) ] [(S_x, 2), (S_z, 1)] [(Sx,2),(Sz,1)]。
- 节点数据版本回收。如今有4个版本的数据存在并在各个节点之间传递了，当节点收到 D 3 D_3 D3或 D 4 D_4 D4时，会根据向量时钟将#D_1#和#D_2#回收掉，因为其是 D 3 D_3 D3和 D 4 D_4 D4的先人。但是收到 D 3 D_3 D3和 D 4 D_4 D4的节点，根据向量时钟发现它们之间是并行关系，则保留二者，并在客户端get时将二者都提交给客户端由其来协调并合并版本。
- 假设客户端读取数据，则会获取到 D 3 D_3 D3和 D 4 D_4 D4，根据两者的向量时钟，会合并为 D 5 D_5 D5和向量时钟 [ ( S x , 2 ) , ( S y , 1 ) , ( S z , 1 ) ] [(S_x, 2), (S_y, 1), (S_z, 1)] [(Sx,2),(Sy,1),(Sz,1)]，节点 S x S_x Sx协调写操作，并更新对象和向量时钟。
成员资格及错误检测
- 由于Dynamo采用了无中心的架构，每个成员节点都需要保存其他节点的路由信息。为保证每个节点都能拥有最新的成员节点信息，Dynamo中采用了一种类似于Gossip（闲聊）协议的技术，每个节点隔断固定时间（1秒）从其他节点中恣意选择一个与之通信。
- 通信毗连乐成后，双方互换各自保存的体系中节点的负载、路由等信息。
- Dynamo中还通过Gossip来实现错误检测。任何节点向其他节点发起通信后，如果对方没有回应，则以为对方节点失效，并选择别的节点进行通信。发起通信的节点定期向失效节点发出消息，如果对方有回应，则可以重新建立通信。
- 为克制新加入的节点之间不能及时发现其他节点的存在，Dynamo中设置一些种子节点（Seed Node）。种子节点和所有的节点都有接洽。当新节点加入时，它饰演一个中介的角色，使新加入节点之间相互感知。
- 如果一新节点加入节点总数为 N N N的体系，并以最优的方式进行传播（即每次通信的两个节点都是第一次互换新节点信息），那么将新节点信息传遍整个体系需要的时间复杂度为 l o g n logn logn。
- 自底向上每一层代表一次随机通信。第一层节点1将信息互换给节点2；第二层节点1和2同时开始随机选择其他节点互换信息，比如节点1向节点3发送信息，节点2向节点4发送信息；以此类推，直到N个节点全部传遍。
- 整个过程形成一个倒的二叉树，树高为 l o g n logn logn。显然，当N的值很大时，传播时间会变长，因此，Dynamo中的节点数不能太多。
- 根据Amazon的实际履历，当节点数N在数千时，Dynamo的服从是非常高的；但当节点数 N N N增加到数万后，服从就会急剧降落。为此，Amazon采用了分层Dynamo布局来解决该问题 [ 1 ， 40 ] [1，40] [1，40]。
容错机制
临时故障处置惩罚机制
- 为处置惩罚呆板假死等临时失效的节点，Dynamo中采用了一种带有监听的数据回传机制。
- 当捏造节点A失效后，会将数据临时存放在节点D的临时空间中，并在节点A重新可用后，由节点D将数据回传给节点A。
- 节点D是preference list里的最后一个节点。
- 每个节点对应的都有一个自己作为coordinator的preference list
永世性故障处置惩罚机制
- 节点失效超过设定时间仍不能重用，认定为永世性故障。此时，Dynamo需要从其他数据副本进行数据同步
- Dynamo采用Merkle哈希树技术来加快检测和减少数据传输量。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
