Dynamodb Architect

Reference:

Distributive Model (分布式模型)

  • Decentralized Architect, all nodes are equavilent

  • 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 没有办法判断当前的哪个版本是合适的, 所以只能由开发者对分支之间的冲突进行处理.

副本同步

TODO