pingora-ketama

Active contributors: yuchen, fdeng

Purpose

A pure-Rust implementation of the Ketama consistent-hashing algorithm. Used by pingora-load-balancing's Consistent selector to map a key (e.g. a request-derived hash) to a backend in a way that's stable as backends come and go.

Directory layout

pingora-ketama/src/
└── lib.rs              Continuum, Bucket, Node, the hash ring

Key abstractions

Type	File	What it is
Continuum	pingora-ketama/src/lib.rs	The hash ring of (hash, bucket index) pairs
Node	pingora-ketama/src/lib.rs	A backend identity (typically SocketAddr)
Bucket	pingora-ketama/src/lib.rs	A weighted entry in the ring

How it works

For each Bucket(node, weight), ketama generates weight * 160 virtual hash points spread around a 32-bit integer space. To find the bucket for a key, hash the key and walk forward to the first virtual point. If a node leaves, only its share of keys redistribute — the rest stay put.

The 0.7.0 release added a configurable runtime upgrade that reduces CPU and memory at lookup time. Lookup is O(log N) via binary search on a sorted vector of (u32 hash, bucket_idx).

The 0.8.0 release fixed a bug where ketama state wasn't being persisted across LoadBalancer::update calls — the new healthy set was rebuilding the ring from scratch and breaking sticky routing.

Integration points

• Consumed by pingora-load-balancing/src/selection/consistent.rs.
• Standalone enough that external crates can use it directly.

Entry points for modification

• Hash function tweaks → lib.rs.
• Different point-multiplier (160 is the libketama default) → lib.rs.

Key source files

File	Purpose
pingora-ketama/src/lib.rs	Whole crate