분산시스템 (6) Consensus

- 주제: consensus and agreement. 다수결.

교실의 36명에게 투표를 해서 시험시간의 시간을 선택하는 예. 선거도 동일.

굉장히 다양한 분야에서 활용. 투표 외에도 5명의 목격자에게 물어서 3명이 의도적으로 사고를 냈다고 하고 2명이 아니라고 하면 3명의 말을 신용.

 

 

 

01. 분산시스템의 특징: Unreliable

1) Unreliable networks: 메세지는 로스트될수도, 재전송될수도, 복제될수도, 딜레이될수도 있다.

메세지라고 하는 것이 네트워크를 통해 교환되는데, 메세지를 보냈으면 저쪽에서 100% 받는것을 보장하지 않는다.

 

2) Unreliable Clocks: 각각의 서버는 다른 시간을 가질 수 있는데, 서로 일치하는게 베스트이다.

이 컴퓨터에서는 9시여도 다른 컴퓨터에서는 9시 1분일 수 있다. 시간이라는 것은 굉장히 작은 단위로 쪼개질 수 있고 - 엄밀하게 따지면 각각의 서버들은 나노 단위로라도 시간이 다를수밖에 없다.

'그 서버의 시간' = 네이비즘. 

분산시스템이 궁극적으로 목적하는 것: 컴퓨터를 100대 사용하더라도 서버가 한대만 있는 것처럼 보여지는게 좋은 것(클라이언트 입장에서). 모든 컴퓨터가 하나의 오차도 없이 동일한 시간을 보유하고 있는 것이 최적 - 하나가 있다는 경험을 얻을 수 있다.

 

3) Unreliable Knowledge: 서버가 거짓말을 할 수 있다.

이때까지는 진실만을 이야기하는 서버들을 가정해왔다. 그러나 서버가 거짓말을 할 수도 있다.

어떤 경우에?

(1) 웹서버가 3개가 있는데, 하나가 해킹을 당해서 악의적인 데이터가 심어졌다면 - 세개가 동일한 목적의 웹서버라고 했을 때 해킹을 당한 서버로 가면 잘못된 값을 읽게 된다.

(2) 실제로는 해킹이 아니어도 서버가 잘못된 응답을 할 수 있다. 하드웨어와 소프트웨어는 "버그"에 취약하다.

- 소프트웨어: 100번 질문을 하면 99번은 정답을 내도 1번은 오답을 낼 수 있다.

- 하드웨어: 물리적으로 노후화가 되어서 비트가 뒤집히며 전혀 다른 값이 도출될 수 있다.

 

 

 

02. Lamport wallclock (=Lamport timestamp)

 

1. Linearizability

- 클라이언트는 가장 최신의 데이터를 읽어야 한다.

- 가자 최신의 데이터 = 순서의 문제. 모든 요청은 순서에 따라 실행된다.

- 이때 순서는 시스템 서버에 따라 동의된 순서이다.

 

수많은 메세지들이 도착하게 되었을 때, 순서대로 실행이 되어야 한다.

클라이언트들은 항상 최신의 데이터를 읽어야 한다. A=3일때, read(A)를 하면 3을 얻고, A=4가 되면 read(A)에서 4를 얻어야 한다. 이때 값이 중간에 변경되면 그것 또한 즉시 반영되어야 한다. 그러나 어떤 클라이언트는 짧은 시간동안 3을 얻을 수 있다. (weak consistence)

 

최신의 데이터라는 것은 순서의 문제.

모든 요청은 순서대로 실행되어야 한다. A=3, A=4이면 최종적으로 4. A=4, A=3이면 최종적으로 3.

이때 순서는 시스템에 서버들이 서로 동의를 한 순서이다. 클라이언트와 서버의 순서가 서로 다르다면, Linearizability할 수 없다.

클라이언트가 어떻게 보냈는지는 중요하지 않고, 서버들이 서로 동의한 순서가 중요하다. 클라이언트가 항상 최신의 값을 읽기 때문이다. 이때 최신의 기준은 서버이다. 서버의 도출값이 서로 같으면 Linearizability하다! (심지어 클라이언트의 순서와 달리 뒤집혀 있어도.)

 

 

