Linearizability

1
2
3
4
5

  클라이언트 A: ----W(x)---R(x)----
  클라이언트 B: ---------R(x)------W(x)----
  클라이언트 C: --------------R(x)-------R(x)--
  
  선형화된 순서: --R(x)--W(x)--R(x)--R(x)--W(x)--R(x)--

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

시스템 구성: 리더(L)와 두 개의 팔로워(F1, F2)로 구성된 MySQL 클러스터

시나리오:
1. 초기 상태: 키 K의 값은 "value1"
2. 클라이언트 C1이 10:00:01에 키 K 읽기 요청 → "value1" 반환
3. 클라이언트 C2가 10:00:02에 키 K 업데이트 요청: K = "value2"
   - 요청이 리더 L로 라우팅
   - L이 변경사항 적용 및 로그 기록
   - L이 F1, F2에 동기식으로 복제 요청
   - F1, F2가 변경사항 적용 및 확인 응답
   - 모든 팔로워의 확인 후 L이 C2에 성공 응답
4. 클라이언트 C3가 10:00:03에 키 K 읽기 요청
   - 리더 또는 팔로워 중 어디에서 읽어도 "value2" 반환
5. 리더 장애 시:
   - 새 리더 선출 전까지 쓰기 불가
   - 읽기는 가장 최신 상태를 가진 노드에서 처리

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

시스템 구성: 5개의 노드로 구성된 키-값 저장소

시나리오 (키 X의 값 업데이트):
1. 클라이언트가 키 X 값을 "new_value"로 업데이트 요청
2. 제안자 P1이 제안 번호 n=5로 준비 요청 전송:
   - 메시지: "PREPARE n=5"
3. 수락자들이 자신이 수락한 최대 제안 번호가 5보다 작으면 응답:
   - "PROMISE n=5, 이전에 수락한 값 없음"
4. P1이 과반수(3개 이상) 응답 받으면 수락 요청 전송:
   - 메시지: "ACCEPT n=5, value='new_value'"
5. 수락자들이 더 큰 제안 번호를 약속하지 않았다면 제안 수락:
   - "ACCEPTED n=5, value='new_value'"
6. 과반수가 수락하면 값 "new_value"가 결정됨
7. 학습자들이 결정된 값을 적용하고 클라이언트에 응답
8. 이후 모든 읽기 요청은 "new_value" 반환

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

시스템 구성: 5개 노드(S1-S5)로 구성된 etcd 클러스터

시나리오:
1. 초기 상태: S1이 리더, 임기(term) 3
2. 클라이언트가 키 K의 값을 "val1"로 설정 요청
3. 리더 S1이 로그 엔트리 생성: {term: 3, index: 10, command: "SET K='val1'"}
4. S1이 팔로워에게 AppendEntries RPC 전송:
   - 로그 엔트리 및 이전 로그 인덱스/임기 포함
5. 팔로워들이 로그 일관성 확인 후 엔트리 추가 및 응답
6. 과반수(최소 3개 노드) 확인 시 S1이 커밋 인덱스 업데이트: commitIndex = 10
7. S1이 상태 머신에 명령 적용: K = "val1"
8. S1이 클라이언트에 성공 응답
9. 다른 노드들도 커밋 인덱스 업데이트 시 상태 머신에 명령 적용
10. 이후 어떤 노드에 읽기 요청이 가더라도 K = "val1" 반환

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

시스템 구성: 5개 노드(N=5), W=3, R=3인 분산 키-값 저장소

시나리오:
1. 초기 상태: 모든 노드에 키 X의 값이 "old"로 저장됨
2. 클라이언트 C1이 키 X의 값을 "new"로 업데이트 요청
   - 코디네이터가 버전 타임스탬프 v2 생성
   - 모든 노드에 쓰기 요청 전송: {key: X, value: "new", version: v2}
   - 노드 N1, N2, N3에서 성공 응답(W=3 충족)
   - 코디네이터가 C1에 성공 응답
   - 장애로 N4, N5는 아직 업데이트되지 않음: {key: X, value: "old", version: v1}
3. 클라이언트 C2가 키 X 읽기 요청
   - 코디네이터가 모든 노드에 읽기 요청
   - 최소 R=3개 노드 응답 필요
   - 응답: N1, N2, N3: {X, "new", v2}, N4, N5: {X, "old", v1}
   - 코디네이터가 가장 높은 버전의 값 선택: "new"
   - C2에 "new" 반환
4. W+R > N 보장으로 항상 최신 업데이트가 읽히게 됨

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

시스템 구성: 3개 노드(A, B, C)로 구성된 분산 데이터베이스

