Reference：Dynamo: Amazon’s Highly Available Key-value Store
Dynamo是Amazon在07年SOSP上提出的分布式KV解决方案，是基于变种一致性Hash算法与矢量时间戳的Nosql数据库，注重AP。
系统设计需求
- QueryModel - 单纯kv查询
- ACID - 没有isolation，只允许单key
- Efficience - 性能、成本、可靠性、持久性trade-off
- Safety - 内网部署,不提供授权机制
- Service Level Agreement - 不注重平均，注重极端99.9%的情况
- Consistency - 最终一致性
- Always writable - 冲突集中到Read从而避免拒绝write
- Conflict Resolution - 应用服务器决议冲突，自行决定适合方法
- Incremental scalability：增加新节点影响最小。
- Symmetry: 所有节点职责相同
- Decentralization: 去中心化,p2p
- Heterogeneity: 异构化,可以单独为某个节点提供更多容量而无需变更整体
系统架构
一致性Hash算法改进
Sharding
首先是基本的带虚拟节点的一致性hash保证partition，amazon给了标准答案。除了最基本的在增/删时能均分负载之外，通过调整虚拟节点个数实现异构。
Replication
然后是保证replication,将Key对Node的查找延伸到了后面N个物理节点，从而在负载均衡层面就达成了Replication。紧跟着的节点就是Coordinator，后继作为Participant。这里每个节点维护>N个物理节点(跳过相同地址的虚拟节点)的preference list以容错
妙啊,可惜当时写lab的时候没看,负载均衡底下又整了个2PC。
Data Versioning - 矢量时间戳
MVCC，数据都是immutable的,所有的写操作并不会引起数据的修改，而是创建新版本的数据。
为了处理同时多个分支版本(e.g. git merge)出现的问题，这里采用矢量时间戳: (node, counter)列表 。如果矢量时间戳的每个维度都更大或者相同，则认为发生在其后;否则需要进行调解。
当进行写操作时，用户必须先指定对应的版本。
在Read时，将会顺带着返回对应的矢量时间戳，以及所有分支。这个调解将由客户端完成，然后通过写操作把合并的时间戳写回。
由于这里key只涉及到相关的n个节点，因此矢量时间戳的大小是有限的。当发生failure时，因为会新增服务器，需要限制size增长。这里通过为每个维度增加Modified Time，当维度超过10时就淘汰最老的。合并的时候会增加开销，不过amazon表示生产环境没遇到这问题。
读写执行流
请求可以通过普通的负载均衡，也可以直接指定coordinator
负载均衡会分发到随机节点上，然后该节点进行forward转发给key对应的preference list第一个可用的服务器作为coordinator。(这里没有用专门的节点做一致性hash，和之前提到的去中心化有关)
这里用到了之前学过的算法。读和写有着不同的Quorum，
和
，通过才成功
，这样两个majority之间必然存在交集。读的开销大时，读的额度就应该适当减少，vice versa。也可以通过额度控制availability。
下面两个情况都需要Quorum通过
- 写的时候coordinator将会收到矢量时间戳，并且通知前N个preference list的节点
- 读的时候coordinator将会从N个节点收集矢量时间戳，并且将结果返回给客户端调解。
Weighted voting for replicated data
异常处理
hinted handoff
这里的并不是严格的quorom，而是sloppy quorum，也就是跳过那些无法服务的节点。这样的话即使节点崩了，读写的Quorum都是在这些可服务节点中进行选举的，从而保证了availability。当然这样肯定会牺牲一定的consistency(比如突然崩了一堆,结果你读了新加入节点的数据)。
通过调节
可以改变操作的availability。
Replica synchronization
这里用了Merkle tree，一种自底向上建立的哈希树。这个数据结构常常用来校验数据的完整性，例如在TEE中进行内存的校验。这里的Merkle Tree是针对虚拟节点建立的，因为节点变动涉及的数据是以虚拟节点为单位。
- 建立时，Merkle Tree会把相邻block进行hash，将相邻hash再hash，最后变为单hash。
- 校验时，自顶向下校验，首先看根节点，然后向下直到叶。这样可以最小化校验的开销。
也存在问题，例如物理节点加入/离开时，校验会产生大量开销。因此后面做了优化。
成员监测
gossip-based protocol
节点创建时随机选择一组虚拟节点进行映射，一开始的时候只知道本地信息，每秒钟随机选一个peer交换信息(一开始通过seed)，最后知道整体的view(zero-hop DHT）。这里也是利用最终一致性。
然后在负载均衡时，正确的forward到对应的peer上。(也就是说每个节点本身都承载着一致性hash的职责,去中心化)
External Discovery
假如让A加入环，B也加入环，两个节点都不知道彼此，因此无法gossip。因此需要seed，seed通过静态配置或者服务配置，能够被所有节点知晓，从而担任沟通的桥梁。
Failure Detection
避免向那些无法达到的节点发送无意义的请求，如果请求失败了，就替换节点，并且定期地询问该节点是否恢复。每个节点只负责自己的hinted handoff。(分区情况，例如A->B无法通信，但是C->B可以）
成员变化
这里非常巧妙地利用上面提到的
实现了平滑扩容，节点新增时，原本的
依然能处理读请求，同时那些通过gossip知道变化的节点会主动把不再负责的数据迁移到新增的节点上。因为虚拟节点，数据来源于不同节点，可以并发地迁移数据。 通过在source->dest间增加配置，已经迁移之后的数据将不会继续被迁移。
优化
参数选择
Amazon将(N,R,W)设定为(3,2,2)，这里的数值越大则C越大，越小则A越大。所以出于performance, durability, consistency, and availability 考虑选择这个值。
Balancing Performance and Durability
增加write buffer，提高读写性能，降低持久性。
Ensuring Uniform Load distribution
下面的T为常数，Q为总分段数，S为总节点数目
- Strategy 1: T random tokens per node and partition by token value
- Strategy 2: T random tokens per node and equal sized partitions
- Strategy 3: Q/S tokens per node, equal-sized partitions
客户端协调
避免额外增加一个服务器专门协调带来的开销
后台任务
监控前台读写资源占用率，仅在空闲的时候进行同步、数据迁移等操作
Problem: 高可用，可拓展性，高性能的KV
Related work: 注重C而不是A, SQL数据库维护太多额外信息，不易拓展与负载均衡
Observation: P2P Quorum for R and W Vector Clock
Solution: P2P保证负载均衡与去中心化，Quorum保证可用性，矢量时间戳进行MVCC
Evaluation: 最终一致性，每个Dynamo都持有全局view直接forward
Comments: 如果继续拓展，全局view显然不可维护，也不容易gossip。
