레이블이 consistency인 게시물을 표시합니다. 모든 게시물 표시
레이블이 consistency인 게시물을 표시합니다. 모든 게시물 표시

2018-03-25

CAP theorem

CAP theorem은 분산 스토리지는 consistency(a.k.a. C), availability(a.k.a A), partition tolerance(a.k.a. P)를 동시에 만족시킬 수 없다는 것이다. 여기서 C, A, P는 각자 일반적으로 사용되는 용어와 다른 용어로 사용되기 때문에 CAP theorem을 이해하려면 각자가 정의하는 것을 이해하는 것이 중요하다.

C는 모든 read operation이 최신 데이터를 받는 것을 보장하는 것이다. C를 보장하는 시스템은 만약 최신 데이터를 돌려줄 것을 보장하지 못한다면 에러를 돌려줘야 한다. 개인적으로 분산 스토리지를 구현할 때 C, A, P 중 가장 구현하기 어려운 특성은 C라고 생각한다.

A는 모든 operation이 에러가 아닌 데이터를 돌려주는 것이다. 이때 돌려주는 값은 최신 값이 아니어도 상관없다. 심지어 eventual consistencyA를 보장하는 시스템에서는 실제로 존재할 수 없는 데이터 조합이 생길 수도 있다.

P는 partition 상황에서도 시스템이 정상 동작해야 한다는 것이다. 여기서 시스템이 정상 동작한다는 것이 언제나 최신 데이터를 보장하거나 에러가 아닌 값을 준다는 것이 아니다. 그것은 CA가 보장하는 것이고 partition 상황에서도 partition이 아닌 상황과 같은 것을 보장하면 P를 보장한다고 할 수 있다.

근데 여기서 partition은 정말 네트워크 레이어에 문제가 생겨 물리적으로 다른 망이 구성되는 상황을 말하는 것이 아니다. partition은 일부 메시지가 전달되지 않는 상황도 포함된다. 이는 분산환경에서 매우 흔히 발생하는 일이고 P를 포기한다는 것은 결국, 분산 환경을 포기한다는 말이 되기 때문에 분산 데이터 스토리지를 만들 때는 결국 CPAP 중 하나를 선택해야 한다.

개인적으로 생각하기에 CPAP 중 구현하기 더 어려운 것은 CP라고 생각된다. 모든 노드가 언제나 같은 상태를 유지하게 하는 것은 생각보다 어렵고 비싸다. 게다가 CP는 근본적으로 AP보다 latency와 throughput이 떨어진다.

하지만 이런 문제에도 불구하고 데이터 스토리지를 사용하는 application을 선택하는 입장에서는 AP보다 CP를 선호해야 한다고 생각한다. CP 대신 AP를 선택하는 이유는 가용성 때문이다. 가용성은 분명 중요하다. 하지만 스토리지의 가용성과 application 전체의 가용성은 다른 말이다. 데이터 스토리지가 정상적으로 동작하고 있다고 하더라도, 데이터의 일관성이 보장되지 못해서 잘못된 값을 돌려주었다면 이 application은 정상적으로 동작했다고 말할 수 있을까.

이런 일을 방지하기 위해서 AP인 스토리지를 사용하는 로직에는 데이터를 체크하는 복잡한 로직이 들어간다. 복잡한 로직은 높은 버그 가능성과 같은 의미이다. application 로직이 복잡해져서 버그가 발생했고 이를 고치기 위해 서비스를 종료했다면 이 application의 가용성은 떨어지게 된다. 게다가 버그로 인해 잘못된 응답을 준 경우는 오히려 처리하기 쉽다. 만약 버그로 인해 잘못된 데이터가 스토리지에 저장됐다면 이는 잡기도 어려울뿐더러, 고치기도 어렵다.

APCP보다 latency와 throughput이 떨어지기 때문에 성능이 필요한 application을 위해서는 AP인 스토리지를 선택해야 주장하는 사람들도 있다. 하지만 성능도 가용성과 마찬가지로 스토리지의 성능은 스토리지를 사용하는 application의 성능과는 별개다. AP인 스토리지를 사용하여 CP인 스토리지를 사용할 때보다 높은 성능을 보여준다는 것을 주장하기 위해서는 데이터 스토리지의 처리 시간이 application 처리 시간의 대부분을 차지한다는 것을 증명해야 한다. 여기서 측정하는 시간은 단순히 데이터 스토리지에 요청한 operation의 처리속도가 아니라, 네트워크 전송 속도를 제외한 데이터 스토리지 내부의 소요 시간이어야 한다.

