Facebook timeline

01 · CONTEXT

From days of activity to decades

Facebook's earlier profile pages showed a few days or weeks of activity. With Timeline, the team had to think in years and even decades: it was necessary to scan, aggregate and rank posts, shares, photos and check-ins to highlight the most significant events across years of activity.

The schedule was very aggressive. One of the priorities was to eliminate technical risk by keeping the system as simple as possible and using technologies already proven inside the company. The team built on four core technologies: MySQL/InnoDB for storage, Multifeed (the technology that powers News Feed) for ranking, Thrift for communication and memcached for caching.

The most interesting design point is none of these pieces, but the way the data was organized for them. That is the subject of the next section.

02 · THE PROBLEM

Why the normalized model did not work

Before Timeline, the data was highly normalizados, which required many trips to the database; the design therefore depended on cache to keep everything fast. When a piece of data was not in the cache, it was unlikely to be clustered on disk, and this generated a lot of random IO, potentially slow.

Ranking years of activity under this model would have required keeping the entire dataset in cache, including low-value data that was not even displayed. The High Scalability analysis sums it up: given the volume and how much of it is cold, caching everything is not a good design.

1. The browser requests the profile from the web tier.

2. With normalized data, the design relied on the cache to keep everything fast.

3. When the data was not in the cache, it was unlikely to be clustered on disk, which generated potentially slow random IO.

4. Ranking years of activity would require keeping the entire dataset in cache, including low-value data.

03 · DENORMALIZE

Rows that already carry the ranking

The answer was massive denormalization, so that all the data needed for ranking was available in a few IO-efficient requests. Each database row came to contain information about the action and enough ranking metadata to be selected or discarded without additional lookups.

The data is sorted by (user, time) on disk, and InnoDB does a good job of reading it as a stream with a primary-key range query. High Scalability sums up the gain from denormalization: it reduces random IO by reducing trips to the database.

04 · READ

Local aggregator and two kinds of cache

The Timeline aggregator was built on top of the database. It started as a modified version of the Multifeed aggregator and now runs locally on each database server, which allows it to exhaust the disks' capacity without sending data that will not be displayed over the network. Its story generators range from grouping nearby check-ins to ranking status updates, are written in C++ and run their analyses in a few milliseconds.

1. The browser requests the Timeline from the web tier.

2. Results of large queries, such as ranking a whole year of activity, are small and stay in memcached for a long time without invalidation.

3. The aggregator runs locally on each database server.

4. The story generators read the denormalized rows, sorted by user and time, and group and rank them.

5. Data that will not be displayed is not sent over the network.

6. For Recent Activity, which changes frequently, the cache is a row cache: InnoDB buffer pool in RAM and Flashcache on flash.

05 · MIGRATION AND TEAM

Getting to the new model and shipping fast

There were dozens of legacy data formats that had evolved over the years, and a custom language expressed the conversion rules, with a compiler that turned it into executable PHP. The new schema adopted a data model compatible with Multifeed, more flexible and with more semantic context.

Non-recent activity data was in slow network storage. A read-only version of MySQL, on hundreds of servers, copied this data in weeks instead of months. The join tables were consolidated into a flash-only database tier, queried in parallel by a proxy.

1. The source data was in legacy formats and, for non-recent activity, in slow network storage.

2. A read-only version of MySQL on hundreds of servers extracted the data with maximum IO pressure.

3. Rules written in a custom language, compiled to PHP, converted the old formats.

4. The join tables were placed in flash-only databases, and a proxy queried the whole tier in parallel.

5. The result is denormalized rows in a Multifeed-compatible model.

Timeline started as a hackathon project in late 2010, with two full-time engineers, an intern and a designer who built a demo in a single night. The full team was split into design, front-end, infrastructure and data migration, and the workstreams moved in parallel: the team designed UI prototypes on top of the old backend and ran simulated load tests to validate capacity estimates. From the first infrastructure review meeting to the load test with 100% of the backend took only six months.