发布时间 : 星期五 文章NoSQL数据库学习教程更新完毕开始阅读24a5d7523c1ec5da50e270b1
http://blog.sina.com.cn/mpl398235717
然而，在最后的八个月左右，他们―盔甲‖内的漏洞开始呈现出来了。第一个弱点前兆是，新加入的Amazon SMALL实例的性能出现了问题。根据我们的监控，在服务器场中新添加的机器，与原先的那些相比性能有所下降。开始我们认为这是自然出现的怪现象，只是碰 巧发生在―吵闹的邻居‖（Noisy Neighbors）旁边。根据随机法则，一次快速的停机和重新启动经常就会让我们回到―安静的邻居‖旁边，那样我们可以达到目的。
然而，在最后的一两个月中，我们发现，甚至是这些―使用高级CPU的中等实例‖也遭受了与小实例相同的命运，其中，新的实例不管处于什么位置，看起来似乎都表现得一样。经过调查，我们还发现了一个新问题，它已经悄悄渗透到到Amazon的世界中，那就是内部网络延迟。
算法的选择
不同的哈希算法可以导致数据分布的不同位置，如果十分均匀，那么一次MapReduce就涉及节点较多，但热点均匀，方便管理。反之，热点不均，会大致机器效率发挥不完全。
Quorum NRW
? ? ?
N: 复制的节点数量
R: 成功读操作的最小节点数 W: 成功写操作的最小节点数
只需W + R > N，就可以保证强一致性。
第一个关键参数是 N，这个 N 指的是数据对象将被复制到 N 台主机上，N 在实例级别配置，协调器将负责把数据复制到 N-1 个节点上。N 的典型值设置为 3.
复制中的一致性，采用类似于Quorum 系统的一致性协议实现。这个协议有两个关键值：R 与 W。R 代表一次成功的读取操作中最小参与节点数量，W 代表一次成功的写操作中最小参与节点数量。R + W>N ，则会产生类似 quorum 的效果。该模型中的读(写)延迟由最慢的 R(W)复制决定，为得到比较小的延迟，R 和 W 有的时候的和又设置比 N 小。
如果N中的1台发生故障，Dynamo立即写入到preference list中下一台，确保永远可写入 如 果W+R>N，那么分布式系统就会提供强一致性的保证，因为读取数据的节点和被同步写入的节点是有重叠的。在一个RDBMS的复制模型中 （Master/salve)，假如N=2,那么
W=2,R=1此时是一种强一致性,但是这样造成的问题就是可用性的减低，因为要想写操作成功，必须要等 2个节点都完成以后才可以。
在分布式系统中，一般都要有容错性，因此一般N都是大于3的，此时根据CAP理论，一致
http://blog.sina.com.cn/mpl398235717
http://blog.sina.com.cn/mpl398235717
性，可用性和分区容错 性最多只能满足两个，那么我们就需要在一致性和分区容错性之间做一平衡，如果要高的一致性，那么就配置N=W，R=1,这个时候可用性就会大大降低。如果 想要高的可用性，那么此时就需要放松一致性的要求，此时可以配置W=1，这样使得写操作延迟最低，同时通过异步的机制更新剩余的N-W个节点。
当存储系统保证最终一致性时，存储系统的配置一般是W+R<=N,此时读取和写入操作是不重叠的，不一致性的窗口就依赖于存储系统的异步实现方式，不一致性的窗口大小也就等于从更新开始到所有的节点都异步更新完成之间的时间。
(N,R,W) 的值典型设置为 (3, 2 ,2),兼顾性能与可用性。R 和 W 直接影响性能、扩展性、一致性，如果 W 设置 为 1，则一个实例中只要有一个节点可用，也不会影响写操作，如果 R 设置为 1 ，只要有一个节点可用，也不会影响读请求，R 和 W 值过小则影响一致性，过大也不好，这两个值要平衡。对于这套系统的典型的 SLA 要求 99.9% 的读写操作在 300ms 内完成。
无 论是Read-your-writes-consistency,Session consistency,Monotonic read consistency,它们都通过黏贴（stickiness)客户端到执行分布式请求的服务器端来实现的，这种方式简单是简单，但是它使得负载均衡以 及分区容错变的更加难于管理，有时候也可以通过客户端来实现Read-your-writes-consistency和Monotonic read consistency,此时需要对写的操作的数据加版本号，这样客户端就可以遗弃版本号小于最近看到的版本号的数据。
在系统开发过程 中，根据CAP理论，可用性和一致性在一个大型分区容错的系统中只能满足一个，因此为了高可用性，我们必须放低一致性的要求，但是不同的系统保证的一致性 还是有差别的，这就要求开发者要清楚自己用的系统提供什么样子的最终一致性的保证，一个非常流行的例子就是web应用系统，在大多数的web应用系统中都 有―用户可感知一致性‖的概念，这也就是说最终一致性中的―一致性窗口\大小要小于用户下一次的请求，在下次读取操作来之前，数据可以在存储的各个节点之 间复制。还比如假如存储系统提供了
read-your-write-consistency一致性，那么当一个用户写操作完成以后可以立马看到自己的更 新，但是其它的用户要过一会才可以看到更新。
几种特殊情况：
W = 1, R = N,对写操作要求高性能高可用。
R = 1, W = N , 对读操作要求高性能高可用，比如类似cache之类业务。
W = Q, R = Q where Q = N / 2 + 1 一般应用适用，读写性能之间取得平衡。如N=3,W=2,R=2
Vector clock
http://blog.sina.com.cn/mpl398235717
http://blog.sina.com.cn/mpl398235717
vector clock算法。可以把这个vector clock想象成每个节点都记录自己的版本信息，而一个数据，包含所有这些版本信息。来看一个例子：假设一个写请求，第一次被节点A处理了。节点A会增加一个版本信息(A，1)。我们把这个时候的数据记做D1(A，1)。 然后另外一个对同样key(这一段讨论都是针对同样的key的)的请求还是被A处理了于是有D2(A，2)。
这个时候，D2是可以覆盖D1的，不会有冲突产生。现在我们假设D2传播到了所有节点(B和C)，B和C收到的数据不是从客户产生的，而是别人复制给他们的，所以他们不产生新的版本信息，所以现在B和C都持有数据D2(A，2)。好，继续，又一个请求，被B处理了，生成数据D3(A，2;B，1)，因为这是一个新版本的数据，被B处理，所以要增加B的版本信息。
假设D3没有传播到C的时候又一个请求被C处理记做D4(A，2;C，1)。假设在这些版本没有传播开来以前，有一个读取操作，我们要记得，我们的W=1 那么R=N=3，所以R会从所有三个节点上读，在这个例子中将读到三个版本。A上的D2(A，2);B上的D3(A，2;B，1);C上的D4(A，2;C，1)这个时候可以判断出，D2已经是旧版本，可以舍弃，但是D3和D4都是新版本，需要应用自己去合并。
如果需要高可写性，就要处理这种合并问题。好假设应用完成了冲入解决，这里就是合并D3和D4版本，然后重新做了写入，假设是B处理这个请求，于是有D5(A，2;B，2;C，1);这个版本将可以覆盖掉D1-D4那四个版本。这个例子只举了一个客户的请求在被不同节点处理时候的情况， 而且每次写更新都是可接受的，大家可以自己更深入的演算一下几个并发客户的情况，以及用一个旧版本做更新的情况。
上面问题看似好像可以通过在三个节点里选择一个主节点来解决，所有的读取和写入都从主节点来进行。但是这样就违背了W=1这个约定，实际上还是退化到W=N的情况了。所以如果系统不需要很大的弹性，W=N为所有应用都接受，那么系统的设计上可以得到很大的简化。Dynamo 为了给出充分的弹性而被设计成完全的对等集群(peer to peer)，网络中的任何一个节点都不是特殊的。
Virtual node
http://blog.sina.com.cn/mpl398235717
http://blog.sina.com.cn/mpl398235717
虚拟节点，未完成 gossip
Gossip协议是一个Gossip思想的P2P实现。现代的分布式系统经常使用这个协议，他往往是唯一的手段。因为底层的结构非常复杂，而且Gossip也很有效。
Gossip协议也被戏称为病毒式传播，因为他的行为生物界的病毒很相似。
Gossip (State Transfer Model)
在状态转移到模式下，每个重复节点都保持的一个Vector clock和一个state version tree。每个节点的状态都是相同的(based on vector clock comparison),换句话说，state version tree包含有全部的冲突updates.
At query time, the client will attach its vector clock and the replica will send back a subset of the state tree which precedes the client's vector clock (this will provide
monotonic read consistency). The client will then advance its vector clock by merging all the versions. This means the client is responsible to resolve the conflict of all these versions because when the client sends the update later, its vector clock will precede all these versions.
http://blog.sina.com.cn/mpl398235717