序：前几日网上偶尔看到”程序员必读论文系列“，顺便搜了一下，发现有多个版本共31篇，不过看起来都不错，故准备花时间都读一下，可以拓宽下视野。来源论文题目主要参考 http://blog.csdn.net/turingbook/article/details/3946421 和 http://top.jobbole.com/17733/ 。每读完一篇论文就写些笔记，或长或短，也就是这几篇文章的由来。

1. An Axiomatic Basis for Computer Programming. 1969年的一篇论文，主要讲用公理基础证明计算机编程的正确性，包括赋值/递推/组合/循环等。不是那么容易读懂，特别是一些数理符号，想要完全看懂估计得查不少书。扫过重要的部分，关键就是 P{Q}R， 即前置条件满足assert(P) 为true，Q是一段程序（可以是多个子程序的组合），后置条件R是人们可以期望的正确结果，跟Q的执行输出有关，若assert(R)为true，可以证明Q是正确的程序。

2. Dynamo: Amazon’s Highly Available Key-value Store.2007年的这篇论文长达16页，详细介绍了曾经服务于Amazon Services的一个key/value 分布式存储系统，包括背景需求，设计与实现，同类产品的研究工作，生产过程中使用Dynamo的经验等。Amazon Services是高度去中心化，松耦合和以服务为导向的架构，故Dynamo也是去中心化的，对于Amazon Services来说只需要通过Key查询数据，故传统关系型数据库复杂的查询逻辑在此派不上用场，此外关系型数据库也没有很好的复制技术，以便支撑因为负载均衡而产生的数据库的扩展和分区需求。如下图所示。一个客户端请求需要多个services服务，需要Aggregator Services来做聚合。一个node认为是一台host，一个instance是多个node的集合，一个services使用自己的instances。

Dynamo 的可扩展性和可用性采用的都比较成熟的技术，数据分区并用改进的(virtual node)一致性哈希[3](consistent hashing)方式进行复制，利用数据对象的版本化和vector clock实现最终一致性。更新时因为副本之间产生的一致性问题的维护采取类似 quorum[1] 的机制以及去中心化的复制同步协议[2]。

Dynamo的实现是一个最终一致性的数据存储，对于分布式系统的CAP原理来说，牺牲了部分一致性，也就是弱一致性模型，提高可用性，即”always writeable"。

对于数据冲突的解决并不是传统的 read only write all，而是类似quorum机制把部分压力给了read。而解决冲突的执行者不是application而是data store，使用的是简单的"last write wins" 策略。

数据分区策略：采用改进的一致性哈希算法，也就是引入virtual nodes，即可以将一个真实物理host映射为n个虚拟nodes，这样可以实现load balance，特别是不同物理host的容量不一致的情况下，比如容量大的主机的n值可以大些。

数据复制策略：Dynamo 会将数据复制在N台host上，N是一个instance的配置参数。通常除由一个协调node存储在本地外，还负责复制到它的两个顺时针走向的N-1个node上。注意，如果使用了virtual node，则负责如下图Key K （K=hash(dataobject)）的 preference list 会跳过一些位置，以保证list只包含真正的物理nodes。To account for node failures, preference list contains more than N nodes.

如上图所示，Key K 的数据会存在node B, C, D（N=3）。同理对于node D来说，Node D will store the keys that fall in the ranges (A, B], (B, C], and (C, D].

数据同步策略：采用类似于 Quorum 系统的一致性协议实现（“sloppy quorum”： all read and write operations are performed on the first N healthy nodes from the preference list, which may not always be the first N nodes encountered while walking the consistent hashing ring.）。这个协议有两个关键值：R 与 W。R 代表一次成功的读取操作中最小参与节点数量，W 代表一次成功的写操作中最小参与节点数量。R + W>N ，则会产生类似 quorum 的效果。该模型中的读(写)延迟由最慢的 R(W)副本决定，为得到比较小的延迟，通常R 和 W各自的值设置得比 N 小。

若(N,R,W) 的值设置为 (3, 2 ,2)。举例get()和put()操作来说，读写通常由一个协调node来处理（preference list的第一个node）。

对于一个key的put()操作，协调node会为此版本的数据产生vector clock 类似[Sx, 1]（Sx表示node），并将数据写在本地，此外会将数据带上vector clock信息发送给另外N-1=2个node，但只要W-1=1个node回应就表示说写成功（当然最后一个node的写进程还是在进行的）。

同样地，对于一个key的get()操作，协调node会向所有存在此数据任何版本的node发起请求（包括自己），如果有R=2个node响应表示读取成功。如果此时两个版本的数据不一致，协调node会进行合并操作并将最新的版本write back。

注：对于一般的session信息存储，是由协调node来执行"last write wins" 合并数据版本。而类似购物车信息之类的是由application logic 自己来执行合并数据版本。

数据容灾策略：以上图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[4]的Anti-Entropy系统，如下图所示：

A Merkle tree is a hash tree where leaves are hashes of the values of individual keys. Parent nodes higher in the tree are hashes of their respective children. 也就是说如果比对两个副本，只需要从root节点开始比对，如果相等则数据一致，否则继续找子节点比对下去，直至找到hash值不一致的节点，同步这部分数据即可。

伙伴关系和失败发现策略：

由于各种各样的原因，暂时性的节点掉线是时有发生的。如果因为一个节点暂时性的掉线，而导致副本迁移等代价高昂的操作显然是不合适的。所以Dynamo提供了一组命令行接口和HTTP接口供管理员手工添加，删除节点。一旦一个节点的角色发生改变（上线或下线等），它都会将状态改变的时间存储到一个持久的数据库中，这些数据构成了一个节点的状态变迁历史。然后通过一个Gossip-Based Protocol将这个消息传递出去。节点在收到其它节点的消息时，会将收到的消息与自己本地存储的消息进行合并，最终每个节点都会得到整个集群的信息。为了应对可能出现的“logical partitions”现象，某些Dynamo节点作为“种子”节点，种子节点可以通过全局的方式被其它所有节点发现，最终所有的节点自己存储的状态信息都与种子节点的状态信息合并。与正常节点发现类似，对错误节点的发现机制也是使用的Gossip-Based Protocol，每个节点都记录自己与其它节点的连通状态。

具体实现：Dynamo的一个存储node主要由三个组件组成，包括请求处理、伙伴关系与失败检测、持久型存储引擎。这三者都是用java实现。对于存储引擎来说，提供多种选择，application可以选择适合自己的引擎，比如 Berkeley Database (BDB) Transactional Data Store2, BDB Java Edition, MySQL, and an in-memory buffer with persistent backing store. 

参考：

[1]. http://www.cnblogs.com/jzhlin/archive/2012/07/23/Quorum.html

[2]. http://dbanotes.net/tech-memo/amazon_dynamo.html

[3]. http://dl.acm.org/citation.cfm?id=258660

[4]. http://blog.csdn.net/xtu_xiaoxin/article/details/8148237

建议程序员都读一读的31篇论文系列笔记(1~2)