분산 시스템 일관성 한판정리

분산환경 시스템을 학습하다 보면  linearizability, causal consistency, total ordering, atomic broadcast 등 비슷하면서도 다른 개념들로 인해 분산 시스템에서의 일관성을 이해하는데 종종 어려움을 겪고는 했습니다. 이번 포스팅을 통하여 위 개념들이 무엇을 의미하고 그리고 어떻게 다른지 살펴보도록 하겠습니다. 

 

Linearizable(Strong Consistency, Atomic Consistency) 

Linearizable 한 시스템은 분산 환경에서 발생한 모든 이벤트를 발생한 절대적인 시간 기준으로 순서(global order)를 매길 수 있습니다. Linearizable 한 시스템에서 발생한 모든 이벤트는 단일 프로세스에서 이벤트를 순차적으로 발생시킨 상황처럼 모든 이벤트 간의 순서를 알 수 있습니다. 

 

Total Ordering 

Total ordering를 보장하는 시스템은 분산 환경에서 발생한 모든 이벤트의 순서를 매길 수 있습니다. Linearizable과 다른 점은 이벤트가 발생한 절대적인 시간이 아닌, 논리적인 순서를 지정할 수 있음을 의미합니다. 예를 들어 total ordering을 보장하는 시스템에서 두 이벤트 A, B가 순차적으로 발생했다고 보더라도 linearizable 한 시스템에서 B가 A보다 절대적인 시간을 기준으로 더 빠르게 발생한 이벤트라면 B가 A보다 순서가 빠르다고 간주합니다. 

 

Lamport Clock(or Timestamp) 

Lamport clock은 total ordering을 가능케 하는 대표적인 방식입니다. 동작 방식은 다음과 같습니다. 

• N개의 프로세스로 구성된 분산 시스템이라고 가정하면(p0, p1, ... pN-1) 
• 각각의 프로세스는 스스로 생성하는 모든 이벤트에 (logical_clock, process_id)를 추가합니다. logical_clock는 timestamp가 될 수도 있고 또는 전체 프로세스에서 가장 큰 값이 될 수도 있습니다. 
• 두 이벤트의 logical_clock이 동일하면 process_id를 활용해서 이벤트 간 순서를 비교합니다. 

Lamport clock을 사용하는 시스템에서 만드는 모든 이벤트는 (logical_clock, process_id)가 유일함을 보장할 수 있기에 total ordering이 가능합니다. Total ordering은 가능하지만 linearizable은 왜 보장할 수 없을까요? Lamport clock에서 각 프로세스가 스스로의 시간을 사용하면 linearizable을 보장할 수 있는 게 아닐까요? 각 프로세스의 시간이 과연 동기화(clock synchronization)가 되어있을까요? 정확하게 동기화가 되지 않는 이상 각각의 프로세스에서 생성된 timestamp는 절대적인 기준의 시간이 될 수 없습니다. 따라서 linearizable 한 시스템이 보장해야 하는 이벤트 간 절대적인 시간 기준에 대한 조건이 충족될 수 없기 때문에 lamport clock이 각 프로세스의 timestamp를 사용하더라도 linearizable 하다고 볼 수 없습니다. 

 

Causal Consistency 

Causal consistency를 보장하는 시스템은 A 이벤트(원인)로 인해 B 이벤트(결과)가 발생하였을 때, B로 인한 효과를 관찰할 수 있으면 시스템의 어디에서든 A로 인한 효과도 관찰할 수 있도록 보장합니다. Total ordering, linearizable과 비교하자면 앞선 두 속성은 모든 이벤트 간의 순서(global order)에 관심을 두지만 causal consistency는 부분적인 이벤트들 간의 순서(partial order)에 관심을 둡니다. 

 

Vector Clock 

Vector clock은 causal consistency를 보장할 수 있는 대표적인 방식입니다. Vector clock의 특성은 다음과 같습니다. 

• Vector clock은 일종의 배열(array)입니다. 시스템 내 전체 프로세스의 수를 N이라고 가정했을 때 vector clock의 길이는 N이 됩니다. 
• 각각의 프로세스는 모든 메시지에 자신이 알고 있는 vector clock을 포함시킵니다. 

동작 방식은 다음과 같습니다. 

• 프로세스가 실행되면 vector clock을 초기화합니다. 시스템에 5개의 프로세스가 있다고 가정하면 vector clock은 [0, 0, 0, 0, 0]으로 초기화됩니다. 
• 프로세스가 이벤트를 생성하는 경우 vector clock에서 해당하는 위치의 값을 1 증가시킵니다. [0, 0, 0, 0, 0] -> [0, 1, 0, 0, 0] 
• 다른 프로세스로부터 메시지를 수신받으면 메시지에 포함된 vector clock과 자신이 소유한 vector clock을 합칩니다. Vector clock의 최댓값만을 선택하는 방법으로 합치게 됩니다. 예를 들어 [0, 1, 0, 0, 0]과 [1, 0, 0, 0, 0]을 합치면 [1, 1, 0, 0, 0]이 됩니다. 

