Gists

A synced, readable copy of my gists from gist.github.com/bl9. Each page is the gist content pasted verbatim; the table links to the local page and to the original gist.

21 gists, newest first. Last synced 2026-08-07.

🔒 = secret gist (unlisted on GitHub).

Two additional gists (codes, gistfile1.txt) hold private recovery phrases and are intentionally kept out of this published section.

Source: opensearch_knn_filter_pushdown · opensearch_knn_filter_pushdown.md · updated 2026-08-07 · 🔒 secret gist

Synced verbatim from gist.github.com/bl9.

Common Filter Push-Down in OpenSearch — RFC, Design, and the k-NN filter() Implementation

Deep dive on:

• RFC: neural-search#1135 — Common Filter Support for Hybrid Query Sub-Queries
• Implementation: k-NN#2599 — Add filter function to KNNQueryBuilder
• Prerequisite: OpenSearch#17409 — Add filter function for AbstractQueryBuilder, BoolQueryBuilder, ConstantScoreQueryBuilder
• Consumer: neural-search#1206 — Add filter function for NeuralQueryBuilder and HybridQueryBuilder

Shipped in OpenSearch 3.0.

Table of Contents

1. TL;DR
2. Background concepts you need first
   • 2.1 The OpenSearch query lifecycle
   • 2.2 QueryBuilder vs Lucene Query
   • 2.3 Hybrid search and why it exists
   • 2.4 Filtering in vector search: pre, post, and efficient
   • 2.5 Why "tail relevant results" get dropped
