负载均衡技术原理及分类

介绍

面对大量用户访问、高并发请求,海量数据,可以使用高性能的服务器、大型数据库,存储设备,高性能Web服务器,采用高效率的编程语言比如(Go,Scala)等,当单机容量达到极限时,我们需要考虑业务拆分和分布式部署,来解决大型网站访问量大,并发量高,海量数据的问题。

从单机网站到分布式网站,很重要的区别是业务拆分和分布式部署,将应用拆分后,部署到不同的机器上,实现大规模分布式系统。分布式和业务拆分解决了,从集中到分布的问题,但是每个部署的独立业务还存在单点的问题和访问统一入口问题,为解决单点故障,我们可以采取冗余的方式。将相同的应用部署到多台机器上。解决访问统一入口问题,我们可以在集群前面增加负载均衡设备,实现流量分发。

负载均衡(Load Balance),意思是将负载(工作任务,访问请求)进行平衡、分摊到多个操作单元(服务器,组件)上进行执行。是解决高性能,单点故障(高可用),扩展性(水平伸缩)的终极解决方案。

系统的扩展可分为纵向(垂直)扩展和横向(水平)扩展。纵向扩展,是从单机的角度通过增加硬件处理能力,比如CPU处理能力,内存容量,磁盘等方面,实现服务器处理能力的提升;而单机能力总有上限,因此需要采用横向扩展的方式,通过添加更多机器来提升更强的系统处理能力。比如:一台机器不能满足,则增加两台或者多台机器,共同承担访问压力。在分布式系统中相同的服务常常会部署很多台,每一台被称为一个服务节点(实例)。通过一些负载均衡策略将服务请求均匀地分布到各个节点,以实现整个系统支撑海量请求的需求。

负载均衡的作用(解决的问题):

  1. 解决并发压力,提高应用处理性能(增加吞吐量,加强网络处理能力);
  2. 提供故障转移,实现高可用;
  3. 通过添加或减少服务器数量,提供网站伸缩性(扩展性);
  4. 安全防护;(负载均衡设备上做一些过滤,黑白名单等处理)

负载均衡虽然理解起来简单,但实现方式就很多了,可大可小;可以软件实现,也可以硬件实现,由于涉及的技术很多,这里只是简单的介绍常用技术。

负载均衡分类

DNS负载均衡

DNS是最简单的、也是最常见的负载均衡方式,一般用来实现地理级别的均衡,例如北方的用户访问北京的机房,南方的用户访问广州的机房;一般不太会使用DNS来做机器级别的负载均衡,因为太耗费IP资源了,例如百度搜索可能要10000台机器以上,不可能将这么多机器全部配置公网ip然后用DNS来做负载均衡。有兴趣的同学可以在linux用 dig baidu.com命令看看实际上用了几个ip地址。

优点

  • 使用简单:负载均衡工作,交给DNS服务器处理,省掉了负载均衡服务器维护的麻烦
  • 提高性能:可以支持基于地址的域名解析,解析成距离用户最近的服务器地址,可以加快访问速度,改善性能;

缺点

  • 可用性差:DNS解析是多级解析,新增/修改DNS后,解析时间较长;解析过程中,用户访问网站将失败;
  • 扩展性低:DNS负载均衡的控制权在域名商那里,无法对其做更多的改善和扩展;
  • 维护性差:也不能反映服务器的当前运行状态;支持的算法少;不能区分服务器的差异(不能根据系统与服务的状态来判断负载)

所以对于时延和故障敏感的业务,有一些公司自己实现了HTTP-DNS的功能,即:使用http协议实现一个私有的DNS系统。这样的方案和通用的DNS优缺点正好相反。

硬件负载均衡

采用硬件的方式实现负载均衡,一般是单独的负载均衡服务器,价格昂贵,一般土豪级公司可以考虑,业界领先的有两款,F5和A10。

使用硬件负载均衡,主要考虑一下几个方面:

  • 功能考虑:功能全面支持各层级的负载均衡,支持全面的负载均衡算法,支持全局负载均衡;
  • 性能考虑:硬件远远高于软件,一般软件负载均衡支持到5万级并发已经很困难了,硬件负载均衡可以支持;
  • 稳定性:商用硬件负载均衡,经过了良好的严格的测试,从经过大规模使用,在稳定性方面高;
  • 安全防护:硬件均衡设备除具备负载均衡功能外,还具备防火墙,防DDOS攻击等安全功能;
  • 维护角度:提供良好的维护管理界面,售后服务和技术支持;
  • 土豪公司:F5 Big Ip 价格:15w~55w不等;A10 价格:55w-100w不等;

