[분산 시스템] Consistency and Replication

replication : 복제 

복제를 하는 이유 : 시스템의 reliability를 증가시키기 위해서, availability, 퍼포먼스를 향상하기 위해

퍼포먼스 : 많은 수와 데이터의 퍼포먼스를 향상시켜줄수 있고 지리적으로 멀리 있어도 빠르게 서비스를 줄 수 있다.

 

단점 : relpica들의 consistency문제점을 해결해야 한다. 서버가 하나일 때는 따질 필요가 없다. 그러나 동일한 데이터가 여러 개 있을 경우에 업데이트를 하면 문제가 발생한다. 이렇게 서로 다른 값을 갖게 되는 문제를 일관성 문제라고 한다. 그래서 업데이트를 하면 모든 replica들에게도 업데이트를 한 것을 알려줘야 한다.

 

퍼포먼스 향상을 위해서 replication과 caching을 주로 사용한다.

caching은 클라이언트 딴에서 복제를 하는 것이고 replication은 서버입장에서 복제를 하는 것으로 서버노드들 사이에 미리 데이터를 복사해 두는 것이다. 그래서 consistency를 지키기 위해서 모든 replica를 최신으로 유지해야 한다. 이것 자체가 cost가 되어서 scalability 문제가 발생할 수 있다. 

 

일관성이라는 것이 항상 100퍼센트 유지해야 할까? 그럴 필요는 없다. 

Tight consistency는 타이트하게 일관성을 유지하는 경우이다. 즉, 업데이트가 되면 모든 replica에게 알려줘야 한다. 그러나 매번 업데이트할 때마다 cost가 커져서 퍼포먼스가 떨어질 수가 있다. 이러한 관계를 consistency와 performance사이의 trade off라고 한다. 

 

consistency의 제약사항을 완화시키는 건 어떨까? 즉, 항상 타이트하게 일관성을 유지해야 할까? 그래서 일관성 모델이 여러 가지로 나누어진다. 

 

데이터 중심 일관성 모델 : 데이터들이 저장되는 공간이 물리적으로 분리되어 있다.

inconsistencies(불일치) 3가지

1. numerical value  = replica들 사이의 데이터 값이 다른 경우

2. replica들 사이의 staleness차이가 있다. staleness가 클수록 데이터가 오래된 것을 의미한다.(신선도가 낮다)

3. 업데이트를 시리즈로 연속으로 하는데 여러 번 수행되는 이 업데이트의 순서가 다르게 되면 불일치가 발생할 수 있다.

 

이런 다양한 측면 중에서 어떠한 것을 허용할 수 있을까?

Numerical deviations : replica가 가지고 있는 데이터의 값자체가 서로 다른 경우 100퍼센트 지키지 않아도 되는 경우가 있다., 완화시킬 수 있는 방법 ex) 한쪽 주식의 값이 10달러였다면 다른 서버의 주식값은 10.02달러가 되는 정도는 허용을 하겠다. 즉, 이처럼 하나 두 개 정도가 다른 건 허용하겠다는 뜻

 

staleness deviations : replica가 오래 전의 정보를 제공하더라도 문제가 없을 경우에 최신정보를 유지할필요가 없다. ex) 날씨 정보를 측정하는것, 오래전의 날씨 정보를 제공하더라도 문제가 되지 않을 수 있다. 

 

Ordering deviations : 업데이트된 순서가 어느 정도 차이가 있더라도 허용될 수 있는 것이 있다. 앞에 두 측면보다 ordering이 좀 더 다루기 어렵다. 왜냐하면 데이턱 업데이트된 순서를 다 체크해야 하기 때문이다. 

 

W는 write 오퍼레이션이고 i는 프로세스를 의미하고 x는 데이터아이템 x에 대해서 오퍼레이션을 수행한 것이고 그 결과값이 a가 됐다는 의미이다. 즉, i번째 프로세스가 write오퍼레이션을 x라는 데이터에 수행해서 업데이트된 값이 a이다.R도 동일하다. 위의 그림은 딜레이때문에 업데이트된 사항을 늦게 확인하고 데이터를 읽을 수가 있다. 그러나 이런 사항은 딜레이때문이니까 받아들여준다.

 

 

 

