概念解释

集群

集中式系统就是把一整个系统的所有功能，包括数据库等等全部都部署在一起，通过一个整套系统对外提供服务
在多台不同的服务器中部署相同应用或服务模块，构成一个集群，通过负载均衡设备对外提供服务。

集中式系统存在系统大而复杂、难于维护、容易发生单点故障、扩展性差等问题

分布式

分布式是针对集中式来说的，就是把一个集中式系统拆分成多个系统，每一个系统单独对外提供部分功能，整个分布式系统整体对外提供一整套服务
在多台不同的服务器中部署不同的服务模块，通过远程调用协同工作，对外提供服务

计算机越多，CPU、内存、存储资源等也就越多，能够处理的并发访问量也就越大
但是分布式系统中也存在着网络通信延迟、数据一致性等问题
一致性
（Consistency）

CAP理论

组成

• 每次读取都会收到最新的写入数据或错误信息。

可用性
（Availability）

• 每个请求都会收到（非错误的）响应，但不能保证响应包含最新的写入数据。

分区容忍性
（Partition Tolerance）

• 尽管网络节点之间会丢弃（或延迟）任意数量的消息，系统仍然能够继续运行

选择权衡

CA without P

• 这种情况在分布式系统中几乎是不存在的。首先在分布式环境下，网络分区是一个自然的事实。因为分区是必然的，所以如果舍弃P，意味着要舍弃分布式系统。那也就没有必要再讨论CAP理论了。这也是为什么在CAP证明中，我们以系统满足P为前提论述了无法同时满足C和A

• 比如我们熟知的关系型数据库，如My Sql和Oracle就是保证了可用性和数据一致性，但是他并不是个分布式系统。一旦关系型数据库要考虑主备同步、集群部署等就必须要把P也考虑进来。

• 对于一个分布式系统来说。P是一个基本要求，CAP三者中，只能在CA两者之间做权衡，并且要想尽办法提升P

• 无法通过降低CA来提升P。要想提升系统的分区容错性，需要通过提升基础设施的稳定性来保障

CP without A

• 不要求强的可用性，即容许系统停机或者长时间无响应

• 设计成CP的系统其实也不少，其中最典型的就是很多分布式数据库，在发生极端情况时，优先保证数据的强一致性，代价就是舍弃系统的可用性。如HBase，还有分布式系统中常用的Zookeeper也是在CAP三者之中选择优先保证CP的。

AP wihtout C

• 为了保证高可用，需要在用户访问时可以马上得到返回，则每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。

• 很多网站大都是选择的优先保证高可用牺牲了一致性，比如淘宝的购物，12306的买票，你购买的时候提示你是有票的（但是可能实际已经没票了），你也正常的去输入验证码，下单了。但是过了一会系统提示你下单失败，余票不足

• 其实舍弃的只是强一致性。退而求其次保证了最终一致性，也就是说，虽然下单的瞬间，关于车票的库存可能存在数据不一致的情况，但是过了一段时间，还是要保证最终一致性的。

• 对于支付能需要准确保证数据的还是选择的是强一致性，如支付宝

BASE理论

BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，CAP的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consitency）

BASE是指基本可用（Basically Available）、软状态（ Soft State）、最终一致性（ Eventual Consistency）

基本可用

• 降级

• 指分布式系统在出现故障的时候，允许损失部分可用性（降级），即保证核心可用。

• 电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。

软状态

• 中间状态

• 指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。mysql replication的异步复制也是一种体现。

• 其实就是中间状态，比如当前INIT，然后处理中推进到PROCESSING，然后可以基于这个PROCESSING不断重试，直到推进到SUCCESS

最终一致性

• 重试

• 指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况。

拜占庭将军问题

拜占庭帝国的一支军队要攻打一个城市，攻打的成功需要不同将军协同决策，但是有些将军是不忠诚的，他们可能会发送虚假信息或者故意阻碍其他将军的决策。问题是如何让忠诚的将军在不知道其他将军是否忠诚的情况下做出正确的决策。

拜占庭将军问题的本质是分布式系统中的协同问题，即如何使得分布式系统中的不同节点能够在相互独立的情况下达成共识

解决拜占庭将军问题有许多方法，比较常见的就是通过投票算法、共识算法来解决，但是这些算法其实背后都基于了一个思想，那就是超过半数。

