Consistency

Data-centric consistency models에는 세 가지가 있다[1]. client-centric consistency models까지 덧붙여서 생각할 수도 있지만[2], 일단 NOSQL 특성에 주로 표현되는 것만 생각한다.

eventual consistency: 복제를 언젠가는 마쳐서, 다같이 같은 값을 보는 일관성을 보장한다.(가장 약한 보장)
causal consistency: 인과성이 있는 작업은 그 순서대로 보여야 한다.
sequential consistency: 모든 연산이 특정 순서대로 실행된 것으로 보여야 한다.

2번에 추가적인 설명을 하자면, insert A=1 이후 update A=2 를 했다면 맨 마지막 A=2 만 보이거나, A=1이 보인 뒤 A=2가 보여야한다는 말이다. 1번만 보장하는 DB의 경우에는, 방금 두 연산이 node X에서 실행된다고 하면 node X에서는 A=2가 보이고, 데이터를 복제중인 node Y에서는 A=1이 보이는 상황이 가능하기 때문이다.
이 때 2번의 경우에는 insert B=3을 어느 시점에 하더라도, B=3이 어떤 때에 보이는지는 관계없다. 왜냐하면 서로 인과성이 없기 때문이다.(1번도 당연히 같다. 더 약한 보장이기 때문이다.)

단일 리더 복제는 선형적이 될 수 있으며, 설계/동시성 버그/split brain 등으로 인해 비선형적이 되기도 한다. 주키퍼는 합의 알고리즘을 통해 단일 리더를 선출하고 동작하므로 선형적이라고 한다.
다중 리더 복제는 충돌이 필연적으로 발생하므로, 충돌 해소가 필요하며 이 때문에 비선형적이다.
리더 없는 복제는 write와 read를 할 때, 공유하는 node들에게도 실행해서 선형적임을 보장받을 수 있다. 그러나 선택에 따라 비선형적이 될 수도 있는데 이에 대해 설명한다.

리더 없는 복제의 정책

리더 없는 복제는 Dynamo에 기반한 DB에서 사용한다. 정족수(quorum) 쓰기와 읽기를 한다. dynamoDB와 같은 NOSQL은 보통 eventual consistency를 기본으로 제공하고, 정족수를 사용해서 sequential consistency를 제공한다고 알려져있다.

정족수 읽기가 2 이상일 경우(r > 1), 여러 읽기 도중 오래된 값을 가진 node가 있다면 이를 복구해준다. 이를 읽기 복구(read repair)라고 한다. 오래된 값을 가진 node가 있는 지 백그라운드 프로세스가 지속적으로 찾는 것을 안티 엔트로피 처리라고 한다. 두 메커니즘을 모든 DB가 구현하는건 아니다.
쓰기 가용성을 높이기 위해 정족수 w를 만족하지 않아도 일단 연결할 수 있는 node에 기록하는 것을 느슨한 정족수, 나중에 끊어진 node가 연결되면 수용한 쓰기를 보내주는 것을 hinted handoff라고 한다. DB마다 선택할 수 있는 정책이다.

쓰기 충돌이 일어나면 LWW(last-write-wins)를 해소 방법으로 쓰거나, version vector를 사용해서 동시에 일어났는지 판단하고 정책에 따라 값을 정할 수 있다. LWW는 모든 머신간 시간 동기화를 하기 힘드므로 사실상 부정확한(비선형적) 충돌 해소 방법이다. version vector를 통해 동시에 값이 바뀐걸 확인하고, 두 값의 합집합을 취하면 손실없이 데이터를 병합할 수 있다(version clock과 version vector는 다르다고 하지만, 예시이다.[3, 4]).

리더 없는 복제가 선형성을 보장하려면, 정족수를 w + r > n으로 설정하고, read 시 read repair를 동기로 하고, write할 client는 쓰기 충돌을 막기 위해, write를 보낼 node들의 최신 상태를 알아야 한다. Cassandra는 read repair를 동기로 하지만, write시 LWW로 충돌해소를 하기 때문에 선형성을 보장할 수 없다. 사실상 리더 없는 복제는 비선형적이라고 가정하는게 안전하다.

다중 리더 복제와 리더 없는 복제는 결함 노드, 네트워크 중단, 지연 시간 급증에서 견고하지만 일관성을 보장하기 힘들다.

Cassandra의 tunable consistency

Cassandra는 CAP에서 C를 eventual consistency로 제공하지만, linearizable consistency도 제공할 수 있다고 주장한다[5]. 정족수를 파라미터로 설정해서 r + w > n 이면 후자를 보장할 수 있다고 하는데, 이론적으로 거의 가깝지만 앞서 확인했듯이 LWW를 사용하므로 완벽하다고 하기는 어렵다. 그 외에도 파라미터에 다양한 값을 줄 수 있고, 값에 따라 consistency를 "tune"할 수 있다고 하는데 큰 의미는 없어보인다.