如上所示，是一个7个虚拟结点构成的一个换，在Dynamo中，

    定义了常量N，用来表示一个数据会在多少个结点中进行存储。对于一个Key，K，其会存储于其顺时针方向后的N个结点上。

    假设N = 3， 对于上图中的K，会被存储与，B, C, D三个结点上，并且B被称为K的“coordinator”。D会存储(A, D]范围的所有数据。(A, B] ∪ (B, C] ∪ (C, D]

    对于N个结点，会自动对同一个物理结点的虚拟结点进行去重操作。

3.2.3 R & W

    在Dynamo中，定义了其他的几个常量 R 和 W。分别代表参与读操作的最小结点数和写操作的最小结点数。

    对于任意的一个K的读写，首先会被转发到对应的“coordinator”,由这个“coordinator”来主导这次的读写。

    对于写操作，一定要求W(包括其自身)个结点写成功才算是一次成功的写，并返回成功。

    对于读炒作，“coordinator”会将这个读转发至剩下的N-1个副本，并获取至少R(包含自身)个副本(带version)，然后交由“divergent”来进行冲突的处理，并返回。

    在Dyanmo的设计中，如果保证了R+W>N，就可以得到一个“quorum-like”的系统，在这样的环境下，读或者写对延时将是同步的并发R或者W个结点操作的耗时，对R/W/N之间关系的调整，让应用有了对系统进行权衡的方式。

3.2.4 Conflict Reconciliation

    Dynamo要求及时发生了网络隔离之后，仍然提供不间断的读写服务。必然给数据的最终一致带来挑战，相较于一般的消极的写时避免冲突(conflict prevention)，Dynamo提供的是乐观的在读时进行冲突解决(conflict reconciliation)。

    为了完成这样的目的，在进行数据写入时，会给记录添加“object version”，在Dynamo中，允许在同一时间内，保持同一个key的多个version并存；一般在对一个key进行更新操作的时候，要求提供此次更新的“上一版本号”，用于在Dynamo中清除老的实例。版本号的定义为[node, counter],称为一个clock, 不同结点作为coordinator来主导的更新，都会被记录到一个向量之中，形成所谓的“vector clocks”。不同的结点作为coordinator来对一个Key进行修改时，仅仅修改向量的一个维度。

    如果发生了网络隔离，必然会导致在一个Dynamo实例中同时包含了多个version，在读取时，如果发现了多个版本，由应用自定义的方案进行冲突的解决。比较好的方式是对多次写入的结果进行合并，例如电子商务中的多次下单，默认的会使用最新的版本。

    下面是一个具体的例子：

    假设一个Key，在正常情况下，会由结点Sx来负责其coordinator工作，在两次更新每次都会带上上次的version，会失效掉系统中旧的版本，整个Dynamo实例中，仅仅只有一个实例D2([Sx，2])。

    假设此时发生了调整，导致原有的这个Dynamo实例，同时有Sy和Sz同时负责不同分区内的K的coordinator工作，于是当两个分区各有更新的时候，在不同的隔离区上会形成不同的时钟向量，记Sy和Sz主导更新后，分别形成D3([Sx，2], [Sy，1])和D4([Sx，2], [Sz，1])当网络连通，用户端再此读取K是，会得到D2和D3，其向量为([Sx，2], [Sy，1] , [Sz，1]), 如果再次由Sx进行对K的coordinator工作来写入，会得到新的数据D4([Sx，3], [Sy，1] , [Sz，1]).

    在上面的过程中，Sx, Sy, Sz在向量中，都有自己的位置，相互不会进行修改。

