Katkat
Back

Design a distributed key-value store

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This problem tests your ability to design a scalable, fault-tolerant distributed key-value store, focusing on partitioning strategies, replication, and handling node failures.

Distributed Key-Value Store Design

Design a distributed key-value store that supports basic put(key, value) and get(key) operations. Your system should be capable of handling high read/write throughput and must remain functional even if individual nodes or network partitions occur.

Requirements

  1. Functional Requirements:

    • put(key, value): Stores a value associated with a key.
    • get(key): Retrieves the value for a given key.

  2. Non-Functional Requirements:

    • Scalability: The system should handle petabytes of data by adding more nodes.
    • Availability: The system should remain available for reads and writes even during node failures.
    • Fault Tolerance: The system must survive the loss of a data node.

Constraints & Assumptions

  • The system must provide a consistent interface for clients via a load balancer or coordinator.
  • Assume the data exceeds the capacity of a single machine.
  • Your design should address how you handle data partitioning (sharding) and replication across multiple nodes.

Deliverables

  • API Design: Define the interface for clients.
  • Data Model: Briefly explain the storage format.
  • Architecture: Provide a high-level design covering the client, the storage nodes, and the coordination mechanism (e.g., membership service or consistent hashing).
  • Failure Handling: Explain how the system detects a dead node and handles recovery.

Hints

Hint 1

Consider using consistent hashing to map keys to nodes, which minimizes remapping when nodes are added or removed.

Hint 2

Decide on a replication strategy (e.g., primary-backup or leaderless with quorum) to balance consistency and availability.

Hint 3

Think about how a membership service, like Zookeeper or an implementation of a gossip protocol, can keep track of healthy nodes.

Follow-up questions

  • How would you handle a 'hot key' scenario where a single key receives significantly more traffic than others?
  • If you chose a strong consistency model, how would you ensure that a read always reflects the most recent write in the presence of network partitions?
  • How would you implement rebalancing or data migration when the cluster size grows from 10 to 100 nodes?