Lab SR1: Trace Document Routing to a Shard

Background

The masterclass concept chapter gave you the routing formula:

hash      = Murmur3HashFunction.hash(routing ?? _id)   // signed 32-bit
partition = floorMod(hash, number_of_routing_shards)
shardId   = partition / (number_of_routing_shards / number_of_shards)

In this lab you stop reading the formula and become it. You will write a tiny standalone Java program that replicates the exact murmur3 hash the cluster uses, compute a document's destination shard by hand, and then verify against a running OpenSearch node that the document really landed where your arithmetic said it would. When your shardId matches _cat/shards, you have proven you understand routing at the level of the integer — not the diagram.

Why this matters for contributors

Routing bugs are some of the nastiest in OpenSearch because they are silent: a document goes to the wrong shard and simply can't be found by _id, with no error. Anyone touching IndexRouting, OperationRouting, the resize path, or the in-place split RFC (#13925) must be able to compute the expected shard independently of the code under test — otherwise your test "passes" against your own bug. A standalone oracle that reproduces the hash is the contributor's ground truth.

Prerequisites

A single-node OpenSearch cluster reachable at localhost:9200 (./gradlew run from an OpenSearch checkout, or a tarball/Docker node).
A JDK (java/javac) on your PATH — the same major version the cluster uses is ideal but not required for the hash.
An OpenSearch source checkout to grep (for the real class names) and, ideally, its build output on the classpath so you can call the actual Murmur3HashFunction. We give both a dependency-free reimplementation and the real-class path.
You read the concept chapter — especially the floorMod and "partition is fixed for life" points.

Step 1 — Locate the real routing code

Never trust this page's class names; find them in your checkout.

# The hash function the write path uses.
grep -rn "class Murmur3HashFunction\|murmurhash3_x86_32\|public static int hash" \
  server/src/main/java/org/opensearch/cluster/routing/Murmur3HashFunction.java

# Where _routing-or-_id is chosen and scaled to a shard (write path).
grep -rn "calculateScaledShardId\|routingFactor\|getRoutingFactor\|floorMod\|partition" \
  server/src/main/java/org/opensearch/cluster/routing/IndexRouting.java \
  server/src/main/java/org/opensearch/cluster/routing/OperationRouting.java

# The defaults and accessors for the two numbers that matter.
grep -rn "getRoutingNumShards\|getRoutingFactor\|INDEX_NUMBER_OF_ROUTING_SHARDS\|INDEX_NUMBER_OF_SHARDS" \
  server/src/main/java/org/opensearch/cluster/metadata/IndexMetadata.java

Read Murmur3HashFunction.hash(String): it UTF-8-encodes the string and calls Lucene's StringHelper.murmurhash3_x86_32(bytes, 0, len, seed) with a fixed seed (historically 0). Confirm the seed in your checkout:

grep -rn "murmurhash3_x86_32\|0x9747b28c\|seed" \
  server/src/main/java/org/opensearch/cluster/routing/Murmur3HashFunction.java

Note: OpenSearch's Murmur3HashFunction returns a signed int. It is the same murmur3 used to hash terms in Lucene, but applied to the routing string. Do not confuse it with the _uid/_id Lucene term hash; routing uses this one.

Step 2 — A standalone murmur3 oracle (dependency-free)

This reimplements MurmurHash3 x86 32-bit so you can compute the shard with nothing but a JDK. It is byte-for-byte the algorithm StringHelper.murmurhash3_x86_32 runs with seed 0. Save as RouteOracle.java:

import java.nio.charset.StandardCharsets;

public class RouteOracle {

