hashring-rs

hashring is a minimal Rust implementation of consistent hashing, the technique described in the classic “Consistent Hashing and Random Trees” paper for distributing keys across a changing set of nodes with minimal remapping. The crate exposes a single HashRing<T, S> struct with three core operations — add, remove, and get — giving library authors an unopinionated foundation on which to build higher-level abstractions like virtual nodes and replica-aware lookups, both of which are demonstrated directly in the crate’s own README and test suite.

Internally, node keys are computed with a configurable BuildHasher (SipHash by default) and stored in a sorted vector, so lookups resolve via binary search rather than a full ring walk. Beyond the core three methods, hashring also supports batch insertion (batch_add), get_with_replicas for retrieving a key’s owner plus N follow-up replica nodes (useful for read replicas or fallback ordering), and standard iterator support. With a single dependency (siphasher) and roughly 300 lines of code, it’s designed to be embedded inside larger systems — caches, sharded databases, load balancers — where consistent hashing is one building block among many rather than the whole product.

What You Get

• A generic HashRing<T, S> struct usable with any type that implements Hash as a node
• add, remove, get, and batch_add methods for ring membership management
• get_with_replicas for fetching a key’s owner plus N follow-up replica nodes
• A pluggable BuildHasher (SipHash by default) for custom hash strategies
• IntoIterator support for walking ring nodes in ring order

Common Use Cases

• Sharding cache keys across a dynamic pool of cache servers
• Assigning partitions or shards to nodes in a distributed database
• Selecting primary and replica nodes for a key via get_with_replicas
• Load-balancing requests across backend servers with minimal reshuffling on scale events

Under The Hood

Architecture The crate is a single-file monolith (src/lib.rs, ~300 lines) with no module separation. The core type HashRing<T, S> wraps a Vec<Node<T>> kept sorted by each node’s hashed key, where the internal Node<T> struct implements Ord/PartialOrd purely by key comparison to enable binary search. The public surface is new/with_hasher/len/is_empty/add/batch_add/remove/get/get_with_replicas, plus an IntoIterator implementation via a small HashRingIterator wrapper. add() computes a key through the generic hash builder, pushes the node, and re-sorts the entire vector on every call — an intentional simplicity trade-off that batch_add works around by sorting once after inserting many nodes. get() and get_with_replicas() locate the ring successor via binary_search_by with explicit wrap-around handling for keys past the last node. The only extension point is the generic S: BuildHasher parameter; the crate deliberately stays this minimal so downstream code builds virtual-node layers on top rather than the crate absorbing that complexity itself.

Tech Stack The crate targets stable, beta, and nightly Rust (verified in CI via a .github/workflows/main.yml matrix build) and has exactly one external dependency, siphasher 0.3.1, used only to provide the default SipHasher implementation behind DefaultHashBuilder. There is no web framework, ORM, async runtime, or database client involved — this is a bare algorithms crate meant to be pulled into other systems as a building block. An unused nightly feature flag is declared in Cargo.toml but has no gated code behind it. The crate builds with plain cargo build/cargo test, and CI additionally runs cargo fmt --all -- --check and cargo clippy -- -D warnings, so formatting and lint violations fail the pipeline. It is published and consumed via crates.io as a library dependency.

Code Quality Tests live in a #[cfg(test)] mod tests block inside lib.rs itself rather than a separate tests/ directory, with six functions covering add/remove behavior, get distribution across nodes, get_with_replicas (including the case where the requested replica count exceeds the ring size), IntoIterator, and PartialEq equality between rings. Error handling favors idiomatic Rust: get and remove return Option rather than panicking, and the only unwraps appear in test setup code, not the library’s public paths. Naming mirrors standard-library collection conventions (get, is_empty, len), and type safety is enforced entirely through generics and trait bounds (T: Hash, S: BuildHasher) with no dynamic typing or unsafe blocks. CI enforces both formatting and clippy lints as hard gates, though there is no dedicated code-coverage tooling beyond a Codecov badge referenced in the README.

API Design The public API is deliberately tiny — new, with_hasher, add, remove, get, get_with_replicas, batch_add, len, is_empty, and an IntoIterator impl — and mirrors the ergonomics of standard-library collections such as HashMap (get returning Option<&T>, remove returning Option<T>). Getting started requires no boilerplate beyond HashRing::<T>::new() and calling add() with any Hash-implementing type. The main friction point is that customizing the hash function via with_hasher requires implementing the BuildHasher trait directly rather than accepting a simple closure, which adds ceremony for anyone who wants non-default hashing. Top-level documentation is solid — the crate-level doc comment includes a full worked virtual-node example that also renders on docs.rs — but per-method documentation is comparatively shallow, with edge-case behavior like the replica-count-exceeds-ring-size case described in prose rather than shown in an example.