From Hashmod to Jump Consistent Hash — stream-metrics-route Hash Algorithm Upgrade

Introduction

In the previous article, we reviewed the three-year evolution of stream-metrics-route and mentioned that the “dual hashmod scheduling” is the core scheduling mechanism of the entire gateway. However, during continuous production operation, one fatal flaw of hashmod became increasingly obvious—every scaling operation triggers full data redistribution.

This article documents the decision process of migrating from hash % N (hashmod) to Jump Consistent Hash, including the candidate algorithms evaluated, why Jump Hash was ultimately chosen, and the specific impact before and after migration.

This article’s technical details are based on stream-metrics-route’s evaluation document.

Problem: Hashmod’s Scaling Disaster

stream-metrics-route’s original implementation used the most basic hash % N for assigning metrics to backend nodes:

1
2
3
4
5
6

func hashMod(mode int, hash uint32) int {
    if mode <= 1 {
        return 0
    }
    return int(hash % uint32(mode))
}

This algorithm is so simple it barely needs explanation, but it has a fatal flaw: when the number of nodes N changes, almost all key assignments change.

flowchart TD
    B["Before N=3<br/>hash%3"] -->|"Add one node"| A["After N=4<br/>hash%4"]
    A --> R["Nearly all keys<br/>change target node<br/>100% redistribution"]
    style B fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style A fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style R fill:#ffcdd2,stroke:#f44336,color:#B71C1C

What does this mean in a metric routing scenario?

• Complete reassignment of all time series: Every metric is sent to a different stream_task_id
• Downstream vmagent aggregation state is destroyed: Stream aggregation’s in-memory state depends on stream_task_id for deduplication; when the ID changes, aggregation counters reset to zero
• Load imbalance during migration: A large number of time series scatter simultaneously
• Unnecessary network storm: All backend nodes receive a completely new dataset simultaneously

When your backend scales from 100 to 101 nodes, 100% of metrics are rerouted—this isn’t a “move a bit more” problem; it’s “scrap everything and start over.”

sequenceDiagram
    autonumber
    participant GW as Gateway
    participant V0 as vmagent-0
    participant V1 as vmagent-1
    participant V2 as vmagent-2
    participant V3 as vmagent-3 (New)

    Note over GW: N=3 to N=4 scaling triggered

    rect rgba(244,67,54,0.1)
        Note over GW,V3: 100% metric redistribution
        GW->>V0: key_A was on node 0
        GW->>V1: key_B was on node 1
        GW->>V2: key_C was on node 2
        GW->>V3: key_D might route to new node
        GW->>V0: key_E may have changed target
        Note over V0,V3: Most keys' target nodes changed
    end

    rect rgba(255,152,0,0.1)
        Note over V0,V3: vmagent stream aggregation state all invalidated
        V0-->>V0: Internal state cleared, re-accumulating
        V1-->>V1: Internal state cleared, re-accumulating
        V2-->>V2: Internal state cleared, re-accumulating
        V3-->>V3: Starting from zero
    end

For production environments, this “tear everything down for every scale-up” behavior is unacceptable. We need a consistent hashing algorithm—where node changes cause minimal key remapping.

Candidate Algorithm Evaluation

We evaluated five mainstream sharding algorithms, comparing across four dimensions:

Below we analyze each algorithm’s suitability for the stream-metrics-route scenario.

Ring Consistent Hash (Ring Hash)

Ring consistent hash is the most classic consistent hashing implementation, widely used in Dynamo, Cassandra, and other systems.

flowchart TD
    R["Hash ring 0 to 2^32-1<br/>nodes placed by hash value"]
    K1["key hashed"] -->|"Closest clockwise node"| N1["Node0 / Node1 / Node2"]
    N1 -.->|"Scale up"| N2["New node inserted<br/>only affects adjacent range<br/>~K/N keys migrate"]
    style R fill:#f5f5f5,stroke:#999,color:#333
    style K1 fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style N1 fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style N2 fill:#fff3e0,stroke:#FF9800,color:#BF360C

Each node owns the key range from its position clockwise to the next node. Pro: scaling only affects the adjacent range. Con: poor balance with few nodes, requiring virtual nodes (100 backends × 150 virtual nodes = 15000 ring nodes)—too heavy for a lightweight gateway.

Pros: Good scalability, new nodes only affect keys in the adjacent range.

