多图详解分布式高可用性典型——Dynamo DB

2022-04-08 15:13:10

多图详解分布式高可用性典型——Dynamo DB

分布式之DynamoDB

仔细思索分布式的CAP理论，就能发现P数据分区是分布式的特性，是必须满足的特点。如果一个系统没有数据分区的存在，那这样的系统就是单体，而不是分布式。CAP三个特性无法同时满足，那么所有的分布式系统实现都是在A(可用性)和C（一致性）之间权衡选择。

DynamoDB是Amazon的一个分布式的NOSQL数据系统，放弃了CAP的强一致性，保证高可用性。

DynamoDB是什么？

CAP只能保证满足AC中的一个，Dynamo的设计初衷是保证高可用，达到终一致性。

在分布式的环境里，强一致性协议也有很多，比如Raft就是这样的一种协议。但是Dynamo的目标不在于强一致性，可以认为Dynamo是完全去中心化的，满足AP，保证终一致性。

Dynamo的设计是非常有意思的，他的独特的思想和实现给业界带来了很大的冲击。

Dynamo数据分布模型：一致性哈希

在分布式系统里，数据不是存放在一个单体里面，而是需要均匀安全的存放在非常多的节点上面。数据怎么分布，是分布式系统要考虑的关键问题之一。

Dynamo的数据分布（数据分片，也叫分区）使用的模型是一致性哈希模型。

一致性哈希是什么

哈希环的表示如下所示，用一个环表示0-2^32-1之间的范围。

数据分布的每个节点对应一个随机值，是环上的某个点。按照一致性方向，哈希环上的一段区间都映射到这个节点上面来（也就是说这段数据将会存储到这个节点）。

但是这样可能导致数据分布不均匀，负载量小的机器可能分配到很大的一片数值空间，负载量大的机器反而可能分配到很小的一片数值空间。

虚拟节点

为了更好的利用物理机器的异构性，一致性哈希提出了虚拟节点的设计思路：一个机器分配N个随机值（N的大小跟机器的能力有关系），对应哈希环上的N个节点，如下图所示。

Tij表示i机器的第j个虚拟节点,这个Hash Ringm目前有两个节点T1和T2，T1有三个虚拟节点T11、T12和T13，T2有两个虚拟节点T21和T22 。假设他们按照这种方式分布在环上。

全部数值区间按照一致的方向去映射，比如T11对应的数值和T21对应数值之间的那一段的哈希值映射到虚拟节点T21上面。

Dynamo是一个纯粹的KV存储系统，这样的话每个key都会计算出一个哈希值，并存储到对应的虚拟节点上面（对应某一台机器）。

初始环

理解初始环的建立过程是虚拟节点建立一致性哈希的关键，建立过程如下图：

T1初始化作为种子节点,生成【0，2^32-1】范围内的三个随机数，随机数对应T11、T12和T13。
T2初始化，和种子节点联通，生成并上报自己生成的的random值序列T21、T22。
集群机器通过Gossip协议交换信息，这样大家都知道全局的虚拟节点地图了，也就是这个Hash Ring的分布图。

初始化的过程需要设置种子节点，各个节点通过gossip协议获得全局的哈希地图。之后按照各自负责的区域，来处理数据请求并分片存储，以及用相应的副本保证高可用性。

新的节点加入

有新的Node T3加入到系统， T3初始化，根据自己的存储和计算能力生成两个随机值T31和T32，并上报给种子节点T1，也从T1 获得现有的hash ring的地图，于是所有节点都获得新的地图

hash ring 的部分hash区间映射到的节点发生变化，对全局影响不大。 T12-T31之间的区间range1 原来是映射到T13, 需要从T13搬移到T31。另外一个虚拟节点那里也是类似的。

这体现了一致性哈希的好处，新增节点对数据搬移的开销小。

有节点离开

如下图，Node T2离开系统，则需要先迁移数据。

T11-T21之间的区间range3

