dynamo

一、dynamo特点介绍
dynamo 的中文意思是发电机，意思是像发电机一样，提供源源不断的服务。它是Amazon提供的一个分布式Key/Value存储的NoSQL 数据库，完全托管在云端，支持文档和键值存储模型。

其主要特点是如下:

特点 描述
数据模型灵活 schema freee，Nosql必然支持的，没什么说的
效率（速度） 数据采用SSD来进行存储，服务端平均延迟通常不超过十毫秒。随着数据量增多，DynamoDB 会使用自动分区和 SSD 技术来满足吞吐量需求，并针对任意规模的数据库提供低延迟。
高可用 Dynamo 为了达到高可用性和持久性，防止由于节点宕机故障或者数据丢失，将同一份数据在协调者和随后的 N-1 个节点上备份了多次
高度可扩展 dynamo 不会对数据规模大小进行限制，会把数据分布到各个机器上，只需为其指定目标使用率，容量便会自动根据应用程序请求数量的增加或减少而扩展或缩减，无需担心数据库的缩扩容问题
完全托管 无需担心数据库的管理，比如管理集群，软硬件的配置与预设以及监控、部署，省去开发者部署、监控、维护数据库的环境
去中心化 节点对称性、去中心化：系统采用P2P架构，每个节点都是对等的、有相同的责任
ACID属性 为了获得更为灵活的可水平扩展的数据模型，NoSQL 数据库通常会放弃传统关系数据库管理系统 (RDBMS) 的部分 ACID 属性，而且在保证ACID的数据存储时往往有很差的可用性。Dynamo的目标应用程序是高可用性，弱一致性(ACID中的”C”)。

我觉得dynamo最吸引人的地方就是高度扩展性，以及完全托管，这个会节省开发人员大量的运维工作。
当然了不好的地方也是它的数据一致性要求不是很高，在99.94% 左右，而且遇到了不一致问题，都抛给了上层来解决，类似于git merge操作，如果对一致性要求比较高的话，这个还是挺麻烦的，当然了这个主要看应用的选型需求了，后期再详细介绍。

dynamo的高度扩展性，就是采用了一致性hash的原理来实现，我们来着重分析一下，它是如何采用采用一致性hash而达到高扩展性的。

二、数据分布
在dynamo 中创建table的时候，必须要指定一个分区键（partition），分区键可以用hash值，也可以用户自己指定，做唯一主键的时候，不能有重复。

对于刚接触Dynamo的时候不是很明白要如何应用分区键。那么为何要用分区键？

我们回顾一下，一致性hash的实现原理，一致性hash是把数据均匀的映射到一个线性空间，以保证分配的均匀性，以及提高数据的单调性。同时为了减少由于节点数过少导致移动过多的数据项，又加入了虚拟节点。如下:

引入了“虚拟节点”后，映射关系就从【object—>node】转换成了【object—>virtual node—> node】。查询object所在node的映射关系如下图所示。

以上virtual node我们就可以称为 partition，当增加新的node服务器的时候，由于virtual node没有变化，数据的hash值也是固定不变的，因此只需要处理一下，virtual node和node的重分配，这个对数据迁移的影响是最小的。

我们看下代码实现:

我们假设有256个node(2^8)，有partition数4096(2^12)。由于MD5码是32位的，使用PARTITION_SHIFT(等于32- PARTITION_POWER)将数据项的MD5哈希值映射到partition的2^12的空间中。此处引入了partition power 。

ITEMS = 10000000
NODES = 256
PARTITION_POWER = 12
PARTITION_SHIFT = 32
PARTITION = PARTITION_SHIFT - PARTITION_POWER
node_stat = [0 for i in range(NODES)]

#获取hash值
def _hash(value):
k = md5(str(value)).digest()
ha = unpack_from(“>I”, k)[0]
return ha

ring = []
part2node = {}

#虚拟节点和node节点做映射关系
for part in range(2 ** PARTITION_POWER):
ring.append(part)
part2node[part] = part % NODES

for item in range(ITEMS):
#把32位的hash值映射到12位的空间中
h = _hash(item) » PARTITION
#查找最近的partition
partition = bisect_left(ring, h)
n = partition % NODES
node_stat[n] += 1

_ave = ITEMS / NODES
_max = max(node_stat)
_min = min(node_stat)

这个就是为何dynamo在创建表的时候要指定分区键partition,因为要保证其数据的高扩展性，需要把数据分配到不同的node数据服务器上。
有了partition，一张表的数据，就可以分散到不同的node上，同时在数据进行扩容增加node的时候，因为数据的partition并没有发生变化，只是partition对应的node映射发生了变化，对数据的迁移影响是最小的。