3. The RFC (neural-search#1135)
   • 3.1 Problem statement
   • 3.2 Scope and non-goals
   • 3.3 High-level design: two options
   • 3.4 Low-level design: three options
   • 3.5 Per-query-type push-down semantics
   • 3.6 The FilterCombinationMode that didn't ship
   • 3.7 Score filters are blocked
4. Architecture: three repos, one contract
   • 4.1 The contract in core
   • 4.2 Core implementations
   • 4.3 Plugin implementations
   • 4.4 Why the plugins duplicate instead of share
5. k-NN PR #2599, line by line
   • 5.1 Files changed
   • 5.2 CHANGELOG.md
   • 5.3 KNNQueryBuilder.filter() — the 40 lines
   • 5.4 The unit test
   • 5.5 The integration test
   • 5.6 The review debate: mutate or rebuild?
6. End-to-end request trace
7. Semantics, edge cases, and real bugs
8. Build it yourself
   • 8.1 Dev environment
   • 8.2 Implementing the change from scratch
   • 8.3 The same feature for a query type that doesn't have it
9. Testing
   • 9.1 Unit tests
   • 9.2 Integration tests
   • 9.3 Manual REST testing on a live cluster
   • 9.4 Verifying push-down actually happened
10. Limitations and follow-ups
11. Reference index

1. TL;DR

• User-facing feature: hybrid query gets a top-level filter field. One filter, applied to every sub-query.
• Mechanism: a new method QueryBuilder#filter(QueryBuilder) on the core query-builder interface. It means "combine this filter into me and give me back the resulting builder."
• Default behaviour: AbstractQueryBuilder wraps this in a bool { must: this, filter: <f> }. Query types that natively understand filters override it to do something smarter.
• k-NN's job (PR #2599): override filter() on KNNQueryBuilder so the filter lands inside the k-NN query rather than around it. That's the whole point — a filter inside a k-NN query participates in ANN traversal; a filter outside it is post-filtering and silently destroys recall.
• Size: 40 lines of production code, 105 lines of tests, 1 CHANGELOG line. The design work is 95% of the value.

2. Background concepts you need first

2.1 The OpenSearch query lifecycle

A _search request goes through roughly this pipeline:

1. Route — REST layer resolves the handler, request lands on a coordinating node.
2. Parse — the JSON query DSL is parsed into a tree of QueryBuilder objects (fromXContent).
3. Search request processors — if a search pipeline defines any, they mutate the SearchRequest here.
4. Rewrite — QueryBuilder#rewrite() runs, possibly several rounds, possibly async (this is where terms lookups, neural → knn model inference, etc. resolve).
5. Serialize + fan out — the rewritten builder tree is written to StreamOutput and shipped to every data node holding a shard.
6. toQuery() — on each shard, QueryBuilder#toQuery(QueryShardContext) produces a Lucene Query.
7. Execute — Lucene collects hits per segment.
8. Post-process — search phase results processors (e.g. normalization/combination for hybrid), then response.

Steps 2 and 3 are the only two places where you can still restructure the query as a builder. That matters enormously, and is exactly the argument the RFC makes.

2.2 QueryBuilder vs Lucene Query

Two different objects, often confused:

KNNQueryBuilder holds a QueryBuilder filter field. At toQuery() time that filter is handed to KNNQueryFactory, which converts it to a Lucene Query, runs it to get a filtered doc-ID bitset, and feeds that bitset into the ANN search. The filter must be inside the builder before toQuery() runs, or the engine never sees it.

2.3 Hybrid search and why it exists

hybrid (from the neural-search plugin) runs N sub-queries in parallel over the same shards, keeps their score lists separate, then a search-phase processor normalizes each list (min-max, L2, z-score) and combines them (arithmetic/geometric/harmonic mean, RRF). This is how you fuse BM25 lexical relevance with dense-vector semantic relevance without one score scale swamping the other.

Canonical shape:

{
  "hybrid": {
    "queries": [
      { "match":   { "text": "wireless earbuds" } },
      { "neural":  { "embedding": { "query_text": "wireless earbuds", "model_id": "abc", "k": 50 } } }
    ]
  }
}

Because sub-queries are independent, a filter has to be applied to each of them independently.

2.4 Filtering in vector search: pre, post, and efficient

Three strategies, with very different cost/recall profiles:

• Pre-filtering (scoring script / exact): compute the filtered doc set first, then brute-force distance over exactly those docs. Perfect recall, O(P) distance computations. Great when P is tiny, terrible when P is large.
• Post-filtering (bool filter or post_filter): run ANN over the whole graph, get k results, then drop the ones that fail the filter. Cheap, but if the filter is at all restrictive you get back far fewer than k results — sometimes zero.
• Efficient / "during-search" filtering: hand the filter's doc-ID bitset to the ANN algorithm so it only accepts in-filter candidates while traversing. This is what knn.filter does.

Engine support, per the k-NN docs: efficient k-NN filtering applies filtering during the vector search, which ensures k results are returned if at least k results exist in total; it is supported by the Lucene engine with HNSW (OpenSearch 2.4+) and the Faiss engine with HNSW (2.9+) or IVF (2.10+). From OpenSearch 3.1, Faiss + HNSW additionally uses the Lucene ACORN filtering optimization during graph traversal when memory-optimized search is enabled.

Both engines adaptively pick a strategy. The algorithm weighs N (docs in the index), P (docs surviving the filter), k, R (results returned by filtered ANN), FT (the knn.advanced.filtered_exact_search_threshold index setting), and MDC (max distance computations allowed in exact search when FT is unset). Practically: if the filtered doc-ID list is at or below k, it does exact search, because returning k neighbors requires at least k distance computations anyway.

2.5 Why "tail relevant results" get dropped

This phrase appears throughout the RFC. Concretely:

• Index has 1M docs. Filter category = "medical" matches 2,000 of them.
• Filter outside (bool { must: knn(k=10), filter: category=medical }): ANN returns the global top 10 by vector distance. If none of those 10 are medical, you get 0 results. If 2 are, you get 2.
• Filter inside (knn { ..., filter: category=medical }): the engine restricts traversal (or switches to exact search over the 2,000) and returns the top 10 medical docs. You get 10.

The "tail" is the relevant-but-not-globally-top documents. Post-filtering throws them away before you ever see them. This is the single technical reason the RFC rejected the simpler designs.

3. The RFC (neural-search#1135)

Authored by bzhangam, opened 22 Jan 2025, labelled v3.0.0, now closed/implemented.

3.1 Problem statement

To apply one filter across a hybrid query today, you repeat it in every sub-query. The neural/knn sub-queries take a filter field; the rest need wrapping in a bool. Verbose, error-prone, and the wrapping form is semantically different from the inline form.

Before:

{
  "hybrid": {
    "queries": [
      { "neural": { "embedding": { "query_text": "...", "model_id": "m1", "k": 50,
                                   "filter": { "term": { "status": "active" } } } } },
      { "bool": { "must": [ { "match": { "title": "..." } } ],
                  "filter": [ { "term": { "status": "active" } } ] } },
      { "bool": { "must": [ { "match": { "body": "..." } } ],
                  "filter": [ { "term": { "status": "active" } } ] } }
    ]
  }
}

After:

{
  "hybrid": {
    "queries": [
      { "neural": { "embedding": { "query_text": "...", "model_id": "m1", "k": 50 } } },
      { "match": { "title": "..." } },
      { "match": { "body": "..." } }
    ],
    "filter": { "term": { "status": "active" } }
  }
}

3.2 Scope and non-goals

Explicitly out of scope in v1:

• Metrics — no per-feature metric API; deferred to a separate project.
• Configurability — one filter, AND-combined, always. No per-sub-query opt-out.
• No change to filter semantics — push-down only relocates the filter; how neural/knn/bool each interpret a filter is untouched.
• No recursive push-down — the filter reaches the top-level sub-query and stops. It does not descend into a sub-query's own inner queries. Deliberate: keeps the transform predictable and cheap.

3.3 High-level design: two options

Option 1 (chosen): push down during parsing. Add a filter field to the hybrid query; apply the push-down in HybridQueryBuilder.fromXContent.

Option 2 (deferred): a new SearchRequestProcessor. Model it on core's FilterQueryRequestProcessor, register it in the search pipeline alongside the normalization processor.

The deciding constraint: KNNQueryBuilder optimizes its filter before Lucene Query conversion, so push-down must happen at step 2 or 3 of the lifecycle. Both options satisfy that; Option 1 is cheaper and friendlier.

3.4 Low-level design: three options

Option 1 (chosen): copy the filter into sub-queries when the type supports it. Types that natively hold a filter (neural, knn, bool, constant_score, hybrid) get special handling; everything else gets bool-wrapped.

Option 2: always bool-wrap. Trivial to implement, but for neural/knn it degrades to post-filtering and loses the tail. Rejected.

Option 3: use the existing post_filter. Zero effort, but it runs after hybrid normalization and combination, and it is post-filtering by definition. Rejected.

3.5 Per-query-type push-down semantics

Worked example — bool sub-query:

// input
{ "hybrid": {
    "queries": [
      { "bool": { "must": [ <q1> ], "filter": [ <f1> ] } },
      <q2>
    ],
    "filter": <F> } }

// after parsing
{ "hybrid": {
    "queries": [
      { "bool": { "must": [ <q1> ], "filter": [ <f1>, <F> ] } },
      { "bool": { "must": [ <q2> ], "filter": [ <F> ] } }
    ] } }

Worked example — constant_score wrapping a neural:

// input
{ "hybrid": {
    "queries": [
      { "constant_score": { "filter": { "neural": { ... } }, "boost": 1.2 } },
      <q1>
    ],
    "filter": <F> } }

// after parsing — F goes INSIDE the neural query, not around the constant_score
{ "hybrid": {
    "queries": [
      { "constant_score": { "filter": { "neural": { ..., "filter": <F> } }, "boost": 1.2 } },
      { "bool": { "must": [ <q1> ], "filter": [ <F> ] } }
    ] } }

3.6 The FilterCombinationMode that didn't ship

The RFC proposed a two-argument signature:

public QueryBuilder filter(QueryBuilder filter, FilterCombinationMode mode);

public enum FilterCombinationMode {
    AND,               // v1: the only mode
    IGNORE_IF_EXISTS,  // future: skip if the sub-query already has a filter
    OR                 // future
}

What actually merged in core is the one-argument form, AND hard-coded. Reasonable call — the enum was speculative, and adding a parameter later is an additive change. Worth knowing if you read the RFC and then the code and wonder where the mode went.

3.7 Score filters are blocked

Hybrid normalizes scores after sub-queries run. A user writing a score-based filter at the hybrid level would reasonably expect it to apply to normalized scores — but push-down applies it pre-normalization, per sub-query, on raw scores. The numbers would be meaningless. The RFC's answer: reject score-based filters at parse time rather than document a footgun.

4. Architecture: three repos, one contract

┌─────────────────────────────────────────────────────────────┐
│ OpenSearch core  (PR #17409)                                │
│                                                             │
│   interface QueryBuilder                                    │
│       QueryBuilder filter(QueryBuilder filter);   ← contract│
│                                                             │
│   AbstractQueryBuilder      → bool{must:this, filter:f}     │
│   BoolQueryBuilder          → filterClauses.add(f)          │
│   ConstantScoreQueryBuilder → recurse into wrapped filter   │
└───────────────┬─────────────────────────┬───────────────────┘
                │ extends                 │ extends
    ┌───────────▼──────────┐   ┌──────────▼──────────────────┐
    │ k-NN  (PR #2599)     │   │ neural-search (PR #1206)    │
    │  KNNQueryBuilder     │   │  NeuralQueryBuilder         │
    │    → rebuild with    │   │    → set/merge queryfilter  │
    │      merged filter   │   │  HybridQueryBuilder         │
    └──────────────────────┘   │    → fan out to sub-queries │
                               └─────────────────────────────┘

Merge order was forced: core (3 Mar 2025) → k-NN (14 Mar 2025) → neural-search. neural-search's HybridQueryBuilder.filter() calls query.filter(f) polymorphically, so KNNQueryBuilder must already implement it or you get the base-class bool wrapping and the whole point is lost.

4.1 The contract in core

server/src/main/java/org/opensearch/index/query/QueryBuilder.java:

QueryBuilder filter(QueryBuilder filter);

Documented semantics: combine the filter with this builder. If the builder already carries a filter, merge and return the builder itself. Otherwise use a bool query to combine builder and filter, and return the bool. A null filter is a no-op.

Note this is an interface method with no default — every implementor must supply one. That's why AbstractQueryBuilder provides the fallback: all ~60 core query types extend it, so they all inherit sane behaviour for free.

4.2 Core implementations

AbstractQueryBuilder — the universal fallback:

public static boolean validateFilterParams(QueryBuilder filter) {
    return filter != null;
}

public QueryBuilder filter(QueryBuilder filter) {
    if (validateFilterParams(filter) == false) {
        return this;
    }
    final BoolQueryBuilder modifiedQB = new BoolQueryBuilder();
    modifiedQB.must(this);
    modifiedQB.filter(filter);
    return modifiedQB;
}

validateFilterParams is public static on purpose: plugin code in other JARs calls it. It is the shared null-guard for every implementation across all three repos.

BoolQueryBuilder — no wrapper needed:

public BoolQueryBuilder filter(QueryBuilder filter) {
    if (validateFilterParams(filter) == false) {
        return this;
    }
    filterClauses.add(filter);
    return this;
}

This is a pre-existing method, not a new one — BoolQueryBuilder.filter(QueryBuilder) has always meant "add a filter clause." PR #17409 only added the null-guard so the same method could satisfy the new interface contract. The signature covariance (BoolQueryBuilder return type) is legal and keeps the existing fluent API source-compatible. Nice bit of API design: zero breakage, new semantics for free.

ConstantScoreQueryBuilder — recurse:

public ConstantScoreQueryBuilder filter(QueryBuilder filter) {
    if (validateFilterParams(filter) == false) {
        return this;
    }
    QueryBuilder filteredFilterBuilder = filterBuilder.filter(filter);
    if (filteredFilterBuilder != filterBuilder) {
        return new ConstantScoreQueryBuilder(filteredFilterBuilder);
    }
    return this;
}

The != identity check is the interesting line: if the inner builder mutated itself in place (bool, neural), return this and allocate nothing; if it returned a different object (knn, or a bool-wrapped leaf), rebuild the wrapper around the new object. This "returns-self-or-new" convention runs through the entire feature.

4.3 Plugin implementations

HybridQueryBuilder (neural-search) — the fan-out:

public QueryBuilder filter(QueryBuilder filter) {
    if (validateFilterParams(filter) == false) {
        return this;
    }
    ListIterator<QueryBuilder> iterator = queries.listIterator();
    while (iterator.hasNext()) {
        QueryBuilder query = iterator.next();
        // set the query again because query.filter(filter) can return new query.
        iterator.set(query.filter(filter));
    }
    return this;
}

The ListIterator.set() is required, not stylistic. query.filter(f) may return a different object; a plain for-each would compute the new builder and throw it away.

And in fromXContent, the parse-time application:

} else if (FILTER_FIELD.match(currentFieldName, parser.getDeprecationHandler())) {
    filter = parseInnerQueryBuilder(parser);
}
...
for (QueryBuilder query : queries) {
    if (filter == null) {
        compoundQueryBuilder.add(query);
    } else {
        compoundQueryBuilder.add(query.filter(filter));
    }
    ...
}

Two details worth noting in current main:

• filter is only accepted as a START_OBJECT. An array ("filter": [...]) or a scalar hits throwUnsupportedFilterParsingException → "[hybrid] query's [filter] field must be a query object". To combine several filters, wrap them in a bool yourself.
• Usage is instrumented: EventStatsManager.increment(EventStatName.HYBRID_QUERY_FILTER_REQUESTS). The RFC listed metrics as out of scope; they were added later.

NeuralQueryBuilder (neural-search) — mutate in place:

public QueryBuilder filter(QueryBuilder filterToBeAdded) {
    if (validateFilterParams(filterToBeAdded) == false) {
        return this;
    }
    if (this.queryfilter == null) {
        this.queryfilter = filterToBeAdded;
    } else {
        this.queryfilter = this.queryfilter.filter(filterToBeAdded);
    }
    return this;
}

Contrast this with the k-NN version below — same problem, opposite style. Same feature, two plugins, two conventions.

4.4 Why the plugins duplicate instead of share

NeuralQueryBuilder and KNNQueryBuilder want nearly identical logic, but they live in different plugins with no shared dependency. The RFC's call: accept the duplication rather than invent a shared library for ~15 lines. Pragmatic, and correct for the size.

5. k-NN PR #2599, line by line

Author: chloewqg · Merged by: junqiu-lei, 14 Mar 2025 · Commit: 89b6883 (single commit, branch chloewqg:local2)

5.1 Files changed

5.2 CHANGELOG.md

One line under ## [Unreleased 3.0] → ### Features. Mandatory in this repo; CI enforces it. Note the merged line is missing its leading * bullet marker — a cosmetic slip that got through review.

5.3 KNNQueryBuilder.filter() — the 40 lines

Inserted right after doXContent, at what was line 381:

/**
 * Add a filter to Neural Query Builder                      // (a)
 * @param filterToBeAdded fiXlter to be added                // (b)
 * @return return itself with underlying filter combined with passed in filter
 */
@Override                                                     // (c)
public QueryBuilder filter(QueryBuilder filterToBeAdded) {    // (d)
    if (validateFilterParams(filterToBeAdded) == false) {     // (e)
        return this;
    }

    if (this.filter == null) {                                // (f)
        return KNNQueryBuilder.builder()                      // (g)
            .fieldName(fieldName)
            .vector(vector)
            .k(k)
            .maxDistance(maxDistance)
            .minScore(minScore)
            .methodParameters(methodParameters)
            .filter(filterToBeAdded)                          // (h)
            .ignoreUnmapped(ignoreUnmapped)
            .rescoreContext(rescoreContext)
            .expandNested(expandNested)
            .build();                                         // (i)
    }

    return KNNQueryBuilder.builder()                          // (j)
        .fieldName(fieldName)
        .vector(vector)
        .k(k)
        .maxDistance(maxDistance)
        .minScore(minScore)
        .methodParameters(methodParameters)
        .filter(filter.filter(filterToBeAdded))               // (k) ← the whole trick
        .ignoreUnmapped(ignoreUnmapped)
        .rescoreContext(rescoreContext)
        .expandNested(expandNested)
        .build();
}

Annotations:

• (a) Javadoc says "Neural Query Builder" — copy-paste from NeuralQueryBuilder. bzhangam flagged it in review; chloewqg said a follow-up PR would fix it. It is still wrong in main today.

• (b) fiXlter — typo, also still present. Two cosmetic defects that survived review and a year of main. Instructive about what code review actually catches.

• (c) @Override is what binds this to the new core interface method. Without core PR #17409 merged first, this line is a compile error. This is the hard dependency between the two repos.

• (d) Parameter deliberately named filterToBeAdded, not filter, because filter is already a field on the class. Avoids this.filter shadowing noise in the body.

• (e) The shared null-guard from AbstractQueryBuilder. Note the == false style — OpenSearch convention, avoids the easily-missed !. Returning this (not null, not a copy) makes filter(null) a true no-op and lets callers like ConstantScoreQueryBuilder use identity comparison to detect "nothing changed."

• (f) Branch on whether a filter already exists.

• (g) No existing filter → rebuild the whole builder rather than assigning to the field. See §5.6.

• (h) The new filter becomes the filter, verbatim. No wrapping. This is what makes it a real push-down: KNNQueryBuilder.filter is handed to KNNQueryFactory at toQuery() time and drives efficient filtering.

• (i) build() runs Builder.validate() — checks fieldName non-empty, vector non-null/non-empty, exactly one of k/minScore/maxDistance, 0 < k <= K_MAX, minScore > 0. This validation-on-construction is the stated justification for the rebuild.

• (j) Existing filter → same rebuild, one field different.

• (k) The recursive delegation. filter.filter(filterToBeAdded) dispatches polymorphically on the existing filter's type:

  • existing filter is a BoolQueryBuilder → appends to its filterClauses, returns the same instance. Result: bool { ..., filter: [old..., new] }. Flat, no extra nesting.
  • existing filter is a TermQueryBuilder (or any leaf) → AbstractQueryBuilder.filter wraps it: bool { must: term, filter: newFilter }.
  • existing filter is a ConstantScoreQueryBuilder → recurses into its inner query.

  Fifteen lines get correct AND-composition for every query type in the system, present and future. That's the payoff of putting the contract in core.

What this method does NOT copy: boost and queryName. The Builder has both fields (queryName(String), boost(float), default DEFAULT_BOOST), and build() applies them via .boost(boost).queryName(queryName). filter() sets neither, so a pushed-down filter silently resets boost to 1.0 and drops the _name. Since AbstractQueryBuilder.equals compares both, this is observable. The same omission exists in doRewrite(), which predates this PR — so it's a pre-existing pattern that was copied, not a new mistake. Still a real bug. See §7.

5.4 The unit test

KNNQueryBuilderTests.testFilter(), +55 lines, three cases:

@SneakyThrows
public void testFilter() {
    // Case 1 — null is a no-op
    KNNQueryBuilder knnQueryBuilder = new KNNQueryBuilder(FIELD_NAME, QUERY_VECTOR, K);
    KNNQueryBuilder updatedKnnQueryBuilder = (KNNQueryBuilder) knnQueryBuilder.filter(null);
    assertEquals(knnQueryBuilder, updatedKnnQueryBuilder);

    // Case 2 — existing filter, AND-combined
    knnQueryBuilder = KNNQueryBuilder.builder()
        .fieldName(FIELD_NAME).vector(QUERY_VECTOR).filter(TERM_QUERY).k(K).build();
    updatedKnnQueryBuilder = (KNNQueryBuilder) knnQueryBuilder.filter(TERM_QUERY);

    BoolQueryBuilder expectedUpdatedQueryFilter = new BoolQueryBuilder();
    expectedUpdatedQueryFilter.must(TERM_QUERY);
    expectedUpdatedQueryFilter.filter(TERM_QUERY);

    assertEquals(knnQueryBuilder.fieldName(),           updatedKnnQueryBuilder.fieldName());
    assertEquals(knnQueryBuilder.vector(),              updatedKnnQueryBuilder.vector());
    assertEquals(knnQueryBuilder.getK(),                updatedKnnQueryBuilder.getK());
    assertEquals(knnQueryBuilder.getMaxDistance(),      updatedKnnQueryBuilder.getMaxDistance());
    assertEquals(knnQueryBuilder.getMinScore(),         updatedKnnQueryBuilder.getMinScore());
    assertEquals(knnQueryBuilder.getMethodParameters(), updatedKnnQueryBuilder.getMethodParameters());
    assertEquals(knnQueryBuilder.isIgnoreUnmapped(),    updatedKnnQueryBuilder.isIgnoreUnmapped());
    assertEquals(knnQueryBuilder.getRescoreContext(),   updatedKnnQueryBuilder.getRescoreContext());
    assertEquals(knnQueryBuilder.getExpandNested(),     updatedKnnQueryBuilder.getExpandNested());
    assertEquals(expectedUpdatedQueryFilter,            updatedKnnQueryBuilder.getFilter());

    // Case 3 — no existing filter, direct assignment
    knnQueryBuilder = KNNQueryBuilder.builder()
        .fieldName(FIELD_NAME).vector(QUERY_VECTOR).k(K).build();
    updatedKnnQueryBuilder = (KNNQueryBuilder) knnQueryBuilder.filter(TERM_QUERY);
    // ... same field-by-field assertions ...
    assertEquals(TERM_QUERY, updatedKnnQueryBuilder.getFilter());
}

Reading it:

• Case 1 passes precisely because filter(null) returns this — reference equality would also pass, but assertEquals documents intent.
• Case 2 is the important one. TERM_QUERY is a leaf, so filter.filter(TERM_QUERY) hits AbstractQueryBuilder.filter and produces bool { must: TERM_QUERY, filter: TERM_QUERY }. The test asserts that exact structure. It also confirms every other field survives the rebuild — which is the real risk of the rebuild-vs-mutate approach.
• Case 3 confirms the filter == null branch assigns without wrapping.
• Gap: because the assertions are field-by-field rather than assertEquals(expectedBuilder, actual), the dropped boost/queryName never gets caught. A whole-object comparison on a builder with a non-default boost would fail today.
• The (KNNQueryBuilder) casts are needed because the interface returns QueryBuilder. Safe here only because the implementation is known to return a KNNQueryBuilder; in general callers must not assume this (the base implementation returns a BoolQueryBuilder).
• The PR also left a commented-out copy of the production code inside the test as an explanatory note. Dead comment; would not survive a stricter review.

New import: org.opensearch.index.query.BoolQueryBuilder.

5.5 The integration test

FaissIT.testQueryWithFilterFunctionAppliedMultipleShards(), +50 lines. New imports: MatchNoneQueryBuilder, RangeQueryBuilder.

@SneakyThrows
public void testQueryWithFilterFunctionAppliedMultipleShards() {
    XContentBuilder builder = XContentFactory.jsonBuilder()
        .startObject()
          .startObject(PROPERTIES_FIELD_NAME)
            .startObject(FIELD_NAME)
              .field(TYPE_FIELD_NAME, KNN_VECTOR_TYPE)
              .field(DIMENSION_FIELD_NAME, "3")
              .startObject(KNNConstants.KNN_METHOD)
                .field(KNNConstants.NAME, METHOD_HNSW)
                .field(KNNConstants.METHOD_PARAMETER_SPACE_TYPE, SpaceType.L2.getValue())
                .field(KNNConstants.KNN_ENGINE, KNNEngine.FAISS.getName())
              .endObject()
            .endObject()
            .startObject(INTEGER_FIELD_NAME)
              .field(TYPE_FIELD_NAME, FILED_TYPE_INTEGER)
            .endObject()
          .endObject()
        .endObject();
    String mapping = builder.toString();

    createIndex(INDEX_NAME, Settings.builder()
        .put("number_of_shards", 10)
        .put("number_of_replicas", 0)
        .put("index.knn", true).build());
    putMappingRequest(INDEX_NAME, mapping);

    addKnnDocWithAttributes("doc1", new float[] { 7.0f, 7.0f, 3.0f },
                            ImmutableMap.of("dateReceived", "2024-10-01"));
    refreshIndex(INDEX_NAME);

    final float[] searchVector = { 6.0f, 7.0f, 3.0f };

    // (1) matching filter → 1 hit
    RangeQueryBuilder rangeQueryBuilder = QueryBuilders.rangeQuery("dateReceived").gte("2023-11-01");
    KNNQueryBuilder knnQueryBuilder = new KNNQueryBuilder(FIELD_NAME, searchVector, 1, null);
    KNNQueryBuilder updatedKnnQueryBuilder = (KNNQueryBuilder) knnQueryBuilder.filter(rangeQueryBuilder);
    Response response = searchKNNIndex(INDEX_NAME, updatedKnnQueryBuilder, 10);
    List<KNNResult> knnResults = parseSearchResponse(EntityUtils.toString(response.getEntity()), FIELD_NAME);
    assertEquals(1, knnResults.size());

    // (2) impossible filter → 0 hits
    updatedKnnQueryBuilder = (KNNQueryBuilder) knnQueryBuilder.filter(new MatchNoneQueryBuilder());
    response = searchKNNIndex(INDEX_NAME, updatedKnnQueryBuilder, 10);
    knnResults = parseSearchResponse(EntityUtils.toString(response.getEntity()), FIELD_NAME);
    assertEquals(0, knnResults.size());
}

Reading it:

• Faiss + HNSW + L2, index.knn: true — chosen because Faiss is the engine with the richest efficient-filtering path. The test lives in FaissIT, which extends KNNRestTestCase and drives a real cluster over REST.
• 10 shards, 1 document. Deliberate: the doc lands on one shard, the other nine have empty segments. This exercises the serialize→fan-out→toQuery path on shards where the filter matches nothing, catching NPEs and empty-segment bugs. That's why "MultipleShards" is in the name.
• new KNNQueryBuilder(FIELD_NAME, searchVector, 1, null) — the four-arg constructor with an explicit null filter, so the test starts on the filter == null branch.
• knnQueryBuilder.filter(...) twice on the same object — the second call at (2) reuses the original builder, not the updated one. This only works because filter() returns a new instance and leaves the receiver untouched. A mutating implementation would have made the second query range AND match_none. The immutability contract is load-bearing here, and this test would catch a regression to mutation.
• k = 1 in the query, size = 10 in the search — separates ANN k from result size.
• MatchNoneQueryBuilder is the cleanest way to prove the filter is actually reaching the engine: the doc is a perfect vector match, so a nonzero result would mean the filter was ignored.
• Weakness: with one document, this proves the filter is applied, not that it is applied efficiently. It cannot distinguish push-down from post-filtering. A recall test — 10k docs, restrictive filter, assert k results come back — would be the real proof, and isn't here.

5.6 The review debate: mutate or rebuild?

Worth reading in full on the PR; it's the most substantive part.

bzhangam: why construct a new KNNQueryBuilder instead of assigning this.filter and returning this?

heemin32: no behavioural difference today, but validation lives in build(). If a future filter-related validation is added there, direct field assignment bypasses it.

bzhangam: that's speculative — building for a use case that doesn't exist. If the concern is bypass, mark the field final and force mutation through the builder. Two-way door.

heemin32: final on a QueryBuilder reference still permits mutating the referenced object; it only prevents swapping the instance. If we'd adopt the pattern later anyway, adopt it now.

chloewqg closed it by citing a review on k-NN#2585: query builders are intended to be effectively immutable, with all parameters validated together at construction rather than individually.

Rebuild won. And as §5.5 shows, the integration test then depends on that choice. Note the inconsistency though: NeuralQueryBuilder.filter() in the sibling plugin mutates in place and returns this. Both satisfy the interface — the contract only says "return the resulting builder" — but a caller that assumes one style breaks against the other. HybridQueryBuilder handles this correctly with iterator.set(...); hand-written client code often won't.

6. End-to-end request trace

Request:

POST /products/_search?search_pipeline=nlp-pipeline
{
  "query": {
    "hybrid": {
      "queries": [
        { "match": { "title": "running shoes" } },
        { "knn": { "embedding": { "vector": [0.1, 0.2, 0.3], "k": 50 } } }
      ],
      "filter": { "term": { "in_stock": true } }
    }
  }
}

1. REST → parse. HybridQueryBuilder.fromXContent walks the JSON. queries → two builders. filter → a TermQueryBuilder.
2. Push-down loop. For each sub-query, query.filter(termQuery):
   • MatchQueryBuilder has no override → AbstractQueryBuilder.filter → returns bool { must: match, filter: term }.
   • KNNQueryBuilder overrides → this.filter == null → returns a new KNNQueryBuilder with filter = term.
   • Both results are added to the new HybridQueryBuilder. The top-level filter field is not retained — it has been fully distributed.
3. Stats. HYBRID_QUERY_FILTER_REQUESTS incremented.
4. Rewrite. KNNQueryBuilder.doRewrite rewrites the inner filter; if the rewrite produced a different object it rebuilds the k-NN builder around it. (Same missing boost/queryName copy as filter().)
5. Serialize + fan out. No wire-format change was needed anywhere in this feature: KNNQueryBuilder already serialized its filter field. That's why there's no BWC work in PR #2599.
6. toQuery per shard. In KNNQueryBuilder.doToQuery:
   • Guard: if the engine creates custom segment files and doesn't support filters (nmslib), and filter != null → IllegalArgumentException("Engine [x] does not support filters").
   • KNNQueryFactory.CreateQueryRequest.builder()...filter(this.filter)...build() → KNNQueryFactory.create(...).
7. Engine execution. The factory converts the filter builder to a Lucene Query, runs it to get a doc-ID bitset, and picks pre-filter exact search vs filtered ANN based on N/P/k/FT/MDC. The match sub-query's bool runs conventionally.
8. Normalization + combination. The hybrid search-phase processor normalizes each sub-query's score list and combines them.
9. Response.

The key structural fact: the transform happens once, at parse time, on the coordinating node. By the time anything is serialized or executed, the query is indistinguishable from one where the user typed the filters out longhand. That's the RFC's performance argument, and it holds — there's no per-shard or per-segment cost to the feature itself.

7. Semantics, edge cases, and real bugs

Combination is always AND, always. No opt-out. If a sub-query already filters category=books and you push in_stock=true, you get both. If you want OR or per-sub-query behaviour, don't use the common filter — write the filters inline.

Push-down is one level deep. hybrid.filter reaches each sub-query. It does not descend into a sub-query's inner queries — except via the specific overrides (constant_score recursing into its wrapped query, bool appending to its own filter clauses).

boost and queryName are lost. KNNQueryBuilder.filter() and doRewrite() rebuild via KNNQueryBuilder.builder() without .boost(...) or .queryName(...). A knn sub-query with "boost": 2.0 or "_name": "vec" silently loses both when a hybrid filter is pushed into it. AbstractQueryBuilder.equals compares both, so this is observable and testable. Reproduce: build a KNNQueryBuilder with a non-default boost, call filter(termQuery), assert getBoost(). This is a good first-contribution PR if you want one — the fix is two chained calls plus a test.

Filter type matters for the resulting shape.

Repeated push-downs on a leaf filter nest linearly. Not a correctness problem — Lucene flattens most of this at rewrite — but deeply nested bools show up in _validate/query?explain output and can be confusing when debugging.

nmslib rejects filters entirely. A hybrid filter pushed into a knn sub-query on an nmslib index throws at toQuery time, per-shard, not at parse time. The error surfaces as a shard failure, not a 400. Faiss and Lucene engines are fine.

Score-based filters are rejected at parse time by design (§3.7) — the pre/post normalization mismatch would produce nonsense.

Nested hybrid is not supported; pushing a filter into a nested hybrid errors.

filter must be an object. "filter": [ {...}, {...} ] is rejected. Combine with bool instead.

Mutation-style vs rebuild-style implementations coexist. NeuralQueryBuilder mutates and returns this; KNNQueryBuilder rebuilds and returns a new object; BoolQueryBuilder mutates; AbstractQueryBuilder returns a different type entirely. Always use the return value. Never call q.filter(f) for side effects.

8. Build it yourself

8.1 Dev environment

The k-NN plugin has native (JNI) dependencies, so first build is slow.

# JDK 21 is what current main targets; check build.gradle for the exact version
java -version

git clone https://github.com/opensearch-project/k-NN.git
cd k-NN
git submodule update --init -- jni/external/nmslib
git submodule update --init -- jni/external/faiss

# full build, including native libs — expect 20-40 min cold
./gradlew build

# start a single-node cluster with the plugin installed
./gradlew run
# → http://localhost:9200

If you only need the Java side compiled (no native libs, no ITs), ./gradlew compileJava compileTestJava is much faster for iterating.

For the hybrid-query half you also need the neural-search plugin, which depends on ml-commons. Easiest path for end-to-end manual testing is a Docker OpenSearch 3.x image, which bundles all three.

8.2 Implementing the change from scratch

Assume you're on a main that predates the feature.

Step 1 — verify the core contract exists.

grep -n "QueryBuilder filter(QueryBuilder" \
  ~/OpenSearch/server/src/main/java/org/opensearch/index/query/QueryBuilder.java

If it's absent, your k-NN @Override won't compile and you need OpenSearch ≥ 3.0 (or a locally published snapshot) as your dependency. This is the ordering constraint that forced core → k-NN → neural-search.

Step 2 — add the override to src/main/java/org/opensearch/knn/index/query/KNNQueryBuilder.java, after doXContent. Use the code in §5.3 — but fix the javadoc, and add the two lines the original missed:

/**
 * Combine a filter into this KNN query builder.
 * @param filterToBeAdded filter to be added
 * @return a builder whose filter is the AND-combination of the existing filter and the new one
 */
@Override
public QueryBuilder filter(QueryBuilder filterToBeAdded) {
    if (validateFilterParams(filterToBeAdded) == false) {
        return this;
    }
    final QueryBuilder combined = (this.filter == null)
        ? filterToBeAdded
        : this.filter.filter(filterToBeAdded);

    return KNNQueryBuilder.builder()
        .fieldName(fieldName)
        .vector(vector)
        .k(k)
        .maxDistance(maxDistance)
        .minScore(minScore)
        .methodParameters(methodParameters)
        .filter(combined)
        .ignoreUnmapped(ignoreUnmapped)
        .rescoreContext(rescoreContext)
        .expandNested(expandNested)
        .boost(boost)              // ← not in the merged PR
        .queryName(queryName)      // ← not in the merged PR
        .build();
}

Collapsing the two branches into one combined expression also removes the duplicated 11-line builder chain. Behaviourally identical to the merged version except for the boost/name fix.

Step 3 — imports. org.opensearch.index.query.QueryBuilder is almost certainly already imported. validateFilterParams is inherited from AbstractQueryBuilder, no import needed.

Step 4 — CHANGELOG. One bullet under ### Features in the unreleased section. CI fails without it.

Step 5 — spotless. ./gradlew spotlessApply before committing; the repo enforces formatting.

Step 6 — sign your commits. DCO is enforced: git commit --signoff.

8.3 The same feature for a query type that doesn't have it

If you're adding filter() to some other query builder, the checklist is:

1. Does the builder have a field that already means "filter" (or an inner query you should recurse into)? If not, don't override — the AbstractQueryBuilder bool-wrap is the right answer and you get it for free.
2. If it does, decide mutate-vs-rebuild and be consistent with the rest of your plugin.
3. Start with if (validateFilterParams(f) == false) return this; — the identity return is relied on by ConstantScoreQueryBuilder's != check.
4. Combine an existing filter via existing.filter(f), never by hand-rolling a BoolQueryBuilder. Delegation is what makes the feature compose.
5. If you rebuild, copy every field including boost and queryName.
6. Test: null case, no-existing-filter case, existing-filter case, and a whole-object assertEquals against an expected builder with non-default boost/name.

9. Testing

9.1 Unit tests

# just this test
./gradlew test --tests "org.opensearch.knn.index.query.KNNQueryBuilderTests.testFilter"

# whole class
./gradlew test --tests "*KNNQueryBuilderTests"

Cases to cover, beyond what the PR shipped:

public void testFilter_whenBoostAndNameSet_thenPreserved() {
    KNNQueryBuilder qb = KNNQueryBuilder.builder()
        .fieldName(FIELD_NAME).vector(QUERY_VECTOR).k(K)
        .boost(2.0f).queryName("vec").build();
    KNNQueryBuilder updated = (KNNQueryBuilder) qb.filter(TERM_QUERY);
    assertEquals(2.0f, updated.boost(), 0.0f);   // fails on merged code
    assertEquals("vec", updated.queryName());     // fails on merged code
}

public void testFilter_whenExistingFilterIsBool_thenFlatCombination() {
    BoolQueryBuilder existing = new BoolQueryBuilder().filter(TERM_QUERY);
    KNNQueryBuilder qb = KNNQueryBuilder.builder()
        .fieldName(FIELD_NAME).vector(QUERY_VECTOR).k(K).filter(existing).build();
    KNNQueryBuilder updated = (KNNQueryBuilder) qb.filter(RANGE_QUERY);
    BoolQueryBuilder actual = (BoolQueryBuilder) updated.getFilter();
    assertEquals(2, actual.filter().size());      // flat, not nested
}

public void testFilter_whenCalledTwiceOnSameBuilder_thenOriginalUnchanged() {
    KNNQueryBuilder qb = KNNQueryBuilder.builder()
        .fieldName(FIELD_NAME).vector(QUERY_VECTOR).k(K).build();
    qb.filter(TERM_QUERY);
    assertNull(qb.getFilter());                   // immutability contract
}

9.2 Integration tests

# single IT
./gradlew integTest --tests "org.opensearch.knn.index.FaissIT.testQueryWithFilterFunctionAppliedMultipleShards"

# whole IT class
./gradlew integTest --tests "*FaissIT"

ITs need the native libs built, so run a full ./gradlew build at least once first.

Worth adding — a recall test that actually proves push-down rather than mere application:

// index 10_000 docs; only ~50 have category="rare"
// query with k=10 and filter category=rare
// assert 10 results, NOT ~0
// post-filtering would return close to zero; efficient filtering returns 10

That is the assertion that distinguishes this feature from the naive implementation, and it isn't in the repo.

9.3 Manual REST testing on a live cluster

# 1. index with faiss/hnsw
curl -XPUT "localhost:9200/products" -H 'Content-Type: application/json' -d'
{
  "settings": { "index": { "knn": true, "number_of_shards": 2, "number_of_replicas": 0 } },
  "mappings": { "properties": {
    "embedding": { "type": "knn_vector", "dimension": 3,
                   "method": { "name": "hnsw", "space_type": "l2", "engine": "faiss" } },
    "title":    { "type": "text" },
    "in_stock": { "type": "boolean" }
  } }
}'

# 2. docs
curl -XPOST "localhost:9200/products/_bulk?refresh" -H 'Content-Type: application/x-ndjson' -d'
{"index":{"_id":"1"}}
{"embedding":[1.0,1.0,1.0],"title":"running shoes","in_stock":true}
{"index":{"_id":"2"}}
{"embedding":[1.1,1.0,1.0],"title":"running socks","in_stock":false}
{"index":{"_id":"3"}}
{"embedding":[9.0,9.0,9.0],"title":"hiking boots","in_stock":true}
'

# 3. plain knn with an inline filter — the pre-existing capability
curl -XPOST "localhost:9200/products/_search" -H 'Content-Type: application/json' -d'
{ "query": { "knn": { "embedding": {
      "vector": [1.0,1.0,1.0], "k": 2,
      "filter": { "term": { "in_stock": true } } } } } }'
# expect docs 1 and 3 (doc 2 is nearer than 3 but out of stock)

# 4. search pipeline for hybrid
curl -XPUT "localhost:9200/_search/pipeline/nlp-pipeline" -H 'Content-Type: application/json' -d'
{
  "description": "hybrid normalization",
  "phase_results_processors": [
    { "normalization-processor": {
        "normalization": { "technique": "min_max" },
        "combination":   { "technique": "arithmetic_mean", "parameters": { "weights": [0.3, 0.7] } } } }
  ]
}'

# 5. THE FEATURE — one top-level filter, both sub-queries
curl -XPOST "localhost:9200/products/_search?search_pipeline=nlp-pipeline" \
  -H 'Content-Type: application/json' -d'
{
  "query": {
    "hybrid": {
      "queries": [
        { "match": { "title": "running" } },
        { "knn":   { "embedding": { "vector": [1.0,1.0,1.0], "k": 2 } } }
      ],
      "filter": { "term": { "in_stock": true } }
    }
  }
}'
# doc 2 ("running socks") matches both sub-queries but is out of stock → excluded

9.4 Verifying push-down actually happened

Three ways, in increasing order of reliability:

1. _validate/query?explain — shows the Lucene query the builders produced.

curl -XPOST "localhost:9200/products/_validate/query?explain=true" \
  -H 'Content-Type: application/json' -d'
{ "query": { "hybrid": { "queries": [ { "match": { "title": "running" } } ],
                          "filter": { "term": { "in_stock": true } } } } }'

You should see the match clause wrapped in a boolean with a filter clause — proof the push-down ran at parse time.

2. Profile the query with "profile": true and look for the k-NN query implementation in the breakdown. A KnnFloatVectorQuery/Faiss query carrying a filter looks different from a BooleanQuery containing an unfiltered k-NN clause.

3. The recall test. Index enough documents that a restrictive filter would starve post-filtering, then count results. If you get k back, the filter went in. If you get near zero, it didn't. This is the only test that can't be fooled.

10. Limitations and follow-ups

Still open or unresolved as of the current main:

• Javadoc typos in KNNQueryBuilder.filter() — "Neural Query Builder" and "fiXlter". Flagged in review, promised as a follow-up, never fixed.
• boost/queryName dropped on rebuild, in both filter() and doRewrite().
• No FilterCombinationMode. AND only. OR and IGNORE_IF_EXISTS remain speculative.
• No SearchRequestProcessor variant (RFC high-level Option 2), so you can't set an index-default common filter via a default search pipeline.
• No deep push-down into a sub-query's inner queries.
• No performance/recall benchmark in the repo demonstrating the push-down advantage — the ITs prove correctness, not efficiency.
• Two conflicting conventions for filter() across plugins (mutate vs rebuild), with nothing in the interface javadoc that forces one.
• Duplicated logic between NeuralQueryBuilder and KNNQueryBuilder, accepted deliberately.

11. Reference index

Pull requests and issues

Source files

Docs

• Filtering vector search results
• Efficient k-NN filtering
• Hybrid search
• Efficient filtering in the OpenSearch vector engine (blog)

Source: kafka · kafka.md · updated 2026-08-07 · 🔒 secret gist

Synced verbatim from gist.github.com/bl9.

Apache Kafka Internals — A Maintainer's Deep Dive

Source tree: github.com/apache/kafka @ 930ebc5608bb0ac938085321d09b402b850ca87b Version: 4.4.0-SNAPSHOT · Scala 2.13.18 · LATEST_PRODUCTION = IBP_4_3_IV0 Fetched: 2026-08-06

Every file path, class name, and line-level behaviour below was read out of that tree. Where a design decision has a rationale that only exists in a code comment, the comment is the citation — Kafka's best documentation is in-source and most of it never made it into the website docs.

Table of Contents

1. How to read this codebase
2. Module topology
3. The log: on-disk format
   • 3.1 Directory and file layout
   • 3.2 RecordBatch v2, byte by byte
   • 3.3 The inner Record
   • 3.4 Why the CRC is where it is
   • 3.5 The offset index
   • 3.6 The warm-section binary search
   • 3.7 Time index, txn index, epoch cache, producer snapshots
4. The write path, end to end
   • 4.1 Acceptor / Processor / RequestChannel
   • 4.2 Request handler pool and callback re-entry
   • 4.3 ReplicaManager → Partition → UnifiedLog
   • 4.4 Anatomy of UnifiedLog.append
   • 4.5 LogValidator: offset assignment and recompression
   • 4.6 Segment roll
   • 4.7 The fsync question
   • 4.8 Idempotence: ProducerStateManager
   • 4.9 acks=all and the purgatory
5. The read path
   • 5.1 Offset → file position
   • 5.2 Zero-copy and where it breaks
   • 5.3 Fetch sessions (KIP-227)
   • 5.4 DelayedFetch
   • 5.5 Read isolation: HW vs LSO
   • 5.6 Tiered storage reads
6. Hierarchical timing wheels and the purgatory
7. Replication
   • 7.1 Pull replication, and why
   • 7.2 The high watermark, and its one-round-trip lag
   • 7.3 ISR: expand, shrink, maximal ISR
   • 7.4 Leader epochs and log reconciliation
   • 7.5 Eligible Leader Replicas (KIP-966)
8. KRaft
   • 8.1 How it differs from textbook Raft
   • 8.2 The quorum state machine, including Prospective
   • 8.3 Leader HW computation
   • 8.4 Snapshots
   • 8.5 QuorumController: a single-threaded event loop
   • 8.6 MetadataImage / MetadataDelta / MetadataLoader
   • 8.7 Feature flags and MetadataVersion
9. Coordinators
   • 9.1 The coordinator runtime
   • 9.2 Group coordinator: KIP-848
   • 9.3 The reconciliation state machine
   • 9.4 Assignors
   • 9.5 Transaction coordinator and KIP-890
   • 9.6 Share groups (KIP-932)
10. Log compaction
11. Producer client internals
12. Consumer client internals
13. Quotas, throttling, and backpressure
14. Comparison with other streaming systems
15. Design lessons: building your own
16. Maintainer's appendix

1. How to read this codebase

A few navigational facts that will save you a week.

• Scala is nearly gone from the hot paths. The log layer, the indexes, the compactor, the coordinators, the Raft implementation, the purgatory, and the timing wheel are all Java now. What remains in Scala is essentially: KafkaApis, ReplicaManager, Partition, SocketServer, the fetcher threads, KafkaConfig, and the transaction coordinator. The migration is mechanical and ongoing; don't assume a class is where a 2021 blog post says it is.
• The module boundary is a dependency boundary, enforced. clients cannot depend on server. storage cannot depend on core. This is why you see interfaces like RemoteStorageManager and AlterPartitionManager sitting in low modules with the implementation in core. When you add a class, the module you pick determines what you're allowed to call.
• internals packages are the real API. org.apache.kafka.storage.internals.log is where the log lives. org.apache.kafka.common.record.internal is where the record format lives (it moved under internal recently — a lot of stale documentation points at org.apache.kafka.common.record.DefaultRecordBatch, which no longer exists).
• Comments are load-bearing. AbstractIndex has a 40-line comment explaining a page-cache argument that is the entire reason the class is not a plain binary search. DelayedOperationPurgatory has a comment enumerating a specific 7-step deadlock. These are not decoration; they encode post-mortems.
• The generator module is real code. generator/ compiles the JSON schemas in clients/src/main/resources/common/message/*.json into request/response classes. If you're adding an RPC field, you edit JSON, not Java. ./gradlew processMessages regenerates.

2. Module topology

clients/                 protocol, record format, producer, consumer, admin, serde, network
                         (the only artifact most users depend on)
raft/                    KafkaRaftClient — the KRaft consensus implementation
metadata/                controller (QuorumController), metadata records, image/delta, loader
server-common/           purgatory, timing wheel, MetadataVersion, shared utils
server/                  broker-side pieces that don't need core's Scala: quotas, fetch sessions
storage/                 UnifiedLog, LogSegment, indexes, compaction, tiered storage
coordinator-common/      the generic coordinator runtime (event loop + replicated state machine)
group-coordinator/       consumer groups, share groups, streams groups
share-coordinator/       durable share-group acknowledgement state
transaction-coordinator/ transaction metadata types (state machine still partly Scala in core)
core/                    KafkaApis, ReplicaManager, Partition, SocketServer, BrokerServer,
                         ControllerServer, fetcher threads
streams/                 Kafka Streams
connect/                 Kafka Connect
tools/, shell/, trogdor/ CLI, metadata shell, fault injection harness
jmh-benchmarks/          microbenchmarks — read these, they document the hot paths

The dependency direction is roughly clients ← server-common ← {raft, storage, server} ← {metadata, coordinator-common} ← core. core is the only module that can see everything, which is why it's the residual Scala pile.

3. The log: on-disk format

3.1 Directory and file layout

A log.dirs entry contains one directory per partition, named <topic>-<partition>:

/var/lib/kafka/data/
├── meta.properties                  # cluster id, node id, directory id
├── orders-0/
│   ├── partition.metadata           # topic id (written before any data — see below)
│   ├── leader-epoch-checkpoint      # (epoch, startOffset) pairs
│   ├── 00000000000000000000.log     # segment: the actual records
│   ├── 00000000000000000000.index   # offset index, mmapped, sparse
│   ├── 00000000000000000000.timeindex
│   ├── 00000000000000000000.snapshot # producer state snapshot at this base offset
│   ├── 00000000000000368142.log
│   ├── 00000000000000368142.index
│   ├── 00000000000000368142.timeindex
│   ├── 00000000000000368142.txnindex # only if aborted txns exist in this segment
│   └── 00000000000000368142.snapshot
└── __cluster_metadata-0/            # the KRaft log, on controllers and brokers alike
    ├── 00000000000000000000.log
    └── ...-0000000000-0000000000.checkpoint   # KRaft snapshots

The filename is the base offset, zero-padded to 20 digits, which makes lexical sort equal numeric sort. Everything is derivable from that number, which is why LogSegments can be a ConcurrentNavigableMap<Long, LogSegment> and segment lookup is a floorEntry.

One subtlety that costs people data: UnifiedLog.append opens with

// We want to ensure the partition metadata file is written to the log dir before any log data is written to disk.
// This will ensure that any log data can be recovered with the correct topic ID in the case of failure.
maybeFlushMetadataFile();

partition.metadata must hit disk before the first record. Without it, a crash leaves a directory of records that can't be attributed to a topic ID, and topic IDs are how KRaft distinguishes a recreated topic from the original.

Transient files you will see and should recognize:

.cleaned vs .swap is the crash-consistency protocol for compaction: the presence of .swap means the new segment is fully written and the rename is idempotent to redo.

3.2 RecordBatch v2, byte by byte

From clients/src/main/java/org/apache/kafka/common/record/internal/DefaultRecordBatch.java:

Offset  Size  Field
------  ----  -----------------------------------------------------
  0      8    BaseOffset            int64
  8      4    Length                int32   (bytes after this field)
 12      4    PartitionLeaderEpoch  int32   ← NOT covered by CRC
 16      1    Magic                 int8    (= 2)
 17      4    CRC                   uint32  CRC-32C over bytes 21..end
 21      2    Attributes            int16
 23      4    LastOffsetDelta       int32   (also = LastSequenceDelta)
 27      8    BaseTimestamp         int64
 35      8    MaxTimestamp          int64
 43      8    ProducerId            int64
 51      2    ProducerEpoch         int16
 53      4    BaseSequence          int32
 57      4    RecordsCount          int32
 61      -    Records               [Record]  (compressed as one blob if enabled)

RECORD_BATCH_OVERHEAD = 61 bytes. LOG_OVERHEAD = 12 (BaseOffset + Length) — that's the framing prefix that lets you skip a batch without parsing it.

Attributes bitfield:

bit  0-2  compression type (0 none, 1 gzip, 2 snappy, 3 lz4, 4 zstd)
bit  3    timestamp type (0 CreateTime, 1 LogAppendTime)
bit  4    transactional
bit  5    control batch (contains markers, not user data)
bit  6    delete horizon set (compaction tombstone retention)
bit 7-15  unused

Three properties of this layout matter enormously and are worth stealing:

1. Compression is per-batch, not per-record. The compressed blob starts right after RecordsCount. This means the broker can route, index, and replicate a batch without decompressing it. Systems that compress per-message (or per-request-with-per-message framing) give up an order of magnitude on wire efficiency for high-cardinality small records.
2. Offsets and timestamps are deltas. A record stores OffsetDelta and TimestampDelta as varints relative to the batch header. A batch of 10,000 sequential records with clock-adjacent timestamps costs ~1–2 bytes per record for both fields combined.
3. The batch is the unit of everything: the unit of compression, of CRC, of idempotence (BaseSequence/LastOffsetDelta), of transactional membership, and of replication. The entire system's constant factors come from having chosen the batch as the atom.

3.3 The inner Record

From DefaultRecord.java:

Record =>
  Length          Varint
  Attributes      Int8      (currently all bits unused)
  TimestampDelta  Varlong
  OffsetDelta     Varint
  KeyLength       Varint    (-1 = null)
  Key             Bytes
  ValueLength     Varint    (-1 = null)
  Value           Bytes
  HeadersCount    Varint
  Headers         [HeaderKeyLength Varint, HeaderKey String,
                   HeaderValueLength Varint, HeaderValue Bytes]

MAX_RECORD_OVERHEAD = 21 — "5 bytes length + 10 bytes timestamp + 5 bytes offset + 1 byte attributes", the worst case. In practice a record in a dense batch costs 6–8 bytes of framing.

Varints are ZigZag-encoded (Protobuf style), in ByteUtils. sizeOfVarint(-1) is precomputed as NULL_VARINT_SIZE_BYTES because null keys/values are extremely common (tombstones) and the size estimate is on the producer hot path.

A null value is a tombstone — semantically meaningful only in compacted topics, where it instructs the cleaner to remove the key. This is the one place Kafka's storage layer knows anything about record semantics.

3.4 Why the CRC is where it is

This is the single most interesting layout decision in the format, and the comment explains it:

The CRC covers the data from the attributes to the end of the batch [...] It is located after the magic byte, which means that clients must parse the magic byte before deciding how to interpret the bytes between the batch length and the magic byte. The partition leader epoch field is not included in the CRC computation to avoid the need to recompute the CRC when this field is assigned for every batch that is received by the broker.

Read that again. PartitionLeaderEpoch is written by the broker into a batch the producer CRC'd. If it were inside the CRC, every single produced batch would require a full CRC recomputation on the broker — on the hottest path in the system, over the full batch payload. By placing the field outside the checksummed range, the broker does a 4-byte in-place putInt and moves on.

The cost is that the magic byte sits after a field that isn't checksummed, so parsers must read magic first, then decide how to interpret preceding bytes. That's a genuinely awkward format. They took the awkwardness to save the CPU.

CRC-32C (Castagnoli) is used, not CRC-32, because it has a hardware instruction (SSE4.2 CRC32, ARMv8 CRC32C) and the JDK intrinsifies it. On a modern core that's ~1 byte/cycle vs. ~1 byte/8 cycles for a table-driven CRC-32.

Steal this: if you're designing a replicated log format, decide up front which fields are client-authored and which are server-authored, and put a checksum boundary between them.

3.5 The offset index

OffsetIndex is an mmapped array of 8-byte entries: (relativeOffset: int32, physicalPosition: int32).

Relative to the segment base offset — which is why a segment can only span Integer.MAX_VALUE offsets, and why AbstractIndex.toRelative returns OptionalInt.empty() on overflow, and why LogSegmentOffsetOverflowException exists.

It is sparse: an entry is appended only every log.index.interval.bytes (default 4096) of log written. So a lookup is: binary search the index for the largest entry ≤ target, then linear scan the log from that physical position. FileRecords.searchForOffsetFromPosition does the scan, and note how carefully it avoids lastOffset():

// The following logic is intentionally designed to minimize memory usage by avoiding
// unnecessary calls to lastOffset() for every batch.
// Instead, we use baseOffset() comparisons when possible, and only check lastOffset() when absolutely necessary.

baseOffset() is a field read from the batch header. lastOffset() is baseOffset + lastOffsetDelta — also a header read, but on a FileChannelRecordBatch it may force a header materialization. The loop is written to touch as few batch headers as possible.

The whole index for a 1 GB segment at default settings is 1 GB / 4 KB × 8 B = 2 MB. That's the entire index cost of Kafka's storage engine. Compare to an LSM tree's block index plus bloom filters plus manifest.

3.6 The warm-section binary search

This is the best-documented micro-optimization in the codebase and it's worth reproducing the argument, because it generalizes to any mmapped append-only index.

The setup: index files are mmapped, so reads go through the page cache. Appends always land at the end. Lookups (from in-sync followers and caught-up consumers) are also almost always near the end. So the pages near the end are hot and the rest are cold.

Now consider a standard binary search on a 13-page index, looking for something in page 12:

page number: |0|1|2|3|4|5|6|7|8|9|10|11|12 |
steps:       |1| | | | | |3| | |4|  |5 |2/6|

Pages 0, 6, 9, 11, 12 get touched every lookup, so they stay warm. Fine. Now the index grows to 14 pages:

page number: |0|1|2|3|4|5|6|7|8|9|10|11|12|13 |
steps:       |1| | | | | | |3| | | 4|5 | 6|2/7|

The probe set shifts to 0, 7, 10, 12, 13. Pages 7 and 10 have not been touched in a long time. The very next lookup after the index crosses a page boundary takes two cold page faults.

In our test, this can cause the at-least-once produce latency to jump to about 1 second from a few ms.

A one-second p99 spike, periodic, caused by binary search probe-set drift. The fix:

int firstHotEntry = Math.max(0, entries - 1 - warmEntries());
if (compareIndexEntry(parseEntry(idx, firstHotEntry), target, searchEntity) < 0) {
    return binarySearch(idx, target, searchEntity, searchResultType, firstHotEntry, entries - 1);
}
// ... else search [0, firstHotEntry]

warmEntries() = 8192 / entrySize() — i.e., the last 8 KB of the index. Two pages on a 4 KB-page machine. The comment justifies the constant on both sides:

• Not smaller: 8 KB of offset index ≈ 4 MB of log, so with default settings essentially all in-sync lookups land in the warm section.
• Not larger: a warm-section lookup touches exactly three entries — end, end-N, and (end*2-N)/2. With N = 8192 bytes and a ≥4 KB page, those three probes touch all ≤3 pages of the warm section on every lookup, so the entire warm section stays genuinely warm. Make N bigger and you'd have warm-section pages that aren't touched every time, which defeats the point.

The TODO at the end is honest about the remaining hole: low-QPS partitions have cold warm sections too, and the real fix would be a background thread that touches them.

Generalizable rule: when your data structure lives in the page cache and has a skewed access pattern, the algorithm's probe set stability matters as much as its asymptotic complexity. A O(log n) search whose probe set drifts is worse than an O(log n) search whose probe set is pinned.

3.7 Time index, txn index, epoch cache, producer snapshots

.timeindex — 12-byte entries (timestamp: int64, relativeOffset: int32), monotonically increasing in both. Backs ListOffsets by timestamp and time-based retention. Same warm-section search (warmEntries() = 8192/12 ≈ 682 entries).

.txnindex — TransactionIndex, a list of AbortedTxn records (producerId, firstOffset, lastOffset, lastStableOffset). Written on segment.updateTxnIndex(completedTxn, lastStableOffset) when an abort marker is appended. On a READ_COMMITTED fetch, the broker returns this list alongside the records and the consumer does the filtering. The broker never decompresses or filters user data for transactions — a deliberate choice to keep the fetch path zero-copy.

leader-epoch-checkpoint — a plain-text list of (epoch, startOffset). Maintained by LeaderEpochFileCache. This is the substrate of log reconciliation (§7.4). Note in UnifiedLog.append:

validRecords.batches().forEach(batch -> {
    if (batch.magic() >= RecordBatch.MAGIC_VALUE_V2) {
        assignEpochStartOffset(batch.partitionLeaderEpoch(), batch.baseOffset());
    } else {
        // In partial upgrade scenarios, we may get a temporary regression to the message format. In
        // order to ensure the safety of leader election, we clear the epoch cache so that we revert
        // to truncation by high watermark after the next leader election.
        if (leaderEpochCache.nonEmpty()) {
            logger.warn("Clearing leader epoch cache after unexpected append with message format v{}", batch.magic());
            leaderEpochCache.clearAndFlush();
        }
    }
});

The fallback path is the pre-KIP-101 "truncate to HW" behaviour, which is known to be able to lose data. It's preserved as a correctness-degrading-but-not-crashing escape hatch for mixed-format logs.

.snapshot — serialized ProducerStateManager state as of the segment base offset. On recovery, LogLoader finds the newest snapshot ≤ recovery point and replays forward, rather than scanning the whole log to rebuild producer sequence state. Retained for producer.id.expiration.ms worth of segments.

4. The write path, end to end

Let's trace a single ProduceRequest from the socket to fsync.

4.1 Acceptor / Processor / RequestChannel

core/src/main/scala/kafka/network/SocketServer.scala.

The threading model is a two-stage reactor:

 [Acceptor thread]  (1 per listener)
   ServerSocketChannel.accept()
   → round-robin assign to a Processor
   → processor.newConnections.offer(socketChannel)   [ArrayBlockingQueue, size 20]

 [Processor threads]  (num.network.threads per listener, default 3)
   loop:
     configureNewConnections()   // drain newConnections, register with selector
     processNewResponses()       // pull from responseQueue, register writes
     poll()                      // selector.poll(timeout)
     processCompletedReceives()  // → requestChannel.sendRequest(req)
     processCompletedSends()
     processDisconnected()
     closeExcessConnections()

 [RequestChannel]
   requestQueue: ArrayBlockingQueue[BaseRequest](queued.max.requests, default 500)

 [KafkaRequestHandler threads]  (num.io.threads, default 8)
   loop: requestChannel.receiveRequest() → KafkaApis.handle(request)

The interesting details:

Acceptor backpressure. newConnections is bounded at 20 per processor. If a processor is saturated, the acceptor blocks on newConnections.put() — which stops accepting. That's deliberate: better to leave connections in the kernel backlog than to accept them into a queue you can't serve.

Poll timeout. val pollTimeout = if (newConnections.isEmpty) 300 else 0 — if there are connections waiting to be configured, don't block in the selector at all.

Exception discipline. The processor loop catches Throwable at the top and keeps going:

We catch all the throwables here to prevent the processor thread from exiting. We do this because letting a processor exit might cause a bigger impact on the broker.

Losing a network thread silently degrades a third of your connection capacity with no crash. This is the right call for a broker, and the wrong call for most other software; know which one you're writing.

Channel muting. A channel is muted (removed from the read interest set) while its request is in flight. That's how Kafka enforces at most one in-flight request per connection server-side, which in turn is what makes max.in.flight.requests.per.connection=5 safe for idempotent producers — the broker processes a connection's requests strictly in order. handleChannelMuteEvent / tryUnmuteChannel implement it, and throttling piggybacks on the same mechanism (§13).

Memory pool. Selector holds a MemoryPool (queued.max.request.bytes). When memoryPool.availableMemory() < lowMemThreshold (10% of pool), the selector stops reading from all channels:

this.lowMemThreshold = (long) (0.1 * this.memoryPool.size());
...
if (!outOfMemory && memoryPool.availableMemory() < lowMemThreshold) { ... }

This is a global backpressure valve that pushes flow control down into TCP. Under sustained overload, receive windows close and producers block in send() rather than the broker OOMing. If you're building a broker, build this on day one — it is far harder to retrofit.

4.2 Request handler pool and callback re-entry

RequestChannel actually has two queues:

private val requestQueue = new ArrayBlockingQueue[BaseRequest](queueSize)
private val callbackQueue = new ArrayBlockingQueue[BaseRequest](queueSize)
...
def receiveRequest(timeout: Long): BaseRequest = {
  val callbackRequest = callbackQueue.poll()
  if (callbackRequest != null) callbackRequest
  else {
    val request = requestQueue.poll(timeout, TimeUnit.MILLISECONDS)
    request match {
      case _: WakeupRequest => callbackQueue.poll()
      case _ => request
    }
  }
}

The callback queue has strict priority. Its purpose: an operation that went async (a purgatory completion, a coordinator write, a remote-storage read) needs to finish on an I/O thread, and it must not queue behind 500 new produce requests. The WakeupRequest sentinel is pushed into requestQueue when a callback is enqueued, purely to unblock a handler that's parked in requestQueue.poll(timeout).

This is a nice pattern: a priority lane plus a wakeup token, rather than a priority queue (which would put a comparator on the hot path) or a separate thread pool (which would double the context switches).

4.3 ReplicaManager → Partition → UnifiedLog

KafkaApis.handleProduceRequest → ReplicaManager.appendRecords → ReplicaManager.appendToLocalLog → Partition.appendRecordsToLeader → UnifiedLog.appendAsLeader.

Partition.appendRecordsToLeader is where the min.insync.replicas check happens, before the append:

val minIsr = leaderLog.config.minInSyncReplicas.min(remoteReplicasMap.size + 1)

Note the .min(replicas + 1) — if you set min.insync.replicas=3 on a topic with RF=2, it's clamped rather than making the partition permanently unwritable. This clamp is newer than most people's mental model.

Partition holds the ISR machinery. Its partitionState field is a state machine:

CommittedPartitionState      — ISR is what the controller believes
PendingExpandIsr             — we've sent AlterPartition to add a replica, awaiting response
PendingShrinkIsr             — we've sent AlterPartition to remove replicas, awaiting response
OngoingReassignmentState     — adding/removing replicas mid-reassignment

The pending states are why maximalIsr exists (§7.3).

4.4 Anatomy of UnifiedLog.append

storage/src/main/java/org/apache/kafka/storage/internals/log/UnifiedLog.java:1115. The sequence, with the reasoning:

maybeFlushMetadataFile();                                          // topic id durable first
LogAppendInfo appendInfo = analyzeAndValidateRecords(...);         // CRC, sizes, offset monotonicity
if (appendInfo.validBytes() <= 0) return appendInfo;               // nothing to do
MemoryRecords trimmedRecords = trimInvalidBytes(records, appendInfo); // drop partial trailing batch
synchronized (lock) {                                              // ← the per-partition write lock
    // 1. offset assignment + validation + possible recompression
    // 2. leader epoch cache update
    // 3. maybeRoll
    // 4. producer state analysis (idempotence / txn)
    // 5. localLog.append  → FileRecords.append + index maybe-append
    // 6. updateHighWatermarkWithLogEndOffset
    // 7. txn index update, LSO advance
    // 8. flush if unflushedMessages >= flushInterval
}

Things worth calling out:

One lock per partition, and it covers real I/O. localLog.append writes to a FileChannel while holding the lock. It doesn't fsync (usually), so this is a page-cache write, but it is a syscall. Partition count is therefore your write concurrency — a topic with one partition has one writer, period. This is the fundamental reason Kafka's scaling unit is the partition and not the topic, and it's a property you inherit if you copy the design.

Trimming is silent. trimInvalidBytes drops a trailing partial batch without error. That's what makes it safe for a producer to send a truncated buffer, and it's also why a validBytes() <= 0 result returns a successful-looking LogAppendInfo with no offsets.

Two size checks, not one. There's a per-batch maxMessageSize check, and separately:

if (validRecords.sizeInBytes() > config().segmentSize()) {
    throw new RecordBatchTooLargeException(...);
}

You cannot append more than one segment's worth in a single call, because a segment must be able to hold at least one complete append.

Re-validation after recompression. If messageSizeMaybeChanged(), sizes are checked again — a broker recompressing from lz4 to zstd can change the batch size, and the check uses the original size for bytesRejectedRate to keep the metric comparable across the change.

Duplicate detection short-circuits the write entirely. If analyzeAndValidateProducerState returns a maybeDuplicate, the append info is filled in from the original batch's metadata and nothing is written. The producer gets back the offsets it got the first time. This is the whole of idempotent produce, and it's ~10 lines.

Ordering of LEO vs. txn index. The comment is explicit:

Append the records, and increment the local log end offset immediately after the append because a write to the transaction index below may fail, and we want to ensure that the offsets of future appends still grow monotonically. The resulting transaction index inconsistency will be cleaned up after the log directory is recovered.

They chose "monotonic offsets always, txn index may need repair" over "both or neither". Correct choice: offset monotonicity is an invariant every other subsystem depends on; the txn index is rebuildable.

4.5 LogValidator: offset assignment and recompression

LogValidator.validateMessagesAndAssignOffsets has three modes:

1. assignOffsetsNonCompressed — the fast path. Iterate batches, stamp baseOffset, lastOffsetDelta, partitionLeaderEpoch, timestamps, in place in the ByteBuffer. No copy, no CRC recompute (remember: leader epoch is outside the CRC).
2. validateMessagesAndAssignOffsetsCompressed — when source and target compression match and nothing forces a rewrite, it can still do in-place header stamping: it validates the inner records by decompressing into a BufferSupplier-provided buffer, then patches only the header.
3. buildRecordsAndAssignOffsets — the slow path. Full decompress → re-validate → recompress. Triggered by a compression type change (compression.type differs from producer's), a magic downgrade, or LogAppendTime with compressed input requiring timestamp rewrite.

BrokerCompressionType.targetCompression(config().compression, appendInfo.sourceCompression()) decides. compression.type=producer (the default) is what keeps you on paths 1–2. Setting a broker or topic compression.type that differs from what producers send silently puts every produce request on the recompression path. This is the single most common self-inflicted broker CPU problem in production.

The RequestLocal.bufferSupplier() threaded through here is a per-request-handler-thread buffer cache — decompression buffers are recycled per thread rather than allocated per batch. That's why append takes a RequestLocal at all.

4.6 Segment roll

maybeRoll(messagesSize, appendInfo) → LocalLog.roll. Roll triggers:

On roll: the old segment's indexes are trimmed to their actual size (resize() on the mmap — this is where AbstractIndex.resize and its remap write-lock earn their keep), a producer state snapshot is taken, and the new segment's files are created. Index trimming matters: an untrimmed index file is segment.index.bytes (10 MB) regardless of how full it is, so a broker with 50,000 segments would waste 500 GB of sparse-file page cache without it.

Roll is not free — it's file creation, mmap, mmap trim, and a producer snapshot, all under the partition lock. Very small segment.ms on a high-partition-count broker is a known way to make p99 produce latency ugly.

4.7 The fsync question

if (localLog.unflushedMessages() >= config().flushInterval) flush(false);

config().flushInterval is flush.messages, and its default is Long.MAX_VALUE. There is also flush.ms, defaulting to Long.MAX_VALUE.

Kafka does not fsync on the produce path. By default it never explicitly fsyncs a data segment at all except on roll and on clean shutdown. Durability comes from replication, not from the disk. acks=all means "in the page cache of min.insync.replicas machines", not "on the platters of any machine".

The reasoning, which I think is correct and which people still argue about:

• An fsync per produce request caps you at the device's sync IOPS. On NVMe that's survivable; on anything with a battery-backed cache it's fine; on EBS gp3 it is not.
• Correlated failure (a rack, an AZ, a bad kernel) defeats fsync anyway, and uncorrelated failure is exactly what replication handles.
• The page cache is a better cache than anything Kafka could build in the JVM: it's shared with the read path, it's not subject to GC, it survives broker restart, and sendfile can serve directly out of it.

The tail risk is real and named: a simultaneous power loss to min.insync.replicas machines loses acknowledged writes. If your deployment has correlated power domains, set flush.messages=1 and accept the IOPS bill, or put the replicas in different failure domains. There is no third option and the docs should say so more loudly.

Contrast with the KRaft metadata log, which does fsync — KafkaRaftLog flushes before responding to the leader, because Raft's safety proof requires durable votes and durable log entries. Kafka runs two different durability models in the same process, on purpose.

4.8 Idempotence: ProducerStateManager

Per-partition, per-producer-id state. ProducerStateEntry holds the last few BatchMetadata records (NUM_BATCHES_TO_RETAIN = 5):

BatchMetadata(lastSeq, lastOffset, offsetDelta, timestamp)

ProducerAppendInfo.append validates:

• Epoch fencing: incoming producerEpoch < currentEpoch → ProducerFencedException.
• Sequence continuity: expected lastSeq + 1. Gap → OutOfOrderSequenceException. This is fatal-ish, because the broker cannot know whether the missing batch was lost or is merely delayed.
• Duplicate: incoming (baseSequence, lastSequence) matches a retained BatchMetadata → return the cached offsets, write nothing.

Retaining 5 batches, not 1, is what makes max.in.flight.requests.per.connection=5 safe with enable.idempotence=true: a retry of batch n can arrive after n+1..n+4 have been accepted, and the broker still recognizes it as a duplicate rather than an out-of-order sequence.

Sequence numbers are int32 and wrap. Producer IDs are int64, allocated in blocks by the controller (ProducerIdControlManager / RPCProducerIdManager, ProducerIdsRecord in the metadata log) — a block per broker, so InitProducerId is usually a local operation.

State is expired after producer.id.expiration.ms (default 24h) of inactivity, which is also why a producer idle for longer than that can get UNKNOWN_PRODUCER_ID and must re-initialize.

The empty-batch-retention rule from the format comment ties in here:

if all of the records in a batch are removed during compaction, the broker may still retain an empty batch header in order to preserve the producer sequence information [...] retained only until either a new sequence number is written by the corresponding producer or the producerId is expired

Compaction must not destroy the sequence state that a rebuilt leader needs, or every producer would get a spurious OutOfOrderSequence after failover.

4.9 acks=all and the purgatory

ReplicaManager.appendRecords → local append succeeds → if acks == -1, maybeAddDelayedProduce builds a DelayedProduce and puts it in the produce purgatory keyed by TopicPartitionOperationKey per partition.

val delayedProduce = new DelayedProduce(timeoutMs, initialProduceStatus.asJava, delegate, responseCallback.asJava)
delayedProducePurgatory.tryCompleteElseWatch(delayedProduce, producerRequestKeys)

The completion trigger is Partition.maybeIncrementLeaderHW returning true — which happens when a follower's FetchRequest advances the leader's view of that follower's LEO. So the produce response latency for acks=all is:

produce_latency ≈ local_append + (time until every ISR follower's next fetch returns
                                  and its subsequent fetch reports the new LEO)

Note the subsequent fetch. The leader learns a follower has the data only when the follower's next fetch arrives with a higher fetchOffset. replica.fetch.wait.max.ms (default 500 ms) bounds how long a follower's fetch parks, but followers use fetch.min.bytes=1 so a fetch returns as soon as there's data — the practical latency is two network round trips plus the follower's local append.

DelayedProduce.tryComplete checks each partition's PartitionStatusValidator, which distinguishes: still-waiting, HW advanced past the required offset (success), leader changed (NotLeaderOrFollower), or ISR shrank below min.insync.replicas (NotEnoughReplicasAfterAppend — note the AfterAppend variant; the data is in the log and may still become committed, which is why this error is explicitly not safe to retry blindly under exactly-once).

5. The read path

5.1 Offset → file position

UnifiedLog.read(startOffset, maxLength, isolation, minOneMessage)
  → LocalLog.read
    → segments.floorEntry(startOffset)              // ConcurrentNavigableMap
    → segment.read(startOffset, maxSize, maxPosition, minOneMessage)
      → offsetIndex.lookup(startOffset)             // mmap binary search (warm section)
      → FileRecords.searchForOffsetFromPosition()   // linear scan from index hint
      → FileRecords.slice(position, length)         // no bytes read yet!

FileRecords.slice returns a new FileRecords sharing the same FileChannel with different start/end. No data has been read at this point. The FetchDataInfo handed back up the stack contains a lazy view over a file range.

maxPosition is the bound imposed by isolation level. For READ_UNCOMMITTED it's the HW's physical position; for READ_COMMITTED it's the LSO's. This is why LogOffsetMetadata carries (messageOffset, segmentBaseOffset, relativePositionInSegment) rather than just an offset — the fetch path needs the physical position of the HW without doing another index lookup.

minOneMessage handles the case where a single batch exceeds fetch.max.bytes: rather than return empty forever (a livelock), return the one oversized batch.

5.2 Zero-copy and where it breaks

FileRecords.writeTo:

public int writeTo(TransferableChannel destChannel, int offset, int length) throws IOException {
    long newSize = Math.min(channel.size(), end) - start;
    int oldSize = sizeInBytes();
    if (newSize < oldSize)
        throw new KafkaException("Size of FileRecords ... has been truncated during write");
    long position = start + offset;
    int count = Math.min(length, oldSize - offset);
    return (int) destChannel.transferFrom(channel, position, count);
}

transferFrom delegates to FileChannel.transferTo, which on Linux is sendfile(2). The path is page cache → socket buffer, entirely in the kernel. No user-space copy, no JVM heap allocation, no GC pressure proportional to fetch volume.

The truncation check is a real hazard: between building the FetchDataInfo and writing it, the log could be truncated (leader change) or deleted (retention). Failing loudly beats sending garbage.

TransferableChannel's javadoc names the sharp edge:

it will unwrap the destination channel, if possible, in order to benefit from zero copy. This is required because the fast path of transferTo is only executed if the destination buffer inherits from an internal JDK class.

If you wrap the socket channel in anything the JDK doesn't recognize, transferTo silently falls back to a read/write loop through a heap buffer. PlaintextTransportLayer.transferFrom unwraps carefully to stay on the fast path.

Zero-copy is lost when:

The TLS point is worth internalizing: Kafka's headline throughput numbers are plaintext numbers. If you must have TLS in the data path, budget for it, and consider whether sendfile-preserving alternatives (kTLS, offload NICs) are available to you.

5.3 Fetch sessions (KIP-227)

server/src/main/java/org/apache/kafka/server/FetchSession.java and FetchSessionCacheShard.java.

The problem: a follower fetching 5,000 partitions sends a FetchRequest naming all 5,000 partitions every ~100 ms, even though only a handful have new data. The request itself becomes the bottleneck.

The solution: the broker caches the session's partition set and last-fetched offsets. A follow-up "incremental" fetch sends only changes (added/removed partitions, changed offsets) plus a session ID and epoch. The response contains only partitions with data.

private int cachedSize = -1;   // last known size of this session; -1 = not in cache
private final int id;
private final boolean privileged;
private final ImplicitLinkedHashCollection<CachedPartition> partitionMap;
private volatile long lastUsedMs;
private volatile int epoch;

ImplicitLinkedHashCollection is a Kafka-specific data structure: a hash set where the link pointers live in the elements, so there's no per-entry Node object. With hundreds of thousands of cached partitions across sessions, that allocation saving is the difference between this being viable and not.

Eviction is two-tier and it's where the interesting policy lives. FetchSessionCacheShard keeps two TreeMaps:

private final TreeMap<EvictableKey, FetchSession> evictableByAll = new TreeMap<>();
private final TreeMap<EvictableKey, FetchSession> evictableByPrivileged = new TreeMap<>();

privileged = the session was created by a follower (replication), not a consumer. Followers can evict consumers; consumers cannot evict followers. The ordering key is (privileged, size, lastUsedMs) — bigger sessions are preferred for retention, since they save more. A session also becomes evictable-by-all once it's older than evictionMs:

if ((!session.privileged()) || (now - session.creationMs() > evictionMs))

Steal this: when you cache per-client state on a server, classify clients by criticality and make the eviction lattice explicit. "Replication traffic outranks consumer traffic" is a policy you want in the type system, not in a heuristic.

Failure mode to know: when the cache is full (max.incremental.fetch.session.cache.slots, default 1000), new sessions get INVALID_SESSION_ID and fall back to full fetches. This degrades silently into a throughput cliff. Watch NumIncrementalFetchSessions and IncrementalFetchSessionEvictionsPerSec.

5.4 DelayedFetch

If fetch.min.bytes isn't satisfied, the fetch goes into the fetch purgatory with fetch.max.wait.ms. DelayedFetch.tryComplete re-checks accumulated bytes and completes on:

• enough bytes accumulated
• the fetched partition's HW advanced (for follower fetches, LEO advanced)
• leader changed / partition moved / log truncated
• timeout

Completion is triggered from ReplicaManager.completeDelayedFetchRequests(topicPartitions), called after appends. So an acks=1 produce to a partition immediately unblocks consumers parked on that partition, without polling.

Note the interaction: produce completions and fetch completions are both purgatory operations watched on TopicPartitionOperationKey, and an append triggers checkAndComplete on both purgatories. One append can complete N delayed produces and M delayed fetches. The purgatory's estimatedTotalOperations / purgeInterval machinery exists to bound the cost of the watcher lists that build up from completed-but-not-yet-purged operations.

5.5 Read isolation: HW vs LSO

Two ceilings on what a consumer can see:

• High watermark (HW) — the highest offset replicated to all ISR members. READ_UNCOMMITTED consumers read up to HW.
• Last stable offset (LSO) — min(HW, firstUnstableOffset), where firstUnstableOffset is the first offset belonging to an open transaction. READ_COMMITTED consumers read up to LSO.

maybeIncrementFirstUnstableOffset() runs on every append. If a transaction opens at offset 1000 and stays open, LSO pins at 1000 even as HW runs to 10,000,000. A single hung transactional producer blocks every READ_COMMITTED consumer on that partition indefinitely — until transaction.max.timeout.ms fires and the coordinator aborts it. This is the number-one exactly-once operational surprise.

TransactionIndex supplies the abort list, and the consumer filters. In CompletedFetch/AbstractFetch, the consumer maintains a priority queue of aborted transactions by start offset and drops records whose producerId matches an open abort. Control batches (bit 5 of attributes) are consumed by the client and never surfaced to the application.

5.6 Tiered storage reads

RemoteLogManager (storage/src/main/java/org/apache/kafka/server/log/remote/storage/). Two SPIs:

• RemoteStorageManager — bytes. copyLogSegmentData, fetchLogSegment, fetchIndex, deleteLogSegmentData.
• RemoteLogMetadataManager — metadata. Default implementation (TopicBasedRemoteLogMetadataManager) stores it in an internal Kafka topic, __remote_log_metadata. Kafka storing Kafka's metadata in Kafka.

Three task pools:

private final ConcurrentHashMap<TopicIdPartition, RLMTaskWithFuture> leaderCopyRLMTasks;
private final ConcurrentHashMap<TopicIdPartition, RLMTaskWithFuture> leaderExpirationRLMTasks;
private final ConcurrentHashMap<TopicIdPartition, RLMTaskWithFuture> followerRLMTasks;

Copy and expiration are separate pools — that split was added because slow expiration (S3 DELETE throttling) was starving the copy path and causing local disks to fill.

Only segments below the high watermark and fully rolled are copied. Local retention (local.retention.ms / .bytes) then deletes them locally; total retention governs remote.

The read path. ReplicaManager.readFromLog gets an OffsetOutOfRangeException for the local log when the requested offset is below logStartOffset but above the remote start, and builds a RemoteStorageFetchInfo. Then:

remoteFetchTask = remoteLogManager.get.asyncRead(remoteFetchInfo, (result: RemoteLogReadResult) => {
  remoteFetchResult.complete(result)
  ...
})

and a DelayedRemoteFetch goes into the purgatory. The I/O thread is not blocked on S3. A separate RemoteStorageThreadPool does the fetch; the purgatory completes when the future does. Without this, one slow object-store read would consume an num.io.threads slot for its full latency.

RemoteIndexCache caches remote offset/time/txn indexes on local disk (LRU, sized by remote.log.index.file.cache.total.size.bytes) so a remote fetch doesn't re-download the index.

The honest performance picture: remote reads are ~100 ms p50 against S3 vs. ~1 ms from page cache, and they are not zero-copy. Tiered storage is for retention economics and for backfill readers, not for latency-sensitive consumers. Design your consumer groups so that lagging consumers are the ones hitting remote.

6. Hierarchical timing wheels and the purgatory

server-common/src/main/java/org/apache/kafka/server/util/timer/TimingWheel.java is one of the cleanest pieces of code in the tree, and the comment is a small paper.

The problem: hundreds of thousands of concurrent timeouts (every delayed produce, delayed fetch, delayed join, heartbeat expiry), and the overwhelming majority are cancelled before firing. A DelayQueue or ScheduledThreadPoolExecutor gives you O(log n) insert and O(log n) delete. When 99% of your operations are insert-then-delete, that's the wrong shape.

A simple timing wheel is a circular array of n buckets each covering u time units:

A timing wheel has O(1) cost for insert/delete (start-timer/stop-timer) whereas priority queue based timers [...] have O(log n) insert/delete cost.

The drawback is bounded range: n * u. The fix is hierarchy — level k+1 has resolution n times coarser:

level    buckets
1        [c,c]   [c+1,c+1]  [c+2,c+2]
2        [c,c+2] [c+3,c+5]  [c+6,c+8]
3        [c,c+8] [c+9,c+17] [c+18,c+26]

Overflow delegates upward; when a higher bucket expires, its tasks are reinserted and cascade down to finer wheels. Insert is O(m) where m = number of levels (tiny), delete is O(1).

The O(1) delete is the crux, and it comes from TimerTaskList being a doubly-linked list where the TimerTaskEntry is held by the TimerTask itself. Cancelling is entry.remove() — unlink two pointers. No search.

Note the overlap the comment calls out:

bucket [c,c+2] in level 2 won't receive any task since that range is already covered in level 1. [...] This is a bit wasteful, but simplifies the implementation.

A maintainer accepting a small constant-factor waste for a large simplicity win, and documenting it. More code should do this.

How the driving thread works. The wheels themselves don't have a thread. SystemTimer holds a DelayQueue<TimerTaskList> of buckets, not tasks. So the JDK's DelayQueue — with its O(log n) ops — is used over the number of non-empty buckets, which is small and bounded, while the number of tasks is unbounded. This is the trick: use the expensive structure over the cheap dimension.

SystemTimer.advanceClock polls the bucket queue, and an "expiring timer" thread (ExpirationReaper per purgatory) drives it.

The purgatory (DelayedOperationPurgatory) layers a watcher-list index on top:

public <K extends DelayedOperationKey> boolean tryCompleteElseWatch(T operation, List<K> watchKeys) {
    if (operation.safeTryCompleteOrElse(() -> {
        watchKeys.forEach(key -> { if (!operation.isCompleted()) watchForOperation(key, operation); });
        if (!watchKeys.isEmpty()) estimatedTotalOperations.incrementAndGet();
    })) return true;
    if (!operation.isCompleted()) {
        if (timerEnabled) timeoutTimer.add(operation);
        if (operation.isCompleted()) operation.cancel();
    }
    return false;
}

The double-check (try, then watch, then try again under the operation's lock) is the standard "register before re-checking" pattern that avoids missing a concurrent trigger. The comment then enumerates a real deadlock they hit:

1. thread_a holds readlock of stateLock from TransactionStateManager
2. thread_a is executing tryCompleteElseWatch()
3. thread_a adds op to watch list
4. thread_b requires writelock of stateLock (blocked by thread_a)
5. thread_c calls checkAndComplete() and holds lock of op
6. thread_c is waiting readlock of stateLock (blocked by thread_b)
7. thread_a is waiting lock of op (blocked by thread_c)

...and then admits the current fix doesn't eliminate the class, only this instance, and states the convention that actually keeps it safe:

we recommend DelayedOperationPurgatory.checkAndComplete() be called without holding any exclusive lock.

An invariant maintained by convention and comment rather than by construction. Worth knowing if you touch this code.

Reaper / purge. Completed operations stay in watcher lists until purged. purgeInterval (producer.purgatory.purge.interval.requests, default 1000) controls when a scan reclaims them. estimatedTotalOperations vs. actual watched() is the signal. Symptom of getting this wrong: purgatory size metrics climbing without bound while actual pending work is small.

7. Replication

7.1 Pull replication, and why

Followers fetch. There is no push. ReplicaFetcherThread extends AbstractFetcherThread issues FetchRequest to the leader with replicaId set, exactly like a consumer but with privileges (reads above the HW, gets a privileged fetch session, gets OffsetForLeaderEpoch).

Consequences, all of which you inherit if you copy this:

• The leader has no per-follower send queue. No unbounded buffering, no head-of-line blocking from a slow follower. A slow follower just falls behind and eventually leaves the ISR.
• The replication path is the consumer path. Same FetchRequest, same purgatory, same sendfile. One code path to optimize. Fewer bugs.
• The HW lags by one round trip (§7.2). This is the price.
• Adding a replica is trivial — it's just a new fetcher. Compare to push-based systems where the leader must track and manage each replica's stream.

AbstractFetcherManager partitions the work: num.replica.fetchers threads per source broker, partitions hashed across them. A broker with 4,000 partitions replicating from 10 leaders and num.replica.fetchers=4 has 40 fetcher threads, each multiplexing ~100 partitions into one incremental fetch session.

7.2 The high watermark, and its one-round-trip lag

Partition.maybeIncrementLeaderHW:

private def maybeIncrementLeaderHW(leaderLog: UnifiedLog, currentTimeMs: Long = time.milliseconds): Boolean = {
  if (isUnderMinIsr) {
    trace(s"Not increasing HWM because partition is under min ISR(ISR=${partitionState.isr})")
    return false
  }
  val leaderLogEndOffset = leaderLog.logEndOffsetMetadata
  var newHighWatermark = leaderLogEndOffset
  remoteReplicasMap.forEach { (_, replica) =>
    val replicaState = replica.stateSnapshot
    def shouldWaitForReplicaToJoinIsr: Boolean =
      replicaState.isCaughtUp(leaderLogEndOffset.messageOffset, currentTimeMs, replicaLagTimeMaxMs) &&
      isReplicaIsrEligible(replica.brokerId)
    if (replicaState.logEndOffsetMetadata.messageOffset < newHighWatermark.messageOffset &&
        (partitionState.maximalIsr.contains(replica.brokerId) || shouldWaitForReplicaToJoinIsr)) {
      newHighWatermark = replicaState.logEndOffsetMetadata
    }
  }
  leaderLog.maybeIncrementHighWatermark(newHighWatermark) match { ... }
}

Three things:

1. isUnderMinIsr short-circuits. If the ISR is below min.insync.replicas, the HW does not advance at all — even for data that is replicated to everyone currently in the ISR. This is what makes acks=all + min.insync.replicas=2 actually mean something rather than degrading to acks=1 when the ISR shrinks to one.
2. shouldWaitForReplicaToJoinIsr holds the HW back for a replica that's caught up but not yet in the ISR. Without it, the HW could advance past a point, then the catching-up replica joins the ISR, and you'd have an ISR member behind the HW — which breaks the leader-election invariant.
3. The comment marker "using the maximal" — see §7.3.

The lag: the leader learns follower LEO k from a fetch at fetchOffset = k. It then advances HW to k. Followers learn the new HW from the next fetch response. So a follower's HW trails the leader's by one fetch round trip. This is why:

• On leader failover, the new leader truncates to its HW, which may be behind — and this is why KIP-101 leader epochs were needed to avoid data loss/divergence during that truncation.
• log.flush and consumer visibility are both bounded by this, and no amount of tuning removes it.

If you're designing this: a push-based system (Raft AppendEntries) can commit in one round trip because the leader knows immediately that a follower accepted. Kafka trades one RTT of commit latency for a vastly simpler and more uniform replication path. Whether that's the right trade depends on whether your commit latency budget is ~5 ms or ~500 µs.

7.3 ISR: expand, shrink, maximal ISR

Expand (maybeExpandIsr, triggered by a follower fetch):

private def isFollowerInSync(followerReplica: Replica): Boolean = {
  ...
  followerEndOffset >= leaderLog.highWatermark && leaderEpochStartOffsetOpt.exists(followerEndOffset >= _)
}

Two conditions, and the second is the subtle one: the follower must be caught up to the current leader epoch's start offset, not just the HW. Otherwise a follower could join the ISR while still holding records from a previous, diverged epoch.

Shrink (maybeShrinkIsr, from a scheduled task): a follower is out of sync if it hasn't fetched up to the leader's LEO within replica.lag.time.max.ms (default 30s). Note this is purely time-based — the old replica.lag.max.messages was removed years ago because a message-count threshold produces ISR flapping under bursty load.

Both go through the controller. The leader sends AlterPartitionRequest; the controller validates (leader epoch, partition epoch) and writes a PartitionChangeRecord to the metadata log. Only when that's committed and propagated back does the leader's partitionState become CommittedPartitionState again.

maximalIsr exists because of the window in between. When PendingExpandIsr is active:

isr        = {1, 2}          # what the controller has committed
maximalIsr = {1, 2, 3}       # what we've proposed

For HW advancement, the leader uses maximalIsr — pessimistic, waits for replica 3 too. For min.insync.replicas checks it uses the committed isr — pessimistic in the other direction. Both choices are the conservative one, and that's the point: during the uncertainty window, assume whichever set makes you safer for the property in question.

PendingShrinkIsr is symmetric: HW advancement still waits for the replicas you're trying to remove until the controller confirms the removal. If it didn't, you could advance the HW past data that the about-to-be-removed replica has but the survivors don't — and then fail over to a survivor.

7.4 Leader epochs and log reconciliation

This is KIP-101, and it's the mechanism that lets Kafka use pull replication without divergence.

leader-epoch-checkpoint maps epoch → start offset. On becoming a follower, AbstractFetcherThread puts the partition in Truncating state and runs:

1. For each truncating partition, take its latest (epoch, LEO).
2. Send OffsetForLeaderEpochRequest(epoch) to the leader.
   (Or, on modern versions, the leader piggybacks `divergingEpoch` on the FetchResponse —
    see truncateOnFetchResponse.)
3. Leader responds with the end offset of that epoch in ITS log.
4. Follower truncates to min(leaderEndOffsetForEpoch, ownLEO).
5. Repeat with the next-lower epoch if needed.

The key insight: the epoch boundary tells you exactly where two logs can diverge. If the leader says "epoch 5 ended at offset 1000" and you have records at offset 1200 in epoch 5, those 200 records were never committed and must go. You don't need to compare record contents; you don't need to truncate blindly to the HW.

truncateToHighWatermark still exists as the fallback for logs with no epoch information (mixed format, pre-KIP-101 data). It's marked as the unsafe path.

The modern optimization (truncateOnFetchResponse) piggybacks divergingEpoch on the fetch response, so the common case needs no extra RPC at all:

.setLeaderEpoch(partitionData.divergingEpoch.epoch)
.setEndOffset(partitionData.divergingEpoch.endOffset)

Design lesson: if your replication protocol truncates, you need a ratchet that identifies the divergence point without content comparison. Raft uses (prevLogIndex, prevLogTerm) on every AppendEntries. Kafka uses a persisted epoch→offset map queried on demand. Both work; Kafka's version has the advantage of being queryable in bulk for thousands of partitions in one RPC.

7.5 Eligible Leader Replicas (KIP-966)

The pre-ELR world had exactly two options when all ISR members are down:

• unclean.leader.election.enable=false: partition unavailable until an ISR member returns.
• unclean.leader.election.enable=true: elect anyone, silently lose data.

ELR adds a third. PartitionRegistration gains elr[] and lastKnownElr[]. When a replica leaves the ISR because its broker shut down or was fenced — not because it fell behind — it goes into the ELR. An ELR member is known to have had all committed data at the moment it left. So:

if (isValidNewLeader(preferredReplica)) return new ElectionResult(preferredReplica, false);
if (isValidNewLeader(partition.leader))  return ...
// then: any ISR member
// then: any ELR member   ← new, and still a CLEAN election
// then (only if unclean enabled): any live replica

PartitionChangeBuilder maintains it, gated on eligibleLeaderReplicasEnabled (a MetadataVersion feature, IBP_4_0_IV1+ with elr.version). BrokersToElrs is the controller-side reverse index (broker → partitions where it's in the ELR), so that when a broker comes back the controller can immediately find the partitions it can rescue.

lastKnownElr handles the fully-cold-cluster case: if ISR and ELR are both empty, the controller can still elect the last known ELR member — but only if there's exactly one, and only under useLastKnownLeaderInBalancedRecovery:

if (partition.lastKnownElr.length != 1) {
    log.trace("Try to elect last known leader for {}-{} but lastKnownElr does not only have 1 member...");

More than one candidate means you can't tell which had more data, so it refuses.

This is a genuinely good piece of distributed systems design and it's underappreciated. The insight is that "left the ISR" conflates two very different events — fell behind (may be missing data) and went away (had everything up to the moment it went away) — and that distinguishing them recovers availability with no safety loss.

8. KRaft

ZooKeeper is gone — removed entirely in 4.0. KafkaRaftServer starts a ControllerServer, a BrokerServer, or both (combined mode), sharing a SharedServer that owns the KafkaRaftClient.

8.1 How it differs from textbook Raft

The class comment is explicit and worth quoting in full:

This class implements a Kafkaesque version of the Raft protocol. Leader election is more or less pure Raft, but replication is driven by replica fetching and we use Kafka's log reconciliation protocol to truncate the log to a common point following each leader election.

The API set:

The comment explains why BeginQuorumEpoch exists at all:

This is not needed in usual Raft because the leader can use an empty data push to achieve the same purpose. The Kafka Raft implementation, however, is driven by fetch requests from followers, so there must be a way to find the new leader after an election has completed.

That's the fundamental tension of pull-based consensus: the followers don't know who to pull from until someone tells them. BeginQuorumEpoch is retried indefinitely per voter until acknowledged.

Similarly, truncation detection is piggybacked on Fetch rather than being a separate protocol state, matching the partition replication design.

Observers vs. voters. Brokers are observers of __cluster_metadata: they fetch, they never vote, they never become leader. Controllers are voters. This is the same replicaId-based distinction as partition replication, and it means adding a broker doesn't touch the quorum.

MAX_BATCH_SIZE_BYTES = 8 * 1024 * 1024, MAX_FETCH_WAIT_MS = 500, MAX_NUMBER_OF_BATCHES = 10.

8.2 The quorum state machine, including Prospective

QuorumState.java's comment is the authoritative state diagram:

Resigned →     Unattached (higher epoch, or election timeout)
               Follower   (discovered leader with larger epoch)

Unattached →   Unattached (higher epoch, or after giving a binding vote)
               Prospective (election timeout)
               Follower   (discovered leader, equal or larger epoch)

Prospective →  Unattached  (higher epoch; or no last known leader and lost/timed out)
               Candidate   (majority of PreVotes granted)
               Follower    (larger epoch; or had a last known leader and lost/timed out)

Candidate →    Unattached  (higher epoch)
               Prospective (election timeout or loss)
               Leader      (majority of votes)

Leader →       Unattached  (higher epoch)
               Resigned    (graceful shutdown)
               Follower    (larger epoch)

Follower →     Unattached  (higher epoch)
               Prospective (fetch timeout)
               Follower    (larger epoch)

Prospective is the pre-vote state (KIP-996) and it's the most important addition to KRaft's election protocol. ProspectiveState's javadoc:

1. Once started, it will send prevote requests and keep record of the received vote responses
2. If it receives a message denoting a leader with a higher epoch, it will transition to follower
3. If majority votes granted, it will transition to candidate state
4. If majority votes rejected or election times out, it will transition to unattached or follower depending on if it knows the leader id and endpoints or not

The problem pre-vote solves: a partitioned node's election timer fires repeatedly. Each time, it bumps its epoch and campaigns. When the partition heals, its high epoch forces the healthy leader to step down — even though the partitioned node was never a viable leader and has a stale log. In a metadata quorum, that means controller churn and a metadata write stall for no reason.

Pre-vote: campaign without bumping the epoch. Ask "would you vote for me?" Voters answer based on log up-to-dateness and on whether they currently have a healthy leader. Only on a majority of yeses do you bump the epoch and run a real election. canGrantVote(replicaKey, isLogUpToDate, isPreVote) carries the flag through.

Note also the transition rule that a prospective can re-enter Unattached in the same epoch:

if (epoch < currentEpoch || (epoch == currentEpoch && !isProspective())) {
    throw new IllegalStateException(...);
}

Same-epoch backward transitions are normally illegal in Raft; they're legal here specifically because pre-vote didn't bump the epoch, so no state was published.

Complementary is checkQuorum on the leader side (LeaderState):

int majority = (voterStates.size() / 2) + 1;
if (!voterStates.containsKey(localReplicaKey)) majority = majority - 1;
if (fetchedVoters.size() >= majority) { ...reset timer... }

Did not receive fetch request from the majority of the voters within {}ms.

A leader that stops hearing from a majority resigns on its own, rather than waiting to be displaced. That closes the other half of the partitioned-leader problem.

8.3 Leader HW computation

LeaderState.updateHighWatermark:

// Find the largest offset which is replicated to a majority of replicas (the leader counts)
Optional<LogOffsetMetadata> highWatermarkUpdateOpt = followersByDescendingFetchOffset.get(indexOfHw).endOffset;

Sort replicas by fetch offset descending, take the element at the majority index. Standard Raft commit-index computation. Two guards:

if (highWatermarkUpdateOffset > epochStartOffset) { ... }

Raft's rule that a leader may not commit an entry from a previous term by counting replicas — it must commit something from its own term first. epochStartOffset is the enforcement point. And:

} else if (highWatermarkUpdateOffset < currentHighWatermarkMetadata.offset()) {
    log.info("The latest computed high watermark {} is smaller than the current value {}, ...");

HW is monotonic; a decrease means a bug and is logged loudly rather than applied.

The Optional<LogOffsetMetadata> (vs. a bare long) is again the physical-position optimization: the FetchSnapshot/Fetch responder needs the byte position of the HW.

8.4 Snapshots

__cluster_metadata cannot be compacted with the normal log cleaner — the records are deltas (PartitionChangeRecord), not key-value overwrites. So KRaft uses snapshots: a full serialized MetadataImage at (offset, epoch), written as 00000000000000012345-0000000042.checkpoint.

RecordsSnapshotWriter / RecordsSnapshotReader use the same FileRecords machinery as segments, so FetchSnapshot can sendfile too. UnalignedFileRecords exists because snapshot content isn't offset-aligned — the position→offset relationship that FileRecords assumes doesn't hold, so a distinct type prevents accidental misuse.

NotifyingRawSnapshotWriter fires a callback on completion so the log can advance its start offset and delete the now-redundant prefix.

Generation is triggered by metadata.log.max.record.bytes.between.snapshots (default 20 MB) or metadata.log.max.snapshot.interval.ms (default 1h).

The bootstrap snapshot (BOOTSTRAP_SNAPSHOT_ID, offset -1) is how kafka-storage format seeds initial FeatureLevelRecords before any log exists — the bootstrap.checkpoint file.

KRaftControlRecordStateMachine tracks control records embedded in the log (voter set changes, KRaftVersionRecord), and VoterSetHistory / TreeMapLogHistory keep the voter set as of any offset — necessary because a Vote request must be evaluated against the voter set that was current at the relevant offset, not the latest one. Dynamic quorum membership (KIP-853) is what requires this; AddVoterHandler / RemoveVoterHandler / UpdateVoterHandler implement the one-at-a-time membership change protocol.

8.5 QuorumController: a single-threaded event loop

metadata/src/main/java/org/apache/kafka/controller/QuorumController.java. This is the piece that most repays study if you're building a control plane.

Everything is an event on one queue. KafkaEventQueue, one thread. Every mutation is a ControllerWriteEvent:

class ControllerWriteEvent<T> implements EventQueue.Event, DeferredEvent {
    // run():
    //   1. verify still active controller (epoch check)
    //   2. call op.generateRecordsAndResult()  → ControllerResult<T>(records, response)
    //   3. raftClient.scheduleAtomicAppend(records)
    //   4. deferredEventQueue.add(resultAndOffset.offset(), this)   ← does NOT complete the future
    // and later, when the offset is committed:
    //   deferredEventQueue.completeUpTo(offsetControl.lastStableOffset());
}

The design properties this buys:

1. No locks anywhere in the control managers. ReplicationControlManager, ClusterControlManager, ConfigurationControlManager, FeatureControlManager are all single-threaded-by-construction. Read their code — there is not a synchronized or a ConcurrentHashMap in the state. That's an enormous simplification for logic this intricate.
2. Deterministic replay. The controller's state is exactly fold(replay, records). A standby controller applying the same records reaches the same state. This is testable — and test-common/ has harnesses that do exactly that.
3. Responses are deferred until commit. The client's CreateTopicsResponse doesn't arrive until the TopicRecord is committed to a majority of the quorum. No dirty reads of uncommitted controller state ever escape.
4. Snapshottable state. The managers' state lives in TimelineHashMap / TimelineHashSet (server-common/.../timeline/) — persistent data structures with epoch-tagged versions, so the controller can serve reads at a past offset and can revert state if a write is not committed (leadership loss). This is the mechanism that makes "generate records, respond later" safe: if the append fails, the in-memory state is rolled back to the last committed offset.

ControllerOperationFlag carries per-operation policy (e.g. DOES_NOT_UPDATE_QUEUE_TIME for periodic tasks, RUNS_IN_PREMIGRATION).

EventPerformanceMonitor logs slow events. On a controller managing a million partitions, a single event that takes 500 ms stalls all metadata mutation. The monitor exists because that's the dominant failure mode of a single-threaded design and you need it visible.

PeriodicTaskControlManager schedules background work (ELR cleanup, expired-token removal, partition-leader balancing) as events on the same queue, so background work is serialized with foreground work and can't race it.

ActivationRecordsGenerator produces the records written on becoming active controller — a tricky bit of code that handles bootstrap, MetadataVersion upgrades detected at activation, and migration-era leftovers.

Steal all of this. The pattern — single-threaded deterministic state machine, replicated log for durability, deferred completion at commit, persistent data structures for rollback — is the single highest-leverage design in the Kafka codebase. It converts a nightmarishly concurrent problem (cluster metadata mutation) into sequential code that reads like a textbook.

The cost is honest too: one core, and a stall anywhere stalls everything. Kafka's answer is aggressive monitoring plus keeping the per-event work small. If your control plane has genuinely CPU-heavy operations, you need a different answer (batching, or sharding the state machine).

8.6 MetadataImage / MetadataDelta / MetadataLoader

MetadataImage   — immutable snapshot of all cluster metadata at an offset
MetadataDelta   — a mutable builder holding changes since an image
MetadataLoader  — reads the raft log, builds deltas, publishes images
MetadataPublisher — consumers of images/deltas (ReplicaManager, coordinators, quota managers, ...)

public void replay(ApiMessage record) { /* dispatch by record type */ }
public void replay(TopicRecord record)           { getOrCreateTopicsDelta().replay(record); }
public void replay(PartitionChangeRecord record) { getOrCreateTopicsDelta().replay(record); }
public void replay(FeatureLevelRecord record)    { ... }
public void replay(ClearElrRecord record)        { ... }
...

Lazy sub-delta creation (if (topicsDelta == null) topicsDelta = new TopicsDelta(image.topics())) means a batch that only touches configs allocates nothing in the topics dimension. With a million partitions, that's the difference between a metadata batch costing microseconds and costing a full-image copy.

MetadataBatchLoader accumulates records until a batch boundary before publishing — publishers see transactionally-consistent images, never a half-applied batch.

TopicsDelta.localChanges(brokerId) produces a LocalReplicaChanges — exactly the set of leader/follower/delete transitions this broker must perform. ReplicaManager.applyDelta consumes it. This replaces the ZooKeeper-era LeaderAndIsrRequest broadcast entirely: instead of the controller computing and sending per-broker instructions, each broker derives its own instructions from the shared log. That's a fundamental architectural improvement — the controller no longer needs to know what each broker has already processed.

Failure mode this eliminated: in the ZK world, a broker that missed a LeaderAndIsrRequest had stale state and the controller had to detect and resend. In KRaft, a broker that's behind is simply behind in the log, and catches up by fetching. Divergence is impossible by construction.

8.7 Feature flags and MetadataVersion

server-common/src/main/java/org/apache/kafka/server/common/MetadataVersion.java:

IBP_4_0_IV1(23, "4.0", "IV1", true),
IBP_4_0_IV2(24, "4.0", "IV2", false),
IBP_4_0_IV3(25, "4.0", "IV3", false),
IBP_4_1_IV0(26, "4.1", "IV0", false),
IBP_4_1_IV1(27, "4.1", "IV1", false),
IBP_4_2_IV0(28, "4.2", "IV0", false),
IBP_4_2_IV1(29, "4.2", "IV1", false),
IBP_4_3_IV0(30, "4.3", "IV0", true),
IBP_4_4_IV0(31, "4.4", "IV0", false),   // dead-letter queue for share groups (KIP-1191)
IBP_4_4_IV1(32, "4.4", "IV1", true),
IBP_4_4_IV2(33, "4.4", "IV2", true);

public static final MetadataVersion LATEST_PRODUCTION = IBP_4_3_IV0;

The boolean is didMetadataChange — whether the version introduced new metadata record types or versions, which determines whether a downgrade is possible. Versions above LATEST_PRODUCTION are "testing" and require unstable.metadata.versions.enable.

Capability checks read as predicates on the version:

public boolean isElrSupported()        { return this.isAtLeast(IBP_4_0_IV1); }
public boolean isShareGroupDLQSupported() { return this.isAtLeast(IBP_4_4_IV1); }

Beyond metadata.version, there are independent features (kraft.version, transaction.version, group.version, eligible.leader.replicas.version, share.version, streams.version) each with their own level, stored as FeatureLevelRecords and managed by FeatureControlManager. QuorumFeatures and ClusterFeatureSupportDescriber compute the max level the whole cluster supports, so a feature can't be enabled above what the oldest node understands.

This is how you do rolling upgrades in a replicated-log system: the log is the source of truth for what's enabled, the enabling record is itself in the log, and every node's behaviour is a pure function of the log prefix it has applied. There's no "wait for everyone to restart" step and no distributed agreement problem separate from the log.

9. Coordinators

9.1 The coordinator runtime

coordinator-common/src/main/java/org/apache/kafka/coordinator/common/runtime/ — CoordinatorRuntime is a generic framework, and the group, share, and (in progress) transaction coordinators are all instances of it. It is essentially QuorumController's design applied to a partitioned state machine.

CoordinatorRuntime<S extends CoordinatorShard<U>, U>
  ├─ one CoordinatorShard per partition of the backing internal topic
  ├─ CoordinatorEventProcessor — striped executor, events for a shard are serialized
  ├─ coordinator writes produce records → appended to __consumer_offsets / __share_group_state
  └─ responses deferred until the append is committed (HW advances past it)

The properties mirror the controller: single-threaded per shard (so GroupMetadataManager has no locks), deterministic replay from the log, and responses that don't escape before durability.

The difference is sharding — 50 partitions of __consumer_offsets by default means 50 independent state machines and 50 threads' worth of parallelism, which is what lets one broker coordinate tens of thousands of groups.

CoordinatorLoader replays a partition's records into a shard on becoming leader for it. SnapshotRegistry + timeline collections again provide the rollback-on-uncommitted-write property.

9.2 Group coordinator: KIP-848

The old protocol (JoinGroup/SyncGroup, "classic") had a structural problem: the assignment was computed by an elected group leader — a client. That produced:

• Stop-the-world rebalances. Every member revokes everything, rejoins, waits for the leader to compute, gets a new assignment. A 500-member group with a 100 ms assignor takes seconds of total unavailability.
• Client-side assignor code that the broker couldn't validate or version.
• session.timeout.ms / max.poll.interval.ms coupling that made a slow processing loop look like a dead member.

KIP-848 moves assignment server-side and makes reconciliation incremental and per-member. The protocol is a single RPC:

ConsumerGroupHeartbeat(groupId, memberId, memberEpoch, subscribedTopicNames|regex,
                       rebalanceTimeoutMs, topicPartitions[ownedPartitions])
  → ConsumerGroupHeartbeatResponse(memberEpoch, heartbeatIntervalMs, assignment)

That's it. No join, no sync, no leader. ConsumerGroupHeartbeatRequest carries the member's owned partitions; the response carries its target. The state machine in between does the rest.

The coordinator maintains:

• Group epoch — bumped on any subscription/membership/metadata change.
• Target assignment — computed by a server-side assignor when the group epoch changes, stored as ConsumerGroupTargetAssignmentMemberRecords. Has its own epoch.
• Per-member current assignment — reconciled toward the target, one member at a time, independently.

ConsumerGroupHeartbeat also carries subscribedTopicRegex — server-side regex subscription (ResolvedRegularExpression records), which removes the old requirement that every member have metadata for every topic in order to evaluate the pattern consistently.

9.3 The reconciliation state machine

group-coordinator/.../modern/consumer/CurrentAssignmentBuilder.java:

The CurrentAssignmentBuilder class encapsulates the reconciliation engine of the consumer group protocol. Given the current state of a member and a desired or target assignment state, the state machine takes the necessary steps to converge them.

Three member states (modern/MemberState.java):

STABLE               // fully reconciled with the target assignment
UNREVOKED_PARTITIONS // must revoke some partitions before advancing epoch
UNRELEASED_PARTITIONS// advanced epoch, waiting on partitions not yet revoked by previous owners
UNKNOWN              // forward-compat: a state this version doesn't know

build():

case STABLE:
    if (member.memberEpoch() != targetAssignmentEpoch) return computeNextAssignment(...);
    else if (hasSubscriptionChanged) return updateCurrentAssignment(...);
    else return member;

case UNREVOKED_PARTITIONS:
    // revocation is confirmed by ABSENCE from the heartbeat's owned-partitions list
    if (ownsRevokedPartitions(member.partitionsPendingRevocation())) {
        if (hasSubscriptionChanged) return updateCurrentAssignment(...);
        else return member;                      // still waiting — no progress
    }
    return computeNextAssignment(...);

case UNRELEASED_PARTITIONS:
    return computeNextAssignment(...);           // pick up partitions as they free up

case UNKNOWN:
    if (ownedTopicPartitions == null || !ownedTopicPartitions.isEmpty())
        throw new FencedMemberEpochException("The consumer group member is in a unknown state. "
            + "The member must abandon all its partitions and rejoin.");
    return computeNextAssignment(targetAssignmentEpoch, member.assignedPartitions());

Three details worth extracting:

Revocation is proven by omission. The coordinator never asks "did you revoke?" — it observes that the partition stopped appearing in ownedTopicPartitions. That's a level-triggered protocol, not edge-triggered: a lost heartbeat costs you a round trip, not correctness. Enormously more robust than an ack-based revoke.

currentPartitionEpoch is the safety interlock.

/**
 * A function which returns the current epoch of a topic-partition or -1 if the
 * topic-partition is not assigned. The current epoch is the epoch of the current owner.
 */
private BiFunction<Uuid, Integer, Integer> currentPartitionEpoch;

A member can only be given a partition once the previous owner's epoch shows it has released it. UNRELEASED_PARTITIONS is precisely "I've moved to the new epoch, but partition X is still owned by someone at an older epoch." This is the mechanism that makes the whole thing safe without a global barrier: instead of "everyone stops, then everyone starts," it's a per-partition handoff with an epoch-based lock.

The UNKNOWN case is a forward-compatibility fence. A coordinator downgrade encountering a member state written by a newer version can't reason about it, so it forcibly resets the member. Failing safe rather than guessing. Note it only throws if the member claims partitions — a member with nothing to lose is just re-reconciled from scratch.

9.4 Assignors

group-coordinator/.../assignor/:

The homogeneous/heterogeneous split is a real optimization: homogeneous lets you treat the assignment as balancing P partitions over M members with a stickiness bias, which is near-linear. Heterogeneous is a bipartite matching problem.

TopicIds and RangeSet exist to avoid materializing partition lists. A topic with 10,000 partitions is a RangeSet(0, 10000), not a HashSet of 10,000 Integers. UnionSet avoids copying when merging subscriptions. On a coordinator handling large groups these allocation-avoidance types dominate the profile.

TargetAssignmentBuilder computes the new target and diffs it against the old, emitting records only for members whose assignment changed — so a group of 1,000 where one member joins writes ~2 records, not 1,000.

Server-side assignment also means group.consumer.assignors is a broker config with a broker plugin interface. You can now ship a custom assignor without redeploying every consumer. That's the practical win people underrate.

9.5 Transaction coordinator and KIP-890

TransactionState (transaction-coordinator/.../TransactionState.java):

EMPTY           → Ongoing (AddPartitionsToTxn / AddOffsetsToTxn)
                → PrepareAbort (EndTxn abort, TV2 only)
ONGOING         → PrepareCommit (EndTxn commit) | PrepareAbort (EndTxn abort)
PREPARE_COMMIT  → CompleteCommit (all markers acked)
PREPARE_ABORT   → CompleteAbort  (all markers acked)
COMPLETE_COMMIT / COMPLETE_ABORT  → (evicted from cache)
DEAD            → transactionalId expired
PREPARE_EPOCH_FENCE → mid epoch bump, fencing older producers

State lives in __transaction_state (compacted, 50 partitions). The TransactionStateManager + TransactionCoordinator (still Scala in core/src/main/scala/kafka/coordinator/transaction/) own it. TxnMarkerQueue / TransactionMarkerChannelManager drive WriteTxnMarkers to every partition that participated.

Commit is two-phase:

1. Write PREPARE_COMMIT to __transaction_state, durably. (Now the outcome is decided.)
2. Send WriteTxnMarkers to every participating partition leader. Each appends a control batch (attributes bit 5) at the end of the partition, which advances that partition's LSO past the transaction's records.
3. When all markers are acked, write COMPLETE_COMMIT.

A coordinator crash between 1 and 3 is recovered by replaying __transaction_state and re-sending markers. Idempotent because a duplicate marker for an already-completed txn is a no-op.

KIP-890 (transaction version 2) fixes a genuine hanging-transaction bug class. In TV1, the producer's epoch was bumped only on InitProducerId, so a zombie producer that had been partitioned could still have an in-flight Produce land after its transaction was aborted — writing a record into a transaction that no longer existed, hanging the LSO forever.

TV2 fixes it by:

• Bumping the producer epoch on every transaction completion. A zombie's epoch is stale immediately, so its produce is fenced.
• Removing the explicit AddPartitionsToTxn round trip from the client — the broker implicitly adds the partition on first write, and verifies with the coordinator via a broker-side AddPartitionsToTxn (the VerificationGuard you see threaded through UnifiedLog.append).

VerificationGuard is the object identity token proving that a given append was verified against the coordinator for the current transaction. VerificationGuard.SENTINEL means "not applicable."

And KIP-1228 adds epoch validation on markers themselves — hence transactionVersion reaching all the way down into UnifiedLog.append:

// @param transactionVersion the transaction version for the records (1 for TV1, 2 for TV2, etc.)
//                           Used for epoch validation of transaction markers (KIP-1228).

The fact that a wire-protocol feature version has to be plumbed into the storage layer's append method tells you something about how deeply transactions cut across this system.

9.6 Share groups (KIP-932)

The headline feature of the 4.x line: queue semantics on top of the log. Many consumers can read the same partition cooperatively, with per-record acknowledgement — the RabbitMQ/SQS model, without giving up the log.

core/src/main/java/kafka/server/share/SharePartition.java. Per-record state:

Map.of((byte) 0,                     RecordState.ARCHIVED,      // represents gap
       AcknowledgeType.ACCEPT.id,    RecordState.ACKNOWLEDGED,
       AcknowledgeType.RELEASE.id,   RecordState.AVAILABLE,
       AcknowledgeType.REJECT.id,    RecordState.ARCHIVED)

States: AVAILABLE → ACQUIRED (delivered, lock timer running) → ACKNOWLEDGED (accepted) | ARCHIVED (rejected or delivery-count exhausted) | back to AVAILABLE (released or lock timeout).

private final NavigableMap<Long, InFlightBatch> cachedState;  // ConcurrentSkipListMap
private long startOffset;   // SPSO — share-partition start offset
private long endOffset;

startOffset (the Share-Partition Start Offset) is the analogue of a committed consumer offset, but it can only advance past a contiguous run of terminal-state records. Everything between startOffset and endOffset is in the in-flight map.

Mechanics you need to know:

• ShareFetch acquires records and starts an acquisition lock (group.share.record.lock.duration.ms). Lock expiry returns records to AVAILABLE — this is the redelivery mechanism.
• deliveryCount per record. Exceeding group.share.delivery.count.limit archives the record. With KIP-1191 (IBP_4_4_IV1) it goes to a dead-letter queue topic instead of being silently dropped.
• State is durable. The ShareCoordinator persists ShareSnapshot/ShareUpdate records into __share_group_state. PersisterStateBatchCombiner merges overlapping offset ranges to keep the state compact — this is the piece that determines whether the design scales, since naively you'd store per-offset state.
• GapWindow / persisterReadResultGapWindow handles the reconstruction problem: after restart, records that were compacted or never had state must be treated as gaps, not as unacknowledged.

What you give up: ordering. A share group has no ordering guarantee within a partition, because records are acknowledged out of order by design. If you need ordering, use a consumer group. Also, this is materially more per-record broker-side state than a consumer group's single offset — deliveryCompleteCount tracking exists specifically to make lag computable without walking the map.

Why this matters strategically: it removes the main reason teams run both Kafka and a traditional queue. The work-queue use case (competing consumers, per-message ack, redelivery, DLQ) was the one thing Kafka structurally couldn't do. Now it can, at the cost of a coordinator that has to track per-record state.

10. Log compaction

storage/.../log/{LogCleaner, LogCleanerManager, Cleaner, SkimpyOffsetMap}.java.

Selection. LogCleanerManager.grabFilthiestCompactedLog:

List<LogToClean> cleanableLogs = dirtyLogs.stream()
    .filter(ltc -> (ltc.needCompactionNow() && ltc.cleanableBytes() > 0)
                   || ltc.cleanableRatio() > ltc.log().config().minCleanableRatio)
    ...
LogToClean filthiest = cleanableLogs.stream().max(Comparator.comparingDouble(LogToClean::cleanableRatio))

cleanableRatio = dirtyBytes / (dirtyBytes + cleanBytes), compared against min.cleanable.dirty.ratio (default 0.5). needCompactionNow handles max.compaction.lag.ms — a hard deadline that forces compaction regardless of ratio, which exists for GDPR-style delete guarantees:

long maxCompactionLagMs = Math.max(log.config().maxCompactionLagMs, 0L);
long cleanUntilTime = now - maxCompactionLagMs;

There's also min.compaction.lag.ms at the other end — a floor, so recently-written records survive long enough for consumers to see them at least once.

The two-pass algorithm.

Pass 1 — build the offset map. Cleaner.buildOffsetMap scans the dirty section and inserts key → latestOffset into a SkimpyOffsetMap.

Pass 2 — copy segments. For each record in the clean+dirty range, retain it iff offsetMap.get(key) <= record.offset (i.e., this is the latest version) and it isn't an expired tombstone. Write survivors to a .cleaned segment, group several old segments into one new one (since they've shrunk), then .swap, then rename.

SkimpyOffsetMap is the interesting part. It is deliberately, named-in-the-class lossy-ish:

public SkimpyOffsetMap(int memory, String hashAlgorithm) {
    this.digest = MessageDigest.getInstance(hashAlgorithm);   // default MD5
    this.hashSize = digest.getDigestLength();                 // 16 bytes
    this.bytesPerEntry = hashSize + 8;                        // 24 bytes: hash + offset
    this.slots = memory / bytesPerEntry;
}

It stores the MD5 hash of the key, not the key. 24 bytes per entry regardless of key length. Linear probing on collision:

// limit attempt to number of slots once positionOf(..) enters linear search mode
int maxAttempts = slots + hashSize - 4;

The design trade: a 128-bit hash collision would cause the cleaner to retain the wrong record for a key. The probability at any realistic key count is negligible (birthday bound on 2^128), and the payoff is a fixed 24 bytes per key with no key materialization. MD5 here is a hash, not a security primitive — its cryptographic weaknesses are irrelevant and it's fast with a JDK intrinsic.

Capacity math you will need in production:

keys_per_cleaner_pass = (log.cleaner.dedupe.buffer.size / log.cleaner.threads)
                        / 24 bytes × log.cleaner.io.buffer.load.factor

Default: 128 MB / 1 thread / 24 × 0.9 ≈ 5 million keys per pass. If a partition's dirty section has more distinct keys than that, the cleaner compacts only a prefix of the dirty section per pass. It still makes progress, but slowly, and max.compaction.lag.ms guarantees will be missed. Symptom: max-dirty-percent stuck high, __consumer_offsets growing. Fix: raise log.cleaner.dedupe.buffer.size and/or log.cleaner.threads.

Tombstone retention. A null-valued record must be retained long enough for every consumer to observe the delete, otherwise a consumer that was offline would rebuild state with the key still present. delete.retention.ms (24h) governs. The mechanism is the delete horizon (attributes bit 6): when the cleaner first processes a batch containing tombstones, it stamps BaseTimestamp with the horizon time and sets the bit. Subsequent passes remove tombstones past that horizon. Prior to this bit, the horizon was inferred from segment modification time, which was fragile.

What compaction cannot do: it is not a delete-by-predicate, not transactional, and does not compact the active segment. CleanedTransactionMetadata handles the interaction with transactions — aborted-transaction records can be dropped, but their markers must be retained until every record they abort is gone.

log.cleanup.policy=compact,delete applies both: retention deletes old segments and compaction dedupes what remains. This is what __consumer_offsets uses.

11. Producer client internals

clients/src/main/java/org/apache/kafka/clients/producer/internals/.

send() [user thread]
  → interceptors → serializers → partitioner
  → RecordAccumulator.append()            ← batching happens here
  ...
[Sender thread — one per producer]
  loop:
    accumulator.ready(cluster, now)       → which nodes have sendable data
    accumulator.drain(...)                → node → List<ProducerBatch>
    build ProduceRequest per node
    client.poll()                         → NetworkClient / Selector

RecordAccumulator — ConcurrentMap<String /*topic*/, TopicInfo>, each with ConcurrentMap<Integer, Deque<ProducerBatch>>. Locking is per-deque:

Deque<ProducerBatch> dq = topicInfo.batches.computeIfAbsent(effectivePartition, k -> new ArrayDeque<>());
synchronized (dq) {
    if (partitionChanged(topic, topicInfo, partitionInfo, dq, nowMs, cluster)) continue;
    RecordAppendResult appendResult = tryAppend(timestamp, key, value, headers, callbacks, dq, nowMs);
    if (appendResult.appended()) return updatePartitionInfoOnAppend(...);
}

Note the while (true) { ... continue; } retry loop: the partition is peeked before taking the deque lock (to avoid holding a lock across partition selection), so it must be re-validated after. Classic optimistic pattern.

BufferPool.allocate is called outside the deque lock, and can block up to max.block.ms. The comment is explicit about why time.milliseconds() is refreshed after:

// NOTE: getting time may be expensive, so calling it under a lock should be avoided.

BufferPool maintains a free list of exactly-batch.size buffers plus a non-pooled remainder. A record larger than batch.size gets its own oversized buffer that is not returned to the pool. Consistently oversized records therefore mean constant allocation — one reason batch.size should be ≥ your p99 record size.

BuiltInPartitioner — the sticky partitioner, and it is not what people think. It is not "round-robin per batch." From updatePartitionInfo:

int producedBytes = partitionInfo.producedBytes.addAndGet(appendedBytes);
...
if (producedBytes >= stickyBatchSize && enableSwitch || producedBytes >= stickyBatchSize * 2) {
    // switch partition
}

It sticks to a partition until stickyBatchSize bytes have been produced to it, then switches. The * 2 upper bound is a forced switch even when enableSwitch is false:

// between stickyBatchSize and stickyBatchSize * 2 bytes, to better align with batch boundary

enableSwitch is false while the deque has incomplete batches, so the switch aligns with a batch boundary rather than splitting one. And nextPartition is load-aware — it weights by partition queue depth so a slow broker gets less traffic, rather than uniform round-robin.

Delivery timeout. deliveryTimeoutMs is the total budget from send() to callback, covering accumulator time + all retries. nextBatchExpiryTimeMs caches the earliest expiry so the Sender's poll timeout can be set correctly instead of scanning every deque each loop.

Batch splitting. splitAndReenqueue handles RecordTooLargeException after compression: the producer estimated the compressed size, the broker rejected it, so split in half and retry. Sequences are reassigned:

// We treat the newly split batches as if they are not even tried.
// We should track the newly created batches since they already have assigned sequences.

Ordering under retry. insertInSequenceOrder maintains the invariant that batches with assigned sequences leave the deque in sequence order:

// Further, once batches are being retried, we are reduced to a single in flight request for that
// partition. So when the subsequent batches come back in sequence order, they will have to be
// placed further back in the queue.

This, plus max.in.flight.requests.per.connection <= 5, plus the broker's 5-batch producer state retention, is the complete ordering-under-retry story for the idempotent producer.

ChunkedRecordAccumulator / ChunkedProducerBatch are newer: instead of one contiguous batch.size buffer per batch, allocate chunks. Reduces waste when partitions are numerous and batches rarely fill.

TransactionManager — client-side transaction state machine, sequence number allocation, and the TxnPartitionMap of per-partition sequence/epoch state. It is also what enforces that you can't call send() outside beginTransaction() in transactional mode.

12. Consumer client internals

Two implementations behind ConsumerDelegate:

• ClassicKafkaConsumer — the original. User thread does everything; a HeartbeatThread runs alongside for the classic protocol. ConsumerCoordinator implements JoinGroup/SyncGroup.
• AsyncKafkaConsumer — the new one (KIP-945), default with the consumer protocol.

The async design:

[user thread]                     [ConsumerNetworkThread]
poll()                            loop:
  → ApplicationEventQueue  ────►     process application events
  ◄──── BackgroundEventQueue         requestManagers.poll(now) → NetworkClientDelegate
  ← FetchBuffer                      networkClientDelegate.poll()
                                     → completed fetches into FetchBuffer

RequestManager implementations, each owning one concern:

ConsumerNetworkThread.poll() calls each manager's poll(now), gets back PollResults (requests to send + a next-poll timeout), and hands them to NetworkClientDelegate.

Why this matters: in the classic consumer, poll() had to be called frequently or the member was evicted, because heartbeats rode on the user thread's poll loop (partly — the classic protocol did have a background heartbeat thread, but rebalance callbacks still ran on the user thread and blocked everything). In the async consumer, network activity is fully decoupled: a slow poll() loop affects max.poll.interval.ms only.

ConsumerMembershipManager is the client mirror of the coordinator's reconciliation state machine. It receives a target assignment, invokes ConsumerRebalanceListener callbacks via ConsumerRebalanceListenerInvoker (on the user thread, dispatched through the background event queue), and only reports the partition as revoked in the next heartbeat once onPartitionsRevoked has returned. That's what makes the coordinator's "revocation proven by omission" protocol correct.

FetchBuffer / FetchCollector — the network thread parks completed fetches in FetchBuffer; poll() on the user thread drains and deserializes via FetchCollector. Deserialization on the user thread is deliberate: it keeps user-supplied Deserializer code (which can be slow or can throw) off the network thread.

CompletedFetch is where READ_COMMITTED filtering happens — it holds the aborted-transaction priority queue and drops records from aborted producers as it iterates.

AbstractStickyAssignor is still there for classic-protocol groups: CooperativeStickyAssignor implements incremental cooperative rebalancing (KIP-429), the pre-848 mitigation. If you're on the new protocol you don't need it.

13. Quotas, throttling, and backpressure

Four independent quota types, three enforcement mechanisms.

Types: produce byte-rate, fetch byte-rate, request percentage (request_percentage — CPU time in network+IO threads), and controller mutation rate (create/delete topics, partition changes).

ClientQuotaManager (server/src/main/java/org/apache/kafka/server/quota/) uses the metrics library's Rate over N sample windows (quota.window.num = 11, quota.window.size.seconds = 1). When a Sensor.record() throws QuotaViolationException, throttle time is computed as: how long must we pause so that the observed rate falls back to the quota, given the current window's accumulated value.

Quota entities resolve hierarchically: (user, client-id) → (user) → (client-id) → <default>. Configured in __cluster_metadata via ClientQuotaRecord, applied through ClientQuotasDelta.

Enforcement:

1. throttleTimeMs in the response. The client is expected to pause. Well-behaved clients do.

2. Channel muting. The broker also mutes the connection for throttleTimeMs via ThrottledChannel and the purgatory. From SocketServer:

   Try unmuting the channel. If there was no quota violation and the channel has not been throttled, it will be unmuted immediately. If the channel has been throttled, it will be unmuted only if the throttling delay has already passed by now.

   This is the part that makes quotas actually enforceable against a misbehaving client — you don't need the client's cooperation.

3. unrecordQuotaSensor. A subtlety worth reading:

   For a throttled fetch, the broker should return an empty response and thus should not record the value. Ideally, we would like to compute the throttle time before actually recording the value, but the current Sensor code couples value recording and quota checking very tightly. As a workaround, we will unrecord the value for the fetch in case of throttling.

   A negative record to undo an accounting entry, because the API couples measurement and decision. This is the sort of thing you find in mature code, and the honest comment is worth more than a clean-looking abstraction would be.

Replication throttling is separate: leader.replication.throttled.rate / follower.replication.throttled.rate plus per-topic *.throttled.replicas lists (validated by ThrottledReplicaListValidator). Used during reassignments so rebalancing doesn't starve production traffic.

Backpressure layers, from outermost in:

1. TCP receive window  ← MemoryPool exhaustion stops selector reads
2. newConnections queue (20/processor) ← acceptor blocks, kernel backlog absorbs
3. requestQueue (queued.max.requests=500) ← processors block on sendRequest
4. Quotas ← channel mute + throttleTimeMs
5. Purgatory ← delayed ops don't hold IO threads

Layer 5 is the one people miss. A purgatory-based design means a request that's waiting costs a DelayedOperation object and a timing-wheel entry, not a thread. That's why 8 I/O threads can serve 100,000 in-flight acks=all produce requests.

14. Comparison with other streaming systems

14.1 Kafka vs. Amazon Kinesis Data Streams

The single biggest architectural difference: Kinesis has no consumer-side log abstraction — it has a shard iterator.

The deep differences, not the feature table:

1. Kafka's offset is a number; Kinesis's iterator is a capability. A Kafka consumer stores an int64 and can resume from it a week later. A Kinesis ShardIterator expires in 5 minutes, so the consumer must store a SequenceNumber and re-derive an iterator. That's an extra API call and a latency floor per restart, and it means Kinesis can move data around behind the abstraction — which is exactly what makes resharding possible without rewriting history. Kafka's offset stability is why partition count can't decrease.

2. The shard lineage tree is Kinesis's price for elastic scaling. When you reshard, the parent shard is sealed and children are created. Consumers must read the parent to SHARD_END before reading children, or ordering breaks. KCL handles this; hand-rolled consumers routinely get it wrong. Kafka's answer to elasticity is "over-partition up front," which pushes the cost to provisioning time rather than runtime. Neither is obviously better; they're different failure modes.

3. Fan-out economics are inverted. In Kafka, adding a consumer group is nearly free — same page cache, same sendfile, incremental network. In Kinesis, the shared 2 MB/s egress means the n-th consumer group degrades the others, so past ~2 groups you're buying Enhanced Fan-Out at $0.015/consumer-shard-hour plus $0.013/GB. At 100 shards and 5 consumers that's ~$550/month in EFO hours alone before data. This is the number that drives most Kinesis→Kafka migrations.

4. KPL aggregation is a protocol-level wart. Because a record is capped at 1 MB and billed per record, the KPL packs many user records into one Kinesis record using a protobuf envelope. This is a client library convention, not a service feature — so any consumer not using KCL/KPL sees protobuf blobs. Kafka made batching part of the wire format and the storage format, so every consumer benefits and no one has to know.

5. Exactly-once. Kinesis has no equivalent of the idempotent producer or transactions. Building EOS on Kinesis means an external dedup store keyed by a producer-supplied ID, checked on the consumer side. That's a real system you have to build, operate, and scale.

When Kinesis is genuinely the right call: low-to-moderate, predictable throughput; you're all-in on AWS; you value zero operational burden over cost and features; your consumers are Lambda (the integration really is excellent). When it isn't: high fan-out, high throughput, long retention, exactly-once, compaction, or any need for a protocol other than AWS's.

14.2 Kafka vs. Apache Pulsar

Pulsar's core architectural claim is separation of serving and storage: brokers are stateless, storage is BookKeeper.

Honest assessment: Pulsar's storage separation is the better architecture on paper and Kafka's single-system operation is the better architecture in practice. Pulsar's instant failover and zero-data-movement rebalancing are real advantages that Kafka cannot match without a rewrite. But you operate three distributed systems instead of one, and BookKeeper's failure modes (ledger recovery, auto-recovery, bookie decommissioning) are their own specialty.

Note the convergence: share groups are Kafka's answer to Shared subscriptions, tiered storage answered offloaders, and KRaft answered "why do I need ZooKeeper." The remaining structural gap is storage separation.

14.3 Kafka vs. Redpanda

Redpanda is a C++ reimplementation of the Kafka protocol on Seastar (thread-per-core, shared-nothing, DPDK-capable, io_uring).

• Same wire protocol — your clients don't change.
• Thread-per-core with no shared state, so no locks and no cross-core cache-line traffic. Kafka's per-partition synchronized (lock) becomes a core-local operation.
• Raft per partition rather than ISR. Every partition is its own Raft group. This gives real quorum commit semantics instead of ISR, and eliminates the "ISR shrank to 1, now acks=all means nothing" class of problem.
• No JVM — no GC pauses, and memory is explicitly managed rather than page-cache-dependent. Redpanda bypasses the page cache and manages its own.
• fsync by default, unlike Kafka. Their argument is that with Raft + fast NVMe you can afford it; Kafka's counter-argument is the IOPS bill.

Their published p99 advantages are real and largely attributable to the thread-per-core model and the absence of GC. The counter-arguments: a much smaller ecosystem, per-partition Raft has higher metadata overhead at very large partition counts, and you're betting on one vendor's implementation of a protocol whose spec is "whatever Apache Kafka does."

The interesting lesson for a maintainer: most of Redpanda's advantage comes from things Kafka could have (thread-per-core partitioning of work, per-partition consensus) but can't adopt now without breaking everything. Architecture is path-dependent.

14.4 Kafka vs. WarpStream / diskless (KIP-1150)

WarpStream (and Confluent Freight, and AutoMQ) implement the Kafka protocol with S3 as the only storage layer. No local disks, no inter-AZ replication traffic, stateless agents.

The economics: inter-AZ transfer for replication is often the largest line item in a cloud Kafka bill — three copies means 2× your ingest crosses AZ boundaries at ~$0.02/GB each way. Writing straight to S3 (which is already multi-AZ) eliminates it entirely.

The cost: latency. S3 PUT is ~50–200 ms, so produce latency goes from single-digit ms to hundreds of ms. These systems batch aggressively and target workloads where a 200–500 ms end-to-end latency is acceptable — which, honestly, is most analytics pipelines.

KIP-1150 ("diskless topics") brings this model into Apache Kafka itself as a per-topic option. This is the most consequential thing on Kafka's roadmap: it makes the storage model a topic-level choice rather than a cluster-level architecture decision. Latency-sensitive topics stay on local disks with ISR; high-volume log/telemetry topics go diskless and cost 5–10× less to run.

14.5 Quick positioning of the rest

• Azure Event Hubs — has a Kafka-protocol endpoint; underneath it's its own system. Throughput Units, 7-day max retention (90 with Premium/Dedicated), no compaction, no transactions. Same managed-service trade as Kinesis with better protocol compatibility.
• Google Pub/Sub — not a log at all. Per-message ack, no offsets, no replay by position (Seek by timestamp only), automatic scaling, no partitions to manage. Pub/Sub Lite was the partitioned Kafka-like variant; it was deprecated.
• NATS JetStream — dramatically simpler operationally, single binary, excellent for edge/IoT/request-reply. Consumers have both push and pull modes and per-message ack. Not designed for the multi-TB-per-day replayable-log use case.
• Apache RocketMQ — architecturally closest to Kafka; dominant in China. Notable for a single shared CommitLog per broker with per-topic index files, rather than per-partition files — which makes it much better at very high topic counts and worse at per-partition sequential read locality.
• Redis Streams — a log data type inside Redis. Consumer groups with per-message ack (XACK), pending-entries list, XAUTOCLAIM for redelivery. Memory-bound, so retention is small. Excellent for a work queue at the scale where you already run Redis.

15. Design lessons: building your own

If you're implementing a durable log — or borrowing pieces for something else — these are the ideas in Kafka worth taking, ranked by leverage.

15.1 Make the batch, not the record, your atom

Compression, checksum, idempotence identity, transactional membership, index granularity, and replication unit should all be the same object. Kafka's per-record cost is ~6–8 bytes of framing and essentially zero CPU because everything expensive happens once per batch. Systems that made the record the atom (per-message compression, per-message ack, per-message index entry) spend 10–100× more per unit of data and can never claw it back.

Corollary: expose the batch to the client. If the producer builds the batch and the broker stores it byte-identically, you get zero-copy on both sides. If the broker has to reframe, you've lost.

15.2 Put the checksum boundary between client-authored and server-authored fields

PartitionLeaderEpoch outside the CRC is worth its awkwardness many times over. Before you finalize a format, list every field and mark who writes it. Any server-written field inside a client-computed checksum is a full-payload recompute on your hottest path.

15.3 Sparse index + linear scan beats a dense index

8 bytes per 4 KB of log. 2 MB of index per 1 GB segment. Compare to a B-tree or an LSM's block index

• bloom filters + manifest. The linear scan from the index hint is 4 KB of sequential page-cache reads — cheaper than the extra index levels you'd traverse to avoid it. This works because the access pattern is "seek once, then stream," which is true of almost every log consumer.

15.4 Design your data structures around the page cache, not around big-O

The warm-section binary search (§3.6) is the canonical example: same complexity, but a probe set that doesn't drift. Ask of every mmapped structure: which pages does a typical operation touch, and does that set change as the structure grows? If it changes, you have a periodic latency cliff you haven't found yet.

15.5 Don't fsync; replicate — but say so out loud

Kafka's durability model is "N page caches" not "one disk." That's a defensible engineering choice with a precisely-statable failure mode (simultaneous power loss to min.insync.replicas nodes). Whatever you choose, state the failure mode in the docs in one sentence, because your users will assume the other one.

15.6 Use a hierarchical timing wheel for timeouts, and put the priority queue over buckets

O(1) insert and delete matters when 99% of timers are cancelled. And the DelayQueue<TimerTaskList> trick — expensive structure over the cheap dimension (buckets), cheap structure over the expensive dimension (tasks) — generalizes far beyond timers.

15.7 Delayed operations should cost an object, not a thread

The purgatory is why 8 I/O threads serve 100,000 in-flight requests. Any time you're tempted to block a worker thread on a condition that might be satisfied by another request, build a watcher-list + timer instead. The complexity is real (see the deadlock comment) but the alternative is a thread pool sized by your worst-case concurrency.

15.8 One event queue, deterministic replay, deferred completion

The QuorumController pattern (§8.5). If your control plane state is small enough to fit in memory and your mutation rate is low enough for one core:

mutation → single-threaded handler → (records, response)
        → append records to replicated log
        → hold response until the append commits
        → apply records to in-memory state on commit
        → persistent (timeline) data structures so uncommitted state can be reverted

You get: no locks, deterministic replay, testable state machines, no dirty reads, and standby replicas for free. The cost is one core and the need to keep per-event work small. I'd take this trade in almost every control plane I've seen.

15.9 Level-triggered protocols beat edge-triggered ones

KIP-848's revocation is confirmed by a partition's absence from the next heartbeat, not by a revoke-ack message. A lost message costs a round trip, not correctness. Same idea in KRaft: brokers derive their own leader/follower duties from the shared log rather than receiving instructions the controller must track delivery of.

Rule of thumb: if your protocol has a message whose loss requires retry-tracking on the sender, consider whether the receiver could instead just report its state and let the sender diff.

15.10 Distinguish "fell behind" from "went away"

ELR (§7.5). Conflating them cost Kafka a decade of unclean-election data loss. Any time you evict a member from a quorum/ISR/membership set, ask whether the eviction reason tells you something about what that member knows.

15.11 Push the version boundary into the log

MetadataVersion + FeatureLevelRecord: the record that enables a feature is itself in the replicated log, so every node's behaviour is a pure function of its log prefix. No separate agreement protocol, no "wait for all nodes to restart," and downgrade safety is a property you can compute (didMetadataChange).

15.12 Backpressure at every layer, and let TCP be the outermost one

Kafka's five layers (§13) all terminate in "stop reading from the socket," which closes the receive window, which blocks the producer's send(). That's the only backpressure mechanism that can't be ignored by a misbehaving client. Everything else — response-carried throttle times, queue bounds — is an optimization on top of it.

15.13 Write the post-mortem in the comment

AbstractIndex's page-fault analysis, DelayedOperationPurgatory's 7-step deadlock, FileRecords's "avoid calling lastOffset()," ClientQuotaManager's "unrecord as a workaround because the Sensor API couples recording and checking." These comments are why a new maintainer can be productive in this codebase. The value isn't the explanation of what the code does — it's the record of what was tried and why it failed.

16. Maintainer's appendix

16.1 Build and test

./gradlew clean jar -PscalaVersion=2.13          # build
./gradlew processMessages                        # regenerate protocol classes from JSON
./gradlew unitTest                               # unit only
./gradlew :core:test --tests kafka.log.LogManagerTest
./gradlew :storage:test --tests '*UnifiedLog*'
./gradlew checkstyleMain spotbugsMain            # style/static analysis — CI will reject you otherwise
./gradlew :jmh-benchmarks:jmh -PjmhArgs='RecordBatchIterationBenchmark'
./gradlew :core:integrationTest                  # slow

test-common/ holds ClusterTestExtensions — the JUnit 5 machinery for spinning up real KRaft clusters in-process. @ClusterTest(types = {Type.KRAFT}, brokers = 3) gives you a real cluster in a unit test. This is the single most useful thing in the repo for writing a credible patch.

api-checker/ enforces public API compatibility. If you change a signature in clients, it will tell you.

16.2 Adding an RPC field — the actual workflow

1. Edit clients/src/main/resources/common/message/XxxRequest.json / XxxResponse.json. Bump validVersions. Add the field with "versions": "N+".
2. ./gradlew processMessages.
3. Add an ApiKeys entry if it's a new API.
4. Gate on MetadataVersion (or a dedicated feature) if brokers must agree.
5. Handle it in KafkaApis (or ControllerApis).
6. Add to ApiVersionsResponse handling if version negotiation matters.
7. Tests: MessageTest round-trip, RequestResponseTest, and an integration test.

The JSON is the source of truth. Never hand-edit generated classes.

16.3 Metrics you should be able to read cold

16.4 Debugging on a live broker

# Dump a segment, including producer/txn state
kafka-dump-log.sh --files 00000000000000000000.log --print-data-log --deep-iteration

# Just the batch headers — much faster, shows offsets/epochs/producerId/sequences
kafka-dump-log.sh --files 00000000000000000000.log

# Indexes, with consistency verification against the log
kafka-dump-log.sh --files 00000000000000000000.index --index-sanity-check
kafka-dump-log.sh --files 00000000000000000000.timeindex
kafka-dump-log.sh --files 00000000000000000000.txnindex

# Producer state snapshot
kafka-dump-log.sh --files 00000000000000000000.snapshot

# The metadata log itself
kafka-dump-log.sh --cluster-metadata-decoder --files __cluster_metadata-0/*.log

# Interactive metadata browser
kafka-metadata-shell.sh --snapshot __cluster_metadata-0/*.checkpoint
  > ls /topics
  > cat /topics/orders/0/data

# Quorum health
kafka-metadata-quorum.sh --bootstrap-controller localhost:9093 describe --status
kafka-metadata-quorum.sh --bootstrap-controller localhost:9093 describe --replication

# Feature levels
kafka-features.sh --bootstrap-server localhost:9092 describe

# Hanging transaction hunting
kafka-transactions.sh --bootstrap-server localhost:9092 list
kafka-transactions.sh --bootstrap-server localhost:9092 find-hanging --broker-id 1
kafka-transactions.sh --bootstrap-server localhost:9092 abort --topic t --partition 0 --start-offset N

The one to internalize: find-hanging + abort is the fix for a pinned LSO blocking READ_COMMITTED consumers. It's the most common exactly-once incident.

16.5 Failure modes worth memorizing

16.6 Reading order, if you're new to the tree

1. DefaultRecordBatch.java + DefaultRecord.java — the format. Everything else assumes it.
2. UnifiedLog.append — the write path in one method.
3. AbstractIndex — including the whole comment.
4. TimingWheel + DelayedOperationPurgatory — the async model.
5. Partition.scala — ISR, HW, epochs.
6. QuorumState.java + KafkaRaftClient class doc — consensus.
7. QuorumController.java — the control plane pattern.
8. CurrentAssignmentBuilder.java — the cleanest state machine in the repo.
9. RecordAccumulator + Sender — the client side.
10. jmh-benchmarks/ — what the maintainers actually consider hot.

16.7 Things that are not true anymore (but are still in every blog post)

• ZooKeeper. Gone in 4.0. kafka.zk, KafkaController, LeaderAndIsrRequest, UpdateMetadataRequest, StopReplicaRequest — all removed.
• org.apache.kafka.common.record.DefaultRecordBatch — moved to ...record.internal.
• The log layer is Scala. It's Java, in storage/.
• Message formats v0/v1 — removed. Only v2 (magic 2) is supported, so down-conversion is gone.
• --zookeeper on any CLI tool.
• The consumer rebalance protocol is JoinGroup/SyncGroup — that's "classic"; the default is KIP-848.
• Kafka can't do queues. Share groups (KIP-932) exist.
• unclean.leader.election.enable is your only availability lever — ELR (KIP-966) is the third option.
• Kafka requires local disks for everything — tiered storage (KIP-405) is GA, and diskless topics (KIP-1150) are in flight.

Compiled from apache/kafka @ 930ebc5608bb0ac938085321d09b402b850ca87b, 4.4.0-SNAPSHOT. Where I've quoted a comment, it's because the comment is the specification.

Source: CS7641 Machine Learning Prep · cs7641-Machine-Learning-Prep.md · updated 2026-08-06 · 🔒 secret gist

Synced verbatim from gist.github.com/bl9.

CS 7641 Machine Learning — Preparedness Study Guide

Target: be able to answer Yes to all nine questions on the official OMSCS CS 7641 Machine Learning preparedness sheet.

Source: https://omscs.gatech.edu/sites/default/files/documents/2023/CS%207641-Course%20Preparedness%20Questions.pdf

Official prerequisite framing from that document: an introductory AI course, plus representational issues in AI, some AI programming, and background (or willingness to pick up background) in statistics and information theory.

Table of Contents

1. The nine questions at a glance
2. Eigenvectors and eigenvalues
3. Singular Value Decomposition
4. Conditions of a valid distance metric
5. Bayes Rule
6. Expectation of a random variable
7. Covariance and correlation
8. Search algorithms — BFS, DFS, A*
9. Asymptotic analysis of search algorithms
10. Programming background
11. Information theory (implied by the prerequisite text)
12. Reading list, mapped to questions
13. Self-test with answers
14. Three-week study plan
15. The study plan, worked
    • Week 1, Days 1–2 — Vectors, matrices, rank, null space, orthogonality
    • Week 1, Days 3–4 — Eigenvalues and eigenvectors, five 2×2 and two 3×3
    • Week 1, Days 5–6 — SVD by hand, end to end
    • Week 1, Day 7 — PCA from scratch, two ways
    • Week 2, Days 1–2 — Conditional probability and five base-rate problems
    • Week 2, Days 3–4 — Expectation, variance, and the distribution table derived
    • Week 2, Day 5 — Covariance by hand, then with numpy
    • Week 2, Day 6 — Information gain of a decision-tree split
    • Week 2, Day 7 — Bias–variance decomposition, derived
    • Week 3, Days 1–2 — BFS, DFS, UCS implemented
    • Week 3, Days 3–4 — A* and the node-expansion comparison
    • Week 3, Day 5 — The complexity table, derived and measured
    • Week 3, Days 6–7 — The scikit-learn warm-up, run

1. The nine questions at a glance

Practical note: CS 7641 Machine Learning assignments are analysis-and-writeup heavy. Question 9 says "not necessarily programmed," but in practice you will be running scikit-learn, ABAGAIL-style optimization code, and plotting a lot of learning curves. Treat Python + numpy + scikit-learn + matplotlib as the real bar.

2. Eigenvectors and eigenvalues

Definition

For a square matrix A (n×n), a nonzero vector v is an eigenvector with eigenvalue λ if:

A v = λ v

Interpretation: A acts on v by pure scaling — no rotation. Eigenvectors are the invariant directions of the linear map.

How to compute

1. Rearrange: (A − λI) v = 0 with v ≠ 0.
2. A nonzero solution exists only if A − λI is singular, so solve the characteristic equation:

   det(A − λI) = 0
   

   This is a degree-n polynomial in λ; its roots are the eigenvalues.
3. For each λ, solve the null space of (A − λI) to get the eigenvector(s). Normalize if you want unit length.

Worked example (2×2)

A = [ 4  1 ]
    [ 2  3 ]

Characteristic polynomial:

det([4−λ  1 ; 2  3−λ]) = (4−λ)(3−λ) − (1)(2)
                       = λ² − 7λ + 12 − 2
                       = λ² − 7λ + 10
                       = (λ − 5)(λ − 2)

So λ₁ = 5, λ₂ = 2.

• λ = 5: (A − 5I) = [−1 1; 2 −2] → −x + y = 0 → v₁ = (1, 1)ᵀ
• λ = 2: (A − 2I) = [ 2 1; 2 1] → 2x + y = 0 → v₂ = (1, −2)ᵀ

Sanity checks:

• trace(A) = 4 + 3 = 7 = 5 + 2 = Σλᵢ ✅
• det(A) = 12 − 2 = 10 = 5 × 2 = Πλᵢ ✅

Properties worth memorizing

• Σ λᵢ = trace(A), Π λᵢ = det(A)
• A is invertible ⟺ no eigenvalue is 0
• Eigenvalues of Aᵏ are λᵏ; of A⁻¹ are 1/λ
• Symmetric real matrices: all eigenvalues real, eigenvectors for distinct eigenvalues are orthogonal, and A = QΛQᵀ with Q orthogonal (spectral theorem)
• Positive semi-definite ⟺ all λ ≥ 0; positive definite ⟺ all λ > 0
• Algebraic multiplicity (root multiplicity) ≥ geometric multiplicity (null-space dimension). When they differ, A is not diagonalizable.
• Eigendecomposition requires square; SVD does not — that's why SVD is the workhorse in ML

Why CS 7641 Machine Learning cares

• PCA: eigenvectors of the covariance matrix are the principal components; eigenvalues are variance explained per component
• Spectral clustering: eigenvectors of the graph Laplacian
• Markov chains / MDPs: stationary distribution is the eigenvector of the transition matrix for λ = 1
• Optimization: eigenvalues of the Hessian tell you curvature, conditioning, and whether a critical point is a min, max, or saddle

numpy

import numpy as np
A = np.array([[4., 1.], [2., 3.]])
vals, vecs = np.linalg.eig(A)          # general square
vals, vecs = np.linalg.eigh(A)         # symmetric/Hermitian — faster, sorted, real
# vecs[:, i] is the eigenvector for vals[i]

3. Singular Value Decomposition

Definition

For any real m × n matrix A (square or not, full rank or not):

A = U Σ Vᵀ

• U: m × m orthogonal — columns are left singular vectors
• Σ: m × n diagonal, entries σ₁ ≥ σ₂ ≥ … ≥ σᵣ > 0, rest zero — singular values
• V: n × n orthogonal — columns are right singular vectors
• r = rank(A) = number of nonzero singular values

Thin/compact SVD: keep only the first r columns of U and V → A = U_r Σ_r V_rᵀ. This is what you almost always use.

Relationship to eigendecomposition

AᵀA = V Σᵀ Σ Vᵀ   → V = eigenvectors of AᵀA, σᵢ² = eigenvalues of AᵀA
AAᵀ = U Σ Σᵀ Uᵀ   → U = eigenvectors of AAᵀ, same nonzero eigenvalues

That relationship is the hand-computation recipe.

Procedure for computing by hand

1. Form AᵀA (pick whichever of AᵀA / AAᵀ is smaller).
2. Eigendecompose it → eigenvalues λᵢ, eigenvectors vᵢ.
3. σᵢ = √λᵢ, sorted descending. Columns of V are the vᵢ.
4. uᵢ = A vᵢ / σᵢ for each σᵢ > 0. Extend to a full basis with Gram–Schmidt if you need full U.

Worked example (rank-deficient)

A = [ 1  1 ]
    [ 1  1 ]

AᵀA = [2 2; 2 2] → eigenvalues 4 and 0.

• σ₁ = 2, σ₂ = 0 → rank 1
• λ=4 eigenvector: (1,1)ᵀ → v₁ = (1/√2, 1/√2)ᵀ
• λ=0 eigenvector: (1,−1)ᵀ → v₂ = (1/√2, −1/√2)ᵀ
• u₁ = A v₁ / σ₁ = (2/√2, 2/√2)ᵀ / 2 = (1/√2, 1/√2)ᵀ

So A = 2 · u₁ v₁ᵀ, a single rank-1 term. Verify: 2 · (1/√2)(1/√2) = 1 in every entry ✅

Second example (symmetric PSD)

A = [ 3  1 ]
    [ 1  3 ]

Symmetric with positive eigenvalues 4 and 2, so SVD = eigendecomposition: σ = (4, 2), u₁ = v₁ = (1,1)ᵀ/√2, u₂ = v₂ = (1,−1)ᵀ/√2.

Caution: SVD equals eigendecomposition only when A is symmetric positive semi-definite. If a symmetric matrix has a negative eigenvalue λ, then σ = |λ| and the sign moves into u.

Key facts

• Always exists, for every matrix. Singular values are unique; singular vectors are not (sign/rotation freedom in repeated σ).
• Eckart–Young–Mirsky: truncating to the top-k singular triplets gives the best rank-k approximation in both Frobenius and spectral norm. This is the theoretical basis for PCA, LSA, and matrix-completion recommenders.
• ‖A‖₂ = σ₁, ‖A‖_F = √(Σ σᵢ²), condition number κ = σ₁/σᵣ
• Pseudoinverse: A⁺ = V Σ⁺ Uᵀ where Σ⁺ inverts the nonzero σ. This is how least squares is solved stably.
• PCA = SVD of the mean-centered data matrix. Centering is not optional.

numpy

U, s, Vt = np.linalg.svd(A, full_matrices=False)   # thin SVD; s is a 1-D array
A_k = (U[:, :k] * s[:k]) @ Vt[:k, :]               # best rank-k approximation

4. Conditions of a valid distance metric

A function d: X × X → ℝ is a metric iff, for all x, y, z ∈ X:

Note: (1) is implied by (2)+(3)+(4), so some texts list only three axioms. If asked, give all four — say the four and note that non-negativity is derivable.

Weakened variants (know the names)

• Pseudometric: drops "only if" in (2) — distinct points can have distance 0
• Quasimetric: drops symmetry (e.g. one-way street driving distance)
• Semimetric: drops the triangle inequality
• Divergence: only d ≥ 0 and d(x,x) = 0 (e.g. KL)

Common metrics

Non-examples — these are the exam questions

• Squared Euclidean — violates the triangle inequality. On the line: d(0,2) = 4, but d(0,1) + d(1,2) = 1 + 1 = 2, and 4 > 2. ❌
• Cosine "distance" 1 − cos θ — violates the triangle inequality. (The angular version θ/π fixes it.) ❌
• KL divergence D(P‖Q) — violates symmetry and the triangle inequality. It's a divergence, not a metric. Jensen–Shannon distance (√JSD) is a proper metric. ❌
• Lp with p < 1 — e.g. p = 0.5 violates the triangle inequality. ❌

Why CS 7641 Machine Learning cares

k-NN, k-means, kernel methods, and DBSCAN all assume some notion of proximity. Whether it's a true metric determines whether you can use metric-tree indexes (KD-tree, ball tree), whether triangle-inequality pruning is valid, and whether clustering guarantees hold. Also: L2 in high dimensions concentrates (the curse of dimensionality), which is why L1 or cosine often works better on high-dimensional data.

5. Bayes Rule

Statement

P(A | B) = P(B | A) · P(A) / P(B)

with P(B) > 0. In ML naming:

posterior = likelihood × prior / evidence

P(h | D) = P(D | h) · P(h) / P(D)

Derivation (one line — be able to do this)

By definition of conditional probability, P(A|B) = P(A∩B)/P(B) and P(B|A) = P(A∩B)/P(A). Therefore P(A∩B) = P(B|A)P(A), and substituting gives the rule.

Law of total probability (the denominator)

P(B) = Σᵢ P(B | Aᵢ) P(Aᵢ)        for a partition {Aᵢ}

Worked example — base rate fallacy

Disease prevalence 1%. Test sensitivity P(+ | D) = 0.99. Specificity P(− | ¬D) = 0.95, so false positive rate P(+ | ¬D) = 0.05. You test positive. What is P(D | +)?

P(+) = P(+|D)P(D) + P(+|¬D)P(¬D)
     = (0.99)(0.01) + (0.05)(0.99)
     = 0.0099 + 0.0495
     = 0.0594

P(D | +) = 0.0099 / 0.0594 = 0.1667

≈ 16.7%, not 99%. The prior dominates when the base rate is low. If you find this surprising, redo it until you don't.

ML forms you must recognize

• MAP: h_MAP = argmax_h P(D|h)P(h) — the evidence P(D) drops out because it doesn't depend on h
• MLE: h_MLE = argmax_h P(D|h) — MAP with a uniform prior
• Naive Bayes: assume features conditionally independent given the class:

  P(y | x₁…xₙ) ∝ P(y) Πᵢ P(xᵢ | y)
  

  Work in log space to avoid underflow. Use Laplace smoothing for unseen feature values.
• Bayesian vs frequentist framing: Bayesians treat parameters as random variables with priors; MAP/MLE is where CS 7641 Machine Learning spends most of its time (the Bayesian Learning lectures).

Related identities

• Chain rule: P(A,B,C) = P(A|B,C)P(B|C)P(C)
• Conditional independence: P(A,B|C) = P(A|C)P(B|C) — the assumption behind both Naive Bayes and Bayes nets
• Odds form: posterior odds = likelihood ratio × prior odds

6. Expectation of a random variable

Definitions

Discrete:

E[X] = Σₓ x · P(X = x)

Continuous:

E[X] = ∫ x · f(x) dx

LOTUS (law of the unconscious statistician) — expectation of a function, no need to derive the distribution of g(X):

E[g(X)] = Σₓ g(x) P(X = x)     or     ∫ g(x) f(x) dx

Properties

Linearity holding without independence is the single most-used fact in ML derivations. Know it cold.

Worked example — fair six-sided die

E[X]  = (1+2+3+4+5+6)/6 = 21/6 = 3.5
E[X²] = (1+4+9+16+25+36)/6 = 91/6 ≈ 15.167
Var(X) = 91/6 − (3.5)² = 15.167 − 12.25 = 2.9167 = 35/12
SD(X) ≈ 1.708

Standard distributions — memorize these

Why CS 7641 Machine Learning cares

• Expected loss / risk minimization is the definition of the learning objective
• Bias–variance decomposition: E[(y − ŷ)²] = Bias² + Variance + Irreducible error — this is a pure expectation manipulation and it shows up in every assignment writeup
• Value functions in reinforcement learning are expectations over trajectories: V(s) = E[Σ γᵗ rₜ | s₀ = s]
• Entropy is E[−log p(X)]

7. Covariance and correlation

Covariance

Cov(X, Y) = E[(X − μₓ)(Y − μ_y)] = E[XY] − E[X]E[Y]

Sample estimators:

population:  Cov = (1/n)   Σ (xᵢ − x̄)(yᵢ − ȳ)
sample:      Cov = (1/(n−1)) Σ (xᵢ − x̄)(yᵢ − ȳ)     ← Bessel's correction, unbiased

Units are units-of-X × units-of-Y, so the magnitude is not interpretable on its own — that's what correlation fixes.

Pearson correlation

ρ(X, Y) = Cov(X, Y) / (σₓ σ_y)        ρ ∈ [−1, 1]

Dimensionless. ρ = ±1 ⟺ perfect linear relationship.

Worked example

X = [1, 2, 3, 4]     Y = [2, 4, 5, 4]
x̄ = 2.5              ȳ = 3.75

• Population covariance = 3.5 / 4 = 0.875
• Sample covariance = 3.5 / 3 ≈ 1.167
• Var(X)_pop = 5/4 = 1.25 → σₓ = 1.118
• Var(Y)_pop = 4.75/4 = 1.1875 → σ_y = 1.090
• ρ = 0.875 / (1.118 × 1.090) = 0.875 / 1.2183 ≈ **0.718**

(Use the same convention — population or sample — in numerator and denominator; ρ is identical either way since the n vs n−1 cancels.)

Properties

• Cov(X, X) = Var(X)
• Symmetric: Cov(X,Y) = Cov(Y,X)
• Bilinear: Cov(aX + b, cY + d) = ac · Cov(X, Y)
• Independent ⟹ Cov = 0. The converse is false. Classic counterexample: X ~ Uniform(−1,1), Y = X². Then Cov(X,Y) = E[X³] − E[X]E[X²] = 0 − 0 = 0, but Y is fully determined by X.
• Correlation captures linear dependence only. Use mutual information (or Spearman rank correlation) for monotone/nonlinear dependence.
• Correlation ≠ causation. Say it out loud in every assignment writeup.

Covariance matrix

For a random vector X ∈ ℝᵈ:

Σ = E[(X − μ)(X − μ)ᵀ]      d × d, symmetric, positive semi-definite
Σᵢⱼ = Cov(Xᵢ, Xⱼ),  Σᵢᵢ = Var(Xᵢ)

From a centered data matrix X_c (n × d): Σ̂ = X_cᵀ X_c / (n − 1).

PCA = eigendecomposition of Σ̂ = SVD of X_c. That's the through-line from §2, §3, and §7 into the unsupervised-learning half of the course.

numpy

np.cov(X, Y)                # sample covariance (ddof=1 by default) — returns 2×2
np.corrcoef(X, Y)           # correlation matrix
np.cov(data, rowvar=False)  # d×d covariance from an n×d data matrix

8. Search algorithms — BFS, DFS, A*

The general framework

All three are the same loop with a different frontier data structure:

frontier ← {start}
explored ← {}
loop:
    node ← frontier.remove()
    if goal(node): return path
    explored.add(node)
    for child in expand(node):
        if child not in explored ∪ frontier: frontier.add(child)

Breadth-First Search

• Explores level by level. Finds the shallowest goal.
• Optimal only when all step costs are equal. With varying costs, use UCS.
• Complete (if b is finite).
• Space is the killer: the whole frontier lives in memory, O(b^d).
• Goal test on generation rather than expansion saves one full level of work.

Depth-First Search

• Dives to the deepest node, backtracks on dead ends.
• Not optimal, and not complete in infinite-depth or cyclic spaces (graph-search version with an explored set is complete on finite graphs).
• Space is the win: O(bm) — only the current path plus siblings.
• Iterative Deepening DFS (IDS) = DFS space with BFS optimality: repeatedly run depth-limited DFS with limit 0, 1, 2, … Re-expansion cost is negligible because the last level dominates the node count.

A*

f(n) = g(n) + h(n)

• g(n): actual cost from start to n
• h(n): heuristic estimate of cost from n to the goal
• h(goal) = 0

Admissible: h(n) ≤ h*(n) for all n — never overestimates the true remaining cost. → A* with tree search is optimal.

Consistent (monotonic): h(n) ≤ c(n, a, n') + h(n') for every successor n' — a triangle inequality on the heuristic. → A* with graph search is optimal. Consistency ⟹ admissibility (not the converse). Under consistency, f is non-decreasing along any path, and the first time you expand a node you already have its optimal g.

Optimally efficient: no other optimal algorithm using the same heuristic expands fewer nodes (up to tie-breaking).

Dominance: if h₂(n) ≥ h₁(n) for all n and both are admissible, h₂ dominates and A* expands no more nodes with h₂. A larger admissible heuristic is always at least as good.

Special cases:

• h(n) = 0 → A* degenerates to UCS/Dijkstra
• h(n) = h*(n) → A* walks straight to the goal
• g(n) = 0 → greedy best-first (fast, not optimal)

Variants worth naming: IDA* (memory-bounded), weighted A* (f = g + w·h, w > 1 — bounded suboptimality, much faster).

Trace practice

Take any small weighted graph, pick a start and a goal, and hand-trace all three, writing down the frontier contents at every step. If you can do that on a 8–10 node graph without hesitation, question 7 is a Yes.

9. Asymptotic analysis of search algorithms

Notation

• b — branching factor
• d — depth of the shallowest goal
• m — maximum depth of the search tree (may be ∞)
• C* — cost of the optimal solution
• ε — minimum step cost (> 0)

The table

Points that get asked

• Why is IDS O(b^d) and not worse despite re-expansion? Node counts are dominated by the deepest level. Total generated is (d+1)b⁰ + d·b¹ + … + 1·b^d, which is O(b^d) — a constant factor of roughly b/(b−1) above BFS. For b = 10, about 11% overhead. You trade that for O(bd) space instead of O(b^d).
• A's real bottleneck is memory, not time.* It stores every generated node. IDA*, RBFS, and SMA* exist to fix that.
• A time complexity with a good heuristic*: if |h(n) − h*(n)| ≤ O(log h*(n)), growth is sub-exponential. In general it's exponential in the relative error of the heuristic.
• Bidirectional search halves the exponent, which is a much bigger win than any constant-factor optimization — but it requires a well-defined predecessor function and an easily-tested goal state.
• Big-O refresher: O is an upper bound, Ω a lower bound, Θ a tight bound. Drop constants and lower-order terms. O(b^d) with b=10, d=12 is 10¹² nodes — this is why heuristics matter.

10. Programming background

The question only asks whether you have worked with Python, R, MATLAB, or Java. The honest bar for succeeding in CS 7641 Machine Learning is higher. Checklist:

Python core

• Comfortable with list/dict comprehensions, zip, enumerate, classes, virtualenv/conda
• Can read a stack trace and debug someone else's code

numpy

• Vectorization instead of loops; broadcasting rules; axis= semantics
• Slicing, boolean masks, reshape, argsort, linalg module

pandas

• Load CSV, handle missing values, groupby, merge, one-hot encode

scikit-learn — this is the actual course toolkit

• fit / predict / transform API and Pipeline
• train_test_split, cross_val_score, GridSearchCV
• StandardScaler (fit on train only — leakage is a common assignment mistake)
• Classifiers used in Assignment 1: decision trees, boosting, k-NN, SVM, neural nets
• Unsupervised: KMeans, GaussianMixture, PCA, FastICA, SparseRandomProjection
• learning_curve and validation_curve — you will generate dozens of these

matplotlib / seaborn

• Multi-series line plots with labeled axes and legends; subplots; save to file

Warm-up exercise: load a UCI dataset (e.g. Wine or Adult), build a pipeline with scaling + a decision tree, tune max_depth with GridSearchCV, and plot the learning curve and validation curve. If you can do that end-to-end in under an hour, you're ready.

11. Information theory (implied by the prerequisite text)

The preparedness doc doesn't ask a question about this, but the prerequisite paragraph explicitly names information theory, and CS 7641 Machine Learning uses it from the first decision-tree lecture onward.

Entropy — expected surprise, in bits (log base 2):

H(X) = −Σ p(x) log₂ p(x)

Maximized by the uniform distribution (H = log₂ n), zero for a deterministic variable.

Conditional entropy:

H(Y | X) = Σ p(x) H(Y | X = x)

Information gain — the decision-tree splitting criterion:

IG(Y, X) = H(Y) − H(Y | X)

Mutual information:

I(X; Y) = H(X) + H(Y) − H(X,Y) = H(Y) − H(Y|X) ≥ 0

Zero iff X and Y are independent. Unlike correlation, it captures nonlinear dependence.

KL divergence — relative entropy:

D_KL(P ‖ Q) = Σ p(x) log(p(x)/q(x)) ≥ 0

Asymmetric, no triangle inequality (see §4). Cross-entropy loss = H(P) + D_KL(P‖Q); since H(P) is fixed by the data, minimizing cross-entropy = minimizing KL.

Gini impurity — the CART alternative to entropy:

Gini = 1 − Σ p(x)²

Cheaper to compute, behaves very similarly in practice.

Worked micro-example: a node with 9 positives and 5 negatives.

H = −(9/14)log₂(9/14) − (5/14)log₂(5/14)
  = −(0.643)(−0.637) − (0.357)(−1.485)
  ≈ 0.410 + 0.530 = 0.940 bits

12. Reading list, mapped to questions

As given in the official document

Linear algebra — either one:

1. Numerical Linear Algebra — Trefethen & Bau. Read Part I (Fundamentals) through Lecture 5.
2. Introduction to Linear Algebra, 4th ed. — Gilbert Strang.

Probability and statistics:

1. All of Statistics — Larry Wasserman. Read Part I (Probability).

Artificial intelligence (optional):

1. Artificial Intelligence: A Modern Approach — Russell & Norvig.

Which reading covers which question

Useful free supplements

• 3Blue1Brown, Essence of Linear Algebra — the eigenvector and change-of-basis episodes are the fastest intuition available
• MIT 18.06 (Strang) lectures — free on OCW/YouTube
• Mitchell, Machine Learning (1997) — the course's own primary text; Ch. 3 (decision trees) and Ch. 6 (Bayesian learning) map directly onto §5 and §11 here
• Berkeley CS188 Pacman projects — hands-on BFS/DFS/UCS/A* implementation
• MacKay, Information Theory, Inference, and Learning Algorithms — free PDF, for §11

13. Self-test with answers

Do these closed-book. Answers follow each question.

1. Find the eigenvalues of [[2, 1], [1, 2]].

det([2−λ, 1; 1, 2−λ]) = (2−λ)² − 1 = λ² − 4λ + 3 = (λ−3)(λ−1). λ = 3, 1. Eigenvectors (1,1) and (1,−1).

2. What are the singular values of [[3, 0], [0, −4]]?

AᵀA = [[9,0],[0,16]], eigenvalues 16 and 9 → σ = 4, 3 (descending). Note σ is the absolute value; the sign of −4 goes into U.

3. Is d(x,y) = (x − y)² on ℝ a valid metric? Justify.

No. It fails the triangle inequality: d(0,2) = 4 > d(0,1) + d(1,2) = 2.

4. 1 in 1000 people have a condition. A test is 99% sensitive and 98% specific. Given a positive result, what is P(condition)?

P(+) = 0.99(0.001) + 0.02(0.999) = 0.00099 + 0.01998 = 0.02097. P(D|+) = 0.00099 / 0.02097 ≈ **4.7%**.

5. X ~ Uniform(0, 10). Compute E[X] and Var(X).

E[X] = (0+10)/2 = **5**. Var(X) = (10−0)²/12 = 100/12 ≈ **8.33**.

6. If Cov(X,Y) = 0, are X and Y independent?

No. Zero covariance means no linear relationship. Counterexample: X ~ Uniform(−1,1), Y = X².

7. Which of BFS, DFS, and A* guarantee an optimal solution, and under what conditions?

BFS: optimal only with uniform step costs. DFS: never guaranteed. A*: optimal with an admissible heuristic under tree search, and a consistent heuristic under graph search.

8. State the time and space complexity of iterative deepening and explain why the re-expansion is cheap.

Time O(b^d), space O(bd). The deepest level contains the overwhelming majority of nodes, so re-generating all the shallower levels adds only a constant factor of roughly b/(b−1).

9. h₁ and h₂ are both admissible and h₂(n) ≥ h₁(n) everywhere. Which should you use?

h₂ — it dominates, so A* expands no more nodes with it. Larger admissible heuristics are strictly better.

10. A node has 6 positive and 2 negative examples. Compute its entropy.

H = −0.75 log₂ 0.75 − 0.25 log₂ 0.25 = 0.75(0.415) + 0.25(2) = 0.311 + 0.5 = **0.811 bits**.

11. Why is centering the data required before PCA?

Without centering, the first principal component points toward the data's mean rather than the direction of maximum variance. X_cᵀX_c / (n−1) is only the covariance matrix when X_c has zero column means.

12. Write Bayes Rule and identify each term by its ML name.

P(h|D) = P(D|h)P(h)/P(D) — posterior, likelihood, prior, evidence (marginal likelihood).

14. Three-week study plan

Assumes roughly 8–10 hours per week. Compress or stretch as needed.

Week 1 — Linear algebra (Questions 1, 2, and part of 3)

• Days 1–2: vectors, matrices, rank, null space, orthogonality. Strang Ch. 1–3 or Trefethen Lectures 1–3.
• Days 3–4: eigenvalues and eigenvectors. Compute five 2×2 and two 3×3 by hand. Watch the 3Blue1Brown eigenvector episode.
• Days 5–6: SVD. Trefethen Lectures 4–5. Compute one 2×2 by hand end to end, then verify with np.linalg.svd.
• Day 7: implement PCA from scratch with np.linalg.eigh on the covariance matrix, and again with SVD on the centered data. Confirm the components match.

Week 2 — Probability and statistics (Questions 4, 5, 6, plus information theory)

• Days 1–2: sample spaces, conditional probability, independence, Bayes Rule. Wasserman Ch. 1. Do five base-rate problems.
• Days 3–4: random variables, expectation, variance, LOTUS. Wasserman Ch. 3. Memorize the distribution table in §6.
• Day 5: covariance, correlation, covariance matrices. Compute one by hand, verify with np.cov.
• Day 6: entropy, information gain, KL divergence. Hand-compute the information gain of a decision-tree split.
• Day 7: derive the bias–variance decomposition from scratch using linearity of expectation.

Week 3 — Search, complexity, and tooling (Questions 7, 8, 9)

• Days 1–2: Russell & Norvig Ch. 3. Implement BFS, DFS, and UCS on a grid or graph.
• Days 3–4: A*, admissibility, consistency, dominance. Implement A* with Manhattan distance on a grid; compare expanded-node counts against UCS.
• Day 5: reproduce the complexity table in §9 from memory. Verify empirically by counting node expansions.
• Days 6–7: the scikit-learn warm-up from §10 — pipeline, grid search, learning curve, validation curve on a real dataset.

Final check: retake the nine questions. Every one should be a confident Yes with a worked example you can produce on demand.

15. The study plan, worked

Section 14 lists what to do. This section does it — every day of the plan, with the explanation and the finished exercise. All numeric results below were computed and verified, not estimated.

Week 1, Days 1–2 — Vectors, matrices, rank, null space, orthogonality

What it requires: be able to say what rank, null space, and orthogonality mean, and connect them to whether a system has a solution.

The four fundamental subspaces. For A of size m × n:

Rank–nullity theorem: rank(A) + dim N(A) = n. Row rank always equals column rank.

Orthogonality relations: N(A) ⊥ C(Aᵀ) and N(Aᵀ) ⊥ C(A). Those two facts are the whole geometry of least squares.

Worked: rank and null space of a rank-deficient matrix.

A = [ 1  2  3 ]
    [ 2  4  6 ]
    [ 1  1  1 ]

Row-reduce. R2 − 2·R1 → [0 0 0]. R3 − R1 → [0 −1 −2].

[ 1  2  3 ]
[ 0 −1 −2 ]
[ 0  0  0 ]

Two pivots → rank = 2. Nullity = 3 − 2 = 1. Solve Ax = 0: from row 2, −y − 2z = 0 → y = −2z. From row 1, x + 2(−2z) + 3z = 0 → x = z. So N(A) = span{(1, −2, 1)ᵀ}.

Verify: A(1,−2,1)ᵀ = (1−4+3, 2−8+6, 1−2+1)ᵀ = (0,0,0)ᵀ ✅

Why this matters downstream. A rank-deficient design matrix means the normal equations AᵀA x = Aᵀb have infinitely many solutions — this is exactly multicollinearity in linear regression, and it's why you either regularize (ridge adds λI, making AᵀA + λI invertible) or use the pseudoinverse from SVD.

Orthogonality and projection. The projection of b onto C(A) is p = A(AᵀA)⁻¹Aᵀb. The least-squares solution x̂ = (AᵀA)⁻¹Aᵀb is exactly the x making the residual b − Ax orthogonal to the column space. Orthonormal bases make this trivial: if Q has orthonormal columns, QᵀQ = I and the projection is just QQᵀb.

Norms (needed for §4): ‖x‖₁ = Σ|xᵢ|, ‖x‖₂ = √(Σxᵢ²), ‖x‖∞ = max|xᵢ|. Every norm induces a metric via d(x,y) = ‖x − y‖. That's the bridge between this day and the distance-metric question.

Day 1–2 checkpoint: given a 3×4 matrix, state its rank, the dimension of its null space, and whether Ax = b has zero, one, or infinitely many solutions.

Week 1, Days 3–4 — Eigenvalues and eigenvectors, five 2×2 and two 3×3

What it requires: five 2×2 by hand and two 3×3 by hand. Here they are, all verified against np.linalg.eig.

2×2 problem 1 — distinct real eigenvalues

A = [ 5  4 ]      det(A−λI) = (5−λ)(2−λ) − 4 = λ² − 7λ + 6 = (λ−6)(λ−1)
    [ 1  2 ]

• λ = 6: [−1 4; 1 −4] → x = 4y → v = (4, 1)ᵀ
• λ = 1: [ 4 4; 1 1] → x = −y → v = (1, −1)ᵀ
• Check: trace 7 = 6+1 ✅, det 10−4 = 6 = 6·1 ✅

2×2 problem 2 — negative eigenvalues

A = [  0   1 ]    det(A−λI) = (−λ)(−3−λ) + 2 = λ² + 3λ + 2 = (λ+1)(λ+2)
    [ −2  −3 ]

• λ = −1: [1 1; −2 −2] → v = (1, −1)ᵀ
• λ = −2: [2 1; −2 −1] → 2x + y = 0 → v = (1, −2)ᵀ
• Both eigenvalues negative → this is the matrix form of a stable linear system (x' = Ax decays).

2×2 problem 3 — complex eigenvalues

A = [ 2  −1 ]     λ² − 4λ + 5 = 0  →  λ = 2 ± i
    [ 1   2 ]

Real matrices can have complex eigenvalues; they arrive in conjugate pairs. Geometrically this is a rotation combined with a scaling — there is no real invariant direction. |λ| = √5 is the scale factor, arg(λ) = arctan(1/2) the rotation angle. Real symmetric matrices can never do this, which is why the spectral theorem is such a strong guarantee.

2×2 problem 4 — defective (repeated eigenvalue, one eigenvector)

A = [ 3  1 ]      det(A−λI) = (3−λ)² = 0  →  λ = 3 (algebraic multiplicity 2)
    [ 0  3 ]

(A − 3I) = [0 1; 0 0] → y = 0 → the null space is only span{(1,0)ᵀ}. Geometric multiplicity 1 < algebraic multiplicity 2 → A is not diagonalizable. numpy returns two identical eigenvector columns here, which is the numerical symptom of the same fact. This is the standard counterexample to "every matrix has a full eigenbasis," and the reason SVD (which always exists) is preferred in practice.

2×2 problem 5 — symmetric, orthogonal eigenvectors

A = [  6  −2 ]    λ² − 15λ + 50 = (λ−10)(λ−5)
    [ −2   9 ]

• λ = 10: [−4 −2; −2 −1] → y = −2x → v = (1, −2)ᵀ
• λ = 5: [ 1 −2; −2 4] → x = 2y → v = (2, 1)ᵀ
• v₁ · v₂ = 2 − 2 = 0 ✅ orthogonal, as the spectral theorem guarantees. Both eigenvalues positive → positive definite → this is a legitimate covariance matrix.

3×3 problem 1 — block structure

B = [ 2  0  0 ]
    [ 0  3  4 ]
    [ 0  4  9 ]

The top-left is a 1×1 block, so λ = 2 with eigenvector (1,0,0)ᵀ. The bottom-right 2×2 gives λ² − 12λ + (27 − 16) = λ² − 12λ + 11 = (λ−11)(λ−1). Eigenvalues: 11, 2, 1. Verified numerically. Block-diagonal matrices let you decompose the problem — worth spotting before grinding out a cubic.

3×3 problem 2 — triangular

C = [ 4  −2   1 ]
    [ 0   3  −1 ]
    [ 0   0   2 ]

Triangular → eigenvalues are the diagonal: 4, 3, 2. No characteristic polynomial needed.

• λ = 4: (C−4I) = [0 −2 1; 0 −1 −1; 0 0 −2] → z = 0, y = 0 → v = (1,0,0)ᵀ
• λ = 3: [1 −2 1; 0 0 −1; 0 0 −1] → z = 0, x = 2y → v = (2,1,0)ᵀ
• λ = 2: [2 −2 1; 0 1 −1; 0 0 0] → y = z, 2x − 2y + z = 0 → 2x = y → v = (1,2,2)ᵀ
• Verify: C(1,2,2)ᵀ = (4−4+2, 6−2, 4)ᵀ = (2,4,4)ᵀ = 2·(1,2,2)ᵀ ✅

Note the eigenvectors are not orthogonal here — C isn't symmetric.

Day 3–4 checkpoint: you should now be able to spot, before computing, whether a matrix will have real eigenvalues (symmetric), complex ones (rotation-like), a defective spectrum (repeated root with a rank-deficient A − λI), or free eigenvalues (triangular/block).

Week 1, Days 5–6 — SVD by hand, end to end

What it requires: one full 2-column SVD computed by hand, verified with numpy.

The example (the classic non-square case):

A = [ 3   2 ]
    [ 2   3 ]     (3 × 2)
    [ 2  −2 ]

Step 1 — form AᵀA (2×2 is smaller than the 3×3 AAᵀ, so use it):

AᵀA = [ 9+4+4    6+6−4 ]  =  [ 17   8 ]
      [ 6+6−4    4+9+4 ]     [  8  17 ]

Step 2 — eigendecompose it. det([17−λ, 8; 8, 17−λ]) = (17−λ)² − 64. So 17 − λ = ±8 → λ = 25, 9.

Step 3 — singular values. σ₁ = √25 = 5, σ₂ = √9 = 3. Two nonzero singular values → rank(A) = 2.

Step 4 — right singular vectors (eigenvectors of AᵀA):

• λ = 25: [−8 8; 8 −8] → x = y → v₁ = (1, 1)ᵀ/√2
• λ = 9: [ 8 8; 8 8] → x = −y → v₂ = (1, −1)ᵀ/√2

Step 5 — left singular vectors via uᵢ = A vᵢ / σᵢ:

A v₁ = (1/√2)(3+2, 2+3, 2−2)ᵀ = (5, 5, 0)ᵀ/√2
u₁ = A v₁ / 5 = (1, 1, 0)ᵀ/√2

A v₂ = (1/√2)(3−2, 2−3, 2+2)ᵀ = (1, −1, 4)ᵀ/√2
u₂ = A v₂ / 3 = (1, −1, 4)ᵀ/(3√2)

Check ‖u₂‖ = √((1 + 1 + 16)/18) = √(18/18) = 1 ✅ and u₁ · u₂ = (1 − 1 + 0)/6 = 0 ✅

Result:

A = 5 · u₁v₁ᵀ + 3 · u₂v₂ᵀ

Numpy verification (signs may flip — that's the sign ambiguity, not an error):

sigma = [5.  3.]
U  = [[-0.7071,  0.2357], [-0.7071, -0.2357], [-0.0000,  0.9428]]
Vt = [[-0.7071, -0.7071], [ 0.7071, -0.7071]]
U @ diag(s) @ Vt  reproduces A exactly ✅

Note 0.2357 = 1/(3√2) and 0.9428 = 4/(3√2) — the hand computation matches column for column.

Step 6 — the truncation experiment (this is the point of SVD in ML). Best rank-1 approximation:

A₁ = 5 · u₁v₁ᵀ = [ 2.5  2.5 ]
                 [ 2.5  2.5 ]
                 [ 0.0  0.0 ]

Frobenius error ‖A − A₁‖_F = 3.0000, which is exactly σ₂. That's Eckart–Young made concrete: the error of the best rank-k approximation equals √(Σ_{i>k} σᵢ²), and here that's just σ₂. No other rank-1 matrix does better.

Day 5–6 checkpoint: given any small matrix, produce σ, U, V by hand, state the rank, write the rank-1 approximation, and predict its Frobenius error before computing it.

Week 1, Day 7 — PCA from scratch, two ways

What it requires: implement PCA via eigendecomposition of the covariance matrix and via SVD of the centered data, and confirm they agree.

Why they must agree. Let X_c be the mean-centered n × d data matrix. Then:

Σ̂ = X_cᵀ X_c / (n − 1)

Substituting the SVD X_c = UΣVᵀ:

Σ̂ = (VΣᵀUᵀ)(UΣVᵀ)/(n−1) = V (Σ²/(n−1)) Vᵀ

This is exactly the eigendecomposition of Σ̂. So:

• Principal directions = columns of V = right singular vectors of X_c
• Eigenvalues of Σ̂ = σᵢ²/(n−1)
• Scores (projected data) = X_c V = UΣ

The code:

import numpy as np
from sklearn.datasets import load_wine

X = load_wine().data
Xc = (X - X.mean(0)) / X.std(0)          # standardize: center + unit variance

# Route A: eigendecomposition of the covariance matrix
cov = np.cov(Xc, rowvar=False)
w, V = np.linalg.eigh(cov)               # eigh: symmetric, returns ascending
idx = np.argsort(w)[::-1]                # sort descending
w, V = w[idx], V[:, idx]

# Route B: SVD of the centered data
U, s, Vt = np.linalg.svd(Xc, full_matrices=False)

print(w[:5])                              # eigenvalues
print((s**2 / (len(Xc) - 1))[:5])         # should be identical

Actual output on the Wine dataset (13 features, 178 samples):

eigendecomposition eigenvalues : [4.7324  2.5111  1.4542  0.9242  0.8580]
svd  s²/(n−1)                  : [4.7324  2.5111  1.4542  0.9242  0.8580]
max |component_1| difference   : 5.97e-16       (machine precision)
variance explained ratio       : [0.3620  0.1921  0.1112  0.0707  0.0656]

They agree to floating-point noise. First two components explain 55.4% of variance; first five explain 80.2%.

Three things to internalize from this exercise:

1. Standardize before PCA when features have different units. The Wine dataset has proline in the hundreds and hue near 1. Without scaling, proline alone would dominate PC1 because PCA maximizes raw variance. Centering is mandatory; scaling is a modeling choice that is almost always right for heterogeneous features.
2. Prefer the SVD route numerically. Forming XᵀX squares the condition number. svd(Xc) works on Xc directly and is what sklearn.decomposition.PCA actually calls.
3. Eigenvalue = variance along that component. The explained-variance ratio λᵢ/Σλⱼ is what you plot in a scree plot to pick k. In CS 7641 Machine Learning Assignment 3 you will justify your choice of k with exactly this plot, so know what the axis means.

Week 2, Days 1–2 — Conditional probability and five base-rate problems

What it requires: five base-rate problems worked. The pattern is always the same — compute the denominator with the law of total probability, then divide.

Problem 1 — Spam filter

P(spam) = 0.4. The word "free" appears in 30% of spam and 2% of ham. An email contains "free".

P(free) = (0.30)(0.4) + (0.02)(0.6) = 0.120 + 0.012 = 0.132
P(spam | free) = 0.120 / 0.132 = 0.909

≈ 90.9%. A strong likelihood ratio (15:1) plus a near-balanced prior gives a confident posterior — contrast with Problem 2.

Problem 2 — Drug test

5% of a population use a drug. Test is 95% sensitive, 90% specific. Someone tests positive.

P(+) = (0.95)(0.05) + (0.10)(0.95) = 0.0475 + 0.0950 = 0.1425
P(user | +) = 0.0475 / 0.1425 = 1/3

33.3%. A "95% accurate" test leaves you twice as likely to be innocent as guilty, because the 10% false-positive rate applies to a population 19× larger. This is the base-rate fallacy in one line.

Problem 3 — Two machines

Machine A produces 60% of output at a 2% defect rate; machine B produces 40% at 5%. A defective item is found.

P(D) = (0.02)(0.6) + (0.05)(0.4) = 0.012 + 0.020 = 0.032
P(A | D) = 0.012 / 0.032 = 0.375     P(B | D) = 0.625

Machine B makes less output but most of the defects. Prior 60/40 flips to posterior 37.5/62.5.

Problem 4 — Monty Hall, as Bayes

You pick door 1. Host (who knows) opens door 3, revealing a goat.

Prior:      P(C₁) = P(C₂) = P(C₃) = 1/3
Likelihood: P(open3 | C₁) = 1/2   (host picks freely between 2 and 3)
            P(open3 | C₂) = 1     (host is forced)
            P(open3 | C₃) = 0     (host won't reveal the car)

P(open3) = (1/3)(1/2) + (1/3)(1) + 0 = 1/6 + 1/3 = 1/2

P(C₁ | open3) = (1/6)/(1/2) = 1/3
P(C₂ | open3) = (1/3)/(1/2) = 2/3

Switch. The asymmetry lives entirely in the likelihood: the host's constrained behaviour when the car is behind door 2 is what carries the information.

Problem 5 — Naive Bayes, end to end

Training data, 5 documents:

Priors: P(spam) = 2/5 = 0.4, P(ham) = 3/5 = 0.6.

Vocabulary V = {cheap, buy, now, meeting, project, report}, |V| = 6. Token counts: spam has 6 tokens (cheap×3, buy×2, now×1); ham has 9 tokens (meeting×3, project×2, now×2, report×2).

With Laplace (add-1) smoothing, P(w|c) = (count(w,c) + 1)/(N_c + |V|):

P(cheap|spam) = 4/12 = 0.3333      P(cheap|ham)   = 1/15 = 0.0667
P(buy|spam)   = 3/12 = 0.2500      P(buy|ham)     = 1/15 = 0.0667
P(now|spam)   = 2/12 = 0.1667      P(now|ham)     = 3/15 = 0.2000

Classify the new document "cheap buy now":

score(spam) = 0.4 × 0.3333 × 0.2500 × 0.1667 = 0.005556
score(ham)  = 0.6 × 0.0667 × 0.0667 × 0.2000 = 0.000533
P(spam | doc) = 0.005556 / (0.005556 + 0.000533) = 0.912

Classify as spam, 91.2% posterior.

Three practical notes this exercise is meant to teach:

• Smoothing is not optional. Without add-1, P(cheap|ham) = 0 sends the entire ham score to zero — one unseen word vetoes a class.
• Work in logs. With hundreds of features, the products underflow. Use log P(c) + Σ log P(wᵢ|c) and compare log-scores.
• The independence assumption is wrong and it works anyway. "cheap" and "buy" clearly co-occur. Naive Bayes gets miscalibrated probabilities but often the right argmax, which is why it survives as a baseline.

Week 2, Days 3–4 — Expectation, variance, and the distribution table derived

What it requires: memorize the distribution table. Memorization sticks better after deriving a few, so here are the derivations.

Bernoulli(p). X ∈ {0,1}.

E[X]  = 1·p + 0·(1−p) = p
E[X²] = 1²·p + 0²·(1−p) = p       (since X² = X for a 0/1 variable)
Var   = p − p² = p(1−p)

Maximized at p = 0.5 — a fair coin is the most uncertain Bernoulli, which is also why entropy peaks there.

Binomial(n,p). Write X = Σᵢ Xᵢ as a sum of n iid Bernoullis.

E[X]  = Σ E[Xᵢ] = np                          (linearity — no independence needed)
Var(X) = Σ Var(Xᵢ) = np(1−p)                  (independence needed here)

This decomposition trick — rewrite a complicated variable as a sum of indicators — is the single most useful move in applied probability.

Geometric(p), number of trials until the first success. Condition on the first trial:

E[X] = 1 + (1−p)·E[X]          → E[X](1 − (1−p)) = 1 → E[X] = 1/p

That's the tower property doing real work.

Uniform(a,b).

E[X]  = ∫ₐᵇ x/(b−a) dx = (b² − a²)/(2(b−a)) = (a+b)/2
E[X²] = (b³ − a³)/(3(b−a)) = (a² + ab + b²)/3
Var   = (a² + ab + b²)/3 − (a+b)²/4 = (b−a)²/12

Exponential(λ). Integrate by parts:

E[X] = ∫₀^∞ x λe^(−λx) dx = 1/λ
E[X²] = 2/λ²   →   Var = 2/λ² − 1/λ² = 1/λ²

Memoryless: P(X > s+t | X > s) = P(X > t).

Poisson(λ). E[X] = Var(X) = λ. Mean equals variance is the diagnostic — if your count data has variance far above the mean, you have overdispersion and Poisson is the wrong model.

The one identity to drill: Var(X) = E[X²] − (E[X])². Every derivation above is an application of it.

LOTUS in practice. To get E[X²] you never need the distribution of X². Just sum x²·p(x). Same for E[e^X], E[log X], and any loss function.

Jensen's inequality, and why it matters. For convex g, E[g(X)] ≥ g(E[X]). Consequence: the average of squared errors exceeds the square of the average error, and E[log X] ≤ log E[X] — the latter is the inequality that produces the ELBO in variational inference and the E-step bound in EM.

Day 3–4 checkpoint: state mean and variance for all seven distributions in §6 from memory, then derive any two of them cold.

Week 2, Day 5 — Covariance by hand, then with numpy

What it requires: compute one covariance matrix by hand and verify with np.cov.

Data — 4 observations, 2 features:

X = [1, 2, 3, 4]        Y = [2, 4, 5, 4]
x̄ = 2.5                 ȳ = 3.75

Deviations and products:

Sample covariance matrix (divide by n−1 = 3):

       [ 5.00/3   3.50/3 ]     [ 1.6667   1.1667 ]
Σ̂  =   [ 3.50/3   4.75/3 ]  =  [ 1.1667   1.5833 ]

Correlation:

ρ = 1.1667 / (√1.6667 × √1.5833) = 1.1667 / (1.2910 × 1.2583) = 1.1667 / 1.6246 = 0.718

Identical to the population-convention answer in §7, because the n vs n−1 factor cancels in the ratio.

Verification:

np.cov(X, Y)      # → [[1.6667, 1.1667], [1.1667, 1.5833]]
np.corrcoef(X, Y) # → [[1.0, 0.7181], [0.7181, 1.0]]

Why n−1. The sample mean x̄ is itself estimated from the data, so deviations from it are systematically too small — dividing by n underestimates variance. Bessel's correction fixes the bias by accounting for the one degree of freedom spent on x̄. np.cov uses ddof=1 by default; np.std uses ddof=0. Mixing them silently is a classic source of wrong numbers.

The scaling trap. Covariance magnitude depends on units. Convert X from metres to centimetres and the covariance grows 100×, while ρ doesn't move. This is exactly why PCA on unstandardized heterogeneous features is meaningless, and it connects Day 5 back to Day 7 of Week 1.

Week 2, Day 6 — Information gain of a decision-tree split

What it requires: hand-compute the information gain of a split. Using the canonical 14-example PlayTennis dataset (9 positive, 5 negative), all values verified numerically.

Root entropy:

H(S) = −(9/14)log₂(9/14) − (5/14)log₂(5/14)
     = −(0.6429)(−0.6374) − (0.3571)(−1.4854)
     = 0.4098 + 0.5305 = 0.9403 bits

Candidate split: Outlook.

H(S | Outlook) = (5/14)(0.9710) + (4/14)(0) + (5/14)(0.9710) = 0.6935
IG(Outlook)    = 0.9403 − 0.6935 = 0.2467 bits

All four candidates:

ID3 splits on Outlook at the root, then recurses on the Sunny and Rain branches. Overcast is already pure and becomes a leaf immediately.

Five things this computation is teaching:

1. Entropy of a pure node is 0; of a 50/50 node is 1 bit. Those are the anchors — if a hand computation falls outside [0, 1] for a binary target, you made an arithmetic error.
2. Information gain is always ≥ 0. Conditioning never increases expected entropy. If you compute a negative IG, recheck the weighting.
3. The weights matter. H(S|A) is a weighted average by branch size, not a plain average. Overcast's zero entropy only helps in proportion to its 4/14 share.
4. IG is biased toward high-cardinality attributes. An ID column would split every example into its own pure branch and score maximum gain while generalizing not at all. Gain ratio (C4.5) divides by the split's intrinsic information −Σ (|Sᵥ|/|S|) log₂(|Sᵥ|/|S|) to correct this. Expect this as an exam question.
5. Gini gives nearly the same tree. For the root, Gini = 1 − (9/14)² − (5/14)² = 1 − 0.4133 − 0.1276 = 0.4592. It's cheaper (no logarithm) and ranks splits almost identically — which is why sklearn defaults to it and why the criterion choice rarely changes your Assignment 1 conclusions.

Week 2, Day 7 — Bias–variance decomposition, derived

What it requires: derive it from scratch using linearity of expectation. This is the most quoted result in the course and the one most often recited without understanding.

Setup. True relationship y = f(x) + ε where E[ε] = 0 and Var(ε) = σ². We fit f̂(x) on a random training set D; f̂ is therefore itself random. Fix a test point x.

Goal: decompose E[(y − f̂(x))²], where the expectation is over both the noise ε and the draw of D.

Step 1 — insert and subtract f(x):

E[(y − f̂)²] = E[(f + ε − f̂)²]
            = E[(f − f̂)²] + 2·E[ε(f − f̂)] + E[ε²]

Step 2 — kill the cross term. ε is independent of the training set, and E[ε] = 0:

E[ε(f − f̂)] = E[ε] · E[f − f̂] = 0

And E[ε²] = Var(ε) + (E[ε])² = σ². So:

E[(y − f̂)²] = E[(f − f̂)²] + σ²

Step 3 — decompose the remaining term. Let f̄ = E[f̂], the average prediction over all possible training sets. Insert and subtract it:

E[(f − f̂)²] = E[(f − f̄ + f̄ − f̂)²]
            = (f − f̄)² + 2(f − f̄)·E[f̄ − f̂] + E[(f̄ − f̂)²]

The middle term vanishes because E[f̄ − f̂] = f̄ − E[f̂] = 0, and (f − f̄) is a constant with respect to D.

Result:

E[(y − f̂(x))²]  =  (f(x) − E[f̂(x)])²  +  E[(f̂(x) − E[f̂(x)])²]  +  σ²
                 =        Bias²         +          Variance        +  Irreducible

Reading the three terms:

Diagnosing from curves — the practical payoff.

• Learning curve (error vs training-set size): high train error and high validation error converging to a plateau → high bias. Low train error with a persistent large gap that shrinks as n grows → high variance.
• Validation curve (error vs model complexity): train error falls monotonically; validation error is U-shaped. The minimum is the bias–variance sweet spot.

How this maps to specific algorithms in the course:

• Decision tree depth ↑ → bias ↓, variance ↑
• k-NN k ↑ → bias ↑, variance ↓ (k=1 is minimum bias, maximum variance)
• SVM C ↑ → bias ↓, variance ↑
• Neural net width/epochs ↑ → bias ↓, variance ↑
• Bagging / random forests attack variance by averaging decorrelated high-variance learners; bias stays roughly constant
• Boosting attacks bias by sequentially fitting the residuals of weak (high-bias) learners

Caveat worth knowing. The classic U-shaped curve is not universal — very overparameterized models can show "double descent," where test error falls again past the interpolation threshold. The decomposition above still holds; the assumption that variance grows monotonically with parameter count is what breaks.

Week 3, Days 1–2 — BFS, DFS, UCS implemented

What it requires: implement all three on a grid and observe the behavioural differences.

The test environment: a 10×10 grid, start (0,0), goal (9,9), 4-connected moves, unit costs, with two walls forming a snake — a vertical wall at x=3 for y ∈ [0,6] and another at x=6 for y ∈ [3,9]. That leaves 86 reachable cells and forces a detour, so a naive heuristic can't just walk diagonally.

Shared skeleton. All three algorithms are the same loop; only the frontier structure changes.

def search(start, goal, frontier_pop, frontier_push):
    frontier = init([start]); came = {start: None}; explored = set()
    while frontier:
        node = frontier_pop()
        if node in explored: continue
        explored.add(node)
        if node == goal: return reconstruct(came, goal)
        for child in neighbors(node):
            if child not in explored:
                came[child] = node
                frontier_push(child)
    return None

• BFS — collections.deque, popleft(). Mark nodes as seen when generated, not when expanded, or you duplicate work.
• DFS — a plain list, pop(). Same code, different end of the list. That one-character difference is the whole algorithm.
• UCS — heapq keyed on g(n). Requires the "skip if already expanded" guard because a node can sit in the heap multiple times with different costs.

Measured results:

What the numbers are telling you:

1. BFS and UCS are identical here. With uniform step costs, g(n) = depth, so the priority queue orders nodes exactly the way the FIFO queue does. UCS only earns its extra machinery when edge costs vary.
2. DFS expanded fewer nodes but returned a worse path — 36 steps instead of 28. It got lucky on effort and unlucky on quality. Change the neighbour ordering and both numbers move unpredictably. DFS offers no guarantees about either.
3. BFS and UCS expanded all 86 reachable cells because the goal is in the far corner — the frontier had to sweep the entire space. This is the O(b^d) space problem made concrete: for a real problem with b=10, d=12, "sweep everything shallower than the goal" means 10¹² nodes.
4. DFS's real advantage is memory, not expansions. Its frontier held at most a few dozen nodes along one path; BFS's frontier held a growing fringe.

The bug to watch for: in graph search, add nodes to the explored set (or a "seen" set) so cycles don't cause infinite loops. Tree search without an explored set will loop forever on a grid, since (0,0) → (1,0) → (0,0) is a legal path.

Week 3, Days 3–4 — A* and the node-expansion comparison

What it requires: implement A* with Manhattan distance and compare expansions against UCS.

Implementation. Identical to UCS except the priority key:

heapq.heappush(frontier, (g[child] + h(child), g[child], child))
#                          ^^^^^^^^^^^^^^^^^^  f(n) = g(n) + h(n)

The second tuple element (g) is a tie-breaker; without it Python tries to compare the coordinate tuples, which works but breaks the moment your states aren't orderable.

Measured results on the same grid:

Reading the table — this is the entire lesson of A:*

1. h = 0 reduces A to UCS exactly.* 86 expansions, identical behaviour. A* is not a different algorithm; it's UCS with an informed priority.
2. Manhattan dominates Euclidean on a 4-connected grid. Both are admissible (neither can overestimate when diagonal moves are illegal), but Manhattan is always ≥ Euclidean, so by the dominance theorem it expands no more nodes — 74 vs 77, confirmed. Rule: among admissible heuristics, always pick the largest.
3. The savings are real but modest here (86 → 74, about 14%) because the walls make the Manhattan estimate badly wrong in the detour region — the heuristic doesn't know about obstacles. On an open grid the same heuristic would cut expansions dramatically. Heuristic quality, not heuristic existence, drives the win.
4. Weighted A (w=2) expanded only 59 nodes* — a 31% saving over UCS — and on this particular map still happened to find the 28-step path. But 2h can overestimate, so the optimality guarantee is gone; weighted A* only promises a solution within a factor w of optimal. Getting the optimal answer once is not evidence the guarantee holds.

Admissibility vs consistency, checked concretely. Manhattan distance on a unit-cost grid is consistent: moving one step changes h by at most 1, and the step cost is exactly 1, so h(n) ≤ c(n,n') + h(n') always holds. That's why the graph-search version above is safe to write with a simple "skip if expanded" guard. With an admissible-but-inconsistent heuristic, you would need to reopen closed nodes when a cheaper path to them is discovered.

Constructing admissible heuristics — the standard recipe. Relax the problem. For the 8-puzzle:

• Relax "a tile can move anywhere" → misplaced-tile count h₁
• Relax "a tile can move to any adjacent square, occupied or not" → Manhattan distance h₂
• h₂ ≥ h₁ everywhere, so h₂ dominates. Any exact solution to a relaxed problem is an admissible heuristic for the original — that's the general theorem.
• max(h₁, h₂, …) of several admissible heuristics is admissible and dominates all of them.

Week 3, Day 5 — The complexity table, derived and measured

What it requires: reproduce §9's table from memory, then verify empirically. Here is where each entry comes from.

Counting nodes in a uniform tree. A tree with branching factor b has bᵏ nodes at depth k. Levels 0 through d total:

1 + b + b² + … + b^d = (b^(d+1) − 1)/(b − 1) = O(b^d)

The last level dominates; every complexity entry in the table is a variation on this sum.

• BFS O(b^d) time and space. It expands every node shallower than the goal, and the frontier at depth d holds O(b^d) nodes simultaneously.
• DFS O(b^m) time, O(bm) space. Worst case it explores the entire tree to depth m. But it only stores the current path (m nodes) plus the unexpanded siblings at each level (b−1 each) → O(bm). That's linear, not exponential. This is DFS's entire reason to exist.
• UCS O(b^(1+⌊C*/ε⌋)). UCS expands nodes in order of g, so it processes everything with cost < C*. With minimum step cost ε, the effective depth is ⌊C*/ε⌋. When all costs equal 1, this collapses to O(b^d) and UCS = BFS. The +1 accounts for UCS expanding the goal only after popping it, one level later than BFS.
• IDS O(b^d) time, O(bd) space. Derived below.
• Bidirectional O(b^(d/2)). Two frontiers of depth d/2 meeting in the middle: 2b^(d/2) ≪ b^d. For b=10, d=12, that's 2×10⁶ instead of 10¹² — six orders of magnitude, far more than any constant-factor optimization can buy.

