第37周：L4/L7 负载均衡架构

字数统计: 3.4k字   |   阅读时长≈ 17分

第37周：L4/L7 负载均衡架构

目标：理解工业级负载均衡器（Maglev、Katran、Envoy）的设计思想，掌握一致性哈希算法与高并发调度。

1. 工业级 LB 概览

1.1 主要产品

1
2
3
4
5
6
7
8
9
10
11
12
┌──────────────────┬────────────┬──────────────┬──────────────┐
│ LB                │ 层级       │ 数据面       │ 性能         │
├──────────────────┼────────────┼──────────────┼──────────────┤
│ Google Maglev    │ L4         │ 内核+DPDK     │ 数十 Tbps    │
│ Facebook Katran  │ L4         │ XDP           │ 100M+ pps   │
│ Linux IPVS       │ L4         │ 内核 netfilter│ 1-3 Mpps    │
│ HAProxy          │ L4/L7      │ 用户态 epoll  │ 200K-500K pps│
│ Nginx            │ L7 (HTTP)  │ 事件驱动      │ 100K-300K pps│
│ Envoy            │ L4/L7      │ 线程池       │ 100K-200K pps│
│ Cilium LB        │ L4         │ eBPF/XDP     │ 10M+ pps    │
│ DPDK 自己的 LB    │ L4         │ DPDK PMD      │ 14M+ pps    │
└──────────────────┴────────────┴──────────────┴──────────────┘

1.2 设计目标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
现代 LB 的核心要求：

1. 高吞吐
   - 单节点 10M+ pps（小包）
   - 多节点线性扩展

2. 低延迟
   - L4 LB：< 100μs（首包）
   - L7 LB：< 1ms

3. 一致性
   - 相同 flow 始终到同一后端（会话保持）
   - 增删后端时最小化迁移

4. 高可用
   - 健康检查 + 故障自动摘除
   - 主备自动切换

5. 可扩展
   - 支持百万-千万级 QPS
   - 水平扩展

2. Maglev 详解

2.1 Maglev 概述

1
2
3
4
5
6
7
8
9
10
11
12
Google Maglev（2016 发布论文）：

  - Google 自研 L4 负载均衡
  - 替代了 LVS（Linux Virtual Server）
  - 部署在 Google 边缘，承载数百万 QPS
  - 基于一致性哈希的 ECMP 路由

核心特性：
  - 一致性哈希（minimal disruption）
  - 后端健康检查
  - 多租户支持
  - Maglev VFP（Virtual Forwarding Plane）

2.2 Maglev 一致性哈希

传统一致性哈希问题

1
2
3
4
5
6
7
8
9
10
11
12
传统一致性哈希（环形）：

  Hash 环：
  0 ────── 1000 ────── 2000 ────── 3000
            ↓            ↓
         Node A       Node B
         B1, B2       B3, B4
         
  问题：
  - 后端权重调节困难
  - 后端分布不均匀（特别是后端少时）
  - 删除一个节点，下一个节点压力大增

Maglev 哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Maglev 改进：

  - 预生成大表（通常 65537 或更大）
  - 每个后端在表中有若干 entries
  - Lookup 一次：O(1)

  步骤：
  1. 初始化表
  2. 后端 i 计算 prefer[i] = random("后端" + "i")
  3. 后端 i 计算 skip[i] = random_skip(i)
  4. populate:
       c[i] = 0
       for n in 0..M-1:
           while true:
               c[i] = (c[i] + skip[i]) % M
                 fill[n] = i
                 break

  5. Lookup(key):
       i = hash(key) % M
       return backend[fill[i]]

2.3 Maglev 表的生成

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
// maglev_consistent_hash.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// 64-bit hash
uint64_t hash64(const char *key, size_t len) {
    uint64_t h = 0xcbf29ce484222325ULL;  // FNV-1a 起始值
    for (size_t i = 0; i < len; i++) {
        h ^= (uint8_t)key[i];
        h *= 0x100000001b3ULL;
    }
    return h;
}

// 后端参数
typedef struct {
    const char *name;
    uint64_t    prefer;
    uint64_t    skip;
    int         count;  // 期望的 entries 数
} backend_t;

#define M 65537  // 大表大小（质数）

// Maglev 哈希表
typedef struct {
    int       *fill;        // 长度 M
    int        size;
    backend_t *backends;
    int        backend_count;
} maglev_t;

