In-Memory KV Cache with WAL Log

Problem Statement

Design a low-latency in-memory key-value cache that supports GET, PUT, and DELETE, but unlike a typical best-effort cache, it must also provide durability for acknowledged writes using a Write-Ahead Log (WAL). The cache should be able to recover its state after a crash or restart.

Examples

1. GET: Retrieve the value associated with a given key.
2. PUT: Insert or update a key-value pair in the cache.
3. DELETE: Remove a key-value pair from the cache.

Constraints

1. The cache should handle a large number of concurrent requests.
2. The cache should provide low-latency access to key-value pairs.
3. The Write-Ahead Log (WAL) should ensure that acknowledged writes are durable and can be recovered after a crash or restart.
4. The cache should handle memory constraints and eviction policies if necessary.

Hints

1. Consider using a combination of in-memory data structures (e.g., hash tables) and persistent storage (e.g., disk-based storage) to achieve durability.
2. Think about how to efficiently manage the Write-Ahead Log (WAL) to ensure data durability while minimizing the impact on performance.
3. Consider implementing a background process to periodically flush the in-memory cache to persistent storage to ensure data is not lost in case of a crash.
4. Think about how to handle memory constraints and implement an eviction policy if necessary (e.g., Least Recently Used (LRU)).

Solution

To design a low-latency in-memory key-value cache with durability, you can follow these steps:

1. In-Memory Cache Implementation: Use a hash table to store key-value pairs in memory for fast access. This will provide low-latency access to the data.

2. Write-Ahead Log (WAL): Implement a Write-Ahead Log (WAL) to ensure durability for acknowledged writes. Every PUT and DELETE operation should be logged in the WAL before it is applied to the in-memory cache. This ensures that if the system crashes, the WAL can be used to recover the state of the cache.

3. Concurrency Control: Implement concurrency control mechanisms (e.g., locks, atomic operations) to handle concurrent requests and ensure data consistency.

4. Background Flushing: Periodically flush the in-memory cache to persistent storage (e.g., disk-based storage) to ensure data is not lost in case of a crash. This can be done using a background process that periodically writes the current state of the cache to disk.

5. Recovery Mechanism: Implement a recovery mechanism that reads the WAL and persistent storage during system startup to restore the cache's state. This ensures that the cache can recover from a crash or restart.

6. Eviction Policy: If memory constraints are a concern, implement an eviction policy (e.g., Least Recently Used (LRU)) to remove the least recently used items from the cache when memory is full.

By following these steps, you can design a low-latency in-memory key-value cache with durability that supports GET, PUT, and DELETE operations and can recover its state after a crash or restart.