Dynamodb Architecture#
Keywords: AWS, Amazon, DynamoDB
DynamoDB 是业内较早的云原生 NoSQL 数据库产品中比较成功的一款 (比 Google 的 BigTable 晚一点). 它的一些 “无服务器, 无运维”, “自动扩容”, “高可用”, “性能超高”, “支持事务” 等特性深受开发者喜爱. 但这些特性哪个的底层都有非常深的原理和架构设计. 我研读了很多相关的文章, 本文把 DynamoDB 这个产品的底层原理和架构设计进行了一个汇总, 以供我以后参考.
Distributive Model (分布式模型)#
很多分布式系统都有一个 Master Node (主节点) 用于管理所有的 Worker Node (负载节点) 的 Metadata, 流量 Routing 等. 但是这样主节点本身就可能存在单点故障. 并且主节点本身随着集群的变大也需要扩容, 那谁又来管理主节点集群呢, 所以这样的架构并不是很适合扩容. 有中心节点的设计和无中心节点的设计没有说哪个一定好. 有中心节点的设计实现起来简单, 不太需要依赖复杂的一致性协议, 但是依然存在单点故障, 需要为中心节点本身设计一个分布式的容错机制. 而无中心节点的设计增加新节点和扩容会更容易, 但是数据一致性实现上会更复杂.
DynamoDB 采用的是去中心化策略, 核心要点如下:
Decentralized Architect, all nodes are equivalent.
No master node.
Use gossip to boardcast changes to other node.
Scalability Strategy (弹性伸缩策略)#
Dynamodb 的多个物理节点机器会共同服务. Dynamodb 中的 Hash Key 就是用来决定数据会被哪个物理节点进行处理.
Dynamodb 的负载均衡算法用的是 Consistent Hash, 一种特殊的哈希算法, 能在增加和减少节点时降低数据的移动, 被大量分布式系统所采用. 这里就不展开讲了. 简单来说就是把数字 1 ~ 2**32 当成一个首位相连的环. 一个节点就是环上的一个数字. 对 hash key 计算的结果向上搜索 (超过上限则回到 0), 最先遇到的节点的就是负责的节点, 也叫做 coordinator (协调者).
Highly Available (高可用性实现)#
为了达到高可用性, Dynamodb 会将数据在协调者上成功写入后, 在随后 (数字递增后碰到的节点) 的 N-1 个节点上备份. N 一般取 3. 当节点挂掉后, 会有新的节点启动来代替坏掉的节点, 并从其他的节点上拷贝护具. 这其中参与到该数据写入的节点被称作 preference list (偏好列表)
Read and Write (读写的执行)#
Dynamo 集群中的任意节点都能够接受来自客户端的对于任意键的读写请求, 所有的请求都通过 RPC 调用执行, 客户端在选择节点时有两种不同的策略: 一种是通过一个负载均衡器根据负载选择不同的节点, 另一种是通过一个清楚当前集群分片的库直接请求相应的节点.
Dynamo 使用了 Quorum 一致性协议来保证系统中的一致性, 协议中有两个可以配置的值: R 和 W, 其中 R 是成功参与一个读请求的最小节点数, 而 W 是成功参与写请求的最小节点数.
举例. 当 R = 2 时, 所有的读请求 get() 必须等待两个节点成功返回对应键的结果, 才认为当前的请求结束了, 也就是说读请求的时间取决于返回最慢的节点, 对于写请求来说也是完全相同的; 当协调者接收到了来自客户端的写请求 put() 时,它会创建一个新的向量时钟 (vector clock), 然后将新版本的信息存储在本地, 之后向偏好列表 (preference list) 中的前 N - 1 个节点发送消息, 直到其中的 W - 1 个返回这次请求才成功结束, 读请求 get() 与上述请求的唯一区别就是, 如果协调者发现节点中的数据出现了冲突,就会对冲突尝试进行解决并将结果重新写回对应的节点.
注, 向量时钟:
向量时钟 (Vector Clock) 是一种在分布式环境中为各种操作或事件产生偏序值的技术, 它可以检测操作或事件的并行冲突, 用来保持系统的一致性.
在分布式环境中, 第 i 个节点维护某一数据的时钟时, 根据这些值可以知道其他节点或副本的状态, 例如 Vi[0] 是第 i 个节点所了解的第 0 个节点上的
时钟值
, 而 Vi[n] 是第 i 个节点所了解的第 n 个节点上的时钟值
. 这里的时钟值
是一个从 0, 1, 2, … 递增的整数.下面具体描述向量时钟在分布式系统中的运维规则.
规则1:
初始时, 我们将每个节点的值设置为0. 每当有数据更新发生, 该节点所维护的时钟值将增长一定的步数d, d的值通常由系统提前设置好.
该规则表明, 如果操作a在操作b之前完成. 那么a的向量时钟值大于b向量时钟值.
向量时钟根据以下两个规则进行更新.
规则2:
在节点 i 的数据更新之前, 我们对节点 i 所维护的向量 Vi 进行更新:
Vi[i]= Vi[i]+d (d > 0)
该规则表明, 当 Vi[i] 处理事件时, 其所维护的向量时钟对应的自身数据版本的时钟值将进行更新.
规则3:
当节点 i 向节点 j 发送更新消息时, 将一并发送自身所了解的其他节点的向量时钟信息.
节点 j 将根据接收到的向量与自身所了解的向量时钟信息进行比对, 然后进行更新:
Vj[k] = max{Vi[k], Vj[k]}
在合并时, 节点 j 的向量时钟每一维的值取节点 i 与节点 j 向量时钟该维度值的较大者.
两个向量时钟是否存在偏序关系, 通过以下规则进行比较:
对于 n 维向量来说, Vi > Vj, 如果任意 k (0 <= k <= n1) 均有 Vi[k] > Vj[k].
如果 Vi 既不大于 Vj 且 Vj 也不大于 Vi, 这说明在并行操作中发生了冲突, 这时需要采用冲突解决方法进行处理, 比如合并.
如上所示, 向量时钟主要用来解决不同副本更新操作所产生的数据一致性问题, 副本并不保留客户的向量时钟, 但客户有时需要保存所交互数据的向量时钟.
如在单调读一致性模型中, 用户需要保存上次读取到的数据的向量时钟, 下次读取到的数据所维护的向量时钟则要求比上一个向量时钟大 (即比较新的数据).
优势
节点之间不需要同步时钟, 即不需要全局时钟.
不需要在所有节点上存储, 维护一段数据的版本数.
缺点
该方法的主要缺点就是向量时钟值的大小与参与的用户有关, 在分布式系统中参与的用户很多, 随着时间的推移,向量时钟值会增长到很大.
一些系统中为向量时钟记录时间戳, 某一时间根据记录的时间对向量时钟值进行裁剪, 删除最早记录的字段.
向量时钟在实现中有两个主要问题: 如何确定持有向量时钟值的用户, 如何防止向量时钟值随着时间不断增长.
Eventual Consistency (最终一致性)#
Dynamo 与目前的绝大多数分布式系统一样都提供了最终一致性, 最终一致性能够允许我们异步的更新集群中的节点, put() 请求可能会在所有的节点后更新前就返回对应的结果了, 在这时随后的 get() 就可能获取到过期的数据.
如果在系统中出现了节点故障宕机, 那么数据的更新可能在一段时间内都不会到达失效的节点, 这也是在使用 Dynamo 或者使用相似原理的系统时会遇到的问题, Amazon 中的很多应用虽然都能够忍受这种数据层面可能发生的不一致性, 但是有些对业务数据一致性非常高的应用在选择 Dynamo 时就需要好好考虑了.
因为 Dynamo 在工作的过程中不同的节点可能会发生数据不一致的问题, 这种问题肯定是需要解决的, Dynamo 能够确保一旦数据之间发生了冲突不会丢失, 但是可能会有已被删除的数据重新出现的问题.
在多数情况下, Dynamo 中的最新版本的数据都会取代之前的版本, 系统在这时可以通过语法调解 (syntactic reconcile) 数据库中的正确版本. 但是版本也可能会出现分支, 在这时, Dynamo 就会返回所有它无法处理的数据版本, 由客户端在多个版本的数据中选择或者创建 (collapse) 合适的版本返回给 Dynamo, 其实这个过程比较像出现冲突的 git merge 操作, git 没有办法判断当前的哪个版本是合适的, 所以只能由开发者对分支之间的冲突进行处理.
副本同步#
在 Dynamo 运行的过程中, 由于一些情况会造成不同节点中的数据不一致的问题, Dynamo 使用了反信息熵 (anti-entropy) 的策略保证所有的副本存储的信息都是同步的.
为了快速确认多个副本之间的数据的一致性并避免大量的数据传输, Dynamo 使用了 Merkle tree 对不同节点中的数据进行快速验证.
在 Merkle 树中, 所有父节点中的内容都是叶子节点的哈希, 通过这种方式构建的树形结构能够保证整棵树不会被篡改, 任何的改动都能被立刻发现.
Dynamo 中的每一个节点都为其持有的键的范围维护了一颗 Merkle 树, 在验证两份节点中的数据是否相同时, 只需要发送根节点中的哈希值, 如果相同那么说明两棵树的内容全部相同, 否则就会依次对比不同层级节点中的内容, 直到找出不同的副本, 这种做法虽然能够减少数据的传输并能够快速找到副本之间的不同, 但是当有新的节点加入或者旧的节点退出时会导致大量的 Merkle 树重新计算.
Transaction#
2018 年 11 月, DynamoDB 宣布开始支持 Transaction. 我查遍了网络, 没有发现任何公开信息揭示了 DynamoDB transaction 是如何实现的.
Reference#
分布式键值存储 Dynamo 的实现原理: 作者研读了许多 DynamoDB 的论文, 架构设计资料后写的一篇对 DynamoDB 架构进行介绍的博文. 由于这篇博文非常不错, 我自己留了一份这篇博文的备份
分布式键值存储Dynamo的实现原理.mht
(里面的图片都是 base64 编码后的, 并不需要外链图片).Introduction to DynamoDB: 超高性能 NoSQL 数据库 ScyllaDB 公司的一篇介绍 DynamoDB 的博客 (因为 DynamoDB 是它们的竞品之一).