How Murmur3Partitioner Works with Virtual Nodes (vnodes) for Data Distribution in Apache Cassandra

Apache Cassandra uses the Murmur3Partitioner to convert partition keys into uniformly distributed 64-bit tokens, while virtual nodes (vnodes) divide the token ring into smaller ranges that are randomly assigned to physical nodes to ensure balanced data distribution and seamless scaling.

The Murmur3Partitioner is the default partitioning strategy in Apache Cassandra, implemented in src/java/org/apache/cassandra/dht/Murmur3Partitioner.java. It combines the Murmur3-128 hashing algorithm with virtual nodes to eliminate hot spots and enable elastic cluster expansion. This article examines the source code implementation to explain how tokens are generated, how vnodes divide the ring, and how data flows to replicas.

Token Generation with Murmur3Partitioner

Hashing Partition Keys into LongToken

When a write operation arrives, the Murmur3Partitioner computes a token by hashing the partition key using the Murmur3-128 algorithm. In src/java/org/apache/cassandra/dht/Murmur3Partitioner.java, the decorateKey() method handles this transformation:

// Murmur3Partitioner – token generation
public DecoratedKey decorateKey(ByteBuffer key) {
    long[] hash = getHash(key);                 // Murmur3 hash of the key
    return new PreHashedDecoratedKey(getToken(key, hash), key, hash[0], hash[1]);
}

The getToken() method extracts a signed 64-bit long from the hash, creating a LongToken that represents the partition's position on the ring. Because Murmur3 produces a uniform distribution across the full 2⁶⁴ range, each token occupies roughly equal portions of the logical ring, preventing data skew.

Virtual Nodes (vnodes) and Token Assignment

Configuring Vnodes with num_tokens

Virtual nodes allow each physical server to own multiple non-contiguous token ranges. You configure the number of vnodes per node using the num_tokens parameter in conf/cassandra.yaml. During bootstrap, Cassandra assigns this many random tokens to the joining node rather than a single large range.

TokenMetadata and Range Assignment

The TokenMetadata class (src/java/org/apache/cassandra/locmap/TokenMetadata.java) maintains the authoritative view of the cluster topology. It stores a sorted list of all tokens in sortedTokens and maps each token to its owning node via updateNormalTokens().

Each assigned token defines the start of a vnode range: (token, nextToken], wrapping around the ring. This means a node with 256 vnodes owns 256 distinct, randomly distributed slices of the token space rather than one continuous arc.

Calculating Token Ownership

To monitor distribution, the Murmur3Partitioner implements describeOwnership(), which calculates the fractional ownership of each token by measuring its distance to the next token on the ring. This method (lines 38-70 in Murmur3Partitioner.java) is used by nodetool status (src/java/org/apache/cassandra/tools/nodetool/Status.java) to report load percentages:

// Ownership calculation (simplified)
float age = new BigDecimal(ti.subtract(tim1).add(ri).mod(ri))
                .divide(r, 6, BigDecimal.ROUND_HALF_EVEN)
                .floatValue();   // % of the ring owned by token t

The algorithm computes each token's proportional responsibility, ensuring that the total token space is evenly divided among all vnodes in the cluster.

Data Distribution Flow

When a client writes data, the distribution process follows these steps:

1. Token Computation – The client or coordinator calls Murmur3Partitioner.getToken(partitionKey) to determine the target token.
2. Replica Selection – The AbstractReplicationStrategy (src/java/org/apache/cassandra/locmap/AbstractReplicationStrategy.java) walks the sortedTokens list to locate the primary vnode (the first token greater than or equal to the partition's token) and subsequent replicas.
3. Physical Distribution – Because each node owns many vnodes scattered randomly across the ring, the primary replica and its backups typically reside on different physical machines. This spreads load evenly and ensures that adding or removing a node only requires migrating the specific vnode ranges assigned to that machine.

Practical Code Examples

The following examples demonstrate how to work with the Murmur3Partitioner programmatically:

// Example: obtain the token for a partition key using Murmur3Partitioner
Murmur3Partitioner partitioner = Murmur3Partitioner.instance;
ByteBuffer key = ByteBufferUtil.bytes("myPartitionKey");
LongToken token = partitioner.getToken(key);
System.out.println("Token: " + token);

// Example: calculate ownership percentages for all tokens in a cluster
List<Token> allTokens = tokenMetadata.sortedTokens();   // from TokenMetadata
Map<Token, Float> ownership = partitioner.describeOwnership(allTokens);
ownership.forEach((t, pct) ->
    System.out.printf("Token %s owns %.2f%% of the ring%n", t, pct * 100));

These operations leverage the uniform distribution properties of Murmur3 to provide deterministic mapping from partition keys to physical storage locations.

Summary

• Murmur3Partitioner generates 64-bit tokens using the Murmur3-128 hash algorithm, ensuring uniform distribution across the token ring.
• Virtual nodes divide the ring into small, randomly assigned ranges per physical node, configured via num_tokens in cassandra.yaml.
• TokenMetadata maintains the sorted token list and assigns ownership ranges using updateNormalTokens().
• describeOwnership() calculates fractional ring ownership for monitoring and balancing operations.
• The combination of uniform hashing and random vnode assignment eliminates hot spots and simplifies cluster expansion by limiting data movement to specific token ranges.

Frequently Asked Questions

What is the difference between Murmur3Partitioner and RandomPartitioner?

Murmur3Partitioner uses the Murmur3-128 hash function to generate tokens, while RandomPartitioner uses MD5. Murmur3 is significantly faster computationally and provides better randomness properties. Murmur3Partitioner is the default in modern Cassandra versions and is recommended for all new clusters.

How many vnodes should I configure per node?

Most production deployments use between 128 and 256 vnodes per node (set via num_tokens in cassandra.yaml). Higher numbers improve distribution granularity and rebalance efficiency but increase metadata overhead. The optimal count depends on cluster size and data volume, though 256 is the most common starting point.

Does Murmur3Partitioner guarantee perfectly even data distribution?

While Murmur3Partitioner provides statistically uniform token distribution, actual data distribution depends on the specific partition keys being hashed. Extremely large partitions or uneven key distributions can still create hot spots. However, with sufficiently high num_tokens values and randomized vnode assignment, the variance between nodes typically remains within acceptable bounds.

How does changing the num_tokens setting affect existing data?

Changing num_tokens only affects nodes that join the cluster after the configuration change. Existing nodes retain their current token assignments until they are decommissioned or rebuilt. To change the vnode count on an existing node, you must perform a nodetool decommission followed by re-bootstrap with the new configuration, which triggers streaming of data to the new token ranges.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}