负载均衡算法解析

1、nginx-轮询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
static ngx_http_upstream_rr_peer_t *
ngx_http_upstream_get_peer(ngx_http_upstream_rr_peer_data_t *rrp)
{
    time_t                        now;            // 当前时间
    uintptr_t                     m;              // 位掩码
    ngx_int_t                     total;          // 总权重
    ngx_uint_t                    i, n, p;       // 循环计数器和索引
    ngx_http_upstream_rr_peer_t  *peer, *best;  // 指向当前和最佳服务器的指针

    now = ngx_time();

    // 初始化最佳服务器为 NULL 和总权重为 0
    best = NULL;
    total = 0;

    // 避免编译器警告，如果未使用变量 p
#if (NGX_SUPPRESS_WARN)
    p = 0;
#endif

    // 遍历所有后端服务器
    for (peer = rrp->peers->peer, i = 0;
         peer;
         peer = peer->next, i++)
    {
        // 计算位数组索引和位掩码
        n = i / (8 * sizeof(uintptr_t)); // 索引为当前服务器编号除以每个 uintptr_t 能存储的位数
        m = (uintptr_t) 1 << i % (8 * sizeof(uintptr_t)); // 计算位掩码

        // 如果当前服务器已经被尝试过，则跳过
        if (rrp->tried[n] & m) {
            continue;
        }

        // 如果服务器处于宕机状态，则跳过
        if (peer->down) {
            continue;
        }

        // 如果服务器的失败次数超过了允许的最大失败次数，并且当前时间距离上次检查时间小于失败超时时间，则跳过
        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            continue;
        }

        // 如果服务器达到最大连接数限制，则跳过
        if (peer->max_conns && peer->conns >= peer->max_conns) {
            continue;
        }

        // 增加服务器的当前权重，并将其加入总权重
        peer->current_weight += peer->effective_weight;
        total += peer->effective_weight;

        // 如果服务器的有效权重小于其声明的权重，则增加有效权重
        if (peer->effective_weight < peer->weight) {
            peer->effective_weight++;
        }

        // 选择当前权重最高的服务器作为最佳服务器
        if (best == NULL || peer->current_weight > best->current_weight) {
            best = peer;
            p = i; // 记录最佳服务器的索引
        }
    }

    // 如果没有找到合适的服务器，返回 NULL
    if (best == NULL) {
        return NULL;
    }

    // 设置当前选择的服务器
    rrp->current = best;

    // 更新位数组以记录已尝试的服务器
    n = p / (8 * sizeof(uintptr_t));
    m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));
    rrp->tried[n] |= m;

    // 从最佳服务器的当前权重中减去总权重，为下一次选择做准备
    best->current_weight -= total;

    // 如果当前时间距离最佳服务器的上次检查时间超过失败超时时间，则更新检查时间
    if (now - best->checked > best->fail_timeout) {
        best->checked = now;
    }

    // 返回选择的最佳服务器
    return best;
}
C

2、nginx-ip_hash

1
2
3
4
5
6
7
8
9
10
upstream rrBackend {
    ip_hash;
    server localhost:8001 weight=1;
    server localhost:8002 weight=2;
    server localhost:8003 weight=3;
}