The IDS re-expansion question, measured. IDS re-runs depth-limited DFS at limits 0, 1, …, d. Nodes at depth i are generated (d + 1 − i) times:

IDS nodes = (d+1)b⁰ + (d)b¹ + (d−1)b² + … + 1·b^d
BFS nodes = b⁰ + b¹ + … + b^d

Computed for b = 10, d = 5:

BFS generated : 111,111
IDS generated : 123,456
ratio         : 1.111×

11% overhead to trade O(b^d) space for O(bd) space. As b grows the overhead shrinks toward b/(b−1); at b=2 it's 2×, still only a constant. The intuition: the deepest level is generated once, and it contains more nodes than every shallower level combined.

The measured completeness/optimality claims from the grid experiment above:

Day 5 checkpoint: write out the nine-row table from memory, then justify each O(·) in one sentence.

Week 3, Days 6–7 — The scikit-learn warm-up, run

What it requires: load a dataset, build a scaling + decision-tree pipeline, tune with GridSearchCV, and plot learning and validation curves. Here is the exercise completed on the Wine dataset (178 samples, 13 features, 3 classes).

The code:

from sklearn.datasets import load_wine
from sklearn.model_selection import (train_test_split, GridSearchCV,
                                     learning_curve, validation_curve, StratifiedKFold)
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.tree import DecisionTreeClassifier