완화해서 나온 것

sequential consistency : 실제 순서는 다르더라도 모든 replica들의 오퍼레이션의 순서만 맞다면 이 relpica들은 sequential consistency 하다고 할 수 있다. 가장 최신의 데이터가 아니더라도 순서만 맞으면 sequential consistency 하다고 할 수 있다.

(a)번은 b의 업데이트 내용보다 a의 내용이 나중에 도착해서 발생하는 경우이다. 원래 a다음b가 나와야하는데 p3가 b다음 a를 읽은거처럼 p4도 b다음 a를 읽은거처럼 순서가 같기 떄문에 sequential consistency라고 할 수 있따.

(b)는 sequential consistency 할 수 없다. 

 

여기서 좀 더 약하게 완화시킨 것이 causal consistency이다. 모든 오퍼레이션에서 순서를 맞출 필요는 없고 원인과 결과관계가 분명한 오퍼레이션들의 결과가 같다면 허용한다는 것이다. 

예를 들어서 이벤트 b가 발생된 원인이 a 때문이라면 a와 b사이에는 원인과 결과관계이기 때문에 순서를 맞춰주기만 하면 다른 애들은 순서를 맞출 필요는 없다. 

 

a와 b의 값이 원인과 결과 관계가 아니고 b와 c도 원인결과 관계가 없다. ,그래서 이둘은 순서가 달라도 상관이 없다.P3,P4를 보면 이 두개의 순서가 달라도 상관없다. 이것은 sequential 하지않지만 causal consistency하다고 할 수 있다.

P1이 a를 업데이트하고 P2가 읽었다 그리고 P2가 b라고 업데이트를 했다. 여기서 W1(x)a와 W2(x)b는 potentially한 관게가 있다. 왜냐하면 P2가 읽은 결과에 의해서 W(x)b가 업데이트가 되었기 때문이다. 그래서 다음에 read할때는 동일한 순서로 가야만 한다. P3와 P4의 결과의 순서가 서로 다르기 때문에 이것은 causal consistency하지 못한 예시이다. 그래서 a를 먼저읽으면 다른애도 a를 먼저 읽어야됨, a가 먼저 나오고 b가 업데이트 됐는데 b가 먼저읽어지는건 상관없고 b를 먼저읽었으면 다른애들도 동일한 순서로 읽어야한다.

이 예시는 causal consistency한 예시이냐? yes 왜냐하면 P3과P4의 순서는 다르지만 concurrent한 경우에는 순서가 달라도 상관하지 않기 때문이다. sequential consistency 하냐? No 왜냐하면 causal이든 아니든 read 오퍼레이션 두번의 수행의 순서가 동일해야하기 때문이다.

 

 

Client-centric consistency model

업데이트가 발생할 때 그 데이터가 쉽게 resolved 되거나 대부분의 오퍼레이션이 reading data인 경우에 지정할 수 있다.

 

여러 프로세스들이 같은 아이템에 대해서 동시에 업데이트 오퍼레이션을 수행하는 이런 concurrent 한 오퍼레이션이 자주 벌어지지 않는  분산 데이터 스토어들이 실제로 예시로 많이 나온다. 

 

ex) 많은 데이터베이스 시스템을 보면 업데이트 오퍼레이션을 많이 수행하지 않고 대부분 read오퍼레이션이 주를 이룬다. 

ex) DNS에서 데이터를 업데이트할 때 아무나 하는 게 아니라 특정권한을 갖은 프로세스만 업데이트를 할 수 있다. 그렇기 때문에 하나의 데이터에 여러 프로세스들이 동시에 액세스 하는 충돌문제는 거의 없다.

ex) WWW에서는 write충돌 문제가 거의 발생하지 않는다. 왜냐하면 제한적인 프로세스들만 업데이트를 할 수 있기 때문에 여러프로세스들이 동시에 업데이트해서 충돌문제가 발생하는 경우는 없다.

 

