← 返回专栏列表

网络算法系列

共 10 篇文章

1. 轮询与加权轮询

轮询算法解决多节点负载均衡问题,将请求依次或按权重分发给后端服务器,被 Nginx、HAProxy、Kubernetes 等广泛采用。

2. 最小连接数

最小连接数算法解决请求处理时间不均匀场景下的负载均衡问题,将请求路由到当前活跃连接数最少的节点,被 Nginx least_conn、HAProxy、AWS ALB 等广泛采用。

3. Jump Consistent Hash

Jump Consistent Hash 用 5 行代码实现 O(1) 空间、O(ln N) 时间的一致性哈希,扩容时只迁移 1/(N+1) 的 key,被 Google 分布式存储和负载均衡系统广泛采用。

4. Rendezvous Hashing

Rendezvous Hashing(HRW)通过对每个候选节点计算 hash(key, node_id) 并选最高分实现分布式路由,无需虚拟节点即可天然均匀分布,被 Varnish Cache、Cassandra 和 CDN 边缘调度广泛采用。

5. TCP 拥塞控制(CUBIC 与 BBR)

TCP 拥塞控制解决发送方如何感知网络容量、在不造成拥塞的前提下最大化吞吐的问题,CUBIC 是 Linux 默认算法,BBR 是 Google 2016 年提出的基于带宽探测的新一代算法。

6. QUIC 丢包恢复与拥塞控制

QUIC 是基于 UDP 的应用层可靠传输协议,解决 TCP 的队头阻塞、连接建立延迟和中间盒僵化三大问题,是 HTTP/3 的传输层,被 Google、Cloudflare、Meta 大规模部署。

7. 经典一致性哈希(虚拟节点)

经典一致性哈希将哈希空间映射为环,节点和 key 均匀散布其上,扩缩容时只迁移 1/(N+1) 的数据;虚拟节点进一步解决物理节点数量少时的负载不均问题,是 Cassandra、Memcached、Amazon Dynamo 的核心分片机制。

8. P2C(Power of Two Choices)

P2C(Power of Two Choices)从服务器池中随机挑两台,选负载更低的那台转发请求;以 O(1) 时间实现接近最少连接算法的分布效果,是 Envoy、gRPC、Nginx Plus 的默认负载均衡策略。

9. TCP 滑动窗口与流量控制

TCP 滑动窗口是接收方向发送方通告「我还能接收多少字节」的机制,防止发送方淹没接收方缓冲区;与拥塞控制的 cwnd 共同决定有效发送速率,是 TCP 可靠传输的基础组成部分。

10. Maglev Hashing

Maglev Hashing 通过预计算一张固定大小的查找表将路由操作降至 O(1),同时保持与一致性哈希相同的最小迁移量(1/N),是 Google GFE(Google Frontend)负载均衡器的核心算法,也是 ECMP 路由的工业标准之一。