这篇文章是CMU Intel lab在2011年发表的，它高屋建瓴地提出：空间复杂度下界为O(nlogn)的cache（n为后端节点数）即可保证集群服务的负载均衡可靠性。建模和证明的过程非常巧妙，对cache design会很有启发。

摘要

在大规模的云计算服务中，为了避免后端节点过早暴露性能瓶颈、保证服务的SLO，以及更好地水平扩展，通常会在应用请求到达时经由一个load balancer处理，将请求平滑均匀地分发给后端节点。优秀的负载均衡能力是系统高吞吐，低延迟的前提。

但在生产环境中，没有cache加持的load balancer只能是阿克琉斯之踵：随著集群规模的动态变更，load balancer的partition规则不能保证负载被均匀地划分给各个后端节点；此外，请求负载的类型和分布无法预测，不排除DoS攻击的可能。系统设计者必须很小心地选择/组合load balancing策略，否则不同规格后端节点的处理能力将很容易成为系统瓶颈，被skewed load洪流击垮。

《Small Cache, Big Effect》提出：在load balancer中集成一层空间复杂度下界为O(nlogn)的cache（n为后端节点数！）来缓存热点数据，即可在显著提升load balancer吞吐量的同时，保证到达后端节点的请求负载是均匀分布的。

文中还给出了漂亮的证明过程和模拟结果，非常反直觉对吧？我们往下看。

small, fast cache at the front-end load balancer.

背景

简单讲一下处理负载均衡的两种方式：

  1. 静态处理。根据节点的处理能力（节点的规格，涉及CPU，内存，存储多个维度），load balancer可以对负载预先划分边界，能者多劳。对于hash-based的方法，例如consistent-hashing，引入virtual nodes实现环状hash空间的均匀散列（其实可以在virtual nodes中对节点的规格做分拆，为处理能力强的节点适当分配更多的virtual nodes）。
  2. 动态处理：就是负载均衡的策略选择了，从round-robin，least connections到the power of two random choices（one more random，big effect！这也很有意思，可以看文后的参考资料）。

建模/证明

为了模拟skewed load，文中假设了一个对抗型的请求模式（adversarial workload），请求要尽可能旁路cache，直接命中后端节点，与load balancer呈一个攻防态势。后文直接简称对抗模式。

首先对模型做几个假设吧：

  • key映射到后端节点的过程对客户端透明，且完全随机。
  • cache足够快。
  • cache永远持有最热的c（cache size）个key。
  • 后端节点处理单次请求负载的时间都一致。

再定义一些证明过程需要用到的符号，请别右上角：

  • c（cache size）；
  • n（后端节点数，）；
  • m（记录条数，即请求负载的目标）；
  • Li（划分给节点i的最大请求速率）；
  • ri（节点i的最大请求处理速率）；

请求的范围是所有key或者key的子集，那么对抗模式的请求策略可以用以下分布表示：

S = (p1, p2, ..., p(m))

p1，p2 ... pm即各个key的请求概率，和为1。为了方便证明，给它们排序一下，默认p1到pm降序排列。因为前c个key一定会被缓存，所以S实际上呈如下分布：

S: p1 geq p2 geq ... geq pc=h geq p(c+1) geq ... geq p(m)

对抗模式需要研究的是如何让分布在 p(c+1)~p(m) 这个范围的key，best effort地向后端节点发起请求，设这个临界的概率为h。因为同一个key一定会被hash到同一个节点（假设此过程节点数不变），所以对抗模式通过构造uncached keys对某个或某几个节点发起skewed queries，企图让这些后端节点达到最大负载，直到不可用。

这里再引入一个定理：

某两个未缓存的keyi和keyi， h geq p(i) geq p(j) geq 0 ，对抗模式可以构造一对新的概率：

p(i) = p(i) + delta, p(j) = p(j) - delta delta = minleft {h-p(i), p(j) ight }

实质就是负载可以在节点间转移，证明比较简单，感兴趣的同学可以看参考资料中的原文附录。对抗模式通过lantency等特征来判断key的热度，不断尝试转移负载，并调整keys的概率分布，尽可能多地构造请求概率同样为h的uncached keys，一波操作之后，设最后只剩下x个key。

此时能对系统产生威胁的keys的范围为(c+1)~(x)，共x-c个，如下图所示。

对抗模式构造的最佳keys概率分布

前面的假设中有一条，对每个key的请求都会随机分配给某个后端节点，这是经典的Balls into Bins模型：

M个ball依次随机地投入N个bin中（queries-for-keys依次随机地被分配给某个后端节点）。

当balls数量远大于bins时，负载最大的一个bin中balls数目有极大的概率遵循以下Balls into Bins模型的分布（硬核推导见参考资料中的原文）：

frac{M}{N} + alpha sqrt{2*frac{M}{N}*logN}

alpha>1 ，是一个常系数。在我们的场景中，N = n，M = x-c，那么负载最大的一个节点被分配的keys数遵循以下分布：

frac{x-c}{n} + alpha sqrt{2*frac{x-c}{n}*logn}

更近一步！假设对抗模式发起速率为R的请求，前x-1个key（那些请求概率为h的key）被平均分配到的速率为 R/(x-1) ，那么单节点的负载上界为：

