Consistent Hashing with Bounded Loads & Rendezvous (HRW) Hashing

Ring-Based Consistent Hashing vs Rendezvous (HRW) Hashing

Three algorithms dominate production traffic routing and shard assignment:

• Karger's Ring with Virtual Nodes (VNodes): Map both keys and server replicas onto the 64-bit cyclic integer ring $[0, 2^{64}-1]$. Each physical server $s_i$ places $V$ virtual tokens $h(s_i \mathbin{\|} 0), \dots, h(s_i \mathbin{\|} V-1)$ onto a sorted array or balanced BST (std::map). A key $k$ routes to the first token clockwise with $\text{token} \ge h(k)$ via std::lower_bound in $O(\log(N V))$ time (wrapping around to index $0$ if $h(k)$ exceeds all tokens). Using $V = 150$ VNodes reduces load standard deviation to $\sigma / \mu \approx 1/\sqrt{150} \approx 8\%$.
• Consistent Hashing with Bounded Loads (Mirrokni et al., 2017): Given total active load $W$, number of nodes $N$, and slack parameter $\epsilon \in (0, 1]$ (typically $\epsilon = 0.25$), each server is assigned a hard maximum capacity $C = \lceil (1 + \epsilon) W / N \rceil$. When a key hashes to its primary clockwise server, if that server's current load is $< C$, it accepts the key; otherwise the key walks clockwise to the next server with spare capacity.
• Rendezvous / Highest Random Weight (HRW) Hashing: Requires zero ring state or VNode tables. To route key $k$ across nodes $\{s_1, \dots, s_N\}$, compute a joint score $w_i = \text{hash}(k, s_i)$ for each node and select $s^* = \arg\max_i w_i$. Achieving perfect $1/N$ uniform distribution without VNodes, HRW costs $O(N)$ per lookup (or $O(\log N)$ using a hierarchical skeleton tree), making it ideal for cluster sizes $N \le 64$ or weighted multi-replica selection (picking top-$R$ replicas in one pass).

Visualizing the $2^{64}$ Ring, VNode Arcs & $(1+\epsilon)$ Bounded-Load Overflow

Production C++20 Implementation: Bounded-Load Consistent Ring & Rendezvous (HRW) Router

// C++20: Consistent Hashing with (1 + eps) Bounded Loads & Rendezvous (HRW) Hashing
#include <vector>
#include <cstdint>
#include <algorithm>
#include <cmath>

class BoundedConsistentHashRing {
    struct VNode {
        uint64_t token;
        uint32_t nodeId;
        bool operator<(const VNode& o) const noexcept { return token < o.token; }
    };

    std::vector<VNode> ring_;
    std::vector<uint32_t> loads_;
    uint32_t totalLoad_ = 0;
    double epsilon_;

    static uint64_t mix64(uint64_t x) noexcept {
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

public:
    BoundedConsistentHashRing(uint32_t numNodes, uint32_t vnodesPerNode = 128, double eps = 0.25)
        : loads_(numNodes, 0), epsilon_(eps) {
        ring_.reserve(numNodes * vnodesPerNode);
        for (uint32_t n = 0; n < numNodes; ++n) {
            for (uint32_t v = 0; v < vnodesPerNode; ++v) {
                uint64_t seed = (static_cast<uint64_t>(n) << 32) | v;
                ring_.push_back({mix64(seed), n});
            }
        }
        std::sort(ring_.begin(), ring_.end());
    }

    uint32_t acquireRoute(uint64_t key) {
        const uint32_t N = static_cast<uint32_t>(loads_.size());
        const uint32_t cap = static_cast<uint32_t>(
            std::ceil((1.0 + epsilon_) * static_cast<double>(totalLoad_ + 1) / N)
        );

        uint64_t h = mix64(key);
        auto it = std::lower_bound(ring_.begin(), ring_.end(), VNode{h, 0});
        size_t idx = (it == ring_.end()) ? 0 : static_cast<size_t>(it - ring_.begin());

        for (size_t probes = 0; probes < ring_.size(); ++probes) {
            uint32_t candidate = ring_[idx].nodeId;
            if (loads_[candidate] < cap) {
                ++loads_[candidate];
                ++totalLoad_;
                return candidate;
            }
            idx = (idx + 1 == ring_.size()) ? 0 : idx + 1;
        }
        return ring_[idx].nodeId;
    }

    // Stateless Rendezvous (HRW) Hashing: O(N) time, O(1) auxiliary space
    static uint32_t rendezvousSelect(uint64_t key, const std::vector<uint32_t>& activeNodes) noexcept {
        uint32_t bestNode = 0;
        uint64_t maxWeight = 0;
        for (uint32_t nodeId : activeNodes) {
            uint64_t w = mix64(key ^ mix64(nodeId));
            if (w >= maxWeight) {
                maxWeight = w;
                bestNode = nodeId;
            }
        }
        return bestNode;
    }
};