阅读中文版本

Build a Consistent Hash Router

A consistent hash ring that maps keys to nodes with minimal remapping on node add or remove, using virtual nodes for balance and a sorted ring for O(log n) lookup.

consistent-hash-router/
├── src/ring.ts
├── src/router.ts
├── src/serialize.ts
├── tests/ring.test.ts
└── package.json

for (let i=0;i<v;i++) ring.push({pos:hash(node+":"+i), node}); ring.sort(byPos);

const h = hash(key); const i = lowerBound(ring, h); return ring[i % ring.length].node;

for (let i=0;i<v;i++) insert({pos:hash(node+":"+i), node});

ring = ring.filter(e => e.node !== node);

Project overview

A hash mod n router remaps every key when n changes, because every key hash is taken modulo a different number. Adding a node to a set of a hundred remaps all of them, which is a migration, not a scaling event. A consistent hash ring remaps only a fraction, because each key maps to a position on a ring, not a slot in an array.

The ring is a circle of positions from zero to the hash maximum. Each physical node contributes v virtual nodes, each hashed to a position on the ring. A key is hashed to a position, and the node that owns it is the first virtual node clockwise from that position. Adding a physical node inserts its v virtual nodes, and only the keys between the new positions and the previous owners remap, which is a fraction proportional to one over the node count.

The virtual nodes are what make the distribution balanced. A physical node with one position on the ring owns a random arc that may be large or small. A physical node with a hundred positions owns a hundred small arcs that average out, so no node gets a disproportionate share. The more virtual nodes, the better the balance, at the cost of a larger ring.

The binary search is what makes the lookup fast. A ring of a thousand virtual nodes is a sorted array, and finding the first position at or after a key hash is a lower-bound search in O(log n). A linear scan of a thousand entries per request is too slow; a binary search of ten comparisons is not.

The value of this project is the minimal remapping, not the hashing. A hash ring is easy to build; proving that adding a node remaps only a fraction of keys, and that the fraction is the right fraction, is the part worth learning, because that guarantee is what lets a cluster scale without a full migration.

What you will build

The project delivers five capabilities, each driven by a test:

• Virtual nodes for balance
• O(log n) ring lookup
• Minimal remapping on churn
• Weighted node capacity
• Ring serialization and restore

A sorted array of (hash, node) pairs forms the ring. Each physical node contributes v virtual nodes hashed onto the ring. A key maps to the first node clockwise from its hash, found by binary search. Adding a node inserts its v virtual nodes; removing a node deletes them, and only the keys between the affected arcs remap.

Architecture and data model

The ring is a sorted array of entries, each a position and a node name. The sort is by position, so a binary search can find the first entry at or after a key hash. The wrap-around is a modulo: if the hash is past the last position, the first entry on the ring owns the key.

The virtual node count v is a tunable that trades memory for balance. A hundred virtual nodes per physical node gives good balance for up to a few hundred physical nodes. A thousand is better for larger clusters but makes the ring larger and the binary search marginally slower.

The hash function is SHA-256 truncated to 53 bits, because JavaScript numbers are doubles and a 53-bit integer is the largest exact integer. The truncation does not affect the distribution, because the input space is still large and the output space is still uniform.

Adding a node inserts v entries and re-sorts. The re-sort is O(n log n) but n is the ring size, not the key count, so it is cheap relative to the key remapping it avoids. Removing a node filters out its v entries, which is O(n). Both are infrequent operations compared to routing.

The weighted node capacity is a multiplier on v. A node with twice the capacity of another contributes twice the virtual nodes, so it owns twice the arc length and twice the keys. This lets the ring respect heterogeneous hardware without separate rings per tier.

The serialization writes the ring as a list of entries. A router that restarts reads the list and rebuilds the sorted array, so the node set and the virtual positions are preserved. The serialization is the ring itself, not the key map, because the ring is small and the key map is not the router concern.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• A set of nodes that may join or leave

The dependencies cover the core needs:

• node:crypto (built-in) — SHA-256 ring positions

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

consistent-hash-router/ is organized so each concern is testable in isolation:

consistent-hash-router/
├── src/ring.ts
├── src/router.ts
├── src/serialize.ts
├── tests/ring.test.ts
└── package.json

Phase 1: Build the ring

For each node, hash v virtual positions onto the ring and keep the array sorted by position.

for (let i=0;i<v;i++) ring.push({pos:hash(node+":"+i), node}); ring.sort(byPos);

Virtual nodes spread each physical node across the ring for balance.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Route a key

Hash the key, binary-search the ring for the first position at or after the hash, and return that node.