이러한 특성을 갖는 데이터 스토어에서는 어느 정도의 inconsistency를 허용할 수 있을까?

데이터가 업데이트 됐을 때 업데이트된 사실을 알려야 하는데 이 업데이트되는 사항이 느리게 가더라도 허락할 수 있는 이런 consistency 한 모델을 적용할 수도 있다. 오래 전의 낡은 데이터를 액세스 하더라도 허용이 되는 모델을 eventual consistency모델이라고 한다.

 

eventual consistency :즉, 업데이트가 되는 사항을 느리게 전달하는 것을 허용하겠다는 것이다. 그래서 어느 순간에는 서로 같은 데이터에서 다른 값을 가지더라도 허용하겠다는 것이다. 시간이 지나고 나면 다시 업데이트 메시지가 전달이 되어 concurrent 하게 된다는 것을 의미한다. 

 

이런 것을 지원하는 분산 데이터 스토어를 구현하기가 쉽다. 그러나 약화된 consistency모델이기 때문에 문제가 발생하는 경우가 있다. 같은 프로세스가 짧은 시간에 서로 다른 replica를 액세스 하는 경우에 문제가 발생할 수 있다. 

protable한 애가 다른위치로 이동을 해서 가까운곳에서 데이터를 엑세스하려고했는데 그 두개의 값이 다르게 나올경우에 문제가 생길수있다. 같은 프로세스가 엑세스하는 데이터에 대해서는 consistency를 자켜줘야하는데 깨질수가 있다. 그래서 같은 프로세스가 같은 데이터를 엑세스할 떄는 서로 데이터의 값이 같아야하는 조건이 지켜줘야한다.

그래서 이렇게 타이트한 consistency모델보다 요구사항을 완화시킨 cosistency 모델도 적용할 수 있다. 왜냐하면 타이트하게 가져가면 퍼포먼스와 확장성을 지키기 어렵기 때문에 퍼포먼스 향상을 위해서.

 

client-centric consistency 모델이 data-centric consistency모델과 다른 점은 consistency모델을 적용할 대상이 되는 것은 하나의 single client이다. 즉, 하나의 클라이언트가가 서로 다른 복제된 데이터 스토어들 사이를 이동해서 액세스 할 때 consistency를 유지하는데 초점을 둔 모델이다.   

 

client-centric consistency model : Monotonic reads

Monotonic read consistency : 두 개의 복제된 스토어가 있는데 하나의 스토어에서 read 오퍼레이션을 하고 복제된 다른 스토어로 이동해서도 read 오퍼레이션이 가능한 상태

 

monotonic-read consistency를 제공한다는 것

1. 만약 하나의 프로세스가 데이터 값을 read 하고 난 후 이동을 해서 다시 read작업을 수행하면 그 읽은 데이터 값은 이전에 읽었던 같은 값이거나 최신값이다.

2. 만약 어떤 프로세스가 t라는 시간에 x라고 하는 데이터 아이템의 값을 봤다면 그 값은 x라는 데이터의 이전값을 볼 일이 없다.

ex) distributed e-mail database (데이터 스토리지가 여러 개 있는데 그 안에 저 정 된 데이터는 이메일)

각 mail box는 복사되어 있다. email이 갱신이 되면 다른 연결된 스토리지들로 lazy fasion(적극적으로 알려주는 것이 아니고 업데이트된 채로 있다가 액세스 할 일이 있을 때, 즉 필요할 때 전파하는 방식)으로 전파가 된다. 만약 사용자가 SF에서 자신의 이메일을 읽었을 때 read작업만 수행했을 경우에 mail box에는 다른 영향을 끼치지 않는다. 그런데 그 사용자가 NY으로 가서 그 mail box를 다시 열었는데 SF에서 읽은 내용의 데이터가 적어도 같은 내용은 있고 업데이트된 데이터가 있다면 이것은 monotonic-read consistency를 보장한다고 한다.

 

