Amazon Dynamo的论文做为NoSQL的分布式模型论文中的白皮书,必然也是阅读的第一篇文章,当时读完后对最终一致性,quorum-like以及hinted handoff的概念和去中心化的存储设计有一些记忆外加简单的理解,最近又读了一些有关这个最初模型的文章,大致记录一下。

Dynamo设计的几个原则:

数据分区分布采用一致性哈希(consistent hashing)算法,并结合虚拟节点的思想(virtual nodes)来抑制数据分布存在的不均匀性。

备份之间的不一致采用向量时钟(vector clock)进行冲突解决与合并。

存储过程中采用quorum-like机制,使得R + W > N来保持一致性,如果出现节点失效,采用hinted handoff策略。

当节点加入或者离开Dynamo,数据之间的校验采用merkle tree。

Query Model: 提供简单的读写操作,所有的操作对象都用一个key来标识,对象以blob形式存储,由于所有的操作都只局限在一个data item上,因此不需要传统数据库关系模型以Amazon也在论文中说明适用于那些需要弱一致性,高并发型的application。

Dynamo为了保证Efficiency,提供了一些可配置的选项,从而使得可以满足需要的延迟、吞吐率等等。这些配置会在性能,开销,可用性等方面进行权衡。

乐观的复制策略和最终一致性(即所有的数据备份最终会达到一致),会带来数据的冲突,必须进行检测和解决,检测和解决的问题。Dynamo对冲突的检测和解决提供的方式是,由client在read操作时进行检测和解决。在read操作中进行冲突的解决,即客户端读取到多个备份的数据后进行时钟向量比较,从而判断是否冲突并解决,由read操作来解决冲突可以保证write操作永远不会被拒绝,即always writable。此外,由于client application才会关心存储数据的结构,因此由client来检测和解决冲突是合适的。

zero-hop DHT: Dynamo每一个节点都在本地保存了足够的路由信息使得请求可以直接的转发的对应节点,即被设计为一个zero-hop DHT。在论文最后的discussion中又提到了,由于每一个节点本地保存了大量的整个Dynamo的路由信息,使得Dynamo中的节点数扩展到很大的一个量时是无意义的,因为路由信息会过大,论文中提出了一个引入层次化设计模型来解决此问题的思路。但通过和西门大牛的聊天,业界比较流行采用zookeeper模型来存储路由规则解决此类问题。

virtual node: 数据分布采用一致性哈希,但带来了两个问题,一是随机分配时候产生的不均匀性,另外一个是并没考虑每个节点的能力。Dynamo采用了虚拟节点的解决方案,此方案的优点除了可以是负载有效的分担外,当节点失效时负载可以分散到多台机器上,而节点加入时也可以从其他节点获取大致相等的负载,另外可以根据物理节点的能力来划分虚拟节点的个数。

preference list: preference list是一个索引列表,在coordinator node上保存,存储的是针对某个特定key其备份存储的节点列表,一般而言在Dynamo中如果一个数据有N个备份,则这N个备份会存储在以coordinator为起点的N个顺时针方向的节点上,N个节点指的是N个不同的物理节点,因此会跳过顺时针方向上在同一个物理节点上的虚拟节点,同时,为了避免节点失效带来的问题,一般preference list中会包括多于N个节点。

vector clock: 矢量时钟的详细描述可以参见下图。在Dynamo中,If the counters on the first object’s clock are less-than-or-equal to all of the nodes in the second clock, then the first is an ancestor of the second and can be forgotten. Otherwise, the two changes are considered to be in conflict and require reconciliation. 因此,在Dynamo中当一个client要更新一个对象时,他必须声明是要更新对象的哪一个版本,即write操作必须传递相关的时钟信息,该信息可以从前一次的read操作中获取。

hinted handoff: 即当一个节点失效时,可以先把数据放在另外一个不负责该数据的节点保证W的个数可以满足,然后当节点恢复时再更新回去。可以参考之前有关最终一致性的文章。

merkle tree: merkle tree是一个哈希树,即一个节点是其孩子节点的哈希值,而叶子则是数据的哈希值,主要来进行备份之间的同步校验。有关merkle tree的详细介绍可以参考这篇文章。每一个节点都针对一个key的范围保存了一个单独的merkle tree,这个merkle tree用来进行校验这些keys是否是最新的。这个机制的在此处应用的缺点是当一个节点加入或者离开时,由于邻近节点负责的range发生改变,都需要对merkle tree进行重新计算。

Dynamo的论文系统讲述了分布式的Key-Value存储设计中的思想和方方面面,是学习NoSQL的必读资料之一,同样这个有点纯理论的设计也引来了不少讨论,就有人指出Dynamo是一个缺陷的设计,有关此信息可以参考TimYang的这篇博文

转载请注明来源:Leoncom-《Amazon Dynamo阅读笔记之设计要点》
Trackback

only 1 comment untill now

  1. I love the pops of gold! The hexagons are so cute too. I love it all!

Add your comment now