Execute a TTL Key-Value Store with Transactions

Question

The candidate is asked to design and implement a key-value store that supports time-to-live (TTL) functionality and transactions.

Codemia · Accepted Answer

To design a TTL key-value store with transactions, we need to establish the following requirements:
1. **Key-Value Storage**: The system must allow storing and retrieving values associated with unique keys.
2. **TTL Functionality**: Each key-value pair should have an associated expiration time after which it is no longer accessible.
3. **Transactions**: The store must support atomic operations for multiple key-value pairs, ensuring that either all operations succeed or none do.
4. **Concurrency**: The system should handle concurrent access to ensure data integrity.

The high-level design of the TTL key-value store can be broken down into the following components:
- **Data Structure**: Use a hash map for key-value pairs, where each entry includes the value, expiration time, and a transaction ID.
- **TTL Management**: Implement a background thread that periodically checks for expired keys and removes them from the store.
- **Transaction Support**: Use a versioning system or a two-phase commit protocol to manage transactions, ensuring that all changes are committed or rolled back together.

Here is a simplified implementation in Python:
```python
import time
from threading import Lock

class TTLKeyValueStore:
    def __init__(self):
        self.store = {}
        self.lock = Lock()

def set(self, key, value, ttl):
        expiration_time = time.time() + ttl
        with self.lock:
            self.store[key] = (value, expiration_time)

def get(self, key):
        with self.lock:
            if key in self.store:
                value, expiration_time = self.store[key]
                if time.time() < expiration_time:
                    return value
                else:
                    del self.store[key]  # Remove expired key
        return None

def transaction(self, operations):
        with self.lock:
            # Begin transaction
            temp_store = self.store.copy()
            for op in operations:
                if op['action'] == 'set':
                    temp_store[op['key']] = (op['value'], op['ttl'] + time.time())
            # Commit transaction
            self.store = temp_store
```
This code defines a basic TTL key-value store with set and get methods and a simple transaction method.

When designing this system, several trade-offs need to be considered:
- **Memory Usage**: Storing expiration times increases memory usage. We need to balance between memory efficiency and performance.
- **Concurrency Control**: Using locks can lead to contention in high-concurrency scenarios. Alternatives like lock-free data structures might be explored.
- **TTL Expiration**: The background thread for TTL expiration can introduce latency. An alternative approach could be to check expiration during get operations, but this may impact read performance.

To ensure the correctness of the implementation, we should:
1. **Unit Tests**: Write tests for set, get, and transaction methods, including edge cases like expired keys.
2. **Concurrency Tests**: Simulate concurrent access to validate the integrity of the store.
3. **Performance Tests**: Measure the store's performance under various loads to identify bottlenecks.

Execute a TTL Key-Value Store with Transactions

Opendoor

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Opendoor Backend Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string