三、数据冗余
在上述模型中，虽然解决的数据的扩展性问题，但数据的高可用问题，并没有去达成，每个node节点的数据都是单一的，如果这个节点出故障了，数据怎么处理？

为了让系统达到高可用性和持久性，防止由于节点宕机故障或而造成数据丢失，Dynamo中的数据被复制成N份存于多台主机中。
除了本地存储其范围内的每个结点将同一份数据在协调者和随后的 N-1 个节点上备份了多次，N 是一个可以配置的值，默认情况下是3，其理论依据主要来源于NWR策略。

NWR是一种在分布式存储系统中用于控制一致性级别的一种策略。在Amazon的Dynamo云存储系统中，就应用NWR来控制一致性。每个字母的涵义如下：

  N：同一份数据备份的份数



  W：是更新一个数据对象的时候需要确保成功更新的份数



  R：读取一个数据需要读取的最少节点（备份）的份数

只要满足W+R > N，就可以保证当存在不超过一台机器故障的时候，至少能读到一份有效的数据。如果应用重视读效率，可以设置W=N，R=1; 如果应用需要在读/写之间权衡，一般可设置成N=3, W=2, R=2。Dynamo推荐使用322的组合。

我们在这里称为Replica，在分布式系统中，数据的单点是不允许存在的，即线上正常存在的Replica数量是1的情况是非常危险的。

因为一旦这个Replica再次错误，就可能发生数据的永久性错误。假如我们把N设置成为2，那么，只要有一个存储节点发生损坏，就会有单点的存在。所以N必须大于2。N约高，系统的维护和整体成本就越高。工业界通常把N设置为3。

比如上图中，黄色区域的值会存储在三个节点 A、B 和 C 中，蓝色的区域会被 D、E、F 三个节点处理，负责存储某一个特定键值对的节点列表叫做偏好列表（preference list），因为虚拟节点在环中会随机存在，为了保证出现节点故障时不会影响可用性和持久性，偏好列表中的全部节点必须都为不同的物理节点。

我们来看实现方式

我们在上述代码中引入replica，数量设置为3，其中 node_ids记录的是3个replica存放的node id。part2node[part]是根据partition id 找到对应的node id，也是分区和node节点的映射关系。

ITEMS = 10000000
NODES = 100
PARTITION_POWER = 12
PARTITION_SHIFT = 32
PARTITION = PARTITION_SHIFT - PARTITION_POWER
PARTITION_MAX =2**PARTITION_POWER-1
REPLICAS = 3

node_stat = [0 for i in range(NODES)]

def _hash(value):
k = md5(str(value)).digest()
ha = unpack_from(“>I”, k)[0]
return ha

ring = []
part2node = {}

#虚拟节点和node节点做映射关系
for part in range(2 ** PARTITION_POWER):
ring.append(part)
part2node[part] = part % NODES

for item in range(ITEMS):
#把32位的hash值映射到12位的空间中
h = _hash(item) » PARTITION
part = bisect_left(ring, h)
node_ids = [part2node[part]]
node_stat[node_ids[0]] += 1

#数据replica处理，一份数据存放临近的3个物理节点
for replica in xrange(1, REPLICAS):
while part2node[part] in node_ids:
part += 1
if part > PARTITION_MAX:
part = 0
node_ids.append(part2node[part])
node_stat[node_ids[-1]] += 1

_ave = ITEMS / NODES* REPLICAS
_max = max(node_stat)
_min = min(node_stat)

四、数据一致性
1、冲突
由于加入了replica，特别是NWR 是322的情况下，一个读操作，必须得等待2个节点的数据返回对应结果，才认为当前请求结束了，也就是说会请求时间会受最慢节点的影响，写的情况也是相同。唯一的不同是，发现节点中数据出现了冲突，会对冲突尝试进行解决并将结果重新写回对应的节点。

Dynamo对数据的一致性要求没有那么高，会出现数据不一致情况，当然了多数情况下，Dynamo 都不会出现这种情况，并且即便出现了，Dynamo 能够确保一旦数据之间发生了冲突不会丢失，但是可能会有已被删除的数据重新出现的问题。

针对这种情况，Dynamo提供了向量时钟来解决，每一个对象版本中都存在一个或者多个向量时钟，每次更新数据的时候，都会更新向量时钟的版本。
如果待更新数据的向量钟的每一项都不小于本地向量钟，那么数据无冲突，新的值可以被接受。当客户端再次 请求时就会发现数据出现了冲突，由于 Dynamo 无法根据向量时钟自动解决，所以它需要客户端合并不同的数据版本。就类似git 的merge 操作，把问题抛给了调用方来解决。

2、故障
在一个节点出现临时性故障时，数据会自动进入列表中的下一个节点进行写操作，并标记为handoff数据，如果在指定的时间内该机器重新提供服务，则其他机器会通过Gossip协议发现，并将暂存的数据回传给该临时性故障的机器。

