Bird
Raised Fist0

Graph Databases - When Relationships Are the Primary Data

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Graph Databases - When Relationships Are the Primary Data
45 min · senior
senior

You are designing a graph database backend for a social networking startup with 50 million daily active users (DAU). The system must efficiently store and query billions of relationships (edges) and nodes, supporting complex traversals and relationship-centric queries. The workload is read-heavy with frequent relationship updates. The system must provide P99 query latency under 200ms, support end-to-end encryption at rest and in transit, and allow offline data delivery for mobile clients with eventual sync.

Constraints
  • Support 50M DAU with up to 10 billion edges and 1 billion nodes
  • P99 query latency under 200ms for relationship-centric queries
  • End-to-end encryption at rest and in transit (TLS + disk encryption)
  • Offline data delivery with eventual consistency and conflict resolution
  • High availability with multi-region replication and failover
📋
Guided Steps
1/5
Step 1
Data Model and Storage Choice
How would you model nodes and relationships in storage to optimize for relationship-centric queries at scale?
💡 Hint
Consider storage engines optimized for graph traversals and adjacency queries with efficient edge lookups.
Key Decision
Use JanusGraph on top of Apache Cassandra with edge-centric partition keys to store relationships, enabling efficient adjacency scans and range queries.
Interviewer Expectation
Mid: Names JanusGraph and Cassandra. Senior: Explains edge-centric partition keys to collocate edges for a node, enabling O(1) adjacency scans and why relational DBs or document stores fail at this scale.
⚠️Common Wrong Answer
Using relational databases with join queries - joins on billions of edges cause high latency and do not scale horizontally.
Step 2
Query Execution and Indexing
How will you design query execution and indexing to meet P99 latency under 200ms for relationship traversals?
💡 Hint
Think about graph-specific indexes and caching layers that reduce disk I/O and speed up common traversals.
Key Decision
Implement composite and vertex-centric indexes in JanusGraph with Redis caching for hot adjacency lists to reduce disk reads and accelerate traversals.
Interviewer Expectation
Mid: Mentions use of JanusGraph indexes. Senior: Details vertex-centric indexes for adjacency, Redis caching with TTL for hot nodes, and fallback strategies when cache misses occur.
⚠️Common Wrong Answer
Relying solely on full graph scans or secondary indexes without caching - leads to high tail latency and query timeouts.
Step 3
Security and Encryption
How will you ensure end-to-end encryption at rest and in transit for sensitive graph data?
💡 Hint
Consider TLS for network encryption and disk-level encryption integrated with your storage backend.
Key Decision
Use TLS 1.3 for all client-server and inter-node communication plus Cassandra Transparent Data Encryption (TDE) for disk encryption at rest.
Interviewer Expectation
Mid: Names TLS and disk encryption. Senior: Explains TLS 1.3 benefits, key management integration with KMS, and how Cassandra TDE encrypts SSTables without impacting read/write performance significantly.
⚠️Common Wrong Answer
Encrypting only in transit or only at rest - leaves data vulnerable during one phase, violating compliance.
Step 4
Offline Data Delivery and Sync
How would you design offline data delivery and eventual sync for mobile clients with conflict resolution?
💡 Hint
Think about client-side caching, change logs, and conflict-free replicated data types (CRDTs) or version vectors.
Key Decision
Use client-side local graph cache with sync via Kafka change logs and implement CRDT-based conflict resolution for relationship updates.
Interviewer Expectation
Mid: Mentions offline cache and sync. Senior: Explains Kafka as durable change log, CRDTs for automatic conflict resolution, and how version vectors track causal dependencies for consistency.
⚠️Common Wrong Answer
Using last-write-wins without causal tracking - causes data loss and inconsistent graph states after sync.
Step 5
High Availability and Multi-Region Replication
How will you design replication and failover to ensure high availability across multiple regions?
💡 Hint
Consider storage-level replication and global coordination mechanisms that minimize latency and data loss.
Key Decision
Use Cassandra’s multi-datacenter replication with QUORUM consistency for writes and reads, combined with Paxos-based lightweight transactions for critical updates.
Interviewer Expectation
Mid: Names Cassandra multi-DC replication. Senior: Explains QUORUM consistency trade-offs for latency vs durability, Paxos for linearizable updates, and failover strategies to avoid split-brain.
⚠️Common Wrong Answer
Asynchronous replication without consistency guarantees - leads to stale reads and data divergence.
🔌
API Design Challenge
Sketch 3 core API endpoints for this graph database system focusing on relationship-centric operations.
Hints
  • How does the client create or update relationships between nodes?
  • How does the client query relationships and traverse the graph efficiently?
  • How does the client acknowledge or sync offline changes to maintain consistency?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of a graph database engine optimized for relationship queries (JanusGraph + Cassandra)
  • Edge-centric partitioning to enable efficient adjacency scans
  • TLS and disk encryption for end-to-end security
  • Offline data delivery with conflict resolution (CRDTs or version vectors)
  • Multi-region replication with strong consistency guarantees
