分布式调度面试

服务注册和发现

【基础】什么是服务注册和发现？

要点

服务定义是服务提供者和服务消费者之间的约定，但是在微服务架构中，如何达成这个约定呢？这就依赖于服务注册和发现机制。

在微服务架构下，服务注册和发现机制中主要有三种角色：

• 服务提供者（RPC Server / Provider）
• 服务消费者（RPC Client / Consumer）
• 服务注册中心（Registry）

服务发现通常依赖于注册中心来协调服务发现的过程，其步骤如下：

1. 服务提供者将接口信息以注册到注册中心。
2. 服务消费者从注册中心读取和订阅服务提供者的地址信息。
3. 如果有可用的服务，注册中心会主动通知服务消费者。
4. 服务消费者根据可用服务的地址列表，调用服务提供者的接口。

这个过程很像是生活中的房屋租赁，房东将租房信息挂到中介公司，房客从中介公司查找租房信息。房客如果想要租房东的房子，通过中介公司牵线搭桥，联系上房东，双方谈妥签订协议，就可以正式建立起租赁关系。

img

【中级】注册中心有哪些基本功能？

要点

从服务注册和发现的流程，可以看出，注册中心是服务发现的核心组件。常见的注册中心组件有：Nacos、Consul、Zookeeper 等。

注册中心的实现主要涉及几个问题：注册中心需要提供哪些接口，该如何部署；如何存储服务信息；如何监控服务提供者节点的存活；如果服务提供者节点有变化如何通知服务消费者，以及如何控制注册中心的访问权限。

元数据定义

构建微服务的首要问题是：服务提供者和服务消费者通信时，如何达成共识。具体来说，就是这个服务的接口名是什么？调用这个服务需要传递哪些参数？接口的返回值是什么类型？以及一些其他接口描述信息。

常见的定义服务元数据的方式有：

• XML 文件 - 如果只是企业内部之间的服务调用，并且都是 Java 语言的话，选择 XML 配置方式是最简单的。
• IDL 文件 - 如果企业内部存在多个跨语言服务，建议使用 IDL 文件方式进行描述服务。
• REST API - 如果存在对外开放服务调用的情形的话，使用 REST API 方式则更加通用。

元数据存储

注册中心本质上是一个用于保存元数据的分布式存储。你如果明白了这一点，就会了解实现一个注册中心的所有要点都是围绕这个目标去构建的。

想要构建微服务，首先要解决的问题是，服务提供者如何发布一个服务，服务消费者如何引用这个服务。具体来说，就是这个服务的接口名是什么？调用这个服务需要传递哪些参数？接口的返回值是什么类型？以及一些其他接口描述信息。

服务的元数据信息通常有以下信息：

• 服务节点信息，如 IP、端口等。
• 接口定义，如接口名、请求参数、响应参数等。
• 请求失败的重试次数
• 序列化方式
• 压缩方式
• 通信协议
• 等等

在具体存储时，注册中心一般会按照“服务 - 分组 - 节点信息”的层次化的结构来存储。

注册中心 API

既然是分布式存储，势必要提供支持读写数据的接口，也就是 API，一般来说，需要支持以下功能：

• 服务注册接口：服务提供者通过调用服务注册接口来完成服务注册。
• 服务反注册接口：服务提供者通过调用服务反注册接口来完成服务注销。
• 心跳汇报接口：服务提供者通过调用心跳汇报接口完成节点存活状态上报。
• 服务订阅接口：服务消费者通过调用服务订阅接口完成服务订阅，获取可用的服务提供者节点列表。
• 服务变更查询接口：服务消费者通过调用服务变更查询接口，获取最新的可用服务节点列表。

除此之外，为了便于管理，注册中心还必须提供一些后台管理的 API，例如：

• 服务查询接口：查询注册中心当前注册了哪些服务信息。
• 服务修改接口：修改注册中心中某一服务的信息。

服务健康检测

注册中心除了要支持最基本的服务注册和服务订阅功能以外，还必须具备对服务提供者节点的健康状态检测功能，这样才能保证注册中心里保存的服务节点都是可用的。注册中心通常使用长连接或心跳探测方式检查服务健康状态。

还是以 ZooKeeper 为例，它是基于 ZooKeeper 客户端和服务端的长连接和会话超时控制机制，来实现服务健康状态检测的。在 ZooKeeper 中，客户端和服务端建立连接后，会话也随之建立，并生成一个全局唯一的 Session ID。服务端和客户端维持的是一个长连接，在 SESSION_TIMEOUT 周期内，服务端会检测与客户端的链路是否正常，具体方式是通过客户端定时向服务端发送心跳消息（ping 消息），服务器重置下次 SESSION_TIMEOUT 时间。如果超过 SESSION_TIMEOUT 后服务端都没有收到客户端的心跳消息，则服务端认为这个 Session 就已经结束了，ZooKeeper 就会认为这个服务节点已经不可用，将会从注册中心中删除其信息。

服务状态变更通知

一旦注册中心探测到有服务提供者节点新加入或者被剔除，就必须立刻通知所有订阅该服务的服务消费者，刷新本地缓存的服务节点信息，确保服务调用不会请求不可用的服务提供者节点。注册中心通常基于服务状态订阅来实现服务状态变更通知。

继续以 ZooKeeper 为例，基于 ZooKeeper 的 Watcher 机制，来实现服务状态变更通知给服务消费者的。服务消费者在调用 ZooKeeper 的 getData 方法订阅服务时，还可以通过监听器 Watcher 的 process 方法获取服务的变更，然后调用 getData 方法来获取变更后的数据，刷新本地缓存的服务节点信息。

集群部署

注册中心作为服务提供者和服务消费者之间沟通的桥梁，它的重要性不言而喻。所以注册中心一般都是采用集群部署来保证高可用性，并通过分布式一致性协议来确保集群中不同节点之间的数据保持一致。根据 CAP 理论，三种特性无法同时达成，必须在可用性和一致性之间做取舍。于是，根据不同侧重点，注册中心可以分为 CP 和 AP 两个阵营：

• CP 型注册中心 - 牺牲可用性来换取数据强一致性，最典型的例子就是 ZooKeeper，etcd，Consul 了。ZooKeeper 集群内只有一个 Leader，而且在 Leader 无法使用的时候通过算法选举出一个新的 Leader。这个 Leader 的目的就是保证写信息的时候只向这个 Leader 写入，Leader 会同步信息到 Followers，这个过程就可以保证数据的强一致性。但如果多个 ZooKeeper 之间网络出现问题，造成出现多个 Leader，发生脑裂的话，注册中心就不可用了。而 etcd 和 Consul 集群内都是通过 Raft 协议来保证强一致性，如果出现脑裂的话， 注册中心也不可用。
• AP 型注册中心 - 牺牲一致性（只保证最终一致性）来换取可用性，最典型的例子就是 Eureka、Nacos 了。对比下 Zookeeper，Eureka 不用选举一个 Leader，每个 Eureka 服务器单独保存服务注册地址，因此有可能出现数据信息不一致的情况。但是当网络出现问题的时候，每台服务器都可以完成独立的服务。

【高级】注册中心有哪些扩展功能？

要点

多注册中心

对于服务消费者来说，要能够同时从多个注册中心订阅服务；

对于服务提供者来说，要能够同时向多个注册中心注册服务。

并行订阅服务

如果只支持串行订阅，如果服务消费者订阅的服务较多，并且某些服务节点的初始化连接过程中出现连接超时的情况，则后续所有的服务节点的初始化连接都需要等待它完成，这就会导致消费者启动非常慢。

可以每订阅一个服务就单独用一个线程来处理，这样的话即使遇到个别服务节点连接超时，其他服务节点的初始化连接也不受影响，最慢也就是这个服务节点的初始化连接耗费的时间，最终所有服务节点的初始化连接耗时控制在了 30 秒以内。

批量注销服务

在与注册中心的多次交互中，可能由于网络抖动、注册中心集群异常等原因，导致个别调用失败。对于注册中心来说，偶发的注册调用失败对服务调用基本没有影响，其结果顶多就是某一个服务少了一个可用的节点。但偶发的反注册调用失败会导致不可用的节点残留在注册中心中，变成“僵尸节点”。

需要定时去清理注册中心中的“僵尸节点”，如果支持批量注销服务，就可以一次调用就把该节点上提供的所有服务同时注销掉。

服务变更信息增量更新

为了减少服务消费者从注册中心中拉取的服务可用节点信息的数据量，这个时候可以通过增量更新的方式，注册中心只返回变化的那部分节点信息。尤其在只有少数节点信息变更时，此举可以大大减少服务消费者从注册中心拉取的数据量，从而最大程度避免产生网络风暴。