location /rr {
    proxy_pass http://rrBackend;
}
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
ngx_http_upstream_get_ip_hash_peer(ngx_peer_connection_t *pc, void *data)
{
    ngx_http_upstream_ip_hash_peer_data_t  *iphp = data;

    time_t                        now;
    ngx_int_t                     w;
    uintptr_t                     m;
    ngx_uint_t                    i, n, p, hash;
    ngx_http_upstream_rr_peer_t  *peer;

    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                   "get ip hash peer, try: %ui", pc->tries);

    // 对轮询节点的peers进行读锁定
    ngx_http_upstream_rr_peers_rlock(iphp->rrp.peers);

    // 如果尝试次数超过20次或者只有一个后端节点，则直接返回轮询算法的结果
    if (iphp->tries > 20 || iphp->rrp.peers->single) {
        ngx_http_upstream_rr_peers_unlock(iphp->rrp.peers);
        return iphp->get_rr_peer(pc, &iphp->rrp);
    }

    now = ngx_time();

    pc->cached = 0;
    pc->connection = NULL;

    hash = iphp->hash;

    for ( ;; ) {

        // 计算哈希值，这里只取地址的前三位
        for (i = 0; i < (ngx_uint_t) iphp->addrlen; i++) {
            hash = (hash * 113 + iphp->addr[i]) % 6271;
        }

        // 对总权重取余，使得请求更加均匀的分散到server
        w = hash % iphp->rrp.peers->total_weight;
        peer = iphp->rrp.peers->peer;
        p = 0;

        // 遍历peers，找到权重匹配的peer，权重值越大，越容易得到这个请求
        while (w >= peer->weight) {
            w -= peer->weight;
            peer = peer->next;
            p++;
        }

        // 检查这个peer是否被尝试过
        n = p / (8 * sizeof(uintptr_t));
        m = (uintptr_t) 1 << p % (8 * sizeof(uintptr_t));

        // 如果已经尝试过这个peer，则跳过
        if (iphp->rrp.tried[n] & m) {
            goto next;
        }

        ngx_log_debug2(NGX_LOG_DEBUG_HTTP, pc->log, 0,
                       "get ip hash peer, hash: %ui %04XL", p, (uint64_t) m);

        // 对选定的peer进行加锁
        ngx_http_upstream_rr_peer_lock(iphp->rrp.peers, peer);

        // 如果peer处于down状态，则解锁并跳过
        if (peer->down) {
            ngx_http_upstream_rr_peer_unlock(iphp->rrp.peers, peer);
            goto next;
        }

        // 如果peer失败次数超过阈值并且检查时间在失败超时时间内，则解锁并跳过
        if (peer->max_fails
            && peer->fails >= peer->max_fails
            && now - peer->checked <= peer->fail_timeout)
        {
            ngx_http_upstream_rr_peer_unlock(iphp->rrp.peers, peer);
            goto next;
        }

        // 如果peer的连接数超过最大连接数限制，则解锁并跳过
        if (peer->max_conns && peer->conns >= peer->max_conns) {
            ngx_http_upstream_rr_peer_unlock(iphp->rrp.peers, peer);
            goto next;
        }

        // 如果没有上述情况，则选择此peer
        break;

    next:

        // 如果尝试次数超过20次，则返回轮询算法的结果
        if (++iphp->tries > 20) {
            ngx_http_upstream_rr_peers_unlock(iphp->rrp.peers);
            return iphp->get_rr_peer(pc, &iphp->rrp);
        }
    }

    // 设置当前选择的peer
    iphp->rrp.current = peer;

    // 设置pc结构体的字段，以反映选定的peer
    pc->sockaddr = peer->sockaddr;
    pc->socklen = peer->socklen;
    pc->name = &peer->name;

    // 增加peer的连接数
    peer->conns++;

    // 更新peer的检查时间
    if (now - peer->checked > peer->fail_timeout) {
        peer->checked = now;
    }

    // 解锁选定的peer
    ngx_http_upstream_rr_peer_unlock(iphp->rrp.peers, peer);
    ngx_http_upstream_rr_peers_unlock(iphp->rrp.peers);

    // 在trie中标记已经尝试过这个peer
    iphp->rrp.tried[n] |= m;
    iphp->hash = hash;

    // 函数返回成功
    return NGX_OK;
}
C

3、hash

使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
upstream myapp {
        hash $http_x_real_ip;  # 使用 X-Real-IP 头部的值进行哈希
        server backend1.example.com weight=1;
        server backend2.example.com weight=2;
    }

//或者

upstream myapp {
        hash $http_x_forwarded_for;  # 使用 $http_x_forwarded_for 头部的值进行哈希
        server backend1.example.com weight=1;
        server backend2.example.com weight=2;
    }
JAVASCRIPT

