6.824 阅读笔记4 —— dynamodb

Dynamo: Amazon’s Highly Available Key-value Store

今天来看dynamodb。前面的introduction，related work啥的先放一边，直接来看system architecture

4 System Architecture

本论文主要关注点为dynamo的partitioning, replication, versioning, membership, failure hadling and scaling。

4.1 System Interface

Dnamo提供两个operation：

• get(key)定位含有key的对象备份位置，并返回一个对象，或者是版本上有冲突的多个对象以及其context。
• put(key, context, object)决定对象应该被放在哪个备份力，并写入硬盘。context包含了系统的metadata。该metadata是对caller不透明的（opaque）。context和object一起被存储从而让系统可以判断put request的有效性。

Dynamo回对key做MD5，以生成一个128位长的identifer，用以决定serving该key的存储节点。

4.2 Partitioning Algorithm

Dynamo的分块scheme依赖于一致哈希(consistent hashing)，这里有一篇关于一致哈希的很清楚的文章。在一致哈希中，会有比实际节点多很多的桶，这些桶排成一个环。每个哈希值会对应一个桶，然后按顺时针方向搜索，直到找到一个实际的节点。通过这种方式就可以防止增删节点要把所有的值都重新算一遍。

最基本的一致哈希算法有如下的几个问题：

• 随机的节点位置可能会导致不均匀的数据和负载分布。
• 原始算法忽略了不同节点之间性能的差异。

为了解决这一问题，dynamo改善了这一算法，每个节点映射到环上的多个位置。具体的fine-tuning Dynamo的分块scheme在第6节进行讨论。

利用上述做法有如下好处：

• 如果一个node down了，增加的负载会相对均匀的分散给多个节点。
• 当一个节点复活了，或者增加了一个新节点，新增的节点会得到和其他的节点大致相同的负载。
• 每个节点对应的位置数量可以基于其capacity，以对应heterogeneity in the physical infrastructure。

4.3 Replication

为了实现高可用性与高耐用性，数据会被分配到多个host上。每个数据被复制在$N$个host上，$N$是per-instance配置的。每个key $k$会用上一节提到的方式被分配给一个coordinator节点。coordinator不仅把数据存在本地，还会存在环上之后的顺时针$N-1$个后续节点上。

负责一个键的节点列表被称为preference list。在4.8节会讲系统是如何让每个节点节点参与决定哪些节点应当作为这个list里的一员。为了预防failure，preference list中有超过N个节点。注意，preference list中的节点都是不同的实际节点。

4.4 Data Versioning

Dynamo实现了最终一致性，以允许更新可以异步传输到所有备份。put会在没有存下来的时候就返回，这会让get无法返回最新的版本。

有一些应用可以允许这种不一致。比如购物车。因为加入购物车的操作不会被忘记或拒绝，所以返回老的版本没有问题。注意加入购物车和删除在dynamo中都表现为put。当用户修改一个老版本的购物车的时候，物品会被加入或删除老的购物车，产生的divergent会之后被reconciled。

Dynamo对待每次修改的结果为一个新的immutable的版本。他允许系统中同时存在多个版本。大多数时候，新版本会并入(subsume)旧版本，系统可以决定authoritative版本(syntactic reconciliation)。不过如上面提到的，出现分支是不可避免的。在这种情况下，系统不能解决冲突，必须由用户来解决（semantic reconciliation）。比如对于购物车，就是采用的合并多个版本，不过这样可能会导致删除过的东西又出现了。

Dynamo采用vector clock以得到不同object之间的因果关系（这里有一篇简单介绍vector clock的文章）。一个vector clock是一个(node, counter)对的数组。每个vector object都和每个object的version有关。可以通过查看两个版本的vector clock来比较其是否有英国关系。如果第一个counters的clock小于等于第二个所有的clock，那么那么第一个可以被忽略。不然，两个版本就认为有冲突。

Dynamo中，通过在put里面加入context，确定了更改的对象的版本。注意，context中存储有之前get命令得到的vector clock。在读操作的时候，如果dynamo可以读到多个不能调和的版本，那么就都返回。对这些版本的一个更新会被认为是对他们进行了合并，将他们合并为一个版本。

vector clock的一个问题是，如果服务器太多，那么会导致其太大了。不过实际情况中一般都不会出现，因为write都是由preference list中的前$N$个节点处理的。不过如果有网络故障，还是会用到前$N$个以外的节点，所以还是有必要进行缩减的。dynamo通过记录一个timestamp，把所有很久没有更新过的(node, counter)对去掉。虽然这样会影响reconciliation的效果，但是实际应用上还挺好。

4.5 Execution of get() and put() operations

这又i而我们考虑failure-free的环境，下一节再考虑如何处理故障。

