AOEE: a TAO-style social graph cache in Rust

Every social product eventually asks the same handful of questions, millions of times a second. Who does this person follow? Do these two people know each other? Which friends do we have in common? Who liked this post, and how? Who might this person want to meet next?

None of those questions is hard on its own. What makes them hard is the shape of the data: a few accounts with millions of edges, millions of accounts with a few dozen, and a workload that is overwhelmingly reads. Asking a relational database to answer "mutual friends" with a self-join on an edges table works right up until it doesn’t.

Facebook’s answer, described in the 2013 USENIX paper on TAO, was to treat the graph as a cache of associations in front of MySQL and to serve the read patterns directly. AOEE — Attribute Object Enterprise Edition — is my take on that idea, built as the graph layer for the enterprise social platform I was writing about in another article. The code is on GitHub.

Figure 1. How a request reaches the graph: the JVM side handles HTTP, datasets, and benchmarks; the graph lives in a sharded Rust server behind gRPC.

The data model: ids, edge types, and edge keys

Everything in AOEE is a 64-bit EntityId. The top 16 bits hold the entity type (user, post, comment, photo, group, page, event, tag, or a custom type) and the bottom 48 bits the id itself. Knowing what an id refers to costs a shift, not a lookup, and ids stay plain integers — which matters a great deal for compression, as we’ll see.

Ids can also be generated without a coordinator: the 48-bit part becomes a 32-bit timestamp (seconds since a 2020 epoch) followed by a 16-bit sequence. Any client in any language can mint them.

Relationships are typed, and almost every type comes as a forward/reverse pair: FOLLOWS/FOLLOWED_BY, LIKES/LIKED_BY, AUTHORED/AUTHORED_BY, MEMBER_OF/ HAS_MEMBER, TAGGED_IN/HAS_TAG, and so on. FRIEND_OF is its own reverse. The clients know each type’s reverse, so an application stores both directions and "who follows Alice?" is as cheap as "whom does Alice follow?" — no reverse index to scan. A few types carry a one-byte metadata value per edge — LIKES uses it for the reaction (like, love, haha, wow, sad, angry).

The unit of storage is the posting list for an EdgeKey — a source entity plus an edge type. EdgeKey(User:42, FOLLOWS) is the sorted list of every entity user 42 follows.

That word posting list is deliberate. Most of my career has been in search, and a search engine’s inverted index is exactly this: for each term, a sorted list of document ids, compressed, with fast intersection. Swap "term" for "user and relationship" and the whole toolbox comes across — delta encoding, variable-length integers, skip tables, galloping intersection. AOEE is, in a sense, a search engine whose documents are people.

Posting lists: an LSM tree in miniature

Graphs are mostly read, but they are written constantly, and a perfectly compressed sorted array is miserable to insert into. So each posting list is a tiny log-structured merge tree.

Figure 2. A posting list is an append-only write buffer plus immutable, sorted, encoded segments; compaction moves one into the other.

New edges and deletes go into an unsorted write buffer: the destination id, a nanosecond timestamp, the metadata byte, and a tombstone flag for deletes. When the buffer passes a threshold (256 entries by default in the current code), it is compacted: sorted, deduplicated, tombstones applied, and written out as an immutable segment with the smallest workable encoding. Small segments are merged into larger ones by leveled compaction, the same idea as in RocksDB and LevelDB.

Reads walk a merged iterator over the buffer and the segments, newest first. Each segment records its minimum and maximum id, so a contains check skips segments whose range cannot hold the target, and delta-encoded segments carry a skip table so a lookup can jump close to the answer and decode forward from there rather than decoding the whole segment.

Four encodings, chosen per segment

Social-graph lists span six orders of magnitude, and no single encoding suits all of them. AOEE picks one per segment:

Encoding	When	What it does
SmallVec	under 128 ids	A plain vector of 64-bit ids. For short lists, compression is not worth the CPU.
DeltaVarint	128 to 4,096	Store the first id, then the gap to each next id as an LEB128 varint. Gaps under 128 cost one byte.
BlockPacked	over 4,096	Fixed blocks of 128 ids, bit-packed to the width the block needs — compact, with good random access.
Roaring	over 100,000, or dense	Roaring bitmaps, which shine when ids cluster and make set operations fast.

Encoding

When

What it does

SmallVec

under 128 ids

A plain vector of 64-bit ids. For short lists, compression is not worth the CPU.

DeltaVarint

128 to 4,096

Store the first id, then the gap to each next id as an LEB128 varint. Gaps under 128 cost one byte.

BlockPacked

over 4,096

Fixed blocks of 128 ids, bit-packed to the width the block needs — compact, with good random access.

Roaring

over 100,000, or dense

Roaring bitmaps, which shine when ids cluster and make set operations fast.

Density is simply the count divided by the id range. The repo’s encoding notes work an example: a user with 1,000 followers whose ids run 5,000 to 5,999 takes 8,000 bytes as raw 64-bit integers and about 1,003 bytes delta-encoded — an 87% saving — because every gap is one byte. This is where keeping ids as integers pays off: the 48-bit layout keeps ids of the same type numerically close, so their deltas stay small.

The design point I like best is that the choice is invisible above the segment. Every encoding implements the same PostingIterator trait — next, peek, and seek to the first id at or above a target — so the set operations never know or care how a list is stored.

Set maths instead of joins

"Mutual friends" is an intersection of two sorted lists. "Liked by any of my friends" is a union. With every list sorted and seekable, both are linear merges — no hash tables, no joins, no temporary results.

The interesting case is lopsided input: a user with 80 friends intersected with a celebrity who has two million followers. Merging two million ids to find a handful of matches is wasteful. AOEE’s adaptive intersection checks the sizes, and when one list is more than ten times larger it switches to galloping: for each id in the small list, seek forward in the large one — a binary search over what remains, rather than a step-by-step merge. The cost grows with the small list and only logarithmically with the large one.

Intersection and union also generalise to many lists at once (intersect_many, union_many), which is how multi-way queries such as "groups we are both in that also contain this post’s author" stay cheap.

Friend-of-friend, with a budget

Friend suggestions are the classic two-hop query: for each of my friends, look at their friends, count how many times each person appears, drop me and the people I already know, and rank by that count — the number of mutual connections.

Done naively, one well-connected friend can blow the query up. The FofQuery executor has explicit limits:

a fan-out cap on how many first-hop friends are expanded (1,000 by default), with optional deterministic sampling when someone has more;
an optional time budget, after which it returns what it has and marks the result as truncated;
a minimum score and a maximum number of results;
exclusions for yourself, your existing connections, and anything else you pass in, such as blocked users.

The result reports how many neighbours were processed and whether it was truncated, so the caller can tell a complete answer from a best effort. I think that honesty matters more than the algorithm: a recommendation that is cheap and known to be partial beats one that is exact and occasionally takes two seconds.

Sharding and the server

The Rust server is a workspace of crates: aoee-core (ids, edge types, encodings, iterators, set operations, friend-of-friend), aoee-storage (an EdgeStore trait with an in-memory implementation), aoee-shard (shards and routing), aoee-server (the gRPC service), plus a Rust client and a benchmark crate.

Each EdgeKey maps to a shard through a consistent-hash ring with virtual nodes, so adding shards moves only a fraction of the keys. Within a shard, posting lists live in a DashMap — a concurrent hash map with fine-grained locking — so readers of different keys never contend.

The JVM side, the UI, and persistence

Most of the systems I work with are Java, so AOEE has a first-class Java client:

AoeeClient client = new AoeeClient("localhost", 50051);

client.addEdge(userId, EdgeType.FOLLOWS, targetId);
client.addEdge(userId, EdgeType.LIKES, postId, 0, ReactionType.LOVE.getValue());

List<Long> mutual = client.intersect(
    new EdgeKey(alice, EdgeType.FRIEND_OF),
    new EdgeKey(bob, EdgeType.FRIEND_OF));

FofResponse suggestions = client.friendOfFriend(alice, EdgeType.FRIEND_OF);

On top of it, a Spring Boot proxy exposes the same operations as REST, loads datasets, and runs benchmarks; a React UI provides a dashboard, a force-directed graph explorer, an edge manager with a reaction picker, a query builder for set operations and suggestions, and a dataset loader. An optional persistence service (REST and GraphQL over H2 or PostgreSQL) receives writes through the proxy so the cache can be warmed from a database, and both the server and the proxy have Dockerfiles. To run the whole stack locally:

./start-services.sh            # Rust server, Spring proxy, React UI
./start-services.sh --persist  # ...plus the persistence service

What the numbers say

The benchmark harness generates a synthetic social graph — users with a skewed follow distribution, posts, groups, likes with reactions, a few very popular accounts and a viral post — then times each operation. The small preset builds 1,000 users, 2,000 posts, and 10 groups: 125,657 edges.

In the run recorded in the repo’s benchmarking guide, median latencies for every operation — neighbour lists, lists with reaction metadata, contains, counts, mutual-friend intersections, friend-of-friend, the popular-user lists, and the viral post — fell between 64 and 77 microseconds, with 99th percentiles between 93 and 172 microseconds. The slowest single call was a friend-of-friend query at 1.9 milliseconds.

Two caveats, because benchmarks deserve them. Those numbers are measured end to end from the JVM through gRPC on a development machine, so most of each microsecond budget is transport, not graph work. And the throughput figures in that same output came from a calculation I later found was off by a factor of a thousand — fixed in the commit history, and a good reminder to sanity-check any number that looks either too good or too bad.

What I learned

Search engine techniques transfer beautifully to graphs. Posting lists, gap encoding, skip tables, and galloping intersection solved most of the problems I expected to fight.

Adaptive representation beats a clever single format. The four encodings are each simple; the win is choosing between them per segment and hiding the choice behind one iterator.

Put limits in the query, not around it. Fan-out caps, sampling, and time budgets made friend-of-friend predictable, and reporting truncation made it trustworthy.

Write paths want buffers; read paths want immutability. A small LSM per posting list let both sides be simple.

What’s next

The repo’s roadmap covers the obvious next steps for a production cache: a RocksDB-backed store, leader–follower replication, set operations that span nodes, streaming updates to the UI, a cache for hot friend-of-friend results, time-range queries (one place TAO is still ahead — AOEE orders lists by id, not time), and SIMD-accelerated intersection.