const h = hash(key); const i = lowerBound(ring, h); return ring[i % ring.length].node;

The wrap-around modulo handles keys that hash past the last position.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Add a node

Insert v virtual nodes for the new node and keep the ring sorted; only keys in the new arcs remap.

for (let i=0;i<v;i++) insert({pos:hash(node+":"+i), node});

A re-sort after insert is cheaper than a full rebuild for small churn.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Remove a node

Delete all virtual nodes for the removed node; keys in the freed arcs remap to the next clockwise node.

ring = ring.filter(e => e.node !== node);

Removal does not re-hash the remaining nodes, so their keys stay mapped.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Build a ring of five nodes, route a thousand keys, and record the mapping; add a sixth node and assert only about a sixth of keys remap; remove a node and assert only its keys remap; assert the distribution across nodes is balanced within a tolerance.

The remapping test builds a ring of five nodes, routes a thousand keys, and records the mapping. It adds a sixth node, routes the same keys, and asserts that only about a sixth of keys remapped, because the new node owns about a sixth of the ring. The assertion is a tolerance, not an exact count, because the virtual positions are random.

The removal test removes a node and asserts that only the keys that node owned remapped, and they remapped to the next clockwise node. The keys the removed node did not own stay mapped, because their positions on the ring did not change.

The balance test routes a million keys across five nodes and asserts each node gets about a fifth, within a tolerance. A skewed distribution that gives one node forty percent means v is too low or the hash is biased.

The wrap-around test hashes a key past the last position on the ring and asserts it maps to the first node, proving the modulo handles the circle. The binary-search test routes a key and asserts the lookup does fewer than log2(ring size) comparisons.

The weighted test gives one node twice the virtual nodes and asserts it gets about twice the keys. The serialization test writes the ring, reads it back, and asserts every key routes to the same node before and after.

pnpm vitest run

Observability

Track the virtual nodes for balance rate, the consistent-hash resource usage, and the error count as the three primary signals for the consistent-hash-router system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the o(log n) ring lookup alongside the virtual nodes for balance so a correlation is visible at a glance, because a rising o(log n) ring lookup with a stable virtual nodes for balance means the system is doing more work per unit, not that it is failing.

Log every build the ring transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the consistent-hash identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the virtual nodes for balance error rate crossing a threshold, the consistent-hash utilization exceeding a percentage, and the o(log n) ring lookup latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The consistent-hash-router system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Keep the ring in every router instance, so a routing decision is a local binary search with no network hop. Serialize the ring to a shared store, such as a database or a config service, on every node change, so all instances converge to the same ring without each rebuilding independently.

A node change is a two-step process: update the shared ring, then notify the instances to reload. An instance that reloads before the shared ring is updated routes against a stale ring, which is correct but not optimal. The convergence is eventual, not immediate, and that is acceptable because the stale ring is a valid ring.

Choose v from the cluster size and the balance requirement. A cluster of ten nodes with v of a hundred gives good balance; a cluster of a thousand nodes may need v of a thousand. The memory cost is the ring size, which is nodes times v entries, and the lookup cost is log2 of that.

Do not use the ring for replication. Routing a key to a node tells you where the primary lives, but the ring does not place replicas. Replication is a separate concern that may use the ring, by routing the key plus a replica index, but that is a caller decision, not a ring feature.

Security considerations

Treat every input to the consistent-hash-router system as untrusted, because the virtual nodes for balance path is the one place an external caller controls what the system processes. Validate the input shape before any consistent-hash operation, and reject early with a clear error rather than letting a malformed input propagate into the build the ring phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:crypto credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured consistent-hash-router fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the virtual nodes for balance endpoint per caller, because an unbounded consistent-hash operation is a resource leak as much as a security problem. A caller that can trigger the route a key path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the build the ring logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The consistent-hash-router system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the consistent-hash structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• The ring is in-memory; a restart loses the node set unless restored from serialization.
• No replication; routing a key to a node does not replicate it, that is a separate concern.
• Hash collisions on virtual positions are possible but handled by dedup.

The ring is in memory. A restart loses the node set unless the ring is restored from serialization, so every instance should load the serialized ring on boot. A ring that is not serialized is a ring that forgets its nodes on restart, which is a bug in deployment, not in the router.

There is no replication. The router maps a key to a node, it does not copy the key to other nodes. Replication is a separate pattern that may use the router to place replicas, but the router itself is placement, not durability.

Hash collisions on virtual positions are possible but rare, because the hash space is large and the virtual node count is small relative to it. A collision is handled by dedup, keeping one entry per position, which slightly unbalances the ring but does not corrupt it.