缺点:

  • 价格昂贵;
  • 扩展能力差;

再加上即使硬件的负载均衡也要做双机高可用,因此成本会更高。比如互联网公司通常使用开源软件,小公司甚至都不一定有负载均衡的考虑,因为当前大部分应用采用了软件负载均衡,也就核心应用采用硬件负载均衡,或者说可以使用几台F5做全局负载均衡,内部使用Nginx等软件负载均衡。

软负载均衡(Nginx & LVS & HA)

DNS用于实现地理级别的负载均衡,而Nginx&LVS&HA就是用于同一地点内机器级别的负载均衡。其中Nginx是软件的7层负载均衡,LVS是内核的4层负载均衡。

4层和7层的区别就在于协议和灵活性。Nginx支持HTTP、Email协议,而LVS和F5是4层负载均衡,和协议无关,几乎所有应用都可以做,例如聊天、数据库等。

更多详细信息可以google去查,例如:Nginx、LVS及HAProxy负载均衡软件的优缺点详解

如下图形象的展示了一个实际请求过程中,地理级别的负载均衡和机器级别的负载均衡是如何分工和结合的,其中蓝色线是地理级别的负载均衡,红色线是机器级别的负载均衡:

dns_lvs

Ngnix负载均衡

Ngnix是一款轻量级的Web服务器/反向代理服务器,工作在七层Http协议的负载均衡系统。具有高性能、高并发、低内存使用等特点。是一个轻量级的Http和反向代理服务器。Nginx使用epoll 和 kqueue作为开发模型。能够支持高达 50,000 个并发连接数的响应。
Ngnix的负载均衡策略可以划分为两大类:内置策略和扩展策略。内置策略包含加权轮询和ip hash,在默认情况下这两种策略会编译进nginx内核,只需在nginx配置中指明参数即可。扩展策略有很多,如fair、通用hash、consistent hash等,默认不编译进nginx内核。由于在nginx版本升级中负载均衡的代码没有本质性的变化,因此下面将以nginx1.0.15稳定版为例,从源码角度分析各个策略。

Ngnix的负载均衡策略
  • 加权轮询(weighted round robin)
    轮询的原理很简单,首先我们介绍一下轮询的基本流程。如下是处理一次请求的流程图:

    Ngnix_RoundRobin

图中有两点需要注意,第一,如果可以把加权轮询算法分为先深搜索和先广搜索,那么nginx采用的是先深搜索算法,即将首先将请求都分给高权重的机器,直到该机器的权值降到了比其他机器低,才开始将请求分给下一个高权重的机器;第二,当所有后端机器都down掉时,nginx会立即将所有机器的标志位清成初始状态,以避免造成所有的机器都处在timeout的状态,从而导致整个前端被夯住。

  • IP Hash
    ip hash是nginx内置的另一个负载均衡的策略,流程和轮询很类似,只是其中的算法和具体的策略有些变化,如下图所示:

Ngnix_IpHash

  • fair
    fair策略是扩展策略,默认不被编译进nginx内核。其原理是根据后端服务器的响应时间判断负载情况,从中选出负载最轻的机器进行分流。这种策略具有很强的自适应性,但是实际的网络环境往往不是那么简单,因此要慎用。

  • 通用hash、一致性hash
    这两种也是扩展策略,在具体的实现上有些差别,通用hash比较简单,可以以nginx内置的变量为key进行hash,一致性hash采用了nginx内置的一致性hash环,可以支持memcache。

Ngnix 负载均衡的适合场景

Ngnix一般作为入口负载均衡或内部负载均衡,结合反向代理服务器使用。以下架构示例,仅供参考,具体使用根据场景而定。

  • 入口负载均衡架构

Ngnix_LB_1

Ngnix服务器在用户访问的最前端。根据用户请求再转发到具体的应用服务器或二级负载均衡服务器(LVS)。

  • 内部负载均衡架构

Ngnix_LB_2
LVS作为入口负载均衡,将请求转发到二级Ngnix服务器,Ngnix再根据请求转发到具体的应用服务器。

  • Ngnix高可用
    Ngnix_LB_3
    分布式系统中,应用只部署一台服务器会存在单点故障,负载均衡同样有类似的问题。一般可采用主备或负载均衡设备集群的方式节约单点故障或高并发请求分流。Ngnix高可用,至少包含两个Ngnix服务器,一台主服务器,一台备服务器,之间使用Keepalived做健康监控和故障检测。开放VIP端口,通过防火墙进行外部映射。

