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
이 페이퍼가 제안하고 있는 알고리즘은 대략 다음과 같다.
- 어떤 key-value store에 대한 클라이언트의 모든 액세스에 대해 시작 시각과 종료 시각, 그리고 저장하거나 읽어온 값의 로그를 기록한다.
- 이 로그를 바탕으로 오퍼레이션이 vertex이고, should-happen-before 관계가 edge인 directed graph를 구성한다. 이 때 이 관계는 검증하려는 consistency 종류에 따라서 달라지는데, 대체로 시간의 관계, 값의 인과 관계를 의미한다고 보면 된다.
- 구성된 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