3.2.5 结点调整

    当发生结点调整(人为或者意外)的时候，数据的分片会自动的在Dynamo实例中进行调整。保证原有的数据仍然保持N个副本。

    还是已上面的Hash环，(A, B, C, D, E, F, G) N=3为例，

    如果A正常下线，对于下面区间的Key，对应的N个结点(preference list)会发生相应的变化：

    (E, F] : F G A -> F G B

    (F, G] : G A B -> G B C

    (G, A] : A B C -> B C D

    也就是说，原来结点A上的数据(E, F], (F, G], (G, A]分别需要迁移至B, C, D上。

    如果在A和B之间上线了新的结点X，对应下面区间的Key的“preference list”会发生变化：

    (F, G] : G A B -> G A X

    (G, A] : A B C -> A X B

    (A, X] : B C D -> X B C

    也就是说，原来的B, C, D上的(F, G], (G, A], (A, X]会迁移至结点X，让X上拥有(F, X]的数据。

    另外对于意外的发生，如果A意外下线，这个时候D会完全接管对A的访问，同时，D会将原本发送给A的副本进行保存，当A得到恢复后，D会将这些副本转发给A，D也会删除这些数据，从而恢复原有的结构。

    在设计中，Dynamo这样除了能够应对但结点的意外失效，更能够应对发生网络隔离，IDC范围失败等意外情况。因为Dynamo采用了虚拟结点的方式进行组织，能够保证在各个IDC内，都维护有全量副本，一个Key的preferred list也分布于多个IDC内。这势必要求运行时跨IDC的高速连接。

    为了能够及时的诊断一个系统中结点的健康状况，Dynamo中还包括了一套结点发现，失效检测的机制，这里不进行详细的展开。

3.3Reference Point

3.3.1 设计点

    1. 在数据分片，冗余和复制

    在数据分片上，使用了一个变种的“一致性hash”；同一个key的数据，被冗余至连续的N个虚拟节点。

    节点加入和推出时，发生数据迁移应对变化。

    提供在线服务时，要求至少W个节点的写成功，R个节点的读成功，W+R>N

    2. 最终一致，永远可写，读时冲突解决

    Dynamo及时发生网络隔离的时候，仍然提供持续的写更新有效。这必然带来版本冲突，Dynamo在解决这方面问题的时候，使用的是“读时”冲突解决。为每个记录添加一个版本号(写时提供上一版本号，不匹配时，产生分支)，发生冲突的时候，由应用在多版本下决定如何解决。默认使用最新版本。

    3. 容量，性能持续横向扩展

    4. 去中心化

3.3.2 类似产品

    Cassandra

3.4 Summary

    首先，dynamo的应用场景为全量的Get和Put，不涉及部分更新的问题，所以在很多地方处理相对简单。不用考虑一个更新涉及多个点的问题。但是这样的使用方式，并不能完全适用于社区类的业务数据。

    最终一致性，在很多时候，对大社区业务，意义相对较少(PNuts提供的一致性保证可能更有意义)。但是社区应用，普遍的对一致性要求较少。

    分片和复制，采用了去中心化，节点完全对称，给整个系统的结构带来了优化。但是其多份同步写，多份同步读的更新，带来了读写延迟以及写并发量的成本。

    Dynamo的机制，如果发生网络隔离，实际上每个机房都有W+R>N是没有办法保证的，并且对于“高速网络连接的多IDC”这一假设，可能在我们的实际应用中，并不成立。如果多机房分别部署，数据的一致性又会成为问题。

    由于每个业务使用自己的Dynamo实例，并且仅限于内部使用，不需要进行任何访问控制。

4 Amazon SimpleDB

4.1 Introduction

    Amazon的SimpleDB是其AWS的重要组成部分，SimpleDB以Web Service的形式对外提供实时的结构化数据的实时服务。SimpleDB和S3，EC2一起提供完整的云计算环境。SimpleDB的在业界可谓非常有影响力，直接导致了开源项目CouchDB的展开。

4.1.1 易于使用

    传统的关系型数据库，拥有较多的复杂的功能，并且大多不为web站点所使用；SimpleDB提供了精简的数据模型和简单的操作。

4.1.2 灵活，可扩展

    在数据模型方面，无模式的数据模型，用户不必定义任何的数据scheme，用户只需要按需进行存储就可以了，系统会对用户数据进行索引，面对小量的数据不会有性能压力；用户在进行数据使用上是方便灵活的，数据的纵向扩展非常方便。在横向扩展方面，SimpleDB使用新建Domain的方式进行，SimpleDB内部，Domain之间是没有关系的，有具体的web应用来进行数据的组织。

