[동시 협업 툴-1] 여러명의 사용자가 동시에 같은 문서를 편집할 때 서버는 어떤 동작을 해야할까? (OT와 CRDT)

너무너무 만들고 싶은 것이 있어서 스터디 기록용으로 블로그를 시작하게 되었다. 

동시 협업 툴에 대한 지식을 쌓기 위해서 공부를 시작하려고 한다. 

 

동시 협업 툴에서는 문서를 작성하거나, 슬라이드를 작성할 때 동시에 여러명이 같은 도형이나 단어에 접근해서 변형시키는 것이 가능해야한다. 동기화된 화면을 보여줘야 하기 때문에, 동시에 같은 것에 접근해서 operation 을 했을 때 그것을 서버단에서 어떻게 처리할지가 중요해진다. 예를 들면 같은 단어에 다른 operation이 적용된다면 그걸 서버단에서 잘 처리하는 메커니즘이 필요하다는 것이다. 

 

이 과정을 어떻게 처리하면 좋을 지에 대해서 이미 사용되는 두가지의 방법이 있다고 한다. OT와 CRDT이다. 

1. OT (Operational Transformation) 방식 

- 오퍼레이션이 수행된 시간상의 순서를 고려해서 오퍼레이션이 적용될 우선순위가 부여됨. 

-  앞서 적용된 오퍼레이션의 영향을 후순위 오퍼레이션의 보정 정보로 사용한다. (ex: 똑같은 위치의 문자를 삭제한다고 가정하면, 보정을 해서 두번째 operation은 적용되지 않는다. ) 

- google docs, microsoft office에서 사용 

- 단점: merge작업이 한곳에서 이루어짐. 서버의 부하가 가중됨. 실질적으로는 저장을 하지 않는 한 스토리지가 있는 곳으로 데이터 전송될 필요가 없고, 동시 작업자들사이의 동기화만 이루어지면 됨. 또한 중계 서버가 멀리 있다면, 같은 네트워크 상에 있는 동시 작업자들인데도 중계서버에서 merge된 결과를 받아와야 하므로 latency가 느려짐. 

 

2. CRDT(Conflict-Free-Replicated Data Types) 방식 

- CRDT의 장점은 동시성이 요구되는 동시 작업자들끼리만 데이터를 교환하면 된다는 것이다. 서버에 대한 의존성을 줄이고, 반응속도 향상에 도움이 됨. 

- HAT -> CHAT & HAT -> AT: 추가할 때 ID의 중복 없이 추가하기 때문에 적용순서와 상관 없이 정확한 위치에 해당 문자가 삽입된다. 

- HAT -> AT & HAT -> AT: 마찬가지로 ID를 기반으로 삭제하기 때문에 중복 삭제 문제도 발생하지 않습니다. 

- 단점: OT보다 많은 메모리 소모, 문자열 스트림외에 id를 저장하는 메모리 필요로 함. Peer-to-peer 통신이 항상 가능하지 않기 때문에, peer 간 직접 통신을 해야한다는 CRDT는 단점으로 작용할 수 있다. 패킷 전송 중계하는 서버를 필요로 할 수 밖에 없는데, 결국 서버 부하가 증가하게 된다. 또한 고유 ID를 기반으로 하기 때문에 동기화 결과 문자열이 섞일수도 있음. 그렇기 때문에 OT보다 복잡한 구현을 필요로 한다. 

 

Figma tech blog: How Figma's multiplayer technology works  (2019)

- OT 는 text-based app에 가장 적합함. low memory를 가지는 긴 text 문서를 편집하는데 좋지만, 정확히 구현하는 데 복잡함. 가능한 states가 combinatorial explosion이 가능하기 때문. 

- Figma의 목적 이 작업자체에 필요한 것보다 더 복잡하지 않았으면 좋겠다 였음. 더 간단한 시스템이 더 implement, debut, test, maintain하는 데 더 쉽게 만들기 때문. OT대신에 CRDT에 영향을 받았음. (CRDT는 분산시스템에서 잘 이용되는 갖가지 데이터구조를 뜻한다.) 

- 모든 CRDT들은 최종적 일관성을 보장하는 수학적 특성을 만족한다. 더이상의 업데이트가 일어나지 않으면 결과적으로 그 데이터 구조에 접근하는 모두가 똑같은 걸 보게된다는 뜻이다. 

- CRDT에는 많은 타입이 있다. Grow-only set(element의 집합. 더하는 업데이트만 허용됨. ) & Last-writer-wins register(update는 새로운 value, timestamp, peerID로 구성되어 있음. 최신 value가 value of register 를 결정한다. ) CRDT 자체는 최종 상태를 결정하는 하나의 central authority 가 없는 탈중앙화된 시스템을 위해 디자인 되었기 때문에, 피할수 없는 성능, 메모리 오버헤드가 동반된다. Figma는 중앙화되어있고, 여분의 오버헤드를 없애 더 단순화 시켜서 더 빠르고 lean한 구현을 할 수 있다. 

- Figma의 data structure는 하나의 CRDT가 아니다. 그 대신 여러개의 CRDT에 영감을 받았고, 그것들의 조합으로 최종 data structure 를 만들었다. 

- CRDT를 공부하는 것이 correct system을 구축하기 위해 중요하고, 어플리케이션에 따라서 requirement를 relax해서 사용하면 된다. 

- Single root (entire document) ->  Page objects -> 하나의 page object아래에 hierarchy of object가 있다. 

