REDTao: A Scalable Graph Storage System for Trillion‑Scale Social Networks at Xiaohongshu

Xiaohongshu, a community‑centric product, faces massive social‑graph data (over a trillion relationships) that grows rapidly, causing high CPU load, frequent scaling, and complex maintenance across many business units. To address these challenges, the team designed REDTao, a custom graph storage system inspired by Facebook's Tao.

REDTao follows a three‑layer architecture: an access layer (REDTaoClient → router deployed on Kubernetes), a cache layer (Follower‑Leader hierarchy with local hash tables), and a persistent layer (MySQL cluster). The router provides a unified service name and routes requests based on edge type, enabling seamless multi‑type graph queries.

Read operations first probe the local cache on the Follower; on a miss they fall back to the Leader and finally to MySQL, after which the result is committed back to both caches. Write operations follow a similar path, with conflict detection via cache checks and versioned updates to ensure consistency.

REDTao exposes a simple graph API: AddAssoc , DeleteAssoc , ExistAssoc , GetAssoc , and UpdateAssocData . Additional APIs support risk control (marking fraudulent edges) and cross‑cloud data synchronization via a custom DTS service.

Usability improvements include rich semantic APIs, a unified access URL that abstracts multiple REDTao clusters, and automatic routing based on configuration, allowing business teams to interact with the graph without handling cache or MySQL details.

High‑availability features comprise a distributed cache with Leader/Follower groups, automatic failure detection and recovery, rate‑limiting to protect MySQL, and a robust MySQL cluster with sharding and horizontal scaling.

The internal data structure uses a three‑level nested hash table: top‑level maps from from_id to a graph object, second‑level maps from type_id to edge metadata (including a time‑ordered skip‑list), and third‑level stores up to 1,000 recent edges per to_id to limit memory usage.

Performance tests show cache hit rates above 90%, query latency under a few milliseconds, and the ability to handle 1.5 million queries per second on a 16‑core VM with only 22.5 % CPU utilization. Single‑node QPS reaches 30 k, each RPC aggregating ~50 queries.

Consistency mechanisms include global version numbers for conflict resolution, hash‑based routing to guarantee that reads and writes for the same FromId+AssocType hit the same Follower, asynchronous invalidation queues for Leader‑Follower sync, and optional strong‑read flags to force master reads.

Cross‑cloud multi‑active deployment uses MySQL binlog subscription (DTS) to propagate updates and invalidate stale cache entries, ensuring eventual consistency across regions.

Cloud‑native capabilities enable elastic scaling, multi‑AZ deployment, automatic fault migration, and rolling upgrades by treating each Leader/Follower group as an isolated unit.

Business migration to REDTao is performed gradually with a Tao Proxy SDK that supports dual‑write/dual‑read, data comparison, and cut‑over once consistency is verified.

After deployment, data‑access cost dropped by over 70 %, MySQL CPU usage fell dramatically, and overall infrastructure cost decreased by 21.3 %. The system also reduced the need for additional scaling, limiting cost growth to 14.7 % despite a 250 % increase in graph traffic.

Future work includes tighter integration of REDGraph (another internal graph engine) with REDTao, improving cache invalidation under prolonged failures, and extending the system to handle more complex multi‑cloud scenarios.