心跳开关保护机制

在网络频繁抖动的情况下，注册中心中可用的节点会不断变化，这时候服务消费者会频繁收到服务提供者节点变更的信息，于是就不断地请求注册中心来拉取最新的可用服务节点信息。当有成百上千个服务消费者，同时请求注册中心获取最新的服务提供者的节点信息时，可能会把注册中心的带宽给占满，尤其是注册中心是百兆网卡的情况下。

所以针对这种情况，需要一种保护机制，即使在网络频繁抖动的时候，服务消费者也不至于同时去请求注册中心获取最新的服务节点信息。

我曾经就遇到过这种情况，一个可行的解决方案就是给注册中心设置一个开关，当开关打开时，即使网络频繁抖动，注册中心也不会通知所有的服务消费者有服务节点信息变更，比如只给 10% 的服务消费者返回变更，这样的话就能将注册中心的请求量减少到原来的 1/10。

当然打开这个开关也是有一定代价的，它会导致服务消费者感知最新的服务节点信息延迟，原先可能在 10s 内就能感知到服务提供者节点信息的变更，现在可能会延迟到几分钟，所以在网络正常的情况下，开关并不适合打开；可以作为一个紧急措施，在网络频繁抖动的时候，才打开这个开关。

服务节点摘除保护机制

服务提供者在进程启动时，会注册服务到注册中心，并每隔一段时间，汇报心跳给注册中心，以标识自己的存活状态。如果隔了一段固定时间后，服务提供者仍然没有汇报心跳给注册中心，注册中心就会认为该节点已经处于“dead”状态，于是从服务的可用节点信息中移除出去。

如果遇到网络问题，大批服务提供者节点汇报给注册中心的心跳信息都可能会传达失败，注册中心就会把它们都从可用节点列表中移除出去，造成剩下的可用节点难以承受所有的调用，引起“雪崩”。但是这种情况下，可能大部分服务提供者节点是可用的，仅仅因为网络原因无法汇报心跳给注册中心就被“无情”的摘除了。

这个时候就需要根据实际业务的情况，设定一个阈值比例，即使遇到刚才说的这种情况，注册中心也不能摘除超过这个阈值比例的节点。

这个阈值比例可以根据实际业务的冗余度来确定，我通常会把这个比例设定在 20%，就是说注册中心不能摘除超过 20% 的节点。因为大部分情况下，节点的变化不会这么频繁，只有在网络抖动或者业务明确要下线大批量节点的情况下才有可能发生。而业务明确要下线大批量节点的情况是可以预知的，这种情况下可以关闭阈值保护；而正常情况下，应该打开阈值保护，以防止网络抖动时，大批量可用的服务节点被摘除。

白名单机制

在实际的微服务测试和部署时，通常包含多套环境，比如生产环境一套、测试环境一套。开发在进行业务自测、测试在进行回归测试时，一般都是用测试环境，部署的 RPC Server 节点注册到测试的注册中心集群。但经常会出现开发或者测试在部署时，错误的把测试环境下的服务节点注册到了线上注册中心集群，这样的话线上流量就会调用到测试环境下的 RPC Server 节点，可能会造成意想不到的后果。

为了防止这种情况发生，注册中心需要提供一个保护机制，你可以把注册中心想象成一个带有门禁的房间，只有拥有门禁卡的 RPC Server 才能进入。在实际应用中，注册中心可以提供一个白名单机制，只有添加到注册中心白名单内的 RPC Server，才能够调用注册中心的注册接口，这样的话可以避免测试环境中的节点意外跑到线上环境中去。

静态注册中心

因为服务提供者是向服务消费者提供服务的，服务是否可用，服务消费者应该比注册中心更清楚。因此，可以直接在服务消费者端，根据调用服务提供者是否成功来判定服务提供者是否可用。如果服务消费者调用某一个服务提供者节点连续失败超过一定次数，可以在本地内存中将这个节点标记为不可用。并且每隔一段固定时间，服务消费者都要向标记为不可用的节点发起保活探测，如果探测成功了，就将标记为不可用的节点再恢复为可用状态，重新发起调用。

负载均衡

【基础】什么是负载均衡？为什么需要负载均衡？

要点

“负载均衡（Load Balance，简称 LB）”是一种技术，用来在多个计算机、网络连接、CPU、磁盘驱动器或其他资源中分配负载，以达到优化资源利用率、最大化吞吐率、最小化响应时间、同时避免过载的目的。

负载均衡的主要作用如下：

• 高并发：负载均衡可以优化资源使用率，通过算法调整负载，尽力均匀的分配资源，以此提高资源利用率、从而提升整体吞吐量。
• 伸缩性：发生增减资源时，负载均衡可以自动调整分发，使得应用集群具备伸缩性。
• 高可用：负载均衡器可以监控候选机器，当某机器不可用时，自动跳过，将请求分发给可用的机器。这使得应用集群具备高可用的特性。
• 安全防护：有些负载均衡软件或硬件提供了安全性功能，如：黑白名单、防火墙，防 DDos 攻击等。

【中级】负载均衡技术有哪些分类？

要点

支持负载均衡的技术很多，我们可以通过不同维度去进行分类。

载体维度分类

从支持负载均衡的载体来看，可以将负载均衡分为两类：

• 硬件负载均衡
• 软件负载均衡

硬件负载均衡

硬件负载均衡，一般是在定制处理器上运行的独立负载均衡服务器，价格昂贵，土豪专属。

硬件负载均衡的主流产品有：F5 和 A10。

硬件负载均衡的优点：

• 功能强大：支持全局负载均衡并提供较全面的、复杂的负载均衡算法。
• 性能强悍：硬件负载均衡由于是在专用处理器上运行，因此吞吐量大，可支持单机百万以上的并发。
• 安全性高：往往具备防火墙，防 DDos 攻击等安全功能。

硬件负载均衡的缺点：

• 成本昂贵：购买和维护硬件负载均衡的成本都很高。
• 扩展性差：当访问量突增时，超过限度不能动态扩容。

软件负载均衡

软件负载均衡，应用最广泛，无论大公司还是小公司都会使用。

软件负载均衡从软件层面实现负载均衡，一般可以在任何标准物理设备上运行。

软件负载均衡的 主流产品 有：Nginx、HAProxy、LVS。

• LVS 可以作为四层负载均衡器。其负载均衡的性能要优于 Nginx。
• HAProxy 可以作为 HTTP 和 TCP 负载均衡器。
• Nginx、HAProxy 可以作为四层或七层负载均衡器。

软件负载均衡的 优点：

• 扩展性好：适应动态变化，可以通过添加软件负载均衡实例，动态扩展到超出初始容量的能力。
• 成本低廉：软件负载均衡可以在任何标准物理设备上运行，降低了购买和运维的成本。

软件负载均衡的 缺点：

• 性能略差：相比于硬件负载均衡，软件负载均衡的性能要略低一些。

网络通信分类

软件负载均衡从通信层面来看，又可以分为四层和七层负载均衡。

• 七层负载均衡：就是可以根据访问用户的 HTTP 请求头、URL 信息将请求转发到特定的主机。
  • DNS 重定向
  • HTTP 重定向
  • 反向代理
• 四层负载均衡：基于 IP 地址和端口进行请求的转发。
  • 修改 IP 地址
  • 修改 MAC 地址

DNS 负载均衡

DNS 负载均衡一般用于互联网公司，复杂的业务系统不适合使用。大型网站一般使用 DNS 负载均衡作为 第一级负载均衡手段，然后在内部使用其它方式做第二级负载均衡。DNS 负载均衡属于七层负载均衡。

DNS 即 域名解析服务，是 OSI 第七层网络协议。DNS 被设计为一个树形结构的分布式应用，自上而下依次为：根域名服务器，一级域名服务器，二级域名服务器，... ，本地域名服务器。显然，如果所有数据都存储在根域名服务器，那么 DNS 查询的负载和开销会非常庞大。

因此，DNS 查询相对于 DNS 层级结构，是一个逆向的递归流程，DNS 客户端依次请求本地 DNS 服务器，上一级 DNS 服务器，上上一级 DNS 服务器，... ，根 DNS 服务器（又叫权威 DNS 服务器），一旦命中，立即返回。为了减少查询次数，每一级 DNS 服务器都会设置 DNS 查询缓存。

DNS 负载均衡的工作原理就是：基于 DNS 查询缓存，按照负载情况返回不同服务器的 IP 地址。

img

DNS 重定向的 优点：