시나리오:
1. 초기 벡터 클럭: A[1,0,0], B[0,1,0], C[0,0,1]
2. 객체 O의 초기값: "val0"
3. 노드 A가 O 업데이트: "val0" → "val1"
   - A의 벡터 클럭 증가: [2,0,0]
   - 변경사항 + 벡터 클럭 기록: {O: "val1", VC: [2,0,0]}
4. A의 업데이트가 B와 C로 전파:
   - B의 벡터 클럭 업데이트: max([2,0,0], [0,1,0]) = [2,1,0]
   - C의 벡터 클럭 업데이트: max([2,0,0], [0,0,1]) = [2,0,1]
5. 클라이언트가 C에 읽기 요청:
   - C가 O = "val1", VC = [2,0,1] 반환
6. 클라이언트가 B에 O 업데이트: "val1" → "val2"
   - B의 벡터 클럭 증가: [2,2,0]
   - 변경사항 + 벡터 클럭 기록: {O: "val2", VC: [2,2,0]}
7. 또 다른 클라이언트가 동시에 C에 O 업데이트: "val1" → "val3"
   - C의 벡터 클럭 증가: [2,0,2]
   - 변경사항 + 벡터 클럭 기록: {O: "val3", VC: [2,0,2]}
8. 복제 과정에서 충돌 감지:
   - [2,2,0]과 [2,0,2]는 서로 비교불가능(각각 다른 차원에서 증가)
   - 애플리케이션 정의 충돌 해결 정책 적용 필요

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

시스템 구성: 분산 SQL 데이터베이스, Thomas's Write Rule 적용

시나리오:
1. 데이터 항목 D의 초기값: "init", 타임스탬프 TS(D) = 100
2. 트랜잭션 T1이 타임스탬프 TS(T1) = 200을 받고 D 읽기
3. 트랜잭션 T2가 타임스탬프 TS(T2) = 300을 받고 D 읽기
4. T1이 D 업데이트: "init" → "value1"
   - TS(T1) = 200 > TS(D) = 100 이므로 업데이트 성공
   - D = "value1", TS(D) = 200으로 업데이트
5. T2가 D 업데이트: "init" → "value2"
   - TS(T2) = 300 > TS(D) = 200 이므로 업데이트 성공
   - D = "value2", TS(D) = 300으로 업데이트