2. Lamport Timestamp

- 각각의 노드는 고유한 identifer와 처리된 작업을 위한 counter를 가지고 있다.

식별을 위한 node ID, 카운터를 위한 변화 가능한 counter.

- counter : indentifer 페어.

- 각 이벤트에 글로벌하게 고유해야 한다.

- 일관성 있는 종합적인 순서를 부여해야 한다.

 

1) 카운터에 따라 순서가 진행된다.

2) 만약 카운터가 동일하다면, tie-breaker로 식별자를 사용한다.

3) 실제 시간에 따른 순서 <-> 식별된 순서가 tie-breaker때문에 다르다면? 여전히 linerizable하다고 할 수 있는가?

(1) 만약 서버가 그 순서에 동의한다면, 문제가 되지 않는다.

(2) linerizable가 포함되었는지는 클라이언트의 관찰에 따른다.

 

 

컴퓨터는 시간을 메인보드에 있는 CPU의 틱을 계산하는 기계로 잰다. 컴퓨터는 우리가 인식하는 시간체계를 사용하지 않는다. 1틱이 인간의 시간으로 얼마냐는 CPU에 따라 다르다.

똑같은 시간체계를 내부에서 가지고 있어야 하기 때문에 등장한 것이 Lamport timestamps.

 

메세지를 처음 하나 맡으면 0번, 1번, 2번으로 이어진다.

각각의 노드는 고유한 identifier와 counter을 가지고 있다. 둘이 튜플 형태. 각각의 이번트에 따라 고유하다.

 

카운터는 증가한다 - 글로벌 유니크하지 않다, 겹칠 수 있다.

서버의 요청이 들어올때마다 1씩 증가시키는데 분명히 동일한 카운터 번호를 획득할 수 있다.

identifier을 그래서 넣어준다. 절대 안 겹치게 해준다.

둘로 구성된 조합을 생각하면 - 절대 겹치지 않는다. 겹치는 경우 identifier이 겹쳐야 가능하다.

= 결과적으로 글로벌한 유니크한 타임 스탬프가 나온다.

 

-> 어떻게 순서를 구분하는가?

카운터를 이용해서 순서를 정한다. 1차적으로는 카운터로 순서를 정하고, 카운터가 동일한 수가 된다면 - 그때 식별자를 2차적으로 사용해서 우선순위를 정한다: tie-breaker.

 

분명히 동일한 값이 들어갔는데 최종적인 값이 다른 경우가 생길 수 있다.

 

카운터는 받을때마다 1씩 증가시킨다. identifier은 아니다.

순서는 서버가 정하며 서버가 기준이다.

 

 

 

03. Consensus 합의

: "비록 개개인은 동의하지 않을수도 있어도" 모든 그룹 멤버들에 의해서 도출이 된 결정이다.

- 즉 만장일치가 아니더라도, 다수결에 의해 결정이다.

- 문제점: 서로의 의사를 물어봐야 하는데 - 어떻게 unreliable한 통신에서?

 

- Linearizability, total ordering, consensus은 동일한 문제이다.

total ordering을 전하는 것은 서버. 서버들이 동의했다 = 서버들간의 consensus(합의)의 결정에 의한 순서.

consensus는 만창일치는 아니기 때문에 부수적인 건 들어간다.

- 셋 중 하나를 달성한다 = 셋을 자연스럽게 달성한다.

 

 

1. Consensus protocols

1) Paxos.

수학적, 논리적인 말들로 구성되어 있다. 수업시간에는 말로 풀어서 설명했지만 실제로는 수학적으로 엄밀한 설명이다. 활용 용도는 굉장히 넓은데 사람들이 잘 이해하지 못했다.

2) Raft.

위를 훨씬 더 단순하게 만든 것. 최대한 단순화해서 다양한 사용 케이스에 잘 적용시킬 수 있도록 만들어졌다.

3) ZAB. ZooKeeper Atomic Broadcast.

주키퍼 코디네이터가 다운되어버리면 아무것도 못 하기 때문에 여러개로 복제한다. 결국에는 주키퍼라는 것도 복제하다 보니 - Atomic Broadcast를 사용해서 복제한다.

 

