CRDT : Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types
개요
CRDT를 서칭하다가 Yjs 라이브러리 Github를 보았고, 해당 라이브러리가 Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types
논문의 알고리즘을 수정한 버전을 사용했다는 것을 알았다.
그래서 해당 논문을 읽어보았다.
Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types
1. Introduction
NRT(Near Real-Time) 즉, 근 실시간 P2P 기술이 웹 브라우저에서 어떻게 발전했는지 설명한다.
이 기술이 텍스트, 코딩 등 다양한 곳에서 사용됨을 알려준다.
이러한 어플리케이션에서 일관성을 보장하기 위해 신뢰할 수 있는 알고리즘이 필요하다는 것을 강조하며 이를 위해 OT, CRDT가 사용된다고 말한다.
해당 논문에서는 NRT 협업 어플리케이션을 위한 P2P 알고리즘인 Yet Another Transformation Approach)와 이를 구현한 Javascript 라이브러리인 Yjs를 소개한다고 한다.
2. Related Work
협업 편집 환경에서의 충돌 해결 방법을 다룬다.
주요 기술로는 OT, CRDT가 있다.
OT의 경우 Google Docs같은 시스템에서 사용되었고, CRDT 알고리즘은 P2P환경에서 사용된다.
추가적인 여담으로 OT의 경우 인덱스를 업데이트 하는 방식이고, 서버에 부담이 간다.
CRDT는 클라이언트간 통신이므로, 서버는 시그널링을 제외하고는 클라이언트간 통신에 관여하지 않으므로, 부담이 덜 된다고 할 수 있다.
여기까지만 본다면 "뭐야 그러면 CRDT가 최고네!" 라고 할 수 있지만, 문서를 동시에 편집하는 사용자가 1000명이라고 한다면, 클라이언트가 999명과 통신하는 어마어마한 상황이 발생할 수도 있다.(물론 서버 구성에 따라 다르긴 하다.)다양한 알고리즘의 비교와 기존 연구들을 요약한다.
3. The YATA Approach
YATA 알고리즘 작동 방식을 설명한다.
각 사용자는 고유 식별자(id)를 가진다.
추가적으로 각 사용자는 연산 카운터(operation counter)를 가지며, 사용자가 새로운 연산을 생성할 때마다 이 카운터가 증가한다.
결과적으로 생성된 연산은 사용자 id와 현재 연산 카운터로 구성된 고유 식별자(unique identifier)를 부여받게 된다.
YATA알고리즘은 선형 데이터를 이중 연결 리스트로 표현하는데, 해당 리스트에서 수행되는 연산은 insert, delete 두 가지이다.
3-1. Insert
삽입 연산은 다음과 같다.
O_k(id_k, origin_k, left_k, right_k, isDeleted_k, content_k)
id_k : 연산 O_k의 고유 식별자
origin_k : 연산 O_k가 생성될 때의 직접 선행자 (direct predecessor)
left_k : 연산 O_k의 이전 노드
right_k : 연산 O_k의 다음 노드
isDeleted_k : 연산 O_k가 삭제되었는지를 나타내는 플래그.
content_k : 삽입된 내용(ex,. 문자)
읽다가 direct prodecessor가 도대체 뭘까 이해가 안갔다.
직역하자면 직접 선행자이지만, 조금 더 읽어봐야 알 것 같았다.
읽어본 결과, direct prodecessor는 우리가 글자를 작성할 때 깜빡거리는 커서라고 이해했다.
예를 들어, "사과"에서 "사"와 "과" 사이에 "바나나"를 넣는다면 "사"가 direct prodecessor가 된다.3-2. Example
연산 O_k의 예를 들어보자.
사용자가 새로운 삽입연산(O_new)을 생성하면, 이 연산은 두 개의 삽입(O_i, O_j)의 사이에 통합된다.
새로 생성된 삽입 연산은 아래와 같이 정의된다.
O_new(id_k, O_i, O_i, O_j, false, content_new)
Intention Preservation
삽입 연산의 의도는 삽입이 이루어질 때 좌우 관계를 유지하는 것이다.
이를 위해 다음과 같은 관계가 설정 된다.
O_1 < O_2 <=> O_1이 O_2의 선행자이다.
O_1 <= O_2 <=> O_1 < O_2 V O_1 === O_2
쉽게 풀어쓰자면, 'a' 보다 'b'가 더 뒤에 있으면 'a'가 선행자이다.
만약 뒤에 동일한 'a'글자를 삽입했다고 하면 'a' === 'a'이므로 O_1 === O_2가 된다.
참고로 V는 OR라는 뜻이다.
Conflicting Insertions
충돌 삽입의 경우, 여러 삽입 연산이 동일한 위치에 삽입될 때 발생한다.
부가설명을 하자면,
1 | 2 | 3
a | b | c
위와 같은 표가 있었을 때,
1과 2 index 사이에 d를 삽입한다고 하면
1 | 1.5 | 2 | 3
a | d | b | c
와 같이 된다.
근데, 1과 2 사이에 d와 f를 삽입하면 1.5라는 index가 충돌이 일어나게 된다.
충돌을 해결하기 위해 다음과 같은 규칙을 사용하여 순서를 정의한다.
- 원점 연결의 교차를 금지
즉, 삽입 연산의 위치가(원점이) 서로 겹치게하지 않게 한다.
-
전이성 보장
예를 들어 'ABC'가 있을 때, A와 B사이에 D를 넣고, B와 C사이에 F를 넣는다고 해보자.
F가 삽입될 때, 먼저 넣은 D의 삽입 위치는 보존되어야 한다. -
동일한 원점에 대해 작은 생성자 ID 우선
동일한 위치에 삽입된 경우, ID가 더 작은 연산을 우선한다.(충돌 방지)
id 1이라는 사용자가 A와 B사이에 X를 넣고, id 2라는 사용자가 A와 B사이에 Y를 넣는다고 했을 때 id 1이 더 작으므로 AXYB라는 결과가 나와야 한다.
Correctness
- O_1 위치가 O_2의 origin보다 앞서있으면 O_1가 O_2보다 앞선다고 볼 수 있다.
- 모든 연산 O에 대해 O_2가 O보다 앞서면 O_1도 O보다 앞서야 한다.
- origin_1 === origin_2 즉, O_1과 O_2의 origin이 동일한 경우, ID가 더 작은 쪽이 앞선다.
Extendable Types
YATA가 지원하는 다양한 데이터 타입에 대해 설명한다.
선형 데이터타입, 트리, 그래프, 연관 배열 등.
기본 데이터 타입 바탕으로 JSON, XML과 같은 특정 데이터 형식을 구현할 수 있다고 한다.
Yjs: The P2P Shared Editing Framework
리스트, 연관배열, XML, 텍스트, 리치텍스트 타입 지원한다고 한다.
Evaluation
Yjs라이브러리의 성능 평가 결과이다.
응답성, 확장성 테스트이며, 웹 소켓 커넥터를 이용한 테스트에서 평균 25ms 이하의 응답속도를 기록한다고 한다.
Conclusion & Future work
해당 내용은 추후 성능 개선 계획(오프라인 작업시 연산 제거 지원 등)이 작성되어 있다.
자세한 내용은 아래 링크로 가면 본문이 나온다.
