Dynamo分布式键值系统

2017-04-09 by subond

分布式键值模型是分布式表格模型的一种特例,一般只支持单个key-value的“增、删、查、改”操作,因此适用 哈希分布算法。Amazon Dynamo是分布式键值系统,学习Dynamo的设计思想,设计原则,对理解分布式系统理论很有帮助。

Amazon Dynamo

Dynamo以简单的键值方式存储数据,且存储的是数据的原始形式,不解析数据的内容。以下是Dynamo设计中面临的问题及解决方案,接下来依次查看。

Dynamo设计

数据分布

改进的一致性哈希算法(也称为一致性哈希表,简称DHT)的思想是:每一个物理节点根据其性能的差异分配多个token,每个token对应一个“虚拟节点”。每个虚拟节点的处理能力相当,并 随机分布 在哈希空间中,存储时,数据根据哈希值落在某个虚拟节点的负责的区域中,然后被存储在该虚拟节点对应的物理节点上。

改进的哈希一致性算法

为了找到数据所属的节点,Dynamo系统中 每个节点维护整个集群的信息,客户端也缓存整个集群的信息。与此同时,为了保证每个节点缓存是Dynamo系统中最新的集群信息,所有节点每隔固定时间 通过 Gossip协议 从其他节点中任意一个与之通信的节点。如果连接成功,双方交换各自保存的集群信息

【补充】:Gossip协议

Gossip协议用于P2P系统中自洽的节点协调对整个集群的认识,比如集群的节点,负载情况等。一个简单的例子是这样的(集群中节点A和节点B交换对集群的认识)。

1)A告诉B其管理的所有节点的版本(包括Down状态和Up状态的节点)
2)B告诉A哪些版本比较旧,哪些版本它有最新的,然后把那些最新的版本发给A(处于Down状态下的版本由于没有更新,所有不会被关注)
3)A将B中比较旧的版本发给B,同时将B发来的最新节点信息做本地更新
4)B收到A发来的最新节点信息,然后做本地更新

一致性和复制

Dynamo系统中对副本的管理思想是:假设数据存储N份,DHT定位到数据存储所属的节点K,则将数据存储在节点K, K+1, ..., K+N-1。如果第k+i(0<=i<=N-1)台机器,则往后找一台机器K+N临时替代。如果K+i台机器重启,临时替代的机器K+N能够通过Gossip协议发现,并把临时数据归还K+i,这个过程称为“消息回传”。

Dynamo中的NWR机制,其中N表示副本数,R表示成功读取操作的最少节点数,W表示成功写操作的最少节点数。只要满足W+R>N,可以保证当存在不超过一台机器故障时,至少能够读到一份有效的数据。由于每个节点存储的集群信息有所不同,可能出现同一条记录被多个节点同时更新,但不能多个节点之间的更新顺序。因此,Dynmao利用 向量时钟 技术了解决冲突。

向量时钟机制如下:

[nodes, counter]:其中nodes表示节点,counter表示计数器,初始为0,节点每次更新操作加1。

向量时钟

容错

Dynamo中异常分为两种:临时性异常和永久性异常。Dynamo中的容错机制包括:

1)数据回传
2)Merkle树同步。当出现永久性异常时,利用Merkle树机制从其他副本进行数据同步。其原理是,每个非叶子节点对应多个文件(为其所有节点值组合以后的哈希值);叶子节点对应单个数据文件(为文件内容的哈希值)。因此,任何一个数据文件不匹配都将导致从该文件对应的叶子节点到根节点的所有节点值不同。每台机器对每一段范围的数据维护一棵Merkle树,机器同步时首先传输Merkle树信息,并且只需要同步从根到叶子的所有节点值均不同的文件。
3)读取故障

负载均衡

Dynamo的负载均衡取决于如何给每个机器分配虚拟节点号,即token。一般有两种方法,如下所述。

第一种,随机分配。每台物理节点加入时根据其配置情况随机分配S个Token。优缺点是:可控性差,新节点加入/删除时,集群中的原有节点都需要扫描所有的数据从而找出属于新节点的数据,Merkle树也需要全部更新。

第二种,数据范围等分+随机分配。其思想是将数据额哈希空间等分为Q = N x S份(N = 机器数,S = 每台机器的虚拟节点数),然后每台机器随机选取S个分割点作为Token。优缺点:每台机器都可以对属于每个范围的数据维护一棵逻辑上的Merkle树,新节点加入/删除,只需要扫描部分数据进行同步,并更新这部分数据对应的逻辑Merkle树。

读写流程

Dynamo的读写流程如下图所示。

写操作流程

1) 根据一致性哈希算法计算出每个副本所在的存储节点,然后选取一个副本作为协调者。

2)协调者 并发 地往所有其他副本发送写请求,并将数据写入本地;如果发送写请求失败,协调者将它加入重试列表并不断重试。

3)当副本接收到数据后,成功写入本地,并回复协调者

4)等到W-1(协调者写入成功)个副本回复写入成功后,协调者恢复客户端写入成功;并继续等待或重试,直到所有副本写入成功。

读操作流程

1)根据一致性哈希算法计算出每个副本所在的存储节点,然后选取一个副本作为协调者

2)协调者根据负载策略选择R个副本,并发 地向它们发送请求,并读取本地数据。

3)每个副本读取本地数据,回复协调者读取结果。

4)等到R-1个副本读取成功后,回复客户端。分两种情况,一种是,R个副本返回的数据一致,则将读取结果回复客户端;另一种是根据 冲突处理机制 (根据修改的时间戳选择最新数据)合并多个副本的读取结果,然后回复客户端。