maglev_t *maglev_create(backend_t *backends, int n) {
    maglev_t *m = calloc(1, sizeof(*m));
    m->size = M;
    m->fill = malloc(sizeof(int) * M);
    m->backends = backends;
    m->backend_count = n;

    // 1. 计算总权重
    uint64_t total = 0;
    for (int i = 0; i < n; i++) {
        total += backends[i].count;
    }

    // 2. 按比例分配 entries
    for (int i = 0; i < n; i++) {
        // 计算每个后端的 entry 数
        backends[i].prefer = hash64("seed", 4) ^ (i * 0x9E3779B97F4A7C15ULL);
        backends[i].skip = hash64("skip", 4) ^ (i * 0x9E3779B97F4A7C15ULL);
    }

    // 3. Populate
    int *c = calloc(n, sizeof(int));
    int n_iter = 0;
    int sum_done = 0;
    int i = -1;
    while (sum_done < M) {
        i = (i + 1) % n;
        for (int k = 0; k < n; k++) {
            int idx = (c[i] + backends[i].skip) % M;
            c[i] = idx;
            if (m->fill[idx] == 0 || m->fill[idx] == -1) {
                m->fill[idx] = i;
                sum_done++;
                if (sum_done == M) break;
            }
        }
    }

    free(c);
    return m;
}

// 查询：O(1)
int maglev_lookup(maglev_t *m, const char *key, size_t len) {
    uint64_t h = hash64(key, len);
    int idx = h % m->size;
    return m->fill[idx];
}

2.4 Maglev 表的特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. 均匀性
   - 后端 i 在表中的 entries 数 = count[i]
   - 总 entries = M

2. 一致性
   - 增删后端时，只有少量 entries 变化
   - 通常 < 1/M (例如 M=65537 时只影响 < 0.002%)

3. 最小中断
   - 增减后端不重新分配整张表
   - 增量更新 entries

4. 负载均衡
   - 加权：调整每个后端的 count

2.5 实践：实现一致性哈希调度

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
// maglev_demo.c
#include <stdio.h>

int main() {
    // 3 个后端，期望权重 3:2:1
    backend_t backends[] = {
        {"web-1", 0, 0, 49152},  // 75%
        {"web-2", 0, 0, 32768},  // 50%
        {"web-3", 0, 0, 16385},  // 25%
    };
    int n = 3;

    maglev_t *m = maglev_create(backends, n);

    // 模拟 100 万次查询
    int counts[3] = {0};
    for (int i = 0; i < 1000000; i++) {
        char key[32];
        snprintf(key, sizeof(key), "client-%d", i);
        int idx = maglev_lookup(m, key, strlen(key));
        counts[idx]++;
    }

    printf("Distribution:\n");
    for (int i = 0; i < n; i++) {
        printf("  %s: %d (%.2f%%)\n",
               backends[i].name, counts[i],
               (double)counts[i] / 10000.0);
    }

    // 模拟节点新增
    backend_t new_backends[] = {
        {"web-1", 0, 0, 49152},
        {"web-2", 0, 0, 32768},
        {"web-3", 0, 0, 16385},
        {"web-4", 0, 0, 32768},  // 新增
    };
    maglev_t *m2 = maglev_create(new_backends, 4);

    // 比较迁移率
    int migrations = 0;
    for (int i = 0; i < 1000000; i++) {
        char key[32];
        snprintf(key, sizeof(key), "client-%d", i);
        int old_idx = maglev_lookup(m, key, strlen(key));
        int new_idx = maglev_lookup(m2, key, strlen(key));
        if (old_idx != new_idx) migrations++;
    }
    printf("\nMigration rate: %.2f%% (%d / 1M)\n",
           (double)migrations / 10000.0, migrations);

    return 0;
}

3. Katran 详解（Facebook）

3.1 Katran 概述

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
Katran（Facebook）：
  - 基于 XDP 的 L4 负载均衡
  - 完全运行在 Linux 内核
  - 单核可达 10M+ pps
  - 健康检查 + 一致性哈希

