분산시스템(Distributed System) - 4(Replication)

Replication이란 fault tolerance한 분산시스템을 만들기 위해 데이터의 카피를 여러 노드에 복사해서 관리하는 것이다. 하나의 노드가 죽거나 문제가 생기더라도 다른 노드에 같은 데이터를 가지고 있기 때문에 시스템은 중단이나 문제없이 계속 실행이 될 수 있다. 하지만 데이터는 계속 변화가 있을 것이고 이를 모든 replica에 적용을 하고 유지하는 것은 쉽지 않다. 이번 강의에서는 latency 등은 고려하지 않고 순수하게 여러 노드에서 데이터를 일정하게 유지하려면 어떻게 해볼까를 다루고 있다. 

 

왜 어려울까?

여러 노드에서 데이터를 관리한다는것은 모든 노드의 데이터 싱크를 맞추어야 한다는 것과 같은 말이다. 클라이언트에서 데이터 변경 또는 읽는 요청을 보낼 때 어떤 각 노드의 데이터가 다르다면 문제가 생길 수 있다. 이를 Read-after-write consistency라고 부른다. 데이터 업데이트를 하고 해당 값을 다시 보았을 때 업데이트된 값이 보여야 한다.

하지만 위의 경우처럼 A노드에는 데이터 업데이트가 원활히 되지 않았는데 데이터를 읽을 때는 A의 데이터만을 가지고 오는 경우 발생할 수 있다. replica가 많아진다면 데이터를 읽는 요청을 보냈을 때 다른 응답 값들이 올 것이다 이중에 어떤 값이 맞는 값인지 판단하는 것은 쉽지 않다. 

 

어떻게 다른 데이터를 가지고 있을 수 있는 여러 노드에서 read-after-write consistency를 보장할 수 있을까?

 

대부분의 분산시스템은 majority quorum이라는 알고리즘을 이용하여 이 문제를 해결한다. (n + 1) /2 를 반올림한 수만큼의 노드에 데이터 업데이트와 수정을 하면  최소한 하나 이상의 공통 노드가 선택된다. 노드가 A, B, C 3개라고 가정한다면 쓰기를 A, B에 하고 읽기를 B, C노드를 통해 한다면 B노드라는 공통이 생긴다. 각 노드에서의 최신 데이터를 구분하기 위해 데이터에 logical clock을 이용하여 순서를 기록하고 데이터를 제거하는 경우 실제 데이터를 제거하는 방식이 아닌 deleted상태를 명시적으로 표시함으로써 데이터 변화의 히스토리를 남길 수도 있도록 한다면 분산 환경에서 각 노드들의 상태를 관리할 수 있다. 하지만 majority quorum을 이용하기 위해서는 최소한 3개의 노드가 필요하기 때문에 노드가 죽는 경우를 생각하여 3개보다 더 많은 수의 노드를 사용해야 한다.

그렇다면 최신 값이 업데이트되지 않은 노드들은 어떻게 싱크를 맞추는 것일까

 

위의 이미지처럼 최신 값을 받은 노드를 제외한 나머지 노드에 새로운 값을 보내주면 된다.

클라이언트가 읽기 요청을 보내고 A와 B에서 데이터를 받는다 C는 실패하지만 quorum만큼 응답을 받기 때문에 읽기는 완료가 되고 이중 가장 최신의 정보를 이용하고 최신 정보를 보내준 노드 B를 제외한 노드에게 새로운 값을 업데이트해준다 이때 노드 C의 상태는 상관없이 업데이트를 해준다. 이러한 과정을 read repair라고 한다. (AWS의 Dynamo database에서 이와 같은 방식을 사용하고 있다고 한다)

 

데이터의 싱크를 어떻게 맞출지에 대해서는 끝났지만 네트워크는 항상 불안하다 메시지가 누실될 수 있다. 이를 위해 broadcast 알고리즘을 도입한다. FIFO-total-order-broadcast를 이용할 것이다. FIFO-total-order-broadcast를 이용한다면 replica들의 상태가 메시지를 받을 때마다 업데이트될 것이고 이를 state machine replication(SMR)이라 한다. SMR에서는노드가 동일한 순서로 input을 처리한다면 동일한 순서의 output 이 나오게 된다. 그렇기 때문에 동일한 순서의 input 을 결정해서 그것을 모든 노드에 뿌려주는 작업을 해야 한다(이는 FIFO total order broadcast이다). 같은 상태를 가진 두 개의 replica들이 같은 input을 가진다면 같은 상태로 변할 것이다. 에러가 발생하는 것도 둘 다 똑같이 적용될 것이다. 만약 하나만 에러가 발생한다면 둘의 상태는 다른상태가 된것이다. 이것또한 똑같아야한다. 하지만 total-order-broadcast를 이용한다면 전체의 순서를 맞추기위해 바로 적용이 되지않는 단점이있다. 그리고 전체의 순서를 관리할 리더의 존재가 필요하다. 리더가 single point of failure(SPOF)기 때문에 이를 관리해주어야하는데 이는 다음 포스트에서 정리할 Concensus에서 볼것이다. 사실 이강의를 보기 시작한 raft 알고리즘이 있는 포스트가 될것이다. 

 

포스트의 모든 이미지는

https://www.youtube.com/channel/UClB4KPy5LkJj1t3SgYVtMOQ/videos 와 Introduction to Reliable and Secure Distributed Second Edition에 있다.