LVS负载均衡

LVS是一个开源的软件,由毕业于国防科技大学的章文嵩博士于1998年5月创立,用来实现Linux平台下的简单负载均衡。LVS是Linux Virtual Server的缩写,意思是Linux虚拟服务器。

基于IP层的负载均衡调度技术,它在操作系统核心层上,将来自IP层的TCP/UDP请求均衡地转移到不同的 服务器,从而将一组服务器构成一个高性能、高可用的虚拟服务器。

LVS的主要功能是实现IP层(网络层)负载均衡,有NAT,TUN,DR三种请求转发模式。

LVS/NAT方式的负载均衡集群

NAT是指Network Address Translation,它的转发流程是:Director机器收到外界请求,改写数据包的目标地址,按相应的调度算法将其发送到相应Real Server上,Real Server处理完该请求后,将结果数据包返回到其默认网关,即Director机器上,Director机器再改写数据包的源地址,最后将其返回给外界。这样就完成一次负载调度。

构架一个最简单的LVS/NAT方式的负载均衡集群Real Server可以是任何的操作系统,而且无需做任何特殊的设定,惟一要做的就是将其默认网关指向Director机器。Real Server可以使用局域网的内部IP(192.168.0.0/24)。Director要有两块网卡,一块网卡绑定一个外部IP地址 (10.0.0.1),另一块网卡绑定局域网的内部IP(192.168.0.254),作为Real Server的默认网关。

LVS/NAT方式实现起来最为简单,而且Real Server使用的是内部IP,可以节省Real IP的开销。但因为执行NAT需要重写流经Director的数据包,在速度上有一定延迟;当用户的请求非常短,而服务器的回应非常大的情况下,会对Director形成很大压力,成为新的瓶颈,从而使整个系统的性能受到限制。

LVS/TUN方式的负载均衡集群

TUN是指IP Tunneling,它的转发流程是:Director机器收到外界请求,按相应的调度算法,通过IP隧道发送到相应Real Server,Real Server处理完该请求后,将结果数据包直接返回给客户。至此完成一次负载调度。

最简单的LVS/TUN方式的负载均衡集群架构使用IP Tunneling技术,在Director机器和Real Server机器之间架设一个IP Tunnel,通过IP Tunnel将负载分配到Real Server机器上。Director和Real Server之间的关系比较松散,可以是在同一个网络中,也可以是在不同的网络中,只要两者能够通过IP Tunnel相连就行。收到负载分配的Real Server机器处理完后会直接将反馈数据送回给客户,而不必通过Director机器。实际应用中,服务器必须拥有正式的IP地址用于与客户机直接通信,并且所有服务器必须支持IP隧道协议。

该方式中Director将客户请求分配到不同的Real Server,Real Server处理请求后直接回应给用户,这样Director就只处理客户机与服务器的一半连接,极大地提高了Director的调度处理能力,使集群系统能容纳更多的节点数。另外TUN方式中的Real Server可以在任何LAN或WAN上运行,这样可以构筑跨地域的集群,其应对灾难的能力也更强,但是服务器需要为IP封装付出一定的资源开销,而且后端的Real Server必须是支持IP Tunneling的操作系统。

LVS/TUN方式的负载均衡集群

DR是指Direct Routing,它的转发流程是:Director机器收到外界请求,按相应的调度算法将其直接发送到相应Real Server,Real Server处理完该请求后,将结果数据包直接返回给客户,完成一次负载调度。

构架一个最简单的LVS/DR方式的负载均衡集群Real Server和Director都在同一个物理网段中,Director的网卡IP是192.168.0.253,再绑定另一个IP: 192.168.0.254作为对外界的virtual IP,外界客户通过该IP来访问整个集群系统。Real Server在lo上绑定IP:192.168.0.254,同时加入相应的路由。

LVS/DR方式与前面的LVS/TUN方式有些类似,前台的Director机器也是只需要接收和调度外界的请求,而不需要负责返回这些请求的反馈结果,所以能够负载更多的Real Server,提高Director的调度处理能力,使集群系统容纳更多的Real Server。但LVS/DR需要改写请求报文的MAC地址,所以所有服务器必须在同一物理网段内。

