经常有人问我负载均衡不是网关干的活吗你一个写业务逻辑的折腾它干嘛说实话我早些年也是这么想的。后来在服务治理、RPC 框架、缓存路由这些场景里被按在地上摩擦了几次才明白一个道理网关负责的是“外部流量怎么进”而代码里的负载均衡负责的是“内部请求怎么选”这俩根本不是一回事。你写微服务要选实例写 SDK 要选节点写缓存客户端要选分片这些场景没有现成网关替你挡着只能自己在代码里做调度。这篇文章把“手写负载均衡算法”这件事从头到尾捋一遍。从最朴素的轮询开始到生产能用的平滑加权轮询、最少连接数再到缓存和会话场景避不开的一致性哈希。每个算法我都会给出可以直接抄的代码、一步步的推演以及实际工程里的坑。不管你是要给 RPC 框架加负载均衡还是面试前想彻底搞懂这些算法的门道这篇都值得读完。1. 为什么写业务代码的人也需要手写一遍负载均衡1.1 两类负载均衡先别搞混很多人一说负载均衡脑子里就是机房入口那台四层设备或者七层反代网关。这类基础设施负载均衡解决的是“流量到达服务之前如何分发”的问题它的选路逻辑确实不需要业务方操心。但还有另一类进程内的负载均衡。服务发现组件给你返回十个实例地址你作为调用方必须选一个发请求缓存客户端要在若干分片里选一个写数据消息消费者要从多个队列节点里挑一个建连接。这些决策发生在你的代码里不在任何网关里。你选得好不好直接决定这一条请求的时延、这个节点的压力、整条链路的稳定性。所以不是“写业务代码不需要懂负载均衡”而是“只要你写分布式相关代码你就已经在用某种负载均衡策略了只是你可能没意识到”。1.2 手写一遍的价值恰恰在于理解代价老实说手写负载均衡算法这件事最直接的收益不是“省一个组件钱”而是帮你建立对算法的判断力。每个负载均衡算法都藏着假设。轮询假设所有节点能力一样、所有请求成本一样加权轮询假设权重能反映节点能力最少连接数假设“连接数”能代表“压力”一致性哈希假设“key 的路由稳定性”比“绝对均匀”更重要。这些假设平时藏在封装好的框架里看不见一旦线上出现负载不均、缓存命中率骤降、节点雪崩你如果没有亲手实现过根本不知道从哪儿开始排查。另外手写的代码量其实很小几百行就能覆盖主流算法但每一行背后的权衡都能讲出故事。这也是为什么面试里这个题目从没凉过。1.3 本文要实现的算法地图先把接下来要写的算法放到一张表里方便你对照着看算法核心思想明显优点明显缺点典型场景轮询请求依次轮流分发实现最简单不考虑节点差异与真实负载节点同配置、请求开销接近加权轮询按权重分配流量能体现节点能力差异朴素实现会产生流量突刺节点配置有差异时平滑加权轮询用动态修正量平滑调度平滑且比例精准略复杂需锁保护大多数生产场景首选最少连接数选当前连接数最少的节点动态感知瞬时负载连接数不等于真实负载长连接、请求耗时不均一致性哈希按 key 固定路由到节点增删节点影响面小可能倾斜需虚拟节点缓存、会话保持后面每一节都会对着这张表展开。2. 轮询算法五分钟写出来但别急着上生产2.1 最简实现长什么样轮询是最容易理解的一种手里有一份节点列表来一个请求就给下一个节点走完一圈回到开头。Go 实现非常短type RoundRobin struct { mu sync.Mutex servers []string current int } func NewRoundRobin(servers []string) *RoundRobin { return RoundRobin{servers: servers} } func (r *RoundRobin) Next() string { r.mu.Lock() defer r.mu.Unlock() if len(r.servers) 0 { return } server : r.servers[r.current%len(r.servers)] r.current return server }注意这里我上了锁。current是共享变量高并发下多个 goroutine 同时自增会丢计数轻则顺序乱重则索引越界。写负载均衡的第一条纪律就是所有涉及共享状态的操作都要考虑并发安全。这个实现的好处是干净坏处是它假设了一个世界每个节点处理能力一模一样每个请求消耗的资源一模一样而且节点永远不会挂。2.2 轮询的两个隐藏假设现实世界很少满足这些假设。先说节点差异。你手里十个节点八个是新机器两个是退役下来的老机器轮询照样一视同仁。老机器被塞满请求处理不过来请求超时超时又触发重试重试的请求继续被均匀分发继续压到老机器上。最后表现就是整个集群的时延被最慢的那台机器拖住了。再说请求差异。就算节点能力相同请求的成本也不一样。一个读缓存的请求和一次全表扫描的请求对节点的消耗差了几十倍。轮询只管“次数平均”不管“成本平均”次数上去了成本可能完全失衡。所以轮询适合什么场景节点同规格、请求开销稳定、处理时间接近比如纯转发、短平快的内部查询。只要有一条不满足就该往下一个算法走了。2.3 加权轮询从“完全平均”到“按比例分配”既然节点能力不一样最容易想到的改进就是加权给能力强的节点更大的权重能力弱的给小权重。朴素的做法是把权重展开成序列。比如三个节点 A(5)、B(1)、C(1)展开成[A, A, A, A, A, B, C]然后在这个序列上做轮询// 朴素加权轮询把权重展开成序列后依次取 func buildWeightedSeq(weights map[string]int) []string { var seq []string for addr, w : range weights { for i : 0; i w; i { seq append(seq, addr) } } return seq }这个方案能解决“按比例分配”的问题A 确实会收到 5/7 的流量但它引入了新的问题——突刺。看展开后的序列前五个请求全部落在 A 上。A 会在很短时间里被连打五下然后 B、C 各接一下接着又是 A 连续五下。这种“一阵一阵”的流量看起来不痛不痒实际在低延迟场景里很容易形成瞬时排队也让监控曲线变得很难看。能不能在保持 5:1:1 比例的同时把 A 的五个请求尽量均匀地穿插开这就是平滑加权轮询要做的事。3. 平滑加权轮询让流量像呼吸一样均匀3.1 为什么朴素加权轮询会产生“突刺”突刺的本质是“权重被一次性兑现”。展开序列相当于把 A 的 5 次配额一口气花完B 和 C 的配额只能排队等。如果改成“每次从三个节点里挑一个挑完动态调整下次的选择”就有机会把 A 的配额摊进整个周期。很多人以为只要“随机地在权重范围内选”就能解决。随机确实能把突刺磨平一些但随机没法保证比例足够精确小样本下偏差很明显。我们希望的是既精确到 5:1:1又平滑到不连续出现。3.2 平滑加权轮询的三条规则这个算法我直接讲规则讲完你再看代码会觉得它极其直白每个节点有两个量固定权重配置值不变和动态当前值每次都会变初始为 0。每来一个请求先把所有节点的当前值都加上自己的固定权重然后选出当前值最大的节点。被选中的节点把当前值减去所有节点的固定权重之和。听起来有点像“先给所有节点发一轮积分积分最高的出手出手后扣掉一整轮的积分总量”。这个“扣掉总权重”的设计是整个算法平滑的关键它保证所有节点的当前值总和始终为零谁被选中谁就暂时“欠债”没被选中的持续“攒分”于是权重大的节点不会连着被选中权重小的节点也会在合适的时候冒出来。3.3 完整实现type SmoothWeightedServer struct { addr string weight int current int } type SmoothWeightedRR struct { mu sync.Mutex servers []*SmoothWeightedServer totalWeight int } func NewSmoothWeightedRR(weights map[string]int) *SmoothWeightedRR { rr : SmoothWeightedRR{} for addr, w : range weights { rr.servers append(rr.servers, SmoothWeightedServer{ addr: addr, weight: w, }) rr.totalWeight w } return rr } func (s *SmoothWeightedRR) Next() string { s.mu.Lock() defer s.mu.Unlock() if len(s.servers) 0 { return } var best *SmoothWeightedServer for _, server : range s.servers { server.current server.weight if best nil || server.current best.current { best server } } if best ! nil { best.current - s.totalWeight } return best.addr }只有二十几行核心就是Next()里的三步累加、选最大、被选中者扣总权重。3.4 拿 A(5) B(1) C(1) 手工推演一遍纸上推演是最能验证算法的方式。三个节点 A、B、C权重分别是 5、1、1总权重 7。轮次累加权重后的 current选中扣除总权重后的 current1A5, B1, C1AA-2, B1, C12A3, B2, C2AA-4, B2, C23A1, B3, C3BA1, B-4, C34A6, B-3, C4AA-1, B-3, C45A4, B-2, C5CA4, B-2, C-26A9, B-1, C-1AA2, B-1, C-17A7, B0, C0AA0, B0, C0一个周期七次选择选中序列是A A B A C A A。A 出现五次B、C 各一次比例严格是 5:1:1但你再也不会看到连续五个 A 挨在一起。C 和 B 被均匀地嵌进 A 的序列里这就是“平滑”的意思。到第八轮所有当前值清零整个周期重新开始。所以它还是一个严格周期的算法不会出现长期漂移。3.5 工程上补几个细节平滑加权轮询在我心里是“生产默认首选”但它落地时有几个容易翻车的点。一是节点列表变化。新增节点或删掉节点后总权重变了所有节点的当前值也应该重置不然旧账会带进新周期前几次选择可能明显异常。我习惯在节点变更时直接重建整个结构简单粗暴反正这个结构本身不大。二是权重变化的频率不能太高。动态调权比如根据 CPU 使用率调权重是另一个话题频繁改动会让调度记录永远收敛不到稳定状态。调权周期建议至少秒级甚至分钟级别在请求路径上实时改。三是锁的粒度。这里用一把大锁包住整个选择过程节点数少、QPS 高时没问题节点几百个时可以把“当前值”设计成原子操作但大多数场景没这个必要别过早优化。4. 最少连接数把请求交给最闲的节点4.1 什么场景下“连接数”能代表负载平滑加权轮询再好也是“开环”的——它只按照预设权重分发从不看节点当下到底忙不忙。如果请求处理时间很不均匀比如有的请求几毫秒返回有的要跑几十秒轮询类算法就会失真。这时候需要引入反馈用每个节点的活跃连接数衡量它的忙碌程度把新请求交给连接数最少的节点。注意“连接数”这个指标什么时候有效它适合长连接、请求持续占用时间差异大的场景。比如数据库连接池、消息推送服务、文件传输服务连接多基本意味着压力大。但如果是 CPU 密集的短请求连接数还没来得及累计就被释放了这个指标并不敏感。4.2 最少连接数的实现实现本身不复杂核心是维护每个节点的连接计数选择时取最小值type LeastConnection struct { mu sync.Mutex servers []string conns []int } func NewLeastConnection(servers []string) *LeastConnection { return LeastConnection{ servers: servers, conns: make([]int, len(servers)), } } func (l *LeastConnection) Next() string { l.mu.Lock() defer l.mu.Unlock() if len(l.servers) 0 { return } minIdx : 0 for i : 1; i len(l.conns); i { if l.conns[i] l.conns[minIdx] { minIdx i } } l.conns[minIdx] return l.servers[minIdx] } // 请求结束或失败时必须调用 Done 归还计数 func (l *LeastConnection) Done(addr string) { l.mu.Lock() defer l.mu.Unlock() for i, s : range l.servers { if s addr { if l.conns[i] 0 { l.conns[i]-- } return } } }这里有个非常容易被忽略的约定Next()里自增只是“预订”真正让计数减回去的是调用方在请求结束后执行的Done()。如果你的代码在Next()之后发生 panic、超时、连接失败就必须在defer里保证Done()一定执行。漏一次计数就虚高一次时间长了这个节点会被算法“遗忘”再也不会被选中。节点很多时Done()里的线性查找是浪费。实际项目会把servers换成map[string]*node节点对象里存计数查找变成 O(1)。代码结构变复杂一点但思路完全一样。4.3 竞态窗口选完到自增之间的缝隙还有个细节值得单独说。Next()虽然是在锁里完成“选最小自增”但锁释放之后、请求真正发出去之前这个节点的连接数还没被对端感知。也就是说所有并发调用看到的都是“上一个瞬间”的计数快照这会让选择结果有一定偏差。这种偏差在多数场景可以接受因为最少连接数本身就是近似最优。真正要警惕的是另一个问题如果某些节点处理极快连接数永远趋近于零它们反而会承接所有新请求形成“饥饿”。所以最少连接数在实际落地时几乎都会配合一个“最小并发阈值”或者“最低流量占比”之类的保护保证弱节点不至于完全被绕过也不至于被压垮。4.4 这个算法的翻车点我见过最少连接数翻车最典型的一次某个节点的连接池被打满连接悬挂在那里既不成功也不失败计数一直居高不下。最少连接算法会一直避开它但避开的代价是其他节点被迅速打满整体时延飙升。后来排查发现悬挂连接是客户端超时设置不合理导致的。这提醒我连接数这个反馈信号本身也会失真失真来源可能是健康检查没跟上、连接没能及时清理、或者调用方没有正确释放。更进一步的方案是用“加权移动平均响应时间”或者“瞬时错误率”做反馈那就是负载均衡里的自适应算法了代价是统计量更多、实现更重。大多数业务场景最少连接数加一个可靠的健康检查已经够用。5. 一致性哈希缓存与会话的“记忆魔法”5.1 取模哈希为什么在扩容时是灾难前面几种算法都追求“把流量摊匀”但在缓存和会话保持场景里“摊匀”不是第一目标“路由稳定”才是。同一个用户最好每次都被分配到同一个节点这样缓存才能命中、会话才能延续。最朴素的做法是hash(key) % NN 是节点数。问题在于N 一变几乎所有 key 的取模结果都会变。打个比方10 个节点变成 11 个一个 key 原来落在第 3 个节点现在取模结果大概率不是 3。粗略估算只有hash(key) % 10 hash(key) % 11的 key 能留在原节点概率大约是 1/10也就是说扩容一次九成缓存全部失效。这在缓存场景里就是灾难瞬间大量请求穿透到数据库哪怕网关和数据库能扛住也会出现一波明显抖动。5.2 哈希环上的顺时针路由一致性哈希的思路是把整个哈希空间看成一个首尾相接的环通常是0到2^32-1。节点地址经过哈希后放到环上key 也哈希到环上然后沿着环顺时针找遇到的第一个节点就是路由目标。这样做的好处是增删节点只影响局部。比如环上有 A、B、C 三个节点现在删掉 B只有“原本落在 B 和 B 的后继之间”的那些 key 需要重新路由其他 key 动都不动。按概率算删除 N 个节点之一受影响的比例大约是 1/N。从九成变成三成、一成这个差距是质的。5.3 虚拟节点解决数据倾斜一致性哈希有个天然短板如果节点数量少环上的哈希点就稀疏“顺时针找最近节点”可能导致某个节点圈走一大段弧数据分布严重不均匀。解决手段是引入虚拟节点。让每个物理节点在环上生成一批虚拟位置比如 100 个、200 个。物理上是同一个节点但它的虚拟点在环上分散分布。这样三个物理节点加上几百个虚拟点环被切得很碎统计上每个物理节点分到的弧长趋近于 1/3数据自然均匀。虚拟点数量也不是越多越好。每个虚拟点都要存一个映射节点数量大时内存开销明显上升。常见经验值是 100 到 200 个虚拟点均衡效果和内存开销之间比较平衡。哈希函数本身也要选分布均匀的FNV、Murmur 这类都行别用质量很差的简单取模哈希。5.4 完整实现与验证完整的 Go 实现如下type ConsistentHash struct { replicas int ring []uint32 mapping map[uint32]string nodes map[string]struct{} mu sync.RWMutex } func NewConsistentHash(replicas int) *ConsistentHash { return ConsistentHash{ replicas: replicas, mapping: make(map[uint32]string), nodes: make(map[string]struct{}), } } func (c *ConsistentHash) Add(addr string) { c.mu.Lock() defer c.mu.Unlock() if _, ok : c.nodes[addr]; ok { return } for i : 0; i c.replicas; i { key : hashKey([]byte(addr # strconv.Itoa(i))) c.ring append(c.ring, key) c.mapping[key] addr } c.nodes[addr] struct{}{} sort.Slice(c.ring, func(i, j int) bool { return c.ring[i] c.ring[j] }) } func (c *ConsistentHash) Remove(addr string) { c.mu.Lock() defer c.mu.Unlock() if _, ok : c.nodes[addr]; !ok { return } newRing : make([]uint32, 0, len(c.ring)) for _, key : range c.ring { if c.mapping[key] addr { delete(c.mapping, key) } else { newRing append(newRing, key) } } c.ring newRing delete(c.nodes, addr) } func (c *ConsistentHash) Get(key string) string { c.mu.RLock() defer c.mu.RUnlock() if len(c.ring) 0 { return } h : hashKey([]byte(key)) idx : sort.Search(len(c.ring), func(i int) bool { return c.ring[i] h }) if idx len(c.ring) { idx 0 } return c.mapping[c.ring[idx]] } func hashKey(data []byte) uint32 { h : fnv.New32a() h.Write(data) return h.Sum32() }这段代码的关键点是courttyation——其实就两条Remove重建 ring 时要在映射里同步删除虚拟点Get里idx len(c.ring)表示哈希值超过了环上最大点需要折回起点这个边界很多新手会漏。写完之后应该验证验证方式不是“看着对”而是跑数据。比如塞 10 万个 key先看三个节点分布均不均匀然后删掉一个节点统计被迁移的 key 比例是否接近三分之一func main() { ch : NewConsistentHash(160) ch.Add(svc-a) ch.Add(svc-b) ch.Add(svc-c) counts : make(map[string]int) for i : 0; i 100000; i { key : fmt.Sprintf(user-%d, i) counts[ch.Get(key)] } fmt.Println(分布情况:, counts) before : make(map[string]string, 100000) for i : 0; i 100000; i { key : fmt.Sprintf(user-%d, i) before[key] ch.Get(key) } ch.Remove(svc-b) moved : 0 for key, oldNode : range before { if ch.Get(key) ! oldNode { moved } } fmt.Printf(移除一个节点后被迁移的 key 比例: %.2f%%\n, float64(moved)/100000*100) }我每次改完一致性哈希代码都会跑一遍这个验证它能在几分钟内暴露哈希函数质量差、虚拟点数量不足、边界处理错误这类隐蔽问题。5.5 一致性哈希的几个边界问题第一空环。Get里必须先判断len(c.ring) 0返回空串调用方要处理“没有可用节点”的情况而不是 panic。第二重复添加节点。上面代码里用nodes集合做了去重否则同一个节点加两次等于多套虚拟点其他节点被挤占比例失衡。第三key 的设计。一致性哈希对“key 的分布”有要求如果你把 key 都设计成同一个前缀比如user_开头并且后面只有几个值那哈希环再均匀也没用。要避免热点 key办法是给 key 加随机后缀或者分桶前缀让它们在哈希空间里散开。第四它不适合“无条件均衡”的场景。如果只是想让流量平均分配一致性哈希不是最优解它牺牲了一部分均衡性换来了路由稳定性选型时要想清楚你到底要什么。6. 手写负载均衡最容易踩的坑以及怎么验证6.1 健康检查没有它所有算法都是盲选不管用哪个算法节点列表里混入了不健康的节点整个调度就是瞎子摸象。轮询会把请求发给已宕机的节点最少连接数会让计数全乱一致性哈希会让缓存请求持续打到故障节点上。健康检查分两种。主动检查是你的代码定期去探活比如每五秒连一次 TCP、拉一次健康接口失败就把它从节点列表里摘掉被动检查是监听真实请求的成功失败状态连续失败 N 次就把节点标记为不健康。工程上比较好的做法是两者结合主动探活保证“我知道它死了”被动检查保证“我及时知道它变慢了”。摘除和恢复都要延迟一点别一抖动就疯狂上下线常见做法是引入“半健康”状态连续成功几次才恢复上线避免节点在恢复边缘反复横跳。6.2 并发安全共享 map 是最常见的翻车现场手写负载均衡本质上就是一个多 goroutine 共享状态的并发组件。节点列表会被调用方并发读健康检查协程会并发写如果不加保护轻则读到脏数据重则直接 panic。我的习惯是读多写少的场景用读写锁像一致性哈希的Get用RLock节点变更用写锁选路逻辑本身必须和计数器更新放在同一个临界区里否则“选完再自增”就是一个明显的竞态窗口。另一个思路是把节点列表做成不可变快照变更时整体替换读取方永远拿到一份完整的旧快照这个方案在追求极致性能时很好用。6.3 超时与重试算法管得了选择管不了失败负载均衡算法能做的只是在你选节点时尽量选得合理。真正决定链路稳不稳的往往是选完之后的事。调用一个节点超时了你要不要换下一个节点重试要但必须克制。重试一次通常足够重试太多会在下游故障时形成重试风暴把本来还能扛的节点打垮。重试间隔要加随机抖动避免所有客户端在同一个时间点集中重试。另外重试只适合幂等请求。一个写操作第一次到底成没成功你是不知道的盲目重试有可能造成重复扣款、重复下单。负载均衡层能做的只是“换节点重发一次”至于业务上允不允许重复那是上层要判断的事。6.4 用数据验证算法而不是凭感觉手写算法最怕的就是“感觉没问题”。我建议你写一个简单的本地模拟器造 N 个模拟节点每个节点配置不同的处理耗时和失败率然后用真实请求量去压每个算法记录三个指标每个节点收到的请求数、平均响应时间、错误率。跑完一轮你通常会看到类似这样的结果算法节点接收比例典型表现轮询严格 1:1:1慢节点拖累整体时延加权轮询按权重但突刺明显瞬时排队时延抖动平滑加权轮询按权重且平滑整体时延更稳定最少连接数动态偏向快节点慢节点几乎被绕开一致性哈希按 key 固定统计近似均匀缓存命中率高节点增减影响小压测脚本也很好写无非是并发发请求、记录每个请求选中的节点和处理耗时。有了数据再选型比拍脑袋牢靠得多。我自己写完这套东西最深的一个体会是手写负载均衡最大的收获不是那几百行代码而是你终于理解了每个算法在“用什么信息换什么收益”。轮询用零信息换简单加权用配置信息换比例最少连接数用实时计数换反馈一致性哈希用均衡性换稳定性。线上出问题时你能一眼看出是哪一环的假设被打破了这比背下任何框架的配置项都值钱。