    // MurmurHash3 x86 32-bit, seed 0 — matches Lucene StringHelper.murmurhash3_x86_32.
    static int murmur3(byte[] data, int offset, int len, int seed) {
        final int c1 = 0xcc9e2d51, c2 = 0x1b873593;
        int h1 = seed;
        int roundedEnd = offset + (len & 0xfffffffc); // round down to 4-byte blocks
        for (int i = offset; i < roundedEnd; i += 4) {
            int k1 = (data[i] & 0xff)
                   | ((data[i + 1] & 0xff) << 8)
                   | ((data[i + 2] & 0xff) << 16)
                   | (data[i + 3] << 24);
            k1 *= c1; k1 = Integer.rotateLeft(k1, 15); k1 *= c2;
            h1 ^= k1; h1 = Integer.rotateLeft(h1, 13); h1 = h1 * 5 + 0xe6546b64;
        }
        int k1 = 0;
        switch (len & 0x03) {              // tail
            case 3: k1 = (data[roundedEnd + 2] & 0xff) << 16;  // fallthrough
            case 2: k1 |= (data[roundedEnd + 1] & 0xff) << 8;  // fallthrough
            case 1: k1 |= (data[roundedEnd] & 0xff);
                    k1 *= c1; k1 = Integer.rotateLeft(k1, 15); k1 *= c2; h1 ^= k1;
        }
        h1 ^= len;                          // finalization
        h1 ^= h1 >>> 16; h1 *= 0x85ebca6b;
        h1 ^= h1 >>> 13; h1 *= 0xc2b2ae35;
        h1 ^= h1 >>> 16;
        return h1;
    }

    static int hash(String routing) {
        byte[] b = routing.getBytes(StandardCharsets.UTF_8);
        return murmur3(b, 0, b.length, 0);
    }

    public static void main(String[] args) {
        int numShards         = Integer.parseInt(args[0]);
        int numRoutingShards  = Integer.parseInt(args[1]);
        int routingFactor     = numRoutingShards / numShards;
        for (int i = 2; i < args.length; i++) {
            String routing = args[i];
            int h         = hash(routing);
            int partition = Math.floorMod(h, numRoutingShards);
            int shardId   = partition / routingFactor;
            System.out.printf(
                "routing=%-12s hash=%11d partition=%4d shard=%d%n",
                routing, h, partition, shardId);
        }
    }
}

Compile and run it for the canonical layout (N=8, R=1024) on a handful of ids:

javac RouteOracle.java
java RouteOracle 8 1024 user-42 user-43 tenant-7 order-1001 abc

Expected shape of the output (your hashes are deterministic — these are the real murmur3 seed-0 values, so you should get exactly these):

routing=user-42      hash=  ... partition= ... shard=?
routing=tenant-7     hash=  ... partition= ... shard=?
...

Note: The numbers are fully determined by the algorithm above; two correct implementations must agree. If your output differs from the cluster's (Step 5), your murmur3 has a bug — most often a sign error in the tail bytes or a missing & 0xff. Compare against the real class in Step 3.

Step 3 — (Optional but recommended) call the real class

To remove all doubt, call OpenSearch's own Murmur3HashFunction instead of your reimplementation. Build the server jar and put it on the classpath:

# From an OpenSearch checkout — produces server classes you can reference.
./gradlew :server:compileJava -q

# Find the compiled classes / jar.
SERVER_CP=$(find . -path '*server*build*classes/java/main' -type d | head -1)
LUCENE_JAR=$(find ~ -name 'lucene-core-*.jar' 2>/dev/null | head -1)

cat > RealRoute.java <<'JAVA'
import org.opensearch.cluster.routing.Murmur3HashFunction;
public class RealRoute {
  public static void main(String[] a) {
    int N = Integer.parseInt(a[0]), R = Integer.parseInt(a[1]), f = R / N;
    for (int i = 2; i < a.length; i++) {
      int h = Murmur3HashFunction.hash(a[i]);
      int p = Math.floorMod(h, R);
      System.out.printf("routing=%s hash=%d partition=%d shard=%d%n", a[i], h, p, p / f);
    }
  }
}
JAVA