当在 Nginx 配置中使用 hash $http_x_forwarded_for; 作为负载均衡的键时，hash用的就是真实客户端ip，ngx_http_complex_value 函数将用于计算 X-Forwarded-For HTTP 请求头的值，并将该值赋给 hp->key。以下是该过程的详细说明：

  1. 复杂值初始化:
    • 在 Nginx 配置阶段，当遇到 hash $http_x_forwarded_for; 配置时，相关的配置处理函数（如 ngx_http_upstream_hash）将初始化一个 ngx_http_complex_value_t 结构体，这里即 hcf->key。
  2. 请求处理阶段:
    • 当一个请求到达并需要进行上游处理时，ngx_http_upstream_init_hash_peer 函数被调用。
  3. 执行复杂值:
    • ngx_http_complex_value 函数被用来执行 hcf->key 中定义的复杂值，这个复杂值就是 $http_x_forwarded_for。
  4. 计算哈希键:
    • ngx_http_complex_value 函数解析 $http_x_forwarded_for，这通常意味着它将获取请求的 X-Forwarded-For 头的值。
  5. 值的变化:
    • 在执行 ngx_http_complex_value(r, &hcf->key, &hp->key) 之前，hp->key 是未初始化的。
    • 执行后，如果函数返回 NGX_OK，则 hp->key 将包含 X-Forwarded-For 头的值，这可能是一个单一的 IP 地址或者一个 IP 地址列表，具体取决于 X-Forwarded-For 头的内容。
  6. 错误处理:
    • 如果 ngx_http_complex_value 函数返回 NGX_ERROR，这通常意味着在尝试获取或计算 X-Forwarded-For 头的值时出现了问题，比如内存分配失败。在这种情况下，ngx_http_upstream_init_hash_peer 函数将返回 NGX_ERROR，导致当前请求的上游处理初始化失败。
  7. 调试日志:
    • 如果 ngx_http_complex_value 成功执行，将记录一条调试日志，显示 “upstream hash key” 以及计算出的键值。
  8. 继续处理:
    • 如果 ngx_http_complex_value 成功，函数将继续执行，hp->key 将用于后续的哈希计算和对等体选择过程。

总结来说，if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK) { return NGX_ERROR; } 这段代码是用来检查 ngx_http_complex_value 函数是否成功执行，并根据执行结果决定是否继续处理请求。如果 X-Forwarded-For 头存在且格式正确，hp->key 将被赋予相应的值；如果获取头信息失败或在执行过程中遇到错误，请求处理将被中止，并返回错误状态。

初始化：

1
2
3
4
5
6
7
8
9
10
11
tatic ngx_command_t  ngx_http_upstream_hash_commands[] = {

    { ngx_string("hash"),
      NGX_HTTP_UPS_CONF|NGX_CONF_TAKE12,
      ngx_http_upstream_hash,
      NGX_HTTP_SRV_CONF_OFFSET,
      0,
      NULL },

      ngx_null_command
};
C

设置值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
static char *
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_t   ccv;

    value = cf->args->elts;

    ngx_memzero(&ccv, sizeof(ngx_http_compile_complex_value_t));

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

    if (ngx_http_compile_complex_value(&ccv) != NGX_OK) {   //变量替换值，比如：hash $http_x_forwarded_for;
        return NGX_CONF_ERROR;
    }

    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,
                           "load balancing method redefined");
    }

    uscf->flags = NGX_HTTP_UPSTREAM_CREATE
                  |NGX_HTTP_UPSTREAM_WEIGHT
                  |NGX_HTTP_UPSTREAM_MAX_CONNS
                  |NGX_HTTP_UPSTREAM_MAX_FAILS
                  |NGX_HTTP_UPSTREAM_FAIL_TIMEOUT
                  |NGX_HTTP_UPSTREAM_DOWN;

    if (cf->args->nelts == 2) {
        uscf->peer.init_upstream = ngx_http_upstream_init_hash;

    } else if (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,
                           "invalid parameter \"%V\"", &value[2]);
        return NGX_CONF_ERROR;
    }

    return NGX_CONF_OK;
}

C

应用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
static ngx_int_t
ngx_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) {
        return NGX_ERROR;
    }

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

    if (ngx_http_upstream_init_round_robin_peer(r, us) != NGX_OK) {
        return NGX_ERROR;
    }

    r->upstream->peer.get = ngx_http_upstream_get_hash_peer;

    hcf = ngx_http_conf_upstream_srv_conf(us, ngx_http_upstream_hash_module);

    if (ngx_http_complex_value(r, &hcf->key, &hp->key) != NGX_OK) {
        return NGX_ERROR;
    }

    ngx_log_debug1(NGX_LOG_DEBUG_HTTP, r->connection->log, 0,  //这里日志会输出
                   "upstream hash key:\"%V\"", &hp->key);

    hp->conf = hcf;
    hp->tries = 0;
    hp->rehash = 0;
    hp->hash = 0;
    hp->get_rr_peer = ngx_http_upstream_get_round_robin_peer;

    return NGX_OK;
}
C

4、sticky

参考自：陶辉《深入剖析Nginx负载均衡算法》：https://www.nginx.org.cn/article/detail/440

#负载均衡 #nginx
负载均衡算法解析
https://zjfans.github.io/2024/06/02/Nginx负载均衡算法解析/
作者
张三疯
发布于
2024年6月2日
许可协议