Unicorn: A System for Searching the Social Graph

Abstract

📜 Abstract

Unicorn is an online, in-memory social graph-aware indexing system designed to search trillions of edges between tens of billions of users and entities on thousands of commodity servers. Unicorn is based on standard concepts in information retrieval, but it includes features to promote results with good social proximity. It also supports queries that require multiple round-trips to leaves in order to retrieve objects that are more than one edge away from source nodes. Unicorn is designed to answer billions of queries per day at latencies in the hundreds of milliseconds, and it serves as an infrastructural building block for Facebook’s Graph Search product. In this paper, we describe the data model and query language supported by Unicorn. We also describe its evolution as it became the primary backend for Facebook’s search offerings.

Description

✨ Summary

Unicorn is Facebook’s large-scale, online search system for structured social-graph data. It adapts conventional information-retrieval techniques—especially inverted indexes, posting lists, set operations, ranking, and in-memory serving—to a graph containing tens of billions of nodes and trillions of edges. The system was designed to support billions of daily queries with response times generally in the hundreds of milliseconds and served as an infrastructure component for Facebook Graph Search. (db.disi.unitn.eu)

The social graph is represented using adjacency lists stored as posting lists. A query term conventionally combines an edge type and source identifier, such as friend:5 or likes:5. Each result contains an identifier, a globally consistent sort key, and optional application-specific metadata. The index is partitioned by result identifier rather than by query term. This allows set operations to execute close to the data, distributes computation across shards, and permits partial results to be returned when machines or network paths fail.

Queries are expressed as composable s-expressions supporting intersection, union, difference, weak conjunction, strong disjunction, and ranking based on matching terms or application-specific metadata. The cluster uses a hierarchy of top aggregators, rack aggregators, and in-memory index servers. Entity-specific verticals isolate users, pages, applications, events, photos, and other result types, allowing each vertical to be scaled and replicated according to its workload.

Indexes are constructed offline from database data through Hadoop-based processing and are updated in near real time through mutation streams. The serving layer combines immutable index data with a mutable update layer. This design emphasizes memory-resident serving and rapid updates rather than authoritative storage guarantees.

The paper’s main query-language additions address social ranking and multi-hop graph retrieval. WeakAnd requires some terms to match while allowing a bounded number or fraction of exceptions, which can promote socially connected results without excluding all non-friends. StrongOr imposes minimum representation requirements for selected result groups, supporting diversity in ranked results. Scoring functions can use query terms, hit metadata, and forward-index metadata.

The Apply operator performs a second query using identifiers returned by an inner query. It supports graph traversals such as friends-of-friends, photos of friends, and other multi-stage searches without fully materializing every possible derived relationship. The paper compares this approach with denormalization: explicitly storing friends-of-friends would greatly increase storage requirements, whereas Apply preserves flexibility at the cost of another backend pass and possible truncation of inner results.

The Extract operator handles one-to-few mappings by retrieving related identifiers from forward-index metadata rather than creating a large number of additional posting-list terms. This is useful for queries such as finding people tagged in photos of a given user. It avoids extra network round trips, although duplicate removal may be required during aggregation.

Unicorn does not make final privacy decisions. Instead, it attaches lineage metadata describing the graph edges that produced each result. An authoritative privacy service or frontend can then determine whether the relevant edges are visible to the requesting user. This separation avoids duplicating Facebook’s complex privacy logic and reflects the system’s preference for availability and partition tolerance over strict consistency.

The principal limitation of multi-stage queries is inner-result truncation. Large inner result sets can cause relevant outer results to be omitted, while increasing the truncation limit raises latency, CPU cost, network traffic, and response-time variance. The paper identifies ranking, selective denormalization, and query planning as ways to reduce this problem. In the reported benchmark, a simple query over a posting list containing more than six million users had an average latency of 11 ms for 100 requested results; for an Apply query, latency exceeded approximately 100 ms when the inner truncation limit reached about 5,000.

The paper documents a production system that supported Facebook typeahead and Graph Search, demonstrating that inverted-index methods and controlled multi-stage traversal could support interactive social-graph search at Facebook scale. (vldb.org) Later bibliographic records identify citations to Unicorn in work on database provenance, distributed in-memory graph databases, graph processing, inverted-list compression, disaggregated-memory indexing, and social-network data management. (rmarcus.info) The paper has also been cited in at least one patent concerning guided keyword-based data exploration. (patents.google.com) These records establish continued use of Unicorn as a reference point for large-scale graph retrieval and indexing, but they do not by themselves demonstrate that every cited system directly adopted Unicorn’s implementation.