关于nosql:分布式存储论文研读三DynamoDB

这篇博客，分享另一个云端巨头：Amazon 的 DynamoDB 数据库的实现论文，“Dynamo: Amazon’s Highly Available Key-value Store”。

Background

System Assumptions and Requirements

与 GFS，Bigtable 等一样，DynamoDB 有一些实用的场景。文章做出以下假如，并依据这些假如进行零碎的设计，会更有针对性：

• Query Model：读写操作简略，且均基于主键。没有跨多行的操作，也不须要关系语义。存储对象通常在 1MB 以下。
• ACID Properties：Dynamo 提供的一致性较弱，不保障隔离性（isolation），且只执行单主键（单行）的更新。
• Efficiency：零碎须要满足高效率，须要在性能、老本效益、可用性和 Durability 保障之间进行衡量。
• 数据库用于外部零碎，不会被针对性攻打，不须要进行鉴权受权。
• 数据库的指标是扩大到上百个数据节点。

Service Level Agreements (SLA)

在做数据库的性能评估时，亚马逊更偏向于应用 99.9% 的散布值来进行掂量，代替罕用的平均值、中位数、方差冀望等等。这和咱们在做一些性能测试时很相像，TP999 更能反馈零碎的个别状况，笼罩近乎所有人，而非大部分人的体验。

Design Considerations

CAP 实践阐明，在区间通信失败或一些网络失败时，数据一致性和高可用性无奈同时保障。DynamoDB 冀望保障数据的最终一致性，就义了肯定的一致性等级来保护服务高可用。此时就须要对一些批改抵触进行解决。很多传统数据库通常在写时进行抵触解决，保障读的逻辑简洁，这会导致一些无奈写到所有分片的写操作失败。而 DynamoDB 心愿能有一个始终可写的数据存储，不心愿驳回用户的写申请。那么此时就会把一些抵触解决迁徙到读的过程中去。

另一个设计理念，是确立由谁来解决写抵触。DynamoDB 设计为能够由服务调用方来应用不同的规定解决批改抵触，也能够将这一职责下放到数据库，由数据库执行一些简略的策略，如“last write wins”。

Dynamo 还应该被设计为能够继续扩大，即在原有集群上能程度扩大一个节点，同时不对原零碎产生太多的影响。

Dynamo 的所有节点职责应该是统一的，也就是没有“主节点”的概念，简化零碎的运维工作。这称为“Symmetry”

比 Symmentry 更进一步，是 Decentralization，去中心化，应用点对点而非核心管制的模式。

最初介绍的一个设计理念是“Heterogeneity”，异质性，零碎该当有利用根底硬件异质性的能力，如在机器间依据其理论能力进行平衡负载。

异质性这部分更多的是我集体的了解，还须要在后续的浏览中明确是否统一。

Related Work

第一代 P2P 零碎，称为非结构化 P2P 网络，如 Freenet，Gnutella，罕用于文件分享，会做分布式存储，但每个申请会尽可能申请所有节点来获取数据。第二代 P2P 零碎，称为结构化网络，能够进行正当正确地路由，快速访问有所须要数据的节点。代表如 Pastry 和 Chord。在此基础上，搭建了不少数据存储系统，如 Oceanstore 和 PAST。

除了 P2P 零碎，也有很多分布式文件存储系统，例如 Bayou，Coda，Ficus，Farsite system 以及之前研读过的 GFS，Bigtable，还有 FAB，Antiquity 等等。

与所有列举的零碎不一样中央：

• Dynamo 强调始终可写；
• 零碎被预期部署在一个所有节点可信赖的环境中；
• 应用 Dynamo 的利用不须要反对结构性的命名空间或是简单的关系语义，只须要简略的 key-value；
• Dynamo 针对时延敏感利用，须要保障 TP999 在几百毫秒的级别。

System Architecture

Dynamo 针对要害性能所采纳的策略见下表：

System Interface

零碎提供简略的 put 和 get 接口来操作数据。get 能够获取到一个数据，也能够是一组抵触的数据，交由利用来解决抵触。put 则须要加上 context 信息，蕴含了一些版本信息等。零碎通过对 key 进行 128 位的 MD5 hash 来决定存储数据的服务器。

Partitioning Algorithm

