分布式算法 - Overview

本文总结下常见的分布式算法,主要是分布式中的一致性算法。@pdai

常见的分布式算法

  • 分布式算法 - 一致性Hash算法
    • 一致性Hash算法是个经典算法,Hash环的引入是为解决单调性(Monotonicity)的问题;虚拟节点的引入是为了解决平衡性(Balance)问题
  • 分布式算法 - Paxos算法
    • Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法,使其获得2013年图灵奖。自Paxos问世以来就持续垄断了分布式一致性算法,Paxos这个名词几乎等同于分布式一致性, 很多分布式一致性算法都由Paxos演变而来
  • 分布式算法 - Raft算法
    • Paxos是出了名的难懂,而Raft正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解,所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案
  • 分布式算法 - ZAB算法
    • ZAB 协议全称:Zookeeper Atomic Broadcast(Zookeeper 原子广播协议), 它应该是所有一致性协议中生产环境中应用最多的了。为什么呢?因为他是为 Zookeeper 设计的分布式一致性协议!
  • 分布式算法 - Snowflake算法
    • Snowflake,雪花算法是由Twitter开源的分布式ID生成算法,以划分命名空间的方式将 64-bit位分割成多个部分,每个部分代表不同的含义。这种就是将64位划分为不同的段,每段代表不同的涵义,基本就是时间戳、机器ID和序列数。为什么如此重要?因为它提供了一种ID生成及生成的思路,当然这种方案就是需要考虑时钟回拨的问题以及做一些 buffer的缓冲设计提高性能。