CRDT vs OT

Channel Talk

2021년 4월 6일

테크 인사이트

*본 콘텐츠는 마틴클랩만의 유튜브 'CRDTs: The Hard Parts'를 요약/정리한 자료입니다

CRDT vs OT

CRDT(Conflict-Free-Replicated Data Types)와 OT(Operational Transformation)란 동시편집 기술로, 실시간 협업 툴에 관련된 기술입니다. 최근 코로나19로 재택근무하는 회사가 많아지면서 '실시간 협업 애플리케이션'도 주목되고 있는 것 같습니다.

실시간 협업 에디터가 동작되는 과정

CRDT와 OT를 설명하기 전에, 실시간 협업 에디터가 어떻게 동작하는지 생각해봅시다.

Google Docs에서 두 명의 사용자가 똑같이 'Hello!'를 보고 있다고 할 때, 한 명은 Hello 와 ! 사이에 World를 넣고, 다른 한 명은 ! 뒤에 :-) 이모티콘을 추가하겠죠. 이렇게 되었을 때 결과가 어떻게 나와야 할까요?

두 사용자가 입력한 값이 모두 합쳐져서, ‘Hello World ! :-)’ 가 나와야 하겠죠

이러한 실시간 에디터에 사용되는 알고리즘은 CRDT와 OT, 2가지가 있습니다.

CRDT와 OT 비교

OT(Operational Transformation)는 2006년 정도까지 사용되었던 기술이라고 해요. Google Docs, MS Office에서 OT 기술이 사용되었습니다. CRDT(Conflict-Free-Replicatied Data Types)는 2006년 이후부터 현재까지 사용되고 있는 기술입니다. 저희가 요즘 사용하는 Figma도 있고, Redis, 국내 협업도구 Yorkie에서도 CRDT를 사용하고 있다고 해요.

OT(Operational Transformation)의 작동 원리

실제 예를 들어서 OT 기술 먼저 설명을 드리겠습니다. 아까처럼 google docs에 두 명의 사용자가 같이 편집한다고 했을 때, 한 명은 helo 사이에 l을 추가하고, 다른 한 명은 마지막에 !를 추가할 수 있겠죠.

이때, 변경사항은 인덱스 위치를 이용해서 L을 position 3에 넣는 오퍼레이션(왼쪽)과 !를 position 4에 넣는 오퍼레이션(오른쪽)이 발생하게 됩니다.

이 두 개의 오퍼레이션을 서버로 보내게 되고, 이를 서버가 받아서 통합합니다.

l을 position 3에 먼저 넣게 될 경우, 원래는 !가 position 4에 들어가야하는데 이미 l이 3에 들어가서 위치가 바뀌어 버렸습니다.

따라서, 인덱스 위치가 바뀌어 !를 4가 아닌 5에 넣게 됩니다

이렇게 오퍼레이션이 이전 동작에 의해 바뀌어 다음 동작을 transform(변환) 시켜줘야 합니다. 이것이 바로 operational transformation OT 기술입니다.

다시 정리하자면, 모든 변경사항 기록 -> 서버에 쭉 전송 -> 순차적 실행 -> 클라이언트에게 주는 방식이 됩니다.

OT 방식의 문제점

이러한 동작으로 인해 OT에는 단점이 있는데요, 유저가 서버에 수정사항을 던지게 되면 다른 유저들과 직접적으로 연동할 방법 없습니다. transformation을 하는 주체인 서버가 있어야 하기 때문이죠.

따라서, OT의 문제는 중앙 집중식 서버/DB가 필요하다는 것입니다. 이런 구조에서는 사람이 몰릴 때 과부화가 올 수 있습니다.

하지만, CRDT는 중앙집중식 서버가 필요 하지 않습니다. 어떤 네트워크, 통신을 선택하든지 제한이 없죠. 그래서 협업 애플리케이션 뿐 아니라, Redis Enterprise 같은 데이터 센터 간에 지역적으로 떨어져서 운영하는 DB 시스템에도 활용된다고 합니다.

CRDT(Conflict-Free-Replicated Data Types)의 작동 원리

CRDT의 정의는 ‘어떤 변경사항을 받으면, 순서와 상관없이 변경사항만 같으면 같은 상태’ 입니다.

OT는 순서가 중요하고, CRDT는 순서가 상관 없고 operation만 같으면 어긋나더라도 같은 상태가 됩니다. 예를 들어 설명 드리겠습니다.

아까 OT는 인덱스로 한다고 했는데 인덱스는 변하게 되잖아요, CRDT는 이 문제를 피하기 위해 각 개체를 유니크한 값으로 봅니다. 따라서 텍스트가 추가될 때 새로운 유니크값을 생성해서 넣어주게 되죠.

예를 들어, 유니크한 값을 0과 1 사이의 숫자들로 한다고 치면

동일하게 L과 !를 넣는 상태에서

L은 0.6과 0.8사이에 0.7을 생성하고, !는 0.8과 1 사이에 0.9를 생성하여 L 과 !가 0.6, 0.8 사이에 각각 0.7, 0.9로 들어가게 되죠.

동시 편집을 하더라도 합치는 과정에서 유니크한 값으로 판별하기 때문에 충돌이 일어나지 않게 됩니다. CRDT는 이러한 기술을 서버응답을 기다릴 필요 없이 할 수 있는 것이죠. 통신은 서버에서 하거나 클라에서 직접 병합하거나 같은 결과를 만들기 때문에 네트워크의 영향을 직접적으로 받지 않을 수 있습니다.