LVS的负载均衡策略

LVS默认支持八种负载均衡策略(除此之外还可以自定义均衡策略),简述如下:

  1. 轮询调度(Round Robin)
    调度器通过“轮询”调度算法将外部请求按顺序轮流分配到集群中的真实服务器上,它均等地对待每一台服务器,而不管服务器上实际的连接数和系统负载。
  2. 加权轮询(Weighted Round Robin)
    调度器通过“加权轮询”调度算法根据真实服务器的不同处理能力来调度访问请求。这样可以保证处理能力强的服务器能处理更多的访问流量。调度器可以自动问询真实服务器的负载情况,并动态地调整其权值。
  3. 最少链接(Least Connections)
    调度器通过“最少连接”调度算法动态地将网络请求调度到已建立的链接数最少的服务器上。如果集群系统的真实服务器具有相近的系统性能,采用“最小连接”调度算法可以较好地均衡负载。
  4. 加权最少链接(Weighted Least Connections)
    在集群系统中的服务器性能差异较大的情况下,调度器采用“加权最少链接”调度算法优化负载均衡性能,具有较高权值的服务器将承受较大比例的活动连接负载。调度器可以自动问询真实服务器的负载情况,并动态地调整其权值。
  5. 基于局部性的最少链接(Locality-Based Least Connections)
    “基于局部性的最少链接”调度算法是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。该算法根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器超载且有服务器处于一半的工作负载,则用“最少链接” 的原则选出一个可用的服务器,将请求发送到该服务器。
  6. 带复制的基于局部性最少链接(Locality-Based Least Connections with Replication)
    “带复制的基于局部性最少链接”调度算法也是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要维护从一个目标IP地址到一组服务器的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。该算法根据请求的目标IP地址找出该目标IP地址对应的服务器组,按“最小连接”原则从服务器组中选出一台服务器,若服务器没有超载,将请求发送到该服务器;若服务器超载,则按“最小连接”原则从这个集群中选出一台服务器,将该服务器加入到服务器组中,将请求发送到该服务器。同时,当该服务器组有一段时间没有被修改,将最忙的服务器从服务器组中删除,以降低复制的程度。
  7. 目标地址散列(Destination Hashing)
    “目标地址散列”调度算法根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。
  8. 源地址散列(Source Hashing)
    “源地址散列”调度算法根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。
LVS负载均衡的适用场景

一般作为入口负载均衡或内部负载均衡,结合反向代理服务器使用。相关架构可参考Ngnix场景架构。

HaProxy负载均衡

HAProxy也是使用较多的一款负载均衡软件。HAProxy提供高可用性、负载均衡以及基于TCP和HTTP应用的代理,支持虚拟主机,是免费、快速并且可靠的一种解决方案。特别适用于那些负载特大的web站点。运行模式使得它可以很简单安全的整合到当前的架构中,同时可以保护你的web服务器不被暴露到网络上。

  • HaProxy特点

    • 支持两种代理模式:TCP(四层)和HTTP(七层),支持虚拟主机;
    • 配置简单,支持url检测后端服务器状态;
    • 做负载均衡软件使用,在高并发情况下,处理速度高于nginx;
    • TCP层多用于Mysql从(读)服务器负载均衡。 (对Mysql进行负载均衡,对后端的DB节点进行检测和负载均衡)
    • 能够补充Nginx的一些缺点比如Session的保持,Cookie引导等工作
  • 均衡策略

    • roundrobin:轮询,轮流分配到后端服务器;
    • static-rr:根据后端服务器性能分配;
    • leastconn:最小连接者优先处理;
    • source:根据请求源IP,与Nginx的IP_Hash类似。

CDN负载均衡

CDN是为了解决用户网络访问时的“最后一公里”效应,本质上是一种“以空间换时间”的加速策略,即:将内容缓存在离用户最近的地方,用户访问的是缓存的内容,而不是站点实时的内容。

但CDN经过这么多年的发展,已经变成了一个很庞大的体系:分布式存储、全局负载均衡、网络重定向、流量控制等都属于CDN的范畴了,本文寥寥数语很难全面覆盖,有兴趣的可以独立深入去研究。

幸运的是,大部分程序员和架构师都不太需要深入理解CDN的细节,因为CDN作为网络的基础服务,独立搭建的成本巨大,很少有公司自己设计和搭建CDN系统,都是从CDN服务商购买CDN服务即可。