• 使用简单：负载均衡工作，交给 DNS 服务器处理，省掉了负载均衡服务器维护的麻烦
• 提高性能：可以支持基于地址的域名解析，解析成距离用户最近的服务器地址（类似 CDN 的原理），可以加快访问速度，改善性能；

DNS 重定向的 缺点：

• 可用性差：DNS 解析是多级解析，新增/修改 DNS 后，解析时间较长；解析过程中，用户访问网站将失败；
• 扩展性差：DNS 负载均衡的控制权在域名商那里，无法对其做更多的改善和扩展；
• 维护性差：也不能反映服务器的当前运行状态；支持的算法少；不能区分服务器的差异（不能根据系统与服务的状态来判断负载）

HTTP 负载均衡

HTTP 负载均衡是基于 HTTP 重定向实现的。HTTP 负载均衡属于七层负载均衡。

HTTP 重定向原理是：根据用户的 HTTP 请求计算出一个真实的服务器地址，将该服务器地址写入 HTTP 重定向响应中，返回给浏览器，由浏览器重新进行访问。

img

HTTP 重定向的 优点：方案简单。

HTTP 重定向的 缺点：

• 额外的转发开销：每次访问需要两次请求服务器，增加了访问的延迟。
• 降低搜索排名：使用重定向后，搜索引擎会视为 SEO 作弊。
• 如果负载均衡器宕机，就无法访问该站点。

由于其缺点比较明显，所以这种负载均衡策略实际应用较少。

反向代理负载均衡

反向代理（Reverse Proxy）方式是指以 代理服务器 来接受网络请求，然后 将请求转发给内网中的服务器，并将从内网中的服务器上得到的结果返回给网络请求的客户端。反向代理负载均衡属于七层负载均衡。

反向代理服务的主流产品：Nginx、Apache。

正向代理与反向代理有什么区别？

• 正向代理：发生在 客户端，是由用户主动发起的。翻墙软件就是典型的正向代理，客户端通过主动访问代理服务器，让代理服务器获得需要的外网数据，然后转发回客户端。
• 反向代理：发生在 服务端，用户不知道代理的存在。

img

反向代理是如何实现负载均衡的呢？以 Nginx 为例，如下所示：

img

首先，在代理服务器上设定好负载均衡规则。然后，当收到客户端请求，反向代理服务器拦截指定的域名或 IP 请求，根据负载均衡算法，将请求分发到候选服务器上。其次，如果某台候选服务器宕机，反向代理服务器会有容错处理，比如分发请求失败 3 次以上，将请求分发到其他候选服务器上。

反向代理的 优点：

• 多种负载均衡算法：支持多种负载均衡算法，以应对不同的场景需求。
• 可以监控服务器：基于 HTTP 协议，可以监控转发服务器的状态，如：系统负载、响应时间、是否可用、连接数、流量等，从而根据这些数据调整负载均衡的策略。

反向代理的 缺点：

• 额外的转发开销：反向代理的转发操作本身是有性能开销的，可能会包括创建连接，等待连接响应，分析响应结果等操作。

• 增加系统复杂度：反向代理常用于做分布式应用的水平扩展，但反向代理服务存在以下问题，为了解决以下问题会给系统整体增加额外的复杂度和运维成本：

• 反向代理服务如果自身宕机，就无法访问站点，所以需要有 高可用 方案，常见的方案有：主备模式（一主一备）、双主模式（互为主备）。

  • 反向代理服务自身也存在性能瓶颈，随着需要转发的请求量不断攀升，需要有 可扩展 方案。

IP 负载均衡

IP 负载均衡是在网络层通过修改请求目的地址进行负载均衡。

img

如上图所示，IP 均衡处理流程大致为：

1. 客户端请求 192.168.137.10，由负载均衡服务器接收到报文。
2. 负载均衡服务器根据算法选出一个服务节点 192.168.0.1，然后将报文请求地址改为该节点的 IP。
3. 真实服务节点收到请求报文，处理后，返回响应数据到负载均衡服务器。
4. 负载均衡服务器将响应数据的源地址改负载均衡服务器地址，返回给客户端。

IP 负载均衡在内核进程完成数据分发，较反向代理负载均衡有更好的处理性能。但是，由于所有请求响应都要经过负载均衡服务器，集群的吞吐量受制于负载均衡服务器的带宽。

数据链路层负载均衡

数据链路层负载均衡是指在通信协议的数据链路层修改 mac 地址进行负载均衡。

img

在 Linux 平台上最好的链路层负载均衡开源产品是 LVS (Linux Virtual Server)。

LVS 是基于 Linux 内核中 netfilter 框架实现的负载均衡系统。netfilter 是内核态的 Linux 防火墙机制，可以在数据包流经过程中，根据规则设置若干个关卡（hook 函数）来执行相关的操作。

LVS 的工作流程大致如下：

• 当用户访问 www.sina.com.cn 时，用户数据通过层层网络，最后通过交换机进入 LVS 服务器网卡，并进入内核网络层。
• 进入 PREROUTING 后经过路由查找，确定访问的目的 VIP 是本机 IP 地址，所以数据包进入到 INPUT 链上
• IPVS 是工作在 INPUT 链上，会根据访问的 vip+port 判断请求是否 IPVS 服务，如果是则调用注册的 IPVS HOOK 函数，进行 IPVS 相关主流程，强行修改数据包的相关数据，并将数据包发往 POSTROUTING 链上。
• POSTROUTING 上收到数据包后，根据目标 IP 地址（后端服务器），通过路由选路，将数据包最终发往后端的服务器上。

开源 LVS 版本有 3 种工作模式，每种模式工作原理截然不同，说各种模式都有自己的优缺点，分别适合不同的应用场景，不过最终本质的功能都是能实现均衡的流量调度和良好的扩展性。主要包括三种模式：DR 模式、NAT 模式、Tunnel 模式。

【高级】负载均衡有哪些算法？

要点

负载均衡器的实现可以分为两个部分：

• 根据负载均衡算法在候选机器列表选出一个机器；
• 将请求数据发送到该机器上。

负载均衡算法是负载均衡服务核心中的核心。负载均衡产品多种多样，但是各种负载均衡算法原理是共性的。

负载均衡算法有很多种，分别适用于不同的应用场景。本章节将由浅入深的，逐一讲解各种负载均衡算法的策略和特性，并根据算法之间的互补关系将它们串联起来。

注：负载均衡算法的实现，推荐阅读 Dubbo 官方负载均衡算法说明 ，源码讲解非常详细，非常值得借鉴。

下文中的各种算法的可执行示例已归档在 Github 仓库：java-load-balance，可以通过执行 io.github.dunwu.javatech.LoadBalanceDemo 查看各算法执行效果。

轮询算法

“轮询算法（Round Robin）”的策略是：将请求“依次”分发到候选机器。

如下图所示，轮询负载均衡器收到来自客户端的 6 个请求，编号为 1、4 的请求会被发送到服务端 0；编号为 2、5 的请求会被发送到服务端 1；编号为 3、6 的请求会被发送到服务端 2。

img

轮询算法适合的场景需要满足：各机器处理能力相近，且每个请求工作量差异不大。

随机算法

“随机算法（Random）” 将请求“随机”分发到候选机器。

如下图所示，随机负载均衡器收到来自客户端的 6 个请求，会随机分发请求，可能会出现：编号为 1、5 的请求会被发送到服务端 0；编号为 2、4 的请求会被发送到服务端 1；编号为 3、6 的请求会被发送到服务端 2。

img

随机算法适合的场景需要满足：各机器处理能力相近，且每个请求工作量差异不大。

学习过概率论的都知道，调用量较小的时候，可能负载并不均匀，调用量越大，负载越均衡。

加权轮询/随机算法

轮询/随机算法适合的场景都需要满足：各机器处理能力相近，且每个请求工作量差异不大。

在理想状况下，假设每个机器的硬件条件相同，如：CPU、内存、网络 IO 等配置都相同；并且每个请求的耗时一样（请求传输时间、请求访问数据时间、计算时间等），这时轮询算法才能真正做到负载均衡。显然，要满足以上条件都相同是几乎不可能的，更不要说实际的网络通信中还有更多复杂的情况。

以上，如果有一点不能满足，都无法做到真正的负载均衡。个体存在较大差异，当请求量较大时，处理较慢的机器可能会逐渐积压请求，从而导致过载甚至宕机。

如下图所示，假设存在这样的场景：

• 服务端 1 的处理能力远低于服务端 0 和服务端 2；
• 轮询/随机算法可以保证将请求尽量均匀的分发给两个机器；
• 编号为 1、4 的请求被发送到服务端 0；编号为 3、6 的请求被发送到服务端 2；二者处理能力强，应对游刃有余；
• 编号为 2、5 的请求被发送到服务端 1，服务端 1 处理能力弱，应对捉襟见肘，导致过载。

