CRDT의 기본 개념과 원리 그리고 구현체인 Yjs의 원리

CRDT

CRDT란 무엇일까?

CRDT는 synchronization이나 consensus와 같은 비싼 작업없이도 conflict가 발생하지 않음이 보장되는 오브젝트를 의미합니다.
CRDT이기 위해서는 모든 업데이트가 commutative하고 eventual consistency함을 만족해야 합니다.

CRDT에 대해 설명하기 전에 2011년에 처음으로 발표된 논문의 Abstract를 읽고 시작하겠습니다.

Eventual Consistency(EC)를 기반으로 하는 분산 데이터 시스템은 어떤 로컬 머신이라도 리모트 머신의 동기화의 도움없이 업데이트하는 것이 가능해진다.
이는 클라우드와 같은 큰 규모의 분산 시스템에서도 performance와 scalibility를 보장해준다.
하지만 이전까지의 EC를 이용한 시스템은 일반화 할 수 없는 해결책(ad-hoc)이었으며 에러가 발생하기 쉬웠다(error-prone).
우리는 일반적인 Strong Eventual Consistency(SEC) 모델을 통해 통합(convergence)에 필요한 조건들에 대해 연구하였다.
SEC에 필요한 조건들에 부합하는 데이터 타입을 Conflict-free Replication Data Type(CRDT)라 한다.
CRDT에 속해있는 머신들은 self-stabilization을 통해 failure-tolerance를 보장받게 된다.
후략...

용어 정리

CRDT를 이해하기 위해서 분산 시스템에 대한 여러 배경지식이 필요한데 필수적인 몇 개의 용어만 간단하게 정리하겠습니다.

• conflict : merge 시에 발생할 수 있는 모든 종류의 문제를 의미.
• collaboration : 모든 변경점을 전부 merge하는(keep-all) 방법론. (CRDT에서 사용)
• consensus : confliction 발생시 collaboration과 반대로 여러 개의 변경점 중 하나만을(pick-one) 선택하는 방법론. (Blockchain에서 사용)
• eventual consistency : 분산 시스템은 CAP Theorem에 의해 Availability와 Consistency 중 하나를 선택해야 하는데 이때 HA(High Availability)는 필수이므로 Consistency를 대체하기 위해 나온 방법. 모든 replica는 결국 같은 값을 갖게 된다는 것을 의미.
• commutative : a * b = b * a가 성립한다는 것을 의미. 다른 말로, eventual consistency가 보장된다면 업데이트가 어떤 순서로 오든 모든 replica는 결국 같은 값을 갖게 된다는 것을 의미.

실시간 협업 툴

실시간 협업 툴(Collaborative Editing Tools)을 구현하기 위해서 옛날(1980년대)부터 많은 논문과 이론들이 출간되어 왔습니다.
하지만 대부분의 논문은 오류가 발견되며 틀렸다는 것이 밝혀졌고(이는 그만큼 알고리즘이 보기보다 훨씬 어려웠다는 것을 의미하기도 합니다.) 소수의 논문만이 올바르다는 것이 증명되었는데 이 논문 중 하나가 Google Docs로 구현된 Operational Transformation(OT)입니다.

OT 알고리즘은 "인덱스 0에 a 입력됨.", "인덱스 1에 p 입력됨."과 같은 시간의 흐름에 따른 변화(operation)를 기록하는 것으로 동작합니다.
해당 알고리즘을 실시간 협업에 사용하게 되면 여러 사람에 의해 concurrent한 변화가 발생되게 되는데 이때 conflict가 발생하지 않게 하기 위해서 index를 바꿔주는 등의 작업(transformation)을 해야 하는데 이때 중앙화된 서버를 필요로 합니다.
하지만 중앙 집중형 서버는 이후 분산 시스템 디자인에서 병목지점으로 동작하였고 이를 해결하기 위한 방법으로 CRDT가 떠오르게 됩니다.

CRDT는 위에서도 언급했듯이 commutative와 eventual consistency를 기반으로 동작합니다. 이는 중앙 집중 서버가 필요없고 네트워크에 의존적이지 않아도 된다는 것을 의미하죠.
하지만 이 개념은 convergence(통합)를 보장하지만 어떤 상태가 유저가 원하는 최종 상태인지를 보장해주지 못 하는데 이를 해결하는 많은 구현체들이 이후에 등장하게 됩니다.

CRDT 원리

CRDT는 모든 문자 하나 하나마다 고유한 id를 부여합니다. 예를 들면 다음과 같습니다.
이러한 id는 단지 개념에 대한 예시일뿐 정해진 형태는 아닙니다.

Node A 
char  -> H  e  l  o
index -> 0a 1a 2a 3a

Node B 
char  -> H  e  l  o
index -> 0a 1a 2a 3a

이때 Node A와 Node B에서 다음과 같이 concurrent하게 edit를 했다고 합시다.

Node A 
char  -> H  e  l  l  o
index -> 0a 1a 2a 4a 3a

Node B 
char  -> H  e  l  o  !
index -> 0a 1a 2a 3a 4b

이런 경우 네트워크 레이어에 발행되는 이벤트는 다음과 같습니다.

Node A
'l'이라는 캐릭터를 4a라는 id로 2a 오른쪽에 넣어줘.

Node B
'!'라는 캐릭터를 4b라는 id로 3a 오른쪽에 넣어줘.

이 이벤트는 같은 CRDT를 공유하는 모든 유저에게 발행되게 됩니다. (CRDT는 네트워크 레이어에 agnostic하므로 WebRTC, WebSocket 등을 선택해서 이용합니다.)

OT에서는 캐릭터가 index를 갖고 그 index에 따라 달라지는 작업을 중앙 서버에서 해주어야 했지만 CRDT에서는 고유한 id를 기준으로 이벤트를 발행하기에 p2p로 동작할 수 있습니다.

