How Kafka’s Index Uses Binary Search and Cache‑Friendly Optimizations

1. Index Architecture

Kafka's index component relies on binary search and has been refined to suit Kafka's specific characteristics.

AbstractIndex.scala : top‑level abstract class that encapsulates common operations for all index types.

LazyIndex.scala : wrapper class on AbstractIndex that implements lazy loading of index entries to improve performance.

OffsetIndex.scala : stores <relative offset, physical file position> pairs.

TimeIndex.scala : stores <timestamp, relative offset> pairs.

TransactionIndex.scala : stores metadata for aborted transactions; appears only when Kafka's transaction feature is enabled.

2. AbstractIndex Code Structure

The AbstractIndex class defines the core workflow for all index types. Its most important field is a MappedByteBuffer named mmap, which provides fast, memory‑mapped I/O for small index files.

2.1 Class Definition

Index file (file) : each index object corresponds to a file on disk; the field is mutable because Kafka can migrate log directories after version 1.1.0.

Base offset (baseOffset) : the starting offset of the log segment that the index belongs to.

Maximum index size (maxIndexSize) : derived from the broker configuration segment.index.bytes (default 10 MB).

Writable flag (writable) : true for read‑write mode, false for read‑only mode.

Each subclass of AbstractIndex implements the abstract method entrySize to specify the byte size of a single index entry.

// OffsetIndex
override def entrySize = 8
// TimeIndex
override def entrySize = 12

3. Why 8 and 12 Bytes?

In OffsetIndex, a 4‑byte relative offset plus a 4‑byte physical position totals 8 bytes. The offset stored is relative to baseOffset, not an absolute long value, which saves space because the difference always fits in an Int (log segments are limited to 4 GB by log.segment.bytes).

In TimeIndex, the timestamp is a 64‑bit long (8 bytes) and the relative offset is 4 bytes, resulting in 12 bytes per entry.

4. Memory‑Mapped File (mmap)

The index uses Java's MappedByteBuffer (exposed as the mmap variable) to map the index file directly into virtual memory, providing high I/O performance and eliminating extra copies between kernel and user space.

Typical operations:

Calculate the current number of entries: protected var _entries: Int = mmap.position() / entrySize Calculate the maximum number of entries the file can hold:

private[this] var _maxEntries: Int = mmap.limit() / entrySize

Check if the index file is full:

def isFull: Boolean = _entries >= _maxEntries

5. Writing Index Entries

The append method of OffsetIndex writes a new entry to the mapped file. The method uses the calculated _entries and entrySize to position the buffer correctly.

6. Searching Index Entries – Binary Search

Kafka locates an entry by binary search, which runs in O(log N) time. The abstract method parseEntry(buffer, n) reads the n ‑th entry from a ByteBuffer and returns an IndexEntry containing indexKey and indexValue.

protected def parseEntry(buffer: ByteBuffer, n: Int): IndexEntry

For OffsetIndex, the implementation is:

override protected def parseEntry(buffer: ByteBuffer, n: Int): OffsetPosition = {
  OffsetPosition(baseOffset + relativeOffset(buffer, n), physical(buffer, n))
}

Here relativeOffset(buffer, n) yields the stored relative offset, which is added to baseOffset to obtain the absolute offset; physical(buffer, n) returns the file position.

7. Cache‑Friendly Binary Search Improvement

The original binary search does not consider the OS page cache, leading to unnecessary page faults when the search path touches cold pages. To mitigate this, the community introduced a cache‑friendly version that splits the index into a hot area and a cold area, performing binary search separately within each region. This keeps the set of pages accessed for hot data constant, improving cache hit rates and reducing I/O latency.

8. Summary

AbstractIndex is the common abstract parent for all Kafka index types; its mmap field is the core of the indexing mechanism. The standard binary‑search algorithm is enhanced with a cache‑friendly strategy that fixes the hot‑area page set, thereby lowering page‑fault overhead and overall system load.