img

《蜘蛛侠》电影中有一句经典台词：能力越大，责任越大。显然，以上情况不符合这句话，处理能力强的机器并没有被分发到更多的请求，它的处理能力被闲置了。那么，如何解决这个问题呢？

一种比较容易想到的思路是：引入权重属性，可以根据机器的硬件条件为其设置合理的权重值，负载均衡时，优先将请求分发到权重较高的机器。

“加权轮询算法（Weighted Round Robbin）” 和“加权随机算法（Weighted Random）” 都采用了加权的思路，在轮询/随机算法的基础上，引入了权重属性，优先将请求分发到权重较高的机器。这样，就可以针对性能高、处理速度快的机器设置较高的权重，让其处理更多的请求；而针对性能低、处理速度慢的机器则与之相反。一言以蔽之，加权策略强调了——能力越大，责任越大。

如下图所示，服务端 0 设置权重为 3，服务端 1 设置权重为 1，服务端 2 设置权重为 2。负载均衡器收到来自客户端的 6 个请求，那么编号为 1、2、5 的请求会被发送到服务端 0，编号为 4 的请求会被发送到服务端 1，编号为 3、6 的请求会被发送到机器 2。

img

最少连接数算法

加权轮询/随机算法虽然一定程度上解决了机器处理能力不同时的负载均衡场景，但它最大的问题在于不能动态应对网络中负载不均的场景。加权的思路是在负载均衡处理的事前，预设好不同机器的权重，然后分发。然而，每个请求的连接时长不同，负载均衡器也不可能准确预估出请求的连接时长。因此，采用加权轮询/随机算法算法，都无法动态应对连接时长不均的网络场景，可能会出现某些机器当前连接数过多，而另一些机器的连接过少的情况，即并非真正的流量负载均衡。

如下图所示，假设存在这样的场景：

• 3 个服务端的处理能力相同；
• 编号为 1、4 的请求被发送到服务端 0，但是 1 很快就断开连接，此时只有 4 请求连接服务端 0；
• 编号为 2、5 的请求被发送到服务端 1，但是 2 始终保持长连接；该系统继续运行时，服务端 1 发生过载；
• 编号为 3、6 的请求被发送到服务端 2，但是 3 很快就断开连接，此时只有 6 请求连接服务端 2；

img

既然，请求的连接时长不同，会导致有的服务端处理慢，积压大量连接数；而有的服务端处理快，保持的连接数少。那么，我们不妨想一下，如果负载均衡器监控一下服务端当前所持有的连接数，优先将请求分发给连接数少的服务端，不就能有效提高分发效率了吗？最少连接数算法正是采用这个思路去设计的。

“最少连接数算法（Least Connections）” 将请求分发到连接数/请求数最少的候选机器。

要根据机器连接数分发，显然要先维护机器的连接数。因此，最少连接数算法需要实时追踪每个候选机器的活跃连接数；然后，动态选出连接数最少的机器，优先分发请求。最少连接数算法会记录当前时刻，每个候选节点正在处理的连接数，然后选择连接数最小的节点。该策略能够动态、实时地反应机器的当前状况，较为合理地将负责分配均匀，适用于对当前系统负载较为敏感的场景。

由此可见，最少连接数算法适用于对系统负载较为敏感且请求连接时长相差较大的场景。

如下图所示，假设存在这样的场景：

• 服务端 0 和服务端 1 的处理能力相同；
• 编号为 1、3 的请求被发送到服务端 0，但是 1、3 很快就断开连接；
• 编号为 2、4 的请求被发送到服务端 1，但是 2、4 保持长连接；
• 由于服务端 0 当前连接数最少，编号为 5、6 的请求被分发到服务端 0。

img

“加权最少连接数算法（Weighted Least Connection）”在最少连接数算法的基础上，根据机器的性能为每台机器分配权重，再根据权重计算出每台机器能处理的连接数。

最少响应时间算法

“最少响应时间算法（Least Time）” 将请求分发到响应时间最短的候选机器。最少响应时间算法和最少连接数算法二者的目标其实是殊途同归，都是动态调整，将请求尽量分发到处理能力强的机器上。不同点在于，最少连接数关注的维度是机器持有的连接数，而最少响应时间关注的维度是机器上一次响应时间哪个最短。理论上来说，持有的连接数少，响应时间短，都可以表明机器潜在的处理能力比较强。

最少响应时间算法具有高度的敏感性、自适应性。但是，由于它需要持续监控候选机器的响应时延，相比于监控候选机器的连接数，会显著增加监控的开销。此外，请求的响应时延并不一定能完全反应机器的处理能力，有可能某机器上一次处理的请求恰好是一个开销非常小的请求。

img

哈希算法

前面提到的负载均衡算法，都只适用于无状态应用。所谓无状态应用，意味着：请求无论分发到集群中的任意机器上，得到的响应都是相同的：然而，有状态服务则不然：请求分发到不同的机器上，得到的结果是不一样的。典型的无状态应用是普通的 Web 服务器；典型的有状态应用是各种分布式数据库（如：Redis、ElasticSearch 等），这些数据库存储了大量，乃至海量的数据，无法全部存储在一台机器上，为了提高整体容量以及吞吐量，采用了分区（分片）的设计，将数据化整为零的存储在不同机器上。

对于有状态应用，不仅仅需要保证负载的均衡，更为重要的是，需要保证针对相同数据的请求始终访问的是相同的机器，否则，就无法获取到正确的数据。

那么，如何解决有状态应用的负载均衡呢？有一种方案是哈希算法。

“哈希算法（Hash）” 根据一个 key （可以是唯一 ID、IP、URL 等），通过哈希函数计算得到一个数值，用该数值在候选机器列表的进行取模运算，得到的结果便是选中的机器。

img

这种算法可以保证，同一关键字（IP 或 URL 等）的请求，始终会被转发到同一台机器上。哈希负载均衡算法常被用于实现会话粘滞（Sticky Session）。

但是 ，哈希算法的问题是：当增减节点时，由于哈希取模函数的基数发生变化，会影响大部分的映射关系，从而导致之前的数据不可访问。要解决这个问题，就必须根据新的计算公式迁移数据。显然，如果数据量很大的情况下，迁移成本很高；并且，在迁移过程中，要保证业务平滑过渡，需要使用数据双写等较为复杂的技术手段。

img

一致性哈希算法

哈希算法的缺点是：当集群中出现增减节点时，由于哈希取模函数的基数发生变化，会导致大量集群中的机器不可用；需要通过代价高昂的数据迁移，来解决问题。那么，我们自然会希望有一种更优化的方案，来尽量减少影响的机器数。一致性哈希算法就是为了这个目标而应运而生。

一致性哈希算法对哈希算法进行了改良。“一致性哈希算法（Consistent Hash）”，根据哈希算法将对应的 key 哈希到一个具有 2^32 个桶的空间，并且头尾相连（0 到 2^32-1），即一个闭合的环形，这个圆环被称为“哈希环”。哈希算法是对节点的数量进行取模运算；而一致性哈希算法则是对 2^32 进行取模运算。

哈希环的空间是按顺时针方向组织的，需要对指定 key 的数据进行读写时，会执行两步：

1. 先对节点进行哈希计算，计算的关键字通常是 IP 或其他唯一标识（例：hash(ip)），然后对 2^32 取模，以确定节点在哈希环上的位置。
2. 先对 key 进行哈希计算（hash(key)），然后对 2^32 取模，以确定 key 在哈希环上的位置。
3. 然后根据 key 的位置，顺时针找到的第一个节点，就是 key 对应的节点。

所以，一致性哈希是将“存储节点”和“数据”都映射到一个顺时针排序的哈希环上。

img

一致性哈希算法会尽可能保证，相同的请求被分发到相同的机器上。当出现增减节点时，只影响哈希环中顺时针方向的相邻的节点，对其他节点无影响，不会引起剧烈变动。

• 相同的请求是指：一般在使用一致性哈希时，需要指定一个 key 用于 hash 计算，可能是：用户 ID、请求方 IP、请求服务名称，参数列表构成的串
• 尽可能是指：哈希环上出现增减节点时，少数机器的变化不应该影响大多数的请求。

（1）增加节点

如下图所示，假设，哈希环中新增了一个节点 S4，新增节点经过哈希计算映射到图中位置：

img

此时，只有 K1 收到影响；而 K0、K2 均不受影响。

（2）减少节点

如下图所示，假设，哈希环中减少了一个节点 S0：

