Distributed Systems
Published:
This is my personal notes for Distributed Systems.
CAP理论
分布式系统的CAP理论是由Eric Brewer于1999年首先提出的，CAP是对Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容忍性）的一种简称，如下图所示：
一致性（C）：指强一致性，在分布式系统中的同一数据有多个副本的情形下，对于数据的更新操作体现出的效果与只有单份数据是一样的。要求数据被一致地更新，所有数据变动都是同步的。
可用性（A）：客户端在任何时刻对大规模数据系统的读/写操作都应该保证在限定延时内完成。即系统在面对各种异常时，依然可以响应客户端的读/写请求并提供正常服务。
分区容忍性（P）：以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况（分布式系统一定会发生分区的情况的，因为存在网络中断、消息丢失等网络问题）。分区容忍性即指在网络中断、消息丢失的情况下，系统照样能够工作。
Eric Brewer在提出CAP概念的同时，也证明了CAP定理：任何分布式系统在可用性、一致性、分区容忍性方面，不可能同时被满足，最多只能得其二。该定理也被称作布鲁尔定理（Brewer’s theorem）。任何分布式系统的设计只是在C、A、P三者中的不同取舍而已，要么AP，要么CP，要么AC，但是不存在CAP同时存在的情况，这就是CAP定理的精髓所在。在网络环境下，运行环境出现网络分区/分割一般是不可避免的，所以分布式系统一般必须具备分区容忍性P。因此，在设计分布式系统时，架构师一般在C和A之间进行权衡和选择，即要么CP，要么AP。当然，如果系统要求为强事务型，比如面向网上支付等金融交易，我们也可以选择CA，支付宝的OceanBase就是如此。
BASE理论
对于很多互联网应用来说，对一致性的要求可以降低，而可用性的要求则更为重要，从而产生了弱一致性的BASE理论。BASE理论是基于CAP理论逐步演化而来的，其核心思想是即使不能达到强一致性，也可以根据应用特点采用适当的方法来达到最终一致性的效果。BASE是Basically Available（基本可用）、Soft state（软状态/柔性状态）、Eventually consistent（最终一致性）三个词组的简写，是对CAP中C和A的延伸。
BASE理论的含义如下：
基本可用：在绝大多数时间内系统处于可用状态，允许偶尔的失败。 软状态/柔性状态：数据状态不要求在任意时刻都完全保持同步，即状态可以有一段时间不同步。 最终一致性：与强一致性相比，最终一致性是一种弱一致性。尽管软状态不要求任意时刻数据保持一致同步，但是最终一致性要求在给定时间窗口内数据会达到一致状态。 以上就是BASE理论的基本概念，可见BASE理论强调的是系统的高可用，允许系统在一定时间内存在数据不一致，但在给定的时间窗口内，系统最终一定是要达到一致状态的。
分布式锁
为什么需要分布式锁
在单机时代，虽然不需要分布式锁，但也面临过类似的问题，只不过在单机的情况下，如果有多个线程要同时访问某个共享资源的时候，我们可以采用线程间加锁的机制，即当某个线程获取到这个资源后，就立即对这个资源进行加锁，当使用完资源之后，再解锁，其它线程就可以接着使用了。例如，在JAVA中，甚至专门提供了一些处理锁机制的一些API（synchronize/Lock等）
但是到了分布式系统的时代，这种线程之间的锁机制，就没作用了，系统可能会有多份并且部署在不同的机器上，这些资源已经不是在线程之间共享了，而是属于进程之间共享的资源。
因此，为了解决这个问题，我们就必须引入分布式锁。
分布式锁，是指在分布式的部署环境下，通过锁机制来让多客户端互斥的对共享资源进行访问。
分布式锁要满足哪些要求呢？
a. 排他性：在同一时间只会有一个客户端能获取到锁，其它客户端无法同时获取
b. 避免死锁：这把锁在一段有限的时间之后，一定会被释放（正常释放或异常释放）
c. 高可用：获取或释放锁的机制必须高可用且性能佳
讲完了背景和理论，那我们接下来再看一下分布式锁的具体分类和实际运用。
分布式锁的实现方式有哪些？
目前主流的有三种，从实现的复杂度上来看，从上往下难度依次增加：
基于数据库实现
基于Redis实现
基于ZooKeeper实现
无论哪种方式，其实都不完美，依旧要根据业务的实际场景来选择。
(1) 基于数据库实现：
基于数据库来做分布式锁，通常有两种做法：基于数据库的乐观锁，基于数据库的悲观锁
基于乐观锁的实现：
乐观锁机制其实就是在数据库表中引入一个版本号（version）字段来实现的。当我们要从数据库中读取数据的时候，同时把这个version字段也读出来，如果要对读出来的数据进行更新后写回数据库，则需要将version加1，同时将新的数据与新的version更新到数据表中，且必须在更新的时候同时检查目前数据库里version值是不是之前的那个version，如果是，则正常更新。如果不是，则更新失败，说明在这个过程中有其它的进程去更新过数据了。
基于悲观锁的实现：
悲观锁也叫作排它锁，在Mysql中是基于 for update 来实现加锁的，例如：
锁定的方法-伪代码
public boolean lock() { connection.setAutoCommit(false) for(){ result = select * from user where id = 100 for update; if(result){ //结果不为空， //则说明获取到了锁 return true; } //没有获取到锁，继续获取 sleep(1000); } return false; } //释放锁-伪代码 connection.commit();上面的示例中，user表中，id是主键，通过 for update 操作，数据库在查询的时候就会给这条记录加上排它锁。
(2) 基于Redis实现：
基于Redis实现的锁机制，主要是依赖redis自身的原子操作，例如：
SET user_key user_value NX PX 100
redis从2.6.12版本开始，SET命令才支持这些参数：
NX：只在键不存在时，才对键进行设置操作，SET key value NX 效果等同于 SETNX key value
PX millisecond：设置键的过期时间为millisecond毫秒，当超过这个时间后，设置的键会自动失效
上述代码示例是指，当redis中不存在user_key这个键的时候，才会去设置一个user_key键，并且给这个键的值设置为 user_value，且这个键的存活时间为100ms
为什么这个命令可以帮我们实现锁机制呢？
因为这个命令是只有在某个key不存在的时候，才会执行成功。那么当多个进程同时并发的去设置同一个key的时候，就永远只会有一个进程成功。
当某个进程设置成功之后，就可以去执行业务逻辑了，等业务逻辑执行完毕之后，再去进行解锁。
解锁很简单，只需要删除这个key就可以了，不过删除之前需要判断，这个key对应的value是当初自己设置的那个。
另外，针对redis集群模式的分布式锁，可以采用redis的Redlock机制。
(3) 基于ZooKeeper实现：
其实基于ZooKeeper，就是使用它的临时有序节点来实现的分布式锁。
原理就是：当某客户端要进行逻辑的加锁时，就在zookeeper上的某个指定节点的目录下，去生成一个唯一的临时有序节点， 然后判断自己是否是这些有序节点中序号最小的一个，如果是，则算是获取了锁。如果不是，则说明没有获取到锁，那么就需要在序列中找到比自己小的那个节点，并对其调用exist()方法，对其注册事件监听，当监听到这个节点被删除了，那就再去判断一次自己当初创建的节点是否变成了序列中最小的。如果是，则获取锁，如果不是，则重复上述步骤。
当释放锁的时候，只需将这个临时节点删除即可。
如图，locker是一个持久节点，node_1, node_2, ……, node_n 就是上面说的临时节点，由客户端client去创建的。
client_1, client_2, ……, clien_n 都是想去获取锁的客户端。以client_1为例，它想去获取分布式锁，则需要跑到locker下面去创建临时节点（假如是node_1）创建完毕后，看一下自己的节点序号是否是locker下面最小的，如果是，则获取了锁。如果不是，则去找到比自己小的那个节点（假如是node_2），找到后，就监听node_2，直到node_2被删除，那么就开始再次判断自己的node_1是不是序列中最小的，如果是，则获取锁，如果还不是，则继续找一下一个节点。