- Consensus protocols은 레플리케이션 프로토콜이 아니지만, 레플리케이션을 하는 데에도 사용할 수 있다.

= 결국 레플리케이션 프로토콜이라는 것은 데이터의 상태정보를 여러대의 서버에 동일하게 가지기 위해서이기 때문이다.

Consensus protocols이 복제 프로토콜보다 더 상위의 개념이다.

 

 

2. quorum(정족수)를 사용.

: 모든 노드의 다수결.

3개의 서버의 2개, 5개의 서버의 3개.

 

의사결정을 위해 다수결을 이용. 이때 consensus에 참여하는 서버의 수가 정족수를 넘어야 한다. 

100명의 사람이 있는데 '무슨 저녁 먹을래?'의 투표에서 한쪽이 51개가 넘어야 한다. 그런데 한 사람이 투표 참여를 하지 않아서 50:49가 나온다.

서버 기준으로 보면 투표에 참여하지 않았음은 모종의 손실문제가 발생했다는 것이다. 정족수를 반드시 만족해야 한다.

일반적으로 홀수 단위로 사용. 동률, 1:1인 경우가 나오기 때문에. 그래서 3, 5, 7 사용.

 

- Quorum reads, Quorum writes.

1) Quorum consistency: 유효성과 성능의 균형을 맞춘다.

2) Read repair: 읽기를 커밋한 이후 레플리카의 오래된 값을 업데이트한다.

 

 

레플리카가 종 5개가 있다. 각각 2 2 2 2 2 라고 하자.

쓰기를 해서 5개의 레플리카에게 전부 메세지를 전달한다. 이때 4,5가 실패한다. 답장이 3개만 돌아온다.

 

Q. 내가 값을 A=3로 바꾸는 것에 동의해?

A. 3개가 동의합니다라고 하고 2개는 동의하지 않습니다를 말한 것과 동일한 결과.

3 3 3.

이때 3은 정족수를 넘었기 때문에 쓰기를 그대로 커밋함. 

 

이제 값은 3 3 3 2 2 가 되었다. 

 

Q. 읽기를 할때 5개에게 보내서 - x라는 값의 키값을 읽고 싶어.

A. 3개의 답을 얻고 2개의 답을 얻지 못했다.

3, 2, 2.

도착을 한 값에서 다수는 2이지만 - 읽기 커럼은 3이다. 이때 커럼은 만족되지 못했다.

커럼이 만족되려면: 3, 3, 3어야 한다. 다른 값 2개와는 관계가 없기 때문에 - consistency가 발동한다.

 

 

- r + w > n : consensus를 성립하는 n개의 노드의 공식.

n = 노드의 수.

r = read Quorum.

w = write Quorum.

 

1) 일반적으로, w와 r은 초과되어야 한다.

2) w + r > n 하면 linearizability하다고 한다. 다르다면, eventual consistency하다.

 

 

밥이 read 요청을 전부에게 보내던가, 최소 2개에게는 보내야 한다.

일부에게만 보내고 싶다면 로지컬 타임스탬프를 사용해서 버전정보를 함께 기입해야 한다.

 

* read repair: 읽고 나서 보니까, 업데이트가 안 된 옛날 값을 가진 서버가 있었다. 읽고 난 후에 다시 업데이트 해준다.

3) 일부에게만 보내져서 linearizabile가 만족되지 않았을 때: 버전정보를 쓰고 리페어를 해야 만족하는 경우도 있다.

 

 

3. Leader election by Raft

- Consensus는 일렉션에서 자주 사용된다.

 

- 리더가 있었는데 리더가 죽었을 때: 누구를 선출해야 할지를 정해야 한다.

방법으로는 다음이 있다.

(1) 사전에 미리 순위를 정해둔다.

(2) 투표로 선출한다.

(3) 리더의 사망 첫 발견자가 리더가 된다.

 

리더가 죽으면 - 그것을 발견한 레플리카가 투표를 요청한다.

리더는 평소에 자신의 상태정보를 레플리카에게 전송한다. 그 메세지가 오지 않으면 레플리카 중 누군가는 사망을 첫 발견하게 된다. 다른 레플리카들에게 리더의 사망 고지/선출 요청을 한다.