img

此时，只有 K0 收到影响；而 K1、K2 均不受影响。

一致性哈希算法并不保证节点能够在哈希环上分布均匀，由此而产生一个问题，哈希环上可能有大量的请求集中在一个节点上。从概率角度来看，哈希环上的节点越多，分布就越均匀。正因为如此，一致性哈希算法不适用于节点数过少的场景。

如下图所示：极端情况下，可能由于节点在哈希环上分布不均，有大量请求计算得到的 key 会被集中映射到少数节点，甚至某一个节点上。此外，节点分布不均匀的情况下，进行容灾与扩容时，哈希环上的相邻节点容易受到过大影响，从而引发雪崩式的连锁反应。

img

虚拟一致性哈希算法

在一致性哈希算法中，如果节点数过少，可能会分布不均，从而导致负载不均衡。在实际生产环境中，一个分布式系统应该具备良好的伸缩性，既能从容的扩展到大规模的集群，也要能支持小规模的集群。为此，又产生了虚拟哈希算法，进一步对一致性哈希算法进行了改良。

虚拟哈希算法的解决思路是：虽然实际的集群可能节点数较少，但是在哈希环上引入大量的虚拟哈希节点。具体来说，“虚拟哈希算法”有二次映射：先将虚拟节点映射到哈希环上，再将虚拟节点映射到实际节点上。

如下图所示，假设存在这样的场景：

• 分布式集群中有 4 个真实节点，分别是：S0、S1、S2、S3；
• 我们不妨先假定分配给哈希环 12 个虚拟节点，并将虚拟节点映射到真实节点上，映射关系如下：
  • S0 - S0_0、S0_1、S0_2、S0_3
  • S1 - S1_0、S1_1、S1_2、S1_3
  • S2 - S2_0、S2_1、S2_2、S2_3
  • S3 - S3_0、S3_1、S3_2、S3_3

img

通过引入虚拟哈希节点，是的哈希环上的节点分布相对均匀了。举例来说，假如此时，某请求的 key 哈希取模后，先映射到哈希环的 [S3_2, S0_0]、[S3_0, S0_1]、[S3_1, S0_2] 这三个区间的任意一点；接下来的二次映射都会匹配到真实节点 S0。

在实际应用中，虚拟哈希节点数一般都比较大（例如：Redis 的虚拟哈希槽有 16384 个），较大的数量保证了虚拟哈希环上的节点分布足够均匀。

虚拟节点除了会提高节点的均衡度，还会提高系统的稳定性。当节点变化时，会有不同的节点共同分担系统的变化，因此稳定性更高。例如，当某个节点被移除时，分配给该节点的多个虚拟节点会被一并移除，而这些虚拟节点按顺时针方向的下一个虚拟节点，可能会对应不同的真实节点，即这些不同的真实节点共同分担了节点变化导致的压力。

此外，有了虚拟节点后，可以通过调整分配给真实节点的虚拟节点数，来达到设置权重一样的效果，使得负载均衡更加灵活。

综上所述，虚拟一致性哈希算法不仅适合硬件配置不同的节点的场景，而且适合节点规模会发生变化的场景。

流量控制

【基础】什么是流量控制？为什么需要流量控制？

要点

流量控制（Flow Control），根据流量、并发线程数、响应时间等指标，把随机到来的流量调整成合适的形状，即流量塑形。避免应用被瞬时的流量高峰冲垮，从而保障应用的高可用性。

复杂的分布式系统架构中的应用程序往往具有数十个依赖项，每个依赖项都会不可避免地在某个时刻失败。 如果主机应用程序未与这些外部故障隔离开来，则可能会被波及。

例如，对于依赖于 30 个服务的应用程序，假设每个服务的正常运行时间为 99.99％，则可以期望：

99.99³⁰ = 99.7％ 的正常运行时间

10 亿个请求中的 0.3％= 3,000,000 个失败

即使所有依赖项都具有出色的正常运行时间，每月也会有 2 个小时以上的停机时间。

然而，现实情况一般比这种估量情况更糟糕。

---

当一切正常时，整体系统如下所示：

img

图片来自 Hystrix Wiki

在分布式系统架构下，这些强依赖的子服务稳定与否对系统的影响非常大。但是，依赖的子服务可能有很多不可控问题：如网络连接、资源繁忙、服务宕机等。例如：下图中有一个 QPS 为 50 的依赖服务 I 出现不可用，但是其他依赖服务是可用的。

img

图片来自 Hystrix Wiki

当流量很大的情况下，某个依赖的阻塞，会导致上游服务请求被阻塞。当这种级联故障愈演愈烈，就可能造成整个线上服务不可用的雪崩效应，如下图。这种情况若持续恶化，如果上游服务本身还被其他服务所依赖，就可能出现多米洛骨牌效应，导致多个服务都无法正常工作。

img

图片来自 Hystrix Wiki

【基础】流量控制有哪些衡量指标？

要点

【中级】流量控制有哪些保护机制？

要点

流量控制常见的手段就是限流、熔断、降级。

什么是降级？

降级是保障服务能够稳定运行的一种保护方式：面对突增的流量，牺牲一些吞吐量以换取系统的稳定。常见的降级实现方式有：开关降级、限流降级、熔断降级。

什么是限流？

限流一般针对下游服务，当上游流量较大时，避免被上游服务的请求撑爆。

限流就是限制系统的输入和输出流量，以达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。

限流规则包含三个部分：时间粒度，接口粒度，最大限流值。限流规则设置是否合理直接影响到限流是否合理有效。

什么是熔断？

熔断一般针对上游服务，当下游服务超时/异常较多时，避免被下游服务拖垮。

当调用链路中某个资源出现不稳定，例如，超时异常比例升高的时候，则对这个资源的调用进行限制，并让请求快速失败，避免影响到其它的资源，最终产生雪崩的效果。

熔断尽最大的可能去完成所有的请求，容忍一些失败，熔断也能自动恢复。熔断的常见策略有：

• 在每秒请求异常数超过多少时触发熔断降级
• 在每秒请求异常错误率超过多少时触发熔断降级
• 在每秒请求平均耗时超过多少时触发熔断降级

流量控制有哪些衡量指标

要点

流量控制有以下几个角度：

• 流量指标，例如 QPS、并发线程数等。
• 资源的调用关系，例如资源的调用链路，资源和资源之间的关系，调用来源等。
• 控制效果，例如排队等待、直接拒绝、Warm Up（预热）等。

【中级】流量控制有哪些隔离模式？

要点

线程池隔离

信号量隔离

资源隔离

【高级】有哪些限流算法？

要点

常见的限流算法有：固定窗口限流算法、滑动窗口限流算法、漏桶限流算法、令牌桶限流算法。

固定窗口限流算法

固定窗口限流算法的原理

固定窗口限流算法的基本策略是：

1. 设置一个固定时间窗口，以及这个固定时间窗口内的最大请求数；
2. 为每个固定时间窗口设置一个计数器，用于统计请求数；
3. 一旦请求数超过最大请求数，则请求会被拦截。

img

固定窗口限流算法的利弊

固定窗口限流算法的优点是：实现简单。

固定窗口限流算法的缺点是：存在临界问题。所谓临界问题，是指：流量分别集中在一个固定时间窗口的尾部和一个固定时间窗口的头部。举例来说，假设限流规则为每分钟不超过 100 次请求。在第一个时间窗口中，起初没有任何请求，在最后 1 s，收到 100 次请求，由于没有达到阈值，所有请求都通过；在第二个时间窗口中，第 1 秒就收到 100 次请求，而后续没有任何请求。虽然，这两个时间窗口内的流量都符合限流要求，但是在两个时间窗口临界的这 2s 内，实际上有 200 次请求，显然是超过预期吞吐量的，存在压垮系统的可能。

img

滑动窗口限流算法

滑动窗口限流算法的原理

滑动窗口限流算法是对固定窗口限流算法的改进，解决了临界问题。

滑动窗口限流算法的基本策略是：

• 将固定时间窗口分片为多个子窗口，每个子窗口的访问次数独立统计；
• 当请求时间大于当前子窗口的最大时间时，则将当前子窗口废弃，并将计时窗口向前滑动，并将下一个子窗口置为当前窗口。
• 要保证所有子窗口的统计数之和不能超过阈值。

滑动窗口限流算法就是针对固定窗口限流算法的更细粒度的控制，分片越多，则限流越精准。

img

滑动窗口限流算法的利弊

滑动窗口限流算法的优点是：在滑动窗口限流算法中，临界位置的突发请求都会被算到时间窗口内，因此可以解决计数器算法的临界问题。

