3.相关工作
3.1点对点（p2p）系统
（1）第一代p2p系统，freenet和guntella：主要用于文件共享；
（2）结构化p2p系统，pastry和cord：使用路由机制；有些系统才有o(1)路由，每个节点保存全局信息；
（3）Oceanstore系统：全局、事务、持久性存储服务，为了保证更新不冲突，数据一致，使用协调更新序列方式实现。
3.2分布式文件系统和数据库
（1）GFS；
（2）BigTable；
3.3讨论
（1）Dynamo的设计原则之一：永远可写；
（2）Dynamo供内部使用，内部节点可信；
（3）Dynamo可以被定义为零条（zero-hop）的DHT，每个节点维护足够的路由信息从而直接从本地将请求路由到相关节点。
4.系统架构
一个商业分布式存储系统架构是十分复杂的，除了数据的持久化，还需要考虑：
（1）负载均衡；
（2）成员及故障检测；
（3）故障恢复；
（4）副本同步；
（5）过载处理；
（6）状态转移；
（7）并发与调度；
（8）请求路由；
（9）监控报警；
（10）配置管理；
等等诸多元素。本文重点讨论的核心是Dynamo中使用什么技术解决以下问题：
（1）划分（partitioning）
（2）复制（replication）
（3）多版本（versioning）
（4）成员（membership）
（5）故障处理（failure handing）
（6）扩展性（scaling）
下表给出Dynamo所使用的技术与其优势：
表一：dynamo所用技术与优点
问题 | 技术解决方案 | 优点
划分 | 一致性哈希（Consistent Hashing） | 增量可扩展
写高可用 | 向量时钟与协商读 | 版本大小与更新率解耦
偶然失败处理 | 乐观仲裁与隐式处理 | 以部分副本的失效换取高可用性
永久故障恢复 | Merkle树反熵技术 | 后台同步副本
成员与故障检测 | Gossip的成员与故障检测协议 | 避免中心节点
4.1系统接口
Dynamo提供几个简单接口：
（1）get(key)：在存储系统中定位与key关联的对象副本，并返回对象副本或包含冲突的各版本与上下文；
（2）put(key, context, object)：存储key极其关联的对象副本，上下文信息，注意这里上下文对调用者是不透明的，例如对象版本信息。
Dynamo系统将调用者提供的key进行MD5产生一个128位的标示符，用来确定key的存储节点。
4.2划分算法
Dynamo的关键设计目标之一是：增量可扩展性。这需要一个机制来将数据动态划分到系统的节点上去。
Dynamo的分区方案依赖于一致性哈希将负载分发到多个存储主机上去，设计要点是：
（1）一个哈希函数的值域视为一个固定圆形空间（环），每个节点分配这个空间中的一个随机值，
代表它在环上的位置；
（2）key通过哈希函数可计算出环空间上的一个值，比该值大的最小节点值节点负载该key的存储；（相当于一个主机负载一块区域）
（3）“虚拟节点”方案：一台主机实际对应环上多个虚拟节点，而不是一个单点（后文所指节点均为虚拟节点）；
优点：
（1）节点的增删不会产生大规模数据迁移与动荡，只影响相邻结点；
（2）数据可均匀分配；
（3）无视节点的异质性，性能好的节点可分配更多的hash空间；
（4）虚拟节点的分配数量可根据节点处理能力来决定；
4.3复制
为了实现高可用与持久性，Dynamo将数据复制到N台主机上，N为可配参数，技术要点是：
（1）每个key通过hash可被分配到一个主机节点，称之为协调节点（coordinator），它负责数据项的复制；
（2）协调节点将数据复制到环上后续N-1个后继结点。
图：Dynamo的成员环
一个负责存储特定key的节点列表成为首选列表（preference list），由于使用虚拟节点的方法，首选列表中
N个后继位置可能实际少于N个物理节点。
4.4数据版本
Dynamo提供最终一致性，它在后台允许更新操作异步传递到所有副本。
put()操作可能在异步更新到所有副本完成之前返回给调用者，这可能导致随后某个get()操作可能返回一个过期的数据。
更新成功，异步副本一致将有一个时间上限，在网络分区时，这个时间可能会很长很长。
Amazon的平台上，有一种类型可以容忍这种不一致：添加到购物车。
“添加到购物车”和“从购物车删除”都将被转化成put请求，客户希望增加一个项目至购物车，但最新版本不可用时，旧版本将被添加，不同版本将在后续协调，技术要点是：
（1）Dynamo将每次修改的结果都最为一个新的，且不可变的数据版本；
（2）允许系统中出现多个版本的对象；
（3）版本分支可能发生在并发写操作中；
（4）由客户端执行冲突的协调，将多个分支数据合并为一致数据（客户端可根据数据、时间戳等语义判断）；
这种机制，保证了一个“添加到购物车”的操作永远不会丢失，只是可能读取到旧的数据（例如已删除数据）。
某些情况下数据版本可能不止两个，例如网络分区，Dynamo使用向量时钟来捕捉一个对象不同版本之间的因果关系，技术要点是：
（1）向量时钟实际上是一个节点、计数器(node, counter)对列表，通过它的审查，能判断出一个对象什么时候出现版本分支；
（2）如果某对象第一个时钟计数器小于第二个，那么第一个就是祖先，可以被忽略（可理解为，一次写操作计数加一）。
（3）两个计数器相同时，则认为数据冲突，需要进行协调；
图：版本冲突
图示说明：
（1）客户端写入新的对象D，Sx节点进行了处理，此时D1对应的向量时钟为[(Sx,1)]；
（2）客户端更新对象D，仍是Sx节点进行的处理，此时D2对应的向量时钟为[(Sx,2)]，但这个更新可能还没传递到其他副本；
（3）假设又一个更新请求，Sy进行了处理，目前系统具有数据D3，其向量时钟为[(Sx,2),(Sy,1)]；
（4）假设另一个客户端读取D2，并要更新它，节点Sz进行了处理，该系统数据D4的向量时钟为[(Sx,2),(Sz,1)]；
此时D3和D4都有更新操作，且均为在对方的变化中反映出来，后续数据读取过程中，这两份数据都会提交给客户端，由客户端来协调仲裁。
（5）某个客户端读取对象D，D3和D4都返回了，即它得到D[(Sx,2),(Sy,1),(Sz,1)]，客户端发起协调，并由Sx处理，将得到D5[(Sx,3),(Sy,1),(Sz,1)]；
为了保证向量时钟不会无限制增长，Dynamo采取了截断方案，保存一个时间戳记录更新时间，当向量时钟要超过阈值时，将最早的记录删除掉。
4.5get()和put()的执行
客户端能有两种策略选择执行节点：
（1）通过某个节点路由请求；
（2）使用一个分区敏感的客户端直接发送请求；
第一个方法的好处是，不需要链接任何Dynamo的代码；
第二个方法的好处是，它跳过一个潜在的转发步骤。
读写操作都涉及首选清单中的N个健康节点（挂掉的节点会被跳过），为了保证副本的一致性，
Dynamo使用的一致性协议类似于仲裁（quorum），该协议有两个关键配置：R和W。
（1）R是一个读操作成功所需读取的最小节点数目；
（2）W是一个写操作成功所需写入的最小节点数目；
（3）设定R和W后，用R+W>N产生类似的仲裁；
例如，我们设副本数N=3，读成功配置R=2，写成功配置W=2，
则有2个副本写成功才算真正写成功，
2个副本渡读成功才算真正读成功；
4.6临时故障处理：Hinted Handoff
Dynamo为了提高系统可用性，使用乐观方式仲裁读写。
读写都不会因为节点失效或网络故障而失败，只有所有节点都失效时读写才会被拒绝。
4.7永久性故障处理：副本同步
Dynamo实现了反熵（anti-entropy）或叫副本同步的协议。
Dynamo采用MerkleTree，一种哈希树来存储key的信息，树的比对能轻易的了解副本是否同步；
每个节点维护一个单独的MerkleTree，树的比对也能轻易的找出不同步的key；
方案的缺点是，当有节点加入或离开系统时，许多key会发生变化，需要对树进行重新计算。
4.8成员与故障检测
4.8.1环成员（Ring Membership）
Amazon环境中，节点故障往往是暂时的，此时不应该重新分配暂时无法访问的副本。
需要有明确的机制发起节点的增加或者删除，一个基于Gossip的协议传播成员的变动信息，并维持成员最终的一致性。
4.8.2外部发现
可能出现逻辑分裂的环。
例如：同时添加A，B到环中，此时A和B都认为自己是环中的一员，但都暂时不知道对方的存在。
解决方案是，环上某些节点通过其他机制来确保它知道所有的节点信息（例如，读取静态配置）。
种子节点是Dynamo环中的全功能节点。
4.8.3故障检测
去中心化的故障检测，也是使用的Gossip协议，系统中每个节点都可以了解到其他节点的到达、离开。
4.9添加/删除节点
节点B被加入到A和C中间，则A和C中部分key存储会自动迁移到B上；删除反之。
评论关闭。