- Map<ObjectID, Map<Property, Value>>  의 형태를 가짐. 

- Syncing object properties: 중요한 점은 변화의 결과가 atomic하다는 점이다. 이는 eventually consistent value 는 어떤 한명이 보낸 값이 되어야 한다는 것이다. 이는 text 가 왜 피그마에서 안되는지에 대한 점을 설명해줄 수 있는데, B를 AB랑 BC로 두명이 변경했을 때 사실 ABC로 되어야하는데 이 특성을 가지고는 ABC로 되지 않는 다는 것이다.

conflicting change가 있을때는 어떻게 해결하는가? 클라이언트단에서 property change는 server의 acknowledgement 를 기다리기 전에 바로 적용된다. 그러나 이렇게 하면 server에서 conflicting change가 들어오면 overwrite되면서 flickering 되는데, 이 행동을 피하고 싶다면 어떻게 해야할까? best prediction을 보여주기 위해서 server에 늦게 들어가는 것이 recent change가 되고, unacknowledged property change와 conflicting 한다면 discard하는 방식으로 한다. 

- Syncing object creation and removal: Object creation 은 last-writer-wins set과 비슷하다. 큰 차이점은 삭제될 때 server에서 properties까지 다 삭제한다. 그리고 undo buffer에 저장되어서 클라이언트가 restore할 수 있게 허용한다. 클라이언트가 오브젝트를 생성할 때 object id는 유일해야하는데 이는 object id에 unique client id를 포함시켜서 구현할 수 있다. work offline도 지원해야하기 때문에 새로 생기는 object에 대해서 server가 unique id를 줄 수 없다. 

 - Syncing trees of objects: eventually-consistent tree structure안에 object들을 배열하는 건 가장 어려운 일이다. 이 시스템에서 complexity는 reparenting operation에서 나온다. 두가지 main 목표가 있었는데, 첫번째는 reparenting과 unrelated properties를 바꿀때 충돌하지 않아야 한다는 것, 두번째는 같은 object를 동시에 reparenting 할 때 separate place로 두개의 copy가 생기지 않도록 하는 것이다. reparenting 을 하는 많은 접근들은 우선 obejct를 삭제하고 새로운 ID를 가지는 object를 새로 생성한다. 이건 concurrent edits가 불가능해지기 때문에 적용이 불가능하다. 그래서 figma에서 적용한 방식은 Parent-child relationship를 링크로 저장하는 것이다. Parent와의 link를 children에게 저장해 놓기 때문에, multiple parents로 끝나지 않게 된다. 이 링크는 Graph 안의 directed edge로 존재하게 되는데, 어떤 restriction 도 없으면 cycle이 없는 valid tree인지 확신하기 어렵고 그렇기 때문에, server에서는 cycle을 만들수 있는 parent property update를 거절할 수 있도록 해야한다. Figma 의 server는 궁극적인 authority를 가지고 있기 때문에, client 는 server에서 내려오는 변화를 거부할 수 없다. 그래서 figma에서는 아래 그림처럼 서로 parent 로 만들어서 server가 client의 변화를 거절할때 까지 tree에서 그들을 삭제한다. 이 솔루션은 사실 object를 일시적으로 삭제하기 때문에 좋진 않다. 하지만 드문 일시적 문제에 대해서는 단순한 솔루션이라서 더 복잡한 솔루션을 적용하지 않았다고 한다. (예를 들면  클라이언트 측에서 cycle을 방지하는 것처럼) 

 

Tree를 construct하기 위해서는 children 의 순서를 결정해야한다. fractional indexing이라는 기술을 쓴다. high. level에서 object의 위치가 parent의 배열의 0, 1 사이의 값을 가진다. Object의 children의 순서는 position으로 그들을 sorting해서 얻게 된다. 두개 object 사이에 새로운 값을 넣으려면 그 사이의 값을 가지게 되는 것이다. 중요한 점은 position정보와 parent link의 정보가 하나의 single property로 저장이 되어서 atomic하게 업데이트가 되어야한다는 것이다. 

 

Implementing Undo: Undo history가 single-player mode 에서는 자연스럽지만,  multiplayer 환경에서는 confusing하다.  그래서 멀티 환경에서 principle을 정하게 되었다: undo를 많이 하고, 어떤 것을 copy하고, redo back tothe present를 하면 document는 바뀌지 않을 것이다. 이것은 명확해 보이지만 single player 구현에서는 redo 는 내가 한 것을 되돌려 놓는 것이고, 이런 것은 결국 다른 사람들이 해놓은 것을 overwrite할 수 있는 것이다. 그래서 undo operation이 redo history를 바꿔놓고 redo operation이 undo history를 바꾸도록 한다. 

 

 

 

Reference 

- https://josephg.com/blog/crdts-are-the-future/

- https://www.samsungsds.com/kr/insights/document_collaboration.html

하이브리드 업무 시대에 더욱 주목받는 실시간 문서 협업, 어떻게 가능해졌을까?

https://www.figma.com/blog/how-figmas-multiplayer-technology-works/

How Figma’s multiplayer technology works

 

What to read next 

https://velog.io/@heelieben/%EC%8B%A4%EC%8B%9C%EA%B0%84-%EB%8F%99%EC%8B%9C-%ED%8E%B8%EC%A7%91-OT-%EC%99%80-CRDT 

실시간 동시 편집 : OT 와 CRDT

https://www.figma.com/blog/realtime-editing-of-ordered-sequences/