AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Nginx的负载均衡 - 一致性哈希 (Consistent Hash)

2016-05-06 7450
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
传统型负载均衡 CLB，每月750个小时 15LCU
推荐场景：
搭建高可用的微信/支付宝小程序服务
网络型负载均衡 NLB，每月750个小时 15LCU
全局流量管理 GTM，标准版 1个月
简介： 【本文转载于Nginx的负载均衡 - 一致性哈希 (Consistent Hash)】 Nginx版本：1.9.1 我的博客：http://blog.csdn.net/zhangskd   算法介绍   当后端是缓存服务器时，经常使用一致性哈希算法来进行负载均衡。 使用一致性哈希的好处在于，增减集群的缓存服务器时，只有少量的缓存会失效，回源量较

【本文转载于Nginx的负载均衡 - 一致性哈希 (Consistent Hash)】

Nginx版本：1.9.1

我的博客：http://blog.csdn.net/zhangskd

 

算法介绍

 

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

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

在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分钟看下这篇文章：

http://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
  1. struct ngx_http_upstream_rr_peer_s {  
  2.     struct sockaddr *sockaddr; /* 后端服务器的地址 */  
  3.     socklen_t socklen; /* 地址的长度*/  
  4.     ngx_str_t name; /* 后端服务器地址的字符串，server.addrs[i].name */  
  5.     ngx_str_t server; /* server的名称，server.name */  
  6.        
  7.     ngx_int_t current_weight; /* 当前的权重，动态调整，初始值为0 */  
  8.     ngx_int_t effective_weight; /* 有效的权重，会因为失败而降低 */  
  9.     ngx_int_t weight; /* 配置项指定的权重，固定值 */  
  10.   
  11.     ngx_uint_t conns; /* 当前连接数 */  
  12.   
  13.     ngx_uint_t fails; /* "一段时间内"，已经失败的次数 */  
  14.     time_t accessed; /* 最近一次失败的时间点 */  
  15.     time_t checked; /* 用于检查是否超过了"一段时间" */  
  16.   
  17.     ngx_uint_t max_fails; /* "一段时间内"，最大的失败次数，固定值 */  
  18.     time_t fail_timeout; /* "一段时间"的值，固定值 */  
  19.     ngx_uint_t down; /* 服务器永久不可用的标志 */  
  20.     ...  
  21.     ngx_http_upstream_rr_peer_t *next; /* 指向下一个后端，用于构成链表 */  
  22.     ...  
  23. } ngx_http_upstream_rr_peer_t;  

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

[java]  view plain  copy
  1. struct ngx_http_upstream_rr_peers_s {  
  2.     ngx_uint_t number; /* 后端服务器的数量 */  
  3.     ...  
  4.     ngx_uint_t total_weight; /* 所有后端服务器权重的累加值 */  
  5.   
  6.     unsigned single:1; /* 是否只有一台后端服务器 */  
  7.     unsigned weighted:1; /* 是否使用权重 */  
  8.   
  9.     ngx_str_t *name; /* upstream配置块的名称 */  
  10.   
  11.     ngx_http_upstream_rr_peers_t *next; /* backup服务器集群 */  
  12.     ngx_http_upstream_rr_peer_t *peer; /* 后端服务器组成的链表 */  
  13. };  

 

2. 虚拟节点

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

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

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

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

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

[java]  view plain  copy
  1. typedef struct {  
  2.     uint32_t hash; /* 虚拟节点的哈希值 */  
  3.     ngx_str_t *server; /* 虚拟节点归属的真实节点，对应真实节点的server成员 */  
  4. } ngx_http_upstream_chash_point_t;  
  5.   
  6. typedef struct {  
  7.     ngx_uint_t number; /* 虚拟节点的个数 */  
  8.     ngx_http_upstream_chash_point_t point[1]; /* 虚拟节点的数组 */  
  9. } ngx_http_upstream_chash_points_t;  
  10.   
  11. typedef struct {  
  12.     ngx_http_complex_value_t key; /* 关联hash指令的第一个参数，用于计算请求的hash值 */  
  13.     ngx_http_upstream_chash_points_t *points; /* 虚拟节点的数组 */  
  14. } ngx_http_upstream_chash_points_t;  

 

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

