복제 이유 (신뢰성/성능) 시스템의 신뢰성을 높이기 위해 데이터가 복제됩니다. (백업)
성능을위한 복제 (병렬처리) - 숫자의 크기 조정 - 지리적 영역의 확장 (거리가 먼 경우 근거리에 복제해서 해시처럼 사용) 경고 -실적 향상 -복제 유지 비용 증가 대역폭
단, 갱신이나 업데이트가 되면 일관성의 문제가 된다.
○ Replication(복제): 분산시스템에서 성능(Performance)과 신뢰성(Reliability)을 확보하는 방법
- 성능: 병렬처리, Caching, 지리적 한계 탈피
- 신뢰성: 자료의 Backup
○ 복제의 문제점
- 데이터의Consistency(일관성)이깨질수있음
- 시스템 운영/관리비용의 증가
○ Consistency Model(일관성 유지 모델)
- Data-Centric(데이터 중심)
- Client-Centric(클라이언트 중심) - MONOTONIC READ /
Data-Centric Consistency Models
○ 클라이언트에 상관없이 Data 일관성 유지
○ 각 Process의 Local Copy로 존재하는 분산 된 Data-Store(복제)를 여러 Process가 하나 의 Data-Store처럼 사용
○ Models
- Continuous Consistency
- Sequential Consistency
- Causal Consistency
- Grouping Operations
- Eventual consistency
Continuous Consistency (연속적으로 일관성유지) ★평가기준중요
○ 복제 간 불일치 정도를 최소화하여야 함
○ 복제 간 불일치 정도 평가
- Numerical Deviation: 값 차이
- Order Deviation: 마지막 Commit 이후 수행한 Operation의차이
- Staleness Deviation: 마지막 Update 이후 시간 차이
○ 원리
Figure 7-2
x/y는 0,0으로 시작함
A (2,5) B에대한 실제 값
B (6,3) A에 대한 실제 값
- Conit (Consistency Unit): 일관성을 유지해야하는 기본 평가 단위를 뜻함 , 변수(x,y)를포함하는 일관성 평가 단위
- 복제 A의 Vector <5, B> 연산은 이미 Commit 됨 (Rollback 불가)
• Vector <x, y>: x는 Vector Clock, y는 복제의 이름
- 그외 복제 A와 B의 연산은 Commit되지않음
- Vector Clock 설명
• A의 Vector Clock:(15, 5) (A의 현재 Clock, B의Update를 Commit한 시점의 A의 Clock)
• B의 Vector Clock:(0, 11) (A의Update를 Commit한 시점의 B의 Clock, B의 현재 Clock)
- Order Deviation: 마지막 Commit 이후 Update 횟수
- Numerical Deviation
• A의 Deviation: (Commit 후 B의 Operation 횟수, Commit 후 차이가 있는 B의 Conit 중 가장 큰 값)
• B의 Deviation: (Commit 후 A의 Operation 횟수, Commit 후 차이가 있는 A의 Conit 중 가장 큰 값)
※ 예제에서는 Staleness Deviation은 언급없음
○ Conit 단위에 따른 Consistency
- Update 시 여러 개의 Data Item을 Group 으로 할 경우 일정 Threshold 이상이 되면 다른 복제에게 Update를 전파하여야 함
- Data Item 개별로 Update를 수행 할 경우 전파가 약간 지연되어도 무방
업데이트 단위에 대한 내용
(a) 크게 하는 경우 : 두 가지 업데이트가 업데이트 전파를 유도합니다.
(b) 개별적으로 하는 경우: 뒤죽박죽 / 업데이트 전파가 필요하지 않습니다 (아직).
Consistency유형: Sequential (순차적) / Causal (인과관계)
Sequential Consistency
W= write / R = Read
P1: W(x)a 실제 값
P2: R(x)NIL x공간의 a를 읽기하였으나, 전파되기전이어서 NIL을 반환함
R(x): 읽음
Data를 읽고 쓰는데 순차적으로 일관성을 유 지하면 됨
○ Write 순차 - P1이 데이터 공간 x에 a값을 기록하고 그 결과가 전파되어야 다른 Process P2가 데이 터 공간 x에서 a값을 읽어 올 수 잇음
- 전파되기 전 P2가 데이터 공간 x에서 a값을 읽어 올려고 하면 NIL 반환함
○ Read 순차 - 다른 Process가 Read를 시작한 순서대로 Read를 유지하면 됨
- Read 순서가 하나라도 깨지면 Sequential 깨짐
- 데이터 공간 x에 P1이 a를 Write하고, 그 뒤 P2가b를Write함(x의상태b)
- 이후 P3가 먼저 데이터 공간 x에 b를 Read 하고, 이후 a를 Read(x의 상태 a)
- 그러나 이후 P4가 데이터 공간 x에 a를 Read하고, b를 Read하면일관성이위배 됨 ⇒ x의 상태는 b가 되어버림 (올바른 결과는 P4가 b를 Read하고, 그 뒤a를Read해야함)
○ 서로 다른 Process의 서로 다른 Data를 읽고 처리하는 경우 순서에 따라 다양한 조합 결과 가 나옴 ⇒ SequentialConsistency의 중요성
데이터 저장소는 다음과 같은 경우 순차적으로 일관됩니다.
모든 실행 결과는 데이터 저장소의 모든 프로세스가 (읽기 및 쓰기) 작업을 수행하는 경우와 같습니다.
어떤 순차적 순서대로 실행되었고 ...
각각의 개별 프로세스의 작업이 나타납니다 ...
-이 순서대로
-그 프로그램에 의해 지정된 순서대로.
(a)의 경우 순서를 잘 지켰다.
(b)의 경우 3번과 4번이 다르게 읽혔다.
P3은 b다음 a가 읽혔으나 P4에서는 a가 먼저 읽히고 b가 그 다음 읽힌다 그런경우 Sequential Consistency가 없다고 할 수 있다.
P3의 R(a) 이후에 P4의 R(a)가 있어야한다.
▲ (4) (5) 처럼 다양한조합이 가능하다
Causal Consistency
○ Update의인과관계가 성립하는지여부를 검사
○ Data를 Update 한 순서가 다른 Process에 게도 정상적으로 전파되면 정상
○ Concurrent 한 Update가 발생하는 경우 인 과관계가 어긋나도 무방
Causal Consistency (2) a를 통해 b,c 생성 (인과관계)
1) P1이 데이터 공간 x에 a를 Write 함 (x의 Write 전개 null → a)
2) P2와 P3 그리고 P4는 동시에 데이터 공간 x에서 a를 Read함. (x의 write 전개 a → a)
3) P2가 x에 b를 Write함 (x의 write 전개 a → b)
4) P1이 데이터 공간 x에 c를 Write함 (x의 Write 전개 a→c)
5) P3가 데이터 공간 X에서 c를 Read하고 동시에 P4도 X에서 b를 Read 함 (X의 Read 전개 P3: a→c, P4: a→b; Write 전개 상태와 일치하므로 Causal 유 지)
6) P3가 데이터 공간 X에서 b를 Read하고 동시에 P4도 X에서 c를 Read 함 (X의 전개 P3: c→b, P4: b→c; 현재 상태가 이전 상태 a에서 왔고, b와 c는 Write 전개에 대한 인과관계가 없으므로 Causal 유지)
※ 만약 단계 5)에서 a가 아닌 b 또는 c를 먼 저 Read 했다면 Causal Consistency 깨짐
Causal Consistency (4) concurrent 관계 - 동시에 생성되는 것에 대해서는 순서가 상관 없다.
Grouping Operations (그룹단위로 자원관리)
○ 공유자원의 배타적 사용에 관한 논의
○ Group 단위로 자원관리
○ Grouping: 어떤 자원을 Acquire 시점부터 Release 시점까지 다른 Process가 사용할 수 없도록 Lock 하는 것
자원을 사용할 때 Lock을 얻어야하고 자원을 다 사용하면 Release 하여야 한다. 독점적으로 베타적으로 공유자원을 쓴다. 일종의 크리티컬섹션으로 볼 수 있다.
*CS(Crtical Section): 다른 프로세스가 침범 할 수 없는 자원 점유시간
Figure 7-10
P1
Acq(Lx) - Rel(Lx) 까지 CS
Acq(Ly) - Rel(Ly) 까지 CS
P2 는 Acq(Lx) - Rel(Lx) 까지 CS 가 끝나면서 바로 Acq(Lx) 사용 R(y)NIL 은 y에대한 사용권한이 없으므로 NIL
↓ 재설명
1) P1이 자원 x에 대해 Lock을 요청(Lx)
2) P1이 자원 x에 대해 Lx를 획득하고, a를 Write
3) P1이 자원 y에 대해 Lock을 요청(Ly)
4) P1이 자원 y에 대해 Ly를 획득하고, b를 Write
5) 자원 x에 대한 사용이 끝난 P1이 Lock(Lx) 을 Release, 이후 P2가 자원 x에 대해 Lock을 요청(Lx)
6) 자원 y에 대한 사용이 끝난 P1이 Lock(Ly) 을 Release, 이후 P3가 자원 y에 대해 Lock을 요청(Ly), P2는 x에서 a를 Read
7) P3가 자원 y에서 b를 Read
8) P2가 자원 y를 Read 시도하였으나 Lock이 없으므로 NIL을 Return 받음
Eventual Consistency
○ 어떤 Event의 수행 후 마지막에 데이터 일관 성을 갖도록 함
○ Update가 가끔 일어나는 상황에 유용 - Wide-area Network 상에서 각 Replica에 게 Update 전파가 느림
○ 느린 Update 전파로 인해 이동이 잦은 Mobile 환경에서 Consistency가 깨지는 문제 있음 → Client-Centric 으로 해결
Client Centeric
MODEL:
Monotonic reads
Monotonic writes
read your writes
write follow reads
Monotonic Reads
○ Monotonic Read의 특징
- Read 상황에서 한결같은 일관성 제공
- 동일 Input이 전파되어 Client 별로 Read 시 최종 결과에 반영되어야 함 (최종값을 읽어야한다)
Monotonic Reads (2)
1) L1이 x1을 Write-Set
2) L2가 x1을 Read 하여 x2로 Write-Set (x1이 전파되어 x2가 나옴)
3) L1이 x1을 Read
4) L2가 x2를 Read
※ 만약 L2가 x1을 Read 하지 않고 바로 x2 로 Write-Set 하였다면 L1과 L2 사이에 동일 Input이 아니므로 Monotonic Read 가 아님
Monotonic Reads (3)
이는 Monotonic Reads가 아니다. 이유는 x2가 x1이 전파가 안된 x2이기 때문이다.
Monotonic Writes
○ 특징
- 동일 Input이 전파되어 다른 Client의 Write 최종 결과에 반영되어야 함
Monotonic Writes (2)
1) L1이 x1을 Write
2) L2가 x1을 Write-set
3) L2가 x1이 Write-set 한 상태에서 x2를 Write
※ 만약 L2가 x1를 Write-Set 하지 않고, x2를 Write 했다면 L1과 L2 사이에 동일 Input 이없으므로Monotonic Write가아님
write set이 없으므로 반영되지 않는 상황이기에 독립적/무관한 상황이다. 따라서 Monotonic Writes가 아니다.
Read Your Writes (Write한 내용을 Read 한다.)
○ 특징 - 특정 Client에 대해 Write 결과가 반영된 Read 수행
1) L1이 x1을 Write
2) L2가 x1을 Read하고 x2를 Write-Set
3) L2가 x2를 Read
※ 만약 L2가 L1의 x1 값과 상관없이 x2를 Write하고 Read 한다면 L1의 Write 결과 가 반영되지 않으므로 Read-Your-Writes 가 아님
Read Your Writes (2)
L1이 W(x1) 전파를 하여 L2에서 Write Set (x1;x2)
이렇게 반영된 x2를 Read한다.
Read Your Writes (3)
x1과 x2의 관계는 무관하기때문에 Read your write가 아니다.
Write Follow Reads (내용을 Read 한 다음 Write 한다.)
○ 특징 - 특정 Client가 Read 한 이후 다른 Client가 Write 수행
1) L1이 x1을 Write-Set
2) L2가 x1을 Read 하여 x2를 Write-set
3) L1이 x1을 Read
4) L2가 x2를 Write
※ 만약 단계 2)에서 L2가 단독으로 x2를 Write-Set 한다면, 이후 L1이 Read 한 x1과 L2가 Write 한 x2와는 관계가 없으 므로 Write-Follow-Reads가 아님
Write Follow Reads (2)
L2의 Write Set은 x1을 읽고 Set 된다.
이후 L1이 x1을 Read한다
그리고 L2가 x2를 Write한다. 즉 x2는 x1이 반영된 것이다.
Write Follow Reads (3)
전파가 전혀이루어지지 않으니 Write follow Reads 가 아니다.
-------consistency 의 2가지 방식 설명 끝---------
-------Replica 시작---------
Replica-Server Placement
○ 분산시스템 환경에서 영역 간 데이터 분포가 균등하지 않다면 서버의 위치 선정이 중요
○ 원리 - 일정한 크기의 Cell로 영역 분할
- 분포가 너무 적지도 않고, 너무 크지도 않은 적당한 Cell에 복제 서버 유지
● = Node를 의미
* 너무 적음(Too Small): 일정 수 이상 모여 있는 데이터 간 거리가 가까움
* 너무 큼(Too Large): 일정 수 이상 모여있 는 데이터 간 거리가 멀거나 분할됨
* 적당(Just Right): 일정 수 이상 모여있는 데이터 간 거리가 적지도, 크지도 않음
Content Replication and Placement
○ Replica 생성 유형
- Permanent (처음부터 복사본수를 미리 정함)
• 처음부터 일정 숫자를 복제
• 시스템최초형성시관리자가복제수량결정
- Server-Initiated (서버가 복사)
- Client-Initiated (클라이언트가 복사((예) 캐시를 사용하는 것))
Server-Initiated Replicas (파일마다 Access Count(액세스횟수) 를 저장)
○ Server-Initiated의 특징
- File-Access를 Count 하여 Threshold를 정함
- Threshold의 종류
• Deletion(S, F): 이하면 삭제 (카운트하여 딜리션 이하면 삭제)
• Replication(S, F): 이상이면 복제 (카운트하여 레플리케이션 이상이면 복제)
*S: Server, F: File - Deletion과 Replication의 관계
○ Client-Initiated의 활용
- Cache를 사용
- 최초사용 시 Client내Cache에File을저장
- File의 Life Time 이내 다시 Access 시도할 경우 Cache 내 File을 사용
Q가 일정 Access 값이 높아지면 P에 복사한다. 이도 저도 아닌 경우엔 Q를 P3로 이동하는 것이 효율적이다.
↑ File Access - 복사 - 이준이상이면 복제
------------------
↕ Ref 이동 - 이도저도 아닌경우 이동
------------------
↓ Del 삭제 기준 이하면 삭제
CDN(Content Distribution Network) : Access 시간을 단축시키기 위해 주로 사용
- 여러 위치에 분산된 데이터를 요청할 때 실 행을 분산
- 접근시간을 단축하기 위해 많이 사용
- State vs. Operations(Update 전파 방식)
- Pull vs. Push Protocol
State versus Operations
업데이트될 수 있는 가능성
1. 업데이트 통지 (업데이트 메시지 전파)
2. 복제에서 다른 복제로 데이터 전송 (업데이트 데이터 전파)
3. 다른 복제에서 업데이트 Operation 을 전파 (업데이트 방법 전파)
Pull versus Push Protocols
○ Pull Protocol
- 서버에 Update Data를 요청하여 수신 (업데이트를 상대에게 알려주고 가져옴)
- 서버의 상태를 유지하지는 않음
- Push보다 오래걸림 (Fetch Update 시간 필요)
○ Push Protocol
- 서버로부터 Update Data를 받음
- 서버 상태, 복제 목록, Data 저장을 위한 Cache 필요
- 즉시 실행 가능
Remote-Write Protocols (primary based)
○ Primary Backup(Replica) 서버 존재
○ Synchronous 방식 - Write 시간이 오래 걸리며, 그동안 Client는 Block 됨
○ Read는 Client에서 가까운 Backup 서버에서 수행
○ Write
1) Client가 가장 가까운 Backup에 Write
2) Write를 전달 받은 Backup은 Primary에 전파
3) Primary는 나머지 Backup 들에 Update 전파
4) 각 Backup은 Update 수행 후 Primary에게 완료응답보냄
5) Primary는 최초 Write를 전달받은 Backup 에게 완료 응답 보냄
6) 최초 Write를 전달받은 Backup은 Client 에게 완료 응답 보냄
Remote방식이다. Primary까지 찾아 가야 하기 때문이다.
Syncronus 방식: 시간이 걸림
Blocking방식
Primary 서버가 업데이트 되어야 백업서버에도 복사가 가능 (업데이트요청)
Local-Write Protocols
○ Client로부터 Write를 요청받은 Backup이 Primary가 됨
○ Remote-Write보다 Write 시 Client의 Block 시간이 짧음
○ Read 절차는 Remote-Write와 동일
○ Write
1) Client가 가장 가까운 Backup에 Write
2) Write 요청받은 Backup은 이전 Primary를 대체하는 새로운Primary가됨, Write 수행
3) Primary는Client에게Write완료응답보냄
4) Primary는 다른 Backup들에 Update 전파
5) 각 Backup은 Update 완료 후 Primary에 게 완료 응답 보냄
[추가정리]
클라이언트가 요청하면 그 서버가 새로운 Primary 서버로 지정
지정되면 기존서버 내용을 새 서버로 보낸다. 업데이트되면 되엇다고 전부에게 알려준다. W4업데이트 요청->w5 로 ACK 알려줌 끝.
Unblocking 방식
Quorum-Based Protocols (Replicated Protocols)
○ Quorum(정족수) 특징
- 일정 정족수(과반수) 이상을 만족할 경우 Update 수행
- 중복이 허용됨; Read Peer와 Write Peer가 중복될 수 있음
○ 기본조건
- Update 시 NW + NR > N이고, NW > N/2 를 항상 만족하여야 함
- NW: Write 정족수 (NW는 N전체노드수의 과반수를 만족해야만 한다.)
- NR: Read 정족수
- N: 전체 노드 수
점선--- Write
실선 ㅡ Read
(a)(b)(c) 슬라이드 모든 노드수는 12개이나 Nr+Nw = 13이다.
(a)에서 C의 경우 Write에 속해있으므로 최신 업데이트를 받을 수 있다.
(b)는 Nw가 6이어서 12의 과반수 6=6이므로 중복이 아닌 분리가되어 베타적인 그룹이 생길 수 있다. 따라서 업데이트가 안될 수 있다.
(c)는 12개 모두 write에 이므로 Read값이 항상 최신값을 받을 수 있다.
'컴퓨터공학 > 분산시스템' 카테고리의 다른 글
| 분산시스템의 결함 허용 (Fault Tolerance) (1) | 2023.12.20 |
|---|---|
| 분산시스템의 동기화(synchronization) (0) | 2023.12.20 |
| 분산시스템의 네이밍 (1) | 2023.12.20 |
| 분산시스템의 커뮤니케이션 (1) | 2023.12.20 |
| 분산시스템에서의 프로세스 (1) | 2023.12.20 |
