Katkat
Back

Design a key-value store

GoogleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSystem Design

Last updated

This question tests the ability to design a distributed, scalable, and fault-tolerant key-value store while addressing challenges related to data distribution, consistency, and storage engine implementation.

Problem: Design a Distributed Key-Value Store

Design a distributed, persistent key-value store capable of handling high write throughput and low-latency reads. Assume the system needs to scale horizontally across multiple data centers.

Functional Requirements

  • put(key, value): Insert or update a value for a given key.
  • get(key): Retrieve the value for a given key.
  • delete(key): Remove a key-value pair.
  • scan(start_key, end_key): Return all values within a given range.

Non-Functional Requirements

  • High availability: The system must remain operational during node failures.
  • Scalability: The system should handle petabytes of data and millions of requests per second.
  • Consistency: Define the consistency model (e.g., eventual vs. strong) and justify your choice.

Your design should address:

  1. Data Partitioning: How will you distribute data across the cluster? How do you handle cluster resizing?
  2. Storage Engine: Choose a storage architecture (e.g., LSM-tree vs. B-Tree) and explain your reasoning based on workload characteristics.
  3. Replication: How do you ensure data durability and handle node failures? How do you manage replica synchronization?
  4. API and Communication: Define the interfaces and the communication strategy between nodes and clients.
  5. Performance: Discuss how to optimize for range scans and how to manage background processes like compaction.

Hints

Hint 1

Consider using consistent hashing to partition data while minimizing remapping during scaling operations.

Hint 2

LSM-trees are often preferred over B-Trees for high-write-throughput systems because they turn random writes into sequential disk I/O.

Hint 3

Think about using a consensus protocol like Raft or Paxos if you need to ensure strong consistency for configuration or metadata management.

Follow-up questions

  • How would your design change if the workload shifted to be read-heavy with infrequent writes?
  • Explain how you would implement a 'hinted handoff' mechanism to improve availability during a temporary node failure.
  • What metrics would you monitor to detect 'hot partitions' and how would you rebalance the data effectively?