选择算法

主线位置：请求主线的 upstream_peer 里，LoadBalancer::select 的第一步：选择器按键给出一串候选后端。本页讲这串候选怎么来；候选怎么按健康状态筛，见上一页 LoadBalancer。

flowchart TB
  bs["BackendSelection"] --> w["Weighted H"]
  bs --> k["KetamaHashing"]
  w --> fnv["FNVHash"]
  w --> rnd["Random"]
  w --> rr["RoundRobin"]
  w --> list["加权下标表"]
  k --> ring["Continuum"]
  ring --> crc["crc32 点"]
  w --> wi["WeightedIterator"]
  k --> oi["OwnedNodeIterator"]

选择算法在 pingora-load-balancing/src/selection/ 下，四个文件正文 397 行；一致性哈希环在单独的 crate pingora-ketama 里（609 行，只有一个 lib.rs），只被这里用。

实验平台：M2 Max、macOS 27、rustc 1.99.0，pingora 0.9.0，tokio 钉在 1.53.2（原因见怎么读这一卷），release 构建。下面的数字都来自 lb-lab/src/bin/dist.rs：10 万个键 key-0 到 key-99999，后端是 10.0.0.1:80 起的几个地址，只看每个键的首选。

两个 trait

BackendSelection：

pub trait BackendSelection: Sized {
    /// The [BackendIter] returned from iter() below.
    type Iter;

    /// The configuration type constructing [BackendSelection]
    type Config: Send + Sync;

    // ...
    fn build_with_config(backends: &BTreeSet<Backend>, _config: &Self::Config) -> Self {
        Self::build(backends)
    }

    /// The function to create a [BackendSelection] implementation.
    fn build(backends: &BTreeSet<Backend>) -> Self;
    // ...
    fn iter(self: &Arc<Self>, key: &[u8]) -> Self::Iter
    where
        Self::Iter: BackendIter;
}

选择器是不可变的：后端集合一变就整个重建（build），旧的留给还在用它的请求，所以 LoadBalancer 把它放在 ArcSwap 里。iter 收的是 &Arc<Self>，迭代器自己持有一份 Arc，不借用选择器。BackendIter 只有一个 fn next(&mut self) -> Option<&Backend>，注释说它「Similar to [Iterator] but allow self referencing」：返回的引用指向迭代器自己持有的那份选择器，标准库的 Iterator 表达不了这种借用。

crate 给了四个现成的类型（selection/mod.rs）：

pub type FNVHash = Weighted<fnv::FnvHasher>;
// ...
pub type Random = Weighted<algorithms::Random>;
/// Round robin selection on weighted backends
pub type RoundRobin = Weighted<algorithms::RoundRobin>;
/// Consistent Ketama hashing on weighted backends
pub type Consistent = consistent::KetamaHashing;

// TODO: least conn

前三个是同一个 Weighted<H>，只换「下一个下标」怎么算；还有一个拼错的 FVNHash 别名，#[doc(hidden)]，留着兼容旧代码。最少连接数（least conn）只有一行 TODO。tower 的负载均衡是另一种思路：P2C 随机挑两个、比较负载，见 tower 卷的 P2C；pingora 这里的算法都不看负载。

Weighted：一张加权下标表

