基本概念

吞吐量

指系统在单位时间能够处理多少个请求

QPS

每秒查询次数，通常是对读操作的压测指标

TPS

每秒处理的事务数目，通常是对写操作的压测指标

RT

响应时间间隔，是指用户发起请求，到接收到请求的时间间隔

熔断

熔断机制，是指在分布式系统中，当某个下游服务出现超时、错误率过高或资源不足等过载现象时，上游服务会迅速切断对该下游服务的请求，以避免出现故障扩散的情况。

熔断机制可以保证整个系统的可用性，避免因一个服务的局部小规模故障，导致整个系统全局瘫痪的后果。

降级

服务降级，是指当系统出现高负载或异常时，通过牺牲部分非核心功能的方式，保证系统核心功能的可用性。

背压

背压思想，被请求方不会直接将请求端的流量直接丢掉，而是不断的反馈自己的处理能力。

请求端根据这些反馈，实时的调整自己的发送频率，比如：TCP/IP中使用滑动窗口来进行流量控制。

CAP原则

Consistency（一致性）

所有节点返回的数据是一致的。

Availability（可用性）

就是某个节点坏了，不能影响其他的节点业务。

如主MySQL节点挂了，但从MySQL没有挂，从MySQL照样提供服务。

Partition Tolerance（分区容错性）

当系统中有节点因网络原因无法通信时，系统依然可以继续运行。

如主MySQL和从MySQL之间没法通信时，系统可用。

分布式系统只能满足三种情况：CA、AP、CP。

分布式系统肯定要实现P，那CA是理论上面的，其实不存在。

大型互联网公司，因为机器数量庞大，网络故障是常态，一般选择AP原则，牺牲掉数据一致性。

• 一些金融产品对数据一致性要求很高的，就会选择CP。

Redis：AP

RocketMQ：AP

2PC：CP

Eureka：AP

BASE理论

BASE 理论是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的总结，是基于 CAP 定理逐步演化而来的，它大大降低了对系统的要求。

核心思想： 即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性，也就是牺牲数据的一致性来满足系统的高可用性，系统中一部分数据的不可用或者不一致时，仍需要保持系统整体主要可用。

基本可用（Basically Available）：

基本可用是指分布式系统在出现不可预知故障的时，允许损失部分可用性。

响应时间上的损失：

• 正常情况下，一个在线搜索引擎需要在0.5秒之内返回给用户相应的查询结果，但由于出现故障，查询结果的响应时间增加了1~2秒；

系统功能上的损失：

• 正常情况下，在一个电商网站上进行购物的时候，消费者几乎能够顺利完成每一笔订单，但是在一些节日大促购物高峰的时候，由于消费者的购物行为激增，为了保护购物系统的稳定性，部分消费者可能会被引导到一个降级页面；

软状态（Soft State）：

软状态是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时；

最终一致性（Eventually Consistent）：

最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。

因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

集群和分布式的区别

集群主要的使用场景是为了分担请求的压力，也就是在几个服务器上部署相同的应用程序，来分担客户端请求。

将多台服务器集中在一起，每台服务器都实现相同的业务，做相同的事情。

分布式是指将多台服务器集中在一起，每台服务器都实现总体中的不同业务，做不同的事情。

• 将一套系统拆分成不同子系统部署在不同服务器上。

IaaS、PaaS和SaaS

软件即服务（SaaS） ：这是一个完整的软件应用程序，具有用户界面。

平台即服务（PaaS） ：开发人员可以在其中部署自己的应用程序的平台。

基础设施即服务（IaaS） ：提供机器、存储和网络资源，开发人员可以通过安装自己的操作系统、应用程序和支持资源来管理。

通俗易懂的解释：

SaaS：租的房子，只能住人和存放物品，不能修改房间的设施。

PaaS：买的精装修房，可以布置一些家电（如电视机、空调等等）、墙上挂一些装饰等等，俗称软装。

IaaS：买来的毛坯房，可以自己装修水电、安装柜子，家电等等，俗称硬装。

一致性Hash算法

假如有三台服务器编号node0、node1、node2，现在有3000万个key，希望可以将这些个key均匀的缓存到三台机器上？

可以使用取模算法hash（key）% N，对key进行hash运算后取模，N是机器的数量。

但服务器数量N发生变化后hash（key）% N计算的结果也会随之变化。

一致性hash算法本质上也是一种取模算法，不过不同于上边按服务器数量取模，一致性hash是对固定值2^32取模。

IPv4的地址是4组8位2进制数组成，所以用2^32可以保证每个IP地址会有唯一的映射。

将这2^32个值抽象成一个圆环，圆环的正上方的点代表0，顺时针排列，以此类推，1、2、3、4、5、6……直到2^32-1，而这个由2的32次方个点组成的圆环统称为hash环。

服务器映射到hash环:

使用服务器IP地址进行hash计算，用哈希后的结果对2^32取模，结果一定是一个0到2^32-1之间的整数，而这个整数映射在hash环上的位置代表了一个服务器，依次将node0、node1、node2三个缓存服务器映射到hash环上。

一致性hash的优势：

