Distributed Key-Value Store

August 7, 2024 6:15 PM PDT

---

This meeting focused on the design of a next-generation distributed key-value (KV) store that will support various services, including authentication, authorization, and messaging. The discussion emphasized the technical requirements, scaling considerations, and architectural decisions necessary to ensure high availability, robustness, and performance.

Functional Requirements

• Services Supported:
  • Authentication
  • Authorization
  • Messaging
• Exclusions:
  • Payment processing
• Key Features:
  • Support for range queries
  • Eventual consistency (no need for transactions)
  • Data type: String

Scaling Requirements

• Storage Capacity: 5 PB
• Key/Value Scaling: Linear scaling
• Data Centers: Multi-data center support anticipated after five years
• Latency: Real-time user experience, with a target of ≤ 0.5 seconds
• Availability: 99.9%
• Robustness: User data should not be lost
• Read/Write Ratio: 99/1
• Technical Implications:
  • B+ tree is preferred over LSM tree for performance
  • CAP Theorem: Prioritize Availability > Partition > Consistency
  • Non-SQL architecture
  • Use of DNS and TCP load balancers

Partitioning Strategy

• Method: Partitioning based on a hash method
• Replication: 3 replicas for each partition
• Multi-tenancy Support: Potential consideration for supporting multiple tenants

Range Query Support

• Approach:
  • Send range queries to all partitions
  • Calculate if keys are sequential
  • Alternative: Calculate the minimum and maximum keys for efficient querying

Node Processing for Range Queries

• Individual Node Responsibilities:
  • Cache data
  • Use hashing and Bloom filters to check key existence
  • Utilize RocksDB for data storage, which employs B+ trees and write-ahead logging
• Read/Write Optimization:
  • For read-heavy workloads: Use RocksDB with SSDs for sequential reads/writes
  • For write-heavy workloads: Consider alternatives to RocksDB

ZooKeeper Integration

• Functionality:
  • Manage primary selection and failover using generation and sequence concepts
  • Maintain status for primary and secondary nodes
  • Provide metadata management and storage backup

Additional Notes

• The interviewee presented a high-level architecture and discussed the fan-out strategy for range queries.
• There were areas where the primary selection process could have been elaborated further.

This structured approach ensures clarity in understanding the design and operational considerations for the distributed key-value store.