javac -cp "$SERVER_CP:$LUCENE_JAR" RealRoute.java
java   -cp ".:$SERVER_CP:$LUCENE_JAR" RealRoute 8 1024 user-42 tenant-7 order-1001

The hash column here must equal your RouteOracle output. If it doesn't, fix RouteOracle until it does — that's the point of having both.

Step 4 — Create an index with a known routing geometry

Now stand up the index your oracle assumed. Pin both numbers explicitly so the math is fully determined.

curl -s -XPUT 'localhost:9200/route-lab' \
  -H 'Content-Type: application/json' -d '{
    "settings": {
      "index.number_of_shards": 8,
      "index.number_of_routing_shards": 1024,
      "index.number_of_replicas": 0
    }
  }' | jq .

# Confirm the geometry the cluster will actually use.
curl -s 'localhost:9200/route-lab/_settings?pretty' \
  | jq '.["route-lab"].settings.index | {number_of_shards, number_of_routing_shards}'

Warning: If you omit number_of_routing_shards, OpenSearch picks a default based on number_of_shards (grep getRoutingNumShards). Your oracle must then be fed the actual value from _settings, not 1024, or your shard prediction will be wrong.

Step 5 — Index the documents and read where they actually landed

Index each id, then ask the cluster which shard holds it. The cleanest way to see the real shard for a single document is the _search_shards API with the same routing value the doc used — it returns the exact shard(s) a routed request maps to:

for id in user-42 user-43 tenant-7 order-1001 abc; do
  curl -s -XPUT "localhost:9200/route-lab/_doc/$id" \
    -H 'Content-Type: application/json' -d "{\"id\":\"$id\"}" >/dev/null
done
curl -s 'localhost:9200/route-lab/_refresh' >/dev/null

# The shard a given _id maps to (routing defaults to _id):
for id in user-42 user-43 tenant-7 order-1001 abc; do
  shard=$(curl -s "localhost:9200/route-lab/_search_shards?routing=$id" \
            | jq -r '.shards[0][0].shard')
  echo "id=$id -> shard $shard"
done

Cross-check the physical distribution and that all 8 shards exist:

curl -s 'localhost:9200/_cat/shards/route-lab?v&h=index,shard,prirep,docs,node'

You can also confirm a single doc's shard by issuing a routed search and reading the _shard in the hit metadata:

curl -s 'localhost:9200/route-lab/_search?routing=user-42&pretty' \
  -H 'Content-Type: application/json' \
  -d '{"explain": true, "query": {"ids": {"values": ["user-42"]}}}' \
  | jq '.hits.hits[0]._shard, .hits.hits[0]._explanation.description' 2>/dev/null

Step 6 — Reconcile oracle vs cluster

Put the two side by side. For each id, your RouteOracle 8 1024 <id> shard= value must equal the _search_shards shard.

echo "id        oracle  cluster"
for id in user-42 user-43 tenant-7 order-1001 abc; do
  o=$(java RouteOracle 8 1024 "$id" | awk '{print $4}' | cut -d= -f2)
  c=$(curl -s "localhost:9200/route-lab/_search_shards?routing=$id" | jq -r '.shards[0][0].shard')
  printf "%-9s %-6s %-6s %s\n" "$id" "$o" "$c" "$([ "$o" = "$c" ] && echo OK || echo MISMATCH)"
done

Every row should print OK. A MISMATCH means one of: (a) the index's real number_of_routing_shards isn't 1024 (re-read _settings), (b) your murmur3 has a tail/sign bug (compare to RealRoute from Step 3), or (c) you forgot floorMod and got a negative partition.

Deliverables

RouteOracle.java compiling and printing hash/partition/shard for any id.
A table of 5+ ids showing oracle shard == cluster shard for every one.
(Stretch) RealRoute.java against the actual Murmur3HashFunction, agreeing with RouteOracle on every hash.
A one-paragraph note: what the partition of user-42 is, and what shard it would move to if you split this index 8 → 16 (recompute with java RouteOracle 16 1024 user-42 — same partition, new shard).