4.1.3 高速可靠

    对用户的数据的完全索引，保证个各种访问的高效性。同时，由Amazon保证了数据本身的高可用性和安全性。

    但是考察Domain的建立方式，SimpleDB服务，还是面向单IDC服务的。

4.1.4 作为aws的一部分而设计

    SimpleDB是作为aws的一部分进行设计的，专门用来存储一个应用的元数据，这些数据的消费端是业务逻辑。而Amazon的S3是专门用来存储“数据对象”的，这些数据作为一个整体进行消费，而不进行业务逻辑的解释；更多的，S3上的数据可以被直接用户浏览器所消费。

4.1.5 数据模型

    SimpleDB使用的是“文档”结构的模型，提供了Account, Domain, Item, Attribute, Value,这样的5层结构，每层之间的关系是一对多的关系。

    其中Account->Domain[]的一对多的关系主要提供用户对不同的数据进行管理，在一个Domain一般用于存储同一类的数据，类似于关系数据模型中的一个表。

    一个Domain内部，有多个Item，每个Item类似于关系数据模型中的一行，每个Item有多个Attribute，类似于列，区别的是，每个Item的Attribute运行不一样；最后一个Attribute可以有多个Value。

4.2 Architecture

    针对simpleDB的设计，能够获取的还是比较少的，现在仅仅对已有的资料做出一些评估，并给出自己的结论。对于更加具体的分析，可以参考后面的CouchDB方面的调研。

4.2.1 功能

    1. 存储的http接口，SOAP & REST

    2. 在同一个账户下，非关系型数据模型，数据模型为Domain，Item，Attribute，Values；在同一个Attribute下面，可以有多个Value.可以看作是一个文档模型。在其上，自动建立索引(SELECT时使用)。

    3. 操作原语非常简单，对于数据操作，仅仅有

    a) PutAttribute/BatchPutAttribute

    b) DeleteAttribute

    c) GetAttributes

    d) Select(针对Attribute的，支持分页)

    4. 容量

    a) 单“Domain”数据量10GByte，“Attribute”数量109

    b) 单“Item”键值对256

    5. 提供最终一致性，读取时，支持“读最新”模式

4.2.2 具体实施

    SimpleDB使用Erlang进行编写。

4.3 Reference Point

4.3.1 设计点

    考虑SimpleDB的创建方式:

    Choose a Region for your Domain(s) to optimize for latency, minimize costs, or address regulatory requirements. Amazon SimpleDB is currently available in the US East (Northern Virginia), US West (Northern California), EU (Ireland), and Asia Pacific (Singapore) Regions.

    ―http://aws.amazon.com/simpledb/

    SimpleDB应该是不支持多IDC数据互通的。如果需要，应该是由上层的应用，进行数据跨IDC的冗余和数据组合，具体的应用中，靠谱吗？

    SimpleDB，对每个“Domain”保存了多份的数据冗余，考虑到整体的数据量(10GByte), 在单机放内部，提供任何方式的一致性保证，应该都不会是一个难点。

    SimpleDB，一个“Domain”下的数据，仅仅10GByte，所以正常的应用，仅仅在容量一侧层面，就会限制住很多体面的应用，因此，使用SimpleDB进行partition，除了常见，更是必须。Amazon给出的要求是，让应用层进行数据的拼装…一个账户可以控制100个“Domain”，这个限制应该比较随意，毕竟，一个账户下的和多个账户下的，在具体的数据组织上应该没有太多的区别。

    SimpleDB最值得说的，除了报道上的商业上的成功，SimpleDB最值得称道的应该算他的数据模式了。文档模型，省掉了没有必要的SQL复杂操作。同时支持自动的索引建立，对于数据使用者，基本上没有任何的“做数据”的需求。针对这种任意多索引具体实施方式上面，没有什么资料进行透露(利用检索的思路？)。

