频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
2016 -Nginx的负载均衡 - 一致性哈希 (Consistent Hash)
2017-06-06 10:11:00         来源:美国清华大学--In The Bei Jing.  
收藏   我要投稿

Nginx版本:1.9.1

算法介绍

当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。Nginx版本:1.9.1

算法介绍

当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。

使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。

在nginx+ats / haproxy+squid等CDN架构中,nginx/haproxy所使用的负载均衡算法便是一致性哈希。

我们举个例子来说明一致性哈希的好处。

假设后端集群包含三台缓存服务器,A、B、C。

请求r1、r2落在A上。

请求r3、r4落在B上。

请求r5、r6落在C上。

使用一致性哈希时,当缓存服务器B宕机时,r1/r2会仍然落在A上,r5/r6会仍然落在C上,

也就是说这两台服务器上的缓存都不会失效。r3/r4会被重新分配给A或者C,并产生回源。

使用其它算法,当缓存服务器B宕机时,r1/r2不再落在A上,r5/r6不再落在C上了。

也就是说A、B、C上的缓存都失效了,所有的请求都要回源。

这里不介绍一致性哈希算法的基本原理,如果不了解,先花个10分钟看下这篇文章:

https://www.codeproject.com/Articles/56138/Consistent-hashing

在分析模块代码之前,先来看下nginx所实现的一致性哈希算法。

1. 初始化upstream块

主要工作是创建和初始化真实节点、创建和初始化虚拟节点。

其中真实节点是使用round robin的方法创建的。

Q:总共有多少个虚拟节点,一个真实节点对应多少个虚拟节点?

累加真实节点的权重,算出总的权重值total_weight,虚拟节点的个数一般为total_weight * 160。

一个权重为weight的真实节点,对应的虚拟节点数为weight * 160。

Q:对于每一个真实节点,是如何创建其对应的虚拟节点的?

1. 真实节点的server成员是其server指令的第一个参数,首先把它解析为HOST和PORT。

base_hash = crc32(HOST 0 PORT)

一个真实节点对应weight * 160个虚拟节点,对于每个虚拟节点来说,base_hash都是一样的。

2. 为了使每个虚拟节点的hash值都不同,又引入了PREV_HASH,它是上一个虚拟节点的hash值。

hash = crc32(base_hash PREV_HASH)

3. 虚拟节点的server成员,指向真实节点的server成员。如此一来,通过比较虚拟节点和真实节点的

server成员是否相同,可以判断它们是否是相对应的。

创建和初始化好虚拟节点数组后,对其中的虚拟节点按照hash值进行排序,对于hash值相同的虚拟节点,只保留第一个。

经过上述步骤,我们得到一个所有虚拟节点组成的数组,其元素的hash值有序而不重复。也就是说,ring建立起来了。

2. 初始话请求的负载均衡数据

根据hash指令第一个参数的实时值KEY,KEY一般是$host$uri之类的,计算出本次请求的哈希值。

hash = crc32(KEY)

根据请求的哈希值,在虚拟节点数组中,找到“顺时针方向”最近的一个虚拟节点,其索引为i。

什么叫顺时针方向最近?就是point[i - 1].hash < hash <= point[i].hash。

本次请求就落在该虚拟节点上了,之后交由其对应的真实节点来处理。

3. 选取真实节点

在peer.init中,已经知道请求落在哪个虚拟节点上了。

在peer.get中,需要查找虚拟节点对应的真实节点。

根据虚拟节点的server成员,在真实节点数组中查找server成员相同的、可用的真实节点。

如果找不到,那么沿着顺时针方向,继续查找下一个虚拟节点对应的真实节点。

如果找到了一个,那么就是它了。

如果找到了多个,使用轮询的方法从中选取一个。

4. 缺陷和改进

一个虚拟节点和一个真实节点,是依据它们的server成员来关联的。

这会出现一种情况,一个虚拟节点对应了多个真实节点,因为:

如果server指令的第一个参数为域名,可能解析为多个真实节点,那么这些真实节点的server成员都是一样的。

对于一个请求,计算其KEY的hash值,顺时针找到最近的虚拟节点后,发现该虚拟节点对应了多个真实节点。

使用哪个真实节点呢?本模块就使用轮询的方法,来从多个真实节点中选一个。

但我们知道使用一致性哈希的场景中,真实节点一般是缓存服务器。

一个虚拟节点对应多个真实节点,会导致一个文件被缓存在多个缓存服务器上。

这会增加磁盘的使用量,以及回源量,显然不是我们希望看到的。

解决这个问题的方法其实很简单,就是虚拟节点和真实节点通过name成员来建立关联。

因为就算对应同一条server配置,server的第一个参数为域名,各个真实节点的name成员也是唯一的。

这样一来,找到了一个虚拟节点,就能找到一个唯一的真实节点,不会有上述问题了。

数据结构

1. 真实节点

就是采用round robin算法所创建的后端服务器,类型为ngx_http_upstream_rr_peer_t。

需要注意的是,如果server指令的第一个参数是IP和端口,那么一条server指令只对应一个真实节点。

如果server指令的第一个参数是域名,一条server指令可能对应多个真实节点。

它们的server成员是相同的,可以通过name成员区分。

[java] view plain copy

structngx_http_upstream_rr_peer_s{structsockaddr*sockaddr;/*后端服务器的地址*/

socklen_tsocklen;/*地址的长度*/ngx_str_tname;/*后端服务器地址的字符串,server.addrs[i].name*/

ngx_str_tserver;/*server的名称,server.name*/

ngx_int_tcurrent_weight;/*当前的权重,动态调整,初始值为0*/ngx_int_teffective_weight;/*有效的权重,会因为失败而降低*/

ngx_int_tweight;/*配置项指定的权重,固定值*/

ngx_uint_tconns;/*当前连接数*/

ngx_uint_tfails;/*"一段时间内",已经失败的次数*/time_taccessed;/*最近一次失败的时间点*/

time_tchecked;/*用于检查是否超过了"一段时间"*/

ngx_uint_tmax_fails;/*"一段时间内",最大的失败次数,固定值*/time_tfail_timeout;/*"一段时间"的值,固定值*/

ngx_uint_tdown;/*服务器永久不可用的标志*/...

ngx_http_upstream_rr_peer_t*next;/*指向下一个后端,用于构成链表*/...

}ngx_http_upstream_rr_peer_t;

ngx_http_upstream_rr_peers_t表示一组后端服务器,比如一个后端集群。

[java] view plain copy

structngx_http_upstream_rr_peers_s{ngx_uint_tnumber;/*后端服务器的数量*/

...ngx_uint_ttotal_weight;/*所有后端服务器权重的累加值*/

unsignedsingle:1;/*是否只有一台后端服务器*/

unsignedweighted:1;/*是否使用权重*/

ngx_str_t*name;/*upstream配置块的名称*/

ngx_http_upstream_rr_peers_t*next;/*backup服务器集群*/ngx_http_upstream_rr_peer_t*peer;/*后端服务器组成的链表*/

};

2. 虚拟节点

一个真实节点,一般会对应weight * 160个虚拟节点。

虚拟节点的server成员,指向它所归属的真实节点的server成员,如此一来找到了一个虚拟节点后,

就能找到其归属的真实节点。

但这里有一个问题,通过一个虚拟节点的server成员,可能会找到多个真实节点,而不是一个。

因为如果server指令的第一个参数为域名,那么多个真实节点的server成员都是一样的。

[java] view plain copy

typedefstruct{uint32_thash;/*虚拟节点的哈希值*/

ngx_str_t*server;/*虚拟节点归属的真实节点,对应真实节点的server成员*/}ngx_http_upstream_chash_point_t;

typedefstruct{

ngx_uint_tnumber;/*虚拟节点的个数*/ngx_http_upstream_chash_point_tpoint[1];/*虚拟节点的数组*/

}ngx_http_upstream_chash_points_t;