滑动窗口限流算法的缺点是：

• 额外的内存开销 - 滑动时间窗口限流算法的时间窗口是持续滑动的，并且除了需要一个计数器来记录时间窗口内接口请求次数之外，还需要记录在时间窗口内每个接口请求到达的时间点，所以存在额外的内存开销。
• 限流的控制粒度受限于窗口分片粒度 - 滑动窗口限流算法，只能在选定的时间粒度上限流，对选定时间粒度内的更加细粒度的访问频率不做限制。但是，由于每个分片窗口都有额外的内存开销，所以也并不是分片数越多越好的。

漏桶限流算法

漏桶限流算法的原理

漏桶限流算法的基本策略是：

• 水（请求）以任意速率由入口进入到漏桶中；
• 水以固定的速率由出口出水（请求通过）；
• 漏桶的容量是固定的，如果水的流入速率大于流出速率，最终会导致漏桶中的水溢出（这意味着请求拒绝）。

img

漏桶限流算法的利弊

漏桶限流算法的优点是：流量速率固定——即无论流量多大，即便是突发的大流量，处理请求的速度始终是固定的。

漏桶限流算法的缺点是：不能灵活的调整流量。例如：一个集群通过增减节点的方式，弹性伸缩了其吞吐能力，漏桶限流算法无法随之调整。

漏桶策略适用于间隔性突发流量且流量不用即时处理的场景。

令牌桶限流算法

令牌桶限流算法的原理

img

令牌桶算法的原理：

1. 接口限制 T 秒内最大访问次数为 N，则每隔 T/N 秒会放一个 token 到桶中
2. 桶内最多存放 M 个 token，如果 token 到达时令牌桶已经满了，那么这个 token 就会被丢弃
3. 接口请求会先从令牌桶中取 token，拿到 token 则处理接口请求，拿不到 token 则进行限流处理

令牌桶限流算法的利弊

因为令牌桶存放了很多令牌，那么大量的突发请求会被执行，但是它不会出现临界问题，在令牌用完之后，令牌是以一个恒定的速率添加到令牌桶中的，因此不能再次发送大量突发请求。

规定固定容量的桶，token 以固定速度往桶内填充，当桶满时 token 不会被继续放入，每过来一个请求把 token 从桶中移除，如果桶中没有 token 不能请求。

令牌桶算法适用于有突发特性的流量，且流量需要即时处理的场景。

扩展

Guava 的 RateLimiter 工具类就是基于令牌桶算法实现，其源码分析可以参考：RateLimiter 基于漏桶算法，但它参考了令牌桶算法

网关路由

【基础】什么是服务路由？路由有什么用？

要点

服务路由是指通过一定的规则从集群中选择合适的节点。

负载均衡的作用和服务路由的功能看上去很近似，二者有什么区别呢？

负载均衡的目标是提供服务分发而不是解决路由问题，常见的静态、动态负载均衡算法无法实现精细化的路由管理，但是负载均衡也可以简单看做是路由方案的一种。

服务路由通常用于以下场景，目的在于实现流量隔离：

• 分组调用：一般来讲，为了保证服务的高可用性，实现异地多活的需求，一个服务往往不止部署在一个数据中心，而且出于节省成本等考虑，有些业务可能不仅在私有机房部署，还会采用公有云部署，甚至采用多家公有云部署。服务节点也会按照不同的数据中心分成不同的分组，这时对于服务消费者来说，选择哪一个分组调用，就必须有相应的路由规则。
• 蓝绿发布：蓝绿发布场景中，一共有两套服务群组：一套是提供旧版功能的服务群组，标记为绿色；另一套是提供新版功能的服务群组，标记为蓝色。两套服务群组都是功能完善的，并且正在运行的系统，只是服务版本和访问流量不同。新版群组（蓝色）通常是为了做内部测试、验收，不对外部用户暴露。
  • 如果新版群组（蓝色）运行稳定，并测试、验收通过后，则通过服务路由、负载均衡等手段逐步将外部用户流量导向新版群组（蓝色）。
  • 如果新版群组（蓝色）运行不稳定，或测试、验收不通过，则排查、解决问题后，再继续测试、验收。
• 灰度发布：灰度发布（又名金丝雀发布）是指在黑与白之间，能够平滑过渡的一种发布方式。在其上可以进行 A/B 测试，即让一部分用户使用特性 A，一部分用户使用特性 B：如果用户对 B 没有什么反对意见，那么逐步扩大发布范围，直到把所有用户都迁移到 B 上面来。灰度发布可以保证整体系统的稳定，在初始灰度的时候就可以发现、调整问题，以保证其影响度。要支持灰度发布，就要求服务能够根据一定的规则，将流量隔离。
• 流量切换：在业务线上运行过程中，经常会遇到一些不可抗力因素导致业务故障，比如某个机房的光缆被挖断，或者发生着火等事故导致整个机房的服务都不可用。这个时候就需要按照某个指令，能够把原来调用这个机房服务的流量切换到其他正常的机房。
• 线下测试联调：线下测试时，可能会缺少相应环境。可以将测试应用注册到线上，然后开启路由规则，在本地进行测试。
• 读写分离。对于大多数互联网业务来说都是读多写少，所以在进行服务部署的时候，可以把读写分开部署，所有写接口可以部署在一起，而读接口部署在另外的节点上。

服务路由有哪些常见规则？

要点

条件路由

条件路由是基于条件表达式的路由规则。各个 RPC 框架的条件路由表达式各不相同。

我们不妨参考一下 Dubbo 的条件路由。Dubbo 的条件路由有两种配置粒度，如下：

• 应用粒度

  # app1 的消费者只能消费所有端口为 20880 的服务实例
  # app2 的消费者只能消费所有端口为 20881 的服务实例
  ---
  scope: application
  force: true
  runtime: true
  enabled: true
  key: governance-conditionrouter-consumer
  conditions:
    - application=app1 => address=*:20880
    - application=app2 => address=*:20881
  

• 服务粒度

  # DemoService 的 sayHello 方法只能消费所有端口为 20880 的服务实例
  # DemoService 的 sayHi 方法只能消费所有端口为 20881 的服务实例
  ---
  scope: service
  force: true
  runtime: true
  enabled: true
  key: org.apache.dubbo.samples.governance.api.DemoService
  conditions:
    - method=sayHello => address=*:20880
    - method=sayHi => address=*:20881
  

其中，conditions 定义具体的路由规则内容。conditions 部分是规则的主体，由 1 到任意多条规则组成。详见：Dubbo 路由规则

Dubbo 的条件路由规则由两个条件组成，分别用于对服务消费者和提供者进行匹配。条件路由规则的格式如下：

[服务消费者匹配条件] => [服务提供者匹配条件]

• 服务消费者匹配条件：所有参数和消费者的 URL 进行对比，当消费者满足匹配条件时，对该消费者执行后面的过滤规则。
• 服务提供者匹配条件：所有参数和提供者的 URL 进行对比，消费者最终只拿到过滤后的地址列表。

condition:// 代表了这是一段用条件表达式编写的路由规则，下面是一个条件路由规则示例：

host = 10.20.153.10 => host = 10.20.153.11

该条规则表示 IP 为 10.20.153.10 的服务消费者只可调用 IP 为 10.20.153.11 机器上的服务，不可调用其他机器上的服务。

下面列举一些 Dubbo 条件路由的典型应用场景：

• 如果服务消费者的匹配条件为空，就表示所有的服务消费者都可以访问，就像下面的表达式一样。

=> host != 10.20.153.11

• 如果服务提供者的过滤条件为空，就表示禁止所有的服务消费者访问，就像下面的表达式一样。

host = 10.20.153.10 =>

• 排除某个服务节点

=> host != 172.22.3.91

• 白名单

register.ip != 10.20.153.10,10.20.153.11 =>

• 黑名单

register.ip = 10.20.153.10,10.20.153.11 =>

• 只暴露部分机器节点

=> host = 172.22.3.1*,172.22.3.2*

• 为重要应用提供额外的机器节点

application != kylin => host != 172.22.3.95,172.22.3.96

• 读写分离

method = find*,list*,get*,is* => host = 172.22.3.94,172.22.3.95,172.22.3.96
method != find*,list*,get*,is* => host = 172.22.3.97,172.22.3.98

• 前后台分离

application = bops => host = 172.22.3.91,172.22.3.92,172.22.3.93
application != bops => host = 172.22.3.94,172.22.3.95,172.22.3.96

• 隔离不同机房网段

host != 172.22.3.* => host != 172.22.3.*

• 提供者与消费者部署在同集群内，本机只访问本机的服务

=> host = $host