基于多数表决的解决方案：假设总共有N个将军，每个将军发送自己的意见给其他将军，然后将军们根据收到的意见进行投票，如果有超过N/2个将军投票一致，则采取投票的结果。这个方案的前提是假设叛徒的数量不超过总将军数的一半，因为如果超过一半的将军都是叛徒，则无法保证多数投票的结果是正确的。这种解决方案在很多算法中都有实践，如Raft、ZAB、Paxos等。
系统保证每个读操作都将返回最近的写操作的结果，即任何时间点，客户端都将看到相同的数据视图。这包括线性一致性（Linearizability）、顺序一致性（Sequential Consistency）和严格可串行性（Strict Serializability）等子模型。强一致性模型通常牺牲了可用性来实现数据一致性

分布式系统一致性

指数据在多个副本之间是否能够保持一致的特性
分布式系统中的一致性模型是一组管理分布式系统行为的规则。它决定了在分布式系统中如何访问和更新数据，以及如何将这些更新提供给客户端。面对网络延迟和局部故障等分布式计算难题，分布式系统的一致性模型对保证系统的一致性和可靠性起着关键作用

大分类

强一致性模型

• 线性一致性

• 是一种最强的一致性模型，它强调在分布式系统中的任何时间点，读操作都应该返回最近的写操作的结果。

• 比如，如果操作A在操作B之前成功完成，那么操作B在序列化中应该看起来在操作A之后发生，即操作A应该在操作B之前完成。线性一致性强调实时性，确保操作在实际时间上的顺序保持一致

• 顺序一致性

• 顺序一致性也是一种强一致性模型，但相对于线性一致性而言，它放宽了一些限制。在顺序一致性模型中，系统维护一个全局的操作顺序，以确保每个客户端看到的操作顺序都是一致的

• 与线性一致性不同，顺序一致性不强调实时性，只要操作的顺序是一致的，就可以接受一些延迟。

• 主要区别在于强调实时性。线性一致性要求操作在实际时间上的顺序保持一致，而顺序一致性只要求操作的顺序是一致的，但不一定要求操作的实际时间顺序

弱一致性模型

弱一致性模型放宽了一致性保证，它允许在不同节点之间的数据访问之间存在一定程度的不一致性，以换取更高的性能和可用性。这包括因果一致性（Causal Consistency）、会话一致性（Session Consistency）和单调一致性（Monotonic Consistency）等子模型。弱一致性模型通常更注重可用性，允许一定程度的数据不一致性。
最终一致性模型是一种最大程度放宽了一致性要求的模型。它允许在系统发生分区或网络故障后，经过一段时间，系统将最终达到一致状态。这个模型在某些情况下提供了很高的可用性，但在一段时间内可能会出现数据不一致的情况。

最终一致性模型

• 在时间上，虽然顺序一致性和最终一致性都不强要求实时性，但是最终一致性的时间放的会更宽。并且最终一致性其实并不强调顺序，他只需要保证最终的结果一致就行了，而顺序一致性要求操作顺序必须一致。

• 顺序一致性还是一种强一致性，比如在Zookeeper中，其实就是通过ZAB算法来保证的顺序一致性，即各个节点之间的写入顺序要求一致。并且要半数以上的节点写入成功才算成功。所以，顺序一致性的典型应用场景就是数据库管理系统以及分布式系统。

负载均衡

算法分类

静态负载均衡算法

轮询

• 顺序循环将请求一次顺序循环地连接每个服务器

比率

• 给每个服务器分配一个加权值为比例，根椐这个比例，把用户的请求分配到每个服务器。

优先权

• 给所有服务器分组,给每个组定义优先权，BIG-IP 用户的请求，分配给优先级最高的服务器组（在同一组内，采用轮询或比率算法，分配用户的请求）

• 当最高优先级中所有服务器出现故障，BIG-IP 才将请求送给次优先级的服务器组。这种方式，实际为用户提供一种热备份的方式。

动态负载均衡算法

最少连接数

• 传递新的连接给那些进行最少连接处理的服务器

最快响应速度

• 传递连接给那些响应最快的服务器

观察模式

• 连接数目和响应时间以这两项的最佳平衡为依据为新的请求选择服务器

预测法