6. 트랜잭션 T3가 타임스탬프 TS(T3) = 250을 받고 D 업데이트 시도: "old" → "value3"
   - TS(T3) = 250 < TS(D) = 300 이므로 업데이트 무시(Thomas's Write Rule)
   - D = "value2", TS(D) = 300 유지
7. 읽기 요청은 항상 최신 타임스탬프의 값 반환

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

시스템 구성: 여러 애플리케이션 서버와 중앙 락 관리자, 공유 저장소

시나리오:
1. 클라이언트 C1이 객체 O1 업데이트 요청
2. 애플리케이션 서버 S1이 락 관리자에게 O1에 대한 쓰기 락 요청
   - 락 요청: {object: O1, type: WRITE, requestor: S1, timestamp: t1}
3. 락 관리자가 O1에 대한 쓰기 락이 없음을 확인하고 S1에 락 부여
   - 락 상태 업데이트: {O1: {owner: S1, type: WRITE, granted_at: t1}}
4. S1이 O1 업데이트 수행 및 저장소에 반영
5. 동시에 클라이언트 C2가 O1 읽기 요청
6. 서버 S2가 락 관리자에게 O1에 대한 읽기 락 요청
   - 락 요청: {object: O1, type: READ, requestor: S2, timestamp: t2}
7. 락 관리자가 O1에 대한 쓰기 락이 있음을 확인하고 S2의 요청을 대기 큐에 추가
8. S1이 작업 완료 후 락 해제 요청
9. 락 관리자가 O1의 락 해제 및 대기 중인 S2의 읽기 락 부여
10. S2가 최신 상태의 O1 읽기 수행 및 클라이언트 응답

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

시스템 구성: 엄격한 2PL을 구현한 분산 SQL 데이터베이스

시나리오:
1. 트랜잭션 T1 시작:
   ```sql
   BEGIN;
   -- 확장 단계 시작
   SELECT * FROM accounts WHERE id = 1; -- 계정 1에 대한 S-lock 획득
   UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- S-lock을 X-lock으로 업그레이드
   SELECT * FROM accounts WHERE id = 2; -- 계정 2에 대한 S-lock 획득
   UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- S-lock을 X-lock으로 업그레이드
   -- 이제 T1은 계정 1과 2에 대한 X-lock을 보유
   COMMIT;
   -- 커밋 시 모든 락 해제 (수축 단계)
	```

2. 동시에 트랜잭션 T2가 같은 계정에 접근 시도:
    
    ```sql
    BEGIN;SELECT * FROM accounts WHERE id = 2; -- T1이 X-lock을 보유하고 있어 차단됨-- T1이 완료될 때까지 대기
    ```
    
3. T1이 커밋되고 락을 해제한 후에야 T2가 진행 가능
4. T2는 T1의 모든 변경사항이 반영된 상태에서 데이터 접근

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

시스템 구성: Google Spanner와 같은 글로벌 분산 데이터베이스

시나리오:

1. 트랜잭션 T1이 10:00:00에 시작:
    
    ```sql
    BEGIN;UPDATE accounts SET balance = 950 WHERE id = 'A'; -- 원래 1000COMMIT; -- 10:00:01에 커밋 성공
    ```
    
2. 트랜잭션 T2가 10:00:02에 시작:
    
    ```sql
    BEGIN;SELECT balance FROM accounts WHERE id = 'A'; -- 950 반환UPDATE accounts SET balance = balance - 200 WHERE id = 'A'; -- 950 -> 750COMMIT; -- 10:00:03에 커밋 성공
    ```
    
3. 트랜잭션 T3가 T1과 T2 사이인 10:00:01.5에 시작했지만 네트워크 지연으로 늦게 처리됨:
    
    ```sql
    BEGIN;SELECT balance FROM accounts WHERE id = 'A'; -- T1 이후, T2 이전이므로 950 반환COMMIT; -- 10:00:04에 커밋 (T2 이후)
    ```
    
4. T3는 실제 시작 시간이 T1 이후, T2 이전이므로 T1의 변경(950)을 보고 T2의 변경(750)은 보지 않음
5. 글로벌 타임스탬프 기반으로 시스템이 각 트랜잭션의 실제 시간 순서 보존

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

시스템 구성: OCC를 구현한 분산 객체 저장소

시나리오:

1. 트랜잭션 T1 시작(타임스탬프 TS1 = 100):
    - 읽기 집합 RS1 = {}, 쓰기 집합 WS1 = {}
2. T1이 객체 A(버전 10)와 B(버전 20) 읽기:
    - RS1 = {(A, 10), (B, 20)}, WS1 = {}
3. T1이, A의 값을 v1으로, B의 값을 v2로 업데이트:
    - RS1 = {(A, 10), (B, 20)}, WS1 = {(A, v1), (B, v2)}
4. 동시에 트랜잭션 T2(타임스탬프 TS2 = 101) 시작:
    - T2가 B(버전 20) 읽기
    - RS2 = {(B, 20)}, WS2 = {}
    - T2가 B 업데이트: B = v3
    - RS2 = {(B, 20)}, WS2 = {(B, v3)}
    - T2가 먼저 커밋 시도 및 유효성 검사 통과
    - B의 버전이 21로 업데이트
5. T1이 커밋 시도:
    - 유효성 검사: RS1의 객체들이 여전히 같은 버전인지 확인
    - B의 버전이 20에서 21로 변경됨 → 검증 실패
    - T1 중단 및 재시도 또는 사용자에게 충돌 알림

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

시스템 구성: 5개 노드(S1-S5)로 구성된 Multi-Paxos 기반 키-값 저장소

시나리오:

1. 초기 상태: S1이 안정적인 리더로 선출됨
2. 클라이언트가 키 K를 v1으로 설정 요청
3. 리더 S1이 로그 인덱스 n에 명령 추가 제안:
    - "PROPOSE: log[n] = set(K, v1)"
4. S1이 과반수(최소 3개 노드)로부터 수락 확인 받음
5. S1이 로그 항목 n을 커밋하고 상태 머신에 적용: K = v1
6. 리더가 클라이언트에 성공 응답
7. 다른 클라이언트가 K를 v2로 업데이트 요청
8. 리더가 로그 인덱스 n+1에 새 명령 추가 및 복제 과정 반복
9. 리더 S1 장애 시:
    - 새 리더(예: S3) 선출
    - S3이 커밋되지 않은 로그 항목에 대한 합의 재개
    - 합의 완료 후 새 명령 처리 재개

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

시스템 구성: CRDT 기반 분산 데이터 저장소 + 토큰 관리자

시나리오:

1. 초기 상태: 카운터 C = 0 (모든 노드에서 동일)
2. 클라이언트 A가 C 증가 요청:
    - 토큰 관리자에게 C에 대한 토큰 요청
    - 토큰 획득 후 로컬 CRDT 업데이트: C += 1
    - 변경사항이 다른 노드로 비동기적으로 전파 시작
    - 토큰 반환 및 클라이언트에 성공 응답
3. 클라이언트 B가 C 증가 요청:
    - 토큰 관리자에게 토큰 요청 (A가 반환한 후)
    - 토큰 획득 및 로컬 CRDT 업데이트: C += 1
    - 전파 및 토큰 반환
4. 클라이언트 C가 C 읽기 요청:
    - 일관된 읽기를 위해 토큰 요청
    - 토큰 획득 시 모든 이전 업데이트가 적용된 상태
    - C = 2 반환 및 토큰 반환
5. CRDT 특성으로 인해 최종 상태는 모든 노드에서 동일하게 수렴

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

                   +-------------------+
                   |    클라이언트      |
                   +-------------------+
                   |                   |
                   v                   v
           +---------------+   +---------------+
           |   프론트엔드   |   |   프론트엔드   |
           +---------------+   +---------------+
                   |                   |
                   v                   v
           +-----------------------------------+
           |         합의 계층 (Paxos/Raft)     |
           +-----------------------------------+
                   |                   |
                   v                   v
         +----------------+     +----------------+
         |  데이터 저장소  |     |  데이터 저장소  |
         |    복제본 1    |     |    복제본 2    |
         +----------------+     +----------------+

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

+------------------+ +------------------+ +------------------+  
| 클라이언트 |      | 클라이언트 |      | 클라이언트 |  
+------------------+ +------------------+ +------------------+  
        | |                         |  
        v v                         v  
+------------------+ +------------------+ +------------------+  
| 타임스탬프 발급기 |      | 분산 락 관리자 |      | 트랜잭션 관리자 |  
+------------------+ +------------------+ +------------------+  
        | |                         |  
        v v                         v  
+----------------------------------------------------------+  
| 합의 프로토콜 |  
+----------------------------------------------------------+  
                            |  
                            v  
+----------------------------------------------------------+  
| 로그 복제 시스템 |  
+----------------------------------------------------------+  
                            |  
                            v  
+------------------+ +------------------+ +------------------+  
| 상태 머신 복제 |      | 상태 머신 복제 |      | 상태 머신 복제 |  
| 노드 1 |      | 노드 2 |      | 노드 3 |  
+------------------+ +------------------+ +------------------+  
        | |                         |  
        v v                         v  
+------------------+ +------------------+ +------------------+  
| 원자적 데이터 구조 |      | 원자적 데이터 구조 |      | 원자적 데이터 구조 |  
+------------------+ +------------------+ +------------------+

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

1. 사용자 A: 인출 요청 (1000 원) → 시스템
2. 사용자 B: 입금 요청 (500 원) → 시스템
3. 시스템: 타임스탬프 할당 (인출: T1, 입금: T2)
4. 시스템: 트랜잭션 순서 결정 (T1 → T2)
5. 시스템: 모든 노드에 합의 요청
6. 노드들: 합의 달성 (T1 → T2 순서로 실행)
7. 노드들: 인출 작업 실행 (잔액 - 1000)
8. 노드들: 입금 작업 실행 (잔액 - 1000 + 500)
9. 시스템: 클라이언트에 결과 반환

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

  +-----------------+ +-----------------+  
  | 사용자 A |           | 사용자 B |  
  | (인출: 1000 원) |           | (입금: 500 원) |  
  +--------+--------+ +--------+--------+  
           | |  
           v v  
  +------------------------------------------+  
  | 로드 밸런서 |  
  +------------------------------------------+  
           | |  
           v v  
  +--------+--------+ +--------+--------+  
  | 애플리케이션 |           | 애플리케이션 |  
  | 서버 1 |           | 서버 2 |  
  +--------+--------+ +--------+--------+  
           | |  
           v v  
  +------------------------------------------+  
  | 트랜잭션 관리자 |  
  | (타임스탬프 할당: T1, T2) |  
  | (순서 결정: T1 → T2) |  
  +------------------+---------------------+  
                     |  
                     v  
  +------------------------------------------+  
  | 합의 계층 (Paxos) |  
  | (모든 노드가 T1 → T2 순서에 합의) |  
  +------------------+---------------------+  
                     |  
       +-------------+-------------+  
       | |  
       v v  
+------+--------+ +------+--------+  
| 데이터베이스 |           | 데이터베이스 |  
| 노드 1 |           | 노드 2 |  
| 1. 인출 (-1000)| | 1. 인출 (-1000)|  
| 2. 입금 (+500) | | 2. 입금 (+500) |  
+---------------+ +---------------+