相关问题发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：发布时间：书籍推荐
版权所有 (C) . All Right Reserved. 为中华文化之崛起而奋斗！论文重读: Amazon Dynamo
马上要写开题报告了，初步打算会做分布式计算方面（或是某些人口中的云计算）的一些研究。之前也看了不少相关的论文，但基本上都是浑沦吞枣，不求甚解。之后在某搜索引擎公司呆了一段时间，对这方面又有了新的认识，所以结合公司遇到的问题，在细细研读一遍这个领域的一些重要的论文。今天看的是Amazon公开的一个分布式KV数据库Dynamo。
互联网公司的大规模分布式计算系统都有一些相同的特点，其中之一就是为了节省成本，一般都将集群搭建在廉价的PC服务器上。这样的话，随着集群规模的增大，发生机器故障的情况就屡见不鲜了。所以此时在设计系统时，应该将机器故障视为一种常态。而Dynamo就是在这种前提下，Amazon的一个解决方案。
综合来看，Dynamo有如下特点：
0）简单的存取模式，只支持KV模式的数据存取，同时特定于小于1M的数据；
1）高可用性，即便在集群中部分机器故障，网络中断，甚至是整个机房下线，仍能保证用户对数据的读写；
2）高可扩展性，除了能够跨机房部署外，动态增加，删除集群节点，同时对正常集群影响很小。
3）数据的高可用性大于数据的一致性，短时间的数据不一致是可以容忍的，采用最终一致性1来保证数据的高可用。
4）服务于内网，数据间没有隔离。
5）服务保证条约，在Amazon一切皆服务2的原则下，每个模块都要为其使用者提供服务时间保证，比如在每秒500个请求的压力下，99.9%的请求要在300ms内返回。接下来详细介绍为了完成上述目标，Dynamo中所采用的技术方案。
数据划分(Partition)
Dynamo作为一个分布式的存储，必须能够将用户输入的数据划分到集群中的不同机器中存储。传统的划分方式都是类Hash的，即按照数据中的某些特征值做Hash（一般都是取模），使数据映射到下边的机器中。但是这种方式有个很大的缺点，那就是当集群中机器增加的时候，之前的Hash全部都是失效了，再Hash的成本很大，也就制约了集群的扩展。
Dynamo中采用的是“一致性Hash”来解决这个问题。基本思想是每一个Dynamo节点都有一个Token，可以将Dynamo想象成一个环，拥有不同Token值的节点处于环的不同位置。当一个GET(key)请求到来时，应用路由层或是Dynamo会将这个key做一个Hash，将这个Key同样映射到环上，然后在环上按照固定顺序往下寻找，找到的第一个Dynamo节点即为对这个Key服务的节点。当要向集群中增加机器时，首先为这个新节点分配一个Token，然后将他下游机器上原来的数据复制到本机上就算完成了。这样的好处是每当增加一个新节点，只会影响一小部分现有节点，不必像以前那样全部数据重新Hash，相比较而言，数据迁移的成本要小得多。
上述只是一个简单的一致性Hash原理的解释，实际并不是按照这种最简单的方式使用的。首先为了应对节点Token在环中分布不均的状况，以及考虑不同机器性能有差异的情况，Dynamo采用了“虚节点”技术，即为每个实际节点分配多个Token，此时一个机器在环中不仅有一个地址而是多个地址。另外考虑到数据的可用性问题，每份数据不是仅存在一个节点中，而是分别复制到下游的多个机器上，复制个数是可以配置的。这样当一个节点失效时，可以继续沿环寻找下一个节点。
副本技术与节点发现机制
上边已经说了Dynamo为了保证数据不丢失，采用了副本技术。Dynamo节点启动的时候会为他配置一个参数N，表示数据的副本数。当一条数据写到Hash环中对应的节点的时候，同样会发送给下游的N-1个节点（这些节点都是实际节点，而非虚节点）。这N个节点在系统中称为“Preference List”，同时为了应对出错的状况，“Preference List”中的节点数往往大于N。这里有个问题，就是当前节点是如何知道他的下游节点的呢？这就是节点发现机制。
由于各种各样的原因，暂时性的节点掉线是时有发生的。如果因为一个节点暂时性的掉线，而导致副本迁移等代价高昂的操作显然是不合适的。所以Dynamo提供了一组命令行接口和HTTP接口供管理员手工添加，删除节点。一旦一个节点的角色发生改变（上线或下线等），它都会将这个改变和放生的时间存储到一个持久的数据库中，这些数据构成了一个节点的状态变迁历史。然后通过一个Gossip-Based Protocol将这个消息传递出去。节点在收到其它节点的消息时，会将收到的消息与自己本地存储的消息进行合并，最终每个节点都会得到整个集群的信息。为了应对可能出现的“Local
Partition”现象，某些Dynamo节点作为“种子”节点，种子节点可以通过全局的方式被其它所有节点发现，最终所有的节点自己存储的状态信息都与种子节点的状态信息合并。
与正常节点发现类似，对错误节点的发现机制也是使用的Gossip-Based Protocol，每个节点都记录自己与其它节点的连通状态。在论文中有关于去中心化的分布式系统中错误发现机制详细介绍的参考。
写操作高可用
Dynamo中，最重要的是要保证写操作的高可用性，即“Always Writeable”，这样就不可避免的牺牲掉数据的一致性。如上所述，Dynamo中并没有对数据做强一致性要求，而是采用的最终一致性。结合上述的数据副本技术，可以看出，若不保证各个副本的强一致性，则用户在读取数据的时候很可能读到的不是最新的数据。Dynamo中将数据的增加或删除这种操作都视为一种增加操作，即每一次操作的结果都作为一份全新的数据保存，这样也就造成了一份数据会存在多个版本，分布在不同的节点上。这种情况类似于版本管理中的多份副本同时有多人在修改。多数情况下，系统会自动合并这些版本，一旦合并尝试失败，那么冲突的解决就交给应用层来解决。这是系统表现出来的现象就是，一个GET(KEY)操作，返回的不是单一的数据，而是一个多版本的数据列表，由用户决定如何合并。这其中的关键技术就是Vector
一个Vector Clock可以理解为一个&节点编号，计数器&对的列表。每一个版本的数据都会带上一个Vector Clock。通过对比两份不同数据的Vector Clock就能发现他们的关系。所以应用层在读取数据的时候，系统会连带这Vector Clock一同返回；在操作数据的时候也需要带上数据的Vector Clock一同提交。大致流程如图。
一个正常的GET和SET流程
之前也说过，Amazon在设计组件的时候采用的是“一切皆服务”的原则。Dynamo也不例外，应用可以通过两种方式使用Dynamo：1）通过一个应用路由层转发请求到对应Dynamo节点。2）通过连接Dynamo的API到自己程序中使用。两种方式各有优劣。负责处理读写请求的Dynamo节点在系统中称为“Coordinator”，一般是之前提到的“Preference List”中的第一台节点。如果不再这个List中的机器收到了读写请求，它会将这个请求转发到在List中的机器上。
Dynamo中一共涉及三个重要的参数，其中N，代表数据的副本数，之前已经说过了。另外还有W和R，分别表示：一次写操作，最小必须写成功节点数；和一次读操作，最小读成功节点数。另外要求W + R & N。设计这两个参数主要是出于性能考虑，不然可以直接令 W = R = N。读数据时，只要有除了Coodinator之外的R-1个节点返回了数据，就算是读成功（此时可能返回多个版本的数据）。同理，写数据时，只要有除了Coordinator之外的W-1个节点写入成功，就算数据写入成功。
故障检测和处理往往都是分布式系统的重点和难点，尤其是对于像Dynamo这种对可用性要求很高的系统。上边说了，通过设定N，W，R参数来保证读写的正确。一旦出现读写失败的情况，都会触发故障处理机制。Dynamo中将故障分为两类，一类是临时性的故障，另一类是持久的故障。分别对应两种不同的处理方式。
以N=3为例，如果在一次写操作时发现节点A挂了，那么本应该存在A上的副本就会发送到D上，同时在D中会记录这个副本的元信息（MetaData）。其中有个标示，表明这份数据是本应该存在A上的，一旦节点D之后检测到A从故障中恢复了，D就会将这个本属于A的副本回传给A，之后删除这份数据。Dynamo中称这种技术为“Hinted
Handoff”。另外为了应对整个机房掉线的故障，Dynamo中应用了一个很巧妙的方案。之前说过“Preference List”，每次读写都会从这个列表中取出R或W个节点。那么只要在这个列表生成的时候，让其中的节点是分布于不同机房的，自然数据就写到了不同机房的节点上。
“Hinted Handoff”的方式在少量的或是短暂的机器故障中表现很好，但是在某些情况下仍然会导致数据丢失。如上所说，如果节点D发现A重新上线了，会将本应该属于A的副本回传过去，这期间D发生故障就会导致副本丢失。为了应对这种情况，Dynamo中用了基于 Merkle Tree的Anti-Entrpy系统（不知道中文怎么翻译），关于Merkle Tree的资料，参考Dynamol中链接。
XTU_xiaoxin
浏览: 171048 次
来自: 北京
checkNameUniqueness(String bean ...
你这里只说了注解的优点，但是没说到xml配置的优点，那就是不用 ...
哥哥哎，我有和你一样的传奇经历
如楼主所述，state的赋值过程可以追加介绍一下吗？
SingleThreadExecutor但工作线程可以将并行任 ...
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
《云计算(第二版)》—第三章 Amazon云计算AWS.pptx 78页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
需要金币：100 &&
《云计算(第二版)》—第三章 Amazon云计算AWS
你可能关注的文档：
······
······
电子工业出版社《云计算(第二版)》配套课件解放军理工大学刘鹏教授主编华东交通大学刘鹏制作第3章Amazon云计算AWS《云计算（第二版）》购买网址：当当网京东商城姊妹力作《实战Hadoop》购买网址：当当网京东商城提纲?Amazon平台基础存储架构：Dynamo?弹性计算云EC2?简单存储服务S3?简单队列服务SQS?简单数据库服务SimpleDB?关系数据库服务RDS?内容推送服务CloudFront?其他Amazon云计算服务?AWS应用实例?小结Amazon提供的云计算服务?弹性计算云EC2?简单存储服务S3?简单数据库服务SimpleDB?简单队列服务SQS?弹性MapReduce服务?内容推送服务CloudFront?电子商务服务DevPay?灵活支付服务FPSDynamo在Amazon服务平台的地位面向服务的Amazon平台架构?Amazon平台的架构是完全的分布式、去中心化?需求——Amazon平台中有很多服务对存储的需求只是读取、写入，（满足简单的键/值式存储）Amazon怎么处理这个需求？Dynamo?简单的键/值方式存储数据，不支持复杂的查询?存储的是数据值的原始形式（bit），不解析数据的具体内容、不识别任何数据结构，这使得它几乎可以处理所有的数据类型Amazon平台基础存储架构：DynamoDynamo架构的主要技术问题采取的相关技术数据均衡分布改进的一致性哈希算法，数据备份数据冲突处理向量时钟（vectorclock）临时故障处理Hintedhandoff（数据回传机制），参数（W,R,N）可调的弱quorum机制永久故障后的恢复Merkle哈希树成员资格以及错误检测基于gossip的成员资格协议和错误检测数据均衡分布的问题?一致性哈希算法?平衡性?单调性?分散性?负载两步进行：求出设备节点的哈希值，并配置到环上的一个点；接着计算数据的哈希值，按顺时针方向将其映射到环上距其最近的节点；添加新节点时，按照上述规则，调整相关数据到新的节点上。删除节点和添加节点过程相反?Dynamo采用的改进算法?虚拟节点?数据分区和等份存储?数据备份当数据被均匀存储到环上各节点后，Dynamo将冗余存储数据（备份数据）思考：Amazon可以保证相邻的节点分别位于不同地区区域，即使某个数据中心由于自然灾害或断电的原因整体瘫痪，仍可以保证在世界上其他数据中心中保存有数据的备份。这里就有一个非常重要的问题——如何进行节点分布，保证相邻节点位于不同的数据中心？数据冲突问题?Dynamo系统选择牺牲一致性来换取系统的可靠性和可用性?解决数据冲突：?最终一致性模型（EventualConsistency）?向量时钟向量时钟原理图容错机制Dynamo临时故障处理机制1）临时故障处理机制?在数据读写中采用了一种称为弱quorum（Sloppyquorum）的机制，涉及三个参数W、R、N?W—代表一次成功的写操作至少需要写入的副本数?R—代表一次成功读操作需由服务器返回给用户的最小副本数?N—每个数据存储的副本数?满足R+W&N，用户即可自行配置R和W?优势：实现可用性与容错性之间的平衡容错机制2）永久性故障处理机制?Merkle哈希树技术?每个虚拟节点保存三颗Merkle树，即每个键值区间建立一个Merkle树?哈希树的叶子节点是存储每个数据分区内所有数据对应的哈希值，父节点是其所有子节点的哈希值成员资格及错误检测基于Gossip协议的成员资格检测机制?Gossip（闲聊）协议?错误检测机制基于Gossip协议的成员资格检测机制基于Gossip协议的最优传遍路径提纲?Amazon平台基础存储架构：Dynamo?弹性计算云EC2?简单存储服务S3?简单队列服务SQS?简单数据库服务SimpleDB?关系数据库服务RDS?内容推送服务CloudFront?其他Amazon云计算服务?AWS应用实例?小结主要特性灵活性：EC2允许用户对运行实例类型、数量自行配置，还可以选择实例运行的地理位置，根据用户的需求随时改变实例的使用数量低成本：EC2使得企业不必为暂时的业务增长而购买额外的服务器等设备。EC2的服务都是按小时来收费，而且价格非常合理安全性：EC2向用户提供了一整套安全措施，包括基于密钥对机制的SSH方式访问、可配置的防火墙机制等，同时允许用户对它的应用程序进行监控易用性：用户可以根据Amazon提供的模块自由构建自己的应用程序，同时EC2还会对用户服务请求自动进行负载平衡容错性：利用系统提供的诸如弹性IP地址之类的机制，在故障发生时EC2能最大程度地保证用户服务仍能维持在稳定的水平弹性计算云EC2EC2基本架构及主要概念EC2的基本架构Amazon机器映像（AMI）?AMI（AmazonMachineImage）是一个可以将用户
正在加载中，请稍后...