[java]  view plain  copy
  1. typedef struct {  
  2.     /* the round robin data must be first */  
  3.     ngx_http_upstream_rr_peer_data_t rrp; /* round robin的per request负载均衡数据 */  
  4.     ngx_http_upstream_hash_srv_conf_t *conf; /* server配置块 */  
  5.     ngx_str_t key; /* 对于本次请求，hash指令的第一个参数的具体值，用于计算本次请求的哈希值 */  
  6.     ngx_uint_t tries; /* 已经尝试的虚拟节点数 */  
  7.     ngx_uint_t rehash; /* 本算法不使用此成员 */  
  8.     uint32_t hash; /* 根据请求的哈希值，找到顺时方向最近的一个虚拟节点，hash为该虚拟节点在数组中的索引 */  
  9.     ngx_event_get_peer_pt get_rr_peer; /* round robin算法的peer.get函数 */  
  10. } ngx_http_upstream_hash_peer_data_t;  

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

[java]  view plain  copy
  1. typedef struct {  
  2.      ngx_http_upstream_rr_peers_t *peers; /* 后端集群 */  
  3.      ngx_http_upstream_rr_peer_t *current; /* 当前使用的后端服务器 */  
  4.      uintptr_t *tried; /* 指向后端服务器的位图 */  
  5.      uintptr_t data; /* 当后端服务器的数量较少时，用于存放其位图 */  
  6. } 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
  1. static char *ngx_http_upstream_hash(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)  
  2. {  
  3.     ngx_http_upstream_hash_srv_conf_t *hcf = conf;  
  4.     ngx_str_t *value;  
  5.     ngx_http_upstream_srv_conf_t *uscf;  
  6.     ngx_http_compile_complex_value_t ccv;  
  7.   
  8.     value = cf->args->elts;  
  9.     ngx_memzero(&ccv, sizeof(ngx_http_compile_complex_value_t));  
  10.   
  11.     /* 把hash指令的第一个参数，关联到一个ngx_http_complex_value_t变量， 
  12.      * 之后可以通过该变量获取参数的实时值。 
  13.      */  
  14.     ccv.cf = conf;  
  15.     ccv.value = &value[1];  
  16.     ccv.complex_value = &hcf->key;  
  17.   
  18.     if (ngx_http_compile_complex_value(&ccv) != NGX_OK)  
  19.         return NGX_CONF_ERROR;  
  20.   
  21.     /* 获取所在的upstream{}块 */  
  22.     uscf = ngx_http_conf_get_module_srv_conf(cf, ngx_http_upstream_module);  
  23.     if (uscf->peer.init_upstream)  
  24.         ngx_conf_log_error(NGX_LOG_WARN, cf, 0, "load balancing method redefined");  
  25.   
  26.     /* 指定此upstream块中server指令支持的属性 */  
  27.     uscf->flags = NGX_HTTP_UPSTREAM_CREATE  
  28.         | NGX_HTTP_UPSTREAM_WEIGHT  
  29.         | NGX_HTTP_UPSTREAM_MAX_FAILS  
  30.         | NGX_HTTP_UPSTREAM_FAIL_TIMEOUT  
  31.         | NGX_HTTP_UPSTREAM_DOWN;  
  32.   
  33.     /* 根据hash指令携带的参数来判断是使用哈希算法，还是一致性哈希算法。 
  34.      * 每种算法都有自己的upstream块初始化函数。 
  35.       */  
  36.     if (cf->args->nelts == 2)  
  37.         uscf->peer.init_upstream = ngx_http_upstream_init_hash;  
  38.     else if (ngx_strcmp(value[2].data, "consistent") == 0)  
  39.         uscf->peer.init_upstream = ngx_http_upstream_init_chash;  
  40.     else  
  41.         ngx_conf_log_error(NGX_LOG_EMERG, cf, 0, "invalid parameter \"%V\"", &value[2]);  
  42.   
  43.     return NGX_CONF_OK;  
  44. }  

 

