Existential Consistency: Measuring and Understanding Consistency at Facebook

Buzzwords

• a trade-off between stronger forms of consistency and higher performance properties

• consistency monitoring system

  1. practical consistency monitoring system
  2. principle consistency monitoring system

• φ-consistency

• Facebook’s Replicated Storage

  1. Database
  2. Two-Level Cache
  3. Graph data model

• Local Consistency Models

  1. Linearizability
  2. Per-Object Sequential Consistency
  3. Read-After-Write Consistency

Summary

The paper introduces the storage for giant read-heavy sites(such as Facebook’s TAO) and their technique to detect anomalies and monitor consistency.

The Facebook’s replicated storage model is a graph data model database and two-level cache with write/read through strategy. The reads process down locally with read through and the writes are routed to the master database and updates other regions asynchronously. And the operation According to the paper, the system maintains per-object sequential consistency, read-after-write consistency within a cache and otherwise eventually consistent. The overall system is based on weak consistency while imposes stronger consistency if the operation is only in the cache. So if the cache hits are high enough, we can expect nice performance and consistency on this system.

The paper also introduces two consistency monitoring system. The first one is principle consistency monitor. It first picks a subset of all objects, then records the operations on the fly and finally offline preprocesses it and detects anomalies based on the logs. According to the pseudo code in the paper, the checker maintains a graph whose vertices are operations and edges are constrains, so we can detect the error by just checking for circles. The paper introduces two anomalies based on this strategy, namely stale read anomaly and total order anomaly.

The second checker is practical consistency monitor. It assigns real-time reads to replicas and checks for correctness. The track two types: φ(G)- consistency and φ(Ri)-consistency. The second one is more lightweight than the first one and Facebook uses it to detect real-time anomalies.

The result of the monitoring is surprising. Tao’s anomaly rate is much lower than expected. So, the design of Tao is high performance with remarkable high consistency.

Strength of the paper

• Two consistency monitoring systems are awesome design and give nice hints between performance and consistency.

• The architecture and tradeoff between performance and consistency of Tao give us a view of how to design the system for large-scale service.

Weakness of the paper

• The linearizability is not true local consistency model, some details may need more explanation.

• The practical checker may need some examples of what anomalies are found.

Paper learned

• A new idea on how to choose between high performance and strong consistency.