마 니 요즘 왜 글 안쓰는데?

오랜만에 글을 쓰는거 같다. 글을 썼는지 2달이 다 되어간다. 1월 중순부터 2월달 동안 스마일게이트 온라인 개발 캠프 때문에 정신이 없었던 것 같다. (스마게 회고록도 써야되는데 언제 쓰지,,,?)
이리저리 바쁘게 치여다니면서 스마일게이트 온라인 개발 캠프도 진행을 했었고, 일본 여행도 다녀왔었다.
3월이 되면서 학기도 이제 시작이 되었고, 여러가지 일을 맡게 되었다.
멋쟁이 사자 아기사자 면접이라던가,,,공식 홈페이지 개발 TF가 된다던가 (사실 급하게 준비한다고 기대도 하지 않았는데 되어버려서 좀 깜짝 놀랐다). 학기에 진행하는 종합프로젝트 2도 회의때문에 정신이 없는것 같다. 웹마스터, 해달 트랙 등등,,, 일 벌리는 건 참 잘하는 것 같다. (올해도 난항이 예상된다.)

이 와중 GDSC라는 동아리도 개인적인 애정을 갖고 있었기 때문에 경북대 GDSC만의 홈페이지를 만들어 보자는 목표를 간직하고 있었다. 그래서 3기 수료 전까지 마지막으로 진행하게 되는 2차 프로젝트 대신 사람들을 모아 GDSC 홈페이지를 기획하게 되었고, 기획 도중 실시간 편집에 관련된 기능을 구현하기로 하였고 이 기능에 관련하여 고민과 공부한 내용을 적어볼까 한다.

---

동시편집? CRDT? OT?

다들 동시편집하면 어떤걸 떠오를까? 노션? 피그마? Draw.io?
협업을 조금이라도 해보셨으면 알겠지만 다들 동시편집 도구의 시대에 살고 있다.

동시편집의 도구를 사용하게 되면서 우리는 대면이 아닌 온라인을 통해 하나의 문서를 동시에 편집하고, 실시간으로 여러 사람들의 편집 내용이 각자 편집 화면에 바로 반영되면서 각자 의사소통을 보다 수월하고 쉽게 할 수 있다.
하지만 동시편집은 구현상 분산된 환경에서 복잡한 문제를 가지고 있고, 그런 모호함을 해결하기 위해 여러 기술들이 사용되고 있다.

그래서 여러 기술이 뭔데?

동시 편집 기술의 핵심은 동시 협업 시 일어나는 충돌을 처리하는 것이며, 충돌처리 방법 또한 여러 방식이 존재한다.

OT(Operational Transformation)

주 사용처 : Google Docs, Google Wave, MS Office

오래전부터 사용했었던 기술이다.
OT(Operational Transformation)이란 입력한 순서에 따라 서버가 이를 적절히 변형하여 전달하는 방식이다. OT는 시간상의 순서를 고려해 우선순위를 부여하고, 앞에서 적용한 변경사항이 다음 순위의 변경사항을 보정하는 정보로 사용된다.

OT 동작원리

Google Docs를 사용하여 User1과 User2과 동시에 같이 편집한다고 했을때, 한명은 helo안에 l을 넣고, 다른 한명은 !를 추가한다고 가정해보자.

이때, 변경사항은 인덱스 위치를 이용해서 l을 인덱스 3에 넣고, !를 인덱스 4에 넣는 일이 발생하게 된다.
이 2가지의 변경사항을 서버에 요청을 하게 되고, 서버가 받아서 통합한다.

l을 인덱스 3에 먼저 넣게 될 경우, 원래 !가 인덱스 4에 들어가야되는데, 이미 인덱스 3이 들어가서 위치가 바뀌어 버리게 된다.

그래서, 인덱스 위치가 바뀌어 4가 아닌 5에 넣게 된다. 이렇게 오퍼레이션이 이전 동작에 의해 바뀌게 되어 다음 동작을 변환(transform)을 시켜주는 것을 OT라고 하고 Operational Transform이라고 한다.

결론을 얘기하자면
1. 모든 변경 사항 기록
2. 서버에 전부 전송
3. 순차적으로 실행
4. 클라이언트에 데이터 전송 및 화면 렌더링
의 순서대로 실행하게 된다.

OT의 문제점

OT는 모든 변경사항을 서버에게 전부 전송하면 변경 사항을 순차적으로 변경해서 화면을 렌더링을 한다. 하지만 이 과정에서 여러 문제점이 있다.

• 서버 과부화
  • 유저는 모든 변경사항을 서버에 전부 전달할때 다른 유저들의 변화를 알아차릴 수 있는 방법이 없다. 그래서 transformation이라는 주체의 서버에서 변환을 진행한다.
    따라서, OT는 중앙 집중식 서버/DB가 필요하다. 하지만 이런 과정에서 트래픽이 몰리게 되면 과부화가 올 수 있다.
    

    가끔씩 과부화로 문서 경고창이 뜰 수 가 있다.

  • 또한 중계 서버에서 operation 패킷이 전송된 뒤에 응답을 받을 수 있어서 응답 시간이 매우 길다.

OT 오픈소스