架构：
  ┌────────────────────────────────┐
  │  XDP Layer                     │
  │  (katran_lb.bpf.c)             │
  │  ┌──────────────────────────┐  │
  │  │  CH ring (Maglev-like)    │  │
  │  └──────────────────────────┘  │
  │  ┌──────────────────────────┐  │
  │  │  Real servers map         │  │
  │  └──────────────────────────┘  │
  │  ┌──────────────────────────┐  │
  │  │  Health check (userspace) │  │
  │  └──────────────────────────┘  │
  └────────────────────────────────┘
       ↑              ↓
       │  BPF map     │  packet events
       │              │
  ┌────┴──────────────┴────┐
  │  Katran userspace       │
  │  - Health checking     │
  │  - Map management      │
  │  - Statistics export   │
  │  - XDP attachment      │
  └─────────────────────────┘

3.2 Katran 源码分析

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
// katran_lb.bpf.c — 关键代码片段（简化）

#include <linux/bpf.h>
#include <linux/if_ether.h>
#include <linux/ip.h>
#include <bpf/bpf_helpers.h>

// 真实服务器表
struct {
    __uint(type, BPF_MAP_TYPE_HASH);
    __uint(max_entries, MAX_REALS);
    __type(key, __u32);          // real server index
    __type(value, struct real_definition);
} reals_map SEC(".maps");

// 一致性哈希 ring（Maglev 风格）
struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __uint(max_entries, RING_SIZE);
    __type(key, __u32);          // 位置
    __type(value, __u32);        // real server index
} ch_ring SEC(".maps");

// 主 XDP 程序
SEC("xdp")
int xdp_lb(struct xdp_md *ctx) {
    void *data = (void *)(long)ctx->data;
    void *data_end = (void *)(long)ctx->data_end;

    struct ethhdr *eth = data;
    if ((void *)(eth + 1) > data_end)
        return XDP_PASS;

    if (eth->h_proto != bpf_htons(ETH_P_IP))
        return XDP_PASS;

    struct iphdr *ip = (void *)(eth + 1);
    if ((void *)(ip + 1) > data_end)
        return XDP_PASS;

    // 1. 计算 hash（5 元组）
    __u32 hash = 0;
    if (ip->protocol == IPPROTO_TCP) {
        struct tcphdr *tcp = (void *)ip + (ip->ihl * 4);
        if ((void *)(tcp + 1) > data_end) return XDP_PASS;
        hash = jhash_2words(ip->saddr, tcp->source, CH_SEED1) ^
               jhash_2words(ip->daddr, tcp->dest, CH_SEED2);
    } else if (ip->protocol == IPPROTO_UDP) {
        struct udphdr *udp = (void *)ip + (ip->ihl * 4);
        if ((void *)(udp + 1) > data_end) return XDP_PASS;
        hash = jhash_2words(ip->saddr, udp->source, CH_SEED1) ^
               jhash_2words(ip->daddr, udp->dest, CH_SEED2);
    } else {
        return XDP_PASS;
    }

    // 2. 一致性哈希查找后端
    __u32 ring_idx = hash % RING_SIZE;
    __u32 *real_idx = bpf_map_lookup_elem(&ch_ring, &ring_idx);
    if (!real_idx)
        return XDP_PASS;

    // 3. 查 real server
    struct real_definition *real;
    real = bpf_map_lookup_elem(&reals_map, real_idx);
    if (!real || real->flags == F_DELETED)
        return XDP_PASS;

    // 4. DNAT
    ip->daddr = real->dst_addr;

    // 5. 重新计算校验和
    ip->check = 0;
    ip->check = bpf_csum_diff();

    // 6. 修改 MAC
    if (eth->h_dest) {  // 已知后端 MAC
        // 转发
    }

    // 7. 统计
    update_stats(*real_idx, ip->tot_len);

    // 8. 转发
    return bpf_redirect(real->ifindex, 0);
}

3.3 Katran 的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Katran 的关键优化：

1. Maglev 一致性哈希
   - O(1) lookup
   - 最小化迁移

2. LPM 优化
   - VIP 用 LPM trie 而不是 hash
   - 快速匹配目的 IP

3. 健康检查
   - 用户态线程定期探测
   - BPF map 反映状态

4. Per-CPU 统计
   - 避免锁

5. SIMD 优化
   - 校验和计算

4. Envoy 线程模型

4.1 Envoy 概述

1
2
3
4
5
6
7
8
9
10
11
12
13
Envoy（Lyft 开源，现为 CNCF 毕业项目）：

  - L4/L7 反向代理
  - 服务网格数据面（与 Istio 集成）
  - 高级路由、负载均衡、可观察性
  - 多语言过滤器（HTTP filter chain）

