[Amazon Dynamo] Vector Clock와 Quorum vote 기본 개념

프로그래밍/서버2020. 9. 18. 22:24

아마존 Dynamo는 eventual consistency를 지원하기 위해 Vector Clock을 사용합니다.

먼저 eventual consistency에 대해 살펴보겠습니다. Distributed system에선 availability를 위해 consistency를 일부 포기하는 경우가 많습니다. 즉, 클라이언트의 요청에 의해 여러 서버의 db가 갱신되어야 할 때, 모든 서버의 db가 갱신되지 않아도 클라이언트에 요청을 완료했다고 보내는 것입니다. 이 순간에는 서버 db의 consistency가 모두 일치하지는 않을 것입니다. 그러나 시간이 조금 지나면 결국(eventual)은 비동기적(asynchronously) 서버 통신에 의해 db는 동일한 값을 가지게 됩니다. 이게 eventaul consistency입니다.

반대말로는 (strong) consistency가 있는데 여러 서버의 db를 갱신해야 하는 경우 모든 서버의 db 값이 갱신됐음을 확인하고 클라이언트에게 리턴을 보냅니다. 이런 경우는 서버가 많아질수록 eventual consistency에 비해 속도가 느려질 것입니다. 또한 여러 서버 중에 일부가 고장나버리면.. 그 서버는 db를 갱신하지 못하게 되고 사용자(클라이언트)는 계속 기다려야 하므로 아주 치명적인 문제가 생깁니다.

 

Eventaul consistency는 개념은 쉽습니다. 그런데 이를 어떻게 구현해야 할까요? 수백, 수천대의 서버가 존재하는 환경에서 각각의 서버가 서로 다른 요청을 받고 그것들을 다른 서버에 전파해야 한다면 아주.. 뒤죽박죽이 될 것입니다.

A서버는 db의 특정 값을 +3 증가시키라는 요청(요청1)을 받고, 동시에 B서버와 C서버는 는 db의 특정 값을 -2 감소시키라는 요청(요청2)을 받았다면 어떻게 처리해야 할까요?

 

그냥 단순히 D서버에.. A, B, C서버가 받을 요청을 다 보내게 되면 요청2가 중복되어 +3 -2 -2의 효과를 가지게 됩니다. 우리가 원하는 효과는 +3-2인데 말이죠.

 

규칙이 있어야 합니다. 

그래서 Data versioning이라는 개념을 도입합니다. 각각의 변하는 값에 대해 version과 함께 기억하는 방법입니다.

0이던 값에 +3을 하게되어 +3이 됐다고 봅시다. 이 데이터를 D1이라고 부르고 version은 1로 줄 수 있습니다.

D1에 -2를 하게되며 +1이 됐습니다. 이 데이터를 D2라고 부르고 version은 2로 볼 수 있습니다.

 

이제 version 개념이 추가되서 version을 비교하면 어느 데이터가 먼저 발생한 데이터인지 나중에 발생한 데이터인지 알 수 있습니다.

 

위의 예는 서버가 1개인 경우에나 적합할 것 같습니다. 서버가 여러 개인 경우에는 어떻게 해야할까요?

 

Vector Clock

Vector Clock의 개념은 아주 간단합니다. 벡터 클락은 노드(서버)와 count의 쌍을 의미합니다. 바로 위의 예에 적용시켜보면 D1의 경우 벡터 클락은 [Sx, 1], D2의 경우 벡터 클락은 [Sx, 2]가 됩니다.(서버의 이름을 Sx라고 가정함)

3개의 서버 Sx, Sy, Sz가 있는 경우를 가정해보겠습니다.

 

 

클라이언트에서 db의 값을 +1 증가시키라는 요청이 왔습니다. 이 요청을 Sx서버가 처리합니다. 0이던 값은 +1이 됐습니다. 이를 D1이라 부르겠습니다. vector clock은 [Sx, 1]이 됩니다. 클라이언트에서 이번에는 서버 db의 값을 +2 증가시키라는 요청이 왔습니다. 이번에도 역시 Sx서버에서 처리하는 경우를 보겠습니다. db의 값은 3이 되겠으며 이를 D2라고 부르겠습니다. vector clock은 [Sx, 2]가 됩니다.

이번에는 client로부터 db의 값을 +3증가시키라는 요청을 받습니다. Sy서버가 이를 받아 처리합니다. 다행히도 Sy서버는 기존의 Sx서버 db에 있던 내용을 전달받은 상황입니다. 그래서 3이던 값은 6이 됩니다. 이를 D3라 부르겠습니다. vector clock은 ([Sx, 2], [Sy, 1])이 됩니다.