X, y = load_wine(return_X_y=True)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3,
                                      random_state=42, stratify=y)

pipe = Pipeline([("scale", StandardScaler()),
                 ("clf",   DecisionTreeClassifier(random_state=42))])

grid = {"clf__max_depth":        [1, 2, 3, 4, 5, 6, 8, 10, None],
        "clf__min_samples_leaf": [1, 2, 5, 10],
        "clf__criterion":        ["gini", "entropy"]}

cv = StratifiedKFold(5, shuffle=True, random_state=42)
gs = GridSearchCV(pipe, grid, cv=cv, scoring="accuracy", n_jobs=-1).fit(Xtr, ytr)

Results:

best params      : criterion='gini', max_depth=3, min_samples_leaf=1
best CV accuracy : 0.8950
held-out test    : 0.9630

Learning curve (fixed at the best estimator, 5-fold CV):

Reading it: train accuracy pinned near 1.0 while CV accuracy climbs and the gap narrows from 0.39 to 0.09 — the signature of a variance-limited model. The curves are still converging at n=99, so more data would help. If the two curves had flattened together at a mediocre value, that would be bias instead, and more data would be wasted effort. Note the non-monotonic dip at n=81: with 178 samples the CV estimates are noisy, so read the trend, not individual points.

Validation curve over max_depth:

Reading it — this is the bias–variance derivation from Week 2 Day 7, made visible:

• Depth 1 is underfitting. Train 0.673, CV 0.646, tiny gap. One split cannot separate three classes. High bias, low variance.
• Depth 3 is the sweet spot. CV accuracy peaks at 0.895.
• Depth 4+ is overfitting. Train hits 1.000 while CV drops to 0.878 and the gap widens to 0.122.
• Curves flatten past depth 6 because the tree stops growing — with 124 training samples and clean class structure, it achieves purity around depth 5 and further depth allowance is inert. Not every hyperparameter range produces movement; say so in your writeup rather than pretending the plateau is a finding.

Five habits this exercise is drilling — all of which are graded in CS 7641 Machine Learning:

1. Scale inside the Pipeline, never before the split. StandardScaler fitted on the full dataset leaks test-set statistics into training. Inside a pipeline, GridSearchCV refits the scaler on each CV fold correctly. Data leakage is the most common silent error in Assignment 1.
2. Stratify the split. stratify=y preserves class proportions. On a 3-class dataset of 178 samples an unstratified split can badly skew a fold.
3. Never tune on the test set. Select with cross-validation on the training data; touch the held-out set exactly once, at the end. Here CV said 0.895 and test said 0.963 — the test set happened to be easy, which is precisely why you don't tune against it.
4. Report the gap, not just accuracy. The train–CV gap is your empirical variance estimate and the thing your analysis should discuss.
5. Fix random_state everywhere. Splits, CV shuffling, and the estimator. Your results must reproduce, and grading rewards being able to explain a number rather than regenerate a different one.