如果超时了一定的间隔，该机器还是处理宕机状态，则会认为是永久下线了，此时需要从其它副本同步数据。为了更快地检测副本之间的不一致性，并减少传输的数据量，Dynamo采用了Merkle树。Merkle树是一个哈希树，其叶子结点是各个key的哈希值，树中较高的父结点均为其各自孩子节点的哈希，通过这种方式构建的树形结构能够保证整棵树不会被篡改，任何的改动都能被立刻发现。如此检测快，数据传送的量也小，同步时只同步从根结点到叶子的所有节点值均不相同的文件。

一、前言
在开始HBase的学习之前，我们有必要了解一下NoSQL，为什么要使用NoSQL，NoSQL和关系型数据库的对比，NoSQL的特点以及NoSQL的基本概念–三大基石等，让我们带着疑惑开始学习吧！😄

二、为什么使用NoSQL
原因很简单，因为互联网的发展，传统关系型的数据库存在瓶颈，而NoSQL 数据库存在以下诸多优势：

高并发读写
高存储
高可用性
高扩展性
低成本
三、NoSQL和关系型数据库对比
对比 NoSQL 关系型数据库
存储格式 文档、键值对、图结构 表格式，行和列
存储规范 鼓励冗余 规范性，避免重复
存储扩展 横向扩展，分布式 纵向扩展（横向扩展有限）
查询方式 非结构化查询 结构化查询语言SQL
事务 不支持事务一致性 支持事务
性能 读写性能高 读写性能差
成本 简单易部署，开源，成本低 成本高
四、NoSQL 的特点
最终一致性

应用程序增加了维护一致性和处理事务等职责

冗余数据存储

NoSQL != 大数据

NoSQL产品是为了帮助解决大数据存储的问题
大数据不仅仅包含数据存储的问题 （Hadoop、Kafka、Spark）
五、NoSQL基本概念
三大基石 （CAP、BASE和最终一致性）
Indexing（索引）、Query（查询）
MapReduce
Sharding
接下来我会重点讲一下 NoSQL 的三大基石，这也是面试里常常会被问道的，所以当然要重点关注辣！😁

六、NoSQL的三大基石（CAP、BASE和最终一致性）

所谓的CAP指的是：
C（Consistency）：一致性，是指任何一个读操作总是能够读到之前完成的写操作的结果。也就是在分布式环境中，多点的数据是一致的，或者说，所有节点在同一时间(读写应该是单线程的，否则写过程的流水线复制过程中各数据节点内容可能不一致)具有相同的数据
A:（Availability）：可用性，可以在确定的时间内返回操作结果，保证每个请求不管成功或者失败都有响应；
P（Tolerance of Network Partition）：分区容忍性，是指当出现网络分区的情况时（即系统中的一部分节点无法和其他节点进行通信），分离的系统也能够正常运行，也就是说，系统中任意信息的丢失或失败不会影响系统的继续运作。

CAP
CAP理论告诉我们，一个分布式系统不可能同时满足一致性、可用性和分区容忍性这三个需求，最多只能同时满足其中两个，正所谓“鱼和熊掌不可兼得”。

举例，为满足一致性，需要确保多副本数据一致，就使得多副本写数据过程中无法响应读请求。所以，NOSql数据库都不能同时满足CA(一致性和可用性)两个要求。关系型数据库可同时满足CA(一致性和可用性)。典型的NOSql数据库Redis、HBase、MongoDB、Neo4j都不能满足CA特性，可满足CP特性。
　　
当处理CAP的问题时，可以有几个明显的选择：

CA：也就是强调一致性（C）和可用性（A），放弃分区容忍性（P），最简单的做法是把所有与事务相关的内容都放到同一台机器上。很显然，这种做法会严重影响系统的可扩展性。传统的关系数据库（MySQL、SQL Server和PostgreSQL），都采用了这种设计原则，因此，扩展性都比较差
CP：也就是强调一致性（C）和分区容忍性（P），放弃可用性（A），当出现网络分区的情况时，受影响的服务需要等待数据一致，因此在等待期间就无法对外提供服务
AP：也就是强调可用性（A）和分区容忍性（P），放弃一致性（C），允许系统返回不一致的数据

BASE

一个数据库事务具有ACID四性：

A（Atomicity）：原子性，是指事务必须是原子工作单元，对于其数据修改(包括新增，修改，删除数据)，要么全都执行，要么全都不执行
C（Consistency）：一致性，是指事务在完成时，必须使所有的数据都保持一致状态
I（Isolation）：隔离性，是指由并发事务所做的修改必须与任何其它并发事务所做的修改隔离
D（Durability）：持久性，是指事务完成之后，它对于系统的影响是永久性的，该修改即使出现致命的系统故障也将一直保持
BASE的基本含义是基本可用（Basically Availble）、软状态（Soft-state）和最终一致性（Eventual consistency）：