假如业务量激增，系统需要进行扩容增加一台服务器node-4，刚好node-4被映射到node-1和node-2之间，沿顺时针方向对象映射节点，发现原本缓存在node-2上的对象key-4、key-5被重新映射到了node-4上，而整个扩容过程中受影响的只有node-4和node-1节点之间的一小部分数据。

假如node-1节点宕机，沿顺时针方向对象映射节点，缓存在node-1上的对象key-1被重新映射到了node-4上，此时受影响的数据只有node-0和node-1之间的一小部分数据。

数据偏斜问题：

在服务器节点数量太少的情况下，很容易因为节点分布不均匀而造成数据倾斜问题，被缓存的对象大部分缓存在node-4服务器上，导致其他节点资源浪费，系统压力大部分集中在node-4节点上，这样的集群是非常不健康的。

一致性Hash算法引入了一个虚拟节点机制，即对每个服务器节点计算出多个hash值，它们都会映射到hash环上，映射到这些虚拟节点的对象key，最终会缓存在真实的节点上。

一致性hash的应用场景：

一致性hash在分布式系统中应该是实现负载均衡的首选算法，比如日常使用较多的缓存中间件memcached和redis集群都有用到它。

限流算法

固定窗口限流算法

原理是在固定时间窗口(单位时间)内限制请求的数量。

• 该算法将时间分成固定的窗口，并在每个窗口内限制请求的数量。

将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出了限制，则拒绝该请求。

假设单位时间(固定时间窗口)是1秒，限流阀值为3。

在单位时间1秒内，每来一个请求，计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。

• 等到1s结束后，计数器清0，重新开始计数。

固定窗口算法缺点:

存在明显的临界问题。

假设限流阀值为5个请求，单位时间窗口是1s。

如果在单位时间内的前0.8-1s和1-1.2s，分别并发5个请求。

虽然都没有超过阀值，但是如果算0.8-1.2s，则并发数高达10，已经超过单位时间1s不超过5阀值的定义了。

滑动窗口限流算法

它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数。

• 并且根据时间滑动删除过期的小周期。

它可以解决固定窗口临界值的问题。

假设单位时间还是1s，滑动窗口算法把它划分为5个小周期，也就是滑动窗口（单位时间）被划分为5个小格子。

• 每格表示0.2s，每过0.2s，时间窗口就会往右滑动一格。

然后每个小周期，都有自己独立的计数器。

• 如果请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。

当滑动窗口的格子周期划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

伪代码实现：

 /**
     * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
     */
    private int SUB_CYCLE = 10;

    /**
     * 每分钟限流请求数
     */
    private int thresholdPerMin = 100;

    /**
     * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
     */
    private final TreeMap<Long, Integer> counters = new TreeMap<>();

   /**
     * 滑动窗口时间算法实现
     */
     public synchronized boolean slidingWindowsTryAcquire() {
        long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
        int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数

        //超过阀值限流
        if (currentWindowNum >= thresholdPerMin) {
            return false;
        }

        //计数器+1
        counters.get(currentWindowTime)++;
        return true;
    }

   /**
    * 统计当前窗口的请求数
    */
    private synchronized int countCurrentWindow(long currentWindowTime) {
        //计算窗口开始位置
        long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
        int count = 0;

        //遍历存储的计数器
        Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Long, Integer> entry = iterator.next();
            // 删除无效过期的子窗口计数器
            if (entry.getKey() < startTime) {
                iterator.remove();
            } else {
                //累加当前窗口的所有计数器之和
                count =count + entry.getValue();
            }
        }
        return count;
    }

算法特点：

• 因为窗口顺延，所以可以抵御窗口间突发流量。

在实际应用中我们要的限流效果往往不希望一下子把流量掐断，而是让流量平滑地进入系统当中。

• 这就需要对流速进行平滑控制。

假如限流10万次/小时，若某个调用者在前10分钟就调用了10万次。

那么他必须再等待1小时才能发起下一次正常请求，所以没有做到前后请求隔离。

漏桶限流算法

对于每个到来的数据包，都将其加入到漏桶中，并检查漏桶中当前的水量是否超过了漏桶的容量。

• 如果超过了容量，就将多余的数据包丢弃。

如果漏桶中还有水，就以一定的速率从桶底输出数据包。

• 保证输出的速率不超过预设的速率，从而达到限流的目的。

算法特点：

因为流出的速度是一定的，可以抵御突发流量，做到更加平滑的限流，而且不允许流量突发。

由于是限定消费速度，无法应对突发流量的来袭，以及处理请求会有延迟，不符合互联网业务低延时的要求。

令牌桶算法

该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶中放入一定数量的令牌。

当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌，否则请求被拒绝。

算法特点：

可以抵御突发流量，因为桶内的令牌数不会超过给定的最大值。

可以做到更加平滑的限流，因为令牌是匀速放入的。

令牌桶算法相比漏桶算法，允许流量一定程度的突发。

在时间点刷新的临界点上，只要剩余Token足够，令牌桶算法会允许对应数量的请求通过。

而后刷新时间因为Token不足，流量也会被限制在外，这样就比较好的控制了瞬时流量，因此令牌桶算法也被广泛使用。

限流组件

异地多活

同城灾备

在同一个城市 再搭建一个机房，原机房叫作 A 机房，新机房叫 B 机房，这两个机房的网络用一条 专线 连通。