脚本路由

脚本路由是基于脚本语言的路由规则，常用的脚本语言比如 JavaScript、Groovy、JRuby 等。

'script://0.0.0.0/com.foo.BarService?category=routers&dynamic=false&rule=' +
  URL.encode('（function route(invokers) { ... } (invokers)）')

这里面 script:// 就代表了这是一段脚本语言编写的路由规则，具体规则定义在脚本语言的 route 方法实现里，比如下面这段用 JavaScript 编写的 route() 方法表达的意思是，只有 IP 为 10.20.153.10 的服务消费者可以发起服务调用。

function route(invokers){
  var result = new java.util.ArrayList(invokers.size());
  for(i =0; i < invokers.size(); i ++){
    if("10.20.153.10".equals(invokers.get(i).getUrl().getHost())){
       result.add(invokers.get(i));
    }
  }
  return result;
 } (invokers)）;

标签路由

标签路由通过将某一个或多个服务的提供者划分到同一个分组，约束流量只在指定分组中流转，从而实现流量隔离的目的，可以作为蓝绿发布、灰度发布等场景的能力基础。

标签主要是指对服务提供者的分组，目前有两种方式可以完成实例分组，分别是动态规则打标和静态规则打标。一般，动态规则优先级比静态规则更高，当两种规则同时存在且出现冲突时，将以动态规则为准。

以 Dubbo 的标签路由用法为例

（1）动态规则打标，可随时在服务治理控制台下发标签归组规则

# governance-tagrouter-provider 应用增加了两个标签分组 tag1 和 tag2
# tag1 包含一个实例 127.0.0.1:20880
# tag2 包含一个实例 127.0.0.1:20881
---
  force: false
  runtime: true
  enabled: true
  key: governance-tagrouter-provider
  tags:
    - name: tag1
      addresses: ["127.0.0.1:20880"]
    - name: tag2
      addresses: ["127.0.0.1:20881"]
 ...

（2）静态规则打标

<dubbo:provider tag="tag1"/>

or

<dubbo:service tag="tag1"/>

or

java -jar xxx-provider.jar -Ddubbo.provider.tag={the tag you want, may come from OS ENV}

（3）服务消费者指定标签路由

RpcContext.getContext().setAttachment(Constants.REQUEST_TAG_KEY,"tag1");

请求标签的作用域为每一次 invocation，使用 attachment 来传递请求标签，注意保存在 attachment 中的值将会在一次完整的远程调用中持续传递，得益于这样的特性，我们只需要在起始调用时，通过一行代码的设置，达到标签的持续传递。

路由规则获取方式

路由规则的获取方式主要有三种：

• 本地静态配置：顾名思义就是路由规则存储在服务消费者本地上。服务消费者发起调用时，从本地固定位置读取路由规则，然后按照路由规则选取一个服务节点发起调用。
• 配置中心管理：这种方式下，所有的服务消费者都从配置中心获取路由规则，由配置中心来统一管理。
• 注册中心动态下发：这种方式下，一般是运维人员或者开发人员，通过服务治理平台修改路由规则，服务治理平台调用配置中心接口，把修改后的路由规则持久化到配置中心。因为服务消费者订阅了路由规则的变更，于是就会从配置中心获取最新的路由规则，按照最新的路由规则来执行。

一般来讲，服务路由最好是存储在配置中心，由配置中心来统一管理。这样的话，所有的服务消费者就不需要在本地管理服务路由，因为大部分的服务消费者并不关心服务路由的问题，或者说也不需要去了解其中的细节。通过配置中心，统一给各个服务消费者下发统一的服务路由，节省了沟通和管理成本。

但也不排除某些服务消费者有特定的需求，需要定制自己的路由规则，这个时候就适合通过本地配置来定制。

而动态下发可以理解为一种高级功能，它能够动态地修改路由规则，在某些业务场景下十分有用。比如某个数据中心存在问题，需要把调用这个数据中心的服务消费者都切换到其他数据中心，这时就可以通过动态下发的方式，向配置中心下发一条路由规则，将所有调用这个数据中心的请求都迁移到别的地方。

分布式任务

【中级】在 Java 中，实现一个进程内定时任务有哪些方案？

要点

定时器有非常多的使用场景，例如生成年/月/周/日统计报表、财务对账、会员积分结算、邮件推送等，都是定时器的使用场景。定时器一般有三种表现形式：按固定周期定时执行、延迟一定时间后执行、指定某个时刻执行。

定时器的本质是设计一种数据结构，能够存储和调度任务集合，而且 deadline 越近的任务拥有更高的优先级。那么定时器如何知道一个任务是否到期了呢？定时器需要通过轮询的方式来实现，每隔一个时间片去检查任务是否到期。

所以定时器的内部结构一般需要一个任务队列和一个异步轮询线程，并且能够提供三种基本操作：

• Schedule 新增任务至任务集合；
• Cancel 取消某个任务；
• Run 执行到期的任务。

JDK 原生提供了三种常用的定时器实现方式，分别为 Timer、DelayedQueue 和 ScheduledThreadPoolExecutor。

JDK 内置的三种实现定时器的方式，实现思路都非常相似，都离不开任务、任务管理、任务调度三个角色。三种定时器新增和取消任务的时间复杂度都是 O(logn)，面对海量任务插入和删除的场景，这三种定时器都会遇到比较严重的性能瓶颈。对于性能要求较高的场景，一般都会采用时间轮算法来实现定时器。

Timer

Timer 属于 JDK 比较早期版本的实现，它可以实现固定周期的任务，以及延迟任务。Timer 会启动一个异步线程去执行到期的任务，任务可以只被调度执行一次，也可以周期性反复执行多次。我们先来看下 Timer 是如何使用的，示例代码如下。

Timer timer = new Timer();
timer.scheduleAtFixedRate(new TimerTask() {
    @Override
    public void run() {
        // do something
    }
}, 10000, 1000);  // 10s 后调度一个周期为 1s 的定时任务

可以看出，任务是由 TimerTask 类实现，TimerTask 是实现了 Runnable 接口的抽象类，Timer 负责调度和执行 TimerTask。接下来我们看下 Timer 的内部构造。

public class Timer {

    private final TaskQueue queue = new TaskQueue();
    private final TimerThread thread = new TimerThread(queue);

    public Timer(String name) {
        thread.setName(name);
        thread.start();
    }
}

TaskQueue 是由数组结构实现的小根堆，deadline 最近的任务位于堆顶端，queue[1] 始终是最优先被执行的任务。所以使用小根堆的数据结构，Run 操作时间复杂度 O(1)，新增（Schedule）和取消（Cancel）操作的时间复杂度都是 O(logn)。

Timer 内部启动了一个 TimerThread 异步线程，不论有多少任务被加入数组，始终都是由 TimerThread 负责处理。TimerThread 会定时轮询 TaskQueue 中的任务，如果堆顶的任务的 deadline 已到，那么执行任务；如果是周期性任务，执行完成后重新计算下一次任务的 deadline，并再次放入小根堆；如果是单次执行的任务，执行结束后会从 TaskQueue 中删除。

Timer 只使用一个线程来执行任务意味着同一时间只能有一个任务得到执行，而前一个任务的延迟或者异常会影响到之后的任务。如果有一个定时任务在运行时，产生未处理的异常，那么当前这个线程就会停止，那么所有的定时任务都会停止，受到影响。

不推荐使用 Timer ，因为 Timer 存在以下设计缺陷：

• Timer 是单线程模式。如果某个 TimerTask 执行时间很久，会影响其他任务的调度。
• Timer 的任务调度是基于系统绝对时间的，如果系统时间不正确，可能会出现问题。
• TimerTask 如果执行出现异常，Timer 并不会捕获，会导致线程终止，其他任务永远不会执行。

ScheduledExecutorService

为了解决 Timer 的设计缺陷，JDK 提供了功能更加丰富的 ScheduledThreadPoolExecutor。ScheduledThreadPoolExecutor 提供了周期执行任务和延迟执行任务的特性。

public class ScheduledExecutorServiceTest {
    public static void main(String[] args) {
        ScheduledExecutorService executor = Executors.newScheduledThreadPool(5);
         // 1s 延迟后开始执行任务，每 2s 重复执行一次
        executor.scheduleAtFixedRate(() -> System.out.println("Hello World"), 1000, 2000, TimeUnit.MILLISECONDS);
    }
}

