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
Designing a scalable graph database optimized for relationship-centric queries at internet scale
mediumDatabases - NoSQLFreq: medium
⚙️
Functional Requirements
  • Store and query billions of nodes and edges with rich properties
  • Support efficient traversal queries (e.g., shortest path, neighborhood queries) with low latency
  • Allow real-time updates to nodes and edges with strong consistency on relationships
  • Support complex graph analytics such as community detection and influence scoring
  • Provide APIs for CRUD operations on nodes and edges and graph pattern matching queries
  • Enable multi-tenant isolation and access control on graph subsets
📊
Non-Functional Requirements
  • Support 2 billion daily active users generating 40 relationship updates per user per day
  • Achieve 99.99% availability with automatic failover and replication
  • Maintain 100ms P99 latency for common traversal queries on neighborhood sizes up to 1000 nodes
  • Scale to handle 925K writes per second and 10M reads per second at peak
  • Data retention of 1 year with replication factor of 3 for durability
❓
Clarifying Questions to Ask
  • What is the expected average and max degree (number of edges) per node?
  • Are relationship properties mutable or mostly append-only?
  • What types of graph queries are most common (e.g., neighborhood, shortest path, pattern matching)?
  • Is strong consistency required for relationship updates or eventual consistency acceptable?
  • What is the expected read-to-write ratio for graph operations?
  • Are there multi-region or geo-distributed deployment requirements?
Out of Scope
✗ Designing a full graph query language parser or optimizer
✗ Handling unstructured data storage (e.g., blobs or files)
✗ Building a visualization or UI layer for graph exploration
✗ Implementing machine learning models on graph data
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 relationship updates per day
  • Average size per relationship update (edge + properties) is 100 bytes
  • Read-to-write ratio is 10:1
⚡
QPS Calculation
write qps2B × 40 / 86400 ≈ 925,926 writes/sec
peak write qpsAssuming 2× peak factor → 1,851,852 writes/sec
read qps10 × write_qps = 9,259,260 reads/sec
peak read qps2× peak factor → 18,518,520 reads/sec
💾
Storage Estimate
daily storage925,926 writes/sec × 100 bytes × 86400 sec ≈ 8 TB/day
retention days365
total storage8 TB/day × 365 ≈ 2.9 PB raw data
with replication2.9 PB × 3 (replication factor) ≈ 8.7 PB total storage
🖥️
Server Estimate
storage nodesAssuming 100 GB usable per node → 8.7 PB / 100 GB ≈ 87,000 nodes
query nodesAssuming each node handles 10K QPS → 18.5M / 10K ≈ 1,852 query nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          | Client API Srv |
          +-------+--------+
                  |
          +-------v--------+
          |  Query Router  |
          +-------+--------+
          /               \
 +--------v--------+  +----v---------+
 | Graph Storage   |  | Graph Compute|
 | Cluster (Cassandra) |  | Cluster (Spark) |
 +--------+--------+  +----+---------+
          |                 |
   +------v------+    +-----v-------+
   | Kafka Event |    | Analytics DB|
   | Streaming   |    | (Druid)     |
   +-------------+    +-------------+
🧩
Components
Client API Server
Handles client requests, authentication, and request validation
Why thisStateless REST/gRPC servers scale horizontally behind load balancers for low latency
Why notMonolithic servers limit scalability and increase failure blast radius
Query Router
Routes graph queries to appropriate storage or compute clusters based on query type
Why thisSeparates read/write paths and enables query optimization and caching
Why notDirect client access to storage nodes causes uneven load and security risks
Graph Storage Cluster (Apache Cassandra)
Stores nodes and edges with properties in a distributed wide-column store
Why thisCassandra offers linear write scalability, tunable consistency, and efficient range scans for adjacency lists
Why notNeo4j or JanusGraph with RDBMS backends do not scale linearly to billions of writes/sec
Graph Compute Cluster (Apache Spark GraphX)
Performs batch and iterative graph analytics like community detection and influence scoring
Why thisSpark GraphX supports distributed graph processing at petabyte scale with fault tolerance
Why notGiraph lacks active development and scalability for very large graphs
Kafka Event Streaming
Streams relationship updates asynchronously for analytics and eventual consistency
Why thisKafka provides durable, ordered, partitioned logs with high throughput for event-driven pipelines
Why notRabbitMQ lacks partitioning and throughput needed for 1.8M writes/sec
Analytics Database (Apache Druid)
Stores aggregated graph metrics and time-series data for real-time dashboards
Why thisDruid supports fast OLAP queries on large-scale event data with sub-second latency
Why notElasticsearch is optimized for text search, not high cardinality aggregations
🔄
Data Flow
1
Client API Server → Query Router
Receive graph query or update request and forward to router
Centralizes routing logic and load balancing
2
Query Router → Graph Storage Cluster
Route write requests to Cassandra nodes based on partition key
Ensures data locality and consistent hashing for adjacency lists
3
Graph Storage Cluster → Kafka Event Streaming
Publish relationship update events asynchronously
Decouples write path from analytics and eventual consistency consumers
4
Query Router → Graph Storage Cluster
Route read/traversal queries to storage nodes or cache
Optimizes for low latency neighborhood queries
5
Kafka Event Streaming → Graph Compute Cluster
Stream updates for batch graph analytics and scoring
Enables offline and near-real-time analytics
6
Graph Compute Cluster → Analytics Database
Store aggregated metrics for dashboard queries
Supports operational monitoring and business insights
🗄️
Nodes
PK: node_id
node_idnode_typepropertiescreated_atupdated_at
Stores graph nodes with their properties and metadata
🗄️
Edges
PK: src_node_id
src_node_idedge_typedst_node_idpropertiescreated_atupdated_at
Stores edges representing relationships between nodes with properties
🔌
CreateNode
Request
{
  "node_type": "string",
  "properties": "map<string, string>"
}
Response
{
  "node_id": "string",
  "status": "string"
}
Creates a new node with given type and properties
🔌
CreateEdge
Request
{
  "src_node_id": "string",
  "edge_type": "string",
  "dst_node_id": "string",
  "properties": "map<string, string>"
}
Response
{
  "edge_id": "string",
  "status": "string"
}
Creates a new edge (relationship) between two nodes
🔌
QueryNeighborhood
Request
{
  "node_id": "string",
  "depth": "int"
}
Response
{
  "neighbors": "list<node>",
  "edges": "list<edge>"
}
Fetches neighborhood nodes and edges up to specified depth

