[분산시스템][공유메모리] Sequential consistency 구현 방법

아래의 분산시스템의 네가지 환경에서 Sequential consistency 구현 방법론

1. NRNMB 

2. NRMB

3. RMB

4. RNMB

1. NRNMB (복제, 마이그레이션 없는 환경)
- DSM 블럭을 복제 또는 마이그레이션 하지 않기 때문에 특정 DSM 블럭이 한 host에만 존재하는 방법.
- 원본 블럭이 한 호스트에만 존재하므로 sequentail consistency가 이행되는데 문제가 없다.

단점
- 블럭에 대한 접근 요청이 블럭을 소유한 호스트에게만 집중되므로 트래픽이 몰릴 수 있다.

블록 위치 찾기 (여러 호스트가 DSM 블럭 위치 찾기)
- block-id = node-id 이기 때문에 node-id 단위로 블럭을 찾을 수 있다.

2. NRMB (복제 없음, 마이그레이션 있는 환경)
- NRNMB 와 동일하게 한 블럭만 존재. Sequential Consistency 보장.
- 다른 호스트에서 블록을 요청하면 블록이 요청한 호스트로 이동.

장점
- 한 호스트가 집중적으로 접근하는 블록이 있을 경우 cost가 많이 줄어든다. 블록이 자주 요청하는 호스트로 마이그레이션이 가능하기 때문이다.

단점
- 반면에 여러 호스트에서 동일한 블록을 요청하면 스레싱이 발생할 수 있다. 블록이 네트워크를 통해 여러 호스트를 이주다니면 Fault가 발생할 수 있기 때문이다.
- 반면에 여러 호스트에서 같은 블럭을 요청할 경우 스레싱이 발생할 수 있다.

블록 위치 찾기 (여러 호스트가 DSM 블럭 위치 찾기)
a. Broadcasting
- OBT에서 필요한 블록에 맞는 호스트 목록을 찾을 수 없으면 전체 노드에게 Broadcasting으로 전달한다.
*OBT(Owned Block Table): host가 갖고 있는 매핑 테이블 (block-id, node-id 매핑 정보)
- 블록을 소유한 호스트는 자신이 블록을 갖고 있다고 응답한다.
- 네트워크 트래픽 때문에 Latency가 발생하며 Scalability 문제가 있다. 

b. Centralized-server
- 호스트 A는 자신이 원하는 블록이 로컬 메모리에서 찾지 못하여서 서버에게 요청
- 서버는 BT (Block Table) 를 갖고 있으며 호스트A는 서버에게 필요한 블록을 요청한다. 
- 서버는 요청받은 블록을 소유한 호스트B에게 호스트A 의 요청 전달
- 호스트B는 A에게 블록을 전달하고 중앙 서버는 BT를 A -> B로 갱신한다.
- 중앙서버의 보편적인 단점인 병행성, reliability, scalability 등이 떨어지게 된다.

c. Fixed distributed-server
- BT를 갖고 있는 서버를 여러대 두는 방식
- 호스트가 블록이 필요할 때 Block Manager에게 요청한다.
- Block Manager는 요청 받은 블록을 갖고 있는 서버에게 전달

d. Dynamic distributed-server
- Block Manager, 서버를 두지 않는 방법으로 모든 호스트가 BT를 갖고 있다.
- 호스트 A가 B에게 블록을 요청했을때 B는 블록을 갖고 있으면 A에게 블록을 전달한다.
- B가 갖고 있지 않고 C에게 전달 했을 경우 C에게 호스트 A가 블록을 요청했다고 알린다.
- C는 A에게 블록을 전송한다.

3. RMB (복제, 마이그레이션 있는 환경)
- 블록을 복제하게 되면 블록간의 consistency를 유지해야하는 이슈가 발생한다.  Read는 데이터 변경이 없기 때문에 문제가 되지는 않지만, Write는 모든 복사된 블록에게 적용되야 한다. 

Sequential consistency를 보장하는 write 규약
a. Write-invalidate (주로 사용)
- 호스트 A가 필요한 블록을 가지고 온다.
- 해당 블록을 write 할 때 다른 호스트에 복제된 블록들에게 invalidate 메세지를 보낸다. 
- 결국 호스트 A가 갖고 있는 싱글 블록만 write하기 때문에 Sequential consistency가 보장된다.

b. Write-update
- 호스트 A가 자신의 블록을 write를 완료하고 다른 호스트에 있는 복사본들을 모두 write한다.
- 여러호스트가 동시에 같은 블록을 write 할 수 있어  Sequential consistency 가 보장되지 않는다. 
- Global Sequencer를 사용하여 블록의 write에 대한 순서를 지정하여 Sequential consistency 를 제공 할 수 있다.

블록 위치 찾기 with Write-invalidate (여러 호스트가 DSM 블럭 위치 찾기)
a. Broadcasting
Read 동작
- 호스트 A는 자신에게 블록이 없을 경우 Broadcast한다.
- 블록을 갖고 있는 호스트B는 자신의 OBT의 copy-set 필드에 A를 추가하고 전달한다. (A에게 카피해줬다는 의미)
Write 동작
- 호스트 A는 Broadcast를 통해 호스트 B로 부터 블록과 copy-set 필드를 전달받는다.
- 호스트 A는 copy-set에 있는 호스트 목록에게 해당 블록에 대한 invalidate 메세지를 전달한다.
- 호스트 A는 write 완료 후 해당 블록의 새로운 주인이 되며 copy-set 필드를 Null로 변경한다.

b. Centralized-server
Read 동작
- 호스트 A는 서버에게 블록을 찾아달라고 요청
- 서버는 해당 블록의 copy-set 필드에 호스트 A를 추가하고 어느 호스트가 갖고 있는지 리턴
- 호스트 A는 리턴 받은 호스트에게 블록을 달라고 요청
- 호스트 A는 블록을 받고 read
Write 동작
- 호스트 A는 서버에게 블록을 찾아달라고 요청
- 서버는 copy-set과 블록을 소유한 호스트 정보를 호스트 A에게 전달과 동시에 자신이 갖고 있는 BT의 copy-set과 소유자를 호스트 A로 변경
- 호스트A는 블록의 소유자에게 요청 후에 블록을 리턴 받는다.
- 호스트A는 블록을 write 하기 전에 전달 받은 copy-set에 있는 소유자들에게 invalidate 메세지를 전달.

c. Fixed distributed-server
- Block manager의 BT에 Copy-set 필드가 추가되며 동작은 NRMB와 동일하다.

d. Dynamic distributed-server
- 각 호스트의 BT에 Copy-set 필드가 추가되며 동작은 NRMB와 동일하다.

4. RNMB
- Write-update 방식이 사용될 수 있다.
- Global sequencer를 사용해야 Sequential consistency가 보장된다.

블록 위치 찾기 (여러 호스트가 DSM 블럭 위치 찾기)
- BT에 Sequence number 필드가 추가 되며 블록 위치 찾는 방법은 위에 나온 방식과 동일하다.