Extension for the last day: swap DecisionTreeClassifier for KNeighborsClassifier, SVC, MLPClassifier, and AdaBoostClassifier, keeping the pipeline and curve code identical. That is structurally the whole of Assignment 1 — five learners, two datasets, learning and validation curves, and an analysis of what each curve says about bias and variance. If you can do it now, you start the course ahead.

Final self-assessment

Go back to the nine questions in §1. For each one, you should be able to produce, without notes:

1. A characteristic polynomial and its eigenvectors ✅ (§15 W1 D3–4 — seven worked matrices)
2. A full SVD by hand plus its rank-1 truncation error ✅ (§15 W1 D5–6)
3. All four metric axioms and a counterexample for each ✅ (§4)
4. A base-rate posterior computed correctly ✅ (§15 W2 D1–2 — five problems)
5. Mean and variance of seven standard distributions, derived ✅ (§15 W2 D3–4)
6. A covariance matrix by hand, with the right denominator ✅ (§15 W2 D5)
7. BFS, DFS, and A* traced and implemented ✅ (§15 W3 D1–4)
8. The complexity table with a justification per row ✅ (§15 W3 D5)
9. An end-to-end scikit-learn pipeline with tuned hyperparameters and diagnostic curves ✅ (§15 W3 D6–7)