Good to Have - 30%
  • Caching layer (Redis) to reduce tail latency on hot nodes
  • Use of Kafka as a durable change log for sync
  • Paxos lightweight transactions for linearizable updates
Bonus - 10%
  • Integration with KMS for encryption key management
  • Detailed API design for relationship-centric operations
Anti-patterns to Avoid
Using relational databases with joins for graph queries - causes high latency and poor horizontal scalability due to expensive join operations on billions of edges.
Relying on last-write-wins conflict resolution without causal tracking - leads to data loss and inconsistent graph states after sync because concurrent updates overwrite each other without awareness.
Encrypting only in transit or only at rest - exposes data during one phase, leaving it vulnerable to interception or unauthorized access.
Polling-based offline sync without durable logs - causes excessive load on servers and inconsistent client states due to missed or duplicated updates.
Asynchronous multi-region replication without consistency guarantees - leads to stale reads and split-brain scenarios causing data divergence.
Full graph scans or secondary index scans without caching - causes high P99 latency and query timeouts due to expensive disk I/O.
✅
Model Answer
▼ Reveal

Design uses JanusGraph on Cassandra with edge-centric partitioning to optimize relationship queries at scale. Security is ensured via TLS 1.3 for all network communication and Cassandra Transparent Data Encryption (TDE) at rest. Query latency is improved using vertex-centric and composite indexes with Redis caching for hot adjacency lists. Offline data delivery is supported through client-side local graph caches synced via Kafka change logs, employing CRDTs for conflict resolution. High availability is achieved with Cassandra multi-datacenter replication using QUORUM consistency and Paxos lightweight transactions. Encryption keys are managed through an integrated KMS.

Key Decisions
  • Choosing JanusGraph on Cassandra for scalable graph storage optimized for relationship-centric queries
  • Using edge-centric partition keys to enable O(1) adjacency scans and efficient range queries
  • Implementing vertex-centric and composite indexes to speed up common traversals
  • Adding Redis caching for hot adjacency lists to reduce disk I/O and meet P99 latency targets
  • Enforcing TLS 1.3 for all network communication to secure data in transit
  • Applying Cassandra TDE to encrypt SSTables on disk without significant performance impact
  • Employing Kafka as a durable change log to support offline sync and eventual consistency
  • Using CRDTs and version vectors on client and server to resolve conflicts and maintain causal consistency
  • Configuring Cassandra multi-region replication with QUORUM consistency to balance latency and durability
  • Utilizing Paxos lightweight transactions for linearizable updates on critical data
  • Integrating with a KMS for secure encryption key management and rotation
  • JanusGraph on Apache Cassandra with edge-centric partition keys for adjacency queries
  • Vertex-centric and composite indexes in JanusGraph to speed up traversals
  • Redis caching layer for hot adjacency lists with TTL-based eviction
  • TLS 1.3 for all network communication and Cassandra Transparent Data Encryption (TDE) at rest
  • Kafka as a durable change log for offline sync and CRDTs for conflict resolution
  • Cassandra multi-datacenter replication with QUORUM consistency and Paxos lightweight transactions
  • Client-side local graph cache enabling offline queries and eventual sync
  • Key management system (KMS) integration for encryption key lifecycle management

Practice

(1/5)
1. If the commit metadata database becomes unavailable, what is the immediate failure observed when a user tries to create a new branch?
medium
A. The system creates the branch but marks it as unverified until metadata is restored
B. The branch creation request fails immediately with an error indicating metadata service unavailability
C. The system queues the branch creation request and retries later without user notification
D. The branch is created locally on the client but not persisted to the server