分区算法要求可能动静地将数据均衡散布到各个节点。Dynamo 次要通过对 key 进行 hash，值域失去一个环，而后散布到各个节点中去。每个数据会放在 hash 失去对应的节点，以及其后一个节点上。

这是最根本的哈希一致性算法，其问题是随机调配会导致数据和地位在环上不平均，同时也疏忽了节点性能的异质性。为此 Dynamo 做了 hash 算法的变种，每个实体节点会调配多个环中的虚构节点。这样有几点益处：

• 如果一个实在节点不可用，其负载会被残余节点平分（设想每个数据有两个正本，实在节点 1 可能存储的是虚构 1、4、7 节点，挂掉时会拜访对应的 2、5、8 节点散布在三个不同的实在节点上）。
• 当一个节点复原可用，或退出到零碎中时，各个其余可用节点能够分担数据迁徙的压力。
• 一个节点具体负责的虚构节点数量能够依据其容量，性能动静调整，能够感触到硬件节点的异质性。

Replication

为了保障数据的高可用性，每条数据都会保留 N 个正本。当一个数据被调配到一个节点上时，这个节点还会负责将这份数据放到它的前 N - 1 个虚构节点上。

负责保留同一份数据的节点列表被称为一个“preference list”，为了保障节点故障时数据仍可用，preference list 数量通常会多于 N。另外，因为应用了虚构节点的概念，几个虚构节点可能处在同一个物理节点上，为了解决这一问题，preference list 会在环中跳跃式调配，保障整个列表蕴含不同的物理节点。

此处的跳跃调配形式也不是很分明。有待后续补充。

Data Versioning

Dynamo 保障数据的最终一致性，也就意味着对同一份数据的多个正本流传批改能够是异步的，通常不须要期待所有分片都写完即可向用户返回后果。造成的问题之前也提到过，在一些特定的谬误场景，如网络分区稳定或服务器宕机等状况下，改变可能无奈传递到所有分片。

在亚马逊平台中，有不少利用其实是能够容忍这种谬误的，例如增加购物车场景，当用户增加时，申请不会被回绝，如果此时最新版本的购物车数据不可达，那么就将数据保留在老一些版本的数据中，这两份不同版本的数据会在获取时进行交融。当然，此时会呈现的另一个问题是，交融过程中被删除的 item 可能从新呈现在列表中。这个过程要求设计的应用程序能感知并解决批改抵触。

Dynamo 应用向量钟（vector clocks）来确定不同版本之间的先后关系。那么此时各个正本中不仅保留了各自的数据，还会保留该数据的多个版本。保留的版本数量无限（如 10 个），当感知到其余分片上的批改时，判断本人分片上的版本全副低于该批改的最新版本，那么本人分片的内容就会被笼罩。否则，则仍会保留多个版本，待读取时进行抵触解决。

Execution of get() and put() Operations

get 和 put 操作有两种形式来找到对应须要操作的节点：

• 将申请发送到一个通用的负载均衡器，由它来依据内容进行路由。这种办法利用不须要本人保护连贯 Dynamo 的代码。
• 应用一个能够感知分区的 client 库来将本人的申请路由到对应的节点。这种办法提早更低，因为少了一层转发（见后续形容）。

通常承受 get 和 put 操作的是 preference list 中的第一个节点（如果是通过负载平衡的申请，可能会路由到 list 中任意一个节点，此时申请会再被转发到第一个节点）。写和读操作波及 N 个节点，和很多仲裁零碎（quorum system）一样，须要保障 R + W > N。R 即读申请时须要收到的分片响应数量，相应的，W 即写申请时须要收到的分片回复数量（蕴含自身解决申请的节点本地读写）。在这种模型中，申请的提早取决于最慢的 R 个读或 W 个写节点。也因而，R 和 W 能够获得尽可能小。

Handling Failures: Hinted Handoff

Dynamo 实际上不须要零碎保障所有的 quorum 节点可用。它应用一种“sloppy quorum”的策略。简略来说，一份数据贮存在 ABC 三个节点中。当 A 节点宕机或不可达时，就长期贮存在 D 节点中。D 节点独自有一块区域存储这些本不属于本人的数据，并进行定时轮询。如果发现 A 节点可用，就将数据传输回去并删掉本地的正本。始终保持三个节点的数据正本。（留神此处抉择 D 不是任意的，应该是在环中最近一个衰弱节点，这样能力保障故障时读写数据能找到该节点）。