4.3.2 类似产品

    CouchDB

4.4Summary

    SimpleDB的一些具体的问题：

    1. 单“Domain”10GByte的容量

    2. 对partition几乎没有任何的支持

    3. 对多IDC几乎没有任何的支持

    值得我们借鉴的，应该是SimpleDB的数据模式。

    这样文档模型，自动的索引机制。

    但是Select中，并没有对ORDER BY的支持，所以在不同的访问模式下，可能需要建立不同的Domain进行数据的存储(tieba的FRS类似的需求)。

    SimpleDB的存储模式非常值得我们学习和思考，但是考虑到，在这样的文档化结构模型，和传统的关系型模型在操作上，还是有着非常大的不同，使用者能够进行过渡，还是一个值得置疑的地方。同时真的对每个字段进行检索，在具体的实现上是否现实，也是值得考虑的，而且由于字段仅仅限于字符串，而不同的数据类型在进行转化时，比较关系是会发生改变的(99<100, “99”>”100”)遮掩的检索是否真的满足需求也不一定。

5 Amazon S3

5.1 Introduction

    Amazon S3，简单而言，是Amazon云体系下的kv存储服务。设计的初衷，是为了屏蔽掉分布式存储的细节，使得网络应用的开发来得跟进简单和快速。

    Amason S3提供一个简单的Web服务接口，可用于在任意时间，任意地点的网页存储和检索任意数量的数据，提供高可用性，可靠安全的数据存储，快速廉价的基础设施。开发者可以通过Amason S3来存储自己业务相关的数据。

    S3主要关注以下的feature：

    1.读、写和删除对象的大小从1byte-5T。对象的数量不做限制。

    2.每个对象会被存储在一个bucket中，通过一个唯一的key获取对象。

    3.一个bucket能够只能被存储在n个分区的其中一个，分区数据不能在线互通。用户可以根据延迟、花费($)、地域管理成本等方面来综合考虑分区的选择。一个对象被存储在一个分区，那么它就只能存在那个分区中，除非显式的进行数据迁移(给$-.-)。

    4.有权限机制，对象可以设置成公有，私有，或者给指定的用户访问。

    5.提供标准的REST接口和SOAP接口。

    6.默认协议是，HTTP协议。

5.2 Architecture

    无相关实现资料，但是根据其一致性模型和实现的feature，估计和mola差不多。

5.3 Reference Point

5.3.1 Design Requirement

    可扩展性：在扩展性方面，S3支持存储容量的无限扩展，以支持应用的存储。扩展的方法是优先为系统自动的增加节点，以达到可用性、速度、吞吐量、容量上的满足。

    可靠性：据首页官方数据，数据的持久存储能做到99.999999999%不丢数据，并且有99.99%的可用性。不存在单点故障不可用的情况。所有错误都能够做冗余并且被修复。

    范围速度：S3需要满足Web应用的高速范围的需求。服务器端的延时和外网的延迟无关。任何的性能瓶颈可以通过简单的增加机器节点来解决。

    廉价：S3由廉价的硬件组件所构成。所有的硬件都有可能随时挂掉，但是保证不会影响整个系统的运行。

    简单：S3要能做到可扩展性，可靠性，快速访问并且廉价的存储。而且需要给应用一个易用的接口与访问环境。

5.3.2 Data Type & Concepts

    S3的数据类型非常简单，只有Buckets 和 Objects。

    Buckets：一个Bucket是存储在S3上的Objects的容器。每个对象都存储在某一个Bucket当中，例如，如果一个对象的名字叫做：photos/puppy.jpg,存储在johnsmith Bucket当中，那么这个访问地址就是：

    http://johnsmith.s3.amazonaws.com/photos/puppy.jpg 使用Bucket的目的有几个：在最高层次定义S3的命名空间，可以定义账号并且为存储和数据传输服务；能够做角色权限的控制；可以做更好的管理操作与配置

    Objects：Objects是S3的基本存储实体。Objects包括Object data和Object metadata。Data部分封装在S3内，而Metadata则是一系列的名值对用于描述对象。

    Keys:一个key是一个Object在一个Bucket里的唯一标识。每个Object在一个Bucket只有一个key。通过组合一个bucket，key和versionID，可以唯一标识每个对象，因此，s3的object可以简单的映射为“bucket+key+version”。

