How Facebook’s Dragon Engine Accelerates Graph Queries at Scale

Every time you visit Facebook you see a flood of information—posts, photos, check‑ins, likes, comments, and shares—customized for each user based on their interactions. The social graph consists of nodes (objects) and edges (associations), and queries typically start from a node and retrieve all edges of a given type.

Facebook originally used memcached and MySQL, then evolved to TAO (The Associations and Objects server) to optimize high‑capacity single‑hop queries. As user volume grew and multi‑hop queries became common, a new distributed query engine called Dragon was built.

Indexing Techniques

Dragon monitors real‑time updates to the graph, creates various indexes, and reduces data transferred to the web layer, lowering latency and freeing CPU cycles. It stores primary edges only and builds indices tailored to query patterns, allowing direct key‑based lookups (e.g., <PostID, Language>) and complex sorting on persistent storage.

Socially Aware Inverted Indices

Frequently queried read‑only data such as friend names is denormalized across hosts, creating a distributed inverted index. While this speeds up reads, writes become slower because updates must be replicated to all hosts holding the data, introducing a consistency‑availability trade‑off.

Functional Programming Primitives

Dragon provides about 20 functional primitives for filtering and ordering graph edges, plus a navigation primitive called assoc. Users can also define custom functions in Lua or JavaScript for complex string manipulation or regex support.

Summary

Dragon is backed by an in‑process key‑value store that updates in real time and offers eventual consistency. By combining indexing, denormalization, and functional query primitives, it reduces storage block reads by roughly 30 % and CPU usage by about 7 %, delivering query latencies as low as 1–2 ms while maintaining high availability.