初始化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
  1. static ngx_int_t ngx_http_upstream_init_chash(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us)  
  2. {  
  3.     u_char *host, *port, c;  
  4.     size_t host_len, port_len, size;  
  5.     uint32_t hash, base_hash;  
  6.     ngx_str_t *server;  
  7.     ngx_uint_t npoints, i, j;  
  8.     ngx_http_upstream_rr_peer_t *peer;  
  9.     ngx_http_upstream_rr_peers_t *peers;  
  10.     ngx_http_upstream_chash_points_t *points;  
  11.     ngx_http_upstream_hash_srv_conf_t *hcf;  
  12.     union {  
  13.         uint32_t value;  
  14.         u_char byte[4];  
  15.     } prev_hash;  
  16.   
  17.     /* 使用round robin的upstream块初始化函数，创建和初始化真实节点 */  
  18.     if (ngx_http_upstream_init_round_robin(cf, us) != NGX_OK)  
  19.         return NGX_ERROR:  
  20.   
  21.     /* 重新设置per request的负载均衡初始化函数 */  
  22.     us->peer.init = ngx_http_upstream_init_chash_peer;  
  23.   
  24.     peers = us->peer.data; /* 真实节点的集群 */  
  25.     npoints = peers->total_weight * 160;  
  26.   
  27.     /* 一共创建npoints个虚拟节点 */  
  28.     size = sizeof(ngx_http_upstream_chash_points_t) +   
  29.         sizeof(ngx_http_upstream_chash_point_t) * (npoints - 1);  
  30.   
  31.     points = ngx_palloc(cf->pool, size);  
  32.     if (points == NULL)  
  33.         return NGX_ERROR;  
  34.   
  35.     points->number = 0;  
  36.   
  37.     /* 初始化所有的虚拟节点 */  
  38.     for (peer = peers->peer; peer; peer = peer->next) {  
  39.         server = &peer->server; /* server指令的第一个参数, server.name */  
  40.           
  41.         /* Hash expression is compatible with Cache::Memcached::Fast: 
  42.          * crc32(HOST 0 PORT PREV_HASH). 
  43.          */  
  44.         if (server->len >= 5 && ngx_strncasecmp(server->data, (u_char *) "unix:", 5) == 0)  
  45.         {  
  46.             host = server->data + 5;  
  47.             host_len = server->len - 5;  
  48.             port = NULL;  
  49.             port_len = 0;  
  50.             goto done;  
  51.         }  
  52.   
  53.         /* 把每个peer的server成员，解析为HOST和PORT */  
  54.         for (j = 0; j < server->len; j++) {  
  55.             c = server->data[server->len - j - 1];  
  56.   
  57.             if (c == ":") {  
  58.                 host = server->data;  
  59.                 host_len = server->len - j - 1;  
  60.                 port = server->data + server->len - j;  
  61.                 port_len = j;  
  62.                 goto done;  
  63.             }  
  64.   
  65.             if (c < '0' || c > '9') /* 表示没有指定端口 */  
  66.                 break;  
  67.         }  
  68.   
  69.         host = server->data;  
  70.         host_len = server->len;  
  71.         port = NULL;  
  72.         port_len = 0;  
  73.   
  74.    done:  
  75.         /* 根据解析peer的server成员所得的HOST和PORT，计算虚拟节点的base_hash值 */  
  76.         ngx_crc32_init(base_hash);  
  77.         ngx_crc32_update(&base_hash, host, host_len);  
  78.         ngx_crc32_update(&base_hash, (u_char *) "", 1); /* 空字符串包含字符\0 */  
  79.         ngx_crc32_update(&base_hash, port, port_len);  
  80.           
  81.         /* 对于归属同一个真实节点的虚拟节点，它们的base_hash值相同，而prev_hash不同 */  
  82.         prev_hash.value = 0;  
  83.         npoints = peer->weight * 160;  
  84.   
  85.         for (j = 0; j < npoints; j++) {  
  86.             hash = base_hash;  
  87.             ngx_crc32_update(&hash, prev_hash.byte, 4);  
  88.             ngx_crc32_final(hash);  
  89.   
  90.             points->point[points->number].hash = hash; /* 虚拟节点的哈希值 */  
  91.             points->point[points->number].server = server; /* 虚拟节点所归属的真实节点，对应真实节点的server成员 */  
  92.             points->number++;  
  93.   
  94. #if (NGX_HAVE_LITTLE_ENDIAN)  
  95.            prev_hash.value = hash;  
  96. #else  
  97.            prev_hash.byte[0] = (u_char) (hash & 0xff);  
  98.            prev_hash.byte[1] = (u_char) ((hash >> 8) & 0xff);  
  99.            prev_hash.byte[2] = (u_char) ((hash >> 16) & 0xff);  
  100.            prev_hash.byte[3] = (u_char) ((hash >> 24) & 0xff);  
  101. #endif  
  102.         }     
  103.     }  
  104.   
  105.     /* 使用快速排序，使虚拟节点数组的元素，按照其hash值从小到大有序 */  
  106.     ngx_qsort(points->point, points->number, sizeof(ngx_http_upstream_chash_point_t),  
  107.         ngx_http_upstream_chash_cmp_points);  
  108.   
  109.     /* 如果虚拟节点数组中，有多个元素的hash值相同，只保留第一个 */  
  110.     for (i = 0, j = 1; j < points->number; j++)  
  111.         if (points->point[i].hash != points->point[j].hash)  
  112.             points->point[++i] = points->point[j];  
  113.   
  114.     /* 经过上述步骤后，虚拟节点数组中的元素，有序而不重复 */  
  115.     points->number = i + 1;  
  116.      
  117.     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);  
  118.     hcf->points = points; /* 保存虚拟节点数组 */  
  119.   
  120.     return NGX_OK;  
  121. }  