Cons: Bare rings have poor balance—with few nodes, some nodes may get far more than 1/N of the key space. The solution is Virtual Nodes, where each physical node has multiple virtual nodes on the ring. But this brings two problems:

• Memory overhead: 100 backends × 150 virtual nodes = 15000 ring nodes to maintain
• Tuning complexity: Virtual node count needs tuning based on backend count and key distribution; there’s no “set it and forget it” parameter

For a lightweight gateway like stream-metrics-route, introducing a ring structure that needs tuning and maintenance is too heavy.

Rendezvous Hash (HRW)

Rendezvous hash, also known as Highest Random Weight (HRW), has a very intuitive approach: calculate a weight for each (key, node) pair, select the node with the highest weight.

1
2
3
4
5

// Pseudocode: calculate weight for each node
for _, node := range nodes {
    weight[hash(key + node) % MAX_INT]
}
// Select the node with the largest weight

Pros: Excellent balance, simple implementation, no virtual nodes needed.

Cons: Each lookup requires computing weights with all nodes—O(N) complexity. When the number of nodes N is large (e.g., hundreds of vmagent instances), each routing requires N hash calculations.

In our scenario, the gateway processes hundreds of thousands of metrics per second, each requiring two routing operations (task partition + node selection). O(N) complexity means performance is linearly inversely correlated with node count. This is far from ideal for a low-latency gateway.

Maglev Hash

Maglev hash was designed by Google and used in the Maglev load balancer. It achieves O(1) routing lookup through a precomputed lookup table.

flowchart TD
    K["Input key"] --> H["hash(key) mod M<br/>lookup M slots"]
    H --> N["Target node<br/>O(1) lookup"]
    N -.->|"On node change"| R["Rebuild entire lookup table<br/>O(N*M) memory"]
    style K fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style H fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style N fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style R fill:#ffcdd2,stroke:#f44336,color:#B71C1C

The lookup table size M is typically far larger than the node count (M » 100×N), and node changes require regenerating the whole table. We don’t need Maglev’s “minimal failure domain” feature but would bear its memory and complexity costs.

Pros: Lookup is indeed O(1), widely used internally at Google.

Cons: The lookup table size M is typically much larger than N (usually M » 100*N), meaning:

• Memory overhead: O(N*M) space, very large with many nodes
• Table rebuild: Node changes require regenerating the entire lookup table
• Minimal failure domain: Table quality depends on node permutation generation; some node combinations may produce poor distribution

For stream-metrics-route, we don’t need Maglev’s “minimal failure domain” feature (which matters for network load balancers), but we’d have to bear its memory and complexity costs.

Jump Consistent Hash

Finally, let’s look at the algorithm we ultimately chose. Jump Consistent Hash comes from a 2014 Google paper: “A Fast, Minimal Memory, Consistent Hash Algorithm”.

Its core idea can be described intuitively: Imagine you’re rolling a special die to decide where each key “jumps” to which bucket. When the number of buckets increases, existing keys have only a small probability of being “jumped” to a new bucket.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func JumpConsistentHash(key uint64, numBuckets int) int {
    if numBuckets <= 1 {
        return 0
    }
    var b int64 = -1
    var j int64 = 0
    for j < int64(numBuckets) {
        b = j
        key = key*2862933555777941757 + 1
        j = int64(float64(b+1) * (float64(int64(1)<<31) / float64((key>>33)+1)))
    }
    return int(b)
}

About 15 lines of code, zero memory allocation, no lookup table, no virtual nodes.

Key features:

1. Minimal migration: N → N+1, only about 1/(N+1) of keys need remapping
2. O(1) time complexity: Same speed as hashmod
3. Excellent distribution: Mathematically proven uniform distribution across buckets
4. Zero configuration: No parameters to tune

This is exactly what we need—hashmod’s performance and simplicity, plus consistent hashing’s minimal migration.

Algorithm Decision Flow

The following flowchart shows our decision logic for evaluating candidate algorithms:

flowchart TD
    Start["Need consistent hashing"] --> Q{"O(1) lookup?<br/>and O(1) memory?"}
    Q -->|"No, O(N) acceptable"| HRW["Rendezvous (HRW)<br/>O(N) time"]
    Q -->|"No, need min failure domain"| Maglev["Maglev<br/>O(N*M) memory"]
    Q -->|"No, O(log N) acceptable"| Ring["Ring hash<br/>needs virtual nodes"]
    Q -->|"Yes"| Jump["Jump Consistent Hash<br/>O(1) time + O(1) memory"]
    style Start fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style Q fill:#f3e5f5,stroke:#9C27B0,color:#4A148C
    style HRW fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style Maglev fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style Ring fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style Jump fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20

