摘要

    

    超级负载均衡旨在为解决服务不断扩展、机器不断增多、机器性能差异等问题，以增强系统的稳定性，自动分配请求压力。算法实现了多个模型和均衡策略，能通过配置实现随机、轮询、一致hash等。同时也能实现跨机房的相关分配。现已经在多个系统中使用。

    TAG

    负载均衡

    内容

    现有系统中存在的问题：

    

    1. 慢连接、瞬时访问慢。

    场景一：

    如果后端新增加机器，cache命中率低，因此响应速度慢，但是能连接上且不超时。如果ui持续访问就会把ui夯住。

    场景二：

    如果后端模块某一台机器响应较慢。如果前端持续访问就会被夯住。

    2. 死机。

    场景一：

    能断断续续响应请求，不过速度很慢。造成ui夯住。

    3. 混合部署。

    场景一：

    多个模块在同一机器上，项目影响。

    4. 机器权重。

    场景一：

    老机器，性能差；新机器，性能彪悍。因此他们应该承载不同的压力。

    5. 跨机房冗余。

    场景一：

    后端对cache依赖很高的模块，因为采用的是一致hash算法，如果挂掉一台机器，对另外的机器cache命中率冲击很大。因此希望将对这个机器的请求均衡到另外一个机房。

    6. php和c使用同样的策略。

    现在php和c希望能使用的策略实际上是有很大的一致。为了避免重复开发，php和c希望采用同样的负载均衡库。

    要解决的问题：

    

    设计思路：

    1. 根据均衡策略计算出的均衡值对Server进行逆序排序。

    2. 负载选择。对步骤1排序后的Server按以下顺序进行选择：

    a、按连接失败概率进行选择。

    

    注：横轴代表失败次数，纵轴代表选择的概率。

    Cconn：一段区间内失败次数

    f(Cconn)：连接概率，取值范围在(0，100]

    b、按健康状态选择。

    整个模型基于服务处理时间的收敛性。

    分析：

    1) 如果机器状态良好，则平均处理时间会保持在一个稳定水平；即使是小波动，也会较快平稳在一个状态。

    2) 如果机器开始出现问题，处理时间会开始增长。如果增长持续超过一段时间，则说明有可能会影响服务；如果一段时间后稳定了，说明对请求没有太多影响。

    f(healthy)：机器健康状态，取值范围[0,1]

    select(healthy)：机器选择概率，取值范围[R,1]

    c、如果所有机器都没选中，则随机选择一台机器进行服务。

    3. 机器流量均分。

    不同的机器处理能力是不一样的。当按照步骤2选择了某台机器，需要将其他处理时间为他的1/T(T>=2)的机器也选取出来，将部分压力分给对应的机器。

    设k台机器的处理时间分别是t1, t2,…,tk, 选中的机器id＝i，比该机器处理能力高的机器时间分别为p1,p2,..,pr, (其中pj × T <= ti)。设一段时间总访问量为Y，每台机器理论上的访问量应该为Vg=Y/k。而实际的Vr=Y/(ti * (1/t1+1/t2+…+1/tk))。则应该分出Vg-Vr的流量给pj。pj的流量比例为1/p1:1/p2:…:1/pr

    算法设计：

    A、均衡算法

    1. 一致hash算法。

    将每个server的ip和port加上balance_key三者做字符串拼接后，做md5签名。

    value(server) = md5(server_ip + server_port + balance_key)

    2. 随机算法。

    value(server) = random();

    3. 轮询算法。

    value(server) =((server.id - (rounds ％ server_count)) + server_count) % server_count

4. 多个选一算法。

rank初始化为1， 如果默认的server失败，则rank＋1

value(server) =((server.id - (rank ％ server_count)) + server_count) % server_count

B、负载算法

1. 连接状态算法。

a、对每一个server开辟一个状态队列。bool queue[K] 用来统计失败次数。每次有坏状态进队，计数加一。如果有坏状态出队，则计数减一。

b、按照f(Cconn)公式计算出选择概率。

c、利用rand()%100是否在[0,f(Cconn)]来决定是否选择该机器。

2. 健康状态算法。

a、每台机器维持一个一秒钟内的处理时间T和次数C。

b、当一秒过去以后，将T、C计算为平均处理时间R。

c、每M秒，统计每台机器最近一段时间的平均处理时间， 按照公式select（healthy）算出选择概率。

d、利用rand()%100是否在[0, select(healthy)*100]来决定是否选择该机器。

C、流量均分

按照策略选出满足要求的机器，按照流量均分公式进行流量分配。

分配时按照balance_key＋server方式和random（）来分配机器， 尽量保证请求落在同一台机器。

by wangbo

建议继续学习：

1. 解析nginx负载均衡    (阅读：14453)
2. 使用HAProxy对MySQL进行负载均衡和状态监控    (阅读：5567)
3. 趣图三幅：负载均衡算法需要改进    (阅读：3846)
4. 服务框架演变过程    (阅读：3645)
5. “集群和负载均衡”的通俗版解释    (阅读：3482)
6. “集群和负载均衡”在实战当中的运用技巧    (阅读：3336)
7. 使用Apache做负载均衡    (阅读：2605)
8. RAC的负载均衡    (阅读：2562)
9. 关于负载均衡和过载保护的一些想法和实现    (阅读：2526)
10. puppetca 高可用性以及负载均衡配置    (阅读：2032)