ScheduledThreadPoolExecutor 继承于 ThreadPoolExecutor，因此它具备线程池异步处理任务的能力。线程池主要负责管理创建和管理线程，并从自身的阻塞队列中不断获取任务执行。线程池有两个重要的角色，分别是任务和阻塞队列。ScheduledThreadPoolExecutor 在 ThreadPoolExecutor 的基础上，重新设计了任务 ScheduledFutureTask 和阻塞队列 DelayedWorkQueue。ScheduledFutureTask 继承于 FutureTask，并重写了 run() 方法，使其具备周期执行任务的能力。DelayedWorkQueue 内部是优先级队列，deadline 最近的任务在队列头部。对于周期执行的任务，在执行完会重新设置时间，并再次放入队列中。

DelayedQueue

DelayedQueue 是 JDK 中一种可以延迟获取对象的阻塞队列，其内部是采用优先级队列 PriorityQueue 存储对象。DelayQueue 中的每个对象都必须实现 Delayed 接口，并重写 compareTo 和 getDelay 方法。DelayedQueue 的使用方法如下：

public class DelayQueueTest {

    public static void main(String[] args) throws Exception {

        BlockingQueue<SampleTask> delayQueue = new DelayQueue<>();
        long now = System.currentTimeMillis();
        delayQueue.put(new SampleTask(now + 1000));
        delayQueue.put(new SampleTask(now + 2000));
        delayQueue.put(new SampleTask(now + 3000));
        for (int i = 0; i < 3; i++) {
            System.out.println(new Date(delayQueue.take().getTime()));
        }
    }

    static class SampleTask implements Delayed {

        long time;

        public SampleTask(long time) {
            this.time = time;
        }

        public long getTime() {
            return time;
        }

        @Override

        public int compareTo(Delayed o) {
            return Long.compare(this.getDelay(TimeUnit.MILLISECONDS), o.getDelay(TimeUnit.MILLISECONDS));
        }

        @Override

        public long getDelay(TimeUnit unit) {
            return unit.convert(time - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
        }
    }

}

DelayQueue 提供了 put() 和 take() 的阻塞方法，可以向队列中添加对象和取出对象。对象被添加到 DelayQueue 后，会根据 compareTo() 方法进行优先级排序。getDelay() 方法用于计算消息延迟的剩余时间，只有 getDelay <=0 时，该对象才能从 DelayQueue 中取出。

DelayQueue 在日常开发中最常用的场景就是实现重试机制。例如，接口调用失败或者请求超时后，可以将当前请求对象放入 DelayQueue，通过一个异步线程 take() 取出对象然后继续进行重试。如果还是请求失败，继续放回 DelayQueue。为了限制重试的频率，可以设置重试的最大次数以及采用指数退避算法设置对象的 deadline，如 2s、4s、8s、16s ……以此类推。

相比于 Timer，DelayQueue 只实现了任务管理的功能，需要与异步线程配合使用。DelayQueue 使用优先级队列实现任务的优先级排序，新增（Schedule）和取消（Cancel）操作的时间复杂度也是 O(logn)。

时间轮

JDK 内置的三种实现定时器的方式，实现思路都非常相似，都离不开任务、任务管理、任务调度三个角色。三种定时器新增和取消任务的时间复杂度都是 O(logn)，面对海量任务插入和删除的场景，这三种定时器都会遇到比较严重的性能瓶颈。对于性能要求较高的场景，一般都会采用时间轮算法来实现定时器。

时间轮（Timing Wheel）是 George Varghese 和 Tony Lauck 在 1996 年的论文 Hashed and Hierarchical Timing Wheels: data structures to efficiently implement a timer facility 实现的，它在 Linux 内核中使用广泛，是 Linux 内核定时器的实现方法和基础之一。

时间轮可以理解为一种环形结构，像钟表一样被分为多个 slot 槽位。每个 slot 代表一个时间段，每个 slot 中可以存放多个任务，使用的是链表结构保存该时间段到期的所有任务。时间轮通过一个时针随着时间一个个 slot 转动，并执行 slot 中的所有到期任务。

图片 22.png

任务是如何添加到时间轮当中的呢？可以根据任务的到期时间进行取模，然后将任务分布到不同的 slot 中。如上图所示，时间轮被划分为 8 个 slot，每个 slot 代表 1s，当前时针指向 2。假如现在需要调度一个 3s 后执行的任务，应该加入 2+3=5 的 slot 中；如果需要调度一个 12s 以后的任务，需要等待时针完整走完一圈 round 零 4 个 slot，需要放入第 (2+12)%8=6 个 slot。

那么当时针走到第 6 个 slot 时，怎么区分每个任务是否需要立即执行，还是需要等待下一圈 round，甚至更久时间之后执行呢？所以我们需要把 round 信息保存在任务中。例如图中第 6 个 slot 的链表中包含 3 个任务，第一个任务 round=0，需要立即执行；第二个任务 round=1，需要等待 1*8=8s 后执行；第三个任务 round=2，需要等待 2*8=8s 后执行。所以当时针转动到对应 slot 时，只执行 round=0 的任务，slot 中其余任务的 round 应当减 1，等待下一个 round 之后执行。

上面介绍了时间轮算法的基本理论，可以看出时间轮有点类似 HashMap，如果多个任务如果对应同一个 slot，处理冲突的方法采用的是拉链法。在任务数量比较多的场景下，适当增加时间轮的 slot 数量，可以减少时针转动时遍历的任务个数。

时间轮定时器最大的优势就是，任务的新增和取消都是 O(1) 时间复杂度，而且只需要一个线程就可以驱动时间轮进行工作。

HashedWheelTimer 是 Netty 中时间轮算法的实现类。

【中级】分布式定时任务有哪些方案？

要点

分布式定时任务常见方案有：

• Quartz
• XXL-Job
• ElasticJob

Quartz

Quartz 是一个经典的开源定时调度框架。它支持进程内调度和分布式调度。

Quartz 提供两种基本作业存储类型：

• RAMJobStore - 在默认情况下 Quartz 将任务调度的运行信息保存在内存中，这种方法提供了最佳的性能，因为内存中数据访问最快。不足之处是缺乏数据的持久性，当程序路途停止或系统崩溃时，所有运行的信息都会丢失。
• JobStoreTX - 所有的任务信息都会保存到数据库中，可以控制事物，还有就是如果应用服务器关闭或者重启，任务信息都不会丢失，并且可以恢复因服务器关闭或者重启而导致执行失败的任务

XXL-Job

xxl-job 是一个分布式任务调度平台。

设计思想

将调度行为抽象形成“调度中心”公共平台，而平台自身并不承担业务逻辑，“调度中心”负责发起调度请求。

将任务抽象成分散的 JobHandler，交由“执行器”统一管理，“执行器”负责接收调度请求并执行对应的 JobHandler 中业务逻辑。

因此，“调度”和“任务”两部分可以相互解耦，提高系统整体稳定性和扩展性；

系统组成

• 调度模块（调度中心）：
  负责管理调度信息，按照调度配置发出调度请求，自身不承担业务代码。调度系统与任务解耦，提高了系统可用性和稳定性，同时调度系统性能不再受限于任务模块；
  支持可视化、简单且动态的管理调度信息，包括任务新建，更新，删除，GLUE 开发和任务报警等，所有上述操作都会实时生效，同时支持监控调度结果以及执行日志，支持执行器 Failover。
• 执行模块（执行器）：
  负责接收调度请求并执行任务逻辑。任务模块专注于任务的执行等操作，开发和维护更加简单和高效；
  接收“调度中心”的执行请求、终止请求和日志请求等。

输入图片说明

ElasticJob

两个相互独立的子项目 ElasticJob-Lite 和 ElasticJob-Cloud 组成。 它通过弹性调度、资源管控、以及作业治理的功能，打造一个适用于互联网场景的分布式调度解决方案，并通过开放的架构设计，提供多元化的作业生态。 它的各个产品使用统一的作业 API，开发者仅需一次开发，即可随意部署。

ElasticJob 采用去中心化架构，没有作业调度中心。它以框架的形式，集成到应用中，提供调度服务。

ElasticJob-Lite 定位为轻量级无中心化解决方案，使用 jar 的形式提供分布式任务的协调服务。

ElasticJob Architecture

ElasticJob-Cloud 采用自研 Mesos Framework 的解决方案，额外提供资源治理、应用分发以及进程隔离等功能。

ElasticJob-Cloud Architecture

ElasticJob-Lite 和 ElasticJob-Cloud 对比：

ElasticJob-Lite	ElasticJob-Cloud
无中心化	是	否
资源分配	不支持	支持
作业模式	常驻	常驻 + 瞬时
部署依赖	ZooKeeper	ZooKeeper + Mesos

ElasticJob-Cloud 的优势在于对资源细粒度治理，适用于需要削峰填谷的大数据系统。