# Design a graph database like Neo4j: system design interview question

> A graph database with efficient adjacency access, bounded queries across machines, and correct edge updates during failures.

Source: https://sysround.com/questions/design-graph-database-like-neo4j
Updated: 2026-11-05


Difficulty: hard. Levels: Senior, Staff+.

## How the interviewer opens it

"Design a database that stores vertices and edges and supports relationship queries. Keep queries efficient as the graph grows beyond one machine."

## What to clarify first

- Graph operations
- Graph size and shape
- Read and write traffic
- Record sizes
- Latency
- Query limits
- Consistency and availability
- Durability and deployment
- Retries and deletion
- Excluded features

## Scope of a strong answer

Core requirements:

- Create, read, update, and delete vertices and edges
- Find adjacent vertices by edge type and direction
- Execute bounded queries across several hops
- Distribute data and query work across machines

Usually out of scope:

- Full Cypher or Gremlin support
- Transactions across multiple entities
- Unbounded queries and global graph algorithms
- Multiple regions

## What interviewers probe

### Edges at one vertex

Most vertices have few edges, but one large vertex can dominate storage, query work, and traffic.

### Queries across machines

Each hop can multiply remote work. Cycles, duplicate routes, and slow machines make both cost and completeness difficult to control.

### Edge changes and failures

One edge appears in several access paths. Retries, delayed updates, and deletion can make those paths disagree.

### Graph placement as it grows

Balanced storage can cause many remote hops. Better locality can create large or hot partitions as the graph changes.

## Common mistakes

- Treating a graph traversal as a sequence of independent point reads
- Using average degree to predict every query cost
- Assuming a result limit also limits examined edges
- Ignoring incoming edges and their update cost
- Promising complete results after a required machine fails
- Adding complex graph placement before measuring remote query costs

## The bar by level

- **Senior:** Designs batched queries across owners with explicit work limits. Handles large vertices, duplicate writes, adjacency delay, deletion, and incomplete results.
- **Staff+:** Defines correctness contracts across failures and ownership changes. Quantifies remote work and write amplification. Justifies placement choices and safe growth without unnecessary coordination.

Practice this question with an AI interviewer: https://sysround.com/practice/new?problem=graph-database


---
SysRound (https://sysround.com) is an AI practice tool for system design interviews. It has a voice or typed AI interviewer and a shared whiteboard. At the end, you get feedback on each skill and a model answer. The AI feedback can be wrong.