[java]  view plain  copy
  1. static int ngx_libc_cdel ngx_http_upstream_chash_cmp_points(const void *one, const void *two)  
  2. {  
  3.     ngx_http_upstream_chash_point_t *first = (ngx_http_upstream_chash_point_t *) one;  
  4.     ngx_http_upstream_chash_point_t *second = (ngx_http_upstream_chash_point_t *) two;  
  5.   
  6.     if (first->hash < second->hash)  
  7.         return -1;  
  8.     else if (first->hash > second->hash)  
  9.         return 1;  
  10.     else  
  11.         return 0;  
  12. }  

 

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

 

收到一个请求后，一般使用的反向代理模块（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 plain  copy
  1. static ngx_int_t ngx_http_upstream_init_chash_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us)  
  2. {  
  3.     uint32_t hash;  
  4.     ngx_http_upstream_hash_srv_conf_t *hcf;  
  5.     ngx_http_upstream_hash_peer_data_t *hp;  
  6.   
  7.     /* 调用hash算法的per request负载均衡初始化函数，创建和初始化请求的负载均衡数据 */  
  8.     if (ngx_http_upstream_init_hash_peer(r, us) != NGX_OK)  
  9.         return NGX_ERROR;  
  10.   
  11.     /* 重新指定peer.get，用于选取一个真实节点 */  
  12.     r->upstream->peer.get = ngx_http_upstream_get_chash_peer;  
  13.   
  14.     hp = r->upstream->peer.data;  
  15.     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);  
  16.   
  17.     /* 根据获取的本请求对应的hash指令的第一个参数值，计算请求的hash值 */  
  18.     hash = ngx_crc32_long(hp->key.data, hp->key.len);  
  19.   
  20.     /* 根据请求的hash值，找到顺时针方向最近的一个虚拟节点，hp->hash记录此虚拟节点 
  21.      * 在数组中的索引。 
  22.      */  
  23.     hp->hash = ngx_http_upstream_find_chash_point(hcf->points, hash);  
  24.   
  25.     return NGX_OK:  
  26. }  

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