基本可用
基本可用，是指一个分布式系统的一部分发生问题变得不可用时，其他部分仍然可以正常使用，也就是允许分区失败的情形出现

软状态
“软状态（soft-state）”是与“硬状态（hard-state）”相对应的一种提法。数据库保存的数据是“硬状态”时，可以保证数据一致性，即保证数据一直是正确的。“软状态”是指状态可以有一段时间不同步，具有一定的滞后性

最终一致性
一致性的类型包括强一致性和弱一致性，二者的主要区别在于高并发的数据访问操作下，后续操作是否能够获取最新的数据。对于强一致性而言，当执行完一次更新操作后，后续的其他读操作就可以保证读到更新后的最新数据；反之，如果不能保证后续访问读到的都是更新后的最新数据，那么就是弱一致性。而最终一致性只不过是弱一致性的一种特例，允许后续的访问操作可以暂时读不到更新后的数据，但是经过一段时间之后，必须最终读到更新后的数据。
最常见的实现最终一致性的系统是DNS（域名系统）。一个域名更新操作根据配置的形式被分发出去，并结合有过期机制的缓存；最终所有的客户端可以看到最新的值。

备注：软状态关注数据在不同节点间同步的滞后性(关注同步状态)，最终一致性关注不同节点数据最终一致(关注最终结果)

最终一致性
如何实现各种类型的一致性？

对于分布式数据系统：

N — 数据复制的份数
W — 更新数据是需要保证写完成的节点数(一个写操作，只有W个节点都写成功，本次写操作才返回成功)
R — 读取数据的时候需要读取的节点数(一个读操作，只有R个节点都读成功，本次读操作才返回成功)

如果W+R>N，写的节点和读的节点重叠(可保证至少读取的一个节点数据是最新写入的数据)，则是强一致性。例如对于典型的一主一备同步复制的关系型数据库，N=2,W=2,R=1，则不管读的是主库还是备库的数据，都是一致的。一般设定是R＋W = N+1，这是保证强一致性的最小设定

如果W+R<=N，则是弱一致性(读取的R个节点，不能保证至少读取的一个节点数据是最新写入的数据)。例如对于一主一备异步复制的关系型数据库，N=2,W=1,R=1，则如果读的是备库，就可能无法读取主库已经更新过的数据，所以是弱一致性。

对于分布式系统，为了保证高可用性，一般设置N>=3。不同的N,W,R组合，是在可用性和一致性之间取一个平衡，以适应不同的应用场景。

如果N=W,R=1，任何一个写节点失效，都会导致写失败，因此可用性会降低，但是由于数据分布的N个节点是同步写入的，因此可以保证强一致性。

实例：HBase是借助其底层的HDFS来实现其数据冗余备份的。HDFS采用的就是强一致性保证。在数据没有完全同步到N个节点前，写操作是不会返回成功的。也就是说它的W＝N，而读操作只需要读到一个值即可，也就是说它R＝1。

像Voldemort，Cassandra和Riak这些类Dynamo的系统，通常都允许用户按需要设置N，R，W三个值，即使是设置成W＋R<= N也是可以的。也就是说他允许用户在强一致性和最终一致性之间自由选择。而在用户选择了最终一致性，或者是W<N的强一致性时，则总会出现一段“各个节点数据不同步导致系统处理不一致的时间”。为了提供最终一致性的支持，这些系统会提供一些工具来使数据更新被最终同步到所有相关节点。

七、NoSQL分类
主要分为以下四类：

八、列存储数据库(Wide Column Store)
终于讲到列存储数据库啦，我们HBase便是其中的佼佼者，我先简单的对列存储数据库做一个介绍，关于HBase 会在后面的文章中慢慢讲解。

将数据储存在列族
一个列族存储经常被一起查询的相关数据
每一个列族包含kv键值对的“列”，可以随行变化
应用于分布式数据存储和管理
优点
查找速度快
可扩展性强
容易进行分布式扩展

CAP是Consistency、Availablity和Partition-tolerance的缩写。分别是指：

1.一致性（Consistency）：每次读操作都能保证返回的是最新数据；

2.可用性（Availablity）：任何一个没有发生故障的节点，会在合理的时间内返回一个正常的结果；

3.分区容忍性（Partition-torlerance）：当节点间出现网络分区，照样可以提供服务。

CAP理论指出：CAP三者只能取其二，不可兼得。其实这一点很好理解：

首先，单机都只能保证CP

有两个或以上节点时，当网络分区发生时，集群中两个节点不能相互通信（也就是说不能保证可用性A）。此时如果保证数据的一致性C，那么必然会有一个节点被标记为不可用的状态，违反了可用性A的要求，只能保证CP。