That's nine Yes answers, each backed by something you've actually done rather than read.

Source: Team Lead & Staff Engineer · TeamLeadStaffEngineer.md · updated 2026-08-03 · 🔒 secret gist

Synced verbatim from gist.github.com/bl9.

Team Lead & Staff Engineer Interview Prep Plan

Table of Contents

Part I — Interview Mechanics

1. What Actually Gets Scored
2. Self-Assessment: Find Your Gaps First
3. The 8-Week Plan
4. Track A — Coding
5. Track B — System Design (Core)
6. Track C — System Design (Your Specialization Edge)
7. Track D — Architecture Deep Dive on Past Work
8. Track E — Leadership & Behavioral
9. Track F — The Rounds People Don't Prepare For
10. Hard Loops: Company-by-Company Breakdown
11. Above-and-Beyond Differentiators
12. Questions to Ask Directors
13. Mock Interview Schedule
14. Resource List

Part II — Deep Technical Domains

15. AI, GenAI, LLM & Agentic Systems
    • 15.1 What the 2026 loop tests · 15.2 Model fundamentals · 15.3 Retrieval & RAG · 15.4 Agentic systems · 15.5 Evaluation · 15.6 Serving & inference · 15.7 Cost engineering · 15.8 Safety & governance · 15.9 Classical ML · 15.10 Design questions
16. Context, Prompt & Graph Engineering
    • 16.1 The distinction · 16.2 Context pipeline · 16.3 Window management · 16.4 Prompting as engineering · 16.5 Graph engineering & GraphRAG
17. Advanced Backend: Streaming, Reactive, APIs
    • 17.1 Kafka & Flink · 17.2 Java reactive, Reactor, WebFlux, virtual threads · 17.3 GraphQL & Netflix DGS · 17.4 gRPC & binary protocols · 17.5 API decision matrix · 17.6 Distributed transactions
18. Real-Time Delivery, CDN, Caching & Edge
    • 18.1 WebSockets · 18.2 SSE · 18.3 HTTP caching · 18.4 CDN architecture · 18.5 Application cache layers
19. Compute: Serverless, Containers, Kubernetes, OS & Kernel
    • 19.1 Serverless · 19.2 Containers & kernel primitives · 19.3 Kubernetes · 19.4 OS & kernel fundamentals
20. Storage, Scaling & Data Platform
    • 20.1 DynamoDB · 20.2 Cassandra/Scylla · 20.3 MongoDB · 20.4 OpenSearch · 20.5 Relational at scale · 20.6 Lakehouse · 20.7 Decision table
21. Security: OAuth, Zero Trust, AppSec & Network
    • 21.1 OAuth/OIDC · 21.2 Zero Trust · 21.3 AppSec · 21.4 Vulnerability management & patching · 21.5 SDN/SD-WAN/SASE · 21.6 Compliance
22. Frontend & Full-Stack for Leads
    • 22.1 React · 22.2 State layers, Redux, thunk vs saga · 22.3 Cross-cutting frontend architecture
23. The Team Leadership Operating Playbook
    • 23.1 Unblocking · 23.2 Growing people · 23.3 PR review · 23.4 Planning & scheduling · 23.5 Product partnership · 23.6 Promotions & retention · 23.7 Hiring · 23.8 Communication · 23.9 Metrics
24. AI as a Cross-Cutting Force
    • 24.1 Leadership frame · 24.2 Layer by layer · 24.3 Questions to have answers to
25. Rapid-Fire Drill Bank
26. Revised Study Calendar (12 Weeks)
27. Final Calibration

Part III — Gap Closure

28. Observability & SRE (Full Depth)
    • 28.1 SLO engineering & burn-rate alerting · 28.2 OpenTelemetry & the three pillars · 28.3 Chaos engineering · 28.4 Load & performance testing · 28.5 Incident management
29. Architecture Discipline: DDD, Team Topologies & Decision-Making
    • 29.1 Domain-Driven Design · 29.2 Microservices vs modular monolith · 29.3 Team Topologies · 29.4 Decision machinery (DACI, ADRs, C4, one-way doors)
30. Delivery Engineering: CI/CD, Testing Strategy & Experimentation
    • 30.1 Trunk-based development · 30.2 Feature flags · 30.3 Testing strategy & contract testing · 30.4 Release engineering · 30.5 Experimentation platform
31. Standards & Frameworks Reference Card
    • DORA · SPACE · DX Core 4 · DevEx · SRE · Well-Architected · 12-Factor · FinOps · Team Topologies · SLSA · NIST CSF · NIST AI RMF/ISO 42001 · WCAG · C4
32. Multi-Region, DR & Business Continuity
33. The Offer Stage: Closing Above and Beyond
34. Updated Weekly Integration

Part IV — Patterns, Contracts, and the Human Layer

35. Design Patterns & Code Architecture
    • 35.1 SOLID with mature caveats · 35.2 The GoF subset that appears · 35.3 Enterprise patterns (Repository, Unit of Work, ACL) · 35.4 Hexagonal/Clean, CQRS, anti-patterns, refactoring vocabulary · 35.5 How it shows up in interviews
36. SLA vs SLO vs SLI — the Contractual Layer
    • SLA remedies & fine print · dependency SLA composition · OLAs · per-tenant SLAs · STAR ↔ SCOR mapping
37. The Question Playbook, by Interviewer
    • 37.1 Recruiter · 37.2 Hiring manager · 37.3 Peers & future reports · 37.4 Director/skip · 37.5 VP/CTO · 37.6 Product partner · 37.7 Bar raiser · 37.8 Universal closers · 37.9 Reverse due-diligence red flags
38. Signals of Seasonality — the Unasked-For Essentials
    • 38.1 Executive communication (BLUF) · 38.2 Handling unknowns · 38.3 Scar-tissue stories · 38.4 "It depends" done right · 38.5 Whiteboard & remote mechanics · 38.6 Operator literacies (budget, vendors, glue work, former peers, legacy) · 38.7 Follow-up etiquette · 38.8 Drills 53–60
39. Deployment & Progressive Delivery (Consolidated Deep Dive)
    • 39.1 Strategy matrix (rolling, blue/green, canary, shadow, rings) · 39.2 Traffic-shifting mechanics · 39.3 Automated canary analysis · 39.4 Canary vs A/B · 39.5 State, data & rollback · 39.6 The pipeline as a system · 39.7 Drills 61–66

Part V — Expanded Reference (full depth: code, case studies, primary sources)

40. Distributed Systems & Performance Foundations
    • 40.1 Latency numbers, Little's Law, queueing, USL, tail-at-scale, benchmarking discipline · 40.2 Paxos, Raft, ZAB — mechanics and production use · 40.3 Replication, consistency models, time (TrueTime/HLC), CRDTs · 40.4 Consistent hashing, jump/Maglev/rendezvous, range partitioning, resharding
41. LLM Serving, Inference & the Economics of Tokens
    • 41.1 Prefill vs decode · 41.2 KV cache math, GQA, PagedAttention, prefix caching · 41.3 Continuous batching + scheduler implementation · 41.4 FlashAttention, speculative decoding, quantization, parallelism · 41.5 Serving stacks · 41.6 Cost engineering with worked math · 41.7 LLM observability
42. Architecture Patterns, Fully Worked
    • 42.1 CQRS — the adoption ladder, Level 1 & Level 4 code, projections, the five eventual-consistency fixes, TAO/Venice/Netflix case studies · 42.2 Event Sourcing — event store schema, optimistic concurrency, snapshots, upcasting, crypto-shredding for GDPR, why Kafka isn't an event store · 42.3 Sagas — orchestration vs choreography, compensation code, Temporal/Cadence/Step Functions · 42.4 Transactional Outbox — SQL, Debezium config, polling vs CDC · 42.5 Repository & Hexagonal, concretely
43. Worked System Design Answers
    • 43.1 Distributed rate limiter (full: algorithms table, Redis Lua, two-tier lease architecture, Stripe/Cloudflare/Envoy references, follow-ups) · 43.2 RAG with document-level access control (full: filtered-ANN recall problem, two-layer authz, contextual chunking, RRF, eval suite, degradation matrix)
44. Worked Design Answers — AI & LLM Systems
    • 44.1 LLM gateway (routing, escalation, two-tier caching, failover, chargeback) · 44.2 Multilingual semantic search (index topology, language-specific pitfalls, vector scaling math, eval without judgments) · 44.3 Agent platform with sandboxed tools (four security gates, lethal trifecta, loop termination) · 44.4 Eval pipeline gating CI · 44.5 Cost attribution across 40 teams
45. Worked Design Answers — The Classics
    • News feed · Notifications · Job scheduler · Metrics pipeline · Ad click aggregation · Payments ledger · Ride dispatch · Object storage/file sync · Ticketing under contention · Multi-region active-active KV
46. Storage Engines & Databases, Expanded
    • 46.1 LSM vs B-tree, compaction strategies, tombstones, RocksDB tuning · 46.2 Postgres MVCC, vacuum, XID wraparound, index types, reading query plans, PgBouncer · 46.3 DynamoDB single-table design · 46.4 Choosing a database
47. Retrieval, Search & Ranking, Expanded
    • 47.1 Inverted index, Lucene segments, BM25 derivation · 47.2 HNSW/IVF-PQ/DiskANN comparison · 47.3 Multi-stage ranking funnel, LTR, features · 47.4 NDCG/MRR, interleaving, position bias, IPS
48. Leadership Scenarios — Full Worked Answers
    • Toxic reviewer · Missed commitments · PM overcommits · Impossible date · Duplicate teams · AI review-queue debt · Reliability budget to a VP · Not-ready promotion · Post-reorg morale · Down-leveled offer
49. Complete Drill Bank — Answer Key — all 66 drills answered
50. Closing Note on Using This Document
51. Gap Register & Expansion Queue

Part VI — The Engineering Management Workshop

52. Team Architecture & Organizational Design
    • 52.1 The Spotify model and why it failed (squads/tribes/chapters/guilds, the four failure modes, three ways to answer) · 52.2 Alternatives compared: two-pizza + STL, Team Topologies, handbook-first, context-not-control, Shape Up, feature crews · 52.3 Microservices & cloud native as org decisions
53. Sizing, Estimation & Assigning Work
    • 53.1 Planning poker, t-shirt, affinity, GitLab weights, Shape Up appetite, Monte Carlo forecasting · 53.2 The Goodhart critique of story points · 53.3 Breaking down an epic — full worked example · 53.4 Assigning work: skill matrix, bus factor, glue work
54. Jira & Azure DevOps — Making the Tool Tell the Truth
    • 54.1 Hierarchy, DoR/DoD · 54.2 Config practices per tool (workflows, components, WIP limits, automation, area vs iteration paths, branch policies) · 54.3 Metrics to read and to refuse
55. The GitLab Workshop
    • Handbook-first · DRI · Iteration & MVC · weights, milestones, async defaults · the honest critique
56. Google, Microsoft, Amazon & Netflix — What Each Proved
    • Project Oxygen & Project Aristotle · two-pizza/STL/PR-FAQ/six-pagers/bar raiser · stack-ranking reversal & 1ES · context-not-control, informed captain, keeper test
57. Management Workshop — Interview Q&A, Multiple Framings
    • Seven core questions, each answered three ways: screen / depth / story
58. Workshop Drills (67–86)

Part VII — Answers to Everything Left Open

59. Questions to Ask — What You're Listening For
    • Every question from §12 and §37 with: why it works · the green flag · the red flag · your follow-up · what you do with the answer. Covers hiring manager, director/skip-level, peers and future reports, VP/CTO, the universal closers, and the reverse due-diligence probe table.
60. Stated-But-Unexplained — The Answers
    • 60.1 Agent determinism & replay (full trace schema, three replay levels, what you lose without it, three-register answer) · 60.2 Idempotency & effectively-once · 60.3 Blast radius & cells · 60.4 Backpressure vs shedding vs admission control · 60.5 Feature stores & point-in-time correctness · 60.6 Sticky sessions starving the canary · 60.7 HNSW delete degradation · 60.8 Composition over inheritance

1. What Actually Gets Scored

Senior interviews test whether you can solve a problem. Staff and TL interviews test whether you can pick the problem, frame it, and get other people to solve it with you. Different bar, different prep.

Shared signals (Staff and TL)

Track-specific

Team Lead adds: performance conversations, hiring bar, delivery predictability, morale under pressure, stakeholder/PM negotiation, headcount and prioritization tradeoffs.

Staff adds: technical strategy over 12–24 months, cross-org standard-setting, deprecation/migration leadership, design review authority, "make the hard call in a room of senior people."

The single most common failure

Candidates tell senior-level stories in a staff-level interview. The story is about what they built, not how the org changed. Fix this in Track E before anything else.

2. Self-Assessment: Find Your Gaps First

Do this in one sitting, week 0. Score 1–5, honestly.

Coding

• Can I solve a medium in 20 min, clean, with tests, while talking?
• Can I do it in a shared editor with no autocomplete?
• Have I done a hard graph/DP problem in the last 30 days?

System design

• Can I do capacity math out loud without freezing (QPS, storage, bandwidth, memory)?
• Can I name 3 consistency models and when each is acceptable?
• Can I design for multi-region without hand-waving the write path?
• Can I draw and defend a rollback/migration strategy?

Deep dive

• Do I have a 45-min narrative of my hardest project with numbers, alternatives, and regrets?
• Can I whiteboard my current system from memory at 3 zoom levels?

Leadership

• Do I have 10 stories that cover conflict, failure, influence, mentoring, and prioritization?
• Can I tell any of them in 3 minutes without rambling?
• For TL: can I role-play a performance conversation without getting soft or harsh?

Anything scored 1–3 gets calendar time in the plan below. Anything at 4–5, don't over-study it.

3. The 8-Week Plan

Assumes ~12–15 hrs/week. Compress to 5 weeks by dropping Weeks 3 and 6 and doubling volume.

Week 1 — Foundation + story mining

• Build the story portfolio (Track E). This is the long pole; start it first.
• Fundamentals refresh: latency numbers, CAP/PACELC, quorum math, consistent hashing.
• 10 coding problems (easy/medium warm-up, arrays, hashmaps, two pointers).
• Write your deep-dive narrative outline (Track C).

Week 2 — Design core + coding volume

• 5 classic system designs, written out (rate limiter, URL shortener, notification system, distributed job scheduler, metrics pipeline).
• 15 coding problems: trees, graphs, BFS/DFS, heaps.
• Rewrite 3 stories from Week 1 in the SCOR format (Section 8).

Week 3 — Storage + streaming internals

• Deep dive: LSM vs B-tree, Kafka internals, Cassandra/DynamoDB partitioning, Postgres MVCC and replication.
• 3 designs: news feed, chat/messaging, ad click aggregation.
• 12 coding problems: intervals, binary search, sliding window.
• First mock: system design, external interviewer.

Week 4 — Reliability, scale, multi-region

• Topics: cell-based architecture, blast radius, circuit breakers, backpressure, graceful degradation, SLO/error budgets, idempotency and the outbox pattern.
• 3 designs: payments ledger, ride-hailing dispatch, multi-region active-active KV store.
• 12 coding problems: DP, backtracking, tries.
• Mock: behavioral/leadership.

Week 5 — Your specialization (the differentiator)

• Full Track C content: search, retrieval, ranking, RAG, agentic platforms, vector index scaling.
• Write 2 designs you could teach: "multilingual semantic search at 10K QPS" and "enterprise RAG with eval harness."
• 10 coding problems, mixed hard.
• Mock: deep dive on your own past work.

Week 6 — Leadership under pressure

• Role-play drills: underperformer, two senior engineers in conflict, PM pushing scope, director wants a date you can't commit to.
• Write a real design doc (5 pages) and a written critique of someone else's.
• Practice the "design doc review" and "code review" round formats.
• Mock: people-management round (TL) or cross-org influence round (Staff).

Week 7 — Company-specific

• Pick your top 3 targets. Study their loop format (Section 10), eng blog, open source, public architecture talks.
• One full-loop simulation in a single day: 2 coding + 1 design + 1 behavioral, back to back, no breaks. This tests stamina, which is what actually breaks people.
• Prepare per-company question lists and 30/60/90 plans.

Week 8 — Polish and taper

• Re-run only your weakest two rounds.
• Trim every story to 3 minutes.
• Light coding daily (2 problems, timed) — maintenance, not growth.
• Sleep. Do not cram new material in the last 3 days; it costs recall on the material you already have.

4. Track A — Coding

Staff and TL loops still have coding rounds at Google, Meta, Stripe, Databricks, Uber, and most AI labs. The bar isn't harder problems — it's cleaner code, better tests, and no flailing.

Volume target

• ~70–90 problems total, not 400. Depth over count.
• Distribution: 20% easy (warm-up/speed), 65% medium, 15% hard.