5.3.3 Data Consistency Model

    S3使用的最终一致性模型。更新一个唯一的key是原子的。例如，如果对一个存在的Key进行PUT操作(更新)，一个序列化的读操作有可能会读到老的数据也或者是更新后的数据，但是不会有写坏或者写部分数据的情况。

    S3为了实现高可用，在多个服务器会部署副本。如果返回“success”,则数据会被安全的存储。然而，更新的改变不会马上的被同步到所有的副本中。

5.3.4 User Interface

    S3提供REST接口和SOAP接口。具体可见附录[3]。

5.4 Summary

    Amason S3主要是提供了一个kv的云存储服务。对于S3,数据转换中间件的参考点有：

    (1)bucket+object+version概念；

    (2)User Interface 参考；

    (3)S3对需求满足的考虑。

6 Apache CouchDB

6.1 Introduction

    开源的CouchDB，可以看作是SimpleDB的开源版本。基本上说CouchDB是一个使用RESTful接口文档模型的数据服务器；其数据模型采用文档结构，无模式。面向高可用性设计，CouchDB也采用分布式部署，自带了复制，数据冲突检测以及冲突解决机制。

6.1.1 文档数据模型

    在CouchDB中，记录的基本元素为Document(类似于SimpleDB中，Domain内的一个Item)，每个Item有多个Field(类似于SimpleDB中的Attribute)，每个Field可以有一个或者多个Value。

    一个CouchDB就是一个Document的集合，每个Document有一个唯一的ID进行标识。

    利用这样面向文档的数据模型，使用CouchDB的应用，不用预先定义表模式，也不需要进行将来需求变更后带来的做数据的麻烦。

6.1.2 试图模型

    CouchDB提供了试图功能(View)。和一般关系数据库的视图一样，都是基于底层具体的数据通过运算的方式来动态建立的。CouchDB提供过利用JavaScript进行试图的描述。除此以外，CouchDB的每一个视图，在实际的作用上，更是一个索引。

6.1.3 分布式设计

    CouchDB在分布式方面，使用了基于对等的设计。多个CouchDB的结点部署在一起形成一个CouchDB集群的时候，每个结点都会保留一份全量的备份。每个结点都提供全量的数据服务(query, add, edit, delete)。结点之间的是双向的对其他结点上的更新进行增量同步。

    如此的并发写环境下，会伴有写冲突(conflict)，CouchDB拥有内建的冲突检测和管理机制。

6.1.4 和SimpleDB的区别

    CouchDB和SimpleDB的在定位上非常相似，在这里做一番对别。

    1. 相似点

    a) 文档结构，无模式数据模型

    b) http访问接口

    c) Erlang所编写

    d) 支持分布式部署

    2. 区别

    a) 具体接口上，SimpleDB除了RESTful接口，还有SOAP接口，并且使用Get方式，参数具体字段说明操作。CouchDB完全RESTful化，使用HTTP中的GET，POST，PUT， DELETE进行方法说明，URL进行数据库的选择。

    b) SimpleDB使用UTF-8编码的字符串作为原子数据类型，CouchDB使用JSON数据类型。

    c) SimpleDB默认对每个Attribute建立索引，CouchDB则利用视图手动建立索引

    d) 由于字段类型的原因，支持的查询修饰操作也会不一样。

    e) SimpleDB使用XML形式返回查询结果，CouchDB使用JSON格式返回。

6.2 Architectrue

    在大的部署方面，CouchDB使用扁平化的结构，也就是每个CouchDB结点都是对等的，没有具体的层次。各个结点之间通过“Replicator”来进行连接，同步彼此之间的更新动作。

    下面是一个CouchDB内部的结构，也是整个CouchDB的功能的主要部分。