负载均衡 Misc

http://blog.me115.com/2015/11/886

Round Robin 轮询调度

以轮询的方式依次请求调度不同的服务器； 
实现时，一般为服务器带上权重；这样有两个好处：

1. 针对服务器的性能差异可分配不同的负载；
2. 当需要将某个结点剔除时，只需要将其权重设置为0即可；

优点：实现简单、高效；易水平扩展； 
缺点：请求到目的结点的不确定，造成其无法适用于有写的场景（缓存，数据库写） 
应用场景：数据库或应用服务层中只有读的场景；

随机方式

请求随机分布到各个结点；在数据足够大的场景能达到一个均衡分布； 
优点：实现简单、易水平扩展； 
缺点：同Round Robin，无法用于有写的场景； 
应用场景：数据库负载均衡，也是只有读的场景；

哈希方式

根据key来计算需要落在的结点上，可以保证一个同一个键一定落在相同的服务器上； 
优点：相同key一定落在同一个结点上，这样就可用于有写有读的缓存场景； 
缺点：在某个结点故障后，会导致哈希键重新分布，造成命中率大幅度下降； 
解决：一致性哈希 or 使用keepalived保证任何一个结点的高可用性，故障后会有其它结点顶上来； 
应用场景：缓存，有读有写；

一致性哈希

在服务器一个结点出现故障时，受影响的只有这个结点上的key，最大程度的保证命中率； 
如twemproxy中的ketama方案； 
生产实现中还可以规划指定子key哈希，从而保证局部相似特征的键能分布在同一个服务器上； 
优点：结点故障后命中率下降有限； 
应用场景：缓存；

根据键的范围来负载

根据键的范围来负载，前1亿个键都存放到第一个服务器，1~2亿在第二个结点； 
优点：水平扩展容易，存储不够用时，加服务器存放后续新增数据； 
缺点：负载不均；数据库的分布不均衡；（数据有冷热区分，一般最近注册的用户更加活跃，这样造成后续的服务器非常繁忙，而前期的结点空闲很多） 
适用场景：数据库分片负载均衡；

根据键对服务器结点数取模来负载；

根据键对服务器结点数取模来负载；比如有4台服务器，key取模为0的落在第一个结点，1落在第二个结点上。 
优点：数据冷热分布均衡，数据库结点负载均衡分布； 
缺点：水平扩展较难； 
适用场景：数据库分片负载均衡；

纯动态结点负载均衡

根据CPU、IO、网络的处理能力来决策接下来的请求如何调度； 
优点：充分利用服务器的资源，保证个结点上负载处理均衡； 
缺点：实现起来复杂，真实使用较少；

不用主动负载均衡；

使用消息队列转为异步模型，将负载均衡的问题消灭 
负载均衡是一种推模型，一直向你发数据，那么，将所有的用户请求发到消息队列中，所有的下游结点谁空闲，谁上来取数据处理；转为拉模型之后，消息了负载的问题； 
优点：通过消息队列的缓冲，保护后端系统，请求剧增时不会冲垮后端服务器； 
水平扩展容易，加入新结点后，直接取queue即可； 
缺点：不具有实时性； 
应用场景：不需要实时返回的场景； 
比如，12036下订单后，立刻返回提示信息：您的订单进去排队了…等处理完毕后，再异步通知；

相关开源工具

• HAProxy：可用来做redis多个结点的负载均衡、也可做mysql等数据库的负载、支持4层负载和7层负载；（一般配合Keepalived做高可用）
• Twemproxy：用来做redis的结点的分片、redis的存储受限与单个结点的内存容量，数据量大到需要分片，使用twemproxy可做到对业务层透明的分片； 
  twemproxy也是使用的单线程reactor模型，一个twemproxy后端接再多的redis结点，其能够支撑的TPS不会超过单个redis结点的处理能力，使用时需要启动多个twemproxy对外提供查询结点；
• nginx：目前的明星开源产品，只支持7层负载，除了用于反向代理负载均衡，更出名的是作为WEB服务器；
• LVS：使用Linux内核集群实现一个高性能、高可用的负载均衡服务器，采用IP负载均衡技术和基于内容请求分发技术。未用过这个，有兴趣的同学可看看这篇文章：http://www.ha97.com/5646.html；

leetcode面试题6 负载均衡

设计一个用于负载均衡的数据结构，支持加入一台机器，撤出一台机器，在活跃的机器集合中"等概率"随机选中一台机器。以上三个操作要尽可能的快。

解答

用一个数组记录当前的活跃机器集，用一个hash记录某个机器在数组中的位置。对于等概率随机选中一台机器，random(数组长度)选中一台机器；对于加入一台机器，在数组最后添加，并记录在hash表中；对于撤出一台机器，先用hash表找到其在数组中的对应位置，用数组最后一个位置的机器和它交换，并在hash表中删除撤出的机器并修改被交换的机器的位置，这样做的目的是保证数组中不会出现空位，这样才能保证随机操作的正确性和高效。三个操作的时间复杂度均为O(1)。

面试官视角：

本题中描述的负载均衡是用于Web Server的负载均衡，并不是存储的负载均衡，所以无需考虑新增加的机器需要尽量多的承载访问请求，所以如果往一致性哈希(Consistent Hash)的方向考虑就错了。本题是纯粹的数据结构题，并非设计题。当看到加入一台机器和撤出一台机器的时候，自然会想到使用hash表来支持O(1)的插入和O(1)的删除。但普通的hash表是不支持等概率随机访问的。想要支持等概率随机访问，那最简单的方法当然是地址空间连续的数组。因此想到结合两种数据结构。剩下来需要解决的问题就是如果让数组支持O(1)的删除并让数组没有空位。一个思维误区是整体移动后面的数据。实际上由于数组所代表的内容是集合，无需保证其结果的连续性，因此采用类似堆中删除元素的操作方法――用最后一个元素覆盖待删除元素，即可解决问题。 本题的考点主要是对于各种数据结构的灵活使用，需要对数组，hash表，甚至堆有一定的了解。

Read full article from leetcode面试题6 负载均衡