August 9, 2020
Introduction
It is the first time I came cross the original conference paper. I like to read the paper as well.
TAO: Facebook’s Distributed Data Store for the Social Graph
Here is the link of paper. Total pages are 12 pages. I like to spend 30 minutes to 60 minutes to read the paper.
Statement:
TAO, a read-optimized graph data store we have built to handle a demanding Facebook workload
read-optimized graph data store -
Web server -> TAO data store -> Database, memcache as a lookaside cache - what is lookaside cache
MySQL - persistent storage - graph-aware cache - how to define graph-aware?
CAP - AP - favors availability and per-machine efficiency over strong consistency.
TAO can sustain a billion reads per second on a changing data set of many petabytes.
efficient and available read-mostly access to a changing graph
objects and associations, a data model and API that we use to access the graph
TAO - a distributed system that implements this API
Facebook has more than a billion active users who record their relationships, share their interests, upload text, images, and video, and curate semantic information about their data [2]. The personalized experience of social applications comes from timely, efficient, and scalable access to this flood of data, the social graph. In this paper we introduce TAO, a read-optimized graph data store we have built to handle a demanding Facebook workload. Before TAO, Facebook’s web servers directly accessed MySQL to read or write the social graph, aggressively using memcache [21] as a lookaside cache. TAO implements a graph abstraction directly, allowing it to avoid some of the fundamental shortcomings of a lookaside cache architecture. TAO continues to use MySQL for persistent storage, but mediates access to the database and uses its own graph-aware cache. TAO is deployed at Facebook as a single geographically distributed instance. It has a minimal API and explicitly favors availability and per-machine efficiency over strong consistency; its novelty is its scale: TAO can sustain a billion reads per second on a changing data set of many petabytes. Overall, this paper makes three contributions. We motivate (§ 2) and characterize (§ 7) a challenging workload: efficient and available read-mostly access to a changing graph. We describe objects and associations, a data model and API that we use to access the graph (§ 3). Lastly, we detail TAO, a geographically distributed system that implements this API (§§ 4–6), and evaluate its performance on our workload (§ 8).
Let me try to read the 2.1 Serving the graph from Memcache
Facebook was originally built by storing the social graph in MySQL, querying it from PHP, and caching results in memcache [21]. This lookaside cache architecture is well suited to Facebook’s rapid iteration cycles, since all of the data mapping and cache-invalidation computations are in client code that is deployed frequently. Over time a PHP abstraction was developed that allowed developers to read and write the objects (nodes) and associations (edges) in the graph, and direct access to MySQL was deprecated for data types that fit the model. TAO is a service we constructed that directly implements the objects and associations model. We were motivated by encapsulation failures in the PHP API, by the opportunity to access the graph easily from non-PHP services, and by several fundamental problems with the lookaside cache architecture:
TAO is a service - objects and associations model
Inefficient edge lists: A key-value cache is not a good semantic fit for lists of edges; queries must always fetch the entire edge list and changes to a single edge require the entire list to be reloaded. Basic list support in a lookaside cache would only address the first problem; something much more complicated is required to coordinate concurrent incremental updates to cached lists.
coordinate concurrent incremental updates to cached lists? - how to coordinate?
Distributed control logic: In a lookaside cache architecture the control logic is run on clients that don’t communicate with each other. This increases the number of failure modes, and makes it difficult to avoid thundering herds. Nishtala et al. provide an in-depth discussion of the problems and present leases, a general solution [21]. For objects and associations the fixed API allows us to move the control logic into the cache itself, where the problem can be solved more efficiently.
What is thundering herds? -
Expensive read-after-write consistency: Facebook uses asynchronous master/slave replication for MySQL, which poses a problem for caches in data centers using a replica. Writes are forwarded to the master, but some time will elapse before they are reflected in the local replica. Nishtala et al.’s remote markers [21] track keys that are known to be stale, forwarding reads for those keys to the master region. By restricting the data model to objects and associations we can update the replica’s cache at write time, then use graph semantics to interpret cache maintenance messages from concurrent updates. This provides (in the absence of multiple failures) read-after-write consistency for all clients that share a cache, without requiring inter-regional communication.
asynchronous master/ slave replication for MySQL - caches in data centers using a replica -
Writes are forwarded to the master, but some time ...
update replica's cache at write time, then ...
read-after-write consistency -
2.2 TAO’s Goal TAO provides basic access to the nodes and edges of a constantly changing graph in data centers across multiple regions. It is optimized heavily for reads, and explicitly favors efficiency and availability over consistency. A system like TAO is likely to be useful for any application domain that needs to efficiently generate fine grained customized content from highly interconnected data. The application should not expect the data to be stale in the common case, but should be able to tolerate it. Many social networks fit in this category
3 TAO Data Model and API
Facebook focuses on people, actions, and relationships. We model these entities and connections as nodes and edges in a graph. This representation is very flexible; it directly models real-life objects, and can also be used to store an application’s internal implementation-specific data. TAO’s goal is not to support a complete set of graph queries, but to provide sufficient expressiveness to handle most application needs while allowing a scalable and efficient implementation.
Consider the social networking example in Figure 1a, in which Alice used her mobile phone to record her visit to a famous landmark with Bob. She ‘checked in’ to the Golden Gate Bridge and ‘tagged’ Bob to indicate that he is with her. Cathy added a comment that David has ‘liked.’ The social graph includes the users (Alice, Bob, Cathy, and David), their relationships, their actions (checking in, commenting, and liking), and a physical location (the Golden Gate Bridge). Facebook’s application servers would query this event’s underlying nodes and edges every time it is rendered. Fine-grained privacy controls mean that each user may see a different view of the checkin: the individual nodes and edges that encode the activity can be reused for all of these views, but the aggregated content and the results of privacy checks cannot.
Social graph - users - Alice, Bob, Cathy, and David
their relationships, their actions - checking in, commenting, and liking
a physical location (the Golden Gate Bridge)
3.1 Objects and Associations
TAO objects are typed nodes, and TAO associations are typed directed edges between objects. Objects are identified by a 64-bit integer (id) that is unique across all objects, regardless of object type (otype). Associations are identified by the source object (id1), association type (atype) and destination object (id2). At most one association of a given type can exist between any two objects. Both objects and associations may contain data as key→value pairs. A per-type schema lists the possible keys, the value type, and a default value. Each association has a 32-bit time field, which plays a central role in queries1.
Object: (id) → (otype, (key value)∗)
Assoc.: (id1, atype, id2) → (time, (key value)∗)
Figure 1b shows how TAO objects and associations might encode the example, with some data and times omitted for clarity. The example’s users are represented by objects, as are the checkin, the landmark, and Cathy’s comment. Associations capture the users’ friendships, authorship of the checkin and comment, and the binding between the checkin and its location and comments.
Actions may be encoded either as objects or associations. Both Cathy’s comment and David’s ‘like’ represent actions taken by a user, but only the comment results in a new object. Associations naturally model actions that can happen at most once or record state transitions, such as the acceptance of an event invitation, while repeatable actions are better represented as objects.
Although associations are directed, it is common for an association to be tightly coupled with an inverse edge. In this example all of the associations have an inverse except for the link of type COMMENT. No inverse edge is required here since the application does not traverse from the comment to the CHECKIN object. Once the checkin’s id is known, rendering Figure 1a only requires traversing outbound associations. Discovering the checkin object, however, requires the inbound edges or that an id is stored in another Facebook system.
The schemas for object and association types describe only the data contained in instances. They do not impose any restrictions on the edge types that can connect to a particular node type, or the node types that can terminate an edge type. The same atype is used to represent authorship of the checkin object and the comment object in Figure 1, for example. Self-edges are allowed.
3.2 Object API
TAO’s object API provides operations to allocate a new object and id, and to retrieve, update, or delete the object associated with an id. A notable omission is a compare-and-set functionality, whose usefulness is substantially reduced by TAO’s eventual consistency semantics. The update operation can be applied to a subset of the fields.
3.3 Association API
Many edges in the social graph are bidirectional, either symmetrically like the example’s FRIEND relationship or asymmetrically like AUTHORED and AUTHORED BY. Bidirectional edges are modeled as two separate associations. TAO provides support for keeping associations in sync with their inverses, by allowing association types to be configured with an inverse type. For such associations, creations, updates, and deletions are automatically coupled with an operation on the inverse association. Symmetric bidirectional types are their own inverses. The association write operations are:
• assoc add(id1, atype, id2, time, (k→v)*) – Adds or overwrites the association (id1, atype,id2), and its inverse (id1, inv(atype), id2) if defined.
• assoc delete(id1, atype, id2) – Deletes the association (id1, atype, id2) and the inverse if it exists.
• assoc change type(id1, atype, id2, newtype) – Changes the association (id1, atype, id2) to (id1, newtype, id2), if (id1, atype, id2) exists.
3.4 Association Query API
The starting point for any TAO association query is an originating object and an association type. This is the natural result of searching for a specific type of information about a particular object. Consider the example in Figure 1. In order to display the CHECKIN object, the application needs to enumerate all tagged users and the most recently added comments.
A characteristic of the social graph is that most of the data is old, but many of the queries are for the newest subset. This creation-time locality arises whenever an application focuses on recent items. If the Alice in Figure 1 is a famous celebrity then there might be thousands of comments attached to her checkin, but only the most recent ones will be rendered by default.
TAO’s association queries are organized around association lists. We define an association list to be the list of all associations with a particular id1 and atype, arranged in descending order by the time field:
Association List: (id1, atype) → [anew ...aold]
For example, the list (i, COMMENT) has edges to the example’s comments about i, most recent first.
TAO’s queries on associations lists:
• assoc get(id1, atype, id2set, high?, low?) – returns all of the associations (id1, atype, id2) and their time and data, where id2 ∈ id2set and high ≥ time ≥ low (if specified). The optional time bounds are to improve cacheability for large association lists (see § 5).
• assoc count(id1, atype) – returns the size of the association list for (id1, atype), which is the number of edges of type atype that originate at id1.
• assoc range(id1, atype, pos, limit) – returns elements of the (id1, atype) association list with index i ∈ [pos,pos+limit).
• assoc time range(id1, atype, high, low, limit) – returns elements from the (id1, atype) association list, starting with the first association where time ≤ high, returning only edges where time ≥ low.
TAO enforces a per-atype upper bound (typically 6,000) on the actual limit used for an association query. To enumerate the elements of a longer association list the client must issue multiple queries, using pos or high to specify a starting point.
For the example shown in Figure 1 we can map some possible queries to the TAO API as follows:
• “50 most recent comments on Alice’s checkin” ⇒ assoc range(632, COMMENT, 0, 50) • “How many checkins at the GG Bridge?” ⇒ assoc count(534, CHECKIN)
4 TAO Architecture
In this section we describe the units that make up TAO, and the multiple layers of aggregation that allow it to scale across data centers and geographic regions. TAO is separated into two caching layers and a storage layer.
4.1 Storage Layer
Objects and associations were stored in MySQL at Facebook even before TAO was built; it was the backing store for the original PHP implementation of the API. This made it the natural choice for TAO’s persistent storage.
The TAO API is mapped to a small set of simple SQL queries, but it could also be mapped efficiently to range scans in a non-SQL data storage system such as LevelDB [3] by explicitly maintaining the required indexes. When evaluating the suitability of a backing store for TAO, however, it is important to consider the data accesses that don’t use the API. These include backups, bulk import and deletion of data, bulk migrations from one data format to another, replica creation, asynchronous replication, consistency monitoring tools, and operational debugging. An alternate store would also have to provide atomic write transactions, efficient granular writes, and few latency outliers.
Database - backups, bulk import and deletion of data, bulk migration from one data format to another, replica creation, asynchronous replication, consistency monitoring tools, and operational debugging.
Given that TAO needs to handle a far larger volume of data than can be stored on a single MySQL server, we divide data into logical shards. Each shard is contained in a logical database. Database servers are responsible for one or more shards. In practice, the number of shards far exceeds the number of servers; we tune the shard to server mapping to balance load across different hosts. By default all object types are stored in one table, and all association types in another.
Each object id contains an embedded shard id that identifies its hosting shard. Objects are bound to a shard for their entire lifetime. An association is stored on the shard of its id1, so that every association query can be served from a single server. Two ids are unlikely to map to the same server unless they were explicitly colocated at creation time.
Actionable Items
I finished reading at 11:23 PM. So it took me more than two hours.
I do think that it is better for me to understand the paper; Best way is to listen the presentation again after paper reading.
No comments:
Post a Comment