Our scenario requires O(1) lookup + O(1) memory + minimal migration; only Jump Consistent Hash satisfies all three.

For stream-metrics-route’s scenario—a high-performance gateway processing hundreds of thousands of metrics per second, requiring minimal migration and zero configuration—Jump Consistent Hash is the only choice that satisfies all constraints simultaneously.

Jump Consistent Hash Deep Dive

Algorithm Intuition

Jump Consistent Hash’s core idea can be understood through the following process:

1. Start from bucket 0
2. Continuously “jump” to higher bucket numbers
3. The probability of each jump decreases as the bucket count increases
4. The bucket you land on is the result

sequenceDiagram
    autonumber
    participant Key as Key hash value
    participant B0 as Bucket 0
    participant B1 as Bucket 1
    participant B2 as Bucket 2
    participant B3 as Bucket 3

    Note over Key: numBuckets = 4
    Key->>B0: b=-1 j=0 initialization
    Key->>Key: key = key * constant + 1
    Key->>B1: j = 1*(2^31/high_key) = 2
    Note over B0,B1: Skipped bucket 0 b=0
    Key->>Key: key = key * constant + 1
    Key->>B2: j = 3*(2^31/high_key) = 3
    Note over B1,B2: Skipped bucket 1 b=2
    Key->>Key: key = key * constant + 1
    Key->>B3: j = 4*(2^31/high_key) = 7
    Note over B2,B3: Skipped bucket 2 b=3
    Note over Key,B3: j=7 > numBuckets=4 stop
    Note over B3: Result: Bucket 3

The key point: when the number of buckets increases from N to N+1, only that one “jump” landing at j=N changes the existing allocation result. This mathematically guarantees approximately 1/(N+1) migration rate.

Scaling Impact Comparison

The diagram below intuitively shows the behavior difference between hashmod and Jump Hash during scaling:

flowchart TD
    HM["Hashmod<br/>100→101 nodes"] --> HM_A["hash_101 ≠ hash_100<br/>100% keys reassigned"]
    JH["Jump Hash<br/>100→101 nodes"] --> JH_A["~99% keys unchanged<br/>~1% migrate to new node"]
    HM_A -.->|"same scenario"| JH_A
    style HM fill:#ffcdd2,stroke:#f44336,color:#B71C1C
    style HM_A fill:#ffcdd2,stroke:#f44336,color:#B71C1C
    style JH fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style JH_A fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20

In concrete numbers:

• Hashmod: 100 → 101 nodes, 100% of stream_task_id values change
• Jump Hash: 100 → 101 nodes, only ~0.99% of stream_task_id values change

This means during scaling operations, vmagent’s stream aggregation state under Jump Hash is almost unaffected—99% of aggregation windows continue normal accumulation, with only about 1% needing reinitialization.

Migration Implementation

Code Changes

The change was very focused—replacing only the hash function, with the routing architecture and dual-hash logic entirely unchanged.

Old version (hashmod):

1
2
3
4
5

hash := common.SortLabelsHashKey(ts.Labels)
dime := common.hashMod(r.dimension, hash)     // hash % N → task partition ID
// ...
hashnode = common.SortLabelsHashKey(tmpLabels)
tmpch := common.hashMod(r.uplen, hashnode)     // hash % N → node selection

New version (Jump Consistent Hash):

1
2
3
4
5

hash := common.SortLabelsHashKey(ts.Labels)
dime := common.JumpConsistentHash(uint64(hash), r.dimension)  // stream_task_id
// ...
hashnode = common.SortLabelsHashKey(tmpLabels)
tmpch := common.JumpConsistentHash(uint64(hashnode), r.uplen) // node selection

Note that the FNV-32a hash calculation in SortLabelsHashKey, the filterLabels function, circuit breaker, and retry logic—all remain unchanged. The change is limited to the final routing function call.

flowchart TD
    A["Receive metrics"] --> B["relabel rules"]
    B --> C["filterLabels"]
    C --> D["FNV-32a hash"]
    D --> E["Routing function<br/>hashmod → Jump Hash"]
    E --> F["Async dispatch"]
    style A fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style B fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style C fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style D fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style E fill:#fff9c4,stroke:#fdd835,color:#F57F17
    style F fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20