만약 SF에서 메일을 읽을 때 새로운 메일이 왔는데 이 내용이 SF데이터 스토리지에 저장이 되었다. 그런데 이 데이터가 NY에 전파되지 않았다면 사용자가 NY에서 데이터 스토리지를 읽어버리면 monotonic read consistency조건에 맞지 않는다.(오래된 데이터를 액세스 했기 때문)

 

WS(x1;x2)는 1번값에 있는 write 오퍼레이션들이 2번스토리지에 있는 x의 값에도 적용이 되었다라는 뜻. 그래서 사용자가 2번 스토리지를 읽을때 데이터가 업데이트되지 않았다면 1번 스토리지 값을 불러온다. 즉 monotonic read를 만족한다.

여기서는 1번 스토리지에서 업데이트가 됐던 내용들이 2번 스토리지에는 반영이 되지않았다. 즉, 2번과 1번 스토리지는 별개의 write오퍼레이션을 한다.

 

client-centric consistency model : Monotonic write

Monotonic write

하나의 데이터 스토리지에서 write를 하고 업데이트를 한다음 다른 데이터 스토리지에 가서 write작업을 할떄 업데이트된 내용으로 write를 할 수 있으면 monotonic write가 만족된다. write 오퍼레이션을 complete한다는 것은 데이터아이템 x에 대해서 write오퍼레이션을 수행을 하면 이전에 write했던 사항이 반영되고 난 후에 write 오퍼레이션을 하면 complete했다라고 의미한다.

data-centric FIFO consistency와 비교해 보자.

write 오퍼레이션을 할 때 이전에 반영된 내용들이 업데이트가 된 후에 write오퍼레이션을 해야 한다라는 내용은 둘이 유사하다. 그러나 data-centric에서는 single process가 아니라 모든 클라이언트에서 적용된다는 차이점이 있다. 

ex) software library

소프트웨어 라이브러리가 업데이트된다면 이 라이브러리 이전에 수행됐던 업데이트가 이미 반영이 된 후에 업데이트가 된다는 것을 보장한다.(monotonic write를 보장)

WS(x1)이 아니라 WS(x1;x2)로 바꿀것(monotonic write를 만족)

(monotonic write가 만족하지 않는 경우) 두번째 작업을하기전에 업데이트된 내용이 반영이 되고난 다음에 오퍼레이션을 했어야한다.

client-centric consistency model : read your write

Read-our-write consistency : 내가 write 오퍼레이션을 수행하고 수행한 내용을 내가 나중에 읽는 경우에 client-centric consistency를 의미. 즉, 앞에서 하나의 프로세스가 write를 하고 어느 다른 스토리지에서 데이터를 읽는다 하더라도 write 한 내용이 반영이 되고 read를 하는 것이 보장되는 것. 그래서 client-centric은 data-centric보다 제약사항이 좀 더 크다. 

 

read-your-write consistency가 보장되지 않는 데이터 스토에 에서의 예시

웹페이지가 업데이트가 됐을 때 사용자가 업데이트되기 전의 화면을 본다면 read-your-write consistency가 만족되지 않는다. 사용자가 웹 브라우저로 볼 때 이전에 캐쉬했었던 웹페이지로 볼때 이런 경우가 있다. 

또 다른 예제로 updating passwd가 있다. 사용자가 패스워드를 바꿨는데 업데이트되는 시간이 걸려서 반영이 되지 않았을 때 로그인을 한다면 액세스를 하지 못하는 경우가 발생할 수 있다. 그래서 업데이트된 내용을 반영을 하고 난 뒤에 읽을 수 있어야 한다.

이전 업데이트의 내용이 반영된 예시

반영되지못한 예시

 

client-centric consistency model : Write follow reads

Write-follow-reads consistency : read를 하고 다른 스토리지에서 write를 가능하게 하는 것

이전에 x에 대해서 프로세스가 read오퍼레이션을 수행하고 그 프로세스가 x에대해서 write오퍼레이션을 수행했을 경우 읽은 갑이나 추가적으로 업데이트가 된 내용들을 x값을 기반으로 write를 보장할 수 있으면 Write-follow-reads이다. 

 

 