설령 스토리지가 처리 속도에 충분한 영향을 준다고 하더라도 AP인 데이터 스토리지를 선택하기 전에 중요한 것이 처리 속도인지, 스토리지를 바꾸지 않으면 처리 속도를 올릴 방법이 없는지 고민해봐야 한다.

2017-12-13

Raft - consistency

 Raft는 모든 결정을 leader가 맡아서 한다. 따라서 term이 변경되기 전에는 leader의 결정을 따르면 된다. 문제는 leader에 문제가 생기거나 네트워크 파티션으로 인해 leader가 변경되고 다음 term으로 진행된 경우다.

 Consistency를 위해 가장 이상적인 것은 모든 노드가 하나의 leader만 따르도록 하는 것이다. 하지만 이는 사실상 불가능하다. 이게 가능하면 애초에 합의에 도달한 것이다. 그래서 Raft에서는 특정 시간에 2개 이상의 리더가 존재할 수 있다. 단, state를 변경시킬 수 있는 리더는 1개 밖에 있을 수 없다. 이 두 말은 별 차이 없는 것 같지만, 이 차이가 분산 환경에서 구현 가능한 시스템이 되도록 만들어준다.

 Raft에서는 leader에 커밋 된 로그만이 state를 변경시킨다. Leader가 커밋하기 위해서는 네트워크에 참여하는 노드 과반의 동의가 필요하다. 새 leader가 선출되면 과거의 leader는 절반 이상의 지지를 받지 못한다. 모든 요청에 요청하는 노드의 term이 담겨있고, 요청받은 쪽은 자신의 term보다 작은 term인 노드가 보낸 요청은 모두 거절한다. 새 leader가 선출됐다는 것은 이미 절반 이상의 노드가 다음 term으로 넘어갔다는 것이고 과거의 leader를 지지하는 노드는 절반이 되지 않기 때문에 과거 leader는 더 이상 상태를 변경시킬 수 없다. 따라서 같은 시간에 두 개의 노드가 상태를 변경시키는 것은 불가능하다.

 물론 leader가 아닌 노드들이 가지고 있는 상태는 consistent 하지 않다. 새 RequestVote를 받기 전에 과거의 leader가 보낸 AppendEntries 메시지를 받고 자신의 상태를 변경시킬 수 있기 때문이다. 하지만 네트워크의 상태는 리더에 커밋 된 로그를 기준으로 만들어지기 때문에 각 노드의 inconsitecy는 클라이언트가 보는 네트워크 상태에 영향을 주지 않는다.

 그렇다면 leader에 커밋 된 로그를 가지지 않은 노드가 leader가 되면 어떻게 될까? 다행히도 raft에서는 이런 일이 발생하지 않는다. RequestVote 메시지에는 candidate이 가지는 최신 로그의 index와 그 index가 생성된 term이 저장돼 있다. 이 index가 자신이 알고 있는 로그의 최신 index보다 작으면 이 RequestVote 요청은 거절된다. 즉, 가장 최신 로그를 가지고 있는 노드만 리더가 될 수 있고, 이 최신 로그에는 최소한 leader에 커밋 된 로그를 포함된다.

 그렇다면 leader를 포함하여 커밋 된 로그를 가진 노드가 모두 죽으면 어떻게 될까? Leader가 어떤 로그를 커밋했다는 것은 최소 과반의 노드가 이 로그를 가지고 있다는 것이다. 이 노드가 모두 죽었다는 것은 네트워크에 남은 노드가 절반이 되지 않는다는 것이고 새 candidate을 지지하는 노드가 절반 이하가 되기 때문에 새 leader를 선출할 수 없고 이후로 네트워크는 상태를 변경할 수 없다. 만약 네트워크에 과반의 노드가 살아있다고 하면, 이는 비둘기집 원리에 따라 커밋 된 로그를 가지고 있는 노드가 최소한 한 개 존재한다는 것이고, 이 노드가 leader가 되면서 consistency를 유지된다.