만약 다음과 같이 정확히 같은 위치에 동시에 이벤트가 발행되면 어떻게 처리할까요?

Node A 
char  -> a  b  c
index -> 0a 1a 2a

Node B 
char  -> a  b  c
index -> 0a 1a 2a

Node A에서는 3a를 0a 다음에 넣고, 4a를 3a 다음에 넣는 동시에
Node B에서는 3b를 0a 다음에 넣고, 4b를 3b 다음에 넣도록 수정합니다.

Node A 
char  -> a  x  y  b  c
index -> 0a 3a 4a 1a 2a

Node B 
char  -> a  p  q  b  c
index -> 0a 3b 4b 1a 2a

이런 경우 다음과 같은 이벤트가 발행되겠죠.

Node A
'x'라는 캐릭터를 3a라는 id로 0a 오른쪽에 넣어줘.
'y'라는 캐릭터를 4a라는 id로 3a 오른쪽에 넣어줘.

Node B
'p'라는 캐릭터를 3b라는 id로 0a 오른쪽에 넣어줘.
'q'라는 캐릭터를 4b라는 id로 3b 오른쪽에 넣어줘.

이때 한쪽 Node에서의 작업 처리는 간단하게 가능합니다.
예를 들어 위의 Node B에서 발행한 이벤트를 Node A에서는 아래와 같이 conflict없이 처리됩니다.

Node A 
char  -> a  p  q  x  y  b  c
index -> 0a 3b 4b 3a 4a 1a 2a

하지만 문제는 다른 Node에서의 작업 처리 방법입니다.
Node B에 naive한 방식으로 Node A에서 발행한 이벤트를 바로 처리하면 다음과 같이 될겁니다.

Node B 
char  -> a  x  y  p  q  b  c
index -> 0a 3a 4a 3b 4b 1a 2a

위와 같이 처리되면 Node끼리 서로 다른 상태를 가지게 됩니다.
이를 해결하기 위해 다음과 같은 조건을 추가합니다.

발행된 이벤트의 id보다 작거나 같은 id가 이미 존재하면 전부 건너 뛰면서.

이 조건이 추가되면 3a라는 id는 Node B에 존재하는 3b, 4b는 3a보다 작거나 같으므로 건너뛰고 2a보다는 크니까 최종적으로 다음 형태를 가지게 되죠.

Node B 
char  -> a  p  q  x  y  b  c
index -> 0a 3b 4b 3a 4a 1a 2a

위와 같은 방식으로 CRDT에서는 distributed system에서 conflict-free한 형태를 가질 수 있게 되었습니다.

Yjs

CRDT는 자료구조와 알고리즘이고 이를 실제로 사용하기 위해서는 구현체가 필요한데 유명한 구현체로는 Automerge, Yjs, Yorkie 등이 있습니다.
이 중 Yjs의 동작 원리에 대해 설명을 진행하도록 하겠습니다.

Edit와 Document

위 CRDT의 원리에서 보았듯 CRDT는 document를 주고받는 것이 아닌 이벤트를 주고받습니다.
이는 CRDT에서는 Document가 아닌 Edit를 일급 객체로 취급한다는 의미이기도 합니다.
모든 이벤트가 commutative, eventual consistency하다면 결국 이벤트만으로 모든 노드가 같은 state를 가질 수 있게 되기 때문이죠.

Document는 일시적(ephemeral)이다

이벤트를 주고받으면서 변경되는 document는 메모리에 일시적으로 저장되며 persistent되지 않습니다.

모든 것은 리스트로 되어있다

내부 구성을 보면 Yjs는 모든 복합 데이터 구조를 list로 구성하고 있습니다.
Array는 item의 list이며, map은 key-value list이고, String은 character로 된 list입니다.(하지만 주로 lazy하게 동작)

Edit

edit는 하나의 document에 발행되는 모든 변경을 의미합니다.

Edit는 일급 객체이다

edit 그 자체가 데이터이며 클라이언트와 서버에 persistent됩니다.
edit를 데이터로 취급하고 이를 persistent하는 덕분에 오프라인 수정 기능이 가능합니다.

일단 edit가 생성되고 나면 edit는 immutable하고 삭제할 수 없습니다.

Edit는 insertion이거나 deletion이다

insertion은 id, content, position 속성 등을 가지고 있고 이는 edit이 어떤 위치에 어떻게 존재해야 하는지를 나타냅니다.

deletion은 어떤 insertion의 id가 숨김 처리되어야 하는지 나타냅니다. 위에서 말했듯 edit은 삭제되지 않기 때문에 insertion을 삭제하는 것이 아닙니다.
edit가 절대 삭제되지 않는다는 점을 통해 정확히 어떤 아이템이 어디에 들어가야 하는지를 확신할 수 있게 됩니다.
하지만 현실적으로 성능을 위해서 insertion은 최대한 truncated되며 완전히 삭제되는 경우 id와 position만을 가지는 tombstone이 됩니다.

어떤 값을 수정하는 경우, 이 또한 update가 아닌 deletion + insertion이 같이 일어남을 의미합니다.

Yjs의 insertion 최적화

이론적으로는 insertion되는 모든 캐릭터에 id를 부여하고 이를 다루었지만 현실적으로 이는 성능 문제를 야기하므로 Yjs는 이를 merging하여 최적화를 진행합니다.

"ABC"라는 캐릭터를 sequential하게 입력하는 경우 "A", "B", "C" 3개의 insertion을 발행하는 것이 아니라 "B", "C"를 "A"에 append하는 식으로 최적화됩니다.

레퍼런스

CRDT 논문

yjs-fundamentals

CRDTs and the Quest for Distributed Consistency