• BIG-IP利用收集到的服务器当前的性能指标，进行预测分析，选择一台服务器在下一个时间片内，其性能将达到最佳的服务器相应用户的请求

动态性能分配

• BIG-IP 收集到的应用程序和应用服务器的各项性能参数，动态调整流量分配。

动态服务器补充

• 当主服务器群中因故障导致数量减少时，动态地将备份服务器补充至主服务器群。

服务质量

• 按不同的优先级对数据流进行分配

服务类型

• 按不同的服务类型（在Type of Field中标识）负载均衡对数据流进行分配

规则模式

• 针对不同的数据流设置导向规则，用户可自行定制

OSI模型

高层（即7、6、5、4层）定义了应用程序的功能，下面3层（即3、2、1层）主要面向通过网络的端到端的数据流。
telnet、HTTP、FTP、NFS、SMTP、DNS等属于第七层应用层的概念。
TCP、UDP、SPX等属于第四层传输层的概念。
IP、IPX等属于第三层网络层的概念。
ATM、FDDI等属于第二层数据链路层的概念。
负载均衡服务器对外依然提供一个VIP（虚IP），集群中不同的机器采用相同IP地址，但是机器的MAC地址不一样。当负载均衡服务器接受到请求之后，通过改写报文的目标MAC地址的方式将请求转发到目标机器实现负载均衡。
和二层负载均衡类似，负载均衡服务器对外依然提供一个VIP（虚IP），但是集群中不同的机器采用不同的IP地址。当负载均衡服务器接受到请求之后，根据不同的负载均衡算法，通过IP将请求转发至不同的真实服务器。
四层负载均衡工作在OSI模型的传输层，由于在传输层，只有TCP/UDP协议，这两种协议中除了包含源IP、目标IP以外，还包含源端口号及目的端口号。四层负载均衡服务器在接受到客户端请求后，以后通过修改数据包的地址信息（IP+端口号）将流量转发到应用服务器。
七层负载均衡工作在OSI模型的应用层，应用层协议较多，常用http、radius、dns等。七层负载就可以基于这些协议来负载。这些应用层协议中会包含很多有意义的内容。比如同一个Web服务器的负载均衡，除了根据IP加端口进行负载外，还可根据七层的URL、浏览器类别、语言来决定是否要进行负载均衡。
LVS（Linux Virtual Server），也就是Linux虚拟服务器, 是一个由章文嵩博士发起的自由软件项目。使用LVS技术要达到的目标是：通过LVS提供的负载均衡技术和Linux操作系统实现一个高性能、高可用的服务器群集，它具有良好可靠性、可扩展性和可操作性。从而以低廉的成本实现最优的服务性能。

负载均衡分类

二层负载均衡

三层负载均衡

四层负载均衡（常用）

七层负载均衡（常用）

负载均衡工具

LVS

• 主要用来做四层负载均衡

Nginx

是一个网页服务器，它能反向代理HTTP, HTTPS, SMTP, POP3, IMAP的协议链接，以及一个负载均衡器和一个HTTP缓存。

• 主要用来做七层负载均衡

HAProxy

是一个使用C语言编写的自由及开放源代码软件，其提供高可用性、负载均衡，以及基于TCP和HTTP的应用程序代理。

• 主要用来做七层负载均衡

业务幂等

一锁、二判、三更新

一锁

第一步，先加锁。可以加分布式锁、或者悲观锁都可以。但是一定要是一个互斥锁
第二步，进行幂等性判断。可以基于状态机、流水表、唯一性索引等等进行重复操作的判断
第三步，进行数据的更新，将数据进行持久化。
依赖悲观锁以及数据库表记录来实现

二判

三更新

分布式锁

实现方式

通过数据库

• 基于数据库表

• 创建一张锁表，当我们要锁住某个方法或资源时，我们就在该表中增加一条记录，想要释放锁的时候就删除这条记录

• CREATE TABLE `methodLock` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键',
  `method_name` varchar(64) NOT NULL DEFAULT '' COMMENT '锁定的方法名',
  `desc` varchar(1024) NOT NULL DEFAULT '备注信息',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '保存数据时间，自动生成',
  PRIMARY KEY (`id`),
  UNIQUE KEY `uidx_method_name` (`method_name `) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='锁定中的方法';

