Paper: Challenges to Adopting Stronger Consistency at Scale

AJOUX, Phillipe, et al. Challenges to Adopting Stronger Consistency at Scale. In: 15th Workshop on Hot Topics in Operating Systems (HotOS XV). USENIX Association. (pdf, slides)

최근 geo-replicated data store에서 높은 consistency를 제공하기 위한 연구들이 많이 있다고 한다. – 이 논문에서 나열하고 있는 그런 논문들의 목록도 흥미로운데 이는 마지막에 한번 정리해보자. – Facebook에서도 사용자들에게 – 특히, 읽기에 대한 – end-to-end consistency를 제공하기 위해서 이러한 연구 결과들을 도입하고 싶으나, 여러가지 이유로 이것이 쉽지가 않은데, 그 이유가 무엇인지 일단 알아보자…라는 것이 이 논문의 취지.

There have been many recent advances in distributed systems that provide stronger semantics for geo-replicated data stores like those underlying Facebook. These research systems provide a range of consistency models and transactional abilities while demonstrating good performance and scalability on experimental workloads. At Facebook we are excited by these lines of research, but fundamental and operational challenges currently make it infeasible to incorporate these advances into deployed systems. This paper describes some of these challenges with the hope that future advances will address them.

Facebook은 확장성과 효율을 위해서 샤딩, 복제, 캐싱 등을 아주 많이 활용하고 있는 것으로 보인다. Sodcial graph 시스템을 예로 들고 있는데, 하나의 node나 edge가 MySQL(!)에 쓰여지면, 이것이 비동기적으로 다른 데이터 센터로 복제되고, 여러 계층의 캐시들을 업데이트하고, pub-sub 시스템에 의해 검색이나 뉴스피드를 위한 다른 시스템으로 전달된다. 당연한 이야기지만, Facebook 내의 여러 기능에 해당하는 시스템들은 효율을 위해 각자 특별한 샤딩 방식이나 캐시, 인덱스들을 유지해야한다. Twitter (http://blog.lastmind.net/archives/664)나 LinkedIn (http://blog.lastmind.net/archives/657)의 시스템과 같이 Primary Data Store (DB)로부터 비동기적인 복제를 통해 Secondary Index를 생성하거나 다른 서비스로 이벤트를 전달하는 방식은 현재의 대규모 인터넷 서비스에서는 매우 공통적인 부분으로 보인다.

Facebook relies on sharding, data replication, and caching to efficiently operate at scale. When a node or edge is added to the social graph, it is first written to a single MySQL instance. From there it is asynchronously replicated to all of our data centers, updated or invalidated in multiple layers of cache, and delivered through a scalable publisher-subscriber system to other services such as Search and News Feed. No single data placement strategy can efficiently serve all workloads in a heavily sharded system, so many of these services choose a specialized sharding function and maintain their own data store, caches, and indexes.

facebook_data_layout

Fundamental Challenges

Integrating Across Stateful Services

Facebook의 Social graph는 여러 서비스들을 위한 시스템에 각 서비스를 위한 형태로 복제되고 있다고 한다. 문제는, 대부분의 연구 결과들에서 나타나는 설계들은 단일한 서비스를 상정하고 있다는 것이다. Facebook는 그러한 여러한 서비스가 따로 사용자에게 제공되기 보다는 하나의 서비스처럼 제공되므로 여러가지 문제들이 발생하게 된다.

Facebook’s architecture of cooperating heterogeneous services is different from the monolithic service that
most research designs assume. This difference alone is not fundamental—Facebook can be externally viewed as a single service even though internally it is comprised of many services.

Storing Data Consistently Across Services

Facebook의 각 서비스들은 Social graph의 일부에 대한 캐시, 인덱스, 복제본 등을 가지고 있다. Wormhole이라는 Facebook의 pub-sub 시스템은 업데이트를 비동기적으로 여러서비스들에 전달해주고 있다.

In a sharded and scaled environment like Facebook’s, services may maintain their own optimized cache, index, or copy of a portion of the social graph. Wormhole [40] is our scalable pub-sub system that asynchronously delivers update notifications to all of the services that manage state.

이 때, 만약 높은 consistency를 제공하기 위해서는 동기적으로 업데이트 통지를 전달할텐데, availability와 latency를 떨어뜨리는 요인이 된다. 인과성을 위한 시스템을 사용하더라도 여러 서비스들 사이의 의존관계를 표현하는 것은 굉장한 복잡도를 가져오게 된다.

To provide strong consistency across our services, we would need to propagate update notifications synchronously impacting availability and latency. A causal system could avoid atomic updates, but would still need to be integrated into every service and threaded through every communication channel greatly increasing the complexity of the dependency graph.

Decentralized Access to Services

클라이언트는 한 화면에서 표시되는 여러 컨텐츠를 별도의 리퀘스트를 통해 가져와서 클라이언트에서 통합한다. 이 때문에 클라이언트는 일관되지 않은 결과들을 가지고 session-based guarantee를 보장함으로써 사용자에게 일관된 상태를 보여주어야 한다.

The Facebook web site and its mobile applications use parallelism and pipelining to reduce latency. The notification bar and the central content are fetched by separate requests, for example, and then merged at the client. Mobile applications also aggressively cache results using local storage, and then merge query results with previously seen values. […] but it leaves the user’s device as the only safe location to define session-based guarantees or demarcate isolation boundaries.

단일한 사용자는 보통 동일한 지역의 동일한 클러스터로 라우팅 되므로 이러한 성질은 사용자가 inconsistency를 경험할 확률을 낮추어준다. 하지만, 그러한 성질이 보장되는 것은 아니므로 역시 문제는 있다.

Requests for a single user are usually routed to the same cluster in the same region. This routing stability assists in reducing the number of user-visible inconsistencies, because most of the variance in asynchronous update propagation is inter-region.

Composing Results

조금 설명이 애매하기는 한데, 여러 서비스로부터의 결과를 조합해야할 경우, 그 사이의 의존관계를 다루어야 하는데, 각 서비스는 각자의 서비스를 위한 일부의 결과를 가지고 있기 때문에, 이를 일반적으로 처리하기가 쉽지 않다는 의미인 듯 하다.

Each service can be thought of as implementing its own limited query language, so it is not clear that the dependencies can be captured in a way that is both sufficiently generic and sufficiently precise.

Query Amplification

사용자 입장에서는 하나의 쿼리지만, 내부적으로는 여러 서비스들에 대한 수천개의 쿼리로 실행될 수 있다는 이야기.

For example, a user’s home page queries News Feed to get a list of stories, which depends on a separate service to ensure story order of previously seen content. These stories are then fetched from TAO to get the content, list of comments, likes, etc. In practice, this behavior produces fork/join query patterns that have fan-out degrees in the hundreds and critical paths dozens deep.

Slowdown Cascades

동일한 데이터가 각각의 서비스에서는 서로 다른 샤딩 방식과 인덱싱을 통해 저장되므로, 서로 다른 서비스들의 샤드 사이에 all-to-all ordering 의존 관계가 발생하고, 높은 consistency를 요구하는 시스템에서는 하나의 서비스에서 하나의 샤드만 실패 또는 지연되더라도 이에 의존하는 모든 다른 서비스의 모든 샤드에 영향을 줄 수 있다는 이야기.

Different services use different sharding and indexing schemes for the same data. For instance, TAO shards data based on a 64-bit integer id, News Feed shards based on a user id, and the secondary index system shards based on values. The use of different sharding schemes creates all-to-all ordering dependencies between shards in different services. This connectedness accelerates slowdown propagation in strongly consistent systems. A failure in one shard of one service would propagate to all shards of a downstream service.

Latency Outliers

여러 쿼리들을 조합해야하는 경우, 하나의 쿼리만 느리더라도 최종적인 응답에 영향을 미칠 수 있음. 이것이 strong consistency와 직접적인 연관성이 있는지는 명확하게 이해하기 어려우나, strongly consistent system의 응답속도나 outlier들이 그렇지 않은 시스템들에 비해 더 높기 때문에 언급되는 것 같음.

Parallel subqueries amplify the impact of latency outliers. A user request does not return until it has joined the results of all of its queries, and thus must wait for the slowest of its internal requests.

Linchpin Objects

데이터의 개수도 많고 매우 자주 읽히는데다 쓰기도 많은 무언가를 Linchpin Object라고 부르고 있다. 흔히 Facebook의 연예인 페이지나 유명 대기업의 페이지를 상상하면 될 것 같다. 역시 좋은 성능을 제공하는 것이 strongly consistent system에서는 중요하다고 얘기하고 있다.

The most frequently read objects are often also frequently written to and highly connected. Examples of these linchpin objects include popular users like celebrities, popular pages like major brands, and popular locations like tourist attractions. […] A system that provides stronger consistency must provide good performance for these linchpin objects.

Net Benefit to Users

stronger consistency는 프로그래머가 프로그램의 정확성에 대해 생각하기 편리하고, 사용자에게 일관성을 제공한다는 측면에서 이점을 가지고 있지만, 이를 정량적으로 측정하기는 어려울 뿐만 아니라, 그러한 이점들이 단점들 – 커뮤니케이션 오버헤드, 무거운 상태관리, 응답속도의 증가 – 을 넘어서지 않을지도 모름.

Systems with strong consistency are easier for programmers to reason about and build on top of [6, 12] and they provide a better experience for users because they avoid some anomalous application behavior. However, these benefits are hard to quantify precisely, and they do not appear in isolation. When all aspects of user experience are considered it might even be the case that the benefit does not outweigh the detriment. […] Stronger properties are provided through added communication and heavier-weight state management mechanisms, increasing latency. Although optimizations may minimize these overheads during failure-free execution, failures are frequent at scale. Higher latency may lead to a worse user experience, potentially resulting in a net detriment.

Operational Challenges

Fully Characterizing Worst-Case Throughput

여러 서비스가 얽혀있는 복잡한 시스템에서 실패나 복구 방법에 대해 미리 예측하거나 관찰하기 쉽지 않을 뿐더러 이를 정형화하기도 쉽지 않다는 얘기.

While there is no theoretical impediment to preserving worst-case throughput despite strengthening Facebook’s consistency guarantees, our experience is that failure and recovery behavior of a complex system is very difficult to characterize fully. Emergent behavior in cross-service interactions is difficult to find ahead of time, and may even be difficult to identify when it is occurring

Polyglot Environment

(아마도 백엔드) 서비스 내에서 C++이 가장 보편적으로 사용되는 언어인 것은 매우 신기함.

While C++ is the predominant language for standalone services at Facebook, Python, Java, Haskell, D, Ruby and Go are also supported by Thrift, our inter-service serialization format. The application code coordinating service invocations is generally written in Hack and PHP, and final composition of query
results may be performed by JavaScript in the browser, Objective C/C++ on IOS, or Java on Android.

여러 언어를 사용하고 있기 때문에 인터페이스나 쓰레딩 모델 등에 대해 가정하는 것이 어렵다는 이야기.

Ports or foreign function interfaces must be provided to give all of these codebases access to an end-to-end
consistency platform. Perhaps the trickiest part of this multi-language support is the wide variety of threading models that are idiomatic for different languages and runtimes, because it is likely the underlying consistency system will need to initiate or delay communication.

Varying Deployment Schedules

낮은 레벨의 서비스들은 매우 보수적인 deployment 프로세스를 가지고 있으므로, 이에 관련한 시스템을 빠르게 개발하는 것은 쉽지 않을거라는 이야기.

Facebook has an extremely aggressive deployment process for the stateless application logic, but we are necessarily more conservative with stateful and mature low level services. An inter-service coordination mechanism that is used by or interposes on these low-level services will have a deployment velocity that is constrained by the release engineering requirements of the most conservative component.

Reduced Incremental Benefit in a Mature System

consistency에 관해 이미 적용된 workaround들이 있으므로, 이를 일반적으로 개선하는 시스템의 이득이 떨어진다는 이야기.

While these workarounds would not exist in a newly built system, their presence in Facebook reduces the incremental benefits of deploying a generic system for stronger consistency guarantees.

Related Work

Prior Facebook Publications

  • memcache cache
    • B. Atikoglu, et al. Workload analysis of a large-scale keyvalue store. In SIGMETRICS, 2012.
    • R. Nishtala, et al. Scaling memcache at facebook. In NSDI, 2013.
  • TAO graph store
    • N. Bronson, et al. Tao: Facebook’s distributed data store for the social graph. In USENIX ATC, 2013.
  • Wormhole pub-sub system
    • Y. Sharma, et al. Wormhole: Reliable pub-sub to support geo-replicated internet services. In NSDI, May 2015
  • a characterization of load imbalance in the caches
    • Q. Huang, et al. Characterizing load imbalance in real-world networked caches. In HotNets, 2014.
  • an analysis of the messages use case
    • T. Harter, et al. Analysis of hdfs under hbase: A facebook messages case study. In FAST, 2014.
  • understanding and improving photo/BLOB storage and delivery
    • D. Beaver, et al. Finding a needle in haystack: Facebook’s photo storage. In OSDI, 2010.
      Q. Huang, et al. An Analysis of Facebook Photo Caching. In SOSP. ACM, 2013.
    • S. Muralidhar, et al. f4: Facebook’s warm blob storage system. In OSDI, 2014.
    • L. Tang, et al. RIPQ: Advanced Photo Caching on Flash For Facebook. In FAST, Feb. 2015.

Systems with Stronger Semantics

  • replicated state machines
    • L. Lamport. Time, clocks, and the ordering of events in a distributed system. Comm. ACM, 21(7), 1978.
    • F. B. Schneider. Implementing fault-tolerant services using the state machine approach: a tutorial. ACM Computer Surveys, 22(4), Dec. 1990.
  • causal and atomic broadcasts
    • K. P. Birman and R. V. Renesse. Reliable Distributed Computing with the ISIS Toolkit. IEEE Comp. Soc. Press, 1994.
  • systems designed for high availability and stronger consistency
    • K. Petersen, et al. Flexible update propagation for weakly consistent replication. In SOSP, Oct. 1997.
  • scalable causal consistency for datacenter-scale and/or geo-replicated services
    • S. Almeida, et al. Chainreaction: a causal+ consistent datastore based on chain replication. In EuroSys, 2013.
    • P. Bailis, et al. Bolton causal consistency. In SIGMOD, 2013.
    • J. Du, et al. Orbe: Scalable causal consistency using dependency matrices and physical clocks. In SOCC, 2013.
    • J. Du, et al. Gentlerain: Cheap and scalable causal consistency with physical clocks. In SOCC, 2014.
    • W. Lloyd, et al. Don’t settle for eventual: Scalable causal consistency for wide-area storage with COPS. In SOSP, Oct. 2011.
    • W. Lloyd,  et al. Stronger semantics for low-latency geo-replicated storage. In NSDI, Apr. 2013.
  • strong consistency for datacenter-scale and/or geo-replicated services
    • J. C. Corbett, et al. Spanner: Google’s globally distributed database. In OSDI, Oct. 2012.
    • R. Escriva, et al. HyperKV: A distributed, searchable key-value store for cloud computing. In SIGCOMM, 2012.
    • L. Glendenning, et al. Scalable consistency in Scatter. In SOSP, Oct. 2011.
    • C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguic¸a, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In OSDI, Oct. 2012.
    • J. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazi`eres, S. Mitra, A. Narayanan,
      M. Rosenblum, S. M. Rumble, E. Stratmann, and R. Stutsman. The case for ramcloud. ACM SIGOPS Operating Systems Review, 43(4), 2010.
    • D. B. Terry, V. Prabhakaran, R. Kotla, M. Balakrishnan, M. K. Aguilera, and H. Abu-Libdeh. Consistency-based service level agreements for cloud storage. In SOSP, 2013.
  • transactions for datacenter-scale and/or geo-replicated services
    • P. Bailis, et al. Scalable atomic visibility with ramp transactions. In SIGMOD, 2014.
    • J. Baker, et al. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, Jan. 2011.
    • J. C. Corbett, et al. Spanner: Google’s globally distributed database. In OSDI, Oct. 2012.
    • T. Kraska, et al. Mdcc: Multi-data center consistency. In EuroSys, 2013.
    • W. Lloyd, et al. Stronger semantics for low-latency geo-replicated storage. In NSDI, Apr. 2013.
    • S. Mu, et al. Extracting more concurrency from distributed transactions. In OSDI, 2014.
    • Y. Sovran, et al. Transactional storage for geo-replicated systems. In SOSP, Oct. 2011.
    • A. Thomson, et al. Calvin: fast distributed transactions for partitioned database systems. In SIGMOD, May 2012.
    • C. Xie, et al. Salt: combining acid and base in a distributed database. In OSDI, 2014.
    • Y. Zhang, et al. Transaction chains: achieving serializability with low latency in geo-distributed storage systems. In SOSP, pages 276–291. ACM, 2013.

Discussions of Challenges to Stronger Consistency

  • criticism of enforcing an order in a communication substrate instead of end to end
    • D. R. Cheriton, et al. Understanding the limitations of causally and totally ordered communication. In
      SOSP, Dec. 1993.
  • slowdown cascades to motivate enforcing only an explicit subset of causal consistency
    • P. Bailis, et al. The potential dangers of causal consistency and an explicit solution. In SOCC, 2012.
  • detail the importance and challenges for tail latency in high-scale services at Google
    • J. Dean, et al. The tail at scale. Comm. ACM, 56(2), 2013.

My Opinion

Strongly consistent system의 연구자들에게 방향을 제시하기 위해 Facebook의 시스템이라는 도메인 내에서 발생하는 숙제들을 정의하고 있는 논문이라고 볼 수 있는데, 마치 Facebook에서 strongly consistent system을 일반적으로 도입해서는 안되는 이유들을 정리해놓은 듯한 느낌이 들었다. 오히려 나의 관심은 Facebook에서 데이터의 복제에 관한 시스템과 복제본 사이의 consistency 문제를 어떻게 다루고 있는가 였는데, 우리가 고심하고 있는 문제들이나 해결 방향이 상당히 닮아 있다는 인상을 받았다. 여러 서비스에 걸친 업데이트 통지를 위해 인프라로서 pub-sub을 적극적으로 활용하고 있는 점이나, 서비스별로 소셜 그래프의 별도 인덱스나 캐시 등을 잘 구축해서 활용하고 있는 점은 잘하고 있다고 생각했다. Facebook의 graph storage인 TAO, pub-sub 시스템인 Wormhole 등에 대해 관심이 생겼다.

What consistency does your key-value store actually provide?

What consistency does your key-value store actually provide? by Anderson, Eric, et al

Many key-value stores have recently been proposed as platforms for always-on, globally-distributed, Internet scale applications. To meet their needs, these stores often sacrifice consistency for availability. Yet, few tools exist that can verify the consistency actually provided by a key-value store, and quantify the violations if any. How can a user check if a storage system meets its promise of consistency? If a system only promises eventual consistency, how bad is it really? In this paper, we present efficient algorithms that help answer these questions. By analyzing the trace of interactions between the client machines and a key-value store, the algorithms can report whether the trace is safe, regular, or atomic, and if not, how many violations there are in the trace. We run these algorithms on traces of our eventually consistent key value store called Pahoehoe and find few or no violations, thus showing that it often behaves like a strongly consistent system during our tests.

예전에 HP-KVS에 관련해서 자료를 찾다가 발견한 페이퍼인데, 얼마전 한국에 다녀올 때 읽어보게 되었습니다.

1. Perceived consistency rather than worst-case consistency

이 페이퍼는 일반적으로 key-value store들이 보장하는 worst-case consistency가 아니라, 실제로 client에 의해서 관찰되는 consistency의 수준을 측정하는 알고리즘을 제안하고 있다. 우리가 스토리지 기술을 선택할 때는 물론 worst-case consistency가 고려되기는 하지만, 실제로는 ‘실용적인’ 접근을 취하는데, 그것이 의미하는 바는 애플리케이션의 액세스 패턴에 따라 사용자가 느끼는 consistency의 수준이 달라질 수 있음을 고려해서 스토리지 기술을 선택한다는 것이다. 이 페이퍼가 해결하려는 문제 자체가 엄밀하거나 학술적이기 보다는 실용적인 의미를 해석하려는 것이기 때문에 한계는 있겠지만, 어떤 worst-case consistency를 가진 스토리지 – 예를 들어 eventually consistent 스토리지들이 어떤 애플리케이션에 필요한 consistency를 달성하기에 충분한지 충분하지 않은지에 대해서 매우 피상적으로 논의하는 것보다는 체계적인 방법을 제공한다는 점 그리고, 그러한 방법이 존재할 수 있다는 점에서 의미가 있는 것 같다.

2. A eager, eventually consistent protocol often achieves strong consistency

이 알고리즘을 통한 검증을 역시 HP에서 만든 eventually consistent key-value store인 Pahoehoe를 가지고 실험한 결과를 보여주고 있는데, 가장 concurrent한 조건 (128 concurrent processes on 1 key)에서도 consistency violation의 수가 10% 이하로 발생하고 있고, 일반적인 조건 하에서는 1% 수준이다. 그 이유를 우리가 일반적인 웹 애플리케이션에서 예상하고 있는 것과 마찬가지로 concurrent write 하에서의 read가 많지 않기 때문으로 설명하고 있다.

3. Lamport’s consistency assumption on registers: safe, regular, and atomic

이 페이퍼가 검증하려고 하는 consistency 수준의 분류로 Leslie Lamport가 On Interprocess Communication. Part I: Basic Formalism에서 제안한 register의 3가지 consistency semantic을 사용하고 있다. 이는 다음과 같다.

3가지의 consistency 모두 write와 concurrent하지 않은 read는 가장 최근의 write에 의한 값을 return 해야한다. 차이는 write와 concurrent한 read에서 발생한다.

  • safe: write와 concurrent한 read는 임의의 값을 return
  • regular: write와 concurrent한 read는 가장 최근의 write에 의한 값과 concurrent한 write들에 의한 값들 중 하나를 return
  • atomic: write와 concurrent한 read도 가장 최근의 write에 의한 값을 return

worst-case consistency를 가지고 예를 든다면, 최근 유행하는 eventual consistent storage들은 concurrent하지 않은 read에 대해서 가장 최근의 write에 의한 값을 return하는 것을 보장하지 않으므로 가장 느슨한 수준인 safe 조차 만족하지 못한다. 반면에 일반적인 ACID 데이터베이스는 atomic 수준에 해당한다.

4. Methods

이 페이퍼가 제안하고 있는 알고리즘은 대략 다음과 같다.

  1. 어떤 key-value store에 대한 클라이언트의 모든 액세스에 대해 시작 시각과 종료 시각, 그리고 저장하거나 읽어온 값의 로그를 기록한다.
  2. 이 로그를 바탕으로 오퍼레이션이 vertex이고, should-happen-before 관계가 edge인 directed graph를 구성한다. 이 때 이 관계는 검증하려는 consistency 종류에 따라서 달라지는데, 대체로 시간의 관계, 값의 인과 관계를 의미한다고 보면 된다.
  3. 구성된 graph에서 cycle이 발견되지 않으면 consistent, 발견되면 inconsistent하다고 판단한다.

straight-forward하기 때문에 쉽게 이해할 수 있다. 시각의 정확성이나 값의 인과관계를 찾는 부분 등에서 보완이 필요한 것 같긴 하지만 중요한 문제는 아닌 것 같다.

5. Measuring Consistability

여러 eventually consistent 스토리지들은 failure가 발생했을 때 consistency를 희생하게 되어있는데 이 때의 consistency 희생이 어느 정도인지 측정하는 작업이 필요하다.

6. Further Reads

  • J. Misra, Axioms for memory access in asynchronous hardware systems, 1986.
  • L. Lamport, On interprocessing communication, Part I: Basic formalism and Part II: Algorithms, 1986
  • W. Vogels, Eventually consistent, 2009
  • A. Aiyer, et al., On the availability of non -strict quorum systems, 2005
  • E. Anderson, et al., Efficient eventual consistency in Pahoehoe, an erasure-coded key-blob archive, 2010

Consistency Tradeoffs in Modern Distributed Database System Design

지난 번에 소개했던 IEEE Computer 2012년 2월호의 CAP Theorem 특집 중 세번째 글입니다. CAP Theorem 특집을 읽게된 계기도 바로 이 글의 저자인 Abadi의 블로그 글이었습니다.

Consistency Tradeoffs in Modern Distributed Database System Design by Daniel J. Abadi

Critique

현대의 DDBS에서 CAP의 consistency/availability tradeoff 보다 consistency/latency tradeoff가 중요한 설계상의 결정임을 주장하고 PACELC라는 모델을 제안하고 있습니다.

CAP 만으로 설명하기 어려웠던 설계 결정들에 대해 의문이 있었다면 PACELC가 완벽하지는 않지만 CAP에 비해서 더 좋은 모델임에 동의할 수 있을 것 같습니다. 주변 분들에게도 PACELC에 대해서 설명해주면 당연하게 받아들이는 눈치였습니다. 한편, 이 글은 매우 간결하면서도 문제로부터 결론을 도출하기 까지 논리의 흐름이 부드럽게 이어지기 때문에 이해가 잘 되고 그리 무겁지 않게 읽을 수 있습니다.

PACELC의 개념이 직관적으로는 이해하기 쉬운 반면, 현재 존재하는 시스템을 분류할 때 저자도 언급하고 있는 애매한 점들이 등장하는 것을 보면 엄밀한 도구라고 보기에는 약간 무리입니다. tradeoff 의 모든 측면을 모델로 표현하는 것은 매우 어렵기 때문에 베이스라인이라는 표현과 이로부터 상대적인 tradeoff의 유무를 기준으로 사용한 것 같습니다.

역시 완벽하지는 않겠지만 현대의 DDBS에서 활용하고 있는 설계 결정들을 모두 정리해서 스펙트럼 또는 이에 상응하는 모델로 정리할 수 있다면 앞으로의 DDBS 프레임워크의 발전에서 중요한 기초가 될 수 있지 않을까 생각합니다.

아래는 이 글의 요약입니다.

CAP is for Failure

CAP에서 consistency와 availability 사이의 tradeoff를 발생시키는 요소는 단지 partition tolerance 만이 아니라, partition tolerance와 network partition의 존재, 두 가지 요소의 조합이기 때문에, network partition이 존재하지 않을 때, CAP 자체는 consistency와 availability를 동시에 만족시키는 시스템을 허용하고 있다.

Consistency/Latency Tradeoff

network partition이 존재하지 않는다고 하더라도 consistency, availability, latency 사이의 tradeoff는 존재한다. 이러한 tradeoff가 존재하는 이유는 high availability 요구사항으로 인해 시스템은 데이터를 복제해야하기 때문이다.

Data Replication

시스템이 데이터를 복제하는 순간부터 consistency와 latency 사이의 tradeoff가 발생한다. 데이터 복제를 구현하는 데에는 아래와 같이 3개의 방법이 존재하지만, 각각은 모두 latency의 요소가 존재한다.

(1) 데이터의 업데이트를 동시에 모든 복제본으로 보내기

선처리 레이어(preprocessing protocol)를 통과하지 않거나 합의 프로토콜 (agreement protocol)이 없다면 오퍼레이션의 적용 순서의 차이로 인해 복제본들 사이의 차이가 발생한다. 선처리 레이어나 합의 프로토콜을 사용한다면 모든 복제본들이 합의된 순서대로 업데이트를 적용하는 것을 보장할 수 있지만, 선처리 레이어를 위한 추가적인 시스템 컴포넌트, 모든 복제본에 대한 업데이트, 합의 프로토콜 자체 등 latency가 발생하는 여러가지 원인들이 된다.

(2) 데이터의 업데이트를 합의된 마스터 노드에 먼저 보내기

마스터 노드는 모든 업데이트 요청을 처리하고 마스터 노드가 처리한 순서는 마스터 노드가 모든 리플리카에 복제하면서 다른 복제본들에도 그대로 적용된다.

마스터로부터 다른 복제본으로의 복제 방법은 아래와 같은 3가지가 존재한다.

a. 동기적인 복제: 복제본들로의 업데이트가 일어날 때까지 마스터 노드는 대기한다. 복제본들이 consistent하지만, 모든 복제본들의 업데이트로 인해 latency가 증가한다.

b. 비동기적인 복제: 복제본들이 업데이트 되었다는 보장이 없으므로, consistency/latency tradeoff는 시스템이 읽기를 어떻게 다루느냐에 달려있다.

i. 시스템이 모든 읽기를 마스터 노드에서 수행한다면 consistency의 감소가 없지만, 마스터 노드가 다른 복제본에 비해서 가까운 곳에 있지 않을 때, 또는 마스터 노드가 과부하 상태이거나 동작 불능 상태일 때는 latency가 발생한다.

ii. 어떤 노드에서도 읽기를 수행하도록 한다면 읽기의 latency는 좋아지지만, 동일한 데이터의 inconsistent한 읽기가 발생한다. update sequence number의 추적을 통해 sequential/timeline consistency 또는 read-your-writes consistency를 구현해 consistency의 감소를 줄일 수 있다.

c. 데이터의 업데이트를 복제본의 일부에 대해서는 동기적으로 복제하고, 나머지는 비동기적으로 복제한다. 이 경우에도 consistency/latency tradeoff는 시스템이 읽기를 다루는 방식에 달려있다.

i. 동기적으로 복제가 된 적어도 1개 이상의 노드로부터 읽기를 수행한다. (R + W > N)

ii. 동기적으로 업데이트 되지 않은 노드들에서 읽기를 수행하도록 허용한다. (R + W <= N)

(3) 데이터의 업데이트를 임의의 노드에 먼저 보내기

하나의 데이터 항목에 대한 두개의 업데이트가 서로 다른 노드로 보내질 수 있다. 동기적인 복제인가, 비동기적인 복제인가에 따라서 (1), (2)에서와 같은 latency 문제나 consistency 문제가 발생한다.

Tradeoff Examples

PNUTS의 경우, 마스터 노드로부터 비동기적으로 데이터를 복제하고, 아무 노드에서나 읽기를 수행하므로 (즉, 2-b-ii의 경우), latency를 위해 consistency를 tradeoff 하고 있다. 반면, CAP의 관점에서는 network partition이 발생했을 때, 소수 (minority) 파티션에 존재하는 마스터 노드는 사용 불가능하므로 consistency를 위해 availability를 trade-off하는 CP 시스템에 해당한다.

PNUTS는 일반적인 상황 (baseline case)에서 consistency를 희생하는 선택은 CAP에서의 consistency/availability tradeoff 라기보다는 consistency/latency tradeoff 때문이라고 할 수 있고, 일반적인 시스템에서 consistency를 희생하는 주된 이유가 CAP이 아니라는 증거를 보여주고 있다.

PACELC

DDBS에서의 consistency tradeoff는 CAP 대신 다음과 같은 PACELC로 좀 더 완전한 설명이 가능하다.

  • if there is a partition (P), how does the system trade off availability and consistency (A and C);
  • else (E), how does the system trade off latency and consistency (L and C)?

예를 들어, partition이 발생했을 때 availability를 위해 consistency를 포기하고, 보통의 상황에서는 낮은 latency를 위해 consistency를 포기하는 Dynamo, Cassandra, Riak과 같은 시스템들은 PA/EL 시스템이다. VoltDB/H-Store, Megastore와 같은 ACID 시스템들, BigTable과 이에 관련된 시스템들 (e.g. HBase) 은 PC/EC 시스템이다. MongoDB는 partition이 발생했을 때 master에서 복제되지 않은 데이터가 있더라도 새로운 master를 선출해서 서비스를 하기 때문에 PA/EC 시스템이다. PNUTS는 위에서 설명한대로 PC/EL 시스템이다. (이 때, PC는 CAP에서의 consistency가 아니라 일반적인 상황에 대비해서 consistency를 희생하지 않는다는 의미이다.)