[java]  view plain  copy
  1. static ngx_int_t ngx_http_upstream_init_hash_peer(ngx_http_request_t *r, ngx_http_upstream_srv_conf_t *us)  
  2. {  
  3.     ngx_http_upstream_hash_srv_conf_t *hcf;  
  4.     ngx_http_upstream_hash_peer_data_t *hp;  
  5.   
  6.     hp = ngx_palloc(r->pool, sizeof(ngx_http_upstream_hash_peer_data_t));  
  7.     if (hp == NULL)  
  8.         return NGX_ERROR:  
  9.   
  10.     /* 调用round robin的per request负载均衡初始化函数 */  
  11.     r->upstream->peer.data = &hp->rrp;  
  12.     if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK)  
  13.         return NGX_ERROR;  
  14.   
  15.     r->upstream->peer.get = ngx_http_upstream_get_hash_peer;  
  16.     hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);  
  17.   
  18.    /* 获取本请求对应的hash指令的第一个参数值，用于计算请求的hash值 */  
  19.     if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK)  
  20.         return NGX_ERROR;  
  21.     ...  
  22.     hp->conf = hcf;  
  23.     hp->tries = 0;  
  24.     hp->rehash = 0;  
  25.     hp->hash = 0;  
  26.     hp->get_rr_peer = ngx_http_upstream_get_round_robin_peer; /* round robin的peer.get函数 */  
  27.   
  28.     return NGX_OK;  
  29. }  

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

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

[java]  view plain  copy
  1. static ngx_uint_t ngx_http_upstream_find_chash_point(ngx_http_upstream_chash_points_t *points, uint32_t hash)  
  2. {  
  3.     ngx_uint_t i, j, k;  
  4.     ngx_http_upstream_chash_point_t *point;  
  5.       
  6.     /* find first point >= hash */  
  7.   
  8.     point = &points->point[0];  
  9.     i = 0;  
  10.     j = points->number;'  
  11.   
  12.     while(i < j) {  
  13.         k = (i + j) / 2;  
  14.   
  15.         if (hash > point[k].hash)  
  16.             i = k + 1;  
  17.         else if (hash < point[k].hash)  
  18.             j = k;  
  19.          else  
  20.             return k;  
  21.     }  
  22.   
  23.     return i;  
  24. }  

 

选取一个真实节点

 

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

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

 

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

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

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

 

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

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

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

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

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

