Dynamo论文介绍

Dynamo是Amazon开发的分布式存储系统,本文是阅读Dynamo论文后的总结:Dynamo: Amazon’s Highly Available Key-value Store。将从背景、定位、简介、问题及解决方案几个方面介绍Dynamo的整体设计思路。

背景

Dynamo是在Amazon所处的应用环境中因运而生的,其需要面对的问题和场景在互联网的业务中也是类似的:

定位

为了理解Dynamo的整体设计,了解其定位是很有必要的,因为从其定位中我们可以清楚的了解到系统关注的问题和可以放弃或妥协的点。针对上所述的背景,Dynamo提出了自己的基本定位:

正是由于上述对自己的定位,Dynamo在设计中可以舍弃掉许多负担,如关系型数据库复杂的查询模型、对ACID的支持,对强一致性的追求,以及复杂的存储结构。同时,Dynamo认为其面对的是相对安全的内部网络环境,所以并没有处理安全或权限问题。

简介

问题及解决方案

1,数据分片

为了更好更灵活的操作管理存储的数据,对数据空间进行分片并将分片分配到不同存储机器是一个显而易见的不错的做法。Dynamo采用类似一致性哈希的方式进行分片的划分和分配。关于数据分片的算法,Dynamo经历了几个阶段的选择和进化。

图1 增加virtrual nodes的一致性hash

图2 等分一致性hash

2,分片备份

为了系统高可用,Dynamo的每个分片都有N个副本,存储在hash ring上顺时针方向的N个节点上。这N个节点称为该数据的preference list。其中的每一个节点都可以对接受针对该数据的操作请求。 图3 分片备份

3,数据版本及冲突处理

由于preference list中的每个节点都可以对同一个数据进行处理,且为了高可用,用户写请求返回前并没有将数据同步到所有分片。当有大量并行访问或故障发生时,集群中的不同机器看到的同一个数据状态可能不同,这时就发生了冲突。Dynamo引入vector clock来在一定程度上缓解冲突的发生,并最终由应用端对冲突进行合并。

vector clock := list{ (node, counter), ...}
node := 机器id
counter := 该数据在node上的处理序序号

4,读写过程

5,发生暂时错误时保证可用

Dynamo中用hinted handoff的方式保证在出现暂时的节点或网络故障时,集群依然可以正常提供服务。

6,降低分片同步数据传输量

通过上面所述,可以看出当故障发生或者有新节点加入、离开集群时,都涉及分片的拷贝和传输。希望能够快速检查分片中内容是否相同,并通过仅发送不同的部分来减少数据传输量。Dynamo采用Merkle Tree来解决这个问题。

7,成员信息及故障检测

总结

论文中介绍了Dynamo面对的问题及其解决方案,而对于其中众多的细节还需要在工程实现中权衡和优化。包括Dynamo中冲突的处理方式,对大多数业务场景来说可能都是无法接受的。

Table of Contents