与此同时，Amazon 为了保障 Dynamo 的高可用性，还会将数据存储节点散布在多个数据中心中，数据中心间通过高速通道连贯，防止自然灾害等导致一个数据中心同时宕机的危险。当然这样的部署对于小型机构来说是根本不可能的，仍须要依赖于 Amazon 平台的基础设施。

Handling Permanet Failures: Replica Synchronization

Dynamo 应用 Merkle tree 来进行节点同步，以尽量减少同步时须要传输的数据。Merkle tree 是一棵 hash 树，简略来说，每个节点就是一个独自 key 的 value 的 hash 值，而父节点又是其子节点的 hash 值。那么在比拟两个节点是否不统一时，只须要比拟最顶层节点，而后依据比拟后果顺次向下比拟，直到同步所有的不统一叶子节点。而不须要将所有数据拿进去进行比拟。每个物理节点会对其上每一个虚构节点保护一棵独自的 Merkle tree。

这个计划的毛病是当有节点退出或来到时，须要从新计算整棵树的 hash 值。该问题后续有解决方案。

依然要弄清楚，Hinted Handoff 和 Replica Synchronization 两者的实用场景有什么不同及分割：相较而言，Hinted Handoff 实用于节点长期不可用的场景，节点还是会回到集群中来，这一过程简直是通明的。而 Replica Synchronization 则实用于节点永恒不可用，须要进行数据同步。

Membership and Failure Detection

• Ring Membership：
  管理员能够通过控制台或浏览器去连贯一个 Dynamo 节点，并收回增加或删除一个节点的指令。解决该指令的节点会将指令写入长久存储的节点改变历史中，一个基于 Gossip 的协定将改变流传到各个节点，并最终维持各个节点上信息统一：每个节点每秒都会抉择一个随机节点，这两个节点之间协商永恒存储的节点改变历史。通过协商，每个节点都能更新本人须要负责存储的区域数据。
• External Discovery：
  在之前介绍的动静增加删除的节点过程中，可能呈现逻辑分区，如 A，B 同时增加进环，它们都认为本人是环中的一员，但还不能立刻感知到对方。此时会有一个由内部机制（动态文件定义，或者内部的配置服务）决定的种子节点，所有其余节点会和种子节点交换本人的 membership，使得逻辑分区根本不可能呈现。
• Failure Detection：
  当节点 A 发现节点 B 不响应其申请时，就会认为节点 B 生效了，从而将申请发送到可选的其余节点中去，施行 Hinted Handoff。同时 A 节点会一直轮询 B，来查看其是否曾经复原。而去中心化的节点生效探查协定应用了简略的相似 gossip 的协定。这实用于节点的长期生效。而对于明确的节点减少和删除，则不在此协商范畴内。

Adding/Removing Storage Nodes

当一个节点被退出到环中时，它就会被随机调配到一系列的 token，示意它所承当的存储的 key。此时有一批节点就不再须要贮存这些 key 的信息，从而将这些数据传输到新增节点上来。而当节点退出零碎时，会施行一个逆过程，将退出节点上的数据从新传输到新计算负责的节点下来。

Dyanmo 的实际操作教训表明，这种办法将负载平均地平摊到各个节点，从而升高提早，提高效率。另外，通过在起始和指标节点之间退出一个确认回路，能够保障不会收到反复的数据传输。

Implementation

Dynamo 中，每个存储节点都有三个要害的软件组成部分：

• request coordination：应用状态机解决节点接管到的申请（存储 N 份数据节点的第一个节点进行申请解决），包含将申请发往数据存储的各个节点并收集响应等。零碎还会对写申请做一些优化，例如通常写申请紧跟在读申请后，那么响应写申请的节点就协调为前一次读申请响应最快的节点。
• membership and failure detection
• local persistence engine：应用插件的形式，容许利用依据本人的数据量来抉择本地长久化引擎，包含 BDB Transactional Data Store，BDB Java Edition，MySQL，内存 buffer。

Experiences & Lessons Learned