• 为了避免 A 机房故障导致数据丢失，需要把数据在 B 机房也存一份。

两地三中心

两地是指 2 个城市，三中心是指有 3 个机房。

• 其中 2 个机房在同一个城市，并且同时提供服务，第 3 个机房部署在异地，只做数据灾备。

异地双活

两个机房同时提供服务，故障随时可切换，可用性高。

同城双活比灾备的优势在于：

• 两个机房都可以接入读写流量，提高可用性的同时，还提升了系统性能。

在最上层把用户区分开，部分用户请求固定打到北京机房，其它用户请求固定打到上海 机房，进入某个机房的用户请求。

• 之后的所有业务操作，都在这一个机房内完成，从根源上避免跨机房。

需要在接入层之上，再部署一个路由层（通常部署在云服务器上），自己可以配置路由规则，把用户分流到不同的机房内。

• 按业务类型分片

• 直接哈希分片

• 按地理位置分片

基本架构

面向服务架构(SOA)

基于分布式架构模式演变而来，俗称服务化，也就是面向接口开发(服务开发)。

将共同存在的业务逻辑抽取成一个共同的服务，提供给其他的服务接口实现调用。

• 服务与服务之间通讯采用RPC远程调用技术，可以解决代码冗余性问题。

采用SOAP协议实现传输。

• 在高并发情况下会存在大量的冗余性传输，非常占用带宽，所以微服务框架用JSON替代了XML。

实现方案为WebService或者是ESB企业服务总线，底层通讯协议SOAP协议（HTTP+XML）实现传输。

• 采用SOAP协议实现通讯，XML传输非常重，效率比较低，而且很占带宽。

微服务架构

微服务架构基于SOA架构演变过来的。

比SOA架构模式对服务拆分粒度更加精细，采用前后端分离的架构模式。

• 让专业的人去做专业的事，目的可以实现高效率的开发。

微服务架构中，每个服务都是独立部署、独立运营，之间互不影响。

服务与服务之间通讯的协议采用Restful形式，数据交换格式采用HTTP+JSON格式实现传输。

• 整个传输过程中，采用二进制，可以实现跨语言。

SOA架构中可能数据库存储会发生共享，微服务强调独每个服务都是单独数据库，保证每个服务于服务之间互不影响。

HTTP和RPC的区别

传输协议

• RPC：可以基于TCP协议，也可以基于HTTP协议。
• HTTP：基于HTTP协议。

传输效率

• RPC：使用自定义的TCP协议，可以让请求报文体积更小。
• HTTP：请求中会包含很多无用的内容。

性能消耗

• RPC：可以基于Thrift实现高效的二进制传输。
• HTTP：大部分是通过JSON实现的，字节大小和序列化耗时都比Thrift要更消耗性能。

负载均衡

• RPC：基本都自带了负载均衡策略。

• HTTP：需要配置Nginx，HAProxy实现负载均衡。

RPC主要用于公司内部服务调用，性能消耗低，传输效率高，服务治理方便。

HTTP主要用于对外的异构环境，浏览器调用，APP接口调用，第三方接口调用等等。

在内部子系统较多、接口较多的情况下，RPC框架的好处就凸显出现了。

首先是长连接，不必每次通信都要像HTTP那样三次握手，减少了网络开销。

其次是RPC框架一般都有注册中心，有丰富的监控发布方法。

RPC接口的发布、下线、动态扩展等对调用方是无感知的、统一化的操作。

Serverless

基于 Serverless 开发者就只需要关心业务逻辑的开发。

进行应用部署时也不再需要关心服务器，不需要关心后续的运维，应用也天然具备了弹性伸缩的能力。

• 并且实现了按需使用，按量付费，也更能进一步节省成本。

Sidecar设计模式

Sidecar，也就是边车模式，是一种分布式服务架构的设计模式。

边车模式中的边车，实际上就是一个 Agent，微服务的通信可以通过 Agent 代理完成。

在部署时，需要同时启动 Agent，Agent 会处理服务注册、服务发现、日志和服务监控等逻辑。

• 这样在开发时，就可以忽略这些和对外业务逻辑本身没有关联的功能，实现更好的内聚和解耦。

ServiceMeh服务网格

Service Mesh 基于边车模式演进，通过在系统中添加边车代理，也就是 Sidecar Proxy 实现。

Service Mesh 服务网格抽象出专门的一层，提供服务治理领域所需的服务注册发现、负载均衡、熔断降级、监控等功能。

• Service Mesh统一管理微服务与上层通信的部分，接管各种网络通信、访问控制等。

我们的业务代码只需要关心业务逻辑就可以，简化开发工作。

Service Mesh 和 API 网关的区别：

部署方式不同，在整体系统架构中的位置不一样。

API 网关通常是独立部署，通过单独的系统提供服务，为了实现高可用，还会通过网关集群等来管理。

而服务网格通常是集成在应用容器内的，服务网格离应用本身更近。

Service Mesh 解决方案：

目前两款流行的 Service Mesh 开源软件分别是 Istio 和 Linker。

应用场景

TraceId

通过 TraceId 来将一个请求在各个服务器上的调用日志串联起来，TraceId 一般由接收请求经过的第一个服务器产生。