[java]  view plain  copy
  1. static ngx_http_upstream_get_chash_peer(ngx_peer_connection_t *pc, void *data)  
  2. {  
  3.     ngx_http_upstream_hash_peer_data_t *hp = data; /* 请求的负载均衡数据 */  
  4.     time_t now;  
  5.     intptr_t m;  
  6.     ngx_str_t *server;  
  7.     ngx_int_t total;  
  8.     ngx_uint_t i, n, best_i;  
  9.     ngx_http_upstream_rr_peer_t *peer, *best;  
  10.     ngx_http_upstream_chash_point_t *point;  
  11.     ngx_http_upstream_chash_points_t *points;  
  12.     ngx_http_upstream_hash_srv_conf_t *hcf;  
  13.     ...  
  14.     pc->cached = 0;  
  15.     pc->connection = NULL:  
  16.     now = ngx_time();  
  17.     hcf = hp->conf;  
  18.     points = hcf->points; /* 虚拟节点数组 */  
  19.     point = &points->point[0]; /* 指向第一个虚拟节点 */  
  20.   
  21.     for ( ; ; ) {  
  22.         /* 在peer.init中，已根据请求的哈希值，找到顺时针方向最近的一个虚拟节点， 
  23.          * hash为该虚拟节点在数组中的索引。 
  24.          * 一开始hash值肯定小于number，之后每尝试一个虚拟节点后，hash++。取模是为了防止越界访问。 
  25.          */  
  26.         server = point[hp->hash % points->number].server;  
  27.         best = NULL;  
  28.         best_i = 0;  
  29.         total = 0;  
  30.   
  31.         /* 遍历真实节点数组，寻找可用的、该虚拟节点归属的真实节点(server成员相同)， 
  32.           * 如果有多个真实节点同时符合条件，那么使用轮询来从中选取一个真实节点。 
  33.           */  
  34.         for (peer = hp->rrp.peers->peer, i = 0; peer; peer = peer->next, i++) {  
  35.             /* 检查此真实节点在状态位图中对应的位，为1时表示不可用 */  
  36.             n = i / (8 * sizeof(uintptr_t));  
  37.             m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t));  
  38.             if (hp->rrp.tried[n] & m)  
  39.                 continue;              
  40.   
  41.             /* server指令中携带了down属性，表示后端永久不可用 */  
  42.             if (peer->down)  
  43.                 continue;  
  44.   
  45.             /* 如果真实节点的server成员和虚拟节点的不同，表示虚拟节点不属于此真实节点 */  
  46.             if (peer->server.len != server->len ||   
  47.                 ngx_strncmp(peer->server.data, server->data, server->len) != 0)  
  48.                 continue;  
  49.   
  50.            /* 在一段时间内，如果此真实节点的失败次数，超过了允许的最大值，那么不允许使用了 */  
  51.            if (peer->max_fails  
  52.                 && peer->fails >= peer->max_fails  
  53.                 && now - peer->checked <= peer->fail_timeout)  
  54.                 continue;  
  55.           
  56.             peer->current_weight += peer->effective_weight; /* 对每个真实节点，增加其当前权重 */  
  57.             total += peer->effective_weight; /* 累加所有真实节点的有效权重 */  
  58.   
  59.             /* 如果之前此真实节点发生了失败，会减小其effective_weight来降低它的权重。           
  60.              * 此后又通过增加其effective_weight来恢复它的权重。           
  61.              */          
  62.             if (peer->effective_weight < peer->weight)   
  63.                 peer->effective_weight++;  
  64.           
  65.             /* 选取当前权重最大者，作为本次选定的真实节点 */  
  66.             if (best == NULL || peer->current_weight > best->current_weight) {  
  67.                 best = peer;  
  68.                 best_i = i;  
  69.             }  
  70.         }  
  71.   
  72.         /* 如果选定了一个真实节点 */  
  73.         if (best) {  
  74.             best->current_weight -= total; /* 如果使用了轮询，需要降低选定节点的当前权重 */  
  75.             goto found;  
  76.         }  
  77.   
  78.         hp->hash++; /* 增加虚拟节点的索引，即“沿着顺时针方向” */  
  79.         hp->tries++; /* 已经尝试的虚拟节点数 */  
  80.   
  81.         /* 如果把所有的虚拟节点都尝试了一遍，还找不到可用的真实节点 */  
  82.         if (hp->tries >= points->number)  
  83.             return NGX_BUSY;  
  84.     }  
  85.   
  86. found: /* 找到了和虚拟节点相对应的、可用的真实节点了 */  
  87.     hp->rrp.current = best; /* 选定的真实节点 */  
  88.     /* 保存选定的后端服务器的地址，之后会向这个地址发起连接 */  
  89.     pc->sockaddr = peer->sockaddr;  
  90.     pc->socklen = peer->socklen;  
  91.     pc->name = &peer->name;  
  92.     best->conns++;  
  93.   
  94.     /* 更新checked时间 */  
  95.     if (now - best->checked > best->fail_timeout)  
  96.         best->checked = now;  
  97.   
  98.     n = best_i / (8 * sizeof(uintptr_t));  
  99.     m = (uintptr_t) 1 << best_i % (8 * sizeof(uintptr_t));  
  100.   
  101.     /* 对于本次请求，如果之后需要再次选取真实节点，不能再选取同一个了 */      
  102.     hp->rrp->tried[n] |= m;  
  103.   
  104.     return NGX_OK;  
  105. }  

