Practice/Databricks/Design a Key-Value Store

Design a Key-Value Store

System DesignMust

Problem Statement

Design a highly available configuration management system that allows applications across multiple data centers to read and update configuration data with strong consistency guarantees. The system must support hierarchical configuration keys (like file paths), versioning of configuration changes, and the ability to watch for changes in real-time. Configuration values can range from small flags (a few bytes) to larger documents (up to 10MB), and the system should handle both low-latency reads and coordinated updates across thousands of services.

The system needs to serve as the source of truth for critical application settings, feature flags, and operational parameters. Given that incorrect configuration can cause widespread outages, the consistency and reliability requirements are paramount. You'll need to balance strong consistency for writes with low-latency reads that can scale to handle requests from tens of thousands of application instances.

Key Requirements

Functional

Hierarchical key-value storage -- support paths like /app/service/database/timeout with the ability to query by prefix
Configuration versioning -- track every change with incrementing versions and allow clients to read historical values
Watch mechanism -- enable clients to subscribe to configuration changes and receive notifications when values update
Atomic updates -- support compare-and-swap operations to prevent conflicting concurrent updates
Access control -- restrict read and write permissions based on service identity or user credentials

Non-Functional

Scalability -- handle 100,000+ read requests per second across all data centers with <10ms p99 latency
Reliability -- tolerate data center failures with no data loss and maintain availability for reads during network partitions
Latency -- writes should complete within 50ms at p99, reads within 5ms at p99 from local replicas
Consistency -- guarantee linearizable reads for configuration changes to prevent services from seeing stale critical settings

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Consistency Model and Consensus

The interviewer will probe how you ensure that configuration updates are strongly consistent across replicas, especially when services in different regions need to see updates immediately.

Hints to consider:

Using a consensus protocol like Raft or Paxos to manage a replicated log of configuration changes
Discussing how leader election works and how you handle leader failures during critical updates
Explaining read strategies -- whether reads go to the leader, use read leases, or employ follower reads with bounded staleness
Addressing the CAP theorem tradeoff and why you prioritize consistency over availability for this use case

2. Hierarchical Data Model and Indexing

How you structure and index hierarchical configuration paths significantly impacts query performance and the ability to support prefix-based subscriptions.

Hints to consider:

Designing a storage layout that allows efficient prefix queries without scanning all keys
Using radix trees, B-trees, or prefix-compressed structures for in-memory indexing
Discussing how to handle large configuration documents that don't fit in memory alongside small flags
Explaining how directory-level watches work and how to propagate changes to subscribers efficiently

3. Watch and Notification Mechanism

Real-time notifications are critical but challenging at scale, especially when thousands of clients are watching overlapping configuration paths.

Hints to consider:

Implementing a subscription index that maps configuration paths to connected clients
Using long-polling, server-sent events, or WebSocket connections to push updates efficiently
Handling reconnection storms when a data center fails and thousands of clients reconnect simultaneously
Discussing how to batch notifications when multiple related keys change in a single transaction

4. Data Replication and Geo-Distribution

Configuration must be available in multiple data centers, but strong consistency requirements complicate replication strategies.

Hints to consider:

Choosing between synchronous replication to all regions versus a primary region with async replication
Using a multi-raft approach where each data center runs its own consensus group with cross-region coordination
Explaining how to handle network partitions between data centers while maintaining consistency
Discussing read-your-writes guarantees when a service updates config in one region and immediately reads from another

Practice/Databricks/Design a Key-Value Store

Design a Key-Value Store

System DesignMust

Problem Statement

Key Requirements

Functional

Hierarchical key-value storage -- support paths like /app/service/database/timeout with the ability to query by prefix
Configuration versioning -- track every change with incrementing versions and allow clients to read historical values
Watch mechanism -- enable clients to subscribe to configuration changes and receive notifications when values update
Atomic updates -- support compare-and-swap operations to prevent conflicting concurrent updates
Access control -- restrict read and write permissions based on service identity or user credentials

Non-Functional

Scalability -- handle 100,000+ read requests per second across all data centers with <10ms p99 latency
Reliability -- tolerate data center failures with no data loss and maintain availability for reads during network partitions
Latency -- writes should complete within 50ms at p99, reads within 5ms at p99 from local replicas
Consistency -- guarantee linearizable reads for configuration changes to prevent services from seeing stale critical settings

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Consistency Model and Consensus

The interviewer will probe how you ensure that configuration updates are strongly consistent across replicas, especially when services in different regions need to see updates immediately.

Hints to consider:

Using a consensus protocol like Raft or Paxos to manage a replicated log of configuration changes
Discussing how leader election works and how you handle leader failures during critical updates
Explaining read strategies -- whether reads go to the leader, use read leases, or employ follower reads with bounded staleness
Addressing the CAP theorem tradeoff and why you prioritize consistency over availability for this use case

2. Hierarchical Data Model and Indexing

How you structure and index hierarchical configuration paths significantly impacts query performance and the ability to support prefix-based subscriptions.

Hints to consider:

Designing a storage layout that allows efficient prefix queries without scanning all keys
Using radix trees, B-trees, or prefix-compressed structures for in-memory indexing
Discussing how to handle large configuration documents that don't fit in memory alongside small flags
Explaining how directory-level watches work and how to propagate changes to subscribers efficiently

3. Watch and Notification Mechanism

Real-time notifications are critical but challenging at scale, especially when thousands of clients are watching overlapping configuration paths.

Hints to consider:

Implementing a subscription index that maps configuration paths to connected clients
Using long-polling, server-sent events, or WebSocket connections to push updates efficiently
Handling reconnection storms when a data center fails and thousands of clients reconnect simultaneously
Discussing how to batch notifications when multiple related keys change in a single transaction

4. Data Replication and Geo-Distribution

Configuration must be available in multiple data centers, but strong consistency requirements complicate replication strategies.

Hints to consider:

Choosing between synchronous replication to all regions versus a primary region with async replication
Using a multi-raft approach where each data center runs its own consensus group with cross-region coordination
Explaining how to handle network partitions between data centers while maintaining consistency
Discussing read-your-writes guarantees when a service updates config in one region and immediately reads from another