SpanId 代表本次调用在整个调用链路树中的位置。

假设一次分布式调用中产生的 TraceId 是 0a1234，SpanId 的产生过程：

• 系统 A 接收了一次用户请求，记录下的 SpanId 是 0，代表是整个调用的根节点。

• A 系统处理这次请求，依次调用 B、C、D 三个系统，SpanId 分别是 0.1，0.2 和 0.3。

• C 系统在处理请求的时候又调用了 E，F 两个系统，那么 E、F 两个系统是 0.2.1 和 0.2.2。

分布式Session

Session复制:

Session复制方案是一个服务器端的方案，对客户端是透明的，客户端不需要改变什么。

这个方案本质是利用了应用服务器自身的特性，如：Tomcat。

修改一下Tomcat的配置文件，就是让应用服务器之间进行Session复制，这样就可以达到每个服务器都有一样的Session。

服务器一旦多起来，就会有问题:

• Ssession之间的复制就会占用很大的网络带宽。

• Session复制是有时间延迟的。

• 服务器的内存是有限的，代表着Session存放是有限的。

Session粘性:

利用负载均衡器的特性，把同一个浏览器的同一个用户都定向发送到同一个服务器上。

用户甲访问系统被负载均衡器一直分配到服务器A上，这样也就保证了用户一直在同一个服务器中进行查找Session，保证了用户Session一致性。

外部存储:

外部存储让Session的存储与应用服务器隔离出来。

把Session的存储的地方改造到一个独立的媒介中，这样就不需要和应用服务器耦合了，客户端传入SessionId时，用户信息的映射关系直接到这个独立媒介中去查找。

• 数据库存储
• Redis存储

分布式ID

数据库号段模式

号段模式为从数据库批量的获取自增ID，每次从数据库取出一个号段范围。

例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。

• biz_type ：代表不同业务类型

• max_id ：当前最大的可用id

• step ：代表号段的长度

• version ：是一个乐观锁，每次都更新version，保证并发时数据的正确性

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '当前最大id',
  step int(20) NOT NULL COMMENT '号段的布长',
  biz_type	int(20) NOT NULL COMMENT '业务类型',
  version int(20) NOT NULL COMMENT '版本号',
  PRIMARY KEY (`id`)
) 

等这批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，update max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]。

update id_generator set max_id = #{max_id+step}, version = version + 1 where version = # {version} and biz_type = XXX

由于多业务端可能同时操作，所以采用版本号version乐观锁方式更新，这种分布式ID生成方式不强依赖于数据库，不会频繁的访问数据库，对数据库的压力小很多。

雪花SnowFlake算法

雪花算法生成64位的二进制正整数，然后转换成10进制的数。

64位二进制数由如下部分组成：

**1位标识符：**始终是0

41位时间戳：存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是ID生成器开始使用的时间，由程序来指定的

10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成

**12位序列：**毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

优点：

每秒能够产生409.6万个ID，性能快

时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增

灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求

缺点：

依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成

优化思路:

思路就是在系统中监控每台时钟是否回拨？如果回拨了，作一下调整就行了。

持久化节点的作用：就是保存各个ID服务的节点信息，并保存时钟。

整体流程:

1、ID服务启动，注册到Zookeeper。

2、检查是否之前注册过，如果没有注册过，就把此服务注册到Zookeeper中。

3、节点的信息利用顺序节点，保证唯一。

• ID服务把此生成的顺序ID当作workID，保存到本地文件系统中，这样以后再次启动时，就拿着此workId到 zk 上面去查找，是否之前注册过。

4、如果之前没有注册过，生成了ID服务的zk节点，并把本地的时钟保存到此zk节点中。

• ID服务会每隔3秒，把本地时钟上报到zk节点上面。

5、如果在注册的时候，发现已经注册了，要去比较一下本地时钟 和 zk 节点上面的时钟。

• 如果本地时钟 大于 zk 上的，表示正常，启动成功。
• 否则表示本地的时钟发生了回拨，启动不成功，启动报警机制。

算法实现：

/**
 * Twitter的SnowFlake算法,使用SnowFlake算法生成一个整数，然后转化为62进制变成一个短地址URL
 *
 * https://github.com/beyondfengyu/SnowFlake
 */
public class SnowFlakeShortUrl {

    /**
     * 起始的时间戳
     */
    private final static long START_TIMESTAMP = 1480166465631L;

    /**
     * 每一部分占用的位数
     */
    private final static long SEQUENCE_BIT = 12;   //序列号占用的位数
    private final static long MACHINE_BIT = 5;     //机器标识占用的位数
    private final static long DATA_CENTER_BIT = 5; //数据中心占用的位数

    /**
     * 每一部分的最大值
     */
    private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
    private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
    private final static long MAX_DATA_CENTER_NUM = -1L ^ (-1L << DATA_CENTER_BIT);

