System|分布式|Dynamo

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。