Troubleshooting

Symptom	Cause	Fix
Oracle shard ≠ cluster shard	Index's real `number_of_routing_shards` ≠ what you passed the oracle	Read `_settings`, pass the real value
Negative partition / `ArrayIndexOutOfBounds` feel	Used `%` not `Math.floorMod` on the signed hash	Use `Math.floorMod(hash, R)`
`RealRoute` won't compile	Wrong classpath / Lucene jar not found	Re-run the `find` for `lucene-core-*.jar`; ensure `:server:compileJava` ran
`_search_shards` returns multiple shards	`routing_partition_size` is set on the index	Recreate without it (that's Lab SR3's territory)
All docs land on one shard	You used the same custom `_routing` for all	Drop `?routing=` on index so `_id` is the routing value

Expected output

_cat/shards shows 8 primaries spread across the (single) node, each with a small nonzero docs count, and the reconciliation table is all OK. If you split to 16 in the stretch and re-run RouteOracle 16 1024, each id's partition is unchanged but its shard is partition / 64.

Stretch goals

Avalanche check. Hash user-1..user-10000, bucket by shard, and confirm the distribution is near-uniform (within a few percent across 8 shards). This is the "uniform" property from the concept chapter, measured.
Split invariance, proven. For 50 ids, print partition for N=8 and N=16 from the oracle and assert the partition column is identical — only the shard column changes. This is the keystone invariant in code.
Custom routing preview. Run java RouteOracle 8 1024 tenant-7 tenant-7 tenant-7 and observe all three land on the same shard — the co-location you'll exploit in Lab SR3.

Coding Exercises

You built an oracle that predicts a shard; these exercises turn that oracle into a graded test suite and connect it to the real classes. Locate every class with rg/find first — never trust a class name or line number from this page.

(warm-up) A cross-check unit test for your oracle. Write a JUnit/OpenSearchTestCase test that calls the real Murmur3HashFunction.hash(String) and your RouteOracle.murmur3 for 1,000 random strings and assertEquals on every hash. Find the real class and its seed:
```
rg -n "class Murmur3HashFunction|murmurhash3_x86_32|hash\(String" \
  server/src/main/java/org/opensearch/cluster/routing/Murmur3HashFunction.java
```
A single mismatch means your tail/sign handling is wrong — the test pins it forever.
(core) Assert the partition invariant in code. Write a test that, for 200 random ids, computes partition = floorMod(hash, R) at R=1024 and asserts it is identical across N ∈ {8,16,32} while shardId = partition / (R/N) changes. This is the keystone "split invariance" property — encode it so a refactor of the shard math can't silently break it. Cross-reference where the cluster computes it:
```
rg -n "calculateScaledShardId|routingFactor|getRoutingFactor|floorMod" \
  server/src/main/java/org/opensearch/cluster/routing/IndexRouting.java
```
(core) A uniformity (avalanche) test. Promote Stretch Goal 1 into an asserting test: hash user-1..user-100000, bucket by shard at N=8, and assertTrue every shard's share is within, say, 5% of 1/8. This is the "near-uniform distribution" claim from the concept chapter, made a regression gate — if someone swaps the hash for a weaker one, the test fails.
(advanced) Drive the real routing path in an OpenSearchTestCase. Find IndexRouting/OperationRouting's entry point that maps a doc to a shard and call it directly (no HTTP):
```
rg -n "class IndexRouting|indexShard\(|getShard\(|public int|effectiveRouting" \
  server/src/main/java/org/opensearch/cluster/routing/IndexRouting.java
rg -ln "extends OpenSearchTestCase" server/src/test/java/org/opensearch/cluster/routing/
```
Build an IndexMetadata with number_of_shards=8, number_of_routing_shards=1024, call the real IndexRouting for your five ids, and assertEquals the shard against RouteOracle. Now your oracle is validated against the production code path, not a reimplementation — exactly the ground truth a routing-bug PR needs.
(Advanced challenge) A property-based routing oracle + cluster differential test. Write an OpenSearchIntegTestCase that: (a) creates route-lab with pinned geometry, (b) for 500 random ids, indexes each and queries _search_shards?routing=<id> (via client().admin()...) to get the cluster's shard, (c) asserts it equals IndexRouting's shard and RouteOracle's shard — a three-way agreement: standalone oracle ≡ real class ≡ live cluster. Then add a custom-_routing variant (foreshadowing Lab SR3) asserting all docs sharing a routing value land on one shard. Find the integ-test and shard-iterator plumbing:
```
rg -ln "extends OpenSearchIntegTestCase" server/src/test/java/org/opensearch/cluster/routing/
rg -n "ClusterSearchShardsRequest|searchShards|GroupShardsIterator" \
  server/src/main/java/org/opensearch/cluster/routing/OperationRouting.java
```
This is the contributor's anti-bug harness: a test that catches a wrong-shard regression no matter which of the three layers introduced it.