    /**
     * 每一部分向左的位移
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
    private final static long TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT;

    private long dataCenterId;  //数据中心
    private long machineId;     //机器标识
    private long sequence = 0L; //序列号
    private long lastTimeStamp = -1L;  //上一次时间戳

    private long getNextMill() {
        long mill = getNewTimeStamp();
        while (mill <= lastTimeStamp) {
            mill = getNewTimeStamp();
        }
        return mill;
    }

    private long getNewTimeStamp() {
        return System.currentTimeMillis();
    }

    /**
     * 根据指定的数据中心ID和机器标志ID生成指定的序列号
     *
     * @param dataCenterId 数据中心ID
     * @param machineId    机器标志ID
     */
    public SnowFlakeShortUrl(long dataCenterId, long machineId) {
        if (dataCenterId > MAX_DATA_CENTER_NUM || dataCenterId < 0) {
            throw new IllegalArgumentException("DtaCenterId can't be greater than MAX_DATA_CENTER_NUM or less than 0！");
        }
        if (machineId > MAX_MACHINE_NUM || machineId < 0) {
            throw new IllegalArgumentException("MachineId can't be greater than MAX_MACHINE_NUM or less than 0！");
        }
        this.dataCenterId = dataCenterId;
        this.machineId = machineId;
    }

    /**
     * 产生下一个ID
     *
     * @return
     */
    public synchronized long nextId() {
        long currTimeStamp = getNewTimeStamp();
        if (currTimeStamp < lastTimeStamp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currTimeStamp == lastTimeStamp) {
            //相同毫秒内，序列号自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列数已经达到最大
            if (sequence == 0L) {
                currTimeStamp = getNextMill();
            }
        } else {
            //不同毫秒内，序列号置为0
            sequence = 0L;
        }

        lastTimeStamp = currTimeStamp;

        return (currTimeStamp - START_TIMESTAMP) << TIMESTAMP_LEFT //时间戳部分
                | dataCenterId << DATA_CENTER_LEFT       //数据中心部分
                | machineId << MACHINE_LEFT             //机器标识部分
                | sequence;                             //序列号部分
    }
    
    public static void main(String[] args) {
        SnowFlakeShortUrl snowFlake = new SnowFlakeShortUrl(2, 3);

        for (int i = 0; i < (1 << 4); i++) {
            //10进制
            System.out.println(snowFlake.nextId());
        }
    }
}

百度（uid-generator）

https://github.com/baidu/uid-generator

美团（Leaf）

https://link.zhihu.com/?target=https%3A//github.com/Meituan-Dianping/Leaf

滴滴（Tinyid）

https://github.com/didi/tinyid

分布式锁

分布式锁是控制分布式系统不同进程共同访问共享资源的一种锁的实现。

如果不同的系统或同一个系统的不同主机之间共享了某个临界资源，往往需要互斥来防止彼此干扰，以保证一致性。

业界分布式锁的实现，一般有这3种方式：

基于数据库实现的分布式锁

基于Redis实现的分布式锁

基于Zookeeper实现的分布式锁

对比：

• 从性能角度（从高到低）Redis > Zookeeper >= 数据库；

• 从实现的复杂性角度（从低到高）Zookeeper > Redis > 数据库。

• 从可靠性角度（从高到低）Zookeeper > Redis > 数据库。

基于数据库的分布式锁

数据库悲观锁实现的分布式锁：

可以使用select ... for update 来实现分布式锁。

数据库乐观锁实现的分布式锁:

加个version字段，每次更新修改，都会自增加一，然后去更新时，把查出来的那个版本号，带上条件去更新，如果是上次那个版本号，就更新，如果不是，就继续重试。

分库分表

分库分表是在海量数据下，由于单库、表数据量过大，导致数据库性能持续下降的问题，演变出的技术方案。

为什么分库分表

单机数据库的存储能力、连接数是有限的，它自身就很容易会成为系统的瓶颈。

当单表数据量千万以上时，数据库很多操作性能下降严重。

如何分库分表

垂直分库:

垂直分库一般来说按照业务和功能的维度进行拆分，将不同业务数据分别放到不同的数据库中。

垂直分表:

垂直分表针对业务上字段比较多的大表进行的，一般是把业务宽表中比较独立的字段。

• 或者不常用的字段拆分到单独的数据表中，是一种大表拆小表的模式。

水平分库:

水平分库是把同一个表按一定规则拆分到不同的数据库中，每个库可以位于不同的服务器上，以此实现水平扩展。

水平分表：

水平分表是在同一个数据库内，把一张大数据量的表按一定规则，切分成多个结构完全相同表，而每个表只存原表的一部分数据。

数据存在哪个库的表

取模算法:

以t_order订单表为例，先给数据库从 0 到 N-1 进行编号。

对 t_order订单表中order_no订单编号字段进行取模hash(order_no) mod N，得到余数i。

i=0存第一个库，i=1存第二个库，i=2存第三个库，以此类推。

优点:

实现简单，数据分布相对比较均匀，不易出现请求都打到一个库上的情况。

缺点:

对集群的伸缩支持不太友好。

如果机器数减少，算法发生变化hash(user_id) mod N-1，同一用户数据落在了在不同数据库中。

• 等这台机器恢复，用user_id作为条件查询用户数据就会少一部分。

范围限定算法：

用户表t_user被拆分成t_user_1、t_user_2、t_user_3三张表。

后续将user_id范围为1 ~ 1000w的用户数据放入t_user_1，1000~ 2000w放入t_user_2，2000~3000w放入t_user_3，以此类推。

优点:

单表数据量是可控的。

水平扩展简单只需增加节点即可，无需对其他分片的数据进行迁移。

