Lab 03 — Code Review: CleverPartitioner

Phase: 05 — Code Quality and Engineering Discipline
Difficulty: ⭐⭐⭐⭐☆ | Estimated Time: 2.5–3 hours
Primary Artifact: CleverPartitioner.java — a Fibonacci-hashing partitioner with 5 correctness issues
Verify: mvn test shows exactly 2 passing + 2 failing tests; then fix the bugs until all 4 pass

Goal

A contributor submitted CleverPartitioner.java as a pull request to replace the existing modulo-based partitioner. The tests tell part of the story — but a good code review catches what the tests miss.

Your job is to:

  1. Run the tests and observe which pass and which fail
  2. Write a code review comment for each issue you find (5 total)
  3. Fix the correctness bugs so all 4 tests pass
  4. Assess whether the fix is sufficient for a real Apache PR to be merged

Background: Fibonacci Hashing

Fibonacci hashing maps a hash value to a bucket using the golden-ratio constant:

φ = (√5 - 1) / 2 ≈ 0.618

In integer arithmetic (64-bit), this is approximated by:

FIBONACCI_MULT = 2^64 × φ = 0x9e3779b97f4a7c15L

The algorithm: multiply the key's hash by FIBONACCI_MULT, then take the top k bits, where k = log₂(n) — this only works when n is a power of two.

The bug in this implementation: the code uses Integer.numberOfTrailingZeros(n) to compute k, which is correct only for powers of two. For n=1, numberOfTrailingZeros(1) = 0, so the shift is 64 - 0 = 64. In Java, shifting a long by 64 is equivalent to shifting by 0 (the shift amount is taken modulo 64), returning the full product instead of 0.

Setup

cd phase-05-code-quality/lab-03-review
mvn test

Expected output: 2 tests PASS, 2 tests FAIL.

Steps

Step 1 — Run the tests and understand the failures

mvn test 2>&1 | grep -E 'Tests run|FAIL|ERROR|expected|but was'

Record:

  • Which test fails?
  • What is the actual vs. expected value?
  • What does that tell you about the algorithm?

Step 2 — Read CleverPartitioner.java and write a review

Before touching any code, write a code review comment for each of the 5 issues marked in the source file. Use the Apache review severity labels:

BLOCKER  — must be fixed before merge
MAJOR    — important but non-blocking correctness issue
MINOR    — should be addressed
NIT      — trivial
QUESTION — asking for clarification

Your review should be in the form:

[BLOCKER] partition(String, int): If n is not a power of two (e.g., n=5),
the shift amount is Integer.numberOfTrailingZeros(5) = 0, so the expression
>>> 64 evaluates as >>> 0 (shift mod 64), returning an unmasked value far
outside [0, n). This is a correctness regression for any cluster with a
non-power-of-two partition count. Requires either: (a) restricting n to
powers of two with an explicit precondition check, or (b) replacing the
algorithm with one that handles arbitrary n.

Step 3 — Fix the correctness bugs

Fix in this order:

  1. Null guard: add a null check on key and throw IllegalArgumentException (not NullPointerException — explicit contract is better than an implicit crash)
  2. Non-positive n guard: throw IllegalArgumentException if n <= 0
  3. Power-of-two guard: throw IllegalArgumentException with a clear message if n is not a power of two — (n & (n - 1)) != 0 is the idiomatic check
  4. n=1 edge case: with the power-of-two guard in place, n=1 is now valid; ensure partition(key, 1) always returns 0 (all keys go to bucket 0 — there is only one bucket)
  5. Magic constant citation: add a Javadoc or inline comment explaining 0x9e3779b97f4a7c15L — this is the Knuth/Fibonacci multiplier and must be cited

Step 4 — Verify all 4 tests pass

mvn test

All 4 tests must pass:

  • testPowerOfTwo_distributionInRange — basic power-of-two bucketing
  • testSingleBucket_alwaysReturnsZero — n=1 must always return 0
  • testNonPowerOfTwo_throwsIllegalArgument — n=5 must throw IllegalArgumentException
  • testNullKey_throwsIllegalArgument — null key must throw IllegalArgumentException

Step 5 — Reassess: is the PR ready to merge?

