# 自定义限流及负载均衡算法

**Repository Path**: salierime/load-balancing-algorithm

## Basic Information

- **Project Name**: 自定义限流及负载均衡算法
- **Description**: 自定义令牌桶限流算法；自定义轮询负载均衡算法；自定义加权轮询负载均衡算法；自定义平滑加权轮询负载均衡算法
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-07-19
- **Last Updated**: 2025-04-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 负载均衡算法

## 介绍
实现不同的负载均衡算法。 

## 涉及内容
1. Eureka集群 

2. Ribbon底层原理 

3. 负载均衡算法：轮询算法 + 加权轮询算法 + 平滑加权轮询算法  
   轮询负载均衡算法：在单线程下可保证不同请求依次打在不同服务实例上。  
   加权轮询负载均衡算法：在单线程下可保证不同请求按权重依次打在不同服务实例上。  
   平滑加权轮询负载均衡算法：在单线程下可保证不同请求按权重平滑打在不同服务实例上，最终请求结果遵循权重关系。  
4. 限流算法：令牌桶算法
   在单线程下可保证接口多次访问限流。


## 系统架构图
1. 请求    -(限流)->     StockOrderService(stock_order表)    -(负载均衡)->     StockService集群(stock表)  
2. StockOrderService、StockService集群 注册在Eureka 集群 

## 【限流算法】
### 定义
在单线程下可保证接口多次访问限流。

### 实现流程
Step1：定义一个CustomTokenAlgorithm类，用于实现令牌桶限流算法核心流程。   
![img_1.png](readme-resource/img_1.png)

Step2：将CustomTokenAlgorithm类应用于业务逻辑层实现限流。 
![img_6.png](readme-resource/img_6.png)

### 功能演示
Step1：启动Eureka集群  
Step2：启动StockOrderService多实例   
![img_2.png](readme-resource/img_2.png)

Step3：接口限流测试(频繁调用接口) 
![img_4.png](readme-resource/img_4.png)

## 【负载均衡算法】简单轮询算法
### 定义
在单线程下可保证不同请求依次打在不同服务实例上。

### 实现流程
![img_7.png](readme-resource/img_7.png)

### 功能演示
- 应用简单轮询算法，调用端口 http://localhost:8871/custom/getStock/1 五次。随着访问次数的增加，简单轮询负载均衡算法会令请求依次打在8862、8864、8863、8865、8861，而后又从8862开始不断循环。

## 【负载均衡算法】加权轮询算法
### 定义
在单线程下可保证不同请求按权重依次打在不同服务实例上

### 实现流程
- 加权轮询算法的数学原理如下：  
   设有三台服务器A、B和C，假设它们的权重遵循 [5, 3, 2]。设有一请求进来的offset = 7。   
   Step1：针对权重数组进行累加，得到数组α [0, 5, 8, 10]。    
   Step2：知 offset > 5，则 offset – 5 = 2，且数组α进行减操作得 [-5, 0, 3, 5]。    
   Step3：知 offset = 2 < 3，故选择服务器A。   
- 权轮询算法的代码实现如图所示：
![img_8.png](readme-resource/img_8.png)

### 功能演示
- 假设端口 [8861, 8862, 8863, 8864, 8865] 的权重分布为 [1, 2, 3, 4, 5] 。应用加权轮询算法，调用端口 http://localhost:8871/custom/getStock/1 十五次，随着访问次数的增加，加权轮询负载均衡算法会令请求依次打在1个8861、2个8862、3个8863、4个8864、5个8865，而后又从1个8861开始循环。

## 【负载均衡算法】平滑加权轮询算法
### 定义
在单线程下可保证不同请求按权重平滑打在不同服务实例上，最终请求结果遵循权重关系。

### 实现流程
- 平滑加权轮询算法（Nginx里默认的算法）的数学原理如下：  
设有三台服务器， 服务器A、服务器B、服务器C。设给 [A, B, C] 配置的为静态权重：weight = [5, 1, 1]。现需输出不同请求进来的负载均衡选择结果。   
解：   
设动态权重 currentWeight = [0, 0, 0]，算法过程如下表所示。   
![img_9.png](readme-resource/img_9.png)  
由表，平滑加权轮询算法保证了第一轮的7个请求能够最终达到依据静态权重请求实例A五次、请求实例B一次、请求实例C一次。

### 功能演示
- 假设端口 [8861, 8862, 8863, 8864, 8865] 的权重分布为 [1, 2, 3, 4, 5] 。应用加权轮询算法，调用端口 http://localhost:8871/custom/getStock/1 十五次，15次请求最终结果保证有1次的8861、2次的8862、3次的8863、4次的8864、5次的8865，而其过程中的顺序并不是严格有序的。