Sy가 작업을 처리하던 즈음에 Sz는 client로부터 db의 값을 -1 감소시키라는 요청을 받습니다. 다행히도 Sz서버도 Sx의 db내용은 전달받은 상황입니다. 6이던 값은 5가 됩니다. 이를 D4라고 부르겠습니다. 벡터 클락은 ([Sx, 2], [Sz, 1])이 됩니다.

 

이 시점에서 보면.. 서버 Sx, Sy, Sz는 모두.. 다른 값을 가지고 있습니다.. ㅎㅎ 말 그대로.. inconsistency한 상황입니다.

이 상황에서 어느 클라이언트로부터 db의 값 조회를 요청 받았다고 보겠습니다. Sx서버가 이를 처리한다고 보겠습니다.

Sx서버는 그냥 자기 db의 값을 리턴하지 않습니다. 현명하게 판단하기 위해 서버 Sy와 Sz의 벡터클락을 참고합니다.

 

서버Sx: ([Sx, 2])

서버Sy: ([Sx, 2], [Sy, 1])

서버Sz: ([Sx, 2], [Sz, 1])

 

각 벡터클락의 count(숫자)를 참고하면 됩니다. 서버 Sx가 볼 때 [Sy, 1]과 [Sz, 1]은 서로 다른 요청에 의한 것이었고 반영이 안된 상태이므로 자신이 이를 처리하여 벡터 클락이 ([Sx, 3], [Sy, 1], [Sz, 1])이 됩니다.(Sx가 이 문제를 처리했으므로 벡터 클락 count가 1 증가됨) 이를 D5라 부를 수 있습니다.

 

Quorum Vote(System)

Quorum을 사전에서 찾아보면.. (의사 결정에 필요한) 정족수 라고 합니다. 이게 Distributed System과 무슨 상관이 있을까요? 

 

Eventual Consistency를 지원하는 환경을 보면 각 서버(노드)는 서로 다른 값을 가지고 있을 수 있습니다. 이러한 상황에서 어떻게 consistency를 유지할 수 있을까요? 이를 위해 도입된 것이 Quorum vote(system)입니다.

 

간단하게 3개의 서버가 있는 경우를 보겠습니다.

Read와 Write를 할 때 3개의 서버를 처음부터 다 반영할 수 있지만 속도가 느려집니다. 

Write를 하는 경우를 보면 3개의 서버에 모두 다 값을 쓰면 1개의 서버에 값을 쓸 때보다 느려질 수 있습니다. 그래서 등장한 것이 eventual consistency이기도 하구요.

 

이런 상황에서 consistency를 유지하기 위해서 값을 쓰거나 읽어올 때 1개의 서버가 아닌 추가로 다른 서버의 값도 함께 보고 판단합니다.

 

R + W > N 

이라는 공식이 있습니다. N은 서버의 수, R는 read할 때 참고할 서버의 수, W는 write할 때 작업할 서버의 수를 의미합니다.

 

N이 3인 경우를 보면 R+W는 4이상이어야 합니다. write 또는 read할 때 0개의 서버에 대해 작업을 하는 것은 말이 안되므로 최소값은 1입니다. 그러면..

 

1. R는 1, W는 3

2. R는 2, W는 2

3. R는 3, W는 1

 

의 값을 가지는 경우가 최소한의 서버를 이용해 위 공식을 만족하는 경우입니다.

 

1. R는 1, W는 3

write할 때 3개의 서버에 모두 작업을 하는 경우에는, 서버의 값을 읽을 때.. 어느 1개의 서버의 값만 읽어와도 consistency가 유지됩니다. 왜냐하면 애초에 write할 때부터 모든 서버에 값을 썼으니까요 ㅎㅎ

 

2. R는 2, W는 2

write할 때 2개의 서버에만 작업을 하고.. 나머지 1개의 서버에는 이 작업이 없는 상태가 됩니다. 이 경우에 제대로 된 값을 읽어오려면 최소한 2개의 서버에서 값을 읽어와야 합니다. 그래야 적어도 그 중에 한 서버는 최신 값을 가지고 있어 그 값을 리턴할 수 있습니다.(최신값 판단은 벡터 클락으로 하는 것 같음)

만약 1개의 서버에서만 값을 읽어온다면.. 문제가 생깁니다. W가 반영되지 않은 바로 그 1개의 서버가 선택될 수도 있거든요.

 

3. R는 3, W는 1

write할 때 1개의 서버에만 작업을 하는 경우에는 read시에 3개의 서버에서 모두 값을 읽어오야 최신 값을 찾아 consistency를 유지할 수 있습니다. 3개가 아닌 2개의 서버에서 값을 읽어온다면 write가 반영되지 않은 바로 그 2개의 서버가 선택될 수도 있어 문제가 됩니다.

 

 

*잘못된 부분이 있을 수 있습니다. 잘못된 부분은 알려주세요~

 

참고

amazon-dynamo-sosp2007.pdf

작성자

Posted by 드리머즈

관련 글

댓글 영역