Dynamo:亚马逊的高可用性键-值存储

                  （3章-4章）

Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati,  

        Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall  

                          Werner Vogels 

                           Amazon.com

  3 相关工作

  3.1端到端系统

     有一些关注数据存储和分布问题的端到端（p2p）系统。第一代的端到端系统，比如Freenet 和 Gnutella，曾经主要用来做文件分享系统。这些非结构化的P2P网络建立了任意端之间的叠加链接。在这些链接中，一个搜索查询会覆盖网络去找到尽可能多的端共享数据。P2P系统升级到现在已广为人知的结构化P2P网络。这些网络采用了全球一致的协议来保证任意端能有效地通过路由搜索查询到所需数据的端。像Pastry 和 Chord系统，使用路由机制来保证查询在一定范围的跳转内得到应答。为了减少多跳路由引起额外的延迟，一些P2P系统，在路由时引用将路由信息保存在本地的做法，这样它可以在适量的端口中路由请求信息。不同的存储系统，比如Oceanstore和PAST。曾建筑在这些路由覆盖之上。Oceanstore提供了全球性，事务性，持久性存储服务支持广泛复制的数据序列化的更新。要允许并发更新，同时避免广域锁固有的问题，他在解决冲突的基础上使用了更新模型。解决冲突，以减少事务终止。Oceanstore解决冲突通过执行一系列的更新，在他们之间选择总的顺序，并原子性执行应用他们。它是建立在数据可以被复制到不可信任的基础设施环境。相比之下，PAST在Pastry之上为持久不可改变的对象提供了抽象层，它假定应用层可以在其之上建立必要的存储语义。

3.2 分布式的文件系统和数据库

在文件系统和据库系统社区，分布式数据的性能，可用性及耐用性已经被广泛研究。和P2P存储系统仅支持平命名空间相比，分布式文件系统更多支持层次命名空间。像Ficus和Coda系统复制文件来达到高可用性花费高一致性。更新冲突管理通常使用专门的冲突解决程序。Farsite系统是一个分布式文件系统比如NFS系统，不使用任何的集中的服务器。Farsite使用复制实现高可用性和可拓展性。Google文件系统是另一个分布式系统作为谷歌内部应用程序状态之间的主持。GFS使用单一主服务器承载整个元数据和数据分割成块，并存储在chunkserver一个简单的设计。Bayou是一个分布式的关系型数据库系统，允许断开连接的操作，并提供最终数据的一致性，在这些系统中，Bayou,Coda和Ficus允许断开的操作和适应问题比如网络分区和中断。这些系统在解决冲突程序上各自不同。比如，Coda和ficus执行系统级的解决冲突和Bayou允许应用级别的解决方法。然而，所有的这些保持一致性。类似这些系统，Dynamo允许读和写操纵继续，甚至是在网络分区和解决更新冲突，使用不同的解决冲突机制，像FBA的块分布式存储系统将大的物体分割成小的物体，以高可用性的方式存储。和这些系统相比，键值系统更适合这种情况，因为：（a）他的目的是保存相对较小的整体（大小<1M）；（b）键值存储更容易配置应用商店的基础.早前是广域分布式系统设计用来处理多台服务器失败。它使用安全日志去保证数据的完整性，在多台服务器复制每个日志保证数据的健壮性，使用Byzantine容错协议确保数据的一致性。在之前，Dynamo并不关注数据的完整性和一致性问题和建立可信赖环境。Bigtable作为管理结构性数据的分布式存储系统。它保持一个稀疏的多维的有序映射，并允许应用程序使用多个属性访问他们的数据。和Bigtable相比，Dynamo的应用程序目标是要求键值访问主要关注高可用性，即使在网络分区服务器失败之后。

传统的复制关系数据库系统集中在保证复制数据一致性的问题。虽然强一致性给应用程序的编写者提供了方便的编程模型，但是这些系统在可用性和可拓展性方面受到限制。这些系统不能够处理网络分区，因为他们通常提供了强一致性的保证。

3.3 讨论

在他们的目标要求看来，Dynamo与之前分散的存储系统不同。首先，Dynamo主要是针对“总是可写”的数据存储，不会因为失败或并发而更新被拒绝。这在许多亚马逊应用中是重要的需求。其次，如之前所示，Dynamo是一个建立在单一的执行域并且假设所有节点都是可信任的基础设施。第三，应用程序使用Dynomo并不需要支持层次性命名空间（在许多文件系统规范）或复杂的关系模式（由数据库支持）。第四，Dynamo是敏感延迟的应用，要求至少在几百毫秒时间之内完成99%的读写操作。为了满足这些严格的延迟要求，我们必须避免通过多个节点的路由请求（这是被一些分布式哈希表系统采用的典型设计，比如Chord和Pastry）。这是因为多路路由在一定响应时间内增加了可变性，于是更高概率上的增加了延迟。Dynamo的特点是零跳的DHT，它在本地保存足够的路由信息，直接路由一个请求到合适的节点。

4系统架构

存储系统的架构，需要复杂的生产经营。除了实际的数据化持久组件，系统需要有负载均衡，会员和故障检测，错误恢复，复制同步，超载处理，状态转移，并发和任务调度，请求编码，请求路由，系统监测和报警以及配置管理的可扩展性的强大方案。描述每个解决方案的细节是不可能的，所以本文集中关注在核心分布式系统技术在Dynamo的使用：分区，复制，版本控制，成员，故障处理和缩放。

表1总结了Dynamo使用的技术和各自的优势

4.1 系统接口

Dynamo通过一个简单的接口，存储与一个键值相关联的物体。它暴露了两个操作：get()和put()。get（key）操作定位的对象，和键值关联在存储系统中存有副值，并返回一个单一的对象以及一个有上下文的冲突版本的对象列表。Put(key, contex, object)操作决定了对象的副本在关联键值的基础上应该存储在哪里，并且将副本写入磁盘。对象的上下文编码系统元数据对于启用者是不透明的，包括像对象的版本号等信息。上下文信息和对象一起存储，于是系统可以验证在推请求中申请的上下文对象的正确性。Dynamo认为调用者提供的键值和对象都是不透明的一组字节。它使用MD5哈希加密键值生成128位的标识符，用来决定存储节点负责服务键值。

4.2分区算法

Dynamo的关键设计要求之一是它必须逐步扩大。它需要一个在系统的设置节点上（存储节点）分区数据的动态机制。Dynamo的分区计划依赖于一致性哈希分发跨多个存储主机的负载。使用一致性哈希，哈希函数的输出范围被视为一个固定的圆形空间，或则“环”。（比如，最大的哈希值环绕到最小的哈希值）。系统中的每个节点被分配到这个空间的随机值，代表着他们在这个环中的位置。