Designing an Infinitely Scalable Key-Value Store on a Relational Database

Building a scalable, performant, and reliable key-value store using a relational database (RDBMS) involves tackling challenges such as infinite scalability, synchronization of operations, and efficient query execution. Here’s a comprehensive system design for such a solution.

System Requirements

1. Functional Requirements:

• GET(k): Retrieve the value for a given key.
• PUT(k, v): Insert or update the value for a given key.
• DEL(k): Delete the key-value pair for a given key.

2. Non-functional Requirements:

• Scalability: Handle large volumes of data and high query rates.
• Consistency: Ensure operations on the same key are synchronized.
• Fault Tolerance: Remain operational during hardware failures.
• Performance: Low latency for GET, PUT, and DEL operations.

High-Level Architecture

Relational Database:

Centralized data storage using a relational database.

Schema:

CREATE TABLE key_value_store (     
key VARCHAR(256) PRIMARY KEY,     
value TEXT NOT NULL,     
ttl TIMESTAMP NULL DEFAULT NULL)

• key: Unique identifier for the record.
• value: The stored data.
• ttl: Expiration time for the key. NULL indicates no expiration.

Application Layer:

• Implements business logic for GET, PUT, DEL, and TTL expiration.
• Ensures synchronized operations using mutexes for individual keys.

TTL Enforcement:

• Use a background process or scheduled task to delete expired keys.
• Enforce TTL during queries by filtering out expired keys.

Sharding:

• Partition the table into shards based on key hashes.
• Each shard resides on a separate database instance for scalability.

Replication:

• Use master-slave replication for high availability and read scalability.
• Writes go to the master node, reads can be load-balanced.

Caching Layer:

• Cache frequently accessed keys (e.g., Redis, Memcached) to reduce database load.
• Include TTL in the cache for faster expiration.

SQL Queries

GET(k)

Retrieve the value for a given key, ignoring expired entries.

SELECT value 
FROM key_value_store 
WHERE key = ? 
  AND (ttl IS NULL OR ttl > NOW());

Steps:

1. Check if the key is cached and valid in the in-memory cache.
2. If not found, execute the SQL query.

PUT(k, v, ttl)

Insert or update a key-value pair with TTL.

UPSERT INTO key_value_store (key, value, ttl) 
VALUES (?, ?, ?);

DEL(k)

Delete a key-value pair (avoid hard delete at first place as trigger rebalancing of B+ tree)

UPDATE key_value_store set ttl=-1 
WHERE key = ? and ttl > NOW(); --WHY to run the op for already expired key

TTL Expiration

Regularly remove expired keys using a scheduled task or background worker.

DELETE FROM key_value_store 
WHERE ttl IS NOT NULL AND ttl <= NOW();

System Design for TTL

TTL Enforcement:

• For immediate expiration: Use a background worker to delete expired keys.
• For lazy expiration: Ignore expired keys during GET queries.

Sharding:

• Hash the key to determine its shard.
• Example:

shard_id = hash(key) % total_shards

Caching with TTL:

• Store TTL in the cache along with the value.
• Use cache eviction policies to remove expired keys automatically.

Replication:

• TTL updates propagate from the master to replicas.
• Ensure consistency by running TTL cleanup on all replicas.

High Availability:

• Use database clusters with failover mechanisms.
• Employ distributed locking (e.g., Redis locks or row-level database locks) for synchronization.

Monitoring and Alerts:

• Track expired key counts, query performance, and cache hit rates.
• Set alerts for database latency or shard imbalances.

Challenges and Solutions

Clock Drift:

• Ensure all nodes use synchronized clocks (e.g., via NTP) to avoid TTL inconsistencies.

Shard Rebalancing:

• Use consistent hashing to minimize key movement when adding/removing shards.

High Write Volume:

• Batch write operations where possible.
• Use write-ahead logging (WAL) for durability.

Expired Data Build-up:

• Schedule frequent TTL cleanup tasks.
• Monitor disk space and table size regularly.

Conclusion

Implementing an infinitely scalable key-value store with TTL on a relational database is feasible with careful architecture design. By combining database sharding, caching, TTL enforcement, and replication, the system can meet scalability, performance, and reliability requirements. Challenges like clock drift and expired data accumulation can be mitigated through robust monitoring and operational practices.