Index

To quickly retrieve a message from disk, we need a mapping of message identifiers to their start positions in the log file.

This concept mirrors how databases use indices to speed up data retrieval.

Think of an index in a book: topics are listed alphabetically, with references to the pages where they appear.

Without an index, finding a topic requires scanning the entire book.

Databases use the same principle to locate data efficiently.

Suppose a table contains employee last names.

Without an index, the database must scan every row to find a specific last name.

As the table grows, sequential scanning becomes slower.

With an index on the last name column, the database can directly jump to the correct data location.

This drastically reduces search time compared to full table scans.

For a messaging system, a hash table could store message identifiers as keys.

The value would be the segment name and message position.

Alternatively, a hash table could be created per segment file.

Each hash table uses the message identifier as a key and the message position as a value.

The per-segment hash table approach offers better memory control.

It avoids storing one large hash table in memory.

Instead, only small hash tables are loaded when needed.

Segments are deleted over time, allowing corresponding indices to be removed.

The main issue is identifying which hash table contains a given message identifier.

One solution: iterate through all hash tables in order of recency.

First, check the most recent segment.

If the message identifier is not found, check the second most recent segment.

Continue this process sequentially.

Because messages are frequently deleted upon consumption, the number of segments remains small.

Introduce a secondary index that lists message identifiers per segment.

This works well when message identifiers are sequential.

For each segment, store the first and last message identifier it holds.

1. Perform a binary search on the range index to locate the segment containing the target message.
2. Use the segment’s index to find the message position within that segment.
3. Retrieve the message bytes from the log file.

This approach is used by Apache Kafka to store and retrieve messages.

It demonstrates practical application of indexing in distributed systems.

We previously established that data must be stored on disk to prevent loss.

Memory cannot be relied upon for persistence.

The indexing system must therefore ensure durability and recoverability.

The per-segment index design supports both efficiency and resilience.

It enables fast retrieval while maintaining data integrity across restarts.

The range index reduces the number of segments to check during retrieval.

This design choice balances performance and memory usage.

It directly addresses the need for scalable, reliable message access.

The structure supports both high-throughput reads and long-term data retention.

The system remains efficient even as message volumes grow.

The indexing strategy is foundational to the system’s performance.

It enables rapid access without sacrificing storage or durability.

Storing indexes in memory does not introduce new risks of data loss. The system remains resilient because indexes are not standalone data stores.

Indexes can always be rebuilt from the original dataset. This means that even if the index is lost or corrupted, the full data set provides a source for reconstruction.

In addition to original data, indexes can be recreated from log files. These logs record all data changes over time, enabling accurate index rebuilds without relying on memory.

If the process of rebuilding an index is expected to be slow or complex, performance can be improved by storing index components on disk.

Systems typically store full indexes or their parts on disk. This allows for faster access during recovery and reduces the time needed to reconstruct indexes after failure.

The approach of storing index parts on disk is standard in real-world systems. It balances performance and data safety by avoiding reliance solely on volatile memory.

This design ensures that index loss does not compromise overall data integrity, because both original data and logs serve as recovery sources.