Pattern checklist (don't move on until each is automatic)

• Hash map / frequency counting
• Two pointers, sliding window
• Binary search — including "search on the answer"
• BFS / DFS / topological sort
• Union-find
• Heaps and top-K
• Intervals (merge, sweep line)
• Prefix sums and difference arrays
• Backtracking with pruning
• DP: 1D, 2D, knapsack, LIS, edit distance
• Tries
• Monotonic stack

Staff-specific coding expectations

• Talk about the API before the algorithm. Name types, name the contract.
• Write tests unprompted. Even 3 assertions. This is a differentiator at every level above senior.
• State complexity before coding, verify after.
• Handle the "make it production" follow-up: what breaks at 100× input, where does it go concurrent, what's the failure mode.
• Don't over-abstract. Staff candidates lose points for building a factory when a function was asked for.

Drill format

Timed, 35 min, out loud, in a plain editor. Record yourself once a week and watch it. Painful, effective.

5. Track B — System Design (Core)

5.1 Fundamentals you must have memorized

Latency numbers (order of magnitude is enough):

• L1 ~1 ns, main memory ~100 ns, SSD random read ~100 µs, network round trip same DC ~0.5 ms, cross-region ~50–150 ms, disk seek ~10 ms.

Capacity math you should do in 60 seconds:

• DAU → QPS (peak ≈ 3–5× average)
• Bytes/record × records/day → storage/year
• Working set → cache size → node count
• Read:write ratio → replication and sharding decision

Distributed systems core:

• CAP, and why PACELC is the more useful framing
• Consistency models: linearizable, sequential, causal, read-your-writes, eventual
• Quorum: R + W > N, and what sloppy quorums buy you
• Consensus: Raft leader election, log replication, why you don't want consensus in the hot path
• Consistent hashing + virtual nodes; when range partitioning beats it
• Idempotency keys, exactly-once as "at-least-once + dedupe"
• Outbox pattern, CDC, dual-write problem
• Backpressure, load shedding, admission control
• Rate limiting: token bucket, leaky bucket, sliding window counter, distributed rate limiting

Storage internals:

• LSM tree (write amplification, compaction, bloom filters) vs B-tree
• Kafka: partitions, ISR, consumer groups, rebalancing, retention, compaction
• DynamoDB/Cassandra: partition key design, hot partitions, LWT cost
• Postgres: MVCC, vacuum, index types, logical replication
• Object storage: S3 consistency, multipart, lifecycle, why it's the default data lake

Reliability:

• SLI/SLO/error budget, and how error budget changes release policy
• Circuit breaker, bulkhead, timeout + retry with jitter, retry storms
• Graceful degradation tiers (what do you turn off first)
• Blast radius and cell-based architecture
• Blue/green, canary, shadow traffic, feature flags, dark launch

Migration and rollout — heavily weighted at staff level, rarely prepared:

• Dual-write + backfill + read-verify + cutover + cleanup
• Strangler fig pattern
• Reversibility: what's the rollback at each phase
• How do you prove correctness during migration (shadow compare, sampled diffing)

5.2 Classic designs to write out (not just read)

1. Distributed rate limiter
2. Notification/fan-out system
3. News feed (push vs pull vs hybrid)
4. Chat / messaging with delivery guarantees
5. Distributed job scheduler with exactly-once semantics
6. Metrics/observability pipeline (ingest → aggregate → query)
7. Ad click aggregation (dedupe, late events, watermarks)
8. Payments ledger with idempotency and double-entry
9. Ride-hailing dispatch (geo-indexing, matching)
10. Object storage / file sync (Dropbox-style)
11. Multi-region active-active KV store
12. Ticketing/inventory with contention (Ticketmaster-style)

5.3 The staff-level design interview structure

Most candidates do requirements → boxes → done. Do this instead:

1. Clarify and scope (5 min). Who's the user, what's the SLA, what's out of scope. Write the non-functional requirements as numbers.
2. Capacity math (3 min). Out loud. This alone separates candidates.
3. API contract (3 min). Before any boxes.
4. Data model + partitioning key (5 min). The partition key choice is where most designs live or die.
5. High-level architecture (10 min).
6. Deep dive on the hardest 1–2 components (15 min). Ask the interviewer which one they want.
7. Failure modes, degradation, operations (7 min). What pages, what's the runbook, what's the blast radius.
8. Tradeoffs and what you'd do differently at 10× (5 min).

Say out loud, at least twice: "The alternative here was X; I'm not choosing it because Y; if Z changed I'd revisit." That sentence is the staff signal.

6. Track C — System Design (Your Specialization Edge)

Search, retrieval, ranking, and agentic systems are your moat. Most interviewers can't go deep here, which means you control the room — but only if you've rehearsed it.

6.1 Search & retrieval

• Inverted index internals, segment merges, refresh vs flush, near-real-time search
• OpenSearch/Elasticsearch: shard sizing math, replica strategy, hot/warm/cold tiers, index lifecycle, alias-based blue/green reindex
• Query understanding: tokenization, analyzers per language, stemming vs lemmatization, CJK segmentation, transliteration
• Multilingual: shared vs per-language index, cross-lingual embeddings, language detection failure modes, script normalization
• Relevance: BM25, learning-to-rank, hybrid (lexical + dense) with reciprocal rank fusion
• Evaluation: NDCG, MRR, recall@k, offline/online correlation, judgment collection

6.2 Vector search

• HNSW: graph structure, M and efConstruction/efSearch tradeoffs, memory formula (roughly d × 4 bytes × N for float32 plus graph overhead), why deletes are expensive
• IVF-PQ vs HNSW: memory vs recall vs build time
• Billion-scale: sharding by ID vs by cluster, routing, replica fan-out, cold start
• Filtered vector search: pre-filter vs post-filter and the recall cliff
• Index rebuild strategy without downtime

6.3 Recommendation systems

• Multi-stage: candidate generation → light ranker → heavy ranker → re-ranking/diversity/business rules
• Feature store: online/offline parity, point-in-time correctness, training/serving skew
• Embedding freshness, two-tower architectures, ANN retrieval for candidates
• Cold start (user and item), exploration vs exploitation, bandits
• Feedback loops and popularity bias — name this unprompted, it's a strong signal
• Evaluation: offline replay, interleaving, A/B tests, guardrail metrics, novelty/diversity metrics

6.4 RAG and LLM systems

• Chunking strategies and why fixed-size is usually wrong
• Hybrid retrieval + cross-encoder reranking, latency budget allocation
• Context assembly, citation grounding, hallucination guardrails
• Eval harness: golden set, LLM-as-judge with its failure modes, regression gates in CI
• Serving: KV cache, continuous batching, speculative decoding, quantization tradeoffs
• Cost model: tokens per request × price, caching layers, model routing (cheap model first, escalate)

6.5 Agentic platforms

• Tool routing and schema design, why tool descriptions are the real prompt
• Sandboxing and permission boundaries for tool execution
• Multi-step orchestration, retries, and loop-termination guarantees
• Observability: trace per step, token/cost attribution, replay
• Eval: task-level success rate, not per-step accuracy
• Failure containment: what does the agent do when the tool is down or the output is malformed

6.6 Designs to have ready to whiteboard

1. Multilingual semantic search over 500M docs, 10K QPS, p99 < 200 ms
2. Personalized recommendation serving with a 50 ms budget
3. Enterprise RAG with document-level access control
4. Online A/B testing and interleaving platform
5. LLM gateway with routing, caching, rate limiting, and cost attribution
6. Agent execution platform with sandboxed tools and full tracing

7. Track D — Architecture Deep Dive on Past Work

Usually 45–60 minutes on a system you built. Underprepared by almost everyone, and it's the round directors weight most heavily.

Prepare three zoom levels of your primary system

1. 30 seconds: what it does, who uses it, what it's worth.
2. 5 minutes: the architecture, the two hardest problems, the outcome with numbers.
3. 45 minutes: component-level detail, data flow, failure modes, the incident, the migration, the thing you'd redo.

The checklist your narrative must hit

• What was the business problem and how was success measured
• What were the constraints (latency, cost, team size, deadline, legacy)
• Which alternatives you seriously evaluated and the specific reason each lost
• What you got wrong and what it cost
• What you'd change with what you know now
• Where you were the decision-maker vs where you influenced someone else's decision

Numbers to have memorized

QPS, p50/p99, data volume, cost, team size, timeline, and the delta on the metric you moved. If you don't have exact numbers, use defensible estimates and say they're estimates.

The trap

Interviewers will poke at a design decision to see if you get defensive. The winning move: "That's a fair criticism — here's the constraint that drove it, and here's what I'd need to change to do it your way." Confidence without brittleness.

8. Track E — Leadership & Behavioral

8.1 Build a story portfolio, not answers to questions

Write 10–12 stories. Tag each with the competencies it covers. In the interview you map the question to a story, not to a memorized answer.

Stories you need:

1. The hardest technical decision you owned
2. A decision you reversed
3. A project that failed or got cancelled
4. Conflict with a peer or another team
5. Disagreement with your manager or a director
6. Influencing without authority across teams
7. Mentoring someone from struggling to strong
8. Prioritization: what you chose not to do and why
9. A major incident you led
10. A migration or deprecation you drove
11. Delivering under an unreasonable deadline
12. Tech debt vs feature pressure

Team Lead adds: 13. Handling an underperformer 14. A hiring decision (including one you got wrong) 15. Managing team morale through a bad quarter 16. Pushing back on a stakeholder's scope or timeline

8.2 Use SCOR, not STAR

STAR under-serves staff-level stories because it has no slot for judgment.

• S — Situation: context and constraints, 20 seconds
• C — Complication: why it was actually hard, what made it non-obvious
• O — Options: the 2–3 real alternatives and why each lost
• R — Result + Reflection: the number, and what you'd do differently

The O is the whole game. It's what makes a story sound like judgment instead of a resume bullet.

8.3 Calibration rules

• 3 minutes per story. Time yourself. Nobody has ever lost an offer for being too concise.
• Use "I" for your decisions and "we" for team execution. Getting this ratio wrong reads as either credit-stealing or passenger.
• Every story needs one number.
• If a story has no failure or regret in it, it isn't a staff story.

8.4 Team Lead role-play drills (practice out loud, with a person)

• Your strongest engineer is toxic in code review. Handle it.
• An engineer has missed three commitments in a row. Run the conversation.
• A PM promises a date to a customer without asking you. Respond.
• A director asks you to cut testing to hit a date. Respond.
• Two senior engineers deadlocked on a framework choice, and it's blocking the sprint.
• You inherit a team with low morale after a reorg. First 30 days?

For each: state your first move, the information you'd gather, and the line you wouldn't cross. That three-part structure makes vague answers concrete.

8.5 Staff-specific influence drills

• Two teams are building the same thing. Neither wants to stop. You have no authority over either.
• You believe the org's chosen architecture is wrong. You've been overruled once already.
• You need three teams to adopt a standard that makes their next quarter slower.

9. Track F — The Rounds People Don't Prepare For

• Design doc review. Given a 4-page doc, critique it live. Practice: write one, then critique a real RFC (Rust RFCs, Kubernetes KEPs, Kafka KIPs are all public and excellent training material).
• Code review round. Given a PR, find correctness, security, and maintainability issues. Practice on open-source PRs. Prioritize your comments — blocking vs nit — that prioritization is the signal.
• Debugging round. A repo with failing tests; find and fix. Practice: clone something unfamiliar, break it, fix it under time.
• Incident simulation. Live "the graphs look like this, what now." Practice the loop: stop the bleeding → mitigate → diagnose → communicate → postmortem. Say "I'd mitigate before I diagnose" out loud; many candidates skip straight to root cause.
• Take-home + presentation. Scope small, ship clean, write a README with tradeoffs and what you'd do with more time. The README is what gets graded at staff level.
• Product/business sense. "How would you prioritize this roadmap?" Have an opinion about your users and your metrics.

10. Hard Loops: Company-by-Company Breakdown

Formats shift; verify with your recruiter. This is the shape as of the most recent public reporting.

Google — Staff (L6) / TLM

• 2 coding rounds (still LeetCode-style, medium-hard), 1–2 system design, 1 "Googleyness & Leadership."
• L6 requires demonstrated cross-team scope. Hiring committee reads a packet — your interviewers must be able to write down your scope. Give them quotable lines.
• Design rounds go deep on data modeling and failure handling.
• Prep weight: coding 30%, design 40%, leadership 30%.

Meta — E6 / Engineering Manager

• IC: 2 coding (two problems per 45-min round — speed matters), 1 system design, 1 "Jedi" behavioral.
• EM: system design, people management, project retrospective, sometimes coding.
• E6 needs org-level impact stories. "I built X" is E5. "I changed how three teams do X" is E6.
• Prep weight: coding speed is the top failure cause; drill 2-problems-in-45-min explicitly.

Amazon — Principal (L7) / SDM

• Leadership Principles dominate. Expect 10–16 LP questions across the loop, plus a Bar Raiser.
• Every LP answer needs data. "Dive Deep" means they will ask for the number three layers down.
• Also: system design, and for L7 a "technical vision" discussion.
• Prep weight: build 2 stories per LP, 16 LPs. This is the single most story-intensive loop in the industry.

Stripe

• Integration round (build against a real API), debugging round (fix a broken repo), system design, and a values/behavioral round.
• Practical over algorithmic. Your editor fluency and debugging method are visible.
• Prep weight: debugging and pragmatic coding 50%.

Netflix — Senior/Staff

• Culture-memo alignment is a real filter: context not control, freedom and responsibility, "keeper test."
• Senior-heavy org, so expect very deep technical conversation and expect to justify autonomy.
• Prep weight: deep dive 40%, culture 30%, design 30%.

Databricks / Snowflake / Confluent

• Hard distributed systems internals plus genuinely hard coding.
• Expect questions on query execution, storage formats, consistency, and concurrency.
• Prep weight: storage/streaming internals 50%.

Uber / Lyft / DoorDash

• High-scale system design with real domain constraints (geo, matching, dispatch, pricing).
• Coding is medium-hard, design is the differentiator.

Shopify (Toronto)

• "Life Story" interview — a structured walk through your career. Prepare a narrative arc, not a list of jobs.
• Pair programming in a real repo, technical deep dive.

OpenAI / Anthropic / AI labs

• Practical coding, often agentic (use the tools, work in a real codebase), take-home with a follow-up deep dive, and a strong emphasis on judgment and safety-mindedness.
• They test whether you can move fast in unfamiliar code. Practice: contribute a real fix to an open-source repo you've never seen, timed.

Nvidia / Cisco / systems companies

• Performance, concurrency, memory, and profiling. Expect C++/systems questions if the role is close to the metal.

11. Above-and-Beyond Differentiators

These are what make a director remember you.

1. Bring an artifact. A one-page architecture diagram or a design doc you can share (sanitized). Almost nobody does this.
2. Write a 30/60/90 plan for their team and send it after the onsite. For a TL role this is close to decisive. Structure: first 30 = listen and map (name what you'd read, who you'd meet, what you'd measure), 60 = one visible fix, 90 = a strategy proposal.
3. Know their public engineering output. Their eng blog, conference talks, open source. Reference it specifically: "In your post on X you mentioned Y — how did that land?"
4. Speak in operational metrics. p99, error budget, DORA metrics, cost per query, on-call load. Leads who talk about cost and toil sound senior instantly.
5. Name your own weaknesses before they find them. "The gap in my background is Z; here's how I'd close it in the first quarter."
6. Have a technical opinion. Not a hot take — a defended position on something in their domain. Directors hire people with a point of view.
7. Send a follow-up that adds value, not thanks. One paragraph continuing the design discussion, or the diagram you sketched, cleaned up.
8. Prepare a diagnostic question set — the questions you'd ask the team in week one. Sharing this signals you already think like the lead.

12. Questions to Ask Directors

Skip the generic ones. These probe real things and signal seniority.

About the role

• What does success look like at 6 months, and who decides?
• Is this role backfilling someone, or is it new scope? What happened to the previous lead?
• What's the split between technical direction and people management you actually expect?

About the team

• What's the team's biggest source of toil right now?
• How much of the roadmap is committed vs discretionary?
• Where does the team's on-call pain come from?

About the org

• How do technical decisions that span teams get made here?
• What's the last significant architectural decision, and how was it reached?
• What's the thing about this org you'd change if you could?

About you as a manager (ask the director)

• How do you like to be disagreed with?
• What's your escalation threshold — when do you want me to bring you in?
• What did the last person who succeeded in a role like this do differently?

The high-leverage closer

• "Is there anything in my background that gives you hesitation? I'd rather address it now than leave it open."

13. Mock Interview Schedule

Real mocks with real humans, not solo practice. Minimum 6 before your first real onsite.

Rules: record everything. Watch at 1.5×. Note filler words, rambling, and the moment you lost the interviewer. Fix one thing per mock.

14. Resource List

System design

• Designing Data-Intensive Applications — Kleppmann (chapters 5–9 are the core)
• Database Internals — Petrov (for storage-engine depth)
• Company engineering blogs: Uber, Netflix, Meta, Discord, Cloudflare, Stripe
• Public design docs: Kubernetes KEPs, Kafka KIPs, Rust RFCs (for the design-review round)

Coding

• NeetCode 150 for pattern coverage
• Timed sessions in a plain editor, not an IDE

Leadership

• The Staff Engineer's Path — Reilly (the definitive staff-scope framing)
• Staff Engineer — Larson
• An Elegant Puzzle — Larson (for TL/EM org questions)
• The Manager's Path — Fournier (TL chapter specifically)

Your domain

• HNSW paper (Malkov & Yashunin), FAISS docs
• Elasticsearch/OpenSearch internals docs on shards, segments, and lifecycle
• Recent RAG and agent evaluation literature — pick 5 papers and know them well enough to critique

PART II — Deep Technical Domains

15. AI, GenAI, LLM & Agentic Systems

15.1 What the 2026 loop actually tests

The content shifted hard. Classical ML theory (backprop, CNNs, gradient descent) is now maybe a quarter of technical rounds; the rest is RAG architecture, evaluation, agents, and production concerns. The four things a modern loop probes that a 2022 loop never did:

1. System design on top of a model you don't control
2. Judgment about retrieval and evaluation
3. Whether you can build and debug the integration by hand
4. Production sense: cost, latency, and the quiet ways these systems fail

Definitions are free now. Judgment is what's being bought.

15.2 Model fundamentals you must hold cold

• Transformer: attention (Q/K/V), multi-head, positional encoding (RoPE, ALiBi), why context length is quadratic in attention and what mitigates it (FlashAttention, sliding window, sparse attention)
• Decoder-only vs encoder-decoder vs encoder-only (and why BERT-family still wins for reranking)
• Tokenization: BPE, why token counts differ across languages (directly relevant to multilingual work — non-Latin scripts can cost 2–4× the tokens)
• Prefill vs decode: prefill is compute-bound, decode is memory-bandwidth-bound. This single distinction explains most serving architecture.
• KV cache: size formula ≈ 2 × layers × heads × head_dim × seq_len × batch × bytes_per_param. Know that it, not weights, is what actually limits your batch size.
• MoE: sparse activation, expert routing, why parameter count ≠ compute cost
• Fine-tuning ladder: prompting → few-shot → RAG → LoRA/QLoRA → full SFT → preference tuning (RLHF, DPO). Know the cost and the "when."
• Quantization: FP16/BF16 → FP8 → INT8 → INT4; GPTQ, AWQ, GGUF. Quality/latency/memory tradeoffs.
• Distillation: use production traffic from a large model to train a small one. The best cost lever nobody mentions.
• Sampling: temperature, top-p, top-k, min-p, repetition penalty, and why greedy isn't always right
• Structured output: JSON mode, constrained decoding / grammar-based sampling, tool-call schemas

15.3 Retrieval & RAG (beyond the basics)

Chunking

• Fixed-size is the default and usually wrong. Know: recursive character splitting, semantic chunking, structure-aware (headings, code blocks), parent-document retrieval, late chunking (embed the full doc, then pool per chunk), contextual retrieval (prepend an LLM-generated summary of the doc to each chunk)
• Overlap tradeoff: recall vs index bloat vs duplicate context

Retrieval

• Hybrid: BM25 + dense, fused with Reciprocal Rank Fusion (1/(k+rank), k≈60). Know why RRF beats score normalization.
• Query transformation: rewriting, decomposition into sub-queries, HyDE (embed a hypothetical answer), step-back prompting
• Multi-hop retrieval and when it's needed vs when it's just latency
• Late interaction (ColBERT) — better recall, much higher index cost
• Access-control-aware retrieval: filter at query time, never post-filter (post-filtering leaks existence and destroys recall)

Reranking

• Cross-encoder rerankers on top-k (k=50–200) from first-stage retrieval
• LLM rerankers: better, slower, expensive; use for the top 10
• The latency budget conversation: retrieval 30 ms, rerank 80 ms, generation 800 ms — know where your budget actually goes

Failure modes to name unprompted

• Retrieval succeeded, generation ignored it (groundedness failure)
• Retrieval failed silently and the model confabulated confidently
• Chunk boundaries split the answer
• Stale index vs live source of truth
• "Lost in the middle" — relevant context in the middle of a long window gets underweighted

15.4 Agentic systems

Patterns

• ReAct (reason → act → observe loop), Plan-and-Execute (decompose upfront, then run), Reflexion (self-critique and retry), router/dispatcher, supervisor with sub-agents, handoff/swarm
• Single agent with good tools beats multi-agent in most production cases. Have the opinion; it's a maturity signal.

Architecture components

• Planner, tool registry, executor, memory store, trace/observability layer
• MCP (Model Context Protocol) as the emerging standard for tool exposure — know it, know that tool descriptions are prompt surface area

Failure modes to design against (name these in the interview)

• Tool misuse → strict input validation, sandboxed execution
• Infinite loops → max iterations, total token budget, cycle detection
• Prompt injection via tool output → sanitize before re-injection, treat all tool output as untrusted
• Hallucinated tool calls → validate against the registered schema, reject and retry
• Scope creep / unintended side effects → permission scoping per tool, human-in-the-loop for destructive actions
• Non-idempotent retries → idempotency keys on every side-effecting tool, compensating actions for rollback

Memory

• Short-term (conversation buffer), long-term (vector or structured store), episodic (past task traces), semantic (facts/entities)
• Compaction and summarization strategies; when to drop vs summarize vs offload to a sub-agent

Determinism and debuggability

• Full trace per step: inputs, tool calls, outputs, tokens, cost, model version
• Replay capability — you cannot debug agents without it
• Checkpointing for long-running workflows

15.5 Evaluation (the round most candidates fail)

• Separate retrieval eval from generation eval. Recall@k and NDCG for retrieval; groundedness/faithfulness and answer relevance for generation. Conflating them is the classic mistake.
• Golden set: 100–500 hand-labeled examples covering the head and the ugly tail. Build it before you build the system.
• LLM-as-judge: cheap and scalable, but know its biases — position bias, verbosity bias, self-preference bias. Mitigate with pairwise comparison, randomized order, and rubric-based scoring with explicit criteria.
• Pointwise vs pairwise vs reference-based grading; when each is appropriate
• Agent eval is task-level success rate, not per-step accuracy. Also: trajectory efficiency (steps to completion), cost per successful task.
• Regression gates in CI: eval suite runs on prompt/model/retrieval changes; block merge on regression beyond a threshold
• Online: A/B, user thumbs, escalation rate, task abandonment
• Red teaming: jailbreaks, injection, PII leakage, refusal calibration
• Drift: model version changes underneath you. Pin versions, re-run evals on every provider update.

15.6 Serving & inference infrastructure

• Continuous (in-flight) batching — the core throughput lever
• PagedAttention / vLLM: KV cache paging, prefix caching for shared system prompts
• Speculative decoding: draft model + verification
• Tensor parallelism (within a node) vs pipeline parallelism (across nodes); when you need either
• Metrics that matter: TTFT (time to first token), TPOT (time per output token), throughput (tokens/sec), GPU utilization, queue depth
• GPU memory math: weights + KV cache + activations + fragmentation. Know how to size a deployment.
• Autoscaling GPUs: cold start is minutes, not seconds. Provisioned floor + queue + graceful degradation.
• Serving stacks: vLLM, TGI, SGLang, TensorRT-LLM; managed (Bedrock, Vertex, Azure OpenAI)
• Common design question: "Design an inference batching system for a single GPU handling up to 100 synchronous requests, maximizing utilization under latency constraints." Practice this one specifically — it's asked verbatim at multiple labs.

15.7 Cost engineering

• Unit economics: cost per request = (input tokens × input price) + (output tokens × output price), amortized over cache hit rate
• Levers, ranked by impact: prompt caching → model routing (cheap first, escalate on low confidence) → context trimming → semantic caching → distillation → batch API
• Track cost per feature, per team, per customer. Attribution is a real engineering problem.
• Budget guardrails: per-tenant token quotas, circuit breakers on spend, alerting on cost-per-request drift
• The lead-level version: token spend is now a line item leadership asks about. Being fluent here differentiates you immediately.

15.8 Safety, guardrails, governance

• OWASP LLM Top 10: prompt injection, insecure output handling, training data poisoning, model DoS, supply chain, sensitive info disclosure, insecure plugin design, excessive agency, overreliance, model theft
• Direct vs indirect prompt injection. Indirect (via retrieved docs, tool output, web content) is the dangerous one and the one interviewers probe.
• Output handling: treat model output as untrusted input. Never eval it, never pass it to a shell, escape before rendering.
• PII: detection and redaction on ingress and egress; data residency for model calls
• Excessive agency: scope tool permissions to the minimum; require confirmation for irreversible actions
• Governance: model cards, approved-model registry, audit logging of prompts and outputs, retention policy
• Regulatory awareness: EU AI Act risk tiers, sector rules (this matters a lot in legal/financial domains)

15.9 Classical ML you still need

• Feature engineering, leakage (especially temporal leakage), point-in-time correctness
• Class imbalance, calibration (Platt, isotonic), threshold selection by business cost
• Metrics: precision/recall/F1, AUC-ROC vs AUC-PR (PR for imbalanced), NDCG for ranking
• Training/serving skew, feature store as the fix
• Model lifecycle: registry, versioning, shadow deploy, canary, rollback
• Drift: data drift vs concept drift, detection (PSI, KS test), retraining triggers

15.10 AI design questions to rehearse

1. Design a RAG system for customer support with document-level access control
2. Design an LLM gateway: routing, caching, rate limiting, cost attribution, failover across providers
3. Design an inference batching system maximizing GPU utilization under a latency SLA
4. Design an agent platform with sandboxed tool execution and full replay
5. Design an evaluation pipeline that gates prompt and model changes in CI
6. Design a multilingual semantic search system with LLM-based query understanding
7. Design a system to detect and mitigate hallucination in production
8. Design cost attribution for LLM spend across 40 teams

16. Context, Prompt & Graph Engineering

16.1 The distinction that matters

Prompt engineering is how you ask. Context engineering is what the model knows, sees, and remembers at the moment it acts. The 2026 framing: prompt engineering is table stakes; context engineering is the multiplier. Prompts control interaction design (format, tone, reasoning strategy, decomposition). Context controls knowledge infrastructure (definitions, entity relationships, access policies, lineage, freshness).

The symptom that means you've outgrown prompting: your prompt template has grown past ~2,000 tokens of business rules and exceptions, and each new edge case adds a paragraph. That's knowledge encoded in the wrong place.

16.2 The context pipeline

1. Source curation — which systems are authoritative, and what's explicitly stale
2. Retrieval strategy — how the right slice reaches the model at the right time
3. Ranking — freshness, authority, proximity to the task
4. Compression — summarization, extraction, dropping the irrelevant
5. Assembly — ordering (put critical instructions at the start and end, not the middle), delimiters, structure
6. Feedback — measure what context was actually used and prune what wasn't

16.3 Context window management

• Budget the window explicitly: system instructions / tools / retrieved context / history / output reserve. Write the budget down.
• "Lost in the middle" — recall degrades for content in the middle of long contexts. Order matters more than most people assume.
• Context rot: more context is not better. Past a point, added context reduces accuracy.
• Compaction strategies: rolling summarization, hierarchical summarization, structured state extraction (keep a JSON state object rather than raw history)
• Sub-agent isolation: give each sub-agent only the slice it needs. Prevents context pollution and cuts cost.
• Tool output truncation with a "fetch more" affordance rather than dumping everything

16.4 Prompt engineering as an engineering discipline

• Version prompts in git, not in a database field
• Prompts get tests. A prompt change without an eval run is an unreviewed deploy.
• Techniques worth knowing precisely: few-shot (and how example selection matters more than example count), chain-of-thought, self-consistency (sample n, majority vote), decomposition, role assignment, output schema constraints
• Anti-patterns: negative instructions ("don't do X" underperforms "do Y"), stacked contradictory rules, examples that conflict with instructions
• Prompt injection defense at the prompt layer is weak. Defense belongs at the architecture layer.

16.5 Graph engineering

When a graph beats a vector index

• Multi-hop reasoning ("which customers are affected by an outage in the service that depends on X")
• Relationship-heavy domains: org structures, supply chains, citations, entitlements, fraud rings
• When explanation matters — a traversal path is auditable, a cosine similarity isn't

Core concepts

• Property graph (Neo4j, Cypher) vs RDF/triple store (SPARQL); Gremlin/TinkerPop as the portable traversal language
• Entity resolution and deduplication — the hardest part of any real knowledge graph
• Ontology/schema design, and the governance problem of who owns it
• Traversal cost, supernode problem, index-free adjacency
• Graph databases at scale: Neo4j, Amazon Neptune, TigerGraph, JanusGraph; graph queries on top of relational (recursive CTEs) when the graph is small

GraphRAG

• Build a graph from documents (entity + relation extraction with an LLM), cluster into communities, generate community summaries
• Query time: local search (entity neighborhood) vs global search (community summaries) — know when each applies
• Cost reality: graph construction is expensive and brittle. Have an opinion on when it's worth it (high-value, stable corpora with relational questions) and when it isn't (large, churning document sets with lookup-style questions).
• Hybrid: vector retrieval for candidates, graph traversal for expansion and verification

Agent graphs (different thing, same word)

• LangGraph-style state machines: nodes, edges, conditional routing, cycles
• Checkpointing for resumability, human-in-the-loop interrupts
• DAG vs cyclic: cycles allow retry/reflection, and require explicit termination conditions
• Why an explicit graph beats a free-form agent loop in production: it's testable, observable, and bounded

17. Advanced Backend: Streaming, Reactive, APIs

17.1 Streaming systems

Kafka (depth beyond the basics)

• Exactly-once: idempotent producer (PID + sequence numbers) + transactions + read_committed consumers. Know that it's exactly-once within Kafka, not end-to-end.
• ISR, min.insync.replicas, acks=all, unclean leader election and the durability tradeoff
• Log compaction vs retention; compacted topics as changelog/state
• Partition count as a scaling and ordering decision; ordering is per-partition only
• Consumer group rebalancing: eager vs cooperative sticky; static membership to avoid rebalance storms
• Consumer lag as the primary health metric; lag-based autoscaling (KEDA)
• KRaft (ZooKeeper removal), tiered storage
• Schema Registry: Avro/Protobuf/JSON Schema, compatibility modes (backward, forward, full, transitive) — a real design decision

Flink / stream processing

• Event time vs processing time vs ingestion time
• Watermarks: how late data is handled, allowed lateness, side outputs for the truly late
• Windows: tumbling, sliding, session, global
• State backends (heap vs RocksDB), checkpointing (Chandy-Lamport), savepoints for upgrades
• Exactly-once sinks via two-phase commit
• Kafka Streams vs Flink vs Spark Structured Streaming — know the tradeoff (operational simplicity vs power vs batch/stream unification)

Patterns

• CDC with Debezium; the dual-write problem and the outbox pattern as its fix
• Backfill and reprocessing: the Lambda vs Kappa architecture argument, and how you actually replay
• Dead letter queues, poison pill handling, retry topics with backoff tiers
• Idempotent consumers — required, always

17.2 Java reactive & Spring

Reactive Streams spec

• Publisher / Subscriber / Subscription / Processor
• Backpressure via request(n) — this is the whole point; if you can't explain demand signalling, you don't know reactive
• Backpressure strategies: buffer, drop, latest, error

Project Reactor

• Mono vs Flux; cold vs hot publishers
• Operators: map/flatMap/concatMap/flatMapSequential (concurrency and ordering differ — a classic interview question)
• publishOn vs subscribeOn — which part of the chain moves threads
• Schedulers: parallel, boundedElastic, single, immediate
• Context propagation (Context/ContextView), and why MDC logging breaks in reactive
• Error handling: onErrorResume, onErrorMap, retryWhen with backoff
• Testing with StepVerifier and VirtualTimeScheduler

Spring WebFlux

• Netty event loop model; never block on an event-loop thread — this is the #1 production bug in reactive Spring
• WebFlux vs Spring MVC: when reactive actually wins (high-concurrency I/O-bound, streaming, many slow downstreams) and when it's pure cost (CPU-bound, simple CRUD, small team)
• R2DBC vs JDBC; reactive Redis, Mongo, Cassandra drivers
• WebClient vs RestClient; connection pooling and timeouts

Virtual threads (Loom, JDK 21+) — have a strong opinion here

• Virtual threads give you scalability with blocking-style code. For many services, this removes the main reason to adopt reactive.
• Pinning: synchronized blocks and native calls pin a virtual thread to a carrier thread. Use ReentrantLock.
• Reactive still wins for: true streaming semantics, backpressure across a network boundary, complex async composition.
• The lead-level answer: "For a new service on JDK 21+, I'd default to virtual threads and structured concurrency. I'd choose reactive only for streaming with real backpressure requirements." That framing lands well.

17.3 GraphQL & Netflix DGS

• Schema design: nullability as a contract, interfaces vs unions, pagination (Relay cursor connections), error handling (errors array vs union result types)
• N+1 and DataLoader — batching and per-request caching. Expect to be asked to explain the fix in detail.
• Federation (Apollo Federation v2): subgraphs, @key, entity resolution across services, supergraph composition, @requires/@provides/@external
• Netflix DGS: annotation-driven (@DgsComponent, @DgsQuery, @DgsData), codegen from SDL, DgsDataLoader, Spring Boot integration, instrumentation hooks, federation support
• Security & cost control: query depth limiting, complexity/cost analysis, persisted queries (APQ), disabling introspection in prod, field-level authorization
• Caching is the hard part — no HTTP cache semantics. Solutions: persisted queries with GET + CDN, response cache keyed on query hash + variables + auth context, @cacheControl hints
• Subscriptions over WebSocket (graphql-ws) or SSE
• When not to use GraphQL: internal service-to-service (use gRPC), simple CRUD with one consumer, file uploads, when your team has no schema governance capacity

17.4 gRPC & binary protocols

• Protobuf wire format: field numbers as the contract, varint encoding, why you never reuse a field number, reserved
• Compatibility rules: adding optional fields is safe, changing types isn't, renaming is fine (names aren't on the wire)
• HTTP/2: multiplexing, header compression (HPACK), flow control, and why head-of-line blocking still exists at the TCP layer (hence HTTP/3 and QUIC)
• Four call types: unary, server streaming, client streaming, bidirectional
• Deadlines and cancellation propagation — gRPC does this properly and REST usually doesn't. Big talking point.
• Interceptors for auth, tracing, retries; metadata as the header equivalent
• Load balancing: client-side (pick_first, round_robin), lookaside LB, xDS/Envoy integration. Note that L4 load balancers break gRPC because of long-lived HTTP/2 connections — a favorite gotcha question.
• gRPC-Web and Connect for browser clients; grpc-JSON transcoding via Envoy for REST compatibility
• Alternatives and when: Thrift (legacy, Meta), Avro (schema-in-data, Kafka-friendly), Cap'n Proto / FlatBuffers (zero-copy, very low latency), MessagePack (schemaless binary JSON)
• Schema governance: buf for lint and breaking-change detection in CI. Mentioning this signals you've run this at scale.

17.5 API decision matrix (have this ready)

17.6 Distributed transaction patterns

• Saga: orchestration (central coordinator, easier to reason about) vs choreography (event-driven, less coupling, harder to debug)
• Compensating transactions and why they're not rollbacks
• Outbox and inbox patterns
• Event sourcing + CQRS: append-only log, projections, snapshots, replay. Know the costs — schema evolution of events is brutal, and most teams don't need it.
• Idempotency keys as a first-class API concept

18. Real-Time Delivery, CDN, Caching & Edge

18.1 WebSockets

• Handshake: HTTP Upgrade → 101 Switching Protocols; frames, masking, ping/pong keepalive
• Scaling: connections are stateful, so you need either sticky routing or a shared pub/sub backplane (Redis, NATS, Kafka) to fan out across nodes
• Resource math: ~10–50 KB per connection; a single node handles 10k–100k connections depending on buffer tuning. Know ulimit -n, ephemeral port exhaustion, and conntrack table limits.
• LB gotchas: idle timeouts kill connections silently. Configure keepalive shorter than the LB timeout.
• Reliability: reconnect with exponential backoff + jitter, resume via sequence number / last-message-id, at-least-once delivery with client-side dedupe
• Presence and fan-out patterns: room-based sharding, topic routing

18.2 Server-Sent Events

• Unidirectional server→client over plain HTTP, auto-reconnect built in, Last-Event-ID for resume
• Works with existing HTTP infrastructure (proxies, auth, compression) — the reason it beat WebSockets for LLM token streaming
• HTTP/1.1 6-connection-per-origin limit is the classic gotcha; HTTP/2 multiplexing solves it
• Buffering by intermediate proxies breaks SSE — disable proxy buffering explicitly (X-Accel-Buffering: no for nginx)

18.3 HTTP caching (know the headers exactly)

• Cache-Control: max-age, s-maxage, public/private, no-cache (revalidate) vs no-store (never store), immutable
• stale-while-revalidate and stale-if-error — the two directives that most improve real-world availability
• Validators: ETag (strong vs weak) + If-None-Match, Last-Modified + If-Modified-Since
• Vary and why Vary: * or Vary: User-Agent destroys your hit rate
• Cache key design: which query params, headers, and cookies participate. Over-inclusive keys are the #1 cause of poor hit rates.

18.4 CDN architecture

• PoP hierarchy, origin shield / tiered caching to protect the origin
• Purge: hard purge vs soft purge (serve stale while refetching) vs surrogate keys / cache tags for group invalidation. Tag-based invalidation is the answer for content with complex dependencies.
• Cache stampede / thundering herd mitigation: request coalescing at the edge, jittered TTLs, probabilistic early expiration (XFetch), lock-and-refresh
• Edge compute: Cloudflare Workers, Lambda@Edge / CloudFront Functions, edge KV. Use for auth checks, A/B assignment, personalization at the edge, header rewriting.
• Personalization vs caching: split the page (cacheable shell + dynamic fragments), or use edge-side includes / streaming SSR
• Security at the edge: WAF, bot management, rate limiting, DDoS absorption via anycast
• Cache poisoning: unkeyed input in the cache key is the vulnerability class to know

18.5 Application caching layers

Layer the answer in interviews — most candidates only name Redis.

1. Browser / HTTP cache
2. CDN / edge
3. API gateway response cache
4. In-process cache (Caffeine, Guava) — nanoseconds, but per-instance, so consistency is the tradeoff
5. Distributed cache (Redis, Memcached)
6. Database buffer pool / materialized views

Patterns: cache-aside (most common), read-through, write-through (consistency, higher write latency), write-behind (throughput, risk of loss), refresh-ahead

Redis specifics

• Eviction policies: allkeys-lru, volatile-ttl, noeviction — and what happens when you pick wrong
• Cluster mode, hash slots, and why multi-key ops break across slots (hash tags fix this)
• Hot key mitigation: client-side local cache, key splitting, read replicas
• Pipelining vs Lua scripts vs transactions
• Persistence: RDB vs AOF, and that Redis is not a database
• Redis vs Memcached: data structures and persistence vs raw simplicity and multithreaded throughput

Invalidation

• TTL-only (simple, stale windows) vs event-driven (correct, complex) vs versioned keys (change the key, never invalidate)
• Negative caching to protect against lookup floods on missing keys
• The cardinal rule to state out loud: cache invalidation bugs are consistency bugs, so choose the staleness you can tolerate before choosing a cache.

19. Compute: Serverless, Containers, Kubernetes, OS & Kernel

19.1 Serverless

• Lambda cold start anatomy: download code → init runtime → run init code → invoke. Reduce with smaller packages, lazy imports, provisioned concurrency, SnapStart (JVM).
• Memory setting controls CPU allocation — undersizing memory to save money often costs more because duration rises
• Concurrency: reserved vs provisioned; account-level limits; throttling behavior and how it interacts with SQS/Kinesis event sources
• VPC-attached Lambdas: ENI setup used to dominate cold start; know the current hyperplane ENI model
• Connection management: never open a DB connection per invocation — RDS Proxy or a data API
• Orchestration: Step Functions (state machine, retries, error handling), EventBridge (routing/schema registry), SQS/SNS fan-out, DLQs everywhere
• Anti-patterns: chatty function-to-function calls, long-running jobs, functions as a monolith, distributed transaction spaghetti
• Decision framework: Lambda for spiky, event-driven, short work. Fargate for containerized services with variable load and no cluster ops. EKS/K8s when you need scheduling control, multi-tenancy, or portability. EC2 for GPU, specialized hardware, or extreme cost optimization at steady scale.
• Cost crossover: serverless wins below roughly 30–40% steady utilization; always-on compute wins above it. Be able to do this math out loud.

19.2 Containers & the kernel underneath

• Namespaces: pid, net, mnt, uts, ipc, user, cgroup — isolation
• cgroups v2 — resource limits (CPU, memory, IO, pids)
• Union filesystems (OverlayFS), copy-on-write, layer caching
• Security primitives: seccomp profiles, Linux capabilities (drop ALL, add back what you need), AppArmor/SELinux, read-only root filesystem, non-root user
• Runtimes: runc (default), gVisor (userspace kernel, stronger isolation), Firecracker (microVM — what Lambda and Fargate run on), Kata
• Image hygiene: multi-stage builds, distroless/scratch base, pinned digests not tags, SBOM generation, vulnerability scanning in CI

19.3 Kubernetes

Control plane

• API server (the only thing that talks to etcd), etcd (Raft, watch semantics), scheduler, controller-manager, kubelet, kube-proxy
• The reconciliation loop is the whole mental model: declared state vs observed state, controllers converging continuously

Scheduling & resources

• Requests vs limits; QoS classes (Guaranteed, Burstable, BestEffort) and eviction order
• CPU limits cause CFS throttling — a top production surprise. Many teams set CPU requests and no CPU limits deliberately. Have an opinion.
• Memory limits cause OOMKill, not throttling — memory is incompressible
• Affinity/anti-affinity, taints/tolerations, topology spread constraints, PodDisruptionBudgets
• Priority classes and preemption

Autoscaling

• HPA (metrics-driven pod count), VPA (right-sizing, conflicts with HPA on the same metric), Cluster Autoscaler vs Karpenter (Karpenter provisions right-sized nodes directly — the modern answer), KEDA (event-driven scaling on queue depth, Kafka lag, etc.)

Networking

• CNI plugins; flat pod network requirement
• Service types (ClusterIP, NodePort, LoadBalancer), kube-proxy modes (iptables → IPVS → eBPF/Cilium and why iptables degrades at scale)
• Ingress vs the Gateway API (Gateway API is the direction of travel)
• NetworkPolicy for east-west segmentation — the zero-trust building block inside the cluster
• Service mesh: sidecar (Istio/Linkerd) vs ambient/sidecarless; mTLS, retries, circuit breaking, traffic splitting. Know the latency and resource cost — mesh is not free.

Stateful & storage

• StatefulSets, PVCs, CSI drivers, StorageClass, volume expansion
• Operators/CRDs for stateful systems; when running a database on K8s is reasonable and when it isn't

Delivery

• Helm vs Kustomize; GitOps with Argo CD or Flux; progressive delivery (Argo Rollouts, Flagger) with canary + automated rollback on SLO breach

Debugging checklist to recite CrashLoopBackOff → check logs and previous logs, init containers, probe config, missing config/secret OOMKilled → memory limit, actual usage, JVM heap vs container limit mismatch Pending → resource requests unschedulable, node selectors, taints, PVC unbound ImagePullBackOff → registry auth, tag typo, rate limits Slow but healthy → CPU throttling, noisy neighbor, probe misconfiguration, DNS (ndots:5 causing 5 lookups per query — a classic)

19.4 OS & kernel fundamentals

• Process vs thread vs coroutine; context switch cost (~1–5 µs); scheduler basics (CFS, and EEVDF in newer kernels)
• Memory: virtual memory, page tables, TLB, page cache, major vs minor faults, huge pages, NUMA locality, swap and why you disable it for latency-sensitive services, the OOM killer and oom_score_adj
• I/O models: blocking, non-blocking, multiplexed (select/poll/epoll/kqueue), async (io_uring), and zero-copy (sendfile, splice, mmap)
• Durability: page cache vs fsync, write barriers, and why "the write returned" doesn't mean "the data is safe"
• Networking stack: three-way handshake, TIME_WAIT, SO_REUSEADDR, backlog queues (somaxconn, accept queue overflow), Nagle vs TCP_NODELAY, congestion control (CUBIC vs BBR), receive/send buffer autotuning, MTU and PMTU discovery, ephemeral port and conntrack exhaustion
• eBPF: safe in-kernel programs for observability (bpftrace, bcc), networking (Cilium), and security (Tetragon, Falco). Knowing eBPF is a strong staff-level signal.
• Performance methodology: USE (Utilization, Saturation, Errors) for resources; RED (Rate, Errors, Duration) for services. State the method before the tool.
• Tooling: perf + flame graphs, strace, ltrace, tcpdump, ss, vmstat, iostat, pidstat, bpftrace
• JVM in containers (if relevant): container-aware heap sizing, GC choice (G1 default, ZGC/Shenandoah for low pause), JFR, async-profiler, why -Xmx at 100% of the container limit gets you OOMKilled

20. Storage, Scaling & Data Platform

20.1 DynamoDB

• Access patterns first, schema second. Say this before anything else; it's the answer they're listening for.
• PK/SK design, composite keys, single-table design and its real tradeoff (query efficiency vs comprehension cost)
• GSIs (eventually consistent, own capacity, projections matter) vs LSIs (strongly consistent, 10 GB per partition limit, must be created at table creation)
• Sparse indexes as a query pattern
• Limits: 400 KB item, 10 GB per partition key for LSI, 1 MB per query result page
• Hot partitions and adaptive capacity; write sharding by suffixing the key
• Capacity: on-demand vs provisioned + auto-scaling; throttling and exponential backoff with jitter
• Transactions (TransactWriteItems, 100-item limit, 2× cost), condition expressions for optimistic concurrency
• Streams → Lambda for CDC; TTL for expiry; PITR; global tables (multi-region active-active, last-writer-wins — know that conflict resolution is not configurable)
• Cost model: RCU/WCU, and that a badly modeled table costs 10× a well-modeled one

20.2 Cassandra / ScyllaDB

• Ring topology, vnodes, NetworkTopologyStrategy, replication factor per DC
• Tunable consistency: ONE/QUORUM/LOCAL_QUORUM/ALL; R + W > RF for strong consistency; LOCAL_QUORUM is the practical default multi-DC choice
• Repair mechanisms: hinted handoff, read repair, anti-entropy repair (and that skipping repair causes resurrection of deleted data past gc_grace_seconds)
• Partition key design; wide partitions and the size ceiling (~100 MB / 100k rows as a rule of thumb)
• Tombstones — deletes create markers, range scans over tombstones cause timeouts. This is the Cassandra gotcha; know it.
• Compaction strategies: STCS (write-heavy), LCS (read-heavy, higher write amp), TWCS (time series)
• LWT (Paxos) is 4× the round trips — use sparingly
• Scylla: C++ rewrite, shard-per-core, same API, much better tail latency
• When Cassandra: high write throughput, multi-DC active-active, known query patterns, linear scale. When not: ad hoc queries, joins, strong transactional needs.

20.3 MongoDB

• Modeling: embed for one-to-few and read-together; reference for one-to-many, unbounded growth, or independent access. 16 MB document limit forces the decision.
• Replica sets: primary election (Raft-like), oplog, write concern (w:majority, j:true), read concern (local/majority/linearizable/snapshot), read preference, causal consistency sessions
• Sharding: shard key is nearly irreversible — evaluate cardinality, frequency, and monotonicity. Monotonic keys create a hot shard; hashed sharding fixes distribution but kills range queries.
• Chunk balancing, jumbo chunks, zone sharding for data residency
• Indexes: compound index ESR rule (Equality, Sort, Range ordering), partial, TTL, text, wildcard; covered queries
• Aggregation pipeline, $lookup limitations (no sharded-collection joins in older versions, no true optimizer)
• Change streams for CDC; multi-document transactions exist but cost you the reason you picked Mongo

20.4 OpenSearch / Elasticsearch (operational depth)

• Node roles: master, data (hot/warm/cold/frozen), ingest, coordinating, ML
• Shard sizing: 10–50 GB per shard as a working range; over-sharding is the most common cluster killer
• JVM heap: 50% of RAM, under ~32 GB to keep compressed object pointers; the other half goes to the OS page cache for Lucene
• Mapping: keyword vs text, dynamic mapping explosion, index: false for unqueried fields, doc_values for aggregations, disable _source only if you understand the consequences
• Search phases: query-then-fetch; deep pagination cost; search_after + PIT instead of from/size; scroll is legacy
• Refresh vs flush vs merge; refresh_interval tuning for bulk indexing (set to -1 during bulk loads)
• Zero-downtime reindex: build new index → alias swap → verify → drop old. Rehearse this; it's a common design answer.
• ILM/rollover for time-series, snapshot/restore, cross-cluster replication and cross-cluster search
• Failure modes: circuit breaker trips, thread pool rejections (search/write queues), unbalanced shards, mapping conflicts, split-brain (pre-7.x quorum config)
• k-NN: Lucene HNSW vs nmslib/faiss engines, ef_search/ef_construction/m, scalar and product quantization, disk-based vector search for memory relief, filtered kNN and the pre/post-filter recall tradeoff

20.5 Relational at scale

• Postgres: MVCC, tuple bloat, autovacuum tuning, transaction ID wraparound (the incident that takes down unmonitored clusters)
• Index types: B-tree, GIN (JSONB, full text), GiST, BRIN (huge append-only tables), partial and covering (INCLUDE) indexes
• Isolation levels and the anomalies each permits (dirty read, non-repeatable read, phantom, write skew); Postgres REPEATABLE READ is snapshot isolation, which allows write skew — a great depth question
• Connection pooling: PgBouncer transaction pooling and what it breaks (prepared statements, session state)
• Partitioning (declarative, by range/list/hash), and partition pruning
• Replication: streaming (physical) vs logical; replica lag and how the app handles read-after-write (sticky-to-primary for N seconds, or read-your-writes tokens)
• Sharding: Vitess, Citus, or application-level; the resharding problem is why you delay this as long as possible
• Online schema change: pt-online-schema-change/gh-ost (MySQL), CREATE INDEX CONCURRENTLY, expand-contract migration pattern

20.6 Analytics & lakehouse

• Columnar formats: Parquet/ORC, row groups, column pruning, predicate pushdown, compression codecs
• Table formats: Iceberg (snapshot isolation, hidden partitioning, time travel, schema evolution), Delta Lake, Hudi. Iceberg is the default answer in 2026.
• Small file problem and compaction; partition evolution
• Warehouses: Snowflake (micro-partitions, clustering keys, warehouse sizing and auto-suspend for cost), BigQuery (slots, partitioning + clustering), Redshift
• Medallion architecture (bronze/silver/gold), dbt for transformation, incremental models
• Data contracts, quality gates, lineage — increasingly a lead's responsibility because AI systems consume this data

20.7 Storage decision table

21. Security: OAuth, Zero Trust, AppSec & Network

21.1 OAuth 2.0 / 2.1 and OIDC

Grants and which are alive

• Authorization Code + PKCE — the only correct choice for any public client (SPA, mobile, CLI). PKCE now recommended for confidential clients too.
• Client Credentials — service-to-service
• Device Authorization — TVs, CLIs, constrained input
• Dead: Implicit (token in URL fragment, leaks), Resource Owner Password Credentials (the app sees the password)

Tokens

• Access token (what you present), refresh token (what you exchange), ID token (OIDC only — an assertion about who, not an authorization to do)
• JWT vs opaque: JWT is stateless and fast but hard to revoke; opaque needs introspection but gives you instant revocation. Common answer: short-lived JWTs (5–15 min) + refresh with rotation.
• Validation checklist: signature against JWKS, iss, aud, exp, nbf, alg allowlist, kid handling and key rotation
• Refresh token rotation with reuse detection — if an old refresh token is replayed, revoke the whole family
• Sender-constrained tokens: DPoP or mTLS-bound tokens. Prevents a stolen bearer token from being usable. This is the "above and beyond" answer.
• Token exchange (RFC 8693) for delegation and on-behalf-of flows in service chains

Vulnerabilities to name

• Redirect URI wildcards / open redirect chaining
• Missing or unbound state → CSRF on the callback
• Mix-up attacks in multi-IdP setups (validate iss in the response)
• Tokens in URLs (referrer leakage, logs, browser history)
• alg: none and algorithm confusion (RS256 verified as HS256 with the public key as the secret)
• Overly broad scopes; scope != permission — do authorization in your own layer

Adjacent