Hash Indexing

source: https://en.wikipedia.org/wiki/Hash_table

Imagine you’re running a popular online bookstore, where thousands of book searches happen every second. Each search queries your vast database for titles, authors, genres, and more. Initially, your system is quick and efficient, delighting customers with rapid responses. But as your inventory and customer base grow, you notice the search responses are slowing down. Customers are waiting longer for results, leading to frustration and, worse, lost sales. This isn’t just a hypothetical scenario — it’s a challenge faced by many growing businesses in the digital age.

This slowdown happens because the basic database system you started with, which worked well with a smaller dataset, struggles under the weight of increased data and search requests. The core issue? It lacks an efficient way to locate data quickly. This is where Hash Indexing comes into play.

Hash Indexing is the superhero in our story. It’s a technique that transforms slow, cumbersome data retrieval into a swift, efficient process. With hash indexing, your bookstore’s database can handle millions of books and customer queries without breaking a sweat. This article will take you on a journey through the world of Hash Indexing. We’ll start with the basics of database storage and see how, without sophisticated structures like hash indexes, even the simplest operations can become a bottleneck. Then, we’ll explore how implementing hash indexing can turn the tables, offering the speed and efficiency necessary to keep up with the demands of a growing, dynamic online business.

This article series draws inspiration from the renowned O’Reilly’s book on distributed systems, specifically the insights on storage engines and retrieval mechanisms.

Database Storage Without Data Structures:

Let’s begin by setting up a basic key-value storage system using bash. In this setup, data is stored in a plain text file, where each line represents a key-value pair.

• Setting a Value:

To store data, we use a simple command to append key-value pairs to a text file. For example:

echo "key1:value1" >> database.txt
echo "key2:value2" >> database.txt

This method is incredibly efficient for writing data as it simply appends information to the end of the file.

• Getting a Value:

Retrieving data, however, is less efficient. To find the value associated with a key, the system must scan through the entire file until it locates the desired key. For instance:

grep "^key1:" database.txt | tail -n 1 | cut -d":" -f2

This command searches for lines starting with ‘key1:’, takes the last entry (the most recent), and extracts the value part. As the file grows, this operation becomes increasingly slow, showing the inefficiency of reads in this system.

• Updating a Value:

Updates are handled similarly to ‘set’ operations. If we update a value, it appends a new line with the same key but a different value:

echo "key1:newValue" >> database.txt

During a ‘get’ operation, only the latest value is retrieved, but the file keeps growing with redundant data.

Introducing Indexes to Enhance Efficiency

After identifying the inefficiencies in our basic storage system, we introduce a hash index to improve retrieval times significantly. In hash indexing, each key is mapped to a memory offset where its corresponding value is stored in the file. This index is maintained in memory, allowing quick access to data.

• Setting a Value with Indexing:

When we append data to ‘database.txt’, we simultaneously update the hash index. For example:

echo "key3:value3" >> database.txt
# Update the hash index with the memory offset for key3

The memory offset of ‘key3’ in ‘database.txt’ is calculated and stored in the hash index.

• Getting a Value with Indexing:

To retrieve a value, we consult the hash index to find the exact location of the data in the file, which drastically reduces retrieval time.

• Representation:

| Key       | Memory Offset |
|-----------|---------------|
| key1      | 1024          |
| key2      | 2048          |
| key3      | 4096          |
| key4      | 8192          |
| key5      | 16384         |

Byte Offset | Data in File
---------------------------
1024        | key1=value1
2048        | key2=value2
4096        | key3=value3
8192        | key4=value4
16384       | key5=value5

Log Segmentation and Compaction

As the database continues to grow with more ‘set’ operations, simply appending data to the end of the file becomes unsustainable. To manage this, we introduce the concept of log segments, which are fixed-size portions of the log.

Creating Log Segments: Instead of one endless file, we divide our writes into segments. Each segment has a maximum size, and when it reaches this limit, it is closed and a new segment is started. This approach helps manage disk space more efficiently and ensures that the system remains responsive as data grows.

Compacting Segments: Over time, each key may be updated multiple times, leading to multiple entries across segments. Compaction is the process of merging segments and discarding redundant keys, keeping only the most recent entry for each key. This not only saves space but also improves read efficiency.

