Partitions and the Key Hash

After this lesson your program picks the same partition Kafka's default producer picks for a record key, bit for bit, and counts how a stream of keys spreads across the partitions of a topic.

Why a topic is split

One log has one writer-at-a-time bottleneck and lives on one machine. A topic is a name for a set of independent logs, its partitions, numbered 0 to n-1. Each partition has its own offsets, its own segments and can sit on a different broker. Readers in one consumer group take one partition each, so more partitions means more parallel readers.

The price is the ordering guarantee. Records in one partition are ordered by offset. Records in different partitions have no order relative to each other. Kafka's answer to "but I need all events for one customer in order" is the record key: the same key always goes to the same partition.

The default partitioner

For a record with a key, the producer computes:

partition = toPositive(murmur2(keyBytes)) mod numPartitions
toPositive(x) = x AND 0x7fffffff

Three details decide whether you match Kafka:

• The hash is over the bytes of the key, not characters. café is 5 bytes in UTF-8.
• murmur2 returns a signed 32-bit integer. toPositive clears the sign bit; it is not abs. For a negative hash the two give different partitions.
• The modulus is applied to the non-negative value, so in languages whose % keeps the sign of the left operand you must mask first.

murmur2, step by step

Pseudocode, not a language. All arithmetic is 32-bit and wraps around; shifts right are logical (zero-filling).

m = 0x5bd1e995
h = 0x9747b28c XOR length
for each complete group of 4 bytes, read as a little-endian number k:
    k = k * m;   k = k XOR (k >> 24);   k = k * m
    h = h * m;   h = h XOR k
leftover bytes (length mod 4):
    3 left: h = h XOR (byte[2] << 16)
    2 or 3: h = h XOR (byte[1] << 8)
    1, 2 or 3: h = h XOR byte[0];  h = h * m
h = h XOR (h >> 13);  h = h * m;  h = h XOR (h >> 15)

Worked trace for the 2-byte key ab (bytes 0x61 0x62), different from your exercise:

h = 0x9747b28c XOR 2          = 0x9747b28e
2 bytes left: h XOR (0x62<<8) = 0x9747d08e
              h XOR 0x61      = 0x9747d0ef
              h * m           = 0xf215221b
h XOR (h >> 13)               = 0xf212b2b2
h * m                         = 0x12d8039a
h XOR (h >> 15)               = 0x12d8262a   = 316155434

Check yourself against Kafka's own unit tests: the key 21 hashes to -973932308 and foobar to -790332482.

Null keys and empty keys

A record with no key (null) has nothing to hash. The classic behaviour is a round robin over the partitions: this exercise keeps one counter that starts at 0, and each null-keyed record takes counter mod n and bumps it. (Modern producers keep a "sticky" partition per batch to build bigger batches; the counter is the simpler cousin.) An empty key (zero bytes) is not null: it is hashed like any key, and murmur2 of nothing is 275646681.

Why the key mapping is fragile

sku-1042: hash 0xd8718699, toPositive = 1484031641
  6 partitions -> 1484031641 mod 6 = 5
  8 partitions -> 1484031641 mod 8 = 1

Adding partitions to a live topic moves keys to new partitions. Old records stay where they were, so per-key order is lost across the change. That is why partition counts are chosen with growth in mind. A single very popular key still lands on one partition no matter how many you add: a hot partition.

Common mistakes

• abs instead of masking. Wrong partition for roughly half of all keys.
• Hashing characters or a language's string hash. Only the UTF-8 bytes through murmur2 match Kafka.
• Treating an empty key as null. The empty key is hashed and always lands on the same partition.
• Signed shifts. An arithmetic right shift smears the sign bit and changes the hash; shifts here are logical.

Your exercise

The starter reads the input and prints the final distribution. Implement murmur2 and the partition choice. The most likely mistake is the final % n on a negative value.