get()和put()都是是用的Amazon基于HTTP的框架。用户选择节点有两个策略：

• route its request through a generic load balancer that will select a node based on load information
• use a partition-aware client library that routes requests directly to the coordinator nodes

处理读写操作的节点被称为coordinator。一般它是preference list中的第一个。如果是采用的上面提到的第一种方法，request可能会被route到一个随机节点，那么这个节点需要把request传给coordinator。

读写操作会依次访问前N个健康节点。为了维持副本间的一致性，Dynamo采用了一个类似于quorum system的consistency protocol。这个协议有R和W两个值，R是在一个成功的读操作中必须参与的最少的节点数，W是一个写操作必须成功的节点数。让$R+W>N$可以得到一个quorum-like system（其实就是先写了W个，再读R个，根据抽屉原理，一定能读到正确的一个）。在这个模型下，get(或put)的latency取决于R(或W)个节点中最慢的副本。

当收到put请求之后，coordinator会为新版本生成vector clock，并在本地写入这个新版本。之后，它会把这个新版本（以及新的vector clock）发送给$N$个highest-ranked reachable nodes。如果至少有W-q个节点回应了，那说明写入就成功了。

同样，当收到get时，coordinator会向$N$个highest-ranked reachable nodes请求existing version，并等待R个回应，再返回给用户。如果最后得到了多分结果，会把相互因果无关的都返还给用户。

4.6 Handling Failures: Hinted Handoff

如果使用传统的quorum方法可能会导致在服务器故障和network partiion下的不可用，同时可能会在很简单的故障模式下损失耐用性（？？？）。为了缓解这一方法，dynamo采用了"sloppy quorum"：读写都发生在前N个健康节点上，而不是前N个节点上（这样会导致没法用抽屉原理了）。

因为原本的节点故障而被扩充的节点被称为hinted node，他们会把收到的本不属于它们的数据独立存在一个地方，并循环扫描。每当扫描到故障的节点恢复了，就把这些数据传回给他们，如果传输成功，就删除本地的存储。

使用hinted handoff，dynamo保证读写不会因为暂时的故障而失效。需要最高的可用性的应用会把$W$设为1，以保证只要有一个节点把数据参下来了就接受这个写入操作。不过在实际情况下，大多数Amazon的服务都会选一个更高的$W$来达到预期的durability。更详细的关于$N$, $R$, $W$的内容在第6节。

4.7 Handling permanent failures: Replica synchronmization

hinted handoff是用于故障为暂时的的情况。有的时候可能hinted replica在把数据传回给origin replica之前就故障了。为了解决这类问题，dynamo实现了anti-entropy (replica synchronization)协议来让副本之间相互同步。

为了更快速检测副本间的不一致（不相同）并且最小化传输数据，dynamo采用了Merkel tree(哈希树)。哈希树的叶节点是不同键的哈希值，父节点是子节点们的哈希是。所以可以快速检测数据之间的差异。

dynamo的anti-entropy是这样的：每个节点为不同key range维护一个不同的哈希树（键范围通过环上位置确定，每个实际节点对应很多环上位置，也就是好多范围）。这让节点之间可以通过传输根节点，来对比范围内的键对应的数据是否是一样的。如果不一样，就可以逐层传输，从而进行合理的同步操作。这种方法的问题在于在节点的增删的时候，键的范围可能会有所改变。不过，在6.2中，有提到优化过的partitioning scheme。

4.8 Membership and Failure Detection

• 4.8.1 Ring Membership

在Amazon的系统中，节点很少是永远离开系统，所以不应该进行自动的rebalance或者修复。采用的人手工操作增删。节点会把membership change持久化在本地，一个gossip-based protocol会传播membership change，从而使其在节点间最终一致。每个节点会在随机的时间间隔联系另一个节点进行membership change history的一致化。

节点第一次启动的时候会把其对应的位置和范围持久化在硬盘上，不同节点之间的这个mappings store也会在上述过程中进行reconcile。所以partitioning and placement information也是通过这个gossip-based protocol进的。这让节点可以把request forward到其他任何节点去。

• 4.8.2 External Discovery

没看懂....

• 4.8.3 Failre Detection

就是用timeout，并会周期性查看recovery。采用的是decentralized failure detection，也就是上面提到的gossip-style。

4.9 Adding/Removing Storage Nodes

当加入一个新节点X的时候，他会被分配个若干随机的环上位置。因为插入了X，所以别的一些节点的key range可能会右所改变，他们会把对应的数据传给X。删除节点的时候，会进行反向的操作。

by adding a confirmation round between the source and the destination, it is made sure that the destination node does not receive any duplicate transfers for a given key range. （这句没懂）