文章标签：
负载均衡
云解析DNS
域名
算法
Java
负载均衡
应用服务中间件
缓存
索引
Unix
CDN
nginx
关键词：
Nginx负载均衡
负载均衡一致性哈希
负载均衡nginx
负载均衡hash
Nginx一致性
相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改，快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡（Server Load Balancer）是对多台云服务器进行流量分发的负载均衡服务，可以通过流量分发扩展应用系统对外的服务能力，通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
wqnmbdd
目录
相关文章
光明顶阳顶天
|
30天前
|
负载均衡 算法 搜索推荐
Nginx 常用的负载均衡算法
【10月更文挑战第17天】在实际应用中，我们需要根据具体的情况来选择合适的负载均衡算法。同时，还可以结合其他的优化措施，如服务器健康检查、动态调整权重等，来进一步提高负载均衡的效果和系统的稳定性。
光明顶阳顶天
113 59
java冯坚持
|
1月前
|
负载均衡 应用服务中间件 Linux
nginx学习，看这一篇就够了：下载、安装。使用：正向代理、反向代理、负载均衡。常用命令和配置文件,很全
这篇博客文章详细介绍了Nginx的下载、安装、配置以及使用，包括正向代理、反向代理、负载均衡、动静分离等高级功能，并通过具体实例讲解了如何进行配置。
java冯坚持
158 4
nginx学习，看这一篇就够了：下载、安装。使用：正向代理、反向代理、负载均衡。常用命令和配置文件,很全
mao29955
|
26天前
|
负载均衡 算法 应用服务中间件
Nginx 常用的负载均衡算法
【10月更文挑战第22天】不同的负载均衡算法各有特点和适用场景。在实际应用中，需要根据具体的业务需求、服务器性能和网络环境等因素来选择合适的算法。
mao29955
33 3
光明顶阳顶天
|
30天前
|
负载均衡 监控 应用服务中间件
除了 Nginx，还有以下一些常见的负载均衡工具
【10月更文挑战第17天】这些负载均衡工具各有特点和优势，在不同的应用场景中发挥着重要作用。选择合适的负载均衡工具需要综合考虑性能、功能、稳定性、成本等因素。
光明顶阳顶天
167 1
最好zzz
|
1月前
|
负载均衡 应用服务中间件 nginx
Nginx的6大负载均衡策略及权重轮询手写配置
【10月更文挑战第9天】 Nginx是一款高性能的HTTP服务器和反向代理服务器，它在处理大量并发请求时表现出色。Nginx的负载均衡功能可以将请求分发到多个服务器，提高网站的吞吐量和可靠性。以下是Nginx支持的6大负载均衡策略：
最好zzz
159 7
技术自由圈/原疯狂创客圈
|
1月前
|
负载均衡 算法 Java
腾讯面试：说说6大Nginx负载均衡？手写一下权重轮询策略?
尼恩，一位资深架构师，分享了关于负载均衡及其策略的深入解析，特别是基于权重的负载均衡策略。文章不仅介绍了Nginx的五大负载均衡策略，如轮询、加权轮询、IP哈希、最少连接数等，还提供了手写加权轮询算法的Java实现示例。通过这些内容，尼恩帮助读者系统化理解负载均衡技术，提升面试竞争力，实现技术上的“肌肉展示”。此外，他还提供了丰富的技术资料和面试指导，助力求职者在大厂面试中脱颖而出。
技术自由圈/原疯狂创客圈
45 0
腾讯面试：说说6大Nginx负载均衡？手写一下权重轮询策略?
java冯坚持
|
1月前
|
缓存 负载均衡 算法
nginx学习：配置文件详解，负载均衡三种算法学习，上接nginx实操篇
Nginx 是一款高性能的 HTTP 和反向代理服务器，也是一个通用的 TCP/UDP 代理服务器，以及一个邮件代理服务器和通用的 HTTP 缓存服务器。
java冯坚持
74 0
nginx学习：配置文件详解，负载均衡三种算法学习，上接nginx实操篇
游客cxtb2yf2r55as
|
1月前
|
开发框架 负载均衡 前端开发
Nginx负载均衡
Nginx负载均衡
游客cxtb2yf2r55as
38 1
游客cxtb2yf2r55as
|
1月前
|
负载均衡 Java 应用服务中间件
Nginx负载均衡配置
Nginx负载均衡配置
游客cxtb2yf2r55as
47 1
木子0204
|
1月前
|
负载均衡 算法 Java
java中nginx负载均衡配置
java中nginx负载均衡配置
木子0204
42 0

