Katkat
Back

Design a Column-Queryable KV Database

SnapchatSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This problem tests your ability to design a distributed key-value storage system that supports efficient column-based filtering and range scans, balancing write performance against analytical query capabilities.

Problem Statement

Design a distributed Key-Value store that supports efficient querying of specific attributes (columns) across a massive dataset of user records. Each record has a primary key user_id and a set of dynamic attributes (e.g., age, location, last_login). The system must handle high-write throughput and provide low-latency lookups by user_id, as well as secondary queries like "find all users in 'California' aged > 25."

Functional Requirements

  • put(user_id, attributes): Upsert a user record.
  • get(user_id): Retrieve all attributes for a specific user.
  • query(filter_expression): Filter users based on arbitrary column-value predicates.

Non-Functional Requirements

  • Handle Peta-scale data with high availability.
  • Support schema evolution (adding/removing columns without downtime).
  • System must scale horizontally as data volume and request traffic grow.

Your Task

Provide a high-level design covering:

  1. Data Model: How to store sparse columns effectively.
  2. Storage Architecture: How to partition and store the data to support both point lookups and range/filter queries.
  3. Indexing Strategy: Trade-offs between maintaining global secondary indexes vs. local indexes.
  4. Scalability: Strategies for sharding and handling consistent growth.

Hints

Hint 1

Consider the trade-offs between an LSM-tree based storage engine for writes and an inverted index or bitmap approach for filtering.

Hint 2

Think about whether to store data in a row-oriented format or a transposed columnar format, and how that impacts the cost of your queries.

Hint 3

Evaluate the impact of eventual consistency on the secondary indexes if you choose to decouple the primary storage from the index service.

Follow-up questions

  • How would you handle a 'hot partition' issue if a specific user segment (e.g., a massive celebrity account) receives a spike in traffic?
  • If we need to perform complex aggregations (e.g., COUNT or AVG), how would you evolve the architecture to support OLAP-style workloads?
  • How do you ensure index consistency during a distributed transaction or concurrent update to the primary key?