Consistency Model

Shared Memory Consistency Model

이 모델들은 distributed system에서 공유 메모리상의 데이터 접근에 대한 rule을 제공한다. 

우리는 distributed system에서 프로그램을 병렬적으로 아주 빠르게 실행하길 원한다. 만약 두 물리 코어가 공유 메모리상에서 임의의 데이터를 공유하면 read/write를 위한 synchronization이 필요하다. Synchronization을 통해 공유 데이터의 consistency를 유지할 수 있다. 이 때, consistency를 유지한다는것은 공유 데이터를 read할 때, 최근 과거에 쓰여진 최신 데이터를 읽는다는것을 의미한다.

Consistency는 보장 정도에 따라 두가지로 나뉜다.

• Strict Consistency
• Non-Strict Consistency

Strict Consistency

Strict consistency는 distributed system에서 항상 과거에 쓰여진 최신 데이터를 읽을 수 있다는것이다. 더 정확히는 time $t$에 write operation을 실행했으면, $t+\delta$에 실행된 read operation은 $t$때 write된 data를 읽을 수 있다. 이는 아래 두 가지 조건중에 한가지를 만족해야 가능하다.

• Distributed system에 global clock이 존재하고 코어들은 global clock에 완벽하게 동기화되어야 한다.

  • Global clock이 있으면 현재 사이클에 write operation을 하고 다음 사이클에 read operation을 하면 된다. (operation의 직렬화)
  • 단, write operation은 read operation 이전에 완료되어야 한다.
• Write가 즉시(빛의속도로) 이루어져야 한다.
  • $\delta$가 $0_+$에 수렴할 때, write operation에 걸리는 시간이 0인경우 strict consistency가 가능하다.

근데 위 두가지 모두 물리적으로 불가능하다. 먼저 global clock부터 생각해보자. 각 distributed nodes들은 global clock에 접근하여 시간을 동기화 시켜야 한다. 하지만 그 접근 시간 조차 deterministic하지 않으므로 완벽한 시간 동기화는 불가능하다. 두번째로 write operation을 빛의속도로 수행하는것 또한 물리적인 제약때문에 불가능하다.

그러므로 strict consistency는 이론적인 consistency model이다. 그리고 만약 혹시라도 외계인을 납치하여 완벽하게 동기화가능한 global clock을 구현한다고 해도 한 클럭이 network 속도에 병목되는 엄청나게 느린 performance를 보여줄 것이다.

Non-Strict Consistency

Non-strict consistency model은 세부분류로 sequential consistency와 relaxed consistency로 나누어진다.

Sequential Consistency

Sequential consistency는 strict consistency보다 한단계 완화된 consistency이다. Strict consistency는 빛의 속도같은 write operation나 완벽히 동기화되는 global clock을 요구했으나 sequential consistency는 이를 요구하지 않는다. 하지만 아래와 같은 물리적으로 가능한 요구사항이 있다.

• Ordering 유지
• Atomic read/write operation

사실 제일 상식적인 consistency이다. 공유 데이터를 접근할 때, single operation queue가 있어 그 큐에는 write operation과 read operation들이 쌓여있다. 그리고 이 operation들은 in-order로 처리되야 한다. 그리고 operation이 수행되고 있으면 single operation queue에 들어있는 다른 operation들은 대기해야 한다.

이는 strict consistency보다는 빠른 성능을 보인다. (Network 속도에 클럭이 병목될 정도는 아니다.) 하지만 operation들이 sequential하게 수행되어야 하므로 성능이 만족할정도로 나오지 않는다. (previous operation이 완료 될 때까지 기다려야 하므로 느리다.)

