Inside ByteGraph: How ByteDance Built a Scalable Distributed Graph Database

Why Graph‑Structured Data Matters

Most of ByteDance’s product data can be classified into three categories—user profiles and relationships, content items (videos, articles, ads), and user‑content interactions (likes, comments, shares). Combined, they form a massive social graph that drives many online services.

ByteGraph Overview

ByteGraph is a custom distributed graph database designed for online OLTP scenarios. It implements a directed‑property graph model, supports the Gremlin query language, and can scale to tens of millions of QPS with millisecond‑level latency. It now powers almost all ByteDance products, including Toutiao, Douyin, TikTok, Xigua, and Volcano.

Beyond OLTP, ByteGraph also targets offline graph analytics, a market predicted to double annually and reach $80 billion by 2020.

Data Model and API

The core elements are Vertex (point) and Edge (relationship). A vertex is identified by id (uint64_t) and type (uint32_t) and can carry arbitrary KV properties. An edge connects two vertices, has a string type, a timestamp (uint64_t), and optional KV attributes.

Edges are directional; ByteGraph supports three directions: forward (A → B), reverse (B ← A), and bidirectional (A ↔ B).

Gremlin API Examples

Creating a follow relationship:

// create vertices for users A and B

g.addV().property("type", A.type).property("id", A.id)

g.addV().property("type", B.type).property("id", B.id)

// create a directed edge A -> B with a timestamp

g.addE("关注").from(A.id, A.type).to(B.id, B.type).property("ts_us", now)

Querying two‑hop followers (A follows B and B follows C):

g.V().has("type", A.type).has("id", A.id).out("关注").where(out("关注").has("type", C.type).has("id", C.id).count().is(gte(1))

Finding friends‑of‑friends:

g.V().has("type", A.type).has("id", A.id).both("好友").both("好友").toSet()

System Architecture

ByteGraph is split into three layers, each composed of many process instances:

Query layer (bgdb) : parses Gremlin, generates execution plans, routes requests to storage nodes, aggregates results. Implemented in Go and stateless, allowing horizontal scaling.

Storage/transaction engine (bgkv) : a sharded C++ service that stores vertices and edges in a custom KV store, pushes operators down to storage for read‑performance gains, and integrates a cache layer for hot data.

Disk storage layer (KV Cluster) : a distributed KV store that provides durable, high‑capacity storage across data‑center racks.

Key Design Points

Stateless query layer enables easy scaling.

bgkv provides operator push‑down and a hybrid cache‑KV model.

All layers communicate via consistent hashing for routing.

Storing Graph Data in a KV Store

ByteGraph groups a vertex with all its outgoing edges into a Group . Small‑degree vertices are stored as a single KV pair (single‑level storage). When a vertex’s out‑degree grows beyond a threshold, it switches to a B‑Tree‑based multi‑KV layout (dual‑level storage). The system can safely migrate between the two representations online.

Single‑level KV format:

Key : source_id + source_type + edge_type Value : serialized list of outgoing edges and their attributes (excluding target vertex properties).

Dual‑level storage splits a massive edge list into multiple KV entries that form a distributed B‑Tree. The B‑Tree root key follows the same encoding as the single‑level key, while internal nodes (Meta) store pointers (PartKey) to leaf KV pairs containing edge chunks.

These techniques keep KV value sizes roughly uniform, avoiding I/O spikes caused by a few “super‑nodes” with millions of followers.

Hot‑Spot Read/Write Strategies

ByteGraph experiences hot data such as viral videos or celebrity accounts. For reads, a multi‑level query cache in bgdb can serve >200 k QPS for a single hot item, and multiple bgdb instances can share the load.

For writes, ByteGraph uses a single‑row transaction model with in‑memory locks that scale to tens of millions of concurrent writes, eliminating lock contention. Disk IOPS limits are mitigated by a Group‑Commit mechanism that batches writes into larger batches before persisting to the KV store.

Indexing

ByteGraph builds primary indexes on edge timestamps and supports secondary indexes on target vertices or custom attributes, turning many full‑graph scans into efficient range or point lookups.

Graph Computation Background

Graph databases excel at OLTP queries on small sub‑graphs, while graph computation systems handle large‑scale analytics (OLAP). Major computation models include vertex‑centric (Pregel/GAS), edge‑centric, and sub‑graph‑centric approaches.

Popular open‑source systems:

Pregel (Google, proprietary)

Giraph (Facebook)

GraphX (Spark)

Gemini (OSDI 16) – uses CSC/CSR storage, hierarchical partitioning, and adaptive push/pull communication.

ByteDance built on Gemini’s ideas to create the open‑source Tencent Plato system, then heavily re‑engineered it for production workloads that exceed Gemini’s original 4‑billion‑vertex limit.

Practical Enhancements on Plato

To support trillions of vertices, ByteDance replaced the single‑machine ID‑mapping table with a sharded distributed mapping, using hash‑based partitioning to assign continuous internal IDs while preserving original business IDs for external use.

Custom algorithm support is currently exposed via low‑level APIs; future work includes Python bindings and a DSL to lower the barrier for business teams.

Future Directions

Move from pure in‑memory to hybrid storage (NVMe, AEP) for cost‑effective scaling.

Enable dynamic graph computation that processes incremental updates without recomputing the whole graph.

Explore heterogeneous acceleration (GPU, FPGA) for compute‑intensive algorithms.

Develop a high‑level graph query language that decouples business logic from engine implementation.

Conclusion

In just a year and a half, ByteGraph evolved from a prototype to a production‑grade graph storage and computation stack that serves billions of users across dozens of products. Ongoing challenges include full ACID support, standardizing query languages, cloud‑native deployment, and HTAP capabilities, all of which guide the roadmap toward a world‑class, one‑stack graph solution.