Paper Review: Mensuration Together With Agreement Consistency At Facebook
I direct hold reviewed many Facebook papers inward this spider web log earlier (see the links at the bottom for total list). Facebook papers are uncomplicated (in the practiced feel of the word) as well as interesting due to the huge scale of performance at Facebook. They are testaments of high scalability inward practice. This 1 hither is no different.
This newspaper investigates the consistency of the Facebook TAO system. The TAO organization is a replicated storage organization for Facebook's social graph of billion vertices. In theory, TAO provides exclusively eventual consistency. The interesting resultant inward this newspaper is this: In practice, Facebook's TAO organization is highly consistent, amongst exclusively five inconsistency violations out of a 1000000 read requests!
Read requests from spider web servers are served past times the corresponding leafage cache inward the local portion (the cache-hit ratios are really high), as well as if that fails it progresses downwardly the stack to locomote served past times the root cache, as well as if that too fails, past times the local database.
Write requests are complicated. The update needs to locomote reflected at the master copy database thus the write is routed all the way to the master copy database as well as back, next the path 1, 2, 3, 4, 5, 6, 7, 8 inward Figure 1. Each of those caches inward that road applies the write when it forwards the database's acknowledgment dorsum towards the client.
When the information is updated at the master copy database, the old information inward other caches (those non inward the road to the writing client) involve to locomote updated every bit well. TAO does non acquire for the update, but goes for the lazy strategy: invalidation of those old information inward the other caches. When a read comes from those other paths, the read volition drive a miss, as well as afterward populate the caches amongst the updated value learned from the regional database. This lazy strategy too has the payoff of existence uncomplicated as well as avoiding inadvertantly messing things (such every bit ordering of writes). TAO chooses to delete cached information instead of updating it inward cache because deletes are idempotent. The database is the authoritative copy, as well as caches, are just, well, caches.
So, how does the invalidation of caches inward other routes work. This proceeds inward an asynchronous fashion. The root caches inward the master copy (6') as well as originating regions (7') both asynchronously invalidate the other leafage caches inward their region. The master copy database asynchronously replicates the write to the slave regions (5'). When a slave database inward a portion that did non originate the write receives it, the database asynchronously invalidates its root cache (6'') that inward plough asynchronously invalidates all its leafage caches (7'').
This asynchronous invalidation of caches resultant inward a "vulnerability fourth dimension window" where inconsistent reads tin happen. In theory, TAO provides per-object sequential consistency as well as read-after-write consistency inside a cache, as well as exclusively eventual consistency across caches.
Well, that is inward theory, but what virtually inward practice? How tin 1 quantify the consistency of Facebook TAO?
Here are the consistency properties considered (going from stronger to weaker): linearizability, per-object sequential consistency, read-after write consistency, as well as eventual consistency. Linearizability agency that in that place exists a total social club over all operations inward the organization (where each performance appears to direct hold number instantaneously at about indicate betwixt when the customer invokes the performance as well as it receives the response), as well as that this social club is consistent amongst the real-time social club of operations. Per object-sequential consistency agency that in that place exists a legal, total social club over all requests to each object that is consistent amongst client’s orders. Read-After-Write agency that when a write asking has committed, all next read requests to that cache ever reverberate this write or afterward writes.
The offline checker converts dependencies betwixt reads as well as writes into a dependency graph as well as checks for cycles inward the dependency graph. Cycle agency a linearizability anomaly. The same technique is too used for checking weaker local-consistency models, per-object consistency, as well as read-after write consistency. They banking concern check for total ordering versus real-time ordering as well as tin procedure these weaker local-consistency models accordingly.
How come upwardly inconsistencies are thus rare considering TAO provides exclusively eventual consistency inward theory? What gives? This stems from the next characteristic of Facebook TAO: "writes are rare". (Check Table 2.) In the traces you lot involve both write as well as reads to an object to run into inconsistency. And exclusively 10%-25% of objects has both. Even then, a write is rare, as well as a read does non right away follow write. Even when a read right away follows write in that place is access locality, the read comes from the same portion where the cache is already updated. These all contribute to maintain inconsistency charge per unit of measurement really low, at 4 inward a million.
The newspaper too considers border update consistency, which render similar results to vertex consistency. An interesting finding hither is that 60% of all observed border anomalies are related to ‘like’ edges.
Phi consistency is an incomparable query amongst linearizability as well as other local-consistency queries, because it is an instant-query, as well as does non depend on history similar the former. So what practiced is it? It is however practiced for catching errors. If for about argue (bad configuration, operator error) caches are non maintained properly (e.g., cache invalidations screw up, etc) these phi queries volition grab that work inward real-time as well as warn.
How generalizable is this finding to other eventual-consistency systems? Of course of education nosotros involve to empathise this finding amongst its limitations. This finding applies for a social network organization updated amongst real-time human actions, thus the information does non alter really fast. And when it does, commonly in that place is no immediate read asking from other regions due to access locality, thus nosotros don't run into much inconsistency. Another limitation to the report is that the way they sample yard vertices out of a billion may non capture the mightiness constabulary model of the social graph. What virtually celebraties that direct hold many followers, their posts are jump to run into to a greater extent than traffic as well as prone to to a greater extent than inconsistency problems, no? I hollo back the newspaper should direct hold investigated the vertices amongst honour to their popularity tiers: high, medium, low.
Finally about other limitation is this. This locomote considers local consistency model. Local consistency agency whenever each private object provides C, the entire organization too provides C. This belongings is satisfied past times linearizability, per-object sequential consistency, read-after write consistency, as well as eventual consistency, but is non satisfied past times causally-consistent as well as transactional consistency models. The newspaper has this to tell on the topic: "Transactional isolation is inherently a non-local belongings as well as thus nosotros cannot mensurate it accurately using exclusively a sample of the total graph. This unfortunately agency nosotros cannot quantify the benefits of consistency models that include transactions, e.g., serializability as well as snapshot isolation, or the produce goodness of fifty-fifty read-only transactions on other consistency models. For instance, spell our results for causal consistency jump the produce goodness of the COPS system, they produce non jump the produce goodness of the COPS-GT organization that too includes read-only transactions."
Probabilistically bounded staleness
Facebook's software architecture
Facebook's Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services
Holistic Configuration Management at Facebook
Scaling Memcache at Facebook
Finding a Needle inward Haystack: Facebook's Photo Storage
One Trillion Edges, Graph Processing at Facebook-Scale
This newspaper investigates the consistency of the Facebook TAO system. The TAO organization is a replicated storage organization for Facebook's social graph of billion vertices. In theory, TAO provides exclusively eventual consistency. The interesting resultant inward this newspaper is this: In practice, Facebook's TAO organization is highly consistent, amongst exclusively five inconsistency violations out of a 1000000 read requests!
Facebook's TAO system
TAO is basically 2-level memcached architecture backed past times a database, every bit showtime discussed inward NSDI'13 paper. TAO architecture is given inward Figure 1. As a prerequisite to TAO consistency give-and-take inward the side past times side section, it volition locomote plenty to review how TAO serves read as well as write requests below.
Read requests from spider web servers are served past times the corresponding leafage cache inward the local portion (the cache-hit ratios are really high), as well as if that fails it progresses downwardly the stack to locomote served past times the root cache, as well as if that too fails, past times the local database.
Write requests are complicated. The update needs to locomote reflected at the master copy database thus the write is routed all the way to the master copy database as well as back, next the path 1, 2, 3, 4, 5, 6, 7, 8 inward Figure 1. Each of those caches inward that road applies the write when it forwards the database's acknowledgment dorsum towards the client.
When the information is updated at the master copy database, the old information inward other caches (those non inward the road to the writing client) involve to locomote updated every bit well. TAO does non acquire for the update, but goes for the lazy strategy: invalidation of those old information inward the other caches. When a read comes from those other paths, the read volition drive a miss, as well as afterward populate the caches amongst the updated value learned from the regional database. This lazy strategy too has the payoff of existence uncomplicated as well as avoiding inadvertantly messing things (such every bit ordering of writes). TAO chooses to delete cached information instead of updating it inward cache because deletes are idempotent. The database is the authoritative copy, as well as caches, are just, well, caches.
So, how does the invalidation of caches inward other routes work. This proceeds inward an asynchronous fashion. The root caches inward the master copy (6') as well as originating regions (7') both asynchronously invalidate the other leafage caches inward their region. The master copy database asynchronously replicates the write to the slave regions (5'). When a slave database inward a portion that did non originate the write receives it, the database asynchronously invalidates its root cache (6'') that inward plough asynchronously invalidates all its leafage caches (7'').
This asynchronous invalidation of caches resultant inward a "vulnerability fourth dimension window" where inconsistent reads tin happen. In theory, TAO provides per-object sequential consistency as well as read-after-write consistency inside a cache, as well as exclusively eventual consistency across caches.
Well, that is inward theory, but what virtually inward practice? How tin 1 quantify the consistency of Facebook TAO?
Consistency analysis setup
To respond this question, the authors prepare an offline checker-based consistency analysis. A random subset of the Facebook graph is chosen for monitoring. Random sampling is done for 1 vertex out of a million, thus this is for yard vertices. Every asking for these yard vertices are logged during their 12 twenty-four hours experiment (the delineate contains over 2.7 billion requests), as well as afterward analyzed past times the offline checker they developed for consistency violations.Here are the consistency properties considered (going from stronger to weaker): linearizability, per-object sequential consistency, read-after write consistency, as well as eventual consistency. Linearizability agency that in that place exists a total social club over all operations inward the organization (where each performance appears to direct hold number instantaneously at about indicate betwixt when the customer invokes the performance as well as it receives the response), as well as that this social club is consistent amongst the real-time social club of operations. Per object-sequential consistency agency that in that place exists a legal, total social club over all requests to each object that is consistent amongst client’s orders. Read-After-Write agency that when a write asking has committed, all next read requests to that cache ever reverberate this write or afterward writes.
The offline checker converts dependencies betwixt reads as well as writes into a dependency graph as well as checks for cycles inward the dependency graph. Cycle agency a linearizability anomaly. The same technique is too used for checking weaker local-consistency models, per-object consistency, as well as read-after write consistency. They banking concern check for total ordering versus real-time ordering as well as tin procedure these weaker local-consistency models accordingly.
Consistency evaluation results
Check Table three for the consistency evaluation results. It turns out the linearizability inconsistencies are really low: 0.0004% And this gets fifty-fifty lower if you lot consider read-after-write inside a unmarried region/cluster: 0.00006%.
How come upwardly inconsistencies are thus rare considering TAO provides exclusively eventual consistency inward theory? What gives? This stems from the next characteristic of Facebook TAO: "writes are rare". (Check Table 2.) In the traces you lot involve both write as well as reads to an object to run into inconsistency. And exclusively 10%-25% of objects has both. Even then, a write is rare, as well as a read does non right away follow write. Even when a read right away follows write in that place is access locality, the read comes from the same portion where the cache is already updated. These all contribute to maintain inconsistency charge per unit of measurement really low, at 4 inward a million.
The newspaper too considers border update consistency, which render similar results to vertex consistency. An interesting finding hither is that 60% of all observed border anomalies are related to ‘like’ edges.
The high update as well as asking charge per unit of measurement of “likes” explains their high contribution to the number of overall anomalies. The high update charge per unit of measurement induces many vulnerability windows during which anomalies could occur as well as the high asking charge per unit of measurement increases the likelihood a read volition occur during that window. The overstep 10 types (of edges) together work concern human relationship for 95% of the anomalies. These most-anomalous border types direct hold implications for the blueprint of systems amongst strong consistency.
Online practical consistency monitoring for Facebook TAO
Offline checker is expensive thus it cannot locomote used every bit online. For online, Facebook uses a heuristic to monitor the consistency of their TAO organization inward production: phi consistency checking. This is is a snapshot query to banking concern check if all caches render the same resultant for a given object. This is basically a mensurate of how closely synchronized the caches are inside regions (phi(R)) as well as globally (phi(G)).Phi consistency is an incomparable query amongst linearizability as well as other local-consistency queries, because it is an instant-query, as well as does non depend on history similar the former. So what practiced is it? It is however practiced for catching errors. If for about argue (bad configuration, operator error) caches are non maintained properly (e.g., cache invalidations screw up, etc) these phi queries volition grab that work inward real-time as well as warn.
So, what did nosotros learn?
Although TAO provides exclusively eventual-consistency inward theory, it turns out TAO is highly consistent inward practice, amongst exclusively five out of a 1000000 read-requests resulting inward a linearizability violation.How generalizable is this finding to other eventual-consistency systems? Of course of education nosotros involve to empathise this finding amongst its limitations. This finding applies for a social network organization updated amongst real-time human actions, thus the information does non alter really fast. And when it does, commonly in that place is no immediate read asking from other regions due to access locality, thus nosotros don't run into much inconsistency. Another limitation to the report is that the way they sample yard vertices out of a billion may non capture the mightiness constabulary model of the social graph. What virtually celebraties that direct hold many followers, their posts are jump to run into to a greater extent than traffic as well as prone to to a greater extent than inconsistency problems, no? I hollo back the newspaper should direct hold investigated the vertices amongst honour to their popularity tiers: high, medium, low.
Finally about other limitation is this. This locomote considers local consistency model. Local consistency agency whenever each private object provides C, the entire organization too provides C. This belongings is satisfied past times linearizability, per-object sequential consistency, read-after write consistency, as well as eventual consistency, but is non satisfied past times causally-consistent as well as transactional consistency models. The newspaper has this to tell on the topic: "Transactional isolation is inherently a non-local belongings as well as thus nosotros cannot mensurate it accurately using exclusively a sample of the total graph. This unfortunately agency nosotros cannot quantify the benefits of consistency models that include transactions, e.g., serializability as well as snapshot isolation, or the produce goodness of fifty-fifty read-only transactions on other consistency models. For instance, spell our results for causal consistency jump the produce goodness of the COPS system, they produce non jump the produce goodness of the COPS-GT organization that too includes read-only transactions."
Related links
Conference presentation video of this paperProbabilistically bounded staleness
Facebook's software architecture
Facebook's Mystery Machine: End-to-end Performance Analysis of Large-scale Internet Services
Holistic Configuration Management at Facebook
Scaling Memcache at Facebook
Finding a Needle inward Haystack: Facebook's Photo Storage
One Trillion Edges, Graph Processing at Facebook-Scale
0 Response to "Paper Review: Mensuration Together With Agreement Consistency At Facebook"
Post a Comment