[http://rsim.cs.uiuc.edu/~sadve/JavaWorkshop00/talk.pdf]

위는 sequential consistency를 설명한 그림이다. 접근은 ordering되어 있으며 각 operation은 atomic하다.

Relaxed Consistency

우리는 squential consistency가 주는 성능에 만족할 수 없다. 그래서 우리는 sequential consistency의 요구사항인 ordering 또는 atomic write operation을 깨고자 한다.

Ordering을 깨는방법은 다음과 같다.

1. Write to Read: Previous write가 끝나기 전 read이 수행될 수 있다.
2. Write to Write: Previous write가 끝나기 전 write이 수행될 수 있다.
3. Read to Read or Write: Previous read가 끝나기 전 read 또는 write를 수행할 수 있다.

그리고 Write atomicity를 깨는 방법은 다음과 같다.

1. Read others' write data early

일단 ordering을 깨는 방법을 설명하고자 한다.

Relaxed Write to Read

a = 3;
write 2 to a;
read a;

이 경우 strict consistency에서는 read a 에서의 리턴 값은 위에서 쓰여진 2가 리턴되어야 한다. 이 때 프로그래머는 두가지의 의도가 있을 수 있다.

1. read a시, a에 있는 value를 바로 읽는다. (전 write 무시)
2. read a시, 바로 전에 write 된 value를 읽는다. (전 write 무시x)

1의 경우는 단순히 asynchronous read하면 된다.

하지만 2의 경우는 read를 미리 수행하나 read a; operation을 리턴(완료)하지 않고 write가 완료되길 기다린다. 만약 write 후에도 미리 읽어둔 a value가 변하지 않았다면 바로 리턴하고 아니라면 read a;를 재수행하여 올바른 값을 리턴한다. 이러한 구조를 optimistic execution¹이라 한다.

이를 통해 optimistic execution의 예측이 맞다면 속도 향상이 있을 것이고 없다면 sequential consistency와 같은 성능을 낼 것이다. 그러므로 최소한 sequential consistency보다 성능이 좋다.

Relaxed Write to Write

이는 Relaxed Write to Read보다 간단하다. 만약 다른 두 주소에 대해 각각 write를 하면 전에 실행된 write를 기다릴 필요 없다. 다음은 그에 대한 예이다.

write 2 to a;
write 3 to b;

a와 b는 서로 주소가 다르므로 두 write operation은 동시에 실행하거나 심지어 반대 순서로 실행할수도 있다. 이는 write를 하나만 처리할때보다 memory bandwidth utilization을 높일 수 있고, 이에 따라 sequential consistency보다 속도를 높일 수 있다.

Relaxed Read to Read or Write

사실 read to read는 설명할게 없다. 다른 메모리 주소를 읽는다면 Relaxed write to write 같이 memory bandwidth utilization을 높일 수 있다.

그리고 read miss가 난 경우, read가 오래 걸리므로 non-blocking cache의 경우 뒤에 있는 operation인 read or write를 다른 메모리 주소에 대해 먼저 실행할 수 있다.

이 또한 sequential consistency보다 성능을 높여준다.

Read others' write data early

위 방법은 write될 data를 write 전에 read 할 수 있게 해준다. 방법은 아래 그림과 같다. 내용이 쉬우므로 설명은 생략한다.

[https://en.wikipedia.org/wiki/Classic_RISC_pipeline]

Summary

우리는 strict consistency와 non-strict consistency를 보았다. Non-strict consistency는 strict consistency를 물리적으로 불가능한 조건들을 완화시켜 sequential consistency를 만들어내었다. 하지만 이는 ordering과 operation의 atomicity를 보장해야 하므로 성능상 느리다. 이 때문에 ordering과 atomicity를 깨서 성능상의 향상을 얻으려는 시도가 있었는데 이는 relaxaed consistency이다. 이 때문에 메모리 성능은 다음과 같이 비교할 수 있다.

Strict consistency (불가능) < Sequential consistency < Relaxed consistency

---

1. Optimistic하게 예측하여 execution한 뒤, 나중에 결과값을 비교하여 다르다면 재실행, 같다면 바로 리턴한다. ↩