Consensus Algorithm for Synchronization

Consensus Algorithm

[합의 알고리즘(Consensus Algorithm)]

간단한 합의 알고리즘 로직

Leader가 되는 유저가 있고, 모든 다른 유저에게 자신의 상태를 브로드캐스트

A: [데이터1, 데이터2] -> Broadcast to B, C, D

브로드캐스트 받은 유저들은 자신이 가진 데이터 목록과 비교하여 누락 데이터를 확인

A가 [데이터1, 데이터2]를 보냈고, B는 [데이터1]을 가지고 있다면 B는 데이터2가 누락되었다고 판단
A가 [데이터1, 데이터2]를 보냈고, C는 [데이터1, 데이터2, 데이터3]을 가지고 있다면 C는 데이터3이 불일치한다고 판단

가장 먼저 Broadcast를 시작한 유저가 Leader 역할을 맡아 상태를 취합하여 누락된 데이터를 재배포

즉, 누락된 데이터 ID를 바탕으로 모든 유저가 합의된 상태를 만들어가는 방식

리더는 자신의 목록과 비교하여 누락 데이터와 추가 데이터를 동시에 확인한다.

A가 리더로 선택되었을 때, 모든 유저의 상태를 전송받는다.
- B -> Missing 데이터2
- C -> Additional 데이터3

이후 데이터 전송 및 수신을 통해 불일치 데이터의 동기화를 진행한다.

[Missing] A -> B에게 데이터2 전송
[Additional] A -> C에게 데이터3 전송 요청

데이터 병합이 완료되면 다시 한 번 Broadcast가 진행된다.

A: [데이터1, 데이터2, 데이터3] -> Broadcast to B, C, D

결과

[화면 기록 2024-11-28 오전 2.54.37.mov]

sequenceDiagram
    loop [Until allSynced]
    A->>+B: 해시 값 전달: hash([String: String])
    A->>+C: 해시 값 전달: hash([String: String])
    A->>+D: 해시 값 전달: hash([String: String])
    B-->>-A: 해시 비교 정보 전달: hashMatch([fileName1: .missing])
    C-->>-A: 해시 비교 정보 전달: hashMatch([fileName2: .additional])
    D-->>-A: 해시 비교 정보 전달: hashMatch([fileName1: .missing, fileName2: .additional])
    Note right of A: sendSyncFlags: [B: false, C: false, D: false]<br/>receiveSyncFlags: [B: false, C: false, D: false]
    A->>+B: missing 파일 전달: shareResource(fileName1)
    A->>+C: additional 파일 요구: SyncMessage.request([fileName2])
    A->>+D: missing 파일 전달: shareResource(fileName1)
    A->>+D: additional 파일 요구: SyncMessage.request([fileName2])
    B-->>-A: sendResponse 전송
    Note right of A: sendSyncFlags: [B: true, C: false, D: false]<br/>receiveSyncFlags: [B: true, C: false, D: false]
    C-->>A: requested 파일 전달: shareResource(fileName2)
    C-->>-A: receiveResponse 전송
    Note right of A: sendSyncFlags: [B: true, C: true, D: false]<br/>receiveSyncFlags: [B: true, C: true, D: false]
    D-->>-A: sendResponse 전송
    Note right of A: sendSyncFlags: [B: true, C: true, D: true]<br/>receiveSyncFlags: [B: true, C: true, D: false]
    D-->>A: requested 파일 전달: shareResource(fileName2)
    D-->>-A: receiveResponse 전송
    Note right of A: sendSyncFlags: [B: true, C: true, D: true]<br/>receiveSyncFlags: [B: true, C: true, D: true]
    end
    A-->A: isSynchronized.send(Void)
    A-->B: completed
    B-->B: isSynchronized.send(Void)
    A-->C: completed
    C-->C: isSynchronized.send(Void)
    A-->D: completed
    D-->D: isSynchronized.send(Void)

    %% A -- hash([String: String]) --> C 
    %% A -- hash([String: String]) --> D
    %% B -- hash matching info (ex. [fileName1: .missing, fileName2: .additional]) --> B

Loading