이것도 문제가 발생하는 예시가 있다.

ex) A network newsgroup

read오퍼레이션을 수행하고 그 데이터에 대해서 write 하려고 할 때 업데이트된 사항이 아니라 old 한 데이터에 업데이트를 한다면 writr follow read가 만족되지 않는다. 

만족되는 예시

만족되지않는 예시

---

Repliaction management : Replica-server placement

optimizstion problem : 최적의 해결책을 찾는 부분은 복잡할 수가 있다. 

 

Qiu et al.(2001) : 클라이언트와 서버들 사이의 거리값이 가장 가까운 애로 지정하자. 주로 latency 와 bandewidth로 거리를 잰다. 다음 replica가 필요하다면 나머지 애들끼리 거리를 비교하자.

 

Radoslavov et al.(2001) : 라우터들의 topology를 replica서버를 정하는 기준이 되겠다. 어떤 기준이냐면 다양한 라우터들 중(autonomous system)에서 가장 큰 애를 replica 서버로 지정한다. 네트워크 인터페이스가 많은 노드들이라는 뜻은 패킷이 움직이는 공간이 많은 지역을 의미한다. 나머지는 그다음 큰애로 지정한다. 

 

이러한 알고리즘들은  computationally expensive 하다는 문제가 있다,

 

Szymaniak et al.(2006) : 노드들 몇 개를 모아서 클러스터로 구성하고 그걸 모아서 k개의 거대한 클러스트를 모아서 region단위로 쪼갠다. 여기서 region은 cell이라는 것으로 표현해서 전체공간을 partition 하는 작업을 수행한다. 그래서 쪼개진 cells들 중에서 k개의 가장 dense 한 cell을 선택해서 그곳에 replica서버를 둔다.

 

여기서 cell의 크기를 너무 크게 하면 같은셀 안에 여려 개의 클러스트가 포함될 수 있기 때문에 하나의 replica서버가 커버할 클러스트가 많아져서 서버 부하가 걸릴 수 있다. cell이 너무 작으면 cell하나가 클러스트하나를 관리하지 못할 수 있다. 그래서 하나의 클러스트가 쪼개져서 여러 cell에 걸쳐서 나눠지는 문제가 생길 수 있다.

 

셀이 너무 작으면 하나의 클러스트가 쪼개져서 두개의 셀에 걸쳐져서 잡히게된다. 셀이 너무 크면 하나의 셀안에 두개의 클러스트가 들어간다.

replica를 3가지로 나타낼 수 있다. permanent replica는 처음부터 replication되는 relpica를 의미한다. server-initiated replica는 permanent이외에 다이나믹하게 그때그떄 필요에 따라서 추가적으로 relpication되는 replica를 의미한다. client-initiated replica는 클라이언트가 필요에의해서 repliaction되는 replica를 의미한다.

Permanent replica : 여러 개의 서버노드들 사이에 최초에 replication된 애들(즉, data store가 운영되는 동안 계속적으로 유지가되는 replica를 의미한다) ex) a web site : replication서버를 여러개 두는 것 다른 방법은 mirroring(웹사이트가 여러 데이터가 복제되는데 차이점은 지리적으로 흩어져있어도 된다)

 

Server-initiated replica : 다이내믹하게 복제가 되는 replica를 의미(퍼포먼스를 향상하기 위해), 데이터 스토어 쪽에서 복제가 일어남 ex) a web server in new york : 뉴욕에서 먼 지점에서 갑자기 요청메시지가 왔을경우 퍼포먼스가 떨어질수있다. 이런경우에 요청메세지가 많이 온 곳에 replica를 두자. 그래서 요구가 많은 쪽에 일시적으로 두자. ex) web hositing service : 특정 서버에 요청이 모이면 그쪽에 replica를 둬서 퍼포먼스를 향상한다.

다이내믹한 replication접근법

