分布式理论基础

CAP 定理

  • 指的是在一个分布式系统中，Consistency (一致性)、Availability (可用性)、Partition tolerance (分区容错性)这三个基本需求，最多只能同时满足其中的2个。
  • Consistency：数据在多个副本之间能够保持一致的特性。
  • Availability：指系统提供的服务必须一直处于可用的状态，每次请求都能获取到非错的响应，但不保证获取的是最新数据。
  • Partition tolerance：指分布式系统在遇到任何网络分区故障的时候，仍能对外提供满足一致性和可用性的服务。
  • 网络分区故障：不同的节点分布在不同的子网络中，由于一些网络故障，子网络之间不能正常通信，只有子网络内部可以正常通信，导致整个系统的环境被切分成了若干个孤立的区域，产生一些局部小集群。在极端情况下，这些局部小集群会独立完成原本需要整个分布式系统才能完成的功能，这就对分布式一致性提出类非常大的挑战。
  • 为什么不能同时满足？
    • Consistency 是保证从每个节点读到的数据都是一致的，Availability是保证响应时间短，Partition tolerance 是保证容错性，也就是节点足够多。
    • 如果要满足 C 和 A，就是要在极短的响应时间里实现数据同步，倘若节点过多，同步时间一定会很久，所以不能有太多节点，也就不能满足 P。
    • 如果要满足 C 和 P，就是要在大量节点之间实现数据同步，同步时间一定会很久，需要等待同步完成再做出响应，所以不能满足 A。
    • 如果要满足 A 和 P，就是要在有大量节点的情况下支持即时响应，必然没有足够时间完成数据同步，所以不能满足 C。
  • 取舍：
    • CA：放弃分区容错性，如传统的单机数据库
    • AP：放弃强一致性，支持弱一致性，如当前很多NoSQL
    • CP：放弃可用性，基本不会选择，因为响应时间太长根本没法用
    • 对于分布式系统而言，网络问题是一定会出现且必须要解决的，所以一定会满足分区容错性，所以一般是在C和A之间寻求平衡(并不是二选一，而是一强一弱)。

BASE理论

  • Basically Available(基本可用)，Soft State(软状态)和Eventually Consistent(最终一致性)的缩写，是对CAP中一致性和可用性权衡的结果。
  • BASE 和 ACID 都是对 CAP 原则的一种具体实现。ACID 适用于传统的单机数据库，牺牲了高可用性来满足强一致性，而 BASE 适用于分布式 NoSQL，采用了弱一致性来满足更高的可用性和分区容错性。
  • Basically Available：响应时间略长，网站功能降级等
  • Soft State：在不影响系统整体可用性的基础上，允许多个不同节点的数据副本存在数据延时。
  • Eventually Consistent：软状态必须有个时间期限，在期限过后应当保证所有副本的数据一致，从而达到数据的最终一致性。这个时间期限取决于网络延时、系统负载、数据复制方案设计等因素。

分布式锁

  • 单机场景下可以使用JVM内置的锁来实现进程同步，但在分布式场景下，需要控制多个节点之间的同步，只能使用分布式锁。
  • 分布式锁应该满足的特性：
    • 高可用的获取锁与释放锁
    • 高性能的获取锁与释放锁
    • 具备可重入特性
    • 具备锁失效机制，防止死锁
    • 具备非阻塞锁特性，没有获取到锁将直接返回获取锁失败
  • 几种具体实现：
    • 数据库唯一索引：当想要获得锁时，就向表中插入一条记录，释放锁时就删除这条记录，唯一索引可以保证该记录只被插入一次。缺点是锁没有过期时间，容易导致死锁。
    • Redis 的 SETNX 指令：和数据库唯一索引类似，区别在于插入的是键值对，而且能够设置键值对的过期时间，可以避免死锁。
    • Redis 的 RedLock 算法：尝试从 N 个相互独立 Redis 实例获取锁，如果一个实例不可用，应该尽快尝试下一个。
    • Zookeeper 的有序节点

负载均衡

  • 算法：
    • 轮询法(Round Robin)：将请求按顺序轮流地分配到后端服务器上，均衡地对待后端的每一台服务器，不关心服务器实际的连接数和当前的系统负载。适合每个服务器性能差不多的场景，如果有性能差异，那么性能差的服务器压力会比较大。
    • 随机法(Random)：把请求随机发送到服务器上，由概率统计可以得知，随着客户端调用服务端的次数增多，其实际效果越来越接近于轮询的结果。
    • 源地址哈希法(IP Hash)：对客户端的IP地址计算哈希值，再用哈希值对服务器数量取模，得到的就是要访问的服务器的序号。采用源地址哈希法进行负载均衡，同一IP的客户端每次都会映射到同一台服务器。
    • 加权轮询法(Weighted Round Robbin)：给配置高、负载低的机器配置更高的权重，让其处理更多请求。给配置低、负载高的机器更低的权重，降低其系统负载。
    • 加权随机法(Weighted Round Robbin)：加权轮询法的无序版本。
    • 最小连接数法(least Connections)：根据后端服务器当前的连接情况，动态地选取其中积压连接数最少的一台服务器来处理当前请求，尽可能地提高后端服务的利用效率.
  • 实现方式：
    • 重定向：将请求全部发送到前置机，前置机通过算法确定目标服务器，然后把请求重定向到目标服务器，最后通过前置机把响应返回给客户端。缺点是每个请求实际都要请求两次，同时前置机压力很大。
    • 反向代理：在前置机使用反向代理的方式将请求分发到服务器，无需再请求一次。实现方式通常有两种，一种是用交换机实现，一种是用nginx这一类软件实现。虽然提高了请求的响应效率，但前置机压力依然很大。
    • 数据链路返回：给应用服务器设置虚拟IP，然后通过修改mac地址的方式将请求分发出去，服务器收到请求后可以直接响应给客户端，而不需要经过前置机。