反正，如果保证可用性A，即两个节点可以继续各自处理请求，那么由于网络不通不能同步数据，必然又会导致数据的不一致，只能保证AP。

一、单实例

单机系统和显然，只能保证CP，牺牲了可用性A。单机版的MySQL，Redis，MongoDB等数据库都是这种模式。

实际中，我们需要一套可用性高的系统，即使部分机器挂掉之后仍然可以继续提供服务。

二、多副本

相比于单实例，这里多了一个节点去备份数据。

对于读操作来说，因为可以访问两个节点中的任意一个，所以可用性提升。

对于写操作来说，根据更新策略分为三种情况：

1.同步更新：即写操作需要等待两个节点都更新成功才返回。这样的话如果一旦发生网络分区故障，写操作便不可用，牺牲了A。

2.异步更新：即写操作直接返回，不需要等待节点更新成功，节点异步地去更新数据（FastDFS文件系统的存储节点就是用这种方式，写完一份数据之后立即返回结果，副本数据由同步线程写入其他同group的节点）。这种方式，牺牲了C来保证A，即无法保证数据是否更新成功，还有可能会由于网络故障等原因，导致数据不一致。

3.折衷：更新部分节点成功后便返回。

这里，先介绍一下类Dynamo系统用于控制分布式存储系统中的一致性级别的策略–NWR：

*N：同一份数据的副本个数

*W：写操作需要确保成功的副本个数

*R：读操作需要读取的副本个数

当W+R>N时，由于读写操作覆盖到的副本集肯定会有交集，读操作只要比较副本集数据的修改时间或者版本号即可选出最新的，所以系统是强一致性的；反之，当W+R<=N时是弱一致性的。

如：(N,W,R)=(1,1,1)为单机系统，是强一致性的；(N,W,R)=(2,1,1)位常见的master-slave模式，是弱一致性的。

举例：

如像Cassandra中的折衷型方案QUORUM，只要超过半数的节点更新成功便返回，读取时返回多副本的一致的值。然后，对于不一致的副本，可以通过read repair的方式解决。read repair：读取某条数据时，查询所有副本中的这条数据，比较数据与大多数副本的最新数据是否一致，若否，则进行一致性修复。其中，W + R > N，故而是强一致性的。

又如Redis的master-slave模式，更新成功一个节点即返回，其他节点异步去备份数据。这种方式只保证了最终一致性。最终一致性：相比于数据时刻保持一致的强一致性，最终一致性允许某段时间内数据不一致。但是随着时间的增长，数据最终会到达一致的状态。其中，W+R<N，所以只能保证最终一致性。

此外，N越大，数据可靠性越好，但是由于W或者R越大，读写开销越大，性能越差，所以一般需要总和考虑一致性，可用性和读写性能，设置W，R都为N/2+1。

其实，折衷方案和异步更新的方式从本质上来说是一样的，都是损失一定的C来换取A的提高。而且，会产生’脑裂’的问题–即网络分区时节点各自处理请求，无法同步数据，当网络恢复时，导致不一致。

一般的，数据库都会提供分区恢复的解决方案：

1.从源头解决：如设定节点通信的超时时间，超时后’少数派’节点不提供服务。这样便不会出现数据不一致的情况，不过可用性降低。

2.从恢复解决：如在通信恢复时，对不同节点的数据进行比较、合并，这样可用性得到了保证。但是在恢复完成之前，数据是不一致的，而且可能出现数数据冲突。

光这样还不够，当数据量较大时，由于一台机器的资源有限并不能容纳所有的数据，我们会向把数据分到好几台机器上存储。

三、分片

相比于单实例，这里多了一个节点去分割数据。

由于所有数据只有一份，一致性得以保证；节点间不需要通信，分区容忍性也有。

然而，当任意一个节点挂掉，丢失了一部分的数据，系统可用性得不到保证。

综上，这和单机版的方案一样，都只能保证CP。

那么，有哪些好处呢？

1.某个节点挂掉只会影响部分服务，即服务降级；

2.由于分片了数据，可以均衡负载；

3.数据量增大/减小后可以相应的扩容/缩容。

大多数的数据库服务都提供了分片的功能。如Redis的slots，Cassandra的patitions，MongoDB的shards等。

基于分片解决了数据量大的问题，可是我们还是希望我们的系统是高可用的，那么，如何牺牲一定的一致性去保证可用性呢？

四、集群

可以看到，上面这种方式综合了前两种方式。同上分析，采用不同的数据同步策略，系统CAP保证各有不同。不过，一般数据库系统都会提供可选的配置，我们根据不同的场景选择不同的特性。

