CRDT (Last‐Write‐Wins)
 |
 |
| 좌양집중 처리 방식인 OT | 분산 동기화 처리 방식인 CRDT |
동시편집을 관리하는 대표적인 방식으로 OT(Operational Transformation)가 오랫동안 사용되어 왔습니다. OT는 중앙 서버를 통해 변경 사항을 중재하며, 동기화 문제를 해결하지만 복잡한 충돌 처리 로직이 필요하고 서버 부하가 가중된다는 단점이 있습니다.
이러한 한계를 해결하기 위해 CRDT(Conflict-free Replicated Data Types)가 등장하게 되었습니다.
 |
 |
CRDT (Conflict-Free-Replicated Data Types) 란 분산 환경에서 각 노드가 독립적으로 작업을 수행할 수 있도록 설계되었으며, 별도의 중앙 중재 없이도 데이터가 자동으로 일관성을 유지하도록 보장합니다.
즉, 네트워크 지연이나 순서가 보장되지 않는 환경에서도 일관된 상태를 유지할 수 있도록 여러 컴퓨터에 걸쳐 복제되는 데이터 구조입니다.
CRDT는 데이터 구조에 따라 크게 3가지로 나뉩니다.
-
상태 기반 CRDT: 전체 상태를 교환하고 병합하는 방식 -
작업 기반 CRDT: 변경 작업만을 전송하여 상태를 계산하는 방식 -
델타 CRDT: 상태와 작업 기반의 하이브리드 방식
이 중에서도 전체 상태를 교환하는 방식인 상태 기반 CRDT 가 구현 난이도가 낮고 빠르게 구현해볼 수 있었기 때문에 먼저 선택하게 되었습니다.
가장 구현 난이도가 낮은 상태 기반 CRDT 중에 LWW (Last-Write-Wins) 방식이 복잡도가 낮아 먼저 적용해보기로 했습니다.
LWW는 여러 노드에서 동일한 키에 대해 충돌이 발생할 때, 가장 최신에 기록된 값을 우선으로 선택하는 방식이다. 이 방식은 타임스탬프를 사용하여 각 값의 작성 시간을 추적하고, 시간 기준으로 가장 최신인 값을 유지함으로써 데이터의 일관성을 보장합니다.
어떤 상태를 저장하느냐에 따라 달라지겠지만, 캔버스와 같은 드로잉 기능에서는 아래와 같은 구조를 사용합니다.
LWWMap이 전체 캔버스 정보, 즉 모든 선들의 정보를 관리하고 (여러 Register를 관리), LWWRegister는 하나의 선(stroke)에 대한 정보를 관리합니다.
LWWRegister는 선 주인 (id), 선 생성 및 수정 timestamp, 선 정보 (value: x, y, color, width)를 관리합니다.
- 쉽게 비유하자면.. ^^.
-
LWWRegister: 한 페이지의 메모장 (선)- 누가 썼는지, 언제 썼는지, 무슨 내용인지 관리
- 새로운 메모가 오면 더 최신 것으로 교체할지 결정
-
LWWMap: 전체 다이어리 (선들)- 여러 페이지(Register)를 관리
- 새 페이지 추가, 페이지 삭제, 다른 사람의 다이어리와 동기화 등을 처리
-
classDiagram
class LWWRegister {
-id: string
-state: [id, timestamp, value]
+get value()
+get state()
+set(value)
+merge(remoteState)
}
class LWWMap {
-id: string
-data: Map<string, LWWRegister>
+get state()
+get strokes()
+addStroke(stroke)
+deleteStroke(id)
+merge(remoteState)
+mergeRegister(key, state)
}
LWWMap --* LWWRegister : contains many
note for LWWRegister "한 개의 데이터를 관리 (선 하나의 정보)"
note for LWWMap "여러 Register를 관리 (모든 선들의 정보)"
전체 LWW 코드를 살펴보기 전에 LWW Register와 LWWMap 클래스 구조를 간단하게 살펴보겠습니다.
LWWRegister는 선 데이터(Stroke)의 상태를 관리하는 기본 단위입니다.
-
value(getter): 현재 저장된 선 데이터만 반환합니다. -
state(getter): 작성자 ID, 타임스탬프, 선 데이터(x, y, color, width) 로 이루어진 전체 상태를 반환합니다. -
set(value: Stroke): 새로운 데이터를 받아 상태를 업데이트합니다. 현재 시간(Date.now())과 작성자 ID를 사용해 타임스탬프를 설정합니다. -
merge(remoteState: [string, number, Stroke]): 다른 사용자의 상태와 비교하여 최신 데이터를 선택합니다.- 시간이 더 최근인 데이터를 선택하고,
- 시간이 같다면 작성자 ID가 더 큰 데이터를 선택합니다.
class LWWRegister {
// 현재 저장된 선 데이터만 가져오기
get value(): Stroke {
return this.state[2]; // [id, timestamp, stroke] 중 stroke만 반환
}
// 전체 상태 가져오기 (작성자, 시간, 데이터)
get state(): [string, number, Stroke] {
return this.state; // [id, timestamp, stroke] 전체 반환
}
// 새로운 값으로 업데이트
set(value: Stroke): void {
this.state = [this.id, Date.now(), value]; // 현재 시간으로 업데이트
}
// 다른 사용자의 데이터와 병합
merge(remoteState: [string, number, Stroke]): boolean {
// 1. 시간 비교: 더 최신 것 선택
// 2. 시간이 같으면 ID 비교: 더 큰 ID 선택
return true/false; // 업데이트 여부 반환
}
}LWWMap은 여러 개의 선 데이터(Stroke)를 관리하는 맵 구조로, 각 선 데이터는 고유 ID로 관리됩니다.
(Map<선ID, Register객체>)
-
strokes(getter): 현재 활성화된 모든 선 데이터를 배열로 반환합니다. 삭제된 선은null로 설정되므로 제외됩니다. -
addStroke(stroke: Stroke): 새로운 선을 추가합니다.- 고유한 ID를 생성(
작성자ID-타임스탬프-랜덤값)한 뒤, 해당 선 데이터를LWWRegister로 생성하여 내부 맵에 저장합니다. - 생성된 ID를 반환합니다.
- 고유한 ID를 생성(
-
deleteStroke(id: string): 특정 선을 삭제합니다.- 실제 데이터를 삭제하지 않고, 대신 해당 선 데이터를
null로 설정합니다.
- 실제 데이터를 삭제하지 않고, 대신 해당 선 데이터를
-
merge(remoteState: MapState): 다른 사용자의 전체 맵 상태와 병합합니다.- 각 선 데이터의 상태를 비교하며 최신 데이터로 업데이트하고, 변경된 선들의 ID를 반환합니다.
-
mergeRegister(key: string, remoteState: RegisterState): 특정 선 하나의 상태를 병합합니다.- 해당 선 데이터의 병합 여부를 반환합니다.
class LWWMap {
// 현재 그려진 모든 선 정보 가져오기
get strokes(): Array<{id: string, stroke: Stroke}> {
// null이 아닌(삭제되지 않은) 모든 선 반환
return [...this.data].filter(stroke => stroke !== null);
}
// 새로운 선 추가
addStroke(stroke: Stroke): string {
const id = `${this.id}-${Date.now()}-${random()}`; // 고유 ID 생성
const register = new LWWRegister(this.id, [this.id, Date.now(), stroke]);
this.data.set(id, register);
return id;
}
// 선 삭제
deleteStroke(id: string): boolean {
const register = this.data.get(id);
if (register) {
register.set(null); // 실제 삭제 대신 null로 설정
return true;
}
return false;
}
// 다른 사용자의 전체 상태와 병합
merge(remoteState: MapState): string[] {
// 모든 선에 대해 하나씩 비교하고 병합
// 변경된 선들의 ID 목록 반환
}
// 단일 선에 대한 업데이트
mergeRegister(key: string, remoteState: RegisterState): boolean {
// 특정 선 하나만 업데이트
// 변경 여부 반환
}
}User 1:
- 새로운 선을 추가하기 위해
addStroke를 호출합니다. - 고유한 ID(
작성자ID-타임스탬프-랜덤값)를 생성하고, 해당 데이터를Register로 래핑하여 맵에 저장합니다. - 이 과정에서
Register.merge는 호출되지 않습니다.
User 2:
- User 1의 작업 결과를 소켓으로 전달받습니다.
- 해당 데이터를 기반으로
mergeRegister를 호출합니다. - 새로운 ID이므로 병합 과정(
Register.merge) 없이 새로운Register를 생성하고 맵에 저장합니다.
// User 1
Map1.addStroke(stroke)
// - 새로운 ID 생성 (user1-timestamp-random)
// - 새로운 Register 생성
// - Register.merge 호출 안됨
// - Map에 push됨
// User 2 (소켓으로 받음)
Map2.mergeRegister(strokeId, registerState)
// - ID가 새로운 것이므로 Register.merge 호출 안됨
// - 새로운 Register 생성되어 Map에 push됨User 1:
- 특정 선을 삭제하기 위해
deleteStroke를 호출합니다. - 맵에서 해당 선의
Register를 찾아 데이터를null로 설정합니다(Register.set(null)). - 이 과정에서도
Register.merge는 호출되지 않습니다.
User 2:
- User 1의 삭제 작업 결과를 소켓으로 전달받습니다.
-
mergeRegister를 호출하여 동일한 ID를 가진Register가 있는지 확인합니다.- 동일한 ID가 있을 경우,
Register.merge를 호출해 타임스탬프를 비교하고 데이터(null)를 병합합니다. - 동일한 ID가 없으면 새로운
Register(null)을 생성하여 맵에 추가합니다.
- 동일한 ID가 있을 경우,
// User 1
Map1.deleteStroke(strokeId)
// - 기존 Register를 찾아서
// - Register.set(null) 호출
// - Register.merge 호출 안됨
// User 2 (소켓으로 받음)
Map2.mergeRegister(strokeId, registerState)
// - 같은 ID의 Register가 있으면 Register.merge 호출됨
// - 타임스탬프 비교 후 null로 업데이트
// - 없으면 새로운 Register(null)가 Map에 push됨현재는 LWWMap에는 선 수정 관련 코드가 없지만, 추후 추가되었을 때의 코드 시나리오를 말씀드리겠습니다.
User 1:
- 특정 선을 수정하기 위해
updateStroke를 호출합니다. - 맵에서 해당 선의
Register를 찾아 새 데이터를 설정합니다(Register.set(newStrokeData)). - 이 과정에서는
Register.merge가 호출되지 않습니다.
User 2:
- User 1의 수정 작업 결과를 소켓으로 전달받습니다.
-
mergeRegister를 호출하여 동일한 ID를 가진Register가 있는지 확인합니다.- 동일한 ID가 있을 경우,
Register.merge를 호출해 타임스탬프를 비교하고 최신 데이터로 업데이트합니다. - 동일한 ID가 없으면 새로운
Register를 생성하여 맵에 추가합니다.
- 동일한 ID가 있을 경우,
// User 1
Map1.updateStroke(strokeId, newStrokeData)
// - 기존 Register를 찾아서
// - Register.set() 호출
// - Register.merge 호출 안됨
// User 2 (소켓으로 받음)
Map2.mergeRegister(strokeId, registerState)
// - 같은 ID의 Register가 있으므로 Register.merge 호출됨!
// - 타임스탬프 비교 후 최신 값으로 업데이트
// - 없으면 새로운 Register가 Map에 push됨- 재연결이나 새로고침 시 전체 상태를 동기화하기 위해
merge를 호출합니다. - 소켓으로 전달받은 모든 데이터를
merge를 통해 병합하며, 맵의 상태를 최신 상태로 업데이트합니다.
// 전체 상태가 필요할 때
Map.merge(entireState) // 모든 stroke 동기화- User 1이 새로운 선을 추가하거나 기존 선을 삭제/수정하면, 해당 작업이 소켓을 통해 User 2에게 전달됩니다.
- User 2는 전달받은 데이터를
mergeRegister로 병합하며, 필요한 경우 새 데이터를 추가하거나 기존 데이터를 업데이트합니다. - 모든 데이터는 LWW(Last-Writer-Wins) 규칙에 따라 타임스탬프를 기준으로 최신 상태를 유지하며, 삭제된 데이터는
null로 표시됩니다. - 재연결이나 새로고침 상황에서는 전체 상태를
merge로 동기화하여 작업 간의 불일치를 방지합니다.
sequenceDiagram
participant User1 as User 1
participant Map1 as Map (User 1)
participant Register1 as Register
participant User2 as User 2
participant Map2 as Map (User 2)
Note over User1,Map2: 1. 가장 흔한 케이스: 새로운 선 그리기
User1->>Map1: addStroke() 호출
activate Map1
Map1->>Map1: ID 생성: user1-timestamp-random
Map1->>Register1: 새 Register 생성<br>[user1, timestamp, strokeData]
deactivate Map1
Note over User1,Map2: 2. 일반적인 케이스: 다른 유저와 동기화
User2->>Map2: addStroke() 호출
activate Map2
Map2->>Map2: ID 생성: user2-timestamp-random
Map2->>Map1: Socket.emit으로 새로운 stroke 전송
Map1->>Map1: mergeRegister() 호출<br>=> 새 Register 생성<br>(ID가 다르므로)
deactivate Map2
Note over User1,Map2: 3. 드문 케이스: 선 삭제
User1->>Map1: deleteStroke() 호출
activate Map1
Map1->>Register1: set(null) 호출
deactivate Map1
Note over User1,Map2: 4. 매우 드문 케이스: Register merge
User1->>Map1: 동일 ID의 stroke 수정
activate Map1
Map1->>Register1: merge() 호출<br>같은 ID를 가진 경우만
Note over Register1: 타임스탬프 비교 후<br>최신 값만 유지
deactivate Map1
Note over User1,Map2: 5. 재연결 시: 전체 동기화
User2->>Map1: socket.on('reconnect')<br>Map.merge() 호출
activate Map1
Note over Map1: 모든 stroke 비교
Map1->>Map1: 각 stroke별 mergeRegister
deactivate Map1
실시간 공동편집에서 WebRTC 기반과 달리, 소켓 서버를 활용한 방식에서는 메시지가 항상 서버를 경유합니다. 이 과정에서 서버가 상태를 유지하지 않는 방식과 상태를 저장하는 방식 두 가지를 고려할 수 있습니다.
CRDT는 병합 작업을 클라이언트가 담당하도록 설계된 반면, 서버가 병합을 담당하면 CRDT의 장점을 상실하게 되고, 이는 OT 방식과 비슷한 구조로 바뀌게 됩니다. 따라서, 본 문서에서는 상태를 유지하지 않는 방식만 소개하겠습니다.
소켓 서버가 상태를 유지하지 않고, 클라이언트 간 데이터를 단순히 중계하는 방식입니다. 클라이언트가 서버로 데이터를 전송하면, 서버는 이를 다른 클라이언트들에게 그대로 전달합니다.
- 클라이언트 입장: 새로운 클라이언트가 방에 들어오면, 서버는 기존 클라이언트에게 현재 상태를 요청하여 새로운 클라이언트에 동기화합니다.
- 실시간 업데이트: 클라이언트의 업데이트 데이터를 서버가 다른 클라이언트들에게 중계합니다.
- 재연결: 클라이언트가 재연결되면 기존 클라이언트가 현재 상태를 공유하여 동기화합니다.
- 장점: 서버 구현이 간단하고 메모리 사용량이 적음
- 단점: 상태를 관리하는 책임이 클라이언트에 집중되며, 클라이언트가 많아질수록 상태 동기화 속도가 느려질 수 있음
sequenceDiagram
participant Client1 as Client 1
participant Server as Socket Server (Stateless)
participant Client2 as Client 2
Note over Client1,Client2: 1. 새로운 클라이언트 입장
Client2->>Server: joinRoom('canvas-room')
Server->>Client1: requestState('canvas-room')
Client1-->>Server: currentState
Server-->>Client2: syncState(currentState)
Note over Client1,Client2: 2. 실시간 그리기
Client1->>Server: draw(updateMessage)
Server-->>Client2: drawUpdate(message)
Note over Server: 단순 중계 역할<br>상태 저장하지 않음
Note over Client1,Client2: 3. 재연결 시
Client2->>Server: reconnect + joinRoom
Server->>Client1: requestState('canvas-room')
Client1-->>Server: currentState
Server-->>Client2: syncState(currentState)
-
초기 설정 (useRef와 useEffect 사용)
-
crdtRef와socketRef는 각각 CRDT 상태를 관리하는LWWMap객체와 Socket.IO 클라이언트를 참조합니다. 이들은useRef를 사용하여 렌더링 사이클과 독립적으로 유지됩니다. -
useEffect는 컴포넌트가 처음 마운트될 때 실행되며, 서버와의 소켓 연결을 설정하고, CRDT 상태 객체를 초기화합니다.
-
-
상태 요청 및 응답
- 클라이언트가 서버에 연결된 후, 다른 클라이언트들이 방에 들어왔을 때, 서버는
'requestState'이벤트를 전송합니다. - 클라이언트는 이 이벤트를 수신하면,
crdtRef.current.state를 서버에'shareState'이벤트를 통해 전달합니다. 이를 통해 서버는 새로 연결된 클라이언트에게 상태를 공유합니다.
- 클라이언트가 서버에 연결된 후, 다른 클라이언트들이 방에 들어왔을 때, 서버는
-
상태 동기화
- 서버는
'syncState'이벤트를 통해 새 클라이언트에게 방의 전체 상태를 보내며, 이를 통해 새 클라이언트는 기존의 상태를 받아와 동기화합니다. - 클라이언트는 이 상태를
crdtRef.current.merge()를 사용해 병합하고, 캔버스를 다시 그립니다.
- 서버는
-
실시간 그리기 업데이트
- 클라이언트가 드로잉 데이터를 수정하면, 서버는
'drawUpdate'이벤트를 통해 다른 클라이언트들에게 이 변경 사항을 전달합니다. - 클라이언트는 이 메시지를 수신하면
mergeRegister메서드를 사용해 상태를 병합하고, 변경된 내용을 캔버스에 반영합니다.
- 클라이언트가 드로잉 데이터를 수정하면, 서버는
function App() {
const crdtRef = useRef<LWWMap>();
const socketRef = useRef<Socket>();
useEffect(() => {
socketRef.current = io('http://localhost:3000');
crdtRef.current = new LWWMap(myIdRef.current);
// 1. 상태 요청 받음 (방에 있던 클라이언트)
socketRef.current.on('requestState', () => {
if (crdtRef.current) {
socketRef.current.emit('shareState', crdtRef.current.state);
}
});
// 2. 상태 수신 (새로 들어온 클라이언트)
socketRef.current.on('syncState', (fullState) => {
if (crdtRef.current) {
crdtRef.current.merge(fullState);
redrawCanvas();
}
});
// 3. 실시간 업데이트
socketRef.current.on('drawUpdate', (message: CRDTMessage) => {
if (!crdtRef.current) return;
if (message.type === 'update') {
const { key, register } = message.state;
if (crdtRef.current.mergeRegister(key, register)) {
redrawCanvas();
}
}
});
}, []);
}-
방 입장 및 상태 요청
- 클라이언트가
'joinRoom'이벤트를 보내면, 서버는 클라이언트를 특정 방에 추가하고, 해당 방의 다른 클라이언트들에게'requestState'이벤트를 전송하여 상태 요청을 합니다.
- 클라이언트가
-
상태 공유
- 기존 클라이언트는 새로 들어온 클라이언트에게
'syncState'이벤트를 보내며, 현재 상태를 전달합니다. 이를 통해 새 클라이언트는 이전 상태를 받아와 동기화합니다.
- 기존 클라이언트는 새로 들어온 클라이언트에게
-
그리기 업데이트 중계
- 클라이언트가 드로잉을 수정하면, 서버는
'drawUpdate'이벤트를 사용해 그리기 데이터를 해당 방의 다른 클라이언트들에게 중계합니다. 이 방식은 실시간으로 다른 클라이언트들의 화면을 업데이트하는 데 사용됩니다.
- 클라이언트가 드로잉을 수정하면, 서버는
-
연결 종료
- 클라이언트가 연결을 종료하면, 서버는
'playerLeft'이벤트를 통해 다른 클라이언트들에게 해당 클라이언트가 방을 떠났다는 사실을 알립니다.
- 클라이언트가 연결을 종료하면, 서버는
import { Server } from 'socket.io';
const io = new Server(3000);
io.on('connection', (socket) => {
let currentRoom: string;
// 1. 방 입장
socket.on('joinRoom', ({ roomId }) => {
socket.join(roomId);
currentRoom = roomId;
// 방의 다른 클라이언트들에게 상태 요청
socket.to(roomId).emit('requestState');
});
// 2. 상태 공유 (기존 클라이언트가 새 클라이언트에게)
socket.on('shareState', (state) => {
socket.to(currentRoom).emit('syncState', state);
});
// 3. 그리기 업데이트 - 단순 중계만
socket.on('draw', ({ roomId, drawData }) => {
// 다른 클라이언트들에게 바로 전달
socket.to(roomId).emit('drawUpdate', drawData);
});
// 4. 연결 종료
socket.on('disconnect', () => {
if (currentRoom) {
socket.to(currentRoom).emit('playerLeft', { socketId: socket.id });
}
});
});**CRDT(Conflict-free Replicated Data Types)**는 분산 환경에서 데이터 일관성을 유지하는 데 효과적인 방법을 제공합니다.
특히 LWW(Last-Write-Wins) 방식의 CRDT는 구현이 간단하면서도 동시성 제어를 효과적으로 처리할 수 있습니다. 중앙 서버 없이도 데이터의 일관성을 보장하며, 타임스탬프를 통해 가장 최신의 작업을 자동으로 선택하여 충돌을 해결합니다.
하지만 상태 기반 CRDT는 모든 상태를 주고받아야 하기 때문에 네트워크 부담이 커질 수 있습니다. 이 문제를 해결하기 위해 변경된 작업 내용만 주고 받는 작업 기반 CRDT 방식으로 개선할 수 있으며, 추후 도전 후에 다음 편 마련해보겠습니다. 모두 안녕~
https://jakelazaroff.com/words/an-interactive-intro-to-crdts/
https://redundant4u.com/post/crdt
[GitHub - lesmana/webrtc-without-signaling-server: webrtc without signaling server. a stun server is still used if connecting over the internet.](https://github.com/lesmana/webrtc-without-signaling-server)