Replication & Consistency

데이터베이스를 구성할 때 복제 (replication) 은 중요한 요소입니다.

데이터의 복제는 성능, 가용성, 내결함성과 밀접한 연관이 있기 때문입니다.

이 포스팅에서는 데이터를 복제하는 방법과 일관성 (Consistency) 를 연관지어 살펴보도록 하겠습니다.

 

Leaderless replication 

Dynamo paper

Medium

Leaderless Replication In Distributed System

 

리더 없는 복제 (Leaderless replication) 에서는 단일 리더가 쓰기를 핸들링하지 않습니다. 

대신 모든 레플리카가 동일한 데이터에 대한 쓰기를 수행할 수 있으며  정족수 일관성(Quorum Consistency) 를 이용해 serial read / write 에 대한 일관성을 보장합니다. 병렬 read/write 가 가능한 환경에서는 eventual consistency 수준의 약한 일관성만을 보장하며 이를 위해 쓰기 충돌 해소를 위한 알고리즘이 필요합니다 ( LWW, Vector Clock, ...)

 

Quorum Consistency 란?

Write: N 개의 클러스터 노드 중 최소 W 개에 쓰기를 성공한 후 클라이언트에 ACK 반환 

Read: N 개의 클러스터 노드 중 최소 R 개의 레플리카로부터 값을 읽어 쓰기 충돌 해소 알고리즘을 통해 값을 결정

 

이와 같은 구현은 위 그림과 같이 W + R > N ( typically = N+1) 경우 선형적인 읽기/쓰기에서 강한 일관성을 보장합니다.

하지만 병렬 쓰기가 허용되는 상황에서는 단조 읽기 (monotonic read) 가 보장되지 않으므로 Leaderless replication 구조에서는 최종적 일관성 (eventually consistent) 이상을 보장하기 매우 힘듭니다. ( 이는 leader-follower 구조와 달리 쓰기가 단일 인스턴스에 의해 정렬되어 복제되지 않는다는 데에서 기인합니다 ) 

 

Eventual consistency 를 보장하기 위해 충분한 시간이 지나면 하나의 값으로 수렴해야 하므로 병렬 쓰기에 대한 충돌 해소 방법이 필요합니다. 자주 쓰이는 방법은 아래와 같습니다. 

 

LWW (Last Write Wins)

모든 쓰기에 타임스탬프를 첨부하고, 타임스탬프가 더 큰 쓰기를 최신값으로 간주합니다. 

컴퓨터가 사용하는 시계는 서로 정확하게 동기화할 수 없으며 오차가 존재하기 때문에 기본적으로 휴리스틱한 방법입니다. 단순한 구현을 위해 일관성을 트레이드 오프했다고 볼 수 있습니다. 예를 들면, 물리적으로 나중에 쓴 쓰기가 시간 오차떄문에 앞선 쓰기에 의해 유실될 수 있습니다. 

 

Vector Clock

클러스터의 노드 갯수를 길이로 가지는 Vector Clock 을 이용해 데이터의 버전을 관리합니다. 충돌하는 쓰기는 read 시점에 모두 반환하여 클라이언트가 병합하거나, 자동 병합 가능한 특수한 자료구조를 사용해 해소하는 방법 등이 존재합니다. Vector Clock 의 자세한 구현 방식에 대해서는 여기서 다루지 않겠습니다.

 

 

Leaderless replication 은 (W 와 R 에 따라 다르지만) 일반적으로 과반수 미만의 장애에 대한 내성을 가질 수 있습니다. 

 

Leader-follower replication 

단일 리더가 쓰기의 순서를 정하고 로그를 순차적으로 팔로워 노드에 복제하는 방식입니다. 단일 리더가 쓰기를 처리하기 때문에 일관성 보장 측면에서는 유리하지만, leaderless replication 처럼 노드 추가를 통해 쓰기 성능을 확장하는 것이 어렵습니다. 

 

Leader-follower 모델을 통해 serializable 수준의 consistency level 을 만족시킬 수 있는데, 좋은 예로 Apache Zookeeper 가 있습니다.  ZooKeeper: Because Coordinating Distributed Systems is a Zoo (apache.org)

ZooKeeper: Because Coordinating Distributed Systems is a Zoo

 

단, 데이터가 파티셔닝된 상황에서는 다릅니다. 파티셔닝이 포함된 leader-follower 모델의 데이터 저장소에 대한 읽기 쓰기는 복제 지연 문제에 의한 문제를 일으킬 수 있습니다. 아래 그림처럼 복제 지연으로 인해 Leader 에 수행한 쓰기의 순서와, Replica 에서 읽는 쓰기의 순서가 달라지는 것이 하나의 예시입니다.

 

 

Leader-Follower replication 은 별도의 장치가 없을 경우 리더 장애에 취약합니다. 이런 경우, Follower 중 하나를 Leader 로 승격시키는 알고리즘이 필요합니다. 일관성을 지키기 위해서는 Raft, Paxos 같은 분산 합의 알고리즘을 통해 새로운 리더를 선출하고, follower 의 과반수에 복제가 된 후 데이터를 커밋 ( follower 는 커밋 로그를 받기 전까지는 해당 쓰기를 읽기에 반환하지 않음) 하는 등의 추가적인 구현이 필요합니다.

 

 

 

 

Further Readings

하나의 세션 관점에서의 consistency 보장에 관해

Session Guarantees for Weakly Consistent Replicated Data (cornell.edu)

Session Guarantees for Weakly Consistent Replicated Data

Consistency Models

Session Guarantees for Weakly Consistent Replicated Data

Causal Consistency and Read and Write Concerns — MongoDB Manual

Causal Consistency and Read and Write Concerns — MongoDB Manual

Consistency Models (jepsen.io)

Consistency Models