[CRDT] CRDT 심화 정리

[CRDT] CRDT 기본 원리 정리

위 기본 원리를 이해한 다음에 쓰는 글입니다.

 

 

마찬가지로 martin kleppmann 씨의 심화 영상을 정리한 내용입니다.

 

CRDT와 OT는 원리가 응용되어서 널리 사용되고 있지만, 학문적으로 직면한 문제들이 있습니다. 그에 대한 소개들입니다.

 

(사람들과) 합의는 되었으나...  예상과 다른 결과들

좌 : 이상, 우 : 현실

 

앞 글에서 설명한 원리들로 CRDT는 여러 사람이 같은 화면(합의)을 보게 만들 수는 있지만, 합의가 예상한 결과는 아닙니다.

 

위 예시 사진처럼 1번 사람은 두 번째 줄에 내용을 수정했고, 2번 사람은 두 번째 줄의 순서를 첫 번째 줄로 바꾸었습니다.

이 과정에서 우리는 두번째 줄을 수정하고  첫 번째줄로 옮겼으니, 첫번째줄의 수정 내용이 있을 것이라 예상했습니다.

하지만, 두번째는 첫 번째줄로 이동하고, 삽입한 내용은 세 번째 줄에 남았습니다....

 

이는 동시 편집 시, 편집자들이 입력한 이벤트(행동과 작업내용)와 이를 처리하는 순서를 정하는 알고리즘에 달려있습니다. 합의에는 이를 수 있지만 사용자 경험에 좋은 결과는 아닙니다.

이 문제는 지속적으로 해결하기 위해서 노력 중입니다. 다양한 논문이 나오고 있으며, 현재는 RAT라는 논문이 성능과 사용자경험에서 가장 적합하게 이를 잡아내고 있습니다. 

Sub Tree 문제

 

위 사진과 같이 subTree를 이동시켰을 때, 나올 수 있는 결과는 총 4가지입니다. 이 중 최악은 b입니다 Tree라는 자료구조를 붕괴시켜버립니다.

좌 : 무한 루프 , 우 : 시계열 순 배열을 통한 예외처리

 

위 사진은 무한 루프가 생긴 트리구조입니다. 트리라는 구조에서 마찬가지로 있어서는 안되고, 구글 드라이브에서는 이런 사이클이 생길 경우 바로 차단해버리는 예외처리 로직을 구현해두었습니다.

좌 : 사이클 검증 이론 우 : 사이클 생기는 지 체크하는 과정

 

그 예외처리 로직은 첫 번째 사진처럼 부모의 존재여부와 조상과의 관계를 통해서 안정성을 체크할 수 있고, 이 작업을 시계열 순으로 나열하여 무한루프가 생기는 지 체크합니다.

 

CRDT 최소안전 조건

결론적으로 안전한 CRDT 트리 구조를 가져가려면, 

- 모두 고유한 부모를 가져아한다.

- 순환이 있어서는 안된다.

를 만족해야합니다.

성능 문제

todoList에서 우선순위를 바꾸는 작업에 대해서 우리는 이걸 change 작업이라 생각합니다.

하지만, 실제로 CRDT에서 change는 없고 delete와 insert 작업을 반복할 뿐입니다.

 

그래서, 사용자 경험은 올릴 수 있지만, 성능이 떨어지고 성능은 보장되었지만 사용자 경험이 안 좋은 상태이죠. 그런데, 이런 과정이 무수히 일어나는 CRDT는 성능이 괜찮을까요?

다행히 거의 대부분의 케이스에서 시간당 600개 이상의 작업이 생기지 않을 것이므로 괜찮다 합니다.

 

CRDT에서 시간당 작업이 매우 많이 일어나기 때문에 효율성이 꽤 중요합니다. 특히, CRDT는 가진 메타데이터가 너무 많아서 overhead가일어날 경우가 너무나도 많습니다. 그 내부에서 효율은 압축 알고리즘이 굉장히 중요하게 작용했습니다.

좌 : 압축 과정, 우 : 압축할 데이터

첫 번째 표에서 성능 개선 내용은 다음과 같습니다

• 실제 원시데이터 크기 : 104,852bytes (27569 bytes : gzip 적용 시)
• 기본적인 CRDT 메타데이터 포함 후 : 695,298bytes (302,067 bytes) => 원시 데이터의 6.8배
  • 커서 이동 포함 시 (1.2배),
  • undo / redo history 포함 시, (2.5배)
  • tombstone 포함 시, (1.5배)
• JSON 변환 시 : 146,406,416 bytes  => 원시 데이터의 1440배

만약, JSON으로 데이터를 교환했다면 실제 전송하고자 하는 데이터의 1440배가 듭니다.

 

그래서, CRDT에서는 binary 형태로 교한하며 불필요한 history를 최대한 제거합니다.

하지만, 이래도 데이터가 원시 데이터에 비해서 매우 크기에 압축을 적용합니다.

 

문서 편집기에 경우 사람들은 연속적으로 내용을 편집하는 경향이 있습니다. 그 내용을 표로 정리한 게 우측입니다. 이 표는 반복되거나 규칙이 있는 부분이 많지만 단순하게 객체로 표현하면 저 표를 모두 넣어야할 것입니다. 하지만, 이런 성향을 고려해서 압축하면 "RLE(6,1), RLE(A,1), ‘hello’" 로 단순하게 압축할 수 있습니다. 이런 식의 압축 알고리즘이 CRDT를 효율적으로 작동하게 만듭니다.

 

---

지금까지 CRDT가 현재 겪는 문제를 소개하였습니다. 사실 이 부분은 학문적인 부분이 매우 큰 부분이라 큰 의견은 내지 못했지만, 압축 알고리즘이나 무한 루프 등 인사이트를 얻었기 때문에 작성하였습니다.