Weighted::build：

    fn build(backends: &BTreeSet<Backend>) -> Self {
        assert!(
            backends.len() <= u16::MAX as usize,
            "support up to 2^16 backends"
        );
        let backends = Vec::from_iter(backends.iter().cloned()).into_boxed_slice();
        let mut weighted = Vec::with_capacity(backends.len());
        for (index, b) in backends.iter().enumerate() {
            for _ in 0..b.weight {
                weighted.push(index as u16);
            }
        }
        // ...

后端按 BTreeSet 的顺序（地址排序）编号，权重是几就在 weighted 里放几次自己的编号，用 u16 省内存。权重 1、2、3 的三个后端，表就是 [0, 1, 1, 2, 2, 2]。

WeightedIterator::next：

        if self.first {
            // initial hash, select from the weighted list
            self.first = false;
            let len = self.backend.weighted.len();
            let index = self.backend.weighted[self.index as usize % len];
            Some(&self.backend.backends[index as usize])
        } else {
            // fallback, select from the unique list
            // deterministically select the next item
            self.index = self.backend.algorithm.next(&self.index.to_le_bytes());
            let len = self.backend.backends.len();
            Some(&self.backend.backends[self.index as usize % len])
        }

首选从加权表里取：algorithm.next(key) 得到一个 u64，对表长取模。
备选从去重的后端表里取：把上一个下标的字节再喂给算法，对后端个数取模。备选不看权重。
这个迭代器永远不会自己结束，要靠 UniqueIterator 的 max_iterations 截断。

三种算法（algorithms.rs）：

任何 Hasher + Default 都直接是算法：新建一个 hasher，write(key)，finish()。FNVHash 就是 fnv::FnvHasher。
RoundRobin 是一个 AtomicUsize，next 忽略输入，fetch_add(1, Relaxed)。首选和备选都从这一个计数器取号，整个选择器共享。
Random 每次调 rand::thread_rng().gen()（crate 钉在 rand 0.8）。

四个权重为 1 的后端，10 万个键的首选分布：

== distribution of first choice, 100000 keys, 4 backends weight 1
FNVHash    10.0.0.1:80=24999 10.0.0.2:80=25001 10.0.0.3:80=25001 10.0.0.4:80=24999
Ketama     10.0.0.1:80=24178 10.0.0.2:80=23419 10.0.0.3:80=24535 10.0.0.4:80=27868
Random     10.0.0.1:80=25168 10.0.0.2:80=24786 10.0.0.3:80=24992 10.0.0.4:80=25054
RoundRobin 10.0.0.1:80=25000 10.0.0.2:80=25000 10.0.0.3:80=25000 10.0.0.4:80=25000
== weights 1,2,3,4
FNVHash    10.0.0.1:80=9925 10.0.0.2:80=19982 10.0.0.3:80=30105 10.0.0.4:80=39988
Ketama     10.0.0.1:80=10636 10.0.0.2:80=20364 10.0.0.3:80=30002 10.0.0.4:80=38998

FNV 的数字均匀得不像统计结果。fnv crate 是 FNV-1a：每个字节先异或进哈希、再乘一个奇数常量。异或和乘法的结果对 4 取余只取决于两个操作数各自对 4 的余数，所以哈希值对 4 的余数只由每个字节的低两位决定；这组键只在末尾几位数字上不同，余数几乎是依次轮转的。一致性哈希最不均匀，四个后端之间差了 4.4 个百分点，原因在后面的环上。

权重对首选生效，对备选不生效，权重为 0 时看得最清楚。三个后端，中间那个权重 0：

== weight 0 on .2 (others 1), FNVHash: first choice and fallbacks
first  {"10.0.0.1:80": 50000, "10.0.0.3:80": 50000}
second {"10.0.0.1:80": 33594, "10.0.0.2:80": 33074, "10.0.0.3:80": 33332}

权重 0 的后端在加权表里一格都没有，从不当首选；但在迭代器给出的第二个候选里，它和别人一样占三分之一。首选不能用时，它照样会被选中。想彻底摘掉一个后端，用 set_enable(false) 或者从发现结果里删掉，不要把权重设成 0。所有后端权重都是 0 时，加权表为空，取模直接 panic：

thread 'main' (5666124) panicked at ~/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/pingora-load-balancing-0.9.0/src/selection/weighted.rs:93:47:
attempt to calculate the remainder with a divisor of zero

release 构建也一样，整数除以零在 Rust 里不受溢出检查开关影响。

轮询加权重，是把同一个后端连着排几次。权重 3、1、1，连续 10 次 iter() 的首选：

RoundRobin .1 .1 .1 .2 .3 .1 .1 .1 .2 .3

权重 3 的后端连续拿 3 个请求，不会和别人交错。备选也从同一个计数器取号，上一页的动脑筋就是这件事的后果。

KetamaHashing：crc32 的环

一致性哈希（consistent hashing）的目标是：后端增减时，只有落在变动后端上的那部分键需要换后端。KetamaHashing 只是一层包装，环在 pingora-ketama 的 Continuum 里。build_with_config 把每个 TCP 地址变成一个 Bucket，UDS 地址直接丢掉（// FIXME: ketama only supports Inet addr, UDS addrs are ignored here）。

建环在 Continuum::new_with_version：

        for bucket in buckets {
            let mut hasher = Hasher::new();

            // We only do the following for backwards compatibility with nginx/memcache:
            // - Convert SocketAddr to string
            // - The hash input is as follows "HOST EMPTY PORT PREVIOUS_HASH". Spaces are only added
            //   for readability.
            // TODO: remove this logic and hash the literal SocketAddr once we no longer
            // need backwards compatibility
            // ...
            write!(&mut hash_bytes, "{}", bucket.node.ip()).unwrap();
            write!(&mut hash_bytes, "\0").unwrap();
            write!(&mut hash_bytes, "{}", bucket.node.port()).unwrap();
            hasher.update(hash_bytes.as_ref());

            // A higher weight will add more points for this node.
            let num_points = bucket.weight * version.point_multiple();

            // This is appended to the crc32 hash for each point.
            let mut prev_hash: u32 = 0;
            addrs.push(bucket.node);
            let node = addrs.len() - 1;
            for _ in 0..num_points {
                let mut hasher = hasher.clone();
                hasher.update(&prev_hash.to_le_bytes());

                let hash = hasher.finalize();
                ring.push(node as u16, hash);
                prev_hash = hash;
            }
        }

每个后端在环上放 weight × 160 个点（DEFAULT_POINT_MULTIPLE，注释说「copied from nginx」）。第 i 个点是 crc32("IP\0PORT" + 第 i-1 个点的哈希)（第一个点接的是 0），一个接一个串出来。
所有点按哈希排序，哈希相同的只留一个。
查找：crc32(key)，在排好序的点里二分（VersionedRing::node_idx），找第一个不小于它的点，到末尾就绕回开头。
迭代器从这个点出发顺着环往后走（get_addr）。相邻的点经常属于同一个后端，所以候选里有大量重复：
```
== iteration order for key "user-42" (first 8 items)
FNVHash    .4 .3 .2 .2 .4 .3 .2 .3
Ketama     .4 .4 .1 .3 .4 .1 .2 .2
RoundRobin .1 .2 .3 .4 .1 .2 .3 .4
```
UniqueIterator 把重复的滤掉，但重复的也算步数。select 的文档注释专门提到「In certain algorithm like Ketama hashing, the search for the next backend is linear and could take a lot steps」：后端多、又有一大片不健康时，max_iterations 太小会在找到健康后端之前就返回 None。
权重为 0 的 Bucket 直接 panic：Bucket::new 里 assert!(weight != 0, "weight must be at least one")。Backend 允许权重 0，所以一个权重 0 的后端会让一致性哈希的 build panic（实测 pingora-ketama-0.9.0/src/lib.rs:95:9: weight must be at least one），而 Weighted 只是不把它当首选。

每个后端 160 个点，总共 640 个点，四个后端拿到的弧长并不相等，这就是上面 23.4% 到 27.9% 的来源。点数越多越均匀，代价是环越大。

和 nginx 一致

pingora-ketama 的 Cargo 描述是「Rust port of the nginx consistent hash function」。仓库里的证据是 test-data/：一份 nginx 配置（hash $request_uri consistent;，9 个 10.0.0.x:443，每个 weight=100）、一个用 curl 请求随机路径的脚本（for i in {0..1000}，1001 次），和 nginx 访问日志里记下的「路径，上游地址」，测试 matches_nginx_sample_data 逐行比对。不在上游仓库里跑测试，把这份 CSV 拷出来，用同样的 9 个桶建 Continuum 自己比一遍：

== nginx sample (9 x weight 100), pingora-ketama Continuum vs nginx access log
match 1001/1001

1001 行全部一致（文件最后一行没有换行符，wc -l 显示 1000）。这份数据能证明的范围是：服务器写成 IP 字面量、权重相同、键是 $request_uri 的配置。pingora 哈希的是 IP 的文本形式，配置里写域名的 nginx 上游是什么情况，这份数据没有覆盖。

加一个、减一个后端

四个后端加一个 .5，或者删掉 .4，有多少键的首选变了：

== keys whose first choice changed: 4 -> 5 backends (add .5)
FNVHash    moved 80018/100000 = 80.0%
Ketama     moved 20931/100000 = 20.9%
== 4 -> 3 backends (remove .4)
FNVHash    moved 75037/100000 = 75.0%
Ketama     moved 27868/100000 = 27.9%

FNV 是「哈希对后端数取模」：4 变 5，一个键只有在哈希对 20 取模落在特定几个余数上时才不动，理论上留下 1/5，实测 80.0% 换了后端。4 变 3 换了 75.0%。缓存类的上游（每个后端各自缓存一部分键）用它，加一台机器就等于清空了大部分缓存。
一致性哈希加一个后端，只有 20.9% 的键换了后端，接近理想的 1/5；按环的构造，这些键只能是换到了新的 .5 上（新点插进环里，只会抢走它前面那一段弧）。删掉 .4，换了后端的正好是 27868 个键，和上面分布里 .4 拥有的键数一个不差：只有原来落在 .4 上的键移走，其他键都没动。

point_multiple 与 v2

0.7.0 起 KetamaHashing 有一个配置 KetamaConfig，唯一的字段 point_multiple: Option<u32>，用 LoadBalancer::from_backends_with_config 传进去。它只在打开 pingora-load-balancing 的 v2 feature 时生效：

        #[allow(unused)]
        let version = if let Some(point_multiple) = point_multiple {
            match () {
                #[cfg(feature = "v2")]
                () => Version::V2 { point_multiple },
                #[cfg(not(feature = "v2"))]
                () => Version::V1,
            }
        } else {
            Version::V1
        };

❗IMPORTANT

动脑筋：只依赖 pingora 门面（features = ["lb", ...]），用 KetamaConfig { point_multiple: Some(10) } 和默认配置各建一个四后端的 KetamaHashing。10 万个键里，有多少个键两边的首选相同？

提示：看上面 cfg 的两个分支，再看门面 crate 的 lb feature 打开了 pingora-load-balancing 的哪些 feature。答案在文末。

要用 V2，得直接依赖 pingora-load-balancing 并写上 features = ["v2"]。V2 的点是 6 字节（u32 哈希加 u16 下标，手工排布），V1 是 8 字节，排序换成 i_key_sort crate；它和 V1 在哈希冲突的处理上略有不同，tests/backwards_compat.rs 允许两者不一致的比例低于 0.1%。i_key_sort 不在本机的 cargo 缓存里，V2 没有实测。

📝NOTE

冷知识：0.8.0 之前，KetamaConfig 只在第一次构造时有效

d6060ed（「Add a configurable upgrade for pingora-ketama that reduces runtime cpu and memory」，首次发布于 0.7.0）加上了 KetamaConfig 和 V2。但 0.7.0 的 LoadBalancer 不保存配置：from_backends_with_config(backends, &config) 用它建了第一个选择器，之后每次 update 发现成员变化，回调里写的是 S::build(&backends)，配置回到默认。后台服务一跑起来，第一次发现之后用的就是 160 个点了。

c469430（「Fix a bug with the ketama load balancing where configurations were not persisted after updates」，首次发布于 0.8.0）给 LoadBalancer 加了 config: Option<S::Config> 字段，from_backends_with_config 的参数改成 Option<S::Config>（一个破坏性变更），update 改为有配置就 build_with_config。现在这段逻辑在 build_selector 里，LoadBalancer 和 0.9.0 的 LoadBalancerGroup 共用。0.8.0 的 CHANGELOG 记的就是提交标题这句话。

动脑筋答案

point_multiple Some(10) vs default, same first choice: 100000/100000

全部相同。门面 crate 的 lb feature 是 ["pingora-load-balancing", "proxy"]；Cargo.toml 里另外提到 pingora-load-balancing 的只有四个 TLS feature 的转发（pingora-load-balancing?/openssl 之类），没有 v2。没开 v2 时，build_with_config 里 Some(point_multiple) 走的是 #[cfg(not(feature = "v2"))] 那个分支，得到 Version::V1，point_multiple 被丢掉，没有警告也没有日志。两个选择器建出的是同一个每后端 160 点的环。

小结

选择器是不可变的，后端集合一变就整个重建；iter 给出无穷的候选序列，首选在前，靠 UniqueIterator 去重和截断。
Weighted 用一张「权重是几就放几次」的 u16 下标表，只有首选看权重，备选在去重后的后端里均匀挑；权重 0 的后端仍会被选为备选，全部为 0 时 build 之后第一次选择就除以零 panic。
RoundRobin 是全局的 fetch_add，加权轮询是连续几次同一个后端；Random 每次用 thread_rng。
KetamaHashing 每个后端放 weight × 160 个 crc32 点，1001 行 nginx 采样数据全部一致；加一个后端只迁移 20.9% 的键（FNV 取模是 80.0%），删一个后端只迁移它自己的键。
KetamaConfig::point_multiple 要开 pingora-load-balancing 的 v2 feature 才生效，否则静默退回默认；0.8.0 之前配置在第一次 update 后就丢了（c469430）。