• SharedDB: JSON 문서 협업을 위한 풀 스택 라이브러리
• Rustpad: OT 기반의 소스 협업 텍스트 편집기
  (https://github.com/ekzhang/rustpad)
  • Rustpad는 완전히 자체 호스팅되며 작은 Docker 이미지에 적합하며 데이터베이스가 필요하지 않는다.
• Jot
  • node.js 및 브라우저에서 사용하기 위해 JavaScript로 작성된 JSON 데이터 모델에서 OT 구현
  • 다른 오픈소스처럼 문자열 작업은 JSON에서 인코딩할 수 있는 모든 종류의 데이터에 대해 작업 가능

CRDT(Conflict-Free-Replicated Data Types)

주사용처 : Figma(UX/UI 프로그램), Redis, Riak, Workie , Apple Notes

동시 편집 기술 초기에는 OT가 주류였으나, 현재에는 CRDT 방식이 인기를 얻고 있다. CRDT는 중앙 서버가 필요 없고, 문서를 편집하는 유저들끼리만 데이터를 교환하면 되므로 속도가 빠르고 서버의 부하를 줄이는 효과가 있다.

OT는 편집 시간과 인덱스를 기반으로 변경사항을 보정하는 것과 다르게, CRDT는 스트림 상의 각 문자에 고유한 id를 부여하고, 이를 기반으로 보정을 정의한다는 차이점이 있다.

한마디로 OT는 순서가 중요하고, CRDT는 순서가 상관 없고 operation만 같으면 어긋나더라도 같은 상태가 된다는 점이다.

CRDT 동작원리

CRDT는 변경사항을 보정할 필요 없이 바로 다른 유저의 문서에 적용된다. 유저1이 'l' 추가하는 경우, 새로운 아이디인 3.5로 부여하고 문자를 id가 4인 문자의 위치에 추가합니다. 그리고 유저2의 환경에서 변경사항을 받아 적용할 수 있습니다. 유저2가 id가 5인 문자를 삭제하는 변경도 마찬가지로 유저1에서 변경사항을 적용할 수 있게됩니다.

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

CRDT 문제점 1 (Interleaving Problem)

하지만 CRDT도 완벽한 것은 아니다. 예시처럼 두 글을 합치게 됐을때 이런 충돌이 일어나게 된다.

앞서 얘기했던 것처럼 CRDT는 unique한 id값을 가지게 된다. 그래서 우리가 의도하지 않았던 대로 독립적으로 글자들이 랜덤화된 값에 의해 merge가 되는 것이다. 그래서 alice와 charlie의 글자들을 정렬했을 때 이상한 글자로 나오게 된다.

그래서 CRDT의 문제를 보완하기 위해 여러 추가 알고리즘 기법들이 존재한다.

• Logoot
• LSEQ
• RGA
• Treedoc
• WOOT
• Astrong

이런 다양한 알고리즘들이 있는데 이런 것이 있구나 하고 넘어가면 될것 같다.

CRDT 문제점 2

또한 다른 문제점들도 존재한다.

우선 OT보다 많은 메모리를 사용한다. 고유 id 값을 저장하는 메모리와 이를 트리구조로 관리하기 위한 메모리를 필요로 하기 때문에, 일반적인 문서보다 2~3배 더 큰 메모리를 사용하게 된다.

또한 Peer-to-Peer 통신이 항상 가능하지는 않다.
보안이 강화되면서 방화벽 등에 의해 Peer 간의 직접 접속이 힘든 상황이 생길 때, 이를해결하기 위해 결국 패킷 전송을 중계하는 서버를 이용할 수 밖에 없게 된다. 결국 특정 서버에 부하가 증가하게 되는데 이는 CRDT의 중앙 서버가 없다는 핵심 장점이 무색해진다는 점이다.

CRDT 오픈소스

• Automerge : 현재 문서가 커질수록 내부의 트리 기반 데이터 구조가 커지고 느려진다.
  그래서 Immutablejs를 많이 사용하여 메모리 사용량이 증가하고 성능이 저하된다고 한다. 결론적으로 얘기하자면 사용하는데는 비추인 것 같다. Automerge는 현재 성능을 개선한 Rust 버전을 별도로 구현중이라고 한다.

• Yjs : Automerge와 똑같이 트리 구조를 사용하지만 모든 항목을 단일 플랫 목록에 넣어 데이터 구조를 개선하였다. 문서 기반 협업 도구를 만든다면 성능이 좋고, 메모리 사용량이 적은 “Yjs”을 추천한다.

• Yorkie : AutoMerge나 Yjs와 같은 라이브러리와 달리 SDK, Server, DB를 포함하여 공동 편집 기능을 쉽게 구현할 수 있도록 한다. 또한 제일 중요한 점은 한국인 개발자가 이 라이브러리를 만들었다는 점이다!(TMI긴 하지만 개발자 분께서 키우시는 강아지가 요크셔테리어라서 Yorkie라고 지었다고 한다.)

결론

CRDT도 OT를 해결하기 위한 알고리즘으로 나왔긴 하지만 결국에는 완벽한 알고리즘은 아닌 것 같다. 하지만 이를 보완해주기 위해 여러 알고리즘들이 나오고 있고 중앙 서버가 필요 없고 유저들 끼리 변경사항을 주고 받을 수 있어서 속도가 빠른점에서 무시할 수 없는 알고리즘 인 것같다.

참고자료

• CRDT, OT 관련 링크들

  • 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
  • https://velog.io/@ninikim/%EB%8F%99%EC%8B%9C-%ED%98%91%EC%97%85-%EA%B8%B0%EC%88%A0-%EB%A6%AC%EC%84%9C%EC%B9%98
  • https://channel.io/ko/blog/crdt_vs_ot
  • https://josephg.com/blog/crdts-are-the-future/
  • https://news.hada.io/topic?id=4744

• 참고한 이미지 및 gif 자료들

  • 구글 문서 경고창 이미지 : https://m.blog.naver.com/toruin84/222972642990
  • 노션 사용하는 방법: https://m.blog.naver.com/freewill_life/221918238701