缺点:

由于连续分片可能存在数据热点。

比如按时间字段分片时，如果某一段时间（双11等大促）订单骤增，存11月数据的表可能会被频繁的读写。

• 其他分片表存储的历史数据则很少被查询，导致数据倾斜，数据库压力分摊不均匀。

范围 + 取模算法

先通过范围算法定义每个库的用户表t_user只存1000w数据。

• 第一个db_order_1库存放userId从1 ~ 1000w，第二个库1000~2000w，第三个库2000~3000w，以此类推。

每个库里再把用户表t_user拆分成t_user_1、t_user_2、t_user_3等，对userd进行取模路由到对应的表中。

有效的避免数据分布不均匀的问题，数据库水平扩展也简单，直接添加实例无需迁移历史数据。

分库分表出来的问题

分页、排序、跨节点联合查询。

事务一致性。

全局唯一的主键。

分库分表架构模式

客户端模式:

指分库分表的逻辑都在你的系统应用内部进行控制，应用会将拆分后的SQL直连多个数据库进行操作，然后本地进行数据的合并汇总等操作。

代理模式：

将应用程序与MySQL数据库隔离，业务方的应用不在需要直连数据库，而是连接Proxy代理服务。

• 代理服务实现了MySQL的协议，对业务方来说代理服务就是数据库，它会将SQL分发到具体的数据库进行执行，并返回结果。

如何部署上线

双写部署法:

假设一张叫 test_tb 的表进行拆分，你要进行双写，系统里和 test_tb表有关的业务会加入一段双写代码，同时往老库和新库中写，然后进行部署。

• 历史数据:在部署前，数据库表 test_tb 的有关数据。

• 增量数据:在部署后，数据库表 test_tb 的新产生的数据。

迁移流程:

计算你要迁移的那张表的 max(主键) 。

在迁移过程中，只迁移 db-old 中 test_tb 表里主键小等于该 max(主键) 的值：历史数据。

与 test_tb 有关的业务，多加一条往消息队列中发消息的代码，将操作的写SQL发送到消息队列中：增量数据。

如何选择分表键

分表键，即用来分库/分表的字段，你以哪个维度来分库分表的。

• 比如你按用户ID分表、按时间分表、按地区分表，这些用户ID、时间、地区就是分表键。

一般数据库表拆分的原则，需要先找到业务主题。

• 比如你的数据库表是一张企业客户信息表，就可以考虑用了客户号做为分表键。

分库分表后非分片键如何查询

基因法:

将分片键的信息保存在想要查询的列中，这样通过查询的列就能直接知道所在的分片信息，叫做基因法。

• 基因法的原理理论：对一个数取余2的n次方，那么余数就是这个数的二进制的最后n位数。

这样实现的缺点是，主键值会变大一些，存储也会相应变大，这样空间换时间的设计。

• 实际上淘宝的订单号也是这样构建的。

假如现在根据user_id进行分片，采用user_id % 16的方式来进行数据库路由，这里的user_id%16。

• 其本质是user_id的最后4个bit位 log(16,2) = 4 决定这行数据落在哪个分片上，这4个bit就是分片基因。

如上图所示，user_id=20160169的用户创建了一个订单（20160169的二进制表示为：1001100111001111010101001)

• 使用user_id%16分片，决定这行数据要插入到哪个分片中。
• 分库基因是user_id的最后4个bit，log(16,2) = 4，即1001。
• 在生成order_id时，先使用一种分布式ID生成算法生成前60bit（上图中绿色部分）。
• 将分库基因加入到order_id的最后4个bit（上图中粉色部分）。
• 拼装成最终的64bit订单order_id（上图中蓝色部分）。

这样保证了同一个用户创建的所有订单都落到了同一个分片上，order_id的最后4个bit都相同，于是：

• 通过user_id %16 能够定位到分片。
• 通过order_id % 16也能定位到分片。

分布式算法

Paxos算法

在常见的 分布式系统 中，总会发生 节点宕机 或 网络异常 (包括消息的 重复、丢失、延迟、乱序、网络分区) 等情况。

Paxos 算法主要就是解决如何在一个 发生如上故障 的分布式系统中，快速正确的在集群内 对某个值达成一致，并且保证 整个系统的一致性。

• 这里某个数据的值并不只是狭义上的某个数，它可以是一条日志，也可以是一条命令。
• 根据应用场景不同，某个数据的值有不同的含义。

角色:

Proposer : Proposer 可以 提出提案 (Proposal)。

Accecptor : Acceptor 可以 接受提案，一旦接受提案，提案 里面的 value 值就被选定了。

Learner : Acceptor 告诉 Learner 哪个提案被选定了，那么 Learner 就学习这个被选择的 value。

算法流程：

学习阶段：Prepare请求

Proposer 选择一个新的提案 向 Acceptor 集合 （数目在半数以上）发送请求，要求 每一个 Acceptor 做出如下响应：

• 如果 Acceptor 没有接受过提案，则向 Proposer 保证 不再接受编号小于N的提案。

• 如果 Acceptor 接受过请求，则向 Proposer 返回 已经接受过的编号小于N的编号最大的提案。

接受阶段：Acceptor请求

