Katkat
Back

Design a disk-backed KV store under contention

SnowflakeSoftware Engineer · Onsite
EasySoftware EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a persistent key-value store that balances disk I/O, memory caching, and thread safety under high concurrency.

Problem Statement

Design a persistent, disk-backed Key-Value (KV) store that supports put(key, value) and get(key) operations. Your system must handle concurrent requests and maintain data durability.

Functional Requirements

  • get(key): Returns the value for a given key.
  • put(key, value): Stores the value, overwriting any existing entry.

Non-Functional Requirements

  • Durability: Once a put is acknowledged, it must survive a system crash.
  • Performance: The store must handle a high volume of read and write requests.
  • Scalability: The system should allow for efficient lookups even if the dataset exceeds RAM capacity.

Constraints & Assumptions

  • Keys are strings; values are arbitrary binary blobs (can be large).
  • The working set of frequently accessed keys fits in memory, but the total dataset resides on disk.
  • Multiple threads will access the store simultaneously.

Your Task

Describe the storage engine architecture. Address the following:

  1. How do you index keys in memory to minimize disk seeks?
  2. How do you handle large values to avoid excessive memory pressure?
  3. How do you manage concurrent access to prevent data corruption while maximizing throughput?
  4. How do you ensure durability without incurring a performance penalty for every write?

Hints

Hint 1

Consider using an append-only log structure (like an LSM tree or Write-Ahead Log) to convert random disk writes into sequential I/O.

Hint 2

Implement a sharded locking strategy or use lock-free data structures to reduce contention on the index.

Hint 3

For large values, consider storing them in separate blob files and keeping only references/offsets in your primary index.

Follow-up questions

  • How would you implement a background process to reclaim space from deleted or overwritten entries (compaction)?
  • If the system were distributed, how would you ensure data consistency across multiple replicas?
  • How would you adjust your design if the access pattern is heavily skewed toward a small set of 'hot' keys?