分布式下的数据一致性

  • 一致性的定义：
    • 全认同(agreement): 所有N个节点都认同一个结果
    • 值合法(validity): 该结果必须由N个节点中的节点提出
    • 可结束(termination): 决议过程在一定时间内结束，不会无休止地进行下去
  • 面临的问题：
    • 消息传递异步无序(asynchronous): 存在消息延时、丢失等问题
    • 节点宕机(fail-stop): 节点持续宕机，不会恢复
    • 节点宕机恢复(fail-recover): 节点宕机一段时间后恢复
    • 网络分化(network partition): N个节点因为网络问题隔离成多个部分
    • 拜占庭将军问题(byzantine failure): 由于硬件错误、网络问题或恶意攻击，部分节点作出错误的响应干扰决议。
  • 同步通信：各个节点的时钟误差存在上限，并且消息传递必须在一定时间内完成，否则认为失败，同时各个节点完成处理消息的时间是一定的。因此同步系统中可以很容易地判断消息是否丢失。同步通信中的一致性被证明是可以达到的
  • 异步通信：各个节点可能存在较大的时钟差异，消息传输时间可能是任意长的，各节点对消息处理的时间也可能是任意长的。因此无法判断某个消息迟迟没有被响应是哪里出了问题(节点故障还是传输故障)。
  • FLP不可能性(FLP impossibility)
    • 概念：用图论的方法证明了，在网络可靠但允许节点失效的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。
    • 例子：三个人在不同房间进行投票，彼此可以通过电话进行沟通，但经常有人会时不时睡着。在某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。此时 A 和 B 将永远无法在有限时间内获知最终的结果，也无法确定究竟是 C 没有应答还是应答的时间过长。如果可以重新投票，则类似情形可以在每次取得结果前发生，这将导致共识过程永远无法完成。而如果是同步通信，A 和 B 就可以及时确定 C 宕机了，就能排除 C 的干扰，仅在两人之间达成共识。
    • FLP 证明了不存在完美的共识机制，而 CAP 则证明了在付出一些代价的情况下可以达到多好的一致性。二者是一个意思，允许有节点宕机就说明要满足分区容错性，FLP其实就是证明了在满足分区容错性时不能同时满足强一致性和高可用性。
    • 2PC 和 3PC 协议就是为了平衡一致性和可用性。
  • 2PC
    • tow phase commit，即两阶段提交。
    • 原理：
      • 第一阶段，协调者发起一个提议，分别问询各参与者是否接受，参与者收到后回复协调者。
      • 第二阶段，协调者根据参与者的反馈，提交或中止事务，如果参与者全部同意则提交，只要有一个参与者不同意就中止。
    • 宕机情况分析：
      • 没有节点宕机时，2PC 协议显然能够实现全认同、值合法、可结束的一致性。
      • 只有协调者宕机，可以引入协调者备份，由协调者备份取代宕机的协调者，通过询问所有参与者的执行情况来确认当前的操作，不会导致数据不一致。
      • 只有参与者宕机，可以引入超时机制，宕机的参与者能在第一阶段被检测出来，宕机了可以再恢复，通过向协调者询问执行记录，可以保持数据的一致性。
      • 协调者和参与者在第一阶段都宕机，还没有执行 commit，所以挂了就挂了吧，新的协调者询问各个参与者的情况，再重新决定是否commit，不会导致数据不一致。
      • 协调者和参与者在第二阶段都宕机。大部分参与者收到并执行了commit，宕机的节点没有收到commit命令，所以会导致短期的数据不一致，通过和协调者的通信，可以想办法把数据搞成一致的。
    • 缺陷：
      • 全流程的同步阻塞：不管是第一阶段还是第二阶段，所有参与节点都是事务阻塞型。
      • 单点故障：一旦协调者发生故障，参与者会一直阻塞下去，所有参与者必须等待协调者备份重新上线后才能继续工作。
      • 数据不一致：在第二阶段中，只有一部分参与者收到了commit命令，未接到commit命令的参与者无法执行事务提交。
      • 事务状态不确定：协调者在发出commit消息之后宕机，而接收到这条消息的参与者同时也宕机了。那么即使产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否已经被提交。

  • 3PC
    • 没太看明白，留坑~
    • 分为CanCommit、PreCommit、DoCommit三个阶段。
    • 第一阶段和2PC的第一阶段相同，询问所有参与者是否可以执行事务操作。
    • 第二阶段，协调者发送PreCommit请求，参与者收到后执行可回滚的事务操作，并返回ACK响应。
    • 第三阶段，协调者发送commit或rollback请求，参与者执行。