typedefstruct{ngx_http_complex_value_tkey;/*关联hash指令的第一个参数,用于计算请求的hash值*/

ngx_http_upstream_chash_points_t*points;/*虚拟节点的数组*/}ngx_http_upstream_chash_points_t;

3. 请求的一致性哈希数据

[java] view plain copy

typedefstruct{/*theroundrobindatamustbefirst*/

ngx_http_upstream_rr_peer_data_trrp;/*roundrobin的perrequest负载均衡数据*/ngx_http_upstream_hash_srv_conf_t*conf;/*server配置块*/

ngx_str_tkey;/*对于本次请求,hash指令的第一个参数的具体值,用于计算本次请求的哈希值*/ngx_uint_ttries;/*已经尝试的虚拟节点数*/

ngx_uint_trehash;/*本算法不使用此成员*/uint32_thash;/*根据请求的哈希值,找到顺时方向最近的一个虚拟节点,hash为该虚拟节点在数组中的索引*/

ngx_event_get_peer_ptget_rr_peer;/*roundrobin算法的peer.get函数*/}ngx_http_upstream_hash_peer_data_t;

round robin的per request负载均衡数据。

[java] view plain copy

typedefstruct{ngx_http_upstream_rr_peers_t*peers;/*后端集群*/

ngx_http_upstream_rr_peer_t*current;/*当前使用的后端服务器*/uintptr_t*tried;/*指向后端服务器的位图*/

uintptr_tdata;/*当后端服务器的数量较少时,用于存放其位图*/}ngx_http_upstream_rr_peer_data_t;

指令的解析函数

在一个upstream配置块中,如果有hash指令,且它只带一个参数,则使用的负载均衡算法为哈希算法,比如:

hash $host$uri;

在一个upstream配置块中,如果有hash指令,且它带了两个参数,且第二个参数为consistent,则使用的

负载均衡算法为一致性哈希算法,比如:

hash $host$uri consistent;

这说明hash指令所属的模块ngx_http_upstream_hash_module同时实现了两种负载均衡算法,而实际上

哈希算法、一致性哈希算法完全可以用两个独立的模块来实现,它们本身并没有多少关联。

哈希算法的实现比较简单,类似之前分析过的ip_hash,接下来分析的是一致性哈希算法。

hash指令的解析函数主要做了:

把hash指令的第一个参数,关联到一个ngx_http_complex_value_t变量,之后可以通过该变量获取参数的实时值。

指定此upstream块中server指令支持的属性。

根据hash指令携带的参数来判断是使用哈希算法,还是一致性哈希算法。如果hash指令的第二个参数为"consistent",

则表示使用一致性哈希算法,指定upstream块的初始化函数uscf->peer.init_upstream。

[java] view plain copy

staticchar*ngx_http_upstream_hash(ngx_conf_t*cf,ngx_command_t*cmd,void*conf){

ngx_http_upstream_hash_srv_conf_t*hcf=conf;ngx_str_t*value;

ngx_http_upstream_srv_conf_t*uscf;ngx_http_compile_complex_value_tccv;

value=cf->args->elts;

ngx_memzero(&ccv,sizeof(ngx_http_compile_complex_value_t));

/*把hash指令的第一个参数,关联到一个ngx_http_complex_value_t变量,*之后可以通过该变量获取参数的实时值。

*/ccv.cf=conf;

ccv.value=&value[1];ccv.complex_value=&hcf->key;

if(ngx_http_compile_complex_value(&ccv)!=NGX_OK)

returnNGX_CONF_ERROR;

/*获取所在的upstream{}块*/uscf=ngx_http_conf_get_module_srv_conf(cf,ngx_http_upstream_module);

if(uscf->peer.init_upstream)ngx_conf_log_error(NGX_LOG_WARN,cf,0,"loadbalancingmethodredefined");

/*指定此upstream块中server指令支持的属性*/

uscf->flags=NGX_HTTP_UPSTREAM_CREATE|NGX_HTTP_UPSTREAM_WEIGHT

|NGX_HTTP_UPSTREAM_MAX_FAILS|NGX_HTTP_UPSTREAM_FAIL_TIMEOUT

|NGX_HTTP_UPSTREAM_DOWN;

/*根据hash指令携带的参数来判断是使用哈希算法,还是一致性哈希算法。*每种算法都有自己的upstream块初始化函数。

*/if(cf->args->nelts==2)

uscf->peer.init_upstream=ngx_http_upstream_init_hash;elseif(ngx_strcmp(value[2].data,"consistent")==0)

uscf->peer.init_upstream=ngx_http_upstream_init_chash;else

ngx_conf_log_error(NGX_LOG_EMERG,cf,0,"invalidparameter\"%V\"",&value[2]);

returnNGX_CONF_OK;}