After your fixes, answer in a comment at the top of CleverPartitioner.java:

  1. Is it still Fibonacci hashing if we restrict n to powers of two? (Yes — this is the standard form.)
  2. A Kafka partition count can be any positive integer, not just a power of two. What algorithm would you recommend as a replacement that handles arbitrary n? (Hint: Math.abs(key.hashCode()) % n is simple but has skew for non-prime n. What's the production alternative?)
  3. Is the 0x45d9f3bL constant on the hashCode mixing step necessary? What does it do?

Verification

# All 4 tests pass
mvn test
echo "Exit code: $?"  # must be 0

Source Files

pom.xml

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>org.example.quality</groupId>
    <artifactId>review-lab</artifactId>
    <version>1.0.0-SNAPSHOT</version>
    <packaging>jar</packaging>
    <name>Code Quality Lab 03 — Code Review</name>

    <properties>
        <maven.compiler.source>11</maven.compiler.source>
        <maven.compiler.target>11</maven.compiler.target>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter</artifactId>
            <version>5.10.2</version>
            <scope>test</scope>
        </dependency>
    </dependencies>

    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-surefire-plugin</artifactId>
                <version>3.2.5</version>
            </plugin>
        </plugins>
    </build>

</project>

CleverPartitioner.java

package org.example.quality;

/**
 * Partitioner using Fibonacci hashing to assign a string key to one of
 * {@code n} buckets.
 *
 * <p>
 * Fibonacci hashing exploits the golden-ratio constant to spread keys more
 * evenly
 * than a simple modulo, especially when hashes cluster around multiples of a
 * common factor.
 *
 * <p>
 * This implementation has 5 issues for code review. Find them all before
 * fixing.
 *
 * <p>
 * Algorithm (for a power-of-two n):
 * 
 * <pre>
 *   h = mix(key.hashCode())
 *   bucket = (int)((h * FIBONACCI_MULT) >>> (64 - log2(n)))
 * </pre>
 *
 * <p>
 * Where {@code FIBONACCI_MULT = 2^64 * (sqrt(5)-1)/2} — the 64-bit
 * Fibonacci/Knuth
 * multiplicative constant.
 *
 * @see <a href=
 *      "https://en.wikipedia.org/wiki/Hash_table#Fibonacci_hashing">Fibonacci
 *      hashing</a>
 */
public class CleverPartitioner {

    // ISSUE 1 — Magic constant with no citation
    // This is the 64-bit Fibonacci multiplicative constant (Knuth, vol 3, §6.4):
    // FIBONACCI_MULT = floor(2^64 * (sqrt(5) - 1) / 2) = 0x9e3779b97f4a7c15L
    // Without the comment (which was "// trust me" in the original PR), a reviewer
    // cannot verify this constant is correct without re-deriving it from scratch.
    // Severity: MAJOR — cite the source.
    private static final long FIBONACCI_MULT = 0x9e3779b97f4a7c15L;

    /**
     * Returns the bucket index for the given key in a cluster of {@code n}
     * partitions.
     *
     * @param key the key to partition (must not be null)
     * @param n   the number of partitions (must be a positive power of two)
     * @return a bucket index in the range {@code [0, n)}
     */
    public int partition(String key, int n) {
        // ISSUE 2 — No null check on 'key'
        // If key is null, key.hashCode() throws NullPointerException with no useful
        // message.
        // The contract should be explicit: IllegalArgumentException with "key must not
        // be null".
        // Severity: MAJOR — silent crash with an unhelpful stack trace.

        // ISSUE 3 — No validation that n > 0
        // If n == 0, the shift amount is 64 - numberOfTrailingZeros(0) = 64 - 32 = 32.
        // If n < 0, numberOfTrailingZeros returns a nonsensical result.
        // Severity: BLOCKER — undefined behavior for invalid inputs.

        // ISSUE 4 — Assumes n is a power of two; no guard
        // numberOfTrailingZeros(n) only gives log2(n) when n IS a power of two.
        // For n = 5: numberOfTrailingZeros(5) = 0, so the shift is (64 - 0) = 64.
        // In Java, (long) >>> 64 is equivalent to >>> 0 (shift mod 64) — the full
        // 64-bit product, truncated to int, which is not in [0, 5).
        // Severity: BLOCKER — wrong results for any non-power-of-two partition count.
        int shift = 64 - Integer.numberOfTrailingZeros(n);

        // ISSUE 5 — Magic mixing constant with no explanation
        // 0x45d9f3bL is a secondary mixing multiplier used to improve bit distribution
        // before the Fibonacci step. Without a comment, reviewers cannot verify this
        // is the correct constant or understand its purpose.
        // Severity: MINOR — code should be self-documenting.
        long h = (long) key.hashCode() * 0x45d9f3bL;

        return (int) ((h * FIBONACCI_MULT) >>> shift);
    }
}

PartitionerTest.java

package org.example.quality;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

/**
 * Tests for {@link CleverPartitioner}.
 *
 * Before fixes: 2 tests pass, 2 tests fail.
 * After fixes: all 4 tests pass.
 *
 * Run with: mvn test
 */
class PartitionerTest {

    private CleverPartitioner partitioner;

    @BeforeEach
    void setUp() {
        partitioner = new CleverPartitioner();
    }

    /**
     * Test 1 — PASSES before fixes.
     *
     * For a power-of-two n (n=8), every key must produce a bucket in [0, 8).
     * Fibonacci hashing is deterministic, so the same key always maps to the same
     * bucket.
     */
    @Test
    void testPowerOfTwo_distributionInRange() {
        int n = 8;
        String[] keys = { "key-0", "key-1", "key-2", "key-3", "alpha", "beta", "gamma", "delta" };
        for (String key : keys) {
            int bucket = partitioner.partition(key, n);
            assertTrue(bucket >= 0 && bucket < n,
                    "Expected bucket in [0, " + n + ") for key=" + key + " but got: " + bucket);
        }
    }

    /**
     * Test 2 — FAILS before fixes.
     *
     * n=1 means "there is only one bucket; everything goes to bucket 0".
     *
     * Bug: numberOfTrailingZeros(1) = 0, so shift = 64 - 0 = 64.
     * In Java, (long) >>> 64 is (long) >>> (64 % 64) = (long) >>> 0, which is the
     * full
     * 64-bit product cast to int — not 0.
     *
     * Fix required: treat n=1 as a special case (return 0 always), OR add a
     * power-of-two guard that catches n=1 and computes shift=0 explicitly using
     * Integer.numberOfLeadingZeros(n) - 1 or Integer.SIZE -
     * Integer.numberOfLeadingZeros(n-1).
     */
    @Test
    void testSingleBucket_alwaysReturnsZero() {
        String[] keys = { "any-key", "another-key", "yet-another" };
        for (String key : keys) {
            int bucket = partitioner.partition(key, 1);
            assertEquals(0, bucket, "With n=1 every key must map to bucket 0, but got: " + bucket);
        }
    }

    /**
     * Test 3 — FAILS before fixes.
     *
     * n=5 is not a power of two. The partitioner must reject it with
     * IllegalArgumentException rather than silently returning a wrong bucket.
     *
     * Bug: without a guard, the code silently returns values outside [0, 5).
     *
     * Fix required: add a precondition check before computing the shift.
     */
    @Test
    void testNonPowerOfTwo_throwsIllegalArgument() {
        assertThrows(IllegalArgumentException.class,
                () -> partitioner.partition("any-key", 5),
                "Expected IllegalArgumentException for non-power-of-two n=5");
    }

    /**
     * Test 4 — PASSES before fixes (an NPE is thrown, and the test expects it).
     *
     * BUT: NullPointerException is the wrong exception here. A method that accepts
     * user input should throw IllegalArgumentException with a clear message, not
     * an opaque NPE. This test is written to document the DESIRED behavior after
     * fix.
     *
     * Before fix: NullPointerException is thrown — test passes because NPE is a
     * subtype
     * of RuntimeException, which satisfies assertThrows(NullPointerException.class,
     * ...).
     *
     * After fix: IllegalArgumentException is thrown — the test must be updated to
     * expect
     * IllegalArgumentException, OR the test is already written correctly and
     * the implementation must throw IllegalArgumentException.
     *
     * The test below expects IllegalArgumentException. Before fixing, it FAILS.
     * After fixing, it PASSES.
     *
     * This is the review point: the test was written to catch the NPE (which
     * already
     * "works") but the right fix is IllegalArgumentException with a useful message.
     */
    @Test
    void testNullKey_throwsIllegalArgument() {
        assertThrows(IllegalArgumentException.class,
                () -> partitioner.partition(null, 4),
                "Expected IllegalArgumentException for null key, not NullPointerException");
    }
}