核心特性：
  - 线程模型
  - 监听器
  - 集群（cluster）
  - 路由
  - 过滤器链

4.2 Envoy 线程模型

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
Envoy 线程模型：

  ┌─────────────────────────────────────┐
  │           Main Thread               │
  │  - 启动 / 关闭 / 重新加载             │
  │  - 配置处理                          │
  │  - 监听器创建                        │
  └──────────────┬──────────────────────┘
                 │
                 │ Cluster Manager
                 │
  ┌──────────────┴──────────────────────┐
  │      Worker Thread(s)              │  ← 通常 = CPU 核心数
  │  - 监听 socket（shared）           │
  │  - 接受连接                         │
  │  - 数据包处理                       │
  │  - 过滤器链执行                     │
  └─────────────────────────────────────┘

每个 Worker：
  ┌─────────────┐
  │  Listener    │ → 多个
  │  (per thread)│
  │  Listener 0  │
  │  Listener 1  │
  └─────────────┘
  ┌─────────────┐
  │  Connection  │ → 大量并发连接
  │              │
  └─────────────┘
  ┌─────────────┐
  │  Filter      │ → 过滤器链
  │  Chain       │
  └─────────────┘

连接分配：
  - 通过 SO_REUSEPORT
  - 多个线程监听同一端口
  - 内核 hash 分配到不同线程

4.3 Envoy 过滤器链

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
# envoy.yaml — 过滤器链配置
listeners:
- name: listener_0
  address:
    socket_address:
      address: 0.0.0.0
      port_value: 8080
  filter_chains:
  - filters:
    # 1. 监听器过滤器
    - name: envoy.filters.network.listener
      typed_config:
        "@type": type.googleapis.com/envoy.extensions.filters.network.listener.v3.Listener
        listener_filters_timeout: 0s
    # 2. HTTP 连接管理
    - name: envoy.filters.network.http_connection_manager
      typed_config:
        "@type": type.googleapis.com/envoy.extensions.filters.network.http_connection_manager.v3.HttpConnectionManager
        stat_prefix: ingress_http
        route_config:
          name: local_route
          virtual_hosts:
          - name: backend
            domains: ["*"]
            routes:
            - match: { prefix: "/" }
              route: { cluster: web_service }
        http_filters:
        # HTTP 过滤器链
        - name: envoy.filters.http.router
        - name: envoy.filters.http.lua  # Lua 脚本
        - name: envoy.filters.http.rate_limit
        - name: envoy.filters.http.fault
    # 3. 原始 TCP 代理
    - name: envoy.filters.network.tcp_proxy
      typed_config:
        "@type": type.googleapis.com/envoy.extensions.filters.network.tcp_proxy.v3.TcpProxy
        stat_prefix: tcp
        cluster: tcp_service

4.4 Envoy 的过滤器类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Envoy 过滤器分类：

1. Listener 过滤器
   - 在连接被接受时运行
   - 例如：TLS inspector、proxy_protocol

2. Network 过滤器
   - 在 L4 处理
   - 例如：http_connection_manager、tcp_proxy、redis_proxy

3. HTTP 过滤器
   - 在 HTTP 协议层
   - 例如：router、rate_limit、fault、gzip、cors、jwt、lua、wasm

每个过滤器可：
  - 读写请求头
  - 修改 body
  - 决定是否继续
  - 短路返回

5. L7 负载均衡（Envoy 高级路由）

5.1 高级路由

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
# 复杂的 L7 路由
virtual_hosts:
- name: api
  domains: ["api.example.com"]
  routes:
  - match:
      prefix: "/v1/users"
      headers:
      - name: ":authority"
        string_match:
          exact: "api.example.com"
      query_parameters:
      - name: "version"
        string_match:
          exact: "2"
    route:
      cluster: user_service_v2

  - match:
      prefix: "/v1/"
      runtime_fraction:
        default_value:
          numerator: 50
          denominator: HUNDRED
        runtime_key: routing.v1.percent
    route:
      cluster: user_service_v1

  - match:
      prefix: "/v2/"
    route:
      weighted_clusters:
        clusters:
        - name: user_service_v2
          weight: 90
        - name: user_service_v2_canary
          weight: 10