Practice

(1/5)
1. For candidate-job matching, which architecture better supports real-time personalized recommendations with low latency and frequent profile updates?
medium
A. Precomputed static candidate-job similarity scores stored in a relational database
B. Batch processing with nightly offline model training and periodic reindexing
C. Online feature store with streaming updates feeding a real-time scoring service
D. Client-side filtering of job listings based on cached candidate preferences

Solution

  1. Step 1: Analyze real-time personalization needs

    Low latency and frequent profile updates require online, streaming data processing.

  2. Step 2: Evaluate architectures

    Batch (A) is too stale; static precomputed scores (C) can't adapt quickly; client-side filtering (D) lacks server-side intelligence. Online feature store with streaming (B) supports fresh data and low latency scoring.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Streaming updates + real-time scoring -> fresh personalized matches [check]
Hint: Streaming + online features enable fresh real-time recommendations [check]
Common Mistakes:
2. If the sliding window counter's timestamp cleanup process fails, what is the most likely failure observed in rate limiting?
medium
A. Requests are allowed without limit because counters reset incorrectly
B. Fixed window counters reset too frequently causing bursty traffic spikes
C. Rate limiter blocks requests indefinitely due to stale timestamps inflating counts
D. Token bucket refills tokens too slowly causing underutilization

Solution

  1. Step 1: Understand sliding window cleanup role

    Cleanup removes timestamps outside the window; failure causes stale timestamps to accumulate.

  2. Step 2: Accumulated stale timestamps inflate request counts, causing the rate limiter to block legitimate requests indefinitely

    This leads to false positives in rate limiting, denying service unnecessarily.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Failed cleanup -> stale timestamps inflate counts -> requests blocked indefinitely [check]
Hint: No cleanup means stale timestamps block requests falsely [check]
Common Mistakes:
3. Without the asynchronous replication component in a PACELC system prioritizing latency, what exactly breaks during a network partition?
medium
A. Reads return stale data indefinitely without updates
B. Writes block until all replicas acknowledge, causing high latency
C. Local writes succeed but are lost if the node crashes before replication
D. The system automatically switches to a single primary mode

Solution

  1. Step 1: Identify role of asynchronous replication

    It propagates updates to other replicas to keep data fresh despite partitions.

  2. Step 2: Trace failure without async replication

    Without it, replicas do not get updates, so reads return stale data indefinitely.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    No async replication -> stale reads persist during partition [check]
Hint: No async replication -> stale reads never update during partition [check]
Common Mistakes:
4. For a system requiring globally unique, roughly time-ordered IDs across multiple data centers, which approach best balances latency and uniqueness guarantees?
medium
A. Use a single centralized ID generator with synchronous replication to all data centers
B. Use decentralized Snowflake-like generators with loosely synchronized clocks and node IDs
C. Generate UUID v4 randomly at each data center without coordination
D. Use database auto-increment IDs partitioned by data center and combine with data center ID

Solution

  1. Step 1: Evaluate centralized generator with sync replication

    This causes high latency and single point of failure, unsuitable for geo-distributed low-latency needs.

  2. Step 2: Assess decentralized Snowflake approach

    Decentralized generators with node IDs and loosely synchronized clocks provide low latency and uniqueness with approximate ordering.

  3. Step 3: Consider UUID v4 and DB auto-increment

    UUID v4 lacks ordering; DB auto-increment with partitioning risks collisions and coordination overhead.

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Decentralized Snowflake -> low latency + uniqueness + approximate ordering [check]
Hint: Decentralized with node ID and clock sync balances latency and uniqueness [check]
Common Mistakes:
5. At 10x scale, which component in a real-time chat system is most likely to fail first due to latency-throughput trade-offs, and why?
hard
A. The database, because it cannot handle the increased write volume
B. The message broker, because partition count cannot be increased beyond a fixed limit
C. The load balancer, because it cannot distribute traffic evenly at high scale
D. The chat servers, because WebSocket connections are stateful and cannot be resharded easily

Solution

  1. Step 1: Identify stateful bottlenecks

    Chat servers maintain WebSocket connections statefully, limiting horizontal scaling.

  2. Step 2: Compare other components

    Databases (A) can be sharded; brokers (C) can add partitions; load balancers (D) scale horizontally; chat servers (B) fail first due to sticky state and connection limits.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stateful WebSocket servers limit scaling more than other components [check]
Hint: Stateful WebSocket servers block scaling first at 10x load [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