其实，对于大多数的非金融类互联网公司，要求并非强一致性，而是可用性和最终一致性的保证。这也是NoSQL流行于互联网应用的一大原因，相比于强一致性系统的ACID原则，它更加倾向于BASE：

Basically Available：基本可用性，即允许分区失败，除了问题仅服务降级；

Soft-state：软状态，即允许异步；

Eventual Consistency：最终一致性，允许数据最终一致性，而不是时刻一直。

Dynamo是Amazon设计的分布式KV存储系统。是为了满足Amazon庞大的电商业务而孕育的产物。Amazon的业务场景对存储系统提出以下严苛的要求：

系统高度可扩展：可以通过增加节点实现容量和性能的线性扩展
系统高可靠：决不能丢数据
系统高可用：在Amazon的业务场景中，要做到”Always-Write”
除此之外，Amazon的许多业务的数据模型相对比较简单，只需要通过Primary key去找到其数据内容，而且多数情况下数据内容比较小。这也意味着无需使用传统的关系型数据库的复杂数据模型。

Dynamo就是针对Amazon的这些应用场景而设计出来的底层存储系统，具备如下特点：

简单的存取模式，只支持KV模式的数据存取，对象小于1M
高可用性，即便在集群中部分机器故障，网络中断，甚至是整个机房下线，仍能保证用户对数据的读写
高可扩展性，除了能够跨机房部署外，动态增加，删除集群节点，同时对正常集群影响很小
数据的高可用性大于数据的一致性，短时间的数据不一致是可以容忍的，采用最终一致性协议
服务SLA保证条约，99.9%的请求要在300ms内返回

系统架构

上图描述了Amazon内部服务化的系统设计。请求从客户端发起，经过中间层的路由，最终到达底层的存储系统，如Dynamo，Amazon S3。我们在这里只讨论Dynamo的设计。

核心技术

一个分布式存储系统需要解决如下几个关键问题：

数据如何分布
数据可靠性
数据一致性
数据布局

关于数据如何布局，主要有两种思路：查表式和计算式。所谓查表式，即通过维护全局统一的映射表，需要访问数据时，先查询该表定位数据所在节点。计算式无需维护该映射表，需要访问数据时，通过一定规则计算出数据所在位置。

查表式和计算式各有优劣：

查表式需要一个中心服务器维护全局的映射表信息，这可能成为系统的瓶颈；
而计算式的主要问题在于存储节点的变更可能带来大量的数据迁移，增加系统复杂度。
查表式的代表是GFS，Dynamo则采用的是计算式。计算式的简单抽象如下图：

整个系统在一个特定的环形运算空间，我们称为Ring。运算空间的大小可自己定义，例如，该空间范围取值为[0, 2**32 - 1]，而之所以称为环形空间是当超出该值后继续归零。

对存储系统中的每个节点的特征值在该空间内进行运算，例如，取节点的特征为其IP地址，对其ip地址进行hash运算，然后在运算空间内取模，得到其在环形运算空间上的值。如上图，A~G每个节点根据其运算得到的值而位于该Ring上的不同位置。

写入对象数据时，首先根据对象key(一般是对象名)在运算空间内计算其特征值，然后在该Ring上沿着顺时针方向查找与其特征值最接近的节点。例如上图的对象K，计算其特征值位于A、B节点之间，根据规则，那K应该被存储在节点B上。

这种方法看似完美，一次计算即可得出其存储节点最终位置。但可能带来以下的致命问题：

新增一个节点，原本存储在Ring上与其相邻节点的数据现在落在了该新增节点上，那势必需要进行数据迁移；
移除一个节点，那原本由该节点负责的数据接下来要由其相邻节点负责，也会带来数据的迁移。

由于计算式数据定位的天然特性，数据迁移的问题根本无法避免。但是上面的方案的问题是数据迁移发生在两个相邻节点之间，如果每个节点存储的数据量很大，那数据迁移带来的压力势必会影响参与迁移的节点正常的请求，导致不可用。

既然无法避免，那就尽量缓解。Dynamo设计中引入了虚拟节点（partition）。所谓的虚拟节点其实就是在一个物理节点（如上面的A/B/C/D）上虚拟出多个逻辑节点。例如A-1、A-2、A-3 ……，将这些虚拟节点参与环形运算空间的计算，如下图：

上图中每个物理节点虚拟出了两个逻辑节点，定位时，首先根据对象key计算其所在的虚拟节点，最后查表知道该虚拟节点位于的物理节点。相当于是一个二级映射函数。

这样做法的好处时，在新增或者移除节点时，会有更多的节点参与到数据迁移过程中，提升迁移效率，但是却无法从根本上避免数据迁移。

从理论分析就知道数据迁移过程参与的节点更多了，效率自然就提升了。

而物理节点如何划分虚拟节点，个人感觉根据实际的使用场景来决定。例如，jedis就使用虚拟ip(真实ip后加上节点编号)。

在存储系统中，物理节点其实抽象的是磁盘，虚拟节点其实就是代表了磁盘上的某个目录（经常称之为Partition）。而一般虚拟节点的数目固定，为2**N个。这样，对象key与虚拟节点的映射关系就可以保持固定，改变的是虚拟节点至物理节点的映射关系。

这种二级映射带来的好处是：

一级映射时增加节点移动的数据单位是单个对象，扫描计算哪些对象需要移动时代价太大；
二级映射时节点变化只影响虚拟节点的情况，新增或者移除节点(磁盘设备)时只需要迁移虚拟节点的数据即可，管理的成本大大减少。

引入虚拟节点后，典型的数据定位流程是：

根据对象名计算MD5，并取MD5的低N位得到虚拟节点编号（这也是为什么虚拟节点数目最好选择2的N次方的原因）；
查表获得虚拟节点所在的物理节点
数据可靠性

保证数据高可靠性的做法一般是使用多副本：即一个对象的数据被写入多个虚拟节点，而且还得要求这多个虚拟节点位于不同的物理节点上。对于存储系统来说，要求多副本位于不同的机器的不同磁盘上。

一般来说，系统在初始化时便会根据系统当前的物理节点数量为每个虚拟节点分配多个物理节点作为多副本：

每个虚拟节点使用如下规则选择其多个存储副本：

对象K根据计算应该落在虚拟节点B上，同时，会选择B的后继虚拟节点C、D作为另外两个副本。但是需要注意的是B、C、D三个虚拟节点必须位于不同的物理节点。

数据一致性

既然存在数据多副本，那就不得不探究下多副本之间的数据一致性问题。Dynamo采用的是最终一致性模型：即虚拟节点的多个副本之间可能会存在不一致的时间窗口，但最终系统会保证多个副本之间数据达成一致。

之所以存在数据不一致窗口，是因为Dynamo为了降低写延迟，客户端将数据推送至虚拟节点的主副本后，该副本除写本地外，还将数据推送至其他副本，但是该副本可以选择等到或者不等其他副本返回应答即可给客户端响应说数据已经正确写入。这时候如果客户端去读那些还没来得及写入数据的副本，便会读不到数据或者读到旧数据，出现数据不一致。

Dynamo使用W+R>N的策略来保证读取数据的正确性：

W：数据写入时返回给客户端前保证已经写入的副本数

R：数据时需要读取的副本数

N：对象副本数
根据鸽笼原理，只W+R>N，便可以保证客户端一定能读到最新版本的数据。

那这就带来了另外一个问题：如何在多个数据副本之间判断谁的数据更新？

Dynamo使用向量时钟来解决该问题。简单来说，接受客户端写请求的副本会为该数据的本次更新增加一个逻辑时间戳，该时间戳为一个二元组<updater, version>

updater：更新的执行者
version：本次更新的版本号
例如，A本地对象object的当前版本为<A, 1>，接下来A又收到客户端的对象更新请求，那么A更新对象数据的同时，将其版本修改为<A, 2>。

假如该对象有另外一个副本位于节点B，B上该对象的版本依然为<A, 1>，如果客户端的更新请求没有发往A，而是发到了B（这是有可能的，因为很可能客户端和A之间发生了网络分区）。B更新对象数据的同时，更新其版本为<A, 1>, <B, 1>，然后将本次更新连同其版本一并发送至其他副本节点。

上图演示了对于一个对象的两次更新过程，第二次中原来的主副本和客户端之间出现了网络不连通的问题，导致客户端选择出了新的主副本。

上图演示了在主从同步出现延迟的情况下客户端的连续数据更新导致数据版本的冲突问题。

客户端读数据时，会根据R的设置从多个副本中读出数据，然后对比副本数据的向量时钟的版本，选择最新的数据版本返回给客户端。但是有可能出现无法合并的情况，例如上面的A节点上数据版本为<A, 2>，B节点上数据版本为<A, 1>, <B, 1>。遇到这种情况，只能交给应用去选择合并了。

再考虑下面这种并发更新的情况：

系统当前是三副本，某个partition的三个副本分别为Sx，Sy，Sz，且R=2， W=2。按照下面的顺序进行数据更新：