5.2 重试与熔断

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
cluster:
  connect_timeout: 1s
  lb_policy: ROUND_ROBIN
  load_assignment:
    cluster_name: backend
    endpoints:
    - lb_endpoints:
      - endpoint:
          address: 10.0.0.1:8080

  # 重试策略
  retry_policy:
    num_retries: 3
    retry_back_off:
      base_interval: 0.1s
      max_interval: 1s
    retry_on: "5xx,gateway-error,connect-failure,refused-stream,reset"

  # 熔断器
  circuit_breakers:
  - thresholds:
    - priority: DEFAULT
      max_connections: 1000
      max_pending_requests: 100
      max_requests: 100
      max_retries: 5
      track_remaining: true

6. 性能对比

1
2
3
4
5
6
7
8
9
10
各类 LB 性能（典型 10GbE，64B 包）：

  方案                │ 单核 pps   │ 延迟       │ CPU 占用
  ─────────────────────┼──────────  │──────────  │─────────
  Maglev（DPDK）        │ 12-14M     │ < 200ns    │ 1 核
  Katran（XDP）         │ 10-14M     │ < 500ns    │ 0.8 核
  IPVS（内核）          │ 3-5M       │ < 5μs      │ 2 核
  HAProxy（用户态）      │ 1-2M       │ < 100μs    │ 1 核
  Nginx（HTTP）         │ 0.5-1M     │ < 1ms      │ 1 核
  Envoy（HTTP）         │ 0.3-0.7M   │ < 1ms      │ 1 核

7. 一致性哈希补充

7.1 哈希函数选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
常见哈希函数：

1. CRC32
   - 硬件加速（CRC32C）
   - 速度快
   - 分布一般

2. FNV-1a（Maglev 使用）
   - 简单
   - 适合短字符串

3. xxHash
   - 极快
   - 分布好
   - 现代首选

4. SpookyHash
   - Jenkins 改进版
   - 高质量

5. CityHash / MurmurHash
   - Google / Austin Appleby
   - 工业级

7.2 实战代码（完整）

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
124
// consistent_hash.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

// xxHash 简化版
static uint64_t xxhash64(const void *key, size_t len, uint64_t seed) {
    const uint64_t PRIME1 = 0x9E3779B185EBCA87ULL;
    const uint64_t PRIME2 = 0xC2B2AE3D27D4EB4FULL;
    const uint64_t PRIME3 = 0x165667B19E3779F9ULL;
    const uint64_t PRIME4 = 0x85EBCA77C2B2AE63ULL;
    const uint64_t PRIME5 = 0x27D4EB2F165667C5ULL;

    uint64_t h64 = seed + PRIME5;
    h64 += (uint64_t)len;

    const uint8_t *p = (const uint8_t *)key;
    while (len >= 8) {
        uint64_t k1 = *(uint64_t *)p;
        k1 *= PRIME2;
        k1 = (k1 << 31) | (k1 >> 33);
        k1 *= PRIME1;
        h64 ^= k1;
        h64 = (h64 << 27) | (h64 >> 37);
        h64 = h64 * PRIME1 + PRIME4;
        p += 8; len -= 8;
    }

    while (len > 0) {
        h64 ^= (*p++) * PRIME5;
        h64 = (h64 << 11) | (h64 >> 53);
        h64 *= PRIME1;
        len--;
    }

    h64 ^= h64 >> 33;
    h64 *= PRIME2;
    h64 ^= h64 >> 29;
    h64 *= PRIME3;
    h64 ^= h64 >> 32;

    return h64;
}

#define BACKEND_COUNT 4
#define RING_SIZE 65537

uint32_t g_ring[RING_SIZE];