Issues to Practice On

Routing bugs are silent (a doc lands on the wrong shard, found by no one), so the tracker prizes anyone who can compute the expected shard independently — your oracle.

What to look for	`gh` command (labels move; confirm on the tracker)
Routing / shard-mapping issues	`gh issue list --repo opensearch-project/OpenSearch --label "ShardManagement:Routing" --state open`
Shard placement / allocation	`gh issue list --repo opensearch-project/OpenSearch --label "ShardManagement:Placement" --state open`
Cluster-manager / coordination	`gh issue list --repo opensearch-project/OpenSearch --label "Cluster Manager" --state open`
Bugs	`gh issue list --repo opensearch-project/OpenSearch --label "bug" --state open`
Newcomer-friendly	`gh issue list --repo opensearch-project/OpenSearch --label "good first issue" --state open`

The ShardManagement:* family is the routing/placement home; list labels first with gh label list --repo opensearch-project/OpenSearch since taxonomies drift. The in-place split routing RFC (#13925) is the live design surface this lab feeds — read it and its linked issues.

Representative patterns. (a) "Document not found by _id after operation X" — a classic silent-routing bug: reproduce with a known id, compute the expected shard with your oracle, then rg IndexRouting/OperationRouting to find where the actual mapping diverges; fix and add a test asserting the doc's shard. (b) "Routing math breaks when number_of_routing_shards is non-default" — reproduce across geometries, locate getRoutingNumShards/getRoutingFactor in IndexMetadata, fix, and add a parameterized test over several (N,R) pairs.

Planted-bug drill. Find the floor-mod in the routing path:

rg -n "floorMod|% .*RoutingShards|Math\\.abs|partition" \
  server/src/main/java/org/opensearch/cluster/routing/IndexRouting.java

Change Math.floorMod(hash, R) to a bare hash % R (reintroducing the negative-shard bug for ids whose hash is negative). Run the routing tests (rg -l "Murmur3|IndexRoutingTests|RoutingTests" server/src/test) and watch which assertion goes red for a negative-hash id. Revert, then add an assertion that pins a known-negative-hash id to its correct nonnegative shard — the exact edge the bug slips through.

Etiquette: claim the issue before working it, reproduce first; every PR needs a test + a CHANGELOG.md entry + DCO Signed-off-by (git commit -s). See community-interaction.

Validation: self-check

Why does the formula use Math.floorMod instead of %? Give a concrete id from your run whose raw hash % 1024 would have been negative.
State user-42's partition and the shard it occupies at N=8, N=16, and N=32. Which number stayed constant, and why is that the property that makes split possible?
Your oracle and the cluster agree. Name the two inputs that, if mismatched, would make them disagree — and where you read the cluster's true value for each.
What does _search_shards?routing=user-42 return, and how is it different from actually running the search?

Open-Source Engineer & Contributor