不同的利用会应用不同配置的 Dynamo，最次要的差异在版本协调逻辑，和读写仲裁节点数量。有以下几个次要模式：

• Business logic specific reconciliation：基于特定业务逻辑的版本协调逻辑，例如之前举例的购物车利用，须要依照业务来 merge 或应用其它解决形式解决不同版本的数据后果。
• Timestamp based reconciliation：与前一点的次要区别在于版本协调逻辑，应用简略的工夫戳比拟，“last write wins”，后批改的失效。例如用户的 session 信息。
• High performance read engine：一些特定场景下，读多写很少，为提高效率，批改 R =1，W=N。例如权限治理缓存等。

Dynamo 的 N，R，W 能够随便调节，通常 N 值设置为 3。不少利用的 (N,R,W) 值设置为(3,2,2)。

Balancing Performance and Durability

Dynamo 的 TP999 为 300ms。因为硬件零碎的 I / O 性能个别，以及服务性能取决于最差的那台机器，提供统一高性能的服务不是一件简略的工作。

在一次为期 30 天（2006 年 12 月）的试验中，服务提早呈现了很显著的每日稳定，每天白天申请多，提早高，夜间申请少，提早低。同时写申请的延时要高于读申请。TP999 在 200ms 左右。这一后果曾经合乎预期，但一些系统对性能要求更高，那么就会就义一些持久性：在节点中开拓一个内存 buffer，所有写申请操作 buffer，并通过一个线程定时写到磁盘。读申请也先查看 buffer 中有没有，没有在读存储引擎。这种办法，即便内存空间很小（包容一千个对象），也能够胜利地将最大提早从 200ms 升高到 100ms 以下。但毛病也不言而喻：一旦机器宕机，就会失落掉 buffer 中未解决的写申请。那此时的进一步优化就是在多个写的分片中，指定一个进行长久化的写，其它分片写到 buffer，保证数据不失落。同时因为写申请时只须要 W 个节点响应，W<N 时也能享受 buffer 带来的性能晋升。

Ensuring Uniform Load Distribution

Dynamo 的负载平衡策略是在一直演进的，分为三个阶段：

1. T random tokens per node and partition by node value：也就是之前介绍的策略。每个节点 T 个随机 token。token 是 hash 空间中的随机值，两个间断 token 定义了一个 range，因为 token 是随机选取的，它们所代表的 range 大小可能不同。这个策略的基本问题是数据分片和分片搁置的地位纠缠在了一起，具体表现为几个问题：

• 当一个节点退出时，它须要从其它节点偷来它本人的 key range。此时老节点就须要扫描本人的存储，取出适合的数据进行传递。这是比价影响性能的操作，为了保障用户体验，启动一个节点的工夫就会变得很漫长（忙碌时须要一天）
• 当节点退出 / 来到时，其它节点的 key range 就会扭转，Merkle tree 须要从新计算。
• 这种策略下，key range 的随机性导致无奈轻松地对整个 key space 进行 snapshot。

2. T random tokens per node and equal sized partitions：这个策略将 hash 空间分为 Q 个大小相等的局部，每个节点被调配到 T 个随机的 token。设置 Q >> N 且 Q >> S*T（S 是零碎节点数量）。token 只是用来创立 value 和 hash 空间的映射函数，不决定宰割。一个分片被搁置在一致性哈希环中遇到的前 N 个不同节点上。这一策略的益处是：

• 解耦了数据分片和分片搁置的地位。
• 容许在运行时动静扭转搁置地位。

3. Q/S tokens per node, equal-sized partitions：第三种策略同样解耦了分片和搁置的地位。每个节点被调配到 Q / S 个 token。当节点退出时，它的 token 被随机散布到残余的节点。节点退出时，就从其它节点偷来本人的 token。它有以下益处：

• Faster bootstrapping/recovery：当 partition range 修复了之后，它们会被存在独立的文件中，一个分片的复原只须要将对应的文件传输即可，防止了去定位特定的 item。
• Ease of archival：此时分片文件能够独立的进行归档。

Divergent Versions: When and How Many?

判断零碎一致性谬误的一个无效度量形式是察看利用获取到的，版本有一致的数据数量。版本一致通常有两种场景：一是零碎中节点宕机，二是零碎解决大规模的并发写。