原来是映射到T21, 需要从T21搬移这区间的数据到T12

T13-T22之间的区间range

原来是映射到T22, 需要从T22搬移到T32 后，移除T2的虚拟节点，生成新的地图。

可以看出，迁移数据的代价也很小。这也体现了一致性哈希的好处，移除节点对数据搬移的开销小。

gossip协议

gossip协议很好懂，就是随机选择节点并传播通信交换数据，也很好实现，而且很快就可以模拟一个来了解这块的细节。

数据分片和副本

在这个数据分布的一致性哈希模型下，哈希区间自然的将数据分片存储。如果没有多副本，系统很难保证高可用性。

副本是保证数据高可用的保证，但也需要保证各个副本之间的一致性，总之是带来了更大的系统开销。

Dynamo副本的存储如规则下：

假设系统设置的副本数N=3，则T21需要存储的数据包括range1,range2和range3。

一致性哈希总结

学习一致性哈希
分布式存储的基础
多台机器存数据
数据分片可扩张
多个备份能可靠
每个节点一范围
真实节点多虚拟
均匀散落哈希环
手拉手围一个环
数据存取也不难
哈希取模来映射
指定节点来存储
这些数据的备份
在接下来的节点
机器宕机也不怕
数据转移且均匀
节点心跳来交流
Gossip协议得全局

请求处理流程

DynamoDB系统是一个KV系统，客户端的请求很简单，基本是两类：PUT和GET。

PUT的时候考虑可用性和一致性的问题：

可用性就是说要多副本存储
一致性，数据一致性，多副本并发写能否保持一致

GET的时候也要考虑可用性和一致性的问题：

可用性就是说要选择一个可用的节点返回需要的数据？
一致性，数据一致性，如果有多个可用的数据，怎么合并解决冲突？

技术没有银弹，AC不可得兼。

可以发现所有的考量都是围绕可用性和一致性，下面详细说说这些过程和要考虑的一些问题。

put数据的处理流程？

客户端发送请求时，会选择协调模式。有两种：

客户端SDK协调
使用负载均衡服务器协调

不管是客户端协调还是负载均衡的协调，都要先选择一个节点作为主要负责put请求的逻辑，这个节点如果不可达，就换下一个可用的节点。

基本步骤：

SDK获取集群metadata信息，选择一个处理请求的节点。
处理请求的节点计算hash(key),如图，key和值要存储到T13，并且复制到T31和T12，所以处理节点将请求发给这三个节点，T1是处理节点，发送put指令给T13、T31和T12三个节点。
假设设置的W=2，则等待至少有一个replica复制成功才返回response给客户端。

当然在使用了Merkle Tree(后面会讲到这是优化一致性的一个数据结构)的情况下，会重新计算这棵树。

get数据的处理流程

同理，不管是客户端协调还是负载均衡的协调，都要先选择一个节点作为主要负责get的逻辑。

如图，这里使用负载均衡服务器

GET的时候，设置读R个节点可返回。

get(key=100)：

计算出key在T13，副本在T31和T12，处理节点T1给这些节点发送get指令
假设设置的R=2，则复制至少等这三个replica的其中两返回数据
根据策略合并结果返回response给客户端或直接返回全部让客户端去处理

向量时钟

Dynamo 使用向量时钟（vector clock）来跟踪同一对象不同版本之间的因果性。

一个向量时钟关联了一个对象的所有版本，可以通过它来判断对象的两个版本是否在并行的分支上，或者它们是否有因果关系。如果对象的个时钟上的所有 counter 都小于它的第二个时钟上的 counter，那个时钟就是第二的祖先，可以安全的删除；否则，这两个修改就是有冲突的，需要 reconciliation。

一个向量时钟就是一个 (node, counter) 列表。node表示处理数据的节点，如上面GET、PUT流程中说到的T1。

下图显示了一个场景：

在T1故障的时候，T2和T3可能都写入了数据，之后T1恢复解决冲突数据。