egin{split} E[Lmax] &leq left ( frac{x-c}{n} + alpha sqrt{2*frac{x-c}{n}*logn} ight )*frac{R}{x-1} \ &= left ( frac{x-c}{x-1} + alpha sqrt{2*frac{x-c}{{(x-1)}^{2}}*n*logn} ight )*frac{R}{n} end{split}

若请求被完全均匀地分发给后端节点，那么每个后端节点处理的请求速率为 R/n ，为了得到这样的运算元，不等式的右侧乘上 frac{n}{x-1}*frac{x-1}{n} ，得到下一行的变换式。

在系统设计阶段，我们不知道哪个节点会承受最大的负载，所以需要为每个节点都预留最大负载所需的资源，严重拉低了整体的资源利用率，显然无法被接受。

对抗模式为了达成目的，要继续优化这个不等式，确定x值使得可能的负载最大化，R和n都可视作常量的话，即求 left ( frac{x-c}{x-1} + alpha sqrt{2*frac{x-c}{{(x-1)}^{2}}*n*logn} ight ) 这部分的最大值，换元求解一下可得函数极大值对应的x，这个x值也是对抗模式应该选取的最优值：

x^{*} = 1+2(c-1)left ( 1+frac{1}{sqrt{1+frac{2alpha^{2}nlogn}{c-1}}-1} ight )

把 x^{*} 代入原来的负载上界不等式，可以得到一个更简洁清晰的式子：

E[Lmax] leq frac{1+sqrt{1+2alpha^{2}frac{nlogn}{c-1}}}{2}*frac{R}{n}

那么单节点的最大吞吐量（最大负载）可以表示为：

frac{E[Lmax]}{R/n} leq frac{1+sqrt{1+2alpha^{2}frac{nlogn}{c-1}}}{2}

这个式子已经代表了cache size（c）和单节点最大负载的关系。为了让最大负载与节点数n无关，把根号下的分式因子消掉，只需要取c = k*nlogn + 1 = O(nlogn) ，k是一个常量系数。

O(nlogn)的空间复杂度是这么得出的！最终独立于节点数n的单节点max-load为：

frac{1}{2} * left ( 1+sqrt{1+frac{2alpha^{2}}{k}} ight )

可以通过调整系数k缩放max-load。对于异构的后端节点，可以参考负载静态处理方式中提到的：把一个physical node拆分成多个virtual nodes。

为每个节点预留max-load所需的资源，即可保证对抗模式发起的请求永远不会饱和。

模拟

以上模型还是有很多理想条件约束的，需要丢到模拟环境里摩擦一下，paper的作者利用1个高性能的前端节点和85个普通后端节点搭建了一个FAWN-KV集群，每个后端节点承担100k的kv键值对存储（key 20bytes / value 128bytes），所有节点与同一个交换机相连，网路不会成为瓶颈。

实验结果非常惊艳：

重点关注adversarial workload和uniform workload，可以明显看到加了cache之后，adversarial workload的吞吐和uniform workload几乎重合，完美符合推演。并且在cache加持下，这三种workload的吞吐和节点数n都呈线性关系。

总结

建模和模拟共同验证了这么一层薄薄的small-fast-cache对负载均衡效果的重大影响，我感觉它在load balancer中像是扮演了一个「filter」的角色，skewed load经由cache过滤，以足够uniform的分布被后端节点处理，很神奇但又很合理。

建模的过程遵循的是朴素的Balls into Bins模型，如果采用The Power of Two Random Choices的方法，max-load还可以进一步降低：

在balls into bins的基础上，一次选择d个bins（d≥2），把ball投入负载最低的bin中

The Power of Two Random Choices模型也很有意思，并且在负载均衡中已经成熟应用，大家可以参见参考资料自行了解。

当然了，建模过程中的很多假设是不能直接搬到真实环境中的，比如「cache只缓存最热的keys」，假设了一个perfect caching policy，但在现实中几乎做不到，诸如LRU、LRU的变种，这些缓存策略也只能在特定场景下做到逼近完美，并且维护key的状态，缓存的置换，保证cache consistency，都会有额外的开销；再比如「后端节点处理单次请求负载的时间都一致」，显然这在真实环境中无法保证。

除此之外，网路，多级缓存设计，读写分离等等都会成为影响最终性能的因素。

也许对于部署在纯应用层的load balancer， O(nlogn) 的指标意义没有特别大，毕竟内存可以放心糟蹋，但对cache的容量规划，命中率与内存利用率的兼顾，还是有一定指导意义的。重点在于，这样经过验证的轻量级缓存，完全可以集成进专有硬体中，比如CPU的L3 cache，甚至是L2 cache，做到真正的 small and fast。

以上。更详细的内容请参见原文，如有不当之处欢迎指出 :)

参考资料：

暗淡了乌云：The Power of Two Random Choices?

zhuanlan.zhihu.com图标「Balls into Bins」 — A Simple and Tight Analysis?

www.dblab.ntua.gr

Small Cache, Big Effect: Provable Load Balancing for. Randomly Partitioned Cluster Services?

www.cs.cmu.edu

The Power of Two Random Choices: A Survey of Techniques and Results?

www.eecs.harvard.edu

古文：[Paper Review]FAST19 DistCache?

zhuanlan.zhihu.com图标
推荐阅读：

相关文章