初始化upstream块

执行完指令的解析函数后,紧接着会调用所有HTTP模块的init main conf函数。

在执行ngx_http_upstream_module的init main conf函数时,会调用所有upstream块的初始化函数。

对于使用一致性哈希的upstream块,其初始化函数(peer.init_upstream)就是上一步中指定

ngx_http_upstream_init_chash,它主要做了:

调用round robin的upstream块初始化函数来创建和初始化真实节点

指定per request的负载均衡初始化函数peer.init

创建和初始化虚拟节点数组,使该数组中的虚拟节点有序而不重复

[java] view plain copy

staticngx_int_tngx_http_upstream_init_chash(ngx_conf_t*cf,ngx_http_upstream_srv_conf_t*us){

u_char*host,*port,c;size_thost_len,port_len,size;

uint32_thash,base_hash;ngx_str_t*server;

ngx_uint_tnpoints,i,j;ngx_http_upstream_rr_peer_t*peer;

ngx_http_upstream_rr_peers_t*peers;ngx_http_upstream_chash_points_t*points;

ngx_http_upstream_hash_srv_conf_t*hcf;union{

uint32_tvalue;u_charbyte[4];

}prev_hash;

/*使用roundrobin的upstream块初始化函数,创建和初始化真实节点*/if(ngx_http_upstream_init_round_robin(cf,us)!=NGX_OK)

returnNGX_ERROR:

/*重新设置perrequest的负载均衡初始化函数*/us->peer.init=ngx_http_upstream_init_chash_peer;

peers=us->peer.data;/*真实节点的集群*/

npoints=peers->total_weight*160;

/*一共创建npoints个虚拟节点*/size=sizeof(ngx_http_upstream_chash_points_t)+

sizeof(ngx_http_upstream_chash_point_t)*(npoints-1);

points=ngx_palloc(cf->pool,size);if(points==NULL)

returnNGX_ERROR;

points->number=0;

/*初始化所有的虚拟节点*/for(peer=peers->peer;peer;peer=peer->next){

server=&peer->server;/*server指令的第一个参数,server.name*/

/*HashexpressioniscompatiblewithCache::Memcached::Fast:*crc32(HOST0PORTPREV_HASH).

*/if(server->len>=5&&ngx_strncasecmp(server->data,(u_char*)"unix:",5)==0)

{host=server->data+5;

host_len=server->len-5;port=NULL;

port_len=0;gotodone;

}

/*把每个peer的server成员,解析为HOST和PORT*/for(j=0;jlen;j++){

c=server->data[server->len-j-1];

if(c==":"){host=server->data;

host_len=server->len-j-1;port=server->data+server->len-j;

port_len=j;gotodone;

}

if(c<'0'||c>'9')/*表示没有指定端口*/break;

}

host=server->data;host_len=server->len;

port=NULL;port_len=0;

done:

/*根据解析peer的server成员所得的HOST和PORT,计算虚拟节点的base_hash值*/ngx_crc32_init(base_hash);

ngx_crc32_update(&base_hash,host,host_len);ngx_crc32_update(&base_hash,(u_char*)"",1);/*空字符串包含字符\0*/

ngx_crc32_update(&base_hash,port,port_len);

/*对于归属同一个真实节点的虚拟节点,它们的base_hash值相同,而prev_hash不同*/prev_hash.value=0;

npoints=peer->weight*160;

for(j=0;jngx_crc32_update(&hash,prev_hash.byte,4);ngx_crc32_final(hash);

points->point[points->number].hash=hash;/*虚拟节点的哈希值*/

points->point[points->number].server=server;/*虚拟节点所归属的真实节点,对应真实节点的server成员*/points->number++;

#if(NGX_HAVE_LITTLE_ENDIAN)

prev_hash.value=hash;#else

prev_hash.byte[0]=(u_char)(hash&0xff);prev_hash.byte[1]=(u_char)((hash>>8)&0xff);

prev_hash.byte[2]=(u_char)((hash>>16)&0xff);prev_hash.byte[3]=(u_char)((hash>>24)&0xff);

#endif}

}

/*使用快速排序,使虚拟节点数组的元素,按照其hash值从小到大有序*/ngx_qsort(points->point,points->number,sizeof(ngx_http_upstream_chash_point_t),

ngx_http_upstream_chash_cmp_points);

/*如果虚拟节点数组中,有多个元素的hash值相同,只保留第一个*/for(i=0,j=1;jnumber;j++)

if(points->point[i].hash!=points->point[j].hash)points->point[++i]=points->point[j];

/*经过上述步骤后,虚拟节点数组中的元素,有序而不重复*/

points->number=i+1;

hcf=ngx_http_conf_upstream_srv_conf(us,ngx_http_upstream_hash_module);hcf->points=points;/*保存虚拟节点数组*/

returnNGX_OK;

} [java]view plaincopy

staticintngx_libc_cdelngx_http_upstream_chash_cmp_points(constvoid*one,constvoid*two){

ngx_http_upstream_chash_point_t*first=(ngx_http_upstream_chash_point_t*)one;ngx_http_upstream_chash_point_t*second=(ngx_http_upstream_chash_point_t*)two;

if(first->hashhash)

return-1;elseif(first->hash>second->hash)

return1;else

return0;}

初始化请求的负载均衡数据

收到一个请求后,一般使用的反向代理模块(upstream模块)为ngx_http_proxy_module,

其NGX_HTTP_CONTENT_PHASE阶段的处理函数为ngx_http_proxy_handler,在初始化upstream机制的

ngx_http_upstream_init_request函数中,调用在第二步中指定的peer.init,主要用于初始化请求的负载均衡数据。

对于一致性哈希,peer.init实例为ngx_http_upstream_init_chash_peer,主要做了:

首先调用hash算法的per request负载均衡初始化函数,创建和初始化请求的负载均衡数据。

重新指定peer.get,用于选取一个真实节点来处理本次请求。

获取的本请求对应的hash指令的第一个参数值,计算请求的hash值。

寻找第一个hash值大于等于请求的哈希值的虚拟节点,即寻找“顺时针方向最近”的一个虚拟节点。

[java]view plaincopy

staticngx_int_tngx_http_upstream_init_chash_peer(ngx_http_request_t*r,ngx_http_upstream_srv_conf_t*us){

uint32_thash;ngx_http_upstream_hash_srv_conf_t*hcf;

ngx_http_upstream_hash_peer_data_t*hp;

/*调用hash算法的perrequest负载均衡初始化函数,创建和初始化请求的负载均衡数据*/if(ngx_http_upstream_init_hash_peer(r,us)!=NGX_OK)

returnNGX_ERROR;

/*重新指定peer.get,用于选取一个真实节点*/r->upstream->peer.get=ngx_http_upstream_get_chash_peer;

hp=r->upstream->peer.data;

hcf=ngx_http_conf_upstream_srv_conf(us,ngx_http_upstream_hash_module);

/*根据获取的本请求对应的hash指令的第一个参数值,计算请求的hash值*/hash=ngx_crc32_long(hp->key.data,hp->key.len);

/*根据请求的hash值,找到顺时针方向最近的一个虚拟节点,hp->hash记录此虚拟节点

*在数组中的索引。*/

hp->hash=ngx_http_upstream_find_chash_point(hcf->points,hash);

returnNGX_OK:}

hash算法的per request负载均衡初始化函数。

[java]view plaincopy

staticngx_int_tngx_http_upstream_init_hash_peer(ngx_http_request_t*r,ngx_http_upstream_srv_conf_t*us){

ngx_http_upstream_hash_srv_conf_t*hcf;ngx_http_upstream_hash_peer_data_t*hp;

hp=ngx_palloc(r->pool,sizeof(ngx_http_upstream_hash_peer_data_t));

if(hp==NULL)returnNGX_ERROR:

/*调用roundrobin的perrequest负载均衡初始化函数*/

r->upstream->peer.data=&hp->rrp;if(ngx_http_upstream_init_round_robin_peer(r,us)!=NGX_OK)

returnNGX_ERROR;

r->upstream->peer.get=ngx_http_upstream_get_hash_peer;hcf=ngx_http_conf_upstream_srv_conf(us,ngx_http_upstream_hash_module);

/*获取本请求对应的hash指令的第一个参数值,用于计算请求的hash值*/

if(ngx_http_complex_value(r,&hcf->key,&hp->key)!=NGX_OK)returnNGX_ERROR;

...hp->conf=hcf;

hp->tries=0;hp->rehash=0;

hp->hash=0;hp->get_rr_peer=ngx_http_upstream_get_round_robin_peer;/*roundrobin的peer.get函数*/

returnNGX_OK;

}

我们知道虚拟节点数组是有序的,事先已按照虚拟节点的hash值从小到大排序好了。

现在使用二分查找,寻找第一个hash值大于等于请求的哈希值的虚拟节点,即“顺时针方向最近”的一个虚拟节点。

[java]view plaincopy

staticngx_uint_tngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t*points,uint32_thash){

ngx_uint_ti,j,k;ngx_http_upstream_chash_point_t*point;

/*findfirstpoint>=hash*/

point=&points->point[0];

i=0;j=points->number;'

while(ik=(i+j)/2;

if(hash>point[k].hash)i=k+1;

elseif(hashelsereturnk;

}

returni;}

选取一个真实节点

一般upstream块中会有多个真实节点,那么对于本次请求,要选定哪一个真实节点呢?

对于一致性哈希算法,选取真实节点的peer.get函数为ngx_http_upstream_get_chash_peer。

其实在peer.init中,已经找到了该请求对应的虚拟节点了:

根据请求对应的hash指令的第一个参数值,计算请求的hash值。

寻找第一个哈希值大于等于请求的hash值的虚拟节点,即“顺时针方向最近”的一个虚拟节点。

在peer.get中,需查找此虚拟节点对应的真实节点。

根据虚拟节点的server成员,在真实节点数组中查找server成员一样的且可用的真实节点。

如果找不到,那么沿着顺时针方向,继续查找下一个虚拟节点对应的真实节点。

如果找到一个真实节点,那么就是它了。

如果找到多个真实节点,使用轮询的方法从中选取一个。

[java]view plaincopy

staticngx_http_upstream_get_chash_peer(ngx_peer_connection_t*pc,void*data){

ngx_http_upstream_hash_peer_data_t*hp=data;/*请求的负载均衡数据*/time_tnow;

intptr_tm;ngx_str_t*server;

ngx_int_ttotal;ngx_uint_ti,n,best_i;

ngx_http_upstream_rr_peer_t*peer,*best;ngx_http_upstream_chash_point_t*point;

ngx_http_upstream_chash_points_t*points;ngx_http_upstream_hash_srv_conf_t*hcf;

...pc->cached=0;

pc->connection=NULL:now=ngx_time();

hcf=hp->conf;points=hcf->points;/*虚拟节点数组*/

point=&points->point[0];/*指向第一个虚拟节点*/

for(;;){/*在peer.init中,已根据请求的哈希值,找到顺时针方向最近的一个虚拟节点,

*hash为该虚拟节点在数组中的索引。*一开始hash值肯定小于number,之后每尝试一个虚拟节点后,hash++。取模是为了防止越界访问。

*/server=point[hp->hash%points->number].server;

best=NULL;best_i=0;

total=0;

/*遍历真实节点数组,寻找可用的、该虚拟节点归属的真实节点(server成员相同),*如果有多个真实节点同时符合条件,那么使用轮询来从中选取一个真实节点。

*/for(peer=hp->rrp.peers->peer,i=0;peer;peer=peer->next,i++){

/*检查此真实节点在状态位图中对应的位,为1时表示不可用*/n=i/(8*sizeof(uintptr_t));

m=(uintptr_t)1

continue;

/*server指令中携带了down属性,表示后端永久不可用*/if(peer->down)

continue;

/*如果真实节点的server成员和虚拟节点的不同,表示虚拟节点不属于此真实节点*/if(peer->server.len!=server->len||

ngx_strncmp(peer->server.data,server->data,server->len)!=0)continue;

/*在一段时间内,如果此真实节点的失败次数,超过了允许的最大值,那么不允许使用了*/

if(peer->max_fails&&peer->fails>=peer->max_fails

&&now-peer->checked<=peer->fail_timeout)continue;

peer->current_weight+=peer->effective_weight;/*对每个真实节点,增加其当前权重*/

total+=peer->effective_weight;/*累加所有真实节点的有效权重*/

/*如果之前此真实节点发生了失败,会减小其effective_weight来降低它的权重。*此后又通过增加其effective_weight来恢复它的权重。

*/if(peer->effective_weightweight)

peer->effective_weight++;

/*选取当前权重最大者,作为本次选定的真实节点*/if(best==NULL||peer->current_weight>best->current_weight){

best=peer;best_i=i;

}}

/*如果选定了一个真实节点*/

if(best){best->current_weight-=total;/*如果使用了轮询,需要降低选定节点的当前权重*/

gotofound;}

hp->hash++;/*增加虚拟节点的索引,即“沿着顺时针方向”*/

hp->tries++;/*已经尝试的虚拟节点数*/

/*如果把所有的虚拟节点都尝试了一遍,还找不到可用的真实节点*/if(hp->tries>=points->number)

returnNGX_BUSY;}

found:/*找到了和虚拟节点相对应的、可用的真实节点了*/

hp->rrp.current=best;/*选定的真实节点*//*保存选定的后端服务器的地址,之后会向这个地址发起连接*/

pc->sockaddr=peer->sockaddr;pc->socklen=peer->socklen;

pc->name=&peer->name;best->conns++;

/*更新checked时间*/

if(now-best->checked>best->fail_timeout)best->checked=now;

n=best_i/(8*sizeof(uintptr_t));

m=(uintptr_t)1rrp->tried[n]|=m;

returnNGX_OK;

}

使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。

在nginx+ats / haproxy+squid等CDN架构中,nginx/haproxy所使用的负载均衡算法便是一致性哈希。

我们举个例子来说明一致性哈希的好处。

假设后端集群包含三台缓存服务器,A、B、C。

请求r1、r2落在A上。

请求r3、r4落在B上。

请求r5、r6落在C上。

使用一致性哈希时,当缓存服务器B宕机时,r1/r2会仍然落在A上,r5/r6会仍然落在C上,

也就是说这两台服务器上的缓存都不会失效。r3/r4会被重新分配给A或者C,并产生回源。

使用其它算法,当缓存服务器B宕机时,r1/r2不再落在A上,r5/r6不再落在C上了。

也就是说A、B、C上的缓存都失效了,所有的请求都要回源。

点击复制链接 与好友分享!回本站首页
上一篇:"围观"设计模式(14)--结构型之外观模式(Facade Pattern)
下一篇:SharedPreference的读写原理分析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站