Let’s visualize the compaction process with a simple example of merging two segments:

Segment 1:
| Key       | Memory Offset | Value     |
|-----------|---------------|-----------|
| key1      | 1024          | value1    |
| key2      | 2048          | value2    |
| key3      | 4096          | value3    |

Segment 2 (newer updates):
| Key       | Memory Offset | Value     |
|-----------|---------------|-----------|
| key2      | 1024          | value2_v2 |
| key3      | 2048          | value3_v2 |
| key4      | 4096          | value4    |

Compacted Segment:
| Key       | Memory Offset | Value     |
|-----------|---------------|-----------|
| key1      | 1024          | value1    |  // From Segment 1, no newer update in Segment 2
| key2      | 2048          | value2_v2 |  // From Segment 2, newer update
| key3      | 4096          | value3_v2 |  // From Segment 2, newer update
| key4      | 8192          | value4    |  // From Segment 2, no previous version

Background Merging: The merging of segments can be done in the background. During this process, read requests are served from the existing segments. Once the merge is complete, new read requests are pointed to the new, compacted segment, and the old segments can be safely deleted.

In-Memory Hash Maps for Each Segment: Each segment has its own in-memory hash map of keys to memory offsets. When a read request comes in, the database starts with the most recent segment and checks the in-memory hash map for the key. If it’s not found, the database continues to check older segments’ hash maps until the key is found or all segments have been searched.

This multi-layered approach allows the database to handle large volumes of data and maintain high performance for both read and write operations, as it scales.

Additional Considerations for Robust Storage

When designing a storage engine like the one we’ve described, several additional considerations ensure the system’s robustness and reliability:

1. Deleting Records: To delete a record, we employ a strategy known as a tombstone. A tombstone is a special record that indicates a key has been deleted. During the compaction process, any key marked with a tombstone is skipped, effectively removing it from the active dataset.

Example: Appending a tombstone for key2 would look like this:

echo "key2:tombstone" >> database.txt

2. Crash Recovery: In the event of a system crash, in-memory data can be lost. To mitigate this, snapshots of each segment’s hash map are stored on disk. These snapshots can be loaded quickly into memory after a restart, ensuring the database can recover to its last known state. Bitcask, for instance, utilizes this mechanism for efficient crash recovery.

3. Partially Written Records: To prevent issues with partially written records, such as those that could occur during a crash or write failure, Bitcask uses checksums. A checksum is a form of redundancy check, a small-size datum derived from the digital data for the purpose of detecting errors which may have been introduced during its transmission or storage.

Example of Checksum Use: For each record written, a checksum is calculated and stored alongside the data. When reading back the data, the checksum is recalculated and compared to the stored checksum to ensure data integrity.

4. Concurrency Control: Concurrency is managed by ensuring writes to the data file are performed in a strict sequential order. A common implementation choice is to have a single writer thread to prevent race conditions. Since data file segments are append-only and made immutable after compaction, this simplifies the design and avoids many concurrency issues.

Recognizing the Limitations and Looking Forward

As we’ve explored the intricacies of our storage engine, it’s important to acknowledge its limitations. Understanding these constraints is vital as it guides us towards further improvements and innovations in database technology.

1. Memory Constraint for Hash Keys: One of the primary limitations of the described storage engine is that all hash keys must fit into memory. This is a significant constraint because it limits the size of the dataset the database can handle efficiently. If the key space grows too large, it will exceed the available memory, leading to performance degradation or even system failure.

2. Lack of Range Queries: Another limitation is the inability to perform range queries efficiently. Since the hash index is designed for direct key access, it does not maintain keys in sorted order. Therefore, it’s not possible to quickly retrieve a sequence of keys within a particular range, which is a common requirement for various applications.

Conclusion

As we wrap up our exploration of Hash Indexing, we’ve seen its powerful impact on database efficiency and performance. Yet, it’s not without its limitations. Our next article will take us further, introducing advanced data structures like SSTables and LSM Trees. These innovations offer solutions to the challenges of scalability and complex querying, marking the next step in the evolution of database technology. Join us as we continue to uncover the tools that shape the future of efficient data management.

[Continue to Part 2 of this series: SSTables and LSM Trees]