多机房负载均衡

从架构上来说,单机房就是一个全局的网络单点,在发生比较大的故障或者灾害时,单机房难以保证业务的高可用。例如:停电、机房网络中断、地震、水灾。。。。。。等都有可能导致一个机房完全瘫痪。很多人以为这种事情的概率比较低,其实这种认识是错误的。停电和机房空调或者网络坏掉这种事故,运气好一年一两次,运气不好一年5、6次;水灾导致的停电在东南沿海几乎年年有,2013年汕头水灾导致整个机房被水淹了。所以机房故障要作为我们设计必须考虑的一个因素。

多机房设计最核心的设计因素就是如何处理时延带来的影响,常见的策略有:

  • 同城多机房

同一个城市多个机房,距离不会太远,可以投入重金,搭建私有的高速网络,基本上能够做到和同机房一样的效果。
这种方式对业务影响很小,但投入较大,如果不是土豪公司,一般是承受不起的;而且遇到极端的地震、2013年汕头水灾这样自然灾害,同城多机房也是有很大风险的。

  • 跨城多机房

在不同的城市搭建多个机房,机房间通过网络进行数据复制(例如MySQL主备复制),但由于跨城网络时延的问题,业务上需要做一定的妥协和兼容,不需要数据的实时强一致性,保证最终一致性。
例如微博类产品,B用户关注了A用户,A用户在北京机房发布了一条微博,B在广州机房不需要立刻看到A用户发的微博,等10分钟看到也可以。
这种方式实现简单,但和业务有很强的相关性,例如微博可以这样做,支付宝就不能这样做。

  • 跨国多机房

和跨城多机房类似,只是地理上分布更远,时延更大。由于时延太大和用户跨国访问实在太慢,跨国多机房一般仅用于备份和服务本国用户。

多中心

多中心必须以多机房为前提,但从设计的角度来看,多中心相比多机房是本质的飞越,难度也高出一个等级。

简单来说,多机房的主要目标是灾备,当机房故障的时候,我们可以比较快速的将业务切换到另外一个机房,这种切换操作允许一定时间的中断(例如10分钟、1个小时),而且业务也可能有损失,例如某些未同步的数据可能就不能马上恢复,或者要等几天才恢复,甚至永远都不能恢复了。但多中心的要求就高多了,要求每个中心都同时对外提供服务,且业务能够自动在多中心之间切换,故障后不需人工干预或者很少人工干预就能自动恢复。

多中心设计的关键就在于“数据一致性”和“数据事务性”如何保证,但这两个难点都和业务紧密相关,不存在通用的解决方案,需要基于业务的特性进行详细的分析和设计。以淘宝为例,淘宝对外宣称自己是多中心的,但是在实际设计过程中,商品浏览的多机房方案、订单的多机房方案、支付的多机房方案都需要独立设计和实现。

正因为多中心设计的复杂性,不一定所有业务都能实现多中心,目前国内的银行、支付宝这类系统就没有完全实现多中心。不然也就不会出现蓝翔挖掘机一铲子下去,支付宝中断4小时的故障。

负载均衡常用策略

Round-Robin

简单地轮询,将所有请求,依次分发到每台服务器上,适合服务器硬件同相同的场景。具体实现时记录一个选择位置,每次请求来时调整该位置到下一个节点:

curId = ++curId % nodeCnt

优点:服务器请求数目相同;

缺点:服务器压力不一样,不适合服务器配置不同的情况;

随机选择

随机地在所有节点中选择:

id = random(nodeCnt);

优点:使用简单;

缺点:不适合机器配置不同的场景;

最少链接

将请求分配到连接数最少的服务器(目前处理请求最少的服务器)。

优点:根据服务器当前的请求处理情况,动态分配;

缺点:算法实现相对复杂,需要监控服务器请求连接数;

Hash(源地址散列)

根据IP地址进行Hash计算,得到IP地址。

优点:将来自同一IP地址的请求,同一会话期内,转发到相同的服务器;实现会话粘滞。

缺点:目标服务器宕机后,会话会丢失;

Weighted Round-Robin(加权轮询)

相对于普通轮询而言,该策略中每一个节点都有自己的权重,优先选择权重更大的节点,通过加权的方式进行负载服务器的分配。权重可以根据机器性能预先配置。

优点:根据权重,调节转发服务器的请求数目;

缺点:使用相对复杂;

摘抄一下网上的算法:

假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1,cw初始化为零。

while (true) {
  i = (i + 1) mod n;
  if (i == 0) {
     cw = cw - gcd(S); 
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  } 
  if (W(Si) >= cw) 
    return Si;
}

遍历完所有节点后权重衰减,衰减到0后重新开始。这样可以让权重更大的节点被选择得更多。

本机优先

访问后台服务的访问者可能本身是一个整合服务,或者是一个proxy,如果后台服务节点恰好有节点部署在本机的,则可以优先使用。在未找到本机节点时则可以继续走Round-robin策略:

if (node->ip() == local_ip) {
    return node;
} else {
    return roundRobin();
}

一旦遍历到本机节点,则后面的请求会一直落到本机节点。所以这里可以加上一些权重机制,仅是保证本机节点会被优先选择,但不会被一直选择。例如:

// initial
cur_weight = 100;
...
// select node
cur_weight -= 5;
if (cur_weight <= 0)
    cur_weight = 100;
if (cur_weight > 50 && node->ip() == local_ip) {
    return node;
} else {
    return roundRobin();
}

本机房优先

服务节点可能会被部署到多个机房,有时候确实是需要考虑跨机房服务。同本机优先策略类似,本机房优先则是优先考虑位于相同机房内的服务节点。该请求是从哪个机房中的前端服务发送过来的,则需要前端在请求参数中携带上机房ID。

在服务节点对应的数据结构中,也最好按照机房来组织。

本机房优先策略实际上会作为节点选择的第一道工序,它可以把非本机房的节点先过滤掉,然后再传入后面的各种节点选择策略。这里还可以考虑节点数参数,如果本机房的节点过少,则可以不使用该策略,避免流量严重不均。

Consistent Hash

一致性哈希。一致性哈希用于在分布式环境中,分布在各个节点上的请求,不会因为新增节点(扩容)或减少节点(节点宕机)而变化。如果每个服务节点上都有自己的缓存,其保存了该节点响应请求时的回应。正常情况下,这些缓存都可以很好地被运用,也即cache命中率较高。

如果某个节点不可用了,我们的选择策略又是基于所有节点的公平选择,那么原来一直分配在节点A上请求就很可能被分配到节点B上,从而导致节点A上的缓存较难被命中。这个时候就可以运用一致性哈希来解决。

其基本思想是,在节点选择区间内,在找节点时以顺时针方向找到不小于该请求对应的哈希值的节点。在这个区间里增加很多虚拟节点,每一个虚拟节点相当于一个物理节点的引用,这样相当于把物理节点变成了一个哈希值区间。这个哈希值区间不会因为增加节点和减少节点而变化,那么对某个请求而言,它就会始终落到这个区间里,也就会始终被分配到原来的节点。

至于这个不可用的节点,其上的请求也会被均匀地分配到其他节点中。

摘抄网上的一段代码:

// 添加一个物理节点时,会随之增加很多虚拟节点
template <class Node, class Data, class Hash>
size_t HashRing<Node, Data, Hash>::AddNode(const Node& node)
{
    size_t hash;
    std::string nodestr = Stringify(node);
    for (unsigned int r = 0; r < replicas_; r++) {
        hash = hash_((nodestr + Stringify(r)).c_str());
        ring_[hash] = node;  // 物理节点和虚拟节点都保存在一个std::map中
    }
    return hash;
}

// 选择data对应的节点,data可以是请求
template <class Node, class Data, class Hash>
const Node& HashRing<Node, Data, Hash>::GetNode(const Data& data) const
{
    if (ring_.empty()) {
        throw EmptyRingException();
    }
    size_t hash = hash_(Stringify(data).c_str()); // 对请求进行哈希
    typename NodeMap::const_iterator it;
    // Look for the first node >= hash
    it = ring_.lower_bound(hash); // 找到第一个不小于请求哈希的节点
    if (it == ring_.end()) {
        // Wrapped around; get the first node
        it = ring_.begin();
    }
    return it->second;
}

Reference

http://blog.csdn.net/yunhua_lee/article/details/49685679
大型网站架构系列:负载均衡详解(1)
大型网站架构系列:负载均衡详解(2)
大型网站架构系列:负载均衡详解(3)
大型网站架构系列:负载均衡详解(4)
分布式环境中的负载均衡策略
Nginx负载均衡实现原理图解
Nginx、LVS及HAProxy负载均衡软件的优缺点详解

念念不忘,必有回响