Dynamo, Cassandra, Riak, Voldemort와 같은 시스템들은 쓰기 가용성 (write availability)을 보장하기 위해, 어떤 하나의 데이터 항목의 여러 복제본이 동일한 데이터 항목의 복제본이 서로 다른 값으로 갈라질 (diverge) 수 있고, 이를 나중에 수리(repair)하는 방법을 고안하고 있다. 이 때, 복제본 버전들을 비교해서 어느 한쪽이 새로운 업데이트라서 다른 복제본들을 교체할 수 있는지, 아니면 동시적 (concurrent)이라서 한지를 semantic reconciliation을 필요로하는 지를 결정할 수단을 필요로 한다. 이러한 비교는 업데이트 사이의 인과적인 의존성 (causal dependency)에 따라 판단하는데, 인과적인 이력 (Causal History)을 모두 기록하는 것은 비효율적이므로, 이 정보를 요약하는 동시에 인과적인 의존성을 따질 수 있는 수단으로 람포트 시계(Lamport Clock)나 버전 벡터(Version Vector) 등의 개념들이 제안되고 실제로 위와 같은 시스템들에서 활용되고 있다.
이 논문에서 도입하고 있는 Dotted Version Vector는 인과적인 이력을 요약하기 위한 이러한 수단들이 가진 정확성(Correctness)의 한계를 개선하고, 동시에 확장성(Scalability)을 가지는 해결 방법으로서 제시되고 있다.
우선 이번 글에서는 논문의 전반부에 소개된, 인과성의 추적을 위해 사용되는 여러 방법들과 한계들에 대해서 알아보도록 하자.
1. 인과적인 이력 (Causal Histories)
우리가 다루고자 하는 클라이언트-서버로 구성된 스토리지 시스템에서, 클라이언트가 서버로 어떤 작업을 요청할 때마다 인과적인 관계가 발생한다. 이러한 관계를 formal하게 표현하기 위한 방법 중 하나가 인과적인 이력 (Mattern, 1994)이다. 인과적인 이력은 업데이트라는 사건들에 대한 유일한 식별자(identifier)의 집합으로 표현할 수 있다. 이 때 업데이트 사건의 식별자는 노드(리플리카 또는 클라이언트)의 식별자와 단조증가하는 카운터를 합쳐서 만들 수 있다. 업데이트가 발생할 때마다 새로운 식별자가 식별자의 집합에 추가하게 되고, 이 집합의 포함관계를 비교해서 인과성의 부분순서(partial order)를 추적할 수 있다. 두 집합이 서로를 포함하고 있지 않다면 동시적이라고 할 수 있다.
인과적인 이력은 개념적으로는 단순하지만, 업데이트에 따라서 식별자의 집합이 선형적으로 커지게 되므로, 실용적인 시스템에 사용하는 것은 적절하지 않다.
2. 인과적으로 호환되는 완전 순서 (Causally compliant total order)
업데이트들 사이의 인과적인 의존성과 호환되는 완전 순서를 정할 수 있다면, 이를 이용해 last writer wins 정책을 적용할 수 있다. 다른 방식들과 달리, 복제본 노드 (Replica Node)는 하나의 값만 유지하면 되고, 쓰기를 위해 읽기 문맥 (get context)에 해당하는 정보를 제공할 필요가 없기 때문에 매우 단순한 시스템을 얻을 수 있다는 장점이 있다. 문제는 이러한 완전 순서는 인과적인 의존성과 호환되지만, 동시적인 (concurrent) 업데이트들도 정렬해버리기 때문에, 어떤 동시적인 업데이트는 last writer wins 정책에 의해 잃어버리게 된다는 것이다.
2.1. 물리적인 시계
클라이언트들의 시계들이 잘 동기화된다면, 업데이트들을 물리적인 시계의 시간 순서에 따라 정렬함 (동시에 일어난 사건은 프로세스 ID를 이용해 정렬)으로써 완전 순서를 얻을 수 있다. 물리적인 시계에 기반한 완전 순서를 사용하는 방식은 Cassandra 0.6.x나 Dynamo에서 일부 애플리케이션에 대해 버전 벡터의 대안으로 사용되었다고 한다.
물리적인 시계에 기반할 경우의 문제점은 역시 클라이언트들의 시계들이 동기화에서 벗어날 때 발생한다. 시계가 느린 복제본 노드나 클라이언트는 항상 동시적인 업데이트 사이의 경쟁에서 지기 때문에, 항상 동시적인 업데이트를 잃어버리는 문제가 발생한다.
2.2. 램포트 시계 (Lamport Clock)
예전의 글에서 소개했듯이 램포트 시계는 역시 완전 순서를 위해 사용될 수 있는 논리적인 시계의 작동 방식을 제공하고 있다.
3. 서버별 항목을 가진 버전 벡터 (Version vectors with per-server entry)
서버별 항목을 가진 버전 벡터를 이용해 인과성을 추적하는 방법은 다음과 같이 작동한다.
- 클라이언트가 GET을 실행할 때 값에 반영된 사건들의 인과적인 이력를 나타내는 버전 벡터를 받음.
- 그 클라이언트가 PUT을 실행할 때, 이전의 GET에서 받았던 버전 벡터를 함께 보냄.
- PUT을 실행하는 서버는 새로운 업데이트를 반영하기 위해 로컬 카운터를 증가시키고, 서버의 식별자에 해당하는 버전 벡터의 항목에 저장.
- 새로운 버전 벡터를 서버에 저장되어 있는 다른 버전 벡터와 비교하고, 낡은 버전들을 모두 버린다.
서로 다른 서버들 사이의 업데이트들 사이의 인과성을 추적하는 것이 가능하지만, 동일한 서버에서 발생한 업데이트들 사이의 인과성을 추적할 수 없다. 즉, 동일한 서버에서 발생한 동시적인 업데이트는 또 다시 last writer wins 정책이 적용되므로, 적어도 하나의 동시적인 업데이트는 잃어버릴 수 밖에 없다. Plausible Clocks에서 설명하듯이, 이러한 문제의 본질적인 원인은, 동시적인 업데이트를 발생시키는 근원에 해당하는 클라이언트의 수에 비해서 적은 수의 버전 벡터 항목을 사용하기 때문이다.
이러한 방식은 Dynamo가 사용하고 있다.
4. 클라이언트별 항목을 가진 버전 벡터 (Version vectors with per-client entry)
서버별 항목을 가진 버전 벡터에서 살펴본 문제를 해결하기 위한 가장 자연스러운 접근 중 하나는 클라이언트별 항목을 가진 버전 벡터를 사용하는 것이다. 동작 방식은 다음과 같다.
- 클라이언트가 GET을 실행할 때 값에 반영된 사건들의 인과적인 이력을 나타내는 버전 벡터를 받음.
- 그 클라이언트가 PUT을 실행할 때, 이전의 GET에서 받았던 버전 벡터, 그리고 클라이언트의 식별자와 클라이언트별로 단조증가하는 카운터를 함께 보냄.
이 방식은 서로 다른 클라이언트들에 의해 발생한 동시적인 업데이트들 사이의 인과성을 완전히 추적할 수 있지만, 클라이언트 당 하나의 항목을 필요로 하기 때문에, 버전 벡터들의 크기가 클라이언트들의 수에 비례하게 되고, 이 방식을 실용적으로 사용할 수 없게 만드는 원인이 된다.
핑백: Paper: Dotted version vectors: Logical clocks for optimistic replication (Part 2) | The Last Mind