数据在Sx节点写入，产生数据的新版本为<Sx, 1>，并同步至Sy，Sz；
数据在Sx节点更新，产生数据新版本为<Sx，2>，并同步至Sy，Sz；
截止目前，Sx，Sy，Sz三个节点的数据版本均为<Sx, 2>，数据处于一致状态；
由于某种原因，A客户端选择了Sy节点对数据进行更新，而此时A客户端看到的数据版本为<Sx, 2>，因此，A向Sy节点发送数据更新请求，且指明本次更新的版本为<Sx, 2>，Sy节点收到更新请求后，选择更新本地数据的版本为<Sx, 2>，<Sy, 1>；
在4进行的过程中，客户端B选择了Sz节点对数据进行更新，此时B客户端看到的数据版本也是<Sx, 2>，于是B给Sz发送请求更新对象的<Sx, 2>的版本数据。Sz同样更新本地的数据以及版本为<Sx, 2>, <Sz, 1>；
接下来数据主从同步的过程中，无论是Sy将自己的数据同步至Sz，还是Sz将数据同步至Sy，都会发现他们之间的数据其实是存在冲突的，而且存储系统自身是无法解决这种冲突的，于是，继续保存这种冲突数据，但是在Sy(或者Sz)向Sx同步数据的时候是没问题的，因为通过向量时钟比对发现Sx的版本无论比Sy还是Sz都要更小；
接下来，客户端发起对数据的读请求，因为存在冲突，冲突的版本都会被发送至客户端，于是客户端看到的数据版本是{<Sx, 2>, <Sy, 1>}和{<Sx, 2>, <Sz, 1>}。接下来应用程序根据自己的业务逻辑尝试去解决冲突，例如，最终选择了{<Sx, 2>, <Sy, 1>}作为最终的数据，那接下来会将自己的协调结果写到某个副本（假如选择Sx写入）上，需要注意的是，客户端指定更新的版本为<Sx, 2>, <Sy, 1>, <Sz, 1>，而Sx收到请求后，会将对象的版本更新为<Sx, 3>,<Sy, 1>, <Sz, 1>。如此这样，接下来Sx将新版本的数据推送到其他副本的时候，就不会在出现冲突了，因为无论是Sy节点上的<Sx, 2>, <Sy, 1>还是Sz节点上的<Sx, 2>, <Sz, 1>均落后于Sx上的当前版本，大家又达成了数据一致性
Handoff机制

所谓的HandOff机制是对Dynamo可用性的进一步提升手段。如同我们上面说到，正常情况下，客户的写入数据会被复制到ring上的N个节点。但是一旦出现异常时，写入的节点不可达，这时候可能就会出错，如下：

假如数据应该被写入至节点A并复制到B和C，但是此时假如A节点异常，可能就会导致数据不可写。

Dynamo的做法是引入Handoff节点，例如这里的D作为A的Handoff，A节点不可写的时候，数据会被写入D，但是在D上这些数据会被存储在特殊位置并且有元数据信息描述该数据的原始位置（A）。一旦D检测到A节点恢复，就会将该本来不属于自己的数据迁移至原本的位置（A）。

节点状态探测

使用Gossip协议来在所有节点之间维护集群的map信息。具体的可以参考论文，但这种做法看起来是复杂了点。

关键流程
在Dynamo的对象副本中，存在一个副本充当协调者的角色，称之为coordinator。该协调者负责处理客户端的读写请求。

写流程

coordinator接受客户的写请求，处理：

为该请求生成向量时钟或者更新对象已有的向量时钟并将数据及其时钟更新至本地
将更新请求发送至所有其他副本；
只要收到其他W-1个副本的回应，就认为本次写成功，给客户端返回响应。
读流程

coordinator接受客户的读请求，处理：

coordinator将请求发送至所有其他副本；
只要收到其他R-1个副本的回应，coordinator认为本次读成功；
coordinator对R个副本（包括自己的一个副本）的内容进行merge，取最新的版本返回给客户端；如果发生冲突无法决定谁的版本最新，那么coordinator就会将产生冲突的版本全部发给客户端；
客户端如果收到了多个冲突版本，会自己解决冲突并将解决的结果写入coordinator，通知其以该版本为最新，后续所有的读取就不再会产生冲突了。
实现细节
在Dynamo中，存储节点主要由三个主要部分组成：

请求处理器
成员管理和错误检测
存储引擎
模块化存储引擎设计

Dynamo底层的存储引擎使用模块化设计，支持可插拔，支持诸如BDB、Mysql等作为底层数据存储容器。

负载均衡

我们前面说过无论读写都存在一个coordinator角色，客户端的所有访问都经过该coordinator，这导致的一个问题是该coordinator的复杂会超过其他副本。好处是所有的读写都串行化了，可以保证数据的一致性。但是缺点也是显而易见的：如果所有的写都是随机选择coordinator，那么很难保证数据副本之间的一致性。假如客户端A写入副本1，而客户度B选择向副本2写入，如果此时A和B并发写的话，那毫无疑问最终会错乱，在一个时间窗口内，会出现数据的不一致。不过想了想，好像Dynamo的应用场景主要是一次写多次读的场景，这种情况并不常见，这个问题待讨论。