Vector clock에서 causal consistency가 보장되는 원리는 다음과 같습니다. 

• [0, 0, 0, 0, 0]는 [1, 1, 1, 1, 1]과 비교했을 때 확실하게 이전에 발생했음을 알 수 있습니다. 즉, 예시의 두 vector clock은 비교 가능합니다. 
• [0, 1, 0, 0, 0]과 [1, 0, 0, 0, 0]에서 어떤 이벤트가 먼저 발생했는지 알 수 없습니다. 즉, 예시의 두 vector clock은 비교가 불가능합니다. 

만약 서로 다른 이벤트가 인과관계가 있다면 vector clock 간에 비교가 가능합니다(이벤트를 발생시키는 주체들끼리 vector clock을 주고받으면서 순차적으로 값을 올리기 때문). 즉, vector clock을 활용하면 이벤트 간에 causal consistency를 보장할 수 있음을 의미합니다. 

 

Causal consistent 한 시스템에서 우리가 "캐릭터명 생성" 기능을 만든다고 가정해 보겠습니다. 캐릭터명은 전체 시스템에서 유일함을 보장해야 한다는 제약조건이 존재합니다.

 

두 클라이언트가 동시에 A, B 요청을 보냈다고 가정하겠습니다. 두 요청은 모두 "devvy"라는 캐릭터명이 포함되었다면 causal consistent 한 시스템은 이를 어떻게 처리할 수 있을까요? 앞서 설명드린 vector clock을 사용해서 A 요청이 [1, 0]에 해당하고 B 요청이 [0, 1]에 해당하는 vector clock을 사용한다고 가정하겠습니다. 그럼 과연 어떤 요청을 수용하고 어떤 요청을 거절해야 할까요. Causal consistent 시스템에서는 인과 관계가 있는 이벤트의 순서는 보장해 주지만 그 외의 경우에는 순서를 보장하지 않습니다. 이러한 한계를 극복할 수 있는 방법으로 total order broadcast가 있습니다. 

 

Total Order Broadcast(Atomic Broadcast) 

Total order broadcast부터는 애플리케이션 개발자들이 자주 접하는 시스템들에 구현체가 존재합니다. 예를 들면 Zookeeper의 ZAB(Zookeeper Atomic Broadcast)라던지 etcd의 RAFT 등이 있습니다. Total order broadcast는 다음과 같은 속성을 지닙니다. 

• Reliable delivery: 메시지는 모든 노드로 전달됩니다. 
• Totally ordered delivery: 메시지는 모든 노드로 동일한 순서로 전달됩니다. 

위 두 특성을 보장하기 때문에 causal consistent 한 시스템에서 불가능했던 기능이 구현이 가능해집니다. Total order broadcast의 대표적인 구현체인 Raft에 대해 살펴보겠습니다. 

 

Raft 

Raft에는 3가지 유형의 참여자가 존재합니다. 

• Leader: 클라이언트의 요청을 처리하며 follower에게 복제 데이터를 제공하는 주체입니다. 
• Follower: Leader로부터 복제 데이터를 받아 저장하지만 클라이언트의 요청을 처리하지는 않습니다. 
• Candidate: Leader로 선출될 가능성이 있는 프로세스를 의미합니다. 

동작 방식은 크게 leader election과 log replication으로 나뉩니다. 

• Leader election
  • Follower process는 leader와 heartbeat message를 주고받습니다. Heartbeat가 일정 시간 동안 오지 않으면 leader election를 수행합니다.
  • Follower는 자기 자신이 새로운 리더가 되기 위해 자신의 상태를 candidate으로 변경하고 다른 프로세스들에게 자신을 leader로 뽑아달라고 요청(vote request)합니다. 
  • 대다수(보통 정족수)의 프로세스에 동의를 받은 candidate가 leader가 됩니다. "대다수"라는 조건 덕분에 split brain 현상을 방지할 수 있습니다. 
• Log replication 
  • Leader가 클라이언트의 쓰기 요청을 수신하면 스스로의 log에 기록하고 follower의 log에도 요청을 기록하도록 합니다. 
  • 대다수의 follower가 log 복제에 성공하면 클라이언트 요청을 처리했다고 간주하고 클라이언트에게 응답합니다. 

시각화를 통해 Raft를 더 자세히 이해하고 싶다면 아래 링크를 확인해주세요. 

Raft