• 要锁住某个方法时，执行以下SQL：
insert into methodLock(method_name,desc) values (‘method_name’,‘desc’)
要释放锁的话，需要执行以下Sql:
delete from methodLock where method_name ='method_name'

• 问题

• 这把锁强依赖数据库的可用性，数据库是一个单点，一旦数据库挂掉，会导致业务系统不可用。

• 这把锁没有失效时间，一旦解锁操作失败，就会导致锁记录一直在数据库中，其他线程无法再获得到锁。

• 这把锁只能是非阻塞的，因为数据的insert操作，一旦插入失败就会直接报错。没有获得锁的线程并不会进入排队队列，要想再次获得锁就要再次触发获得锁操作。

• 这把锁是非重入的，同一个线程在没有释放锁之前无法再次获得该锁。因为数据中数据已经存在了。

• 解决

• 数据库是单点？搞两个数据库，数据之前双向同步。一旦挂掉快速切换到备库上。

• 没有失效时间？只要做一个定时任务，每隔一定时间把数据库中的超时数据清理一遍。

• 非阻塞的？搞一个while循环，直到insert成功再返回成功

• 非重入的？在数据库表中加个字段，记录当前获得锁的机器的主机信息和线程信息，那么下次再获取锁的时候先查询数据库，如果当前机器的主机信息和线程信息在数据库可以查到的话，直接把锁分配给他就可以了。

• 基于数据库排他锁

• 加锁

• public boolean lock(){
    connection.setAutoCommit(false)
    while(true){
        try{
            result = select * from methodLock where method_name=xxx for update;
            if(result==null){
                return true;
            }
        }catch(Exception e){

        }
    }
    return false;
}

• 解锁

• connection.commit();

• 问题

• 虽然我们对method_name 使用了唯一索引，并且显示使用for update来使用行级锁。但是，MySql会对查询进行优化，即便在条件中使用了索引字段，但是否使用索引来检索数据是由 MySQL 通过判断不同执行计划的代价来决定的，如果 MySQL 认为全表扫效率更高，比如对一些很小的表，它就不会使用索引，这种情况下 InnoDB 将使用表锁，而不是行锁。如果发生这种情况就悲剧了

• 使用排他锁来进行分布式锁的lock，那么一个排他锁长时间不提交，就会占用数据库连接。一旦类似的连接变得多了，就可能把数据库连接池撑爆

• 评价

• 优点

• 不依赖三方组件且容易理解直观

• 缺点

• 操作数据库需要一定的开销，性能问题需要考虑

• 数据库的行级锁并不一定靠谱，尤其是当我们的锁表并不大的时候

• 问题解决复杂

Redis

使用setnx、redission以及redlock实现
依赖他提供的临时有序节点来实现

Zookeeper

• 大致思想即为：每个客户端对某个方法加锁时，在zookeeper上的与该方法对应的指定节点的目录下，生成一个唯一的瞬时有序节点。判断是否获取锁的方式很简单，只需要判断有序节点中序号最小的一个。当释放锁的时候，只需将这个瞬时节点删除即可。同时，其可以避免服务宕机导致的锁无法释放，而产生的死锁问题。

锁的要求

同一个方法在同一时间只能被一台机器上的一个线程执行

是一把可重入锁（避免死锁）

一把阻塞锁（可选）

有高可用的获取锁和释放锁功能

获取锁和释放锁的性能要好

分布式session

客户端存储

用户登录后，将Session信息保存在客户端，用户在每次请求的时候，通过客户端的cookie把session信息带过来。这个方案因为要把session暴露给客户端，存在安全风险

基于分布式存储（最常用）

将Session数据保存在分布式存储系统中，如分布式文件系统、分布式数据库等。不同服务器可以共享同一个分布式存储，通过Session ID查找对应的Session数据。唯一的缺点就是需要依赖第三方存储，如Redis、数据库等。

粘性Session

把一个用户固定的路由到指定的机器上，这样只需要这台服务器中保存了session即可，不需要做分布式存储。但是这个存在的问题就是可能存在单点故障的问题

Session复制

当用户的Session在某个服务器上产生之后，通过复制的机制，将他同步到其他的服务器中。这个方案的缺点是有可能有延迟。

tomcat支持session复制
各版本介绍

分布式ID