Rabinovich et al.(1999) : 특정서버에 부하가 걸릴 경우 복제를 해서 다른 서버로 옮기던지 해야 하는데 이 서버는 요구가 많은 서버 근처에 복사를 한다. 

 

Client-initiated replica : 클라이언트가 복제했을 때(cache)를 의미한다. 

 

위의 replica들을 관리할 때 중요한 점

데이터가 업데이트가 됐다면 다른 replica들에게 전해줘서 consistency 하게 유지해야 한다. 전해주는 방식이 3가지가 있다.

1. 업데이트가 됐다는 사실만 보내는 방법

2. 업데이트된 데이터도 같이 보내는 방법

3. 어떤 방식으로 업데이트가 되어야 한다는 동작을 보내는 방법(통지만 하기에 네트워크 banwidth가 적다는 장점이 있다)

 

1번째 방법인 propagating a notifiaction방법은 업데이트는 자주 되지만 데이터를 읽는 요청이 적을 경우 유용하다.

2번째 방법이 유용한 경우는 read-to-write ration가 상대적으로 높을 경우 유용하다.(업데이트 대비 읽는 비율이 더 많은 경우)

3번째 방법은 업데이트하는 데이터의 양이 클 경우에 유용하다. 네트워크 비용은 줄어들 수 있으나 로컬에서 직접 업데이트를 해야 한다. 

 

업데이트하는 내용을 뿌려주기 위해서 pull과 push로 나눌 수 있다.

pull : 업데이트된 데이터를 필요로 하는 쪽에서 업데이트된 데이터를 가지고 오는 방식

다른 용어로 client-based protocol이라고 한다.(서버로부터 업데이트된 내용을 가져오기에)

캐시 쪽에서 업데이트된 데이터를 서버로부터 가져올 때 자주 사용한다. read-to-update(업데이트 대비 액세스요청이 적은 경우) 효율적이다. 클라이언트가 요청했는데 데이터가 업데이트되어야 하는 예전데이터라면 그 데이터를 업데이트할 때까지 기다려야 하는 일이 발생한다.

 

push :  업데이트된 쪽에서 업데이트가 됐다는 사실을 다른 replica로 보내는 방식

다른 용어로 server-based protocol이라고 한다.(업데이트된 것을 서버가 알려주기에)

consistency정도가 높을 경우에 자주 사용한다. 만약 read-to-update(업데이트 대비 액세스하는 요청이 많은 경우) 효율적이다

 

표로정리한것

pull과 push를 섞는 방법도 나왔다.

Gray and Cheriton(1989)

push를 업데이트하는데 lease기간(정해진시간) 동안에는 업데이트된 내용을 알려주는데 lease시간이 만료가 되면 더이상 push를 하지않는다. 그래서 그 후엔 polling방식으로 클라이언트가 데이터를 필요로할떄 업데이트가 됐는지 확인을 하고 업데이트된 데이터를 가져온다. 또다른 방식으로 lease타임이 만료가되면 다시 갱신할 수도 있다.

 

확장된 연구

Duvvuri et al.(2003)

위의 방법과 동일한데 lease타임을 다이내믹하게 늘렸다가 줄일 수 있다. 그럼 무슨 기준으로 늘렸다가 줄이지?

1. age-based : 오랫동안 업데이트되지 않았던 old 한 데이터는 lease타임을 줄이고 young 한 데이터는 lease타임을 늘린다.

2 서버의 오버헤드가 얼마나 큰지에 따른 lease타임조절 : push자체가 서버에 부담이 가는 거라 부하가 많이 걸리는 서버는 lease타임을 줄여서 죽게 만들고 pulling모드로 만들어서 서버 부하를 줄이자.

 

업데이트된 내용을 뿌려주는 방법도 유니캐스트와 멀티캐스트 두 개로 나눌 수 있다. 

push는 갱신된 데이터를 여러 애들한테 알려줘야 해서 one-to-many방식으로 가는 게 효율적이라 멀티캐스트로 보내자.

pulling은 데이터를 필요로 하는 쪽에서 먼저 물어보고 가져오는 거기 때문에 유니캐스트로 보내자.