1. 介绍

最近看到一些文章不错,这里推荐下。下面每个标题都对应一片文章,我都对其内容做了简单几句话的总结。大家可以点击查看原文。

2. 分布式系统理论基础 - 选举、多数派和租约

原文地址: 分布式系统理论基础 - 选举、多数派和租约

该文主要理解以下的选举算法:

  1. bully选举算法:最基本的选举算法,序号最大的作为leader。缺点是网络分区的时候可能导致有多个leader。
  2. 多数派方法:弥补bully选举算法的缺点,网络分化的时候只有具备多数派节点的部分才可能选出leader,这避免了多leader的产生。
  3. 租约:就是判断leader是否挂了的时候,设定一个有效时长(租期)。leader宕机的时候,只有租约到期后才发起重新选举。

3. 分布式系统理论基础 - 一致性、2PC和3PC

原文地址:分布式系统理论基础 - 一致性、2PC和3PC

该文章理解以下内容:

  1. 分布式系统一致性的含义:全认同、值合法、可结束
  2. 一致性的属性:一致性还具备两个属性,一个是强一致(safety),它要求所有节点状态一致、共进退;一个是可用(liveness),它要求分布式系统24*7无间断对外服务。
  3. FLP定理(FLP impossibility):在一个收窄的模型中(异步环境并只存在节点宕机),不能同时满足 safety 和 liveness。
  4. 两种系统模型:两种系统模型,假设了系统所处的环境和会出现的问题。模型1:异步环境(asynchronous)下,节点宕机(fail-stop);模型2:异步环境(asynchronous)下,节点宕机恢复(fail-recover)、网络分化(network partition)
  5. 2PC:两阶段提交。2PC可以在异步网络+节点宕机恢复(主要是需要协调者宕机后能恢复)的模型下实现一致性。
  6. 3PC:改进2PC,使得决议参与者之间能互相之间不依赖,并且在协调者宕机的时候,能迅速回滚到决议前的状态。它防止participant宕机后整个系统进入阻塞态,增强了系统的可用性。主要原理就是引入了准备阶段。协调者宕机了,处于准备阶段的参与者可以回滚。

4. 分布式系统理论基础 - 时间、时钟和事件顺序

原文地址:分布式系统理论基础 - 时间、时钟和事件顺序

这个我自己也专门写了个文章总结了下,可以参考:时钟与分布式系统

5. 分布式系统理论基础 - CAP

原文地址:分布式系统理论基础 - CAP

虽然讲CAP的文章很多,不过该作者的理解还是感觉蛮到位的。CAP理论注意一下几点:

  1. 一般是CP和AP的抉择。C和A的选择更加侧重哪个,需要根据实际情况来看。
  2. P的理解:P指的是网络分区的容忍。网络丢包、节点宕机都有可能导致网络分区。

6. 分布式系统理论进阶 - Paxos

原文地址:分布式系统理论进阶 - Paxos

6.1 Basic Paxos

Basic Paxos算法用于确定并只确定一个值。

为了方便理解Basic Paxos算法,我们一步步推演:

第一步推演: 假设节点不会宕机、消息不会丢失
此时Basic Paxos的算法步骤为:

  1. 一个acceptor接受它收到的第一项提议
  2. acceptor可以接受(accept)不止一项提议,当多数(quorum) acceptor接受一项提议时该提议被确定(chosen)
  3. 如果一项值为v的提议被确定,那么acceptor后续只接受值为v的提议

第二步推演:假设存在节点宕机恢复、消息丢失
和第一步的区别就是: 宕机恢复后的节点会接受他收到的第一项提议。但是该提议的值可能和其他acceptor确定的值不同,这样就矛盾了。

此时Basic Paxos的算法步骤在第一步推演的基础上加上以下约束,来避免上面所说的矛盾问题。

对于提议(n,v),acceptor的多数派S中,如果存在acceptor最近一次(即ID值最大)接受的提议的值为v',那么要求v = v';否则v可为任意值

未完待续。。。