void populate_ring(const char *backends[], int weights[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += weights[i];

    // 计算每个后端在 ring 中的 entries 数
    int *counts = calloc(n, sizeof(int));
    for (int i = 0; i < RING_SIZE; i++) {
        // 按比例分配
        int idx = 0;
        int cumsum = 0;
        int target = (i * total) / RING_SIZE;
        for (int j = 0; j < n; j++) {
            cumsum += weights[j];
            if (target < cumsum) { idx = j; break; }
        }
        counts[idx]++;
    }

    // 随机填充
    srand(42);
    uint64_t *skips = malloc(n * sizeof(uint64_t));
    for (int i = 0; i < n; i++) {
        skips[i] = xxhash64(backends[i], strlen(backends[i]), 0) | 1;
    }

    int *c = calloc(n, sizeof(int));
    int n_filled = 0;
    int i = -1;
    while (n_filled < RING_SIZE) {
        i = (i + 1) % n;
        for (int k = 0; k < 1000; k++) {  // 防止死循环
            c[i] = (c[i] + skips[i]) % RING_SIZE;
            if (g_ring[c[i]] == 0xFFFFFFFF) {
                g_ring[c[i]] = i;
                n_filled++;
                break;
            }
        }
    }

    free(counts);
    free(skips);
    free(c);
}

int lookup(const char *key) {
    uint64_t h = xxhash64(key, strlen(key), 0);
    return g_ring[h % RING_SIZE];
}

int main() {
    const char *backends[] = {"web-1", "web-2", "web-3", "web-4"};
    int weights[] = {3, 2, 2, 1};

    memset(g_ring, 0xFF, sizeof(g_ring));
    populate_ring(backends, weights, 4);

    int counts[4] = {0};
    int N = 1000000;
    for (int i = 0; i < N; i++) {
        char key[32];
        snprintf(key, sizeof(key), "client-%d", i);
        counts[lookup(key)]++;
    }

    printf("Distribution (N=%d):\n", N);
    for (int i = 0; i < 4; i++) {
        printf("  %s: %d (%.2f%%, expected %.2f%%)\n",
               backends[i], counts[i],
               counts[i] * 100.0 / N,
               weights[i] * 100.0 / 8);
    }
    return 0;
}

8. 调度算法对比

算法 哈希分布 加权 增删迁移 复杂度
Round Robin 不均 简单 100% O(1)
Weighted RR 一般 支持 100% O(1)
Random 不均 困难 高 O(1)
一致性哈希（环形） 不均 复杂 ~50% O(log n)
Maglev 哈希 均匀 简单 < 1% O(1)
Rendezvous 均匀 简单 ~33% O(log n)

9. 工程实践要点

9.1 部署考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
部署 LB 的常见架构：

1. 边缘 LB（Edge LB）
   - 部署在 DC 边缘
   - 处理南北向流量
   - 应对外部攻击

2. 集群内 LB（East-West）
   - K8s 内部 Service
   - 服务间调用
   - 取代 kube-proxy

3. 全局 LB（GSLB）
   - 跨 DC / 跨区域
   - DNS 级别
   - Anycast IP

9.2 健康检查

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
// health_check.c — 简单 TCP 健康检查
#include <sys/socket.h>
#include <netinet/in.h>
#include <unistd.h>
#include <fcntl.h>
#include <poll.h>
#include <pthread.h>

typedef struct {
    char host[64];
    int port;
    int is_healthy;
    pthread_mutex_t lock;
} backend_health_t;

int tcp_probe(const char *host, int port, int timeout_ms) {
    int fd = socket(AF_INET, SOCK_STREAM, 0);
    if (fd < 0) return 0;

    // 设置非阻塞
    int flags = fcntl(fd, F_GETFL, 0);
    fcntl(fd, F_SETFL, flags | O_NONBLOCK);

    // 解析地址
    struct sockaddr_in addr = {
        .sin_family = AF_INET,
        .sin_port = htons(port),
    };
    inet_pton(AF_INET, host, &addr.sin_addr);

    // 发起连接
    int ret = connect(fd, (struct sockaddr *)&addr, sizeof(addr));
    if (ret < 0 && errno != EINPROGRESS) {
        close(fd);
        return 0;
    }

    // 等待连接完成
    struct pollfd pfd = {fd, POLLOUT, 0};
    ret = poll(&pfd, 1, timeout_ms);
    if (ret <= 0) {
        close(fd);
        return 0;
    }

    int err;
    socklen_t len = sizeof(err);
    getsockopt(fd, SOL_SOCKET, SO_ERROR, &err, &len);
    close(fd);

    return err == 0;
}

// 多线程健康检查
void *health_check_thread(void *arg) {
    backend_health_t *backends = (backend_health_t *)arg;
    int n = ...;  // 后端数量

    while (1) {
        for (int i = 0; i < n; i++) {
            int healthy = tcp_probe(backends[i].host, backends[i].port, 1000);
            pthread_mutex_lock(&backends[i].lock);
            backends[i].is_healthy = healthy;
            pthread_mutex_unlock(&backends[i].lock);
        }
        sleep(5);
    }
    return NULL;
}
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

主要涉及技术：
Java后端开发、Linux开发、
公众号开发、开源爱好者、Linux

联系QQ:562054870