热门文章

最新文章

  • 1
    NAT负载均衡_ftp
  • 2
    高并发应用场景下的负载均衡与故障转移实践，AgileEAS.NET SOA 负载均衡介绍与实践
  • 3
    构建企业服务之windows 2008 负载均衡服务器部署
  • 4
    Apache + Tomcat 配置负载均衡
  • 5
    使用sidekick为minio集群提供负载均衡和高速缓存
  • 6
    搭建集群负载均衡系统（学习笔记）
  • 7
    LVS+keepalived负载均衡兼高可用集群配置
  • 8
    Dubbo与Zookeeper、SpringMVC整合和使用（负载均衡、容错）（转）
  • 9
    Linux中使用LVS实现负载均衡
  • 10
    负载均衡集群-LVS应用
  • 1
    一文读懂：Nginx 和Gateway
    630
  • 2
    nginx配置集群轮训策略
    672
  • 3
    Nginx笔记
    50
  • 4
    Heartbeat+Nginx实现高可用集群
    88
  • 5
    一文读懂HTTPS⭐揭秘加密传输背后的原理与Nginx配置攻略
    339
  • 6
    docker安装nginx
    82
  • 7
    Docker中报错 Error response from daemon: Conflict. The container name “/nginx01“ is already in use
    313
  • 8
    nginx 302 301 设置 url 转跳 nginx 资源重定向 nginx tcp 和 http 转发
    211
  • 9
    Nginx的referer参数的用法和原理
    853
  • 10
    nginx(1.13.7)首次安装出现：【make： *** 没有规则可以创建“default”需要的目标“build” 问题】解决措施
    606

    • 相关课程

    更多
  • 阿里云负载均衡SLB实战演练
  • Nginx企业级Web服务实战
  • Linux Web服务器Nginx搭建与配置
  • LVS负载均衡实战
  • 超大流量网站的负载均衡
  • 负载均衡入门与产品使用指南

    • 相关电子书

    更多
  • 架构分析、数据整合、负载均衡，梦想旅行解析云上实践
  • CentOS Nginx PHP JAVA 多语言镜像使用手
  • CentOS Nginx PHP JAVA多语言镜像使用手册

    • 相关实验场景

    更多
  • 使用CloudLens观测ALB下的网站访问情况
  • 使用CloudLens观测CLB下的网站访问情况
  • 使用SLB+2ECS+NAS，部署电商web网站的高可用架构
  • 基于云原生网关MSE-Higress插件实现WAF防护能力
  • 基于云原生网关实现微服务的多版本线上灰度
  • SLB负载均衡实践
    • 下一篇
    无影云桌面