如果 Proposer 收到 半数以上 的 Acceptor 响应，则 生成编号为 N，value 为 V 的提案，V 为所有响应中 编号最大 的提案的 value。

如果 Proposer 收到的响应中 没有提案，那么 value 由 Proposer 自己生成，生成后将此提案发送，并期望 Acceptor 能接受此提案。

Raft算法

Raft 是一种更为简单方便易于理解的分布式算法，主要解决了分布式中的一致性问题。

三类角色：

Leader（领袖），Follower（群众），Candidate（候选人）

选举过程

一个最小的 Raft 民主集群需要 三个参与者（A、B、C），这样才可能投出多数票。

初始状态 ABC 都是 Follower，然后发起选举这时有 三种 可能的情形发生。

下图中前二种都能选出 Leader，第三种则表明 本轮投票无效（Split Votes）。

对于第三种，每方都投给了自己，结果没有任何一方获得多数票。

之后 每个参与方 随机休息一阵（Election Timeout）重新发起投票直到一方获得多数票。

这里的关键就是随机 timeout，最先从 timeout 中恢复发起投票的一方，向还在 timeout 中的另外两方 请求投票，这时它就只能投给自己，导致很快达成一致。

选出 Leader 后，Leader 通过 定期 向所有 Follower 发送 心跳信息 维持其统治。

若 Follower 一段时间未收到 Leader 的 心跳，则认为 Leader 可能已经挂了，然后再次发起 选举 过程。

分布式事务

柔性事务

柔性事务主要分为补偿型和通知型。

补偿型事务分：TCC、Saga。

通知型事务分：MQ事务消息、最⼤努⼒通知型。

补偿型事务都是同步的，通知型事务都是异步的。

二阶段提交

二阶段提交协议(2PC)

二阶段提交算法的成立基于以下假设：

在该分布式系统中，存在一个节点作为协调者（Coordinator），其他节点作为参与者（Participants），且节点之间可以进行网络通信；

所有节点都采用预写式日志，日志被写入后被保存在可靠的存储设备上，即使节点损坏也不会导致日志数据的丢失；

所有节点不会永久性损坏，即使损坏后仍然可以恢复。

两阶段提交中的两个阶段，指的是 Commit-Request 阶段和 Commit 阶段，两阶段提交的流程如下：

提交请求阶段（Commit-Request）

在提交请求阶段，协调者将通知事务参与者准备提交事务，然后进入表决过程。

在表决过程中，参与者将告知协调者自己的决策：

• 同意（事务参与者本地事务执行成功）或取消（本地事务执行故障），在第一阶段，参与节点并没有进行Commit操作。

提交阶段（Commit）

在提交阶段，协调者将基于第一个阶段的投票结果进行决策：

提交或取消这个事务，这个结果的处理和前面基于半数以上投票的一致性算法不同，必须当且仅当所有的参与者同意提交，协调者才会通知各个参与者提交事务，否则协调者将通知各个参与者取消事务。

参与者在接收到协调者发来的消息后将执行对应的操作，也就是本地 Commit 或者 Rollback。

两阶段提交存在的问题：

资源被同步阻塞:

• 在执行过程中，所有参与节点都是事务独占状态，当参与者占有公共资源时，那么第三方节点访问公共资源会被阻塞。

协调者可能出现单点故障:

• 一旦协调者发生故障，参与者会一直阻塞下去。

在 Commit 阶段出现数据不一致:

在第二阶段中，假设协调者发出了事务 Commit 的通知，但是由于网络问题该通知仅被一部分参与者所收到并执行 Commit，其余的参与者没有收到通知，一直处于阻塞状态，那么，这段时间就产生了数据的不一致性。

三阶段提交

三阶段提交协议(3PC)

为了解决二阶段协议中的同步阻塞等问题，三阶段提交协议在协调者和参与者中都引入了超时机制，并且把两阶段提交协议的第一个阶段拆分成了两步：询问，然后再锁资源，最后真正提交。

三阶段中的 Three Phase 分别为 CanCommit、PreCommit、DoCommit 阶段。

三阶段提交做了哪些改进:

引入超时机制:

在 2PC 中，只有协调者拥有超时机制，如果在一定时间内没有收到参与者的消息则默认失败，3PC 同时在协调者和参与者中都引入超时机制。

添加预提交阶段:

在 2PC 的准备阶段和提交阶段之间，插入一个准备阶段，使 3PC 拥有 CanCommit、PreCommit、DoCommit 三个阶段，PreCommit 是一个缓冲，保证了在最后提交阶段之前各参与节点的状态是一致的。

三阶段提交协议存在的问题

在阶段三中，如果参与者接收到了 PreCommit 消息后，出现了不能与协调者正常通信的问题，在这种情况下，参与者依然会进行事务的提交，这就出现了数据的不一致性。

MQ消息事务

方案一：依靠MQ的事务消息机制来实现投递消息和参与者⾃身本地事务的⼀致性保障。

消息的可靠发送由发送端 Producer进行保证(消费端无需考虑)，可靠发送消息的步骤如下：

• 发送一个事务消息，RocketMQ将消息状态标记为Prepared，注意此时这条消息消费者是无法消费到的。
• 执行业务代码逻辑，可能是一个本地数据库事务操作。
• 确认发送消息，RocketMQ将消息状态标记为可消费，这个时候消费者，才能真正的保证消费到这条数据。