在察看购物车利用的一次 24h 试验中，99.94% 的申请只有 1 个 version，0.00057% 有 2 个 version，0.00047% 有 3 个，0.00009% 有 4 个。（试验数据有些对不上 100%？）。察看到的次要起因是并发写入，通常触发者是一些主动机器人而非人。

Client-driven or Server-driven Coordination

之前提到 Dynamo 的数据节点有一个 coordination component 通过状态机来解决申请。另一种可行的策略是将状态机移到 Client 端。client 定期（经验值是 10s）向 Dynamo 获取节点的 membership 状态，用这个来间接拜访特定的节点。因为数据根本均匀地调配在各个节点，也不须要做额定的负载平衡。试验中 TP999 的优化成果很显著。次要优化点是缩小了不必要的负载平衡和随机调配节点后，节点再向数据对应节点发送申请的一跳。

Balancing Background vs. Foreground Tasks

一些后盾操作的执行须要保障前台 put/get 申请的用户体验不受影响。因而 Dynamo 将所有的后盾操作对立集成到一个管制机制中。该 controller 会去收集前台操作的一些性能指标，以此判断此时是否能将工夫片调配给后盾申请。

Conclusions

读这篇文章我最大的播种是两点：

1. 技术上对于一致性哈希的理解，最突出的就是 Dynamo 数据分片和数据搁置地位的策略演进。
2. 对于理念上的更新：Dynamo 将它的指标设置为不回绝任何写申请，而在读申请时解决抵触，这是一种反向的思维，区别于咱们平时心愿数据写时尽可能统一，可能进行疾速读取。这一点值得学习。

Six Questions

这个技术呈现的背景、初衷和要达到什么样的指标或是要解决什么样的问题。

依据论文，DynamoDB 须要解决的最间接的挑战是 Amazon 宏大电商零碎的“always-on”体验。Amazon 零碎的底层是上万台服务器和海量的数据，其中硬件故障不可避免且时时产生。DynamoDB 须要为用户营造出一个“永远在服务”的状态。

这个技术的劣势和劣势别离是什么，或者说，这个技术的 trade-off 是什么。

既然说到“always on”，那么在分布式系统的 CAP 原理中，DynamoDB 无疑更重视的是 AP 模型。当然也就不足了一致性 C，须要通过一系列软件操作解决抵触，或者保障最终一致性。这是 DynamoDB 最次要的 trade off。而在解决抵触时，DynamoDB 将抵触解决放在了读一端，而非写一端。舍弃了更简洁的代码逻辑，减少了用户体验。

同时 DynamoDB 也是一个典型的 NoSQL 数据库，应用主键响应大部分需要。

此外 DynamoDB 的响应速度也做了十分多的优化，因为其出身是响应宏大且即时要求高的电商零碎。为此它的老本始终是咱们不应用它的一大妨碍。

这个技术应用的场景。

最典型的应用场景，当然也就是 Amazon 的次要场景：电商。其特点是：规模大，响应工夫要求高，可用性要求高，但同时大部分的查问只须要基于 Key 就能够，没有简单的关系查问。

技术的组成部分和关键点。

Dynamo 实际上是一系列组成集群的，对等的存储节点。存储节点的要害组成部分有三个：

1. request coodination：协调申请。
2. membership and failure detection：维持集群，处理错误。
3. local persistence engine：应用插件来依据需要抉择本地长久化引擎。

技术的底层原理和要害实现。

System Architecture 一章的表中曾经列举了各关键技术：

1. 分区：一致性哈希（Consistent Hashing）
2. 高可用的写：向量钟
3. 解决长期谬误：Sloppy Quorum 以及 hinted handoff。
4. 谬误复原：Merkle trees
5. 谬误查看：基于 Gossip 的协定

已有的实现和它之间的比照。

可比拟的零碎包含 P2P 零碎：Freenet，Gnutella 等，第二代 P2P 网络：Pastry，Chord，另外还有分布式文件存储系统，包含 Bayou，Coda，Ficus，Farsite system，GFS，Bigtable，FAB，Antiquity 等。

DynamoDB 与它们最次要的一些区别包含：

1. 强调始终可写
2. 外部零碎，不强调安全性
3. 应用 key-value
4. 针对时延敏感申请，TP999 在 300-500ms。