JIQ 是微软发的一篇论文《Join-Idle-Queue: A Novel Load Balancing Algorithm for Dynamically Scalable Web Services》里描述的负载均衡算法，这里总结下我所理解的内容。 背景 负载均衡很常见，比如我们经常用 nginx 做反向代理和负载均衡，Nginx 也支持了 weight、ip_hash、url_hash 等均衡算法。 负载均衡的图示： 任务 jobs 不停地经由多个 dispatcher 转发给后面的 processor server 处理。 dispatcher 选择哪一条 processor 来转发任务的过程就是 load balance 的核心问题。尽量降低任务的响应时间是我们的目标。 最简单的算法可能是随机或者轮询，但是这种简单的策略会造成响应时间的最大化，特别是高负载的情况下。 更优化的策略有： JSQ： Join-the-Shortest-Queue，每次将任务加入最少任务队列的 server。这就要求 dispatcher 收集每个 processor server 的任务队列大小信息，但是随着 dispatcher 本身的集群化以及云服务厂商的大规模应用，这个收集产生的网络通讯就更加膨胀了。 SQ(d)（Power-of-d）：每当任务到达的时候， dispatcher 就随机取样 d 个 processor 服务的队列大小，选择最小任务队列的那个派发。通常 d 选择为 2。这个算法相比随机算法能带来响应时间指数级别的提升。但是仍然需要在分发任务的时候获取 processor 队列信息，这个同步调用在任务派发的关键路径上，对性能有很大影响。 工作窃取和共享：工作窃取就是空闲队列主动去从其他任务队列『窃取』任务，或者繁忙的队列主动将任务『推送』给其他空闲队列。这个算法更适合共享内存的系统，对于 web 负载均衡，在不同后端 server 之间做任务的窃取或者推送会带来额外的开销和复杂度，想象一个 web http 请求如何转交到另一台后端 server，涉及 TCP 链接的迁移和请求的同步等等。 JIQ 全称就是 Join-Idle-Queue，它的提出就是为了解决大规模 Web Services 的负载均衡问题。