분산시스템(Distributed System) - 6 - 2(Replica Consistency) Linearizability

여러 노드들로부터 concurrent 하게 데이터를 이용하고 업데이트를 할 때 어떻게 노드가 up-to-date인 상태를 보는 것을 보장할 수 있을까?

Linearizability 란 여러 노드에서 동시에 발생한 여러 사건 들을 하나의 시간축에 넣는 것?이라고 이해를 했다. 

 

 아래 그림의 상태는 linearizable하지 않은 상태이다.

클라이언트 A가 노드 A에 t1이란 시간에 set을 했다. 그리고 직후에 클라이언트 B와 C가 데이터를 읽으려고 시도하는데 노드 A를 포함하여 요청을 보낸 클라이언트 2는 클라이언트A가 수정한 값을 볼 수 있지만, 더 늦게 요청을 보낸 클라이언트 C는 받지 못하는 상황이다.

 

이것이 linearizable 하다고 하려면 client2가 변경된 새로운 값인 v2를 받은 이후에 read를 한 cient3은 v1을 받았어야 한다. 이것은 write가 완료되었냐의 여부와는 다르다. 만약 client 2와 client 3이 비슷하게 시작해서 비슷하게 끝났다면 상관이 없다. 이 둘은 결과가 나오기 전까지는 누가 먼저 끝났는지 알 수 없는 상태이고 둘 다 v0가 나왔다면 둘다 write가 끝나기 전에 발생한 이벤트이고 하나가 v1하나가 v0라면 둘의 순서가 정해지게 된다 그리고 v1이 나온 이벤트보다 나중에 read가 있다면 그것은 무조건 v1 또는 새롭게 업데이트된 값이 있다면 그 값이 나와야 한다.

 

위와 같은 상황에서 앞에서 공부한 read-repair을 해준다고 생각해보자. 

아래의 이미지처럼 될 것이다. 이를 ABD 알고리즘이라고 한다. Attiya, Bar-Noy 그리고 Dolev가 만들었다고 한다.

 

 

이렇게 되면 어떤 하나의 노드가 업데이트를 읽고 그것이 완전히 커밋되지 않았다고 해도 바로 set을 보내기 때문에 이것보다 나중에 읽는 노드는 과반수의 노드에서 읽어오고 이중에 하나는 업데이트가 되었을 것이다.

 

이것이 되기 전이라면 나중의 읽은 노드가 먼저 일어난 이벤트라고 볼 수 있을 거 같다. 하지만 이럴 때 blind write를 한다 최신 값인지 아닌지 모른 채로 write를 하게 되는데 이런 경우 여러 노드가 동시에 set을 하게 되면 가장 나중에 도착한 값이 덮어쓰게 될 것이고 그것이 가장 최신 값이라는 보장은 없다. 

 

이것을 보강한 것이 CAS (compare and swap)이라 한다. 값을 비교하고 맞다면 write를 하고 아니라면 그대로 두는 것이다. 예제를 보면 간단하게 이해될 것이다.

문제는 아래의 그림에서 잘못된 애는 뭔가?이다.

 

 

1. 우선 첫 번째 노드 C와 B가 읽었는데 1이고 같은 시간대에 노드 A가 x = 1 노드 D가 x = 0을 한다. 이것들로 보았을 때 노드 D가 가장 빨랐고 그 후에 노드 A 그리고 노드 B, C이다 누가 먼저인지는 바뀔 수도 있다.
2. 노드 C에서 2를 읽었다 그 동시간대에 노드 B가 x=1이면 2로 바꾼다 CAS에서 true가 나와서 write를 성공하였다는 것을 알 수 있다. 
3. 노드 D는 실패했기 때문에 읽기만 했다. 그리고 노드 A와 C를 보면 노드 C가 2라면 x =4를 하고 노드 A는 4를 읽었다. 그럼 순서가 정해진다.
4.  이렇게 되면 노드 B에서 2를 읽은 것이 틀리다는 것을 알 수 있는데 노드 A에서 읽은 시간이 끝난 후에 노드 B에서 읽기 시작하기 때문에 happen before의 관계이고 둘의 순서는 명확하다 할 수 있다 그렇기 때문에 4를 읽어야 하지만 2를 읽었기 때문에 틀렸다.

linearizability가 무엇인지 linearizable 하다는 것이 뭔지를 알아보았다. 정리하면서도 뭔가 정확하지 않은 것이 아직 완전히 이해하기에는 조금 부족한 거 같다. 나중에 좀 더 많은걸 알게되었을떄 이걸 보게 되면 그때는 좀더 나은 정리를 할 수 있었으면 좋겠다.

 

포스트의 모든 이미지는

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