分布式系统大纲指南之无共识Consensus算法

上篇

　　共识Consensus算法实际是在分布式系统复制数据时，追求大多数更新到一致共识状态，共识本身也是一种追求一致性过程，这个过程遭遇各种突变情况时需要协调以保证共识过程进行下去，协调本身带来的成本是很大的，因此，我们首先讨论如何尽可能在所有地方避免共识。

 

CALM conjecture（CALM猜想）

  • 一致性作为逻辑单调性
    • 如果你能证明系统是一个逻辑单调的，那么协调成本为零。
    • 什么是 "单调monotonic"?
  • 单调，通俗地说就是收放自由
    • 从局部信息的推论从来不会因为新信息变成失效。
    • 无论是关系代数和Datalog没有negation将会是单调的
  • Ameloot, et al, 2011: Relational transducers for declarative networking
    • 理论说明在Datalog中可以不在意网络程度情况下节点处理服务器的协调能只以单调计算
    • "免费协调Coordination-free"不意味着没有通讯
  • 使用不严谨的实践词语表达
    • 尝试简短表达你的问题以至于达到你只需要增加新的事实到系统中即可完成问题的表达。
    • 当你根据目前已知的情况计算出一个新的事实，你能保证这个事实永远不会被收回吗？
    • 考虑特殊的“密封事实”，它被标志成一个完整的事实
    • 只进行增长"grow-only"的算法容易作为单调实现
    • 可能遭遇的权衡: 不完整读
  • Bloom 语言
    • 带有流程分析的Unordered编程
    • 能够告诉你哪里需要协调

Gossip（八卦）

  • 消息广播系统
  • 对于集群管理 服务发现 CDN等有用
  • 非常弱的一致性
  • 非常高的可用性
  • 全局广播
    • 发送一个消息到每个其他节点
    • O(nodes)
  • 网状模型
    • 传染病模型
    • 与邻居玩击鼓传花
    • 以最自由路径max-free-path的顺序传播时间
  • 生成树
    • 用树替代网络
    • 一个节点连接到其他另外节点
    • 减少多余信息
    • 降低延时
    • Plumtree

CRDTs

  • 自由次序Order-free的收敛数据类型
    • 比如计算器, 集合, 图
  • 容忍欺骗，延迟，和重新排序
  • 不像顺序一致的系统，没有“单一来源的真相”
  • 但也不同于幼稚的最终一致的系统，从来不会丢失信息
    • 除非你显式丢弃信息
  • 在高可用系统中工作良好，比如：
    • Web/mobile 客户端
    • Dynamo
    • Gossip
  • INRIA: Shapiro, Preguiça, Baquero, Zawirski, 2011: "A comprehensive study of Convergent and Commutative Replicated Data Types"
    • 假设有一个已经组合的数据类型 X 和merge函数m, 那么就有:
      • 可联合Associative: m(x1, m(x2, x3)) = m(m(x1, x2), x3)
      • 可交换Commutative: m(x1, x2) = m(x2, x1)
      • 幂等Idempotent: m(x1, x1) = m(x1)
  • 易于构建 易于reason about. 能克服各种头疼问题.
    • 通讯失败？再试验一次，它会聚集收敛!
    • 消息到达乱了次序？没有关系
    • 如何同步两个复制？只是融合merge即可！
  • 缺点
    • 有些算法需要秩序，不能用CRDTs
    • 读取可能是任何过期的脏数据
    • 较高的空间成本

HATs

  • Bailis, Davidson, Fekete, et al, 2013: "Highly Available Transactions, Virtues and Limitations"
    • 任何副本都会保证响应
    • 低延时 (比串行化协议速度快1-3个数量级)
    • 读递交Read Committed
    • 单调原子视图Monotonic Atomic View
    • 对于 可交换commutative/单调monotonic的系统表现优秀
    • 多条目更新的外键约束
    • 有限的唯一性约束
    • 对于给定任意有限时滞，可以保证收敛（“最终一致性”）
    • 是地理分布系统的优秀候选方案
    • 最适合解决需要强事务机制的系统
    • 也可以参考: COPS, Swift, Eiger, Calvin等

 

　　如果事件只是不断增加事实（事件数据），不会撤回它们，就只需要少部分协调构建，我们就能使用gossip系统来广播消息到其他处理服务器，CRDTs适合融合merge来自结对节点服务器的更新，而HATs 适合弱隔离事务.

下篇

分布式CRDT模型