特点

全局唯一、高性能&高可用、递增

方案

UUID

• V1. 基于时间戳的UUID

• 基于时间的UUID通过计算当前时间戳、随机数和机器MAC地址得到。由于在算法中使用了MAC地址，这个版本的UUID可以保证在全球范围的唯一性。

• 使用MAC地址会带来安全性问题，如果应用只是在局域网中使用，也可以使用退化的算法，以IP地址来代替MAC地址。

• V2. DCE(Distributed Computing Environment)安全的UUID

• 和基于时间的UUID算法相同，但会把时间戳的前4位置换为POSIX的UID或GID，这个版本的UUID在实际中较少用到。

• V3. 基于名称空间的UUID(MD5)

• 基于名称的UUID通过计算名称和名称空间的MD5散列值得到。

• 这个版本的UUID保证了：相同名称空间中不同名称生成的UUID的唯一性；不同名称空间中的UUID的唯一性；相同名称空间中相同名称的UUID重复生成得到的结果是相同的。

• V4. 基于随机数的UUID

• 根据随机数，或者伪随机数生成UUID，并不适合数据量特别大的场景

• V5. 基于名称空间的UUID(SHA1)

• 和版本3的UUID算法类似，只是散列值计算使用SHA1(Secure Hash Algorithm 1)算法。

• 总结

• Version 1和Version 2 这两个版本的UUID，主要基于时间和MAC地址，所以比较适合应用于分布式计算环境下，具有高度唯一性。

• Version 3和 Version 5 这两种UUID都是基于名称空间的，所以在一定范围内是唯一的，而且如果有需要生成重复UUID的场景的话，这两种是可以实现的。

• Version 4 这种是最简单的，只是基于随机数生成的，但是也是最不靠谱的。适合数据量不是特别大的场景下

优缺点

• 优点

• 性能比较高，不依赖网络，本地就可以生成，使用起来也比较简单。

• 缺点

• 长度过长、没有任何含义、无序

数据库自增ID

优点

• 简单且不依赖三方组件

缺点

• 单点故障问题

• 高并发访问数据库会带来阻塞问题

号段模式

每次去数据库中取ID的时候取出来一批，并放在缓存中，然后下一次生成新ID的时候就从缓存中取。这一批用完了再去数据库中拿新的。
为了防止多个实例之间发生冲突，需要采用号段的方式，即给每个客户端发放的时候按号段分开，如客户端A取的号段是1-1000，客户端B取的是1001-2000
缺点

• 没办法保证全局顺序递增

• 单点故障问题

基于Redis 实现

缺点

• redis持久化方式决定存在数据丢失的情况

雪花算法

基于时间戳+数据中心标识+机器标识+序列号，就保证了在不同进程中主键的不重复，在相同进程中主键的有序性。
缺点限制

• 每个节点的机器ID和数据中心ID都是硬编码在代码中的，而且这些ID是全局唯一的。当某个节点出现故障或者需要扩容时，就需要更改其对应的机器ID或数据中心ID，但是这个过程比较麻烦
还有就是，如果某个节点的机器ID或数据中心ID被设置成了已经被分配的ID，那么就会出现重复的ID，这样会导致系统的错误和异常。

• Snowflake算法中，需要使用zookeeper来协调各个节点的ID生成（非必要），但是ZK的部署其实是有挺大的成本的，并且zookeeper本身也可能成为系统的瓶颈。

• 依赖于系统时间的一致性，如果系统时间被回拨，或者不一致，可能会造成 ID 重复

• 解决

• 美团 Leaf 引入了 Zookeeper 来解决时钟回拨问题，其大致思路为：每个 Leaf 运行时定时向 zk 上报时间戳。每次 Leaf 服务启动时，先校验本机时间与上次发 ID 的时间，再校验与 zk 上所有节点的平均时间戳。如果任何一个阶段有异常，那么就启动失败报警。

• 百度的UidGenerator中有两种UidGenerator，其中DefautlUidGenerator使用了System.currentTimeMillis()获取时间与上一次时间比较，当发生时钟回拨时，抛出异常。而CachedUidGenerator使用是放弃了对机器的时间戳的强依赖，而是改用AtomicLong的incrementAndGet()来获取下一次时间，从而脱离了对服务器时间的依赖。