Only the “Routing function” step changed from hashmod to Jump Hash; the rest of the pipeline (relabel, filterLabels, FNV-32a, circuit breaker, retry) is unchanged.

Breaking Change Assessment

The migration has one minor breaking change: the stream_task_id value for all metrics will change.

But the impact of this change is limited:

1. stream_task_id is a transparent label used by vmagent for aggregation deduplication—its specific value doesn’t matter as long as it’s consistent within the same dimension
2. Static YAML configuration means node changes already require a restart
3. A one-time switch can be done during a maintenance window, no need for gradual migration

flowchart TD
    M1["Confirm maintenance window"] --> M2["Stop stream-metrics-route"]
    M2 --> M3["Update binary<br/>with Jump Hash"]
    M3 --> M4["Start service"]
    M4 --> M5["Verify metric routing"]
    style M1 fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style M2 fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style M3 fill:#f3e5f5,stroke:#9C27B0,color:#4A148C
    style M4 fill:#fff3e0,stroke:#FF9800,color:#BF360C
    style M5 fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20

The migration is a one-time impact, with limited scope:

• Affected: all stream_task_id values change; vmagent aggregation state reinitialized
• Unaffected: relabel / filterLabels logic, circuit breaker / retry logic

Behavior After Migration

After migration, daily scaling operations become very elegant:

As cluster size grows, Jump Hash’s advantage becomes more pronounced—which is exactly where our production environment sits (hundreds of vmagent instances).

Performance Analysis

Benchmark Characteristics

Although Jump Hash has an internal for loop, due to the jump property, the expected number of loop iterations is O(ln N). For our node scale (usually < 200), the actual execution count is minimal. Compared to hashmod, there is no observable additional CPU overhead.

Production Benefits

flowchart TD
    B1["Scaling triggered"] --> B2["100% redistribution<br/>aggregation state lost<br/>accuracy drops"]
    B2 --> B3["Monitoring alert false positives"]
    A1["Scaling triggered"] --> A2["~1% redistribution<br/>99% aggregation state intact"]
    A2 --> A3["Frictionless scaling"]
    B3 -.->|"Same operation"| A3
    style B1 fill:#ffcdd2,stroke:#f44336,color:#B71C1C
    style B2 fill:#ffcdd2,stroke:#f44336,color:#B71C1C
    style B3 fill:#ffcdd2,stroke:#f44336,color:#B71C1C
    style A1 fill:#bbdefb,stroke:#2196F3,color:#1B5E20
    style A2 fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20
    style A3 fill:#c8e6c9,stroke:#4CAF50,color:#1B5E20

Summary of production advantages from Jump Hash:

1. Graceful scaling: Adding backends incrementally doesn’t cause full rebalancing
2. Stable aggregation: Maintains vmagent aggregation state continuity during scaling operations
3. Reduced load: Minimizes network traffic and processing overhead during migration
4. Predictable behavior: Distribution quality is mathematically guaranteed, no “unlucky distribution imbalance” situations

Theoretical Foundation

Jump Consistent Hash isn’t invented out of thin air; it has rigorous mathematical proof:

“A Fast, Minimal Memory, Consistent Hash Algorithm” by John Lamping and Eric Veach, Google, 2014 http://arxiv.org/abs/1406.2294

The paper proves two key properties:

1. Uniform distribution: Each bucket gets approximately 1/N of keys, distribution quality no worse than hashmod
2. Minimal migration: When N → N+1, exactly K/(N+1) keys need remapping, which is the theoretical optimum

This algorithm has been used internally at Google across multiple systems (including Spanner’s tablet routing), with large-scale production verification.

Summary

This migration from hashmod to Jump Consistent Hash can be summarized in one sentence:

Same O(1) performance, migration cost reduced from 100% to 1%.

For any metric routing system using hash % N for sharding that faces dynamic node scaling requirements, Jump Consistent Hash is a worthwhile upgrade path—zero-cost performance with huge operational benefits.

References

• stream-metrics-route Consistent Hash Evaluation Document
• Jump Consistent Hash Paper
• Original hashmod implementation
• Jump Consistent Hash implementation
• Previous: VictoriaMetrics Stream Aggregation Three-Year Review