如果确认消息发送失败了怎么办？

• RocketMQ会定期扫描消息集群中的事务消息，如果发现了Prepared消息，它会向消息发送端(生产者)确认。
• RocketMQ会根据发送端设置的策略来决定是回滚还是继续发送确认消息。
• 这样就保证了消息发送与本地事务同时成功或同时失败。

如果消费失败怎么办？

• 阿里提供的解决方法是：人工解决。

方案二：并不是所有的MQ都支持事务消息。

• 也就是消息一旦发送到消息队列中，消费者立马就可以消费到，此时可以使用独立消息服务、或者本地事务表。

刚开始处于prepare状态，业务逻辑处理成功后，确认发送消息，这个时候 独立消息服务 才会真正的把消息发送给消息队列。

消费者消费成功后，ack时，除了对消息队列进行ack，对于独立消息服务也要进行ack，独立消息服务一般是把这条消息删除。

而定时扫描prepare状态的消息，向消息发送端(生产者)确认的工作也由独立消息服务来完成。

最大努力通知

适用于一些最终一致性时间敏感度低的业务，且被动方处理结果 不影响主动方的处理结果。

典型的使用场景：如银行通知、商户通知等。

最大努力通知型的实现方案，一般符合以下特点：

不可靠消息：

• 业务活动主动方，在完成业务处理之后，向业务活动的被动方发送消息，直到通知N次后不再通知，允许消息丢失(不可靠消息)。

定期校对：

• 业务活动的被动方，根据定时策略，向业务活动主动方查询(主动方提供查询接口)，恢复丢失的业务消息。

举例：一个短信发送平台，背景是公司内部有多个业务都有发送短信的需求，如果每个业务独立实现短信发送功能，存在功能实现上的重复。

有一个短信平台项目，所有的业务方都接入这个短信平台，来实现发送短信的功能。

1、业务方将短信发送请求提交给短信平台

2、短信平台接收到要发送的短信，记录到数据库中，并标记其状态为已接收

3、短信平台调用外部短信发送供应商的接口，发送短信

4、更新短信发送状态为已发送

5、短信发送供应商异步通知短信平台短信发送结果，而通知可能失败，因此最多只会通知N次

6、短信平台接收到短信发送结果后，更新短信发送状态，可能是成功，也可能失败(如手机欠费)

7、如果最多只通知N次，如果都失败了的话，那么短信平台将不知道短信到底有没有成功发送

8、短信发送供应商需要提供一个查询接口，以方便短信平台驱动的去查询，进行定期校对

TCC事务

TCC将事务过程分为Try（尝试）、Confirm（确认）和Cancel（取消）三个阶段，每个阶段由业务代码控制，避免了长事务的问题，从而提高了性能。

Try阶段：

• 尝试执行业务并完成所有业务检查，预留业务资源。

Confirm和Cancel阶段：这两个操作是互斥的，只可以选择其中一个。

• Confirm操作是确认提交，执行业务操作，不进行其他业务检查，只使用Try阶段预留的业务资源。
• Cancel操作在业务执行错误需要回滚的情况下执行，释放预留的资源。

Try 阶段失败可以 Cancel，如果 Confirm 和 Cancel 阶段失败了呢？

TCC事务模型中会使用事务日志来记录Try、Confirm和Cancel阶段的操作。

如果在Confirm或Cancel阶段发生错误，系统会进行重试操作。

因此，这两个阶段需要支持幂等性，以确保多次执行的结果与一次执行的结果相同。

如果重试操作失败，就需要人工介入来进行恢复和处理。

TCC的缺点：

TCC对微服务的侵入性较强，需要对业务系统进行改造，每个分支的业务逻辑都需要实现try、confirm和cancel操作，并且confirm和cancel操作必须保证幂等性。

TCC的事务管理器需要记录事务日志，这也会带来一定的性能损耗。

与2PC/XA两阶段提交的区别:

2PC/XA关注数据库层面的强一致性，持有数据库锁。

而TCC关注业务层面的最终一致性，不涉及加锁，并且将相关的处理从数据库转移到业务中，实现跨数据库的事务。

空回滚问题:

在 try 阶段服务 发生了故障，try 阶段在不考虑重试的情况下，全局事务必须要走向结束状态，这样就需要在服务上执行一次 cancel 操作，这样就空跑了一次回滚操作。

解决办法：

• 第一阶段 Try 方法里会插入一条记录（事务记录表），表示一阶段执行了。

• Cancel 接口里读取该记录，如果该记录存在，则正常回滚；如果该记录不存在，则是空回滚。

防悬挂控制：

在调用TCC服务的一阶段Try操作时，可能会出现因网络拥堵而导致的超时，此时触发二阶段回滚，调用TCC服务的Cancel操作；

在此之后，拥堵在网络上的一阶段Try数据包被TCC服务收到，出现了二阶段Cancel请求比一阶段Try请求先执行的情况；

解决思路：

• 如果二阶段执行完成，那一阶段就不能再继续执行。

• 在执行一阶段事务时判断在该全局事务下，事务记录表中是否已经有二阶段事务记录，如果有则不执行Try。