Kong Least-Connections 负载均衡算法分析

1. 概述

本报告基于 kong/runloop/balancer/least_connections.lua 源码，深入分析 least-connections 负载均衡算法的工作机制。

2. 核心数据结构分析

2.1 二叉堆的使用

-- 第188行：使用最小唯一堆
binaryHeap = binaryHeap.minUnique()

关键特性：

最小堆：优先级值越小的元素在堆顶
唯一堆：每个 payload（address对象）在堆中唯一存在
peek() 特性：总是返回位置1的元素（堆顶）

2.2 优先级计算公式

-- 第28行和第44行：优先级计算
priority = (addr.connectionCount + 1) / addr.weight

公式解析：

连接数越少，优先级越高（值越小）
权重越大，优先级越高（值越小）
+1 确保零连接时权重仍然有效

3. 流量分配机制分析

3.1 地址选择过程

-- 第96行：核心选择逻辑
address = self.binaryHeap:peek()

选择规则：

peek() 总是返回堆顶元素（位置1）
堆顶元素是当前优先级最高的地址
选中后连接数+1，优先级重新计算

3.2 堆重建过程

-- 第158-166行：afterHostUpdate方法
function lc:afterHostUpdate()
  clearHeap(self.binaryHeap)

  for _, target in ipairs(self.balancer.targets) do
    for _, address in ipairs(target.addresses) do
      insertAddr(self.binaryHeap, address)
    end
  end
end

重要发现：地址按照 targets 数组的顺序插入堆中。

4. 低并发场景问题分析

4.1 场景设定

8个target：T1, T2, T3, T4, T5, T6, T7, T8
并发1-2：同时只有1-2个活跃连接
相同权重：所有target权重相同

4.2 流量分配模拟

初始状态（所有target连接数为0）

Target  | 连接数 | 权重 | 优先级    | 堆位置
--------|--------|------|-----------|--------
T1      | 0      | 100  | 1/100=0.01| 1 (堆顶)
T2      | 0      | 100  | 1/100=0.01| 2
T3      | 0      | 100  | 1/100=0.01| 3
...     | ...    | ...  | ...       | ...
T8      | 0      | 100  | 1/100=0.01| 8

并发为1的情况

请求序号 | 选择Target | T1连接数 | T2连接数 | ... | T8连接数 | 堆顶
---------|------------|----------|----------|-----|----------|------
1        | T1         | 1        | 0        | ... | 0        | T2
2        | T2         | 0(释放)  | 1        | ... | 0        | T1
3        | T1         | 1        | 0(释放)  | ... | 0        | T2
4        | T2         | 0(释放)  | 1        | ... | 0        | T1

结果：只有T1和T2获得流量，T3-T8没有流量！

5. 根本原因分析

5.1 二叉堆的位置稳定性

-- binaryheap 的比较函数（默认）
lt = function(a,b) return (a < b) end

关键特性：

当两个元素优先级相同时，a < b 返回 false
相同优先级的元素不会交换位置
堆的相对位置保持稳定

5.2 插入顺序的影响

-- 按targets数组顺序插入
for _, target in ipairs(self.balancer.targets) do
  for _, address in ipairs(target.addresses) do
    insertAddr(self.binaryHeap, address)  -- 先插入的更可能在前面
  end
end

结果：配置中靠前的target更容易占据堆的前部位置。

5.3 peek()的固定性

-- peek()总是返回位置1的元素
address = self.binaryHeap:peek()

问题：在低并发场景下，只有堆顶附近的少数元素会被选中。

6. 问题总结

6.1 核心问题

在低并发场景下，least-connections算法会导致流量集中在少数几个target上，后加入的target可能长期没有流量。

6.2 影响因素

二叉堆的位置稳定性：相同优先级元素位置不变
peek()的固定性：总是选择位置1的元素
插入顺序：先插入的target更容易获得流量
低并发特性：活跃连接少，优先级差异小

6.3 数学证明

在并发为N的场景下，理论上最多只有前N+1个target会获得流量：

N个target各有1个连接（优先级：2/weight）
1个target有0个连接（优先级：1/weight，位于堆顶）

7. 多网关节点场景问题分析

7.1 问题场景描述

在多网关节点部署的环境中，least-connections算法面临更严重的流量分配不均问题：

场景设定：

多个Kong网关节点：Gateway1, Gateway2, Gateway3…
多个后端Target：Target1, Target2, Target3…
轮询请求分发：客户端或负载均衡器将请求轮询分发到各个网关节点
独立堆管理：每个网关节点维护自己的二叉堆，不共享连接状态

7.2 核心问题：堆状态不同步

问题机制

多网关节点场景下，每个网关节点独立维护自己的二叉堆，不共享连接状态。这导致所有节点可能同时选择相同的Target。

时间线分析：

时间	事件	Gateway1状态	Gateway2状态	Target1实际负载
T1	请求1→GW1	T1:1连接,堆顶:T2	T1:0连接,堆顶:T1	1个连接
T2	请求2→GW2	T1:1连接,堆顶:T2	T1:1连接,堆顶:T2	2个连接（过载！）
T3	请求3→GW1	T1:0连接,堆顶:T1	T1:1连接,堆顶:T2	1个连接
T4	请求4→GW2	T1:1连接,堆顶:T2	T1:0连接,堆顶:T1	2个连接（再次过载！）

7.3 问题严重性分析

流量集中效应放大

在单网关节点场景下，流量集中在少数target；在多网关节点场景下，这种集中效应被显著放大：

单网关场景：Target1获得50%流量
多网关场景：Target1可能获得80%+流量