Solution

  1. Step 1: Understand role of commit metadata DB

    Commit metadata DB stores branch pointers; without it, server cannot persist new branches.

  2. Step 2: Trace branch creation failure

    Client may create branch locally, but server cannot persist it, so branch is effectively lost or inconsistent.

  3. Step 3: Eliminate other options

    Queuing without notification hides failure; immediate error is possible but not typical if client allows local ops; marking unverified branches requires metadata DB access.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Metadata DB down -> branch created locally but not persisted [check]
Hint: Metadata DB down -> local branch only, no server persistence [check]
Common Mistakes:
2. If the Inverted Index Update Service crashes and stops updating document frequencies (DF), what is the exact failure observed in search relevance?
medium
A. The system automatically switches to BM25 scoring without DF dependency
B. Ranking uses stale DF causing relevance scores to drift and degrade over time
C. New documents are not indexed but existing DF remains accurate
D. Search queries fail with errors due to missing DF data

Solution

  1. Step 1: Understand DF update role

    Inverted Index Update Service maintains DF counts; if it crashes, DF stops updating and becomes stale.

  2. Step 2: Trace impact on ranking

    Ranking cannot rely on fresh DF; system falls back to BM25 variant that tolerates stale DF or uses approximations; queries do not error out; new documents may still be indexed but DF is outdated.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    System falls back to BM25 variant tolerating stale DF [check]
Hint: Without DF updates, system falls back to BM25 variant [check]
Common Mistakes:
3. For a time-series IoT data ingestion system requiring high write throughput and efficient range queries by device and time, which data modeling approach is best?
medium
A. Partition by timestamp and cluster by device ID
B. Partition by device ID and cluster by timestamp within each partition
C. Use a single partition key for all devices and cluster by timestamp
D. Use a relational database with indexes on device and timestamp

Solution

  1. Step 1: Analyze query and write patterns

    Queries filter by device and time ranges; writes are high volume per device.

  2. Step 2: Evaluate partitioning strategies

    Partitioning by device ID localizes writes and queries; clustering by timestamp supports efficient range scans. Single partition key causes hotspots; partitioning by timestamp scatters device data, hurting queries; relational DBs can't handle high write scale.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Partition by device ID + cluster by timestamp -> balanced writes and efficient queries [check]
Hint: Partition by device, cluster by time for time-series data [check]
Common Mistakes:
4. At 10x scale, which component in a bulkhead-isolated microservices system is most likely to fail first, and why?
hard
A. The shared database, because it becomes a global bottleneck under increased load
B. The bulkhead thread pools, because fixed-size partitions limit concurrency and cause request rejections
C. The load balancer, because it cannot handle the increased number of service instances
D. The network infrastructure, due to increased cross-service communication overhead

Solution

  1. Step 1: Analyze scaling impact on components

    Shared database (A) is a bottleneck but bulkheads isolate failures before database overload. Load balancer (C) scales horizontally. Network (D) overhead increases but is less immediate.

  2. Step 2: Identify bulkhead thread pool limits

    Bulkhead thread pools have fixed sizes; at 10x load, they saturate first, causing request rejections and failure to scale.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Bulkhead thread pools saturate first due to fixed resource limits [check]
Hint: Fixed bulkhead pools saturate first at scale [check]
Common Mistakes:
5. At 10x scale, which component in a TCP-based chat system is most likely to fail first and why?
hard
A. The chat servers, because maintaining many TCP connections consumes memory and CPU per connection
B. The database, because increased writes cause locking and slow queries
C. The load balancer, because it cannot distribute TCP connections evenly
D. The network switches, because TCP traffic overwhelms routing tables

Solution

  1. Step 1: Identify stateful components at scale

    Chat servers maintain stateful TCP connections, each consuming resources like memory and CPU.

  2. Step 2: Analyze scaling impact

    At 10x scale, the number of concurrent TCP connections overwhelms server resources, causing failures before database or network components.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Stateful TCP connections -> chat servers bottleneck first [check]
Hint: Stateful TCP connections -> chat servers bottleneck first [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard