Figma의 multiplayer technology works

* 본 글은 Figma의 'How Figma's multiplayer technology works' 글을 키워드 중심으로만 간략히 살펴보고 이것저것 적은 내용입니다. 원문의 완벽한 번역글이 아니므로, 자세하고 정확한 내용은 아래 본문을 보시면 좋을 것 같습니다! 

 

 

How Figma’s multiplayer technology works

 

---

들어가며

Figma에서 멀티플레이어 기능을 개발하기 시작했을 때, 그들은 자체적인 솔루션을 개발하기로 결정했다고 한다. 다른 디자인 도구에서는 멀티플레이어 기능을 제공하지 않았으며, Google Docs와 같은 앱에서 주로 사용되는 멀티플레이어 알고리즘인 Operational Transforms(a.k.a OTs)을 피그마는 사용하고 싶지 않았기 때문으로 보인다.

 

(여기서 OT(Operational Transforms)란?

모든 변경사항을 기록했다가, 공통으로 사용하는 서버에 순차적으로 전송하고, 들어온 순서대로 순차적으로 실행해 최종 상태를 만들고 이를 다시 클라이언트에게 주는 방식이다.

마틴클랩만의 유튜브 'CRDTs: The Hard Parts'

이러한 OT 방식은 중앙에 집중된 서버를 무조건 필요로 하고, 이는 많은 양의 내용을 처리해야할 때 서버에 부담을 줄 수 있다는 단점이 있다. 변화가 일어났을 때 서버에 반영되기 위해 그 변화들이 대기하고 있고, 서버는 각 유저의 변화를 순서대로 모으고 실행해 다시 클라이언트에게 전달해준다. 다른 유저와 직접적으로 연결될 방법은 기본적으로는 없다.

 

또한 기본이 되는 알고리즘 아이디어는 간단하지만 기준이 되는 인덱스가 계속 변할 수 있어서, 충돌 해결에 있어 꽤 복잡할 수 있다고 생각했는데, 이러한 이유들 때문에 OT 대신 더 나은 알고리즘을 찾으려고 한 것 같다.

 

피그마는 빠르게 출시할 수 있는 기능을 중요시했고, OTs는 피그마가 다루는 문제에 있어서는 불필요하게 복잡한 경향이 있었다. (예외처리 등) 그래서 피그마는 더 간단하고 구현하기 쉬운 맞춤형 멀티플레이어 시스템을 구축했는데, 그 커스텀 멀티플레이어 시스템으로 우리는 지금 피그마의 소프트웨어를 사용하는데 있어 작업 중인 사람을 방해하지 않고 디자인 프로젝트의 최신 상태를 실시간으로 볼 수 있게 되었다. 그럼 피그마가 어떻게 멀티플레이어 모드를 구현했는지 알아보러 가자!

 

 

---

들어가며 2 - Background Context: Figma's setup, OTs, and more

 

피그마의 멀티플레이어 프로토콜에 대해 이야기하기 전에, 멀티플레이어 시스템이 대략적으로 어떻게 구성되어 있는지에 대한 배경 정보를 살펴보자. 피그마는 클라이언트/서버 아키텍처를 사용하고 있는데, Figma에서 클라이언트 단은 '웹 페이지'이며, 웹소켓을 통해 서버군과 통신한다. 각 멀티플레이어 문서마다 별도의 프로세스를 생성하는 구조를 가지고 있는데 그 내용은 다음 아티클을 참고하면 좋을 것 같다.

How Mozilla’s Rust dramatically improved our server-side performance

 

문서가 열리면, 클라이언트는 파일의 카피본을 다운로드하여 시작한다. 그 이후로는 웹소켓 연결을 통해 문서를 양방향으로 동기화할 수 있게 구조를 잡는다. 피그마는 임의의 시간 동안 오프라인 상태에서도 편집이 가능하도록 하는데, 만약 다시 온라인으로 상태가 돌아온다면 클라이언트는 문서의 최신 사본을 다시 다운로드하고, 이 최신 상태 위에 오프라인에서 했던 편집들을 다시 적용한 후 새로운 웹소켓 연결을 통해 업데이트를 동기화한다. 이러한 방식은 연결이나 재연결하는 과정이 간단하고, 멀티플레이어 버전 구현 시 집중해야하는 문제는 어떻게 문서를 업데이트해주냐는 것만 남게 된다. (대략적으로)

 

피그마는 가설의 빠른 검증을 위해 코드 베이스 환경에서의 작업보다 프로토타입 환경을 통해 아이디어를 테스트함을 택했다. 웹 페이지에는 세 개의 클라이언트가 서버에 연결되어 있고, 시스템의 모든 상태를 시각화해준다. 이 프로토타입 환경을 통해 오프라인 클라이언트, bandwidth 제한된 연결 등에 대한 다양한 시나리오를 쉽게 설정하고 테스트해볼 수 있다고 한다. (아래는 internal 프로토타입의 스크린샷)

 

시뮬레이션 환경이 제공되어 있다는 것이 새로운 알고리즘 제작과 동작확인에 효과적이겠다고 생각했다.

 

figma, how-figmas-multiplayer-technology-works

 

---

How OTs and CRDTs informed our multiplayer approach

본격적으로 기존의 동시편집 알고리즘을 활용해 어떤 동시편집 로직을 작성했는지 살펴보기

 

멀티플레이어 기술은 많은 역사를 가지고 있으며, 1968년 Douglas Engelbart's demo (https://en.wikipedia.org/wiki/The_Mother_of_All_Demos) 이후로 존재했을 가능성이 있다고 볼 수 있습니다. 피그마 자체 멀티플레이어 시스템이 어떻게 작동하는지 자세히 알아보기 전에, 피그마 시스템에 영향을 미친 전통적인 접근 방식에 대해 간단히 살펴볼텐데, 바로 OTs와 CRDTs 이다.

 

OTs는 Google Docs와 같은 대부분의 협업 기반 텍스트 앱에 사용되는 기술이다. OTs는 가장 잘 알려진 기술이지만, 피그마가 달성하고자 했던 목표에 비해 오버헤드가 컸다. OTs는 메모리 사용과 성능에 부담이 적은 긴 텍스트 문서를 편집할 수 있는 훌륭한 방법이지만 매우 복잡하고 올바르게 구현하기 어렵기 때문이다. (가능한 상태의 조합 경우의 수가 굉장히 많아지는 일이 발생하며, 이해하기 어려운 문제가 있음) 피그마 팀이 멀티플레이어 시스템을 설계할 때 세운 주된 목표는 일을 수행하는 데 필요한 것 이상으로 복잡하게 구성하지 않도록 하는 것이었기 때문에 CRDT를 기반으로 멀티플레이어 시스템을 구성한 것으로 보인다. 

 

Figma의 기술은 CRDTs라는 개념에서 영감을 받았는데, CRDT는 Conflict-free Replicated Data Types의 약자로 분산 시스템에서 흔히 사용되는 다양한 데이터 구조를 의미한다. 

 

간단한 OT와 CRDT의 설명은 아래 유튜브와 블로그에서 잘 설명되어 있었다.

CRDT vs OT

 

CRDT의 유형

1. Grow-only set

2. Last-writer-wins register

 

Grow-only set은 전체 집합에 요소를 추가하는 식의 아이디어다. 집합에 요소를 추가하는게 유일한 업데이트 유형이고, 이는 업데이트를 어떤 순서로 적용하든 집합의 내용을 결정할 수 있다. 

 

Last-writer-wins register 방식은 새로운 값, timestamp, peer ID로서 업데이트가 이뤄질 수 있고 최신 업데이트 값을 가져와서 레지스터의 값을 결정할 수 있다. (피그마에서 사용하는 방식이 완벽히 이 두 유형을 따라가는 것은 아니고, 중앙 서버 + CRDT의 장점을 살린 접근을 활용하는 것 같다.)

 

---

How a Figma document is structured

Figma의 문서는 HTML DOM과 유사한 객체 트리로 이루어져있다. 문서 전체를 나타내는 단일 루트 객체가 있고 루트 객체 아래에는 페이지 객체가, 각 페이지 객체 아래에는 페이지의 내용을 나타내는 객체들의 계층 구조가 있다. 각 객체는 ID와 값으로 구성된 속성의 컬렉션을 가지고 있는데 이는 Map<ObjectID, Map<Property, Value>>  와 같은 구조를 가지고 있다고 생각할 수도 있고, 또 다른 방법은 (ObjectID, Property, Value) 와 같은 튜플을 저장하는 행을 가진 데이터베이스로도 생각할 수 있다. 이러한 맥락을 바탕으로 피그마에 새로운 기능이 추가된다는 것은 객체에 new properties가 추가된다고도 생각할 수 있겠다.

 

---

The details of Figma's multiplayer system

1. 객체 속성 동기화하기 (Syncing object properties)

피그마의 멀티플레이어 서버는 클라이언트가 특정 객체의 특정 속성에 보낸 최신 값을 추적한다. 이는 서로 다른 두 클라이언트가 동일한 객체의 서로 다른 속성을 변경하면 충돌이 발생하지 않으며, 두 개의 클라이언트가 서로 다른 객체의 동일한 속성을 변경해도 충돌이 발생하지 않는다. 충돌이 발생할 때는 '서로 다른' 클라이언트가 '동일한 객체'의 '동일한 속성'을 변경할 때 발생하며, 이 경우 문서는 서버로 전송된 마지막 값을 가지게 된다. 이 접근 방식은 CRDT의 last-writer-wins register과 유사하지만 timestamp가 필요하지 않다. 서버는 이벤트 순서를 정의할 수 있기 때문!

 

(서버로 모든 것 보낸 후 변경사항 클라이언트들에게 전송)

 

동일한 객체에서 서로 다른 속성을 변경할 때 (충돌X)

 

주어진 속성에 대해 최종적으로 일관된 값은 항상 클라이언트 중 하나가 보낸 값이다. 이것이 Figma에서 동시에 동일한 텍스트 값을 편집할 수 없는 이유인데, 텍스트 값이 B이고 누군가가 AB로 변경하는 동시에 다른 사람이 BC로 변경한다면, 최종 결과는 AB 또는 BC가 될 것이지만 ABC는 될 수 없다.

 

 

클라이언트에서의 충돌처리 방법에 따른 깜빡임 현상 (flickering)

충돌하는 변경 사항이 있는 경우 클라이언트에서 충돌을 처리하는 방법을 선택할 수도 있다. 클라이언트에서 속성 변경은 가능한 한 신속하게 적용되기 때문에 서버로부터 확인을 기다리지 않는다. 그러나 이렇게 하면 서버에서 수신한 모든 변경 사항을 적용하는 동시에 충돌하는 변경 사항이 때로는 "깜빡임" 현상이 발생할 수 있다. 오래된 확인된 값이 임시로 최신 미확인된 값 위에 덮어씌워질 수 있기 때문이고, 이 깜빡임 현상을 피하고자 아래와 같이 적용할 수 있다. 

 

이게 무슨 말이냐면 동시성 제어와 충돌 해결에 관한 내용인데, 클라이언트와 서버는 지속적으로 데이터를 동기화해야한다는 것을 먼저 이해해야 한다. 그리고 서버와 클라이언트 사이의 데이터 동기화에서 충돌이 일어날 수 있고, 그걸 처리하는 과정에서 깜빡임이 발생할 수 있다는 얘기다. 

 

간단 예로 가정하자면, 온라인에서 어떤 문서를 편집하고 있는 상황이다. 이 문서는 클라이언트(우리 컴퓨터)와 서버에 모두 저장되어 있다. 문서 내용을 바꾸면, 변경사항은 먼저 클라이언트에 적용되고, 그 다음에 서버에 전송된다. 그럼 사용자는 변경사항이 즉시 적용된 것처럼 느낄 수 있는데, 이런 걸 '옵티미스틱 업데이트'라고 부른다. 그런데 문제는 우리가 문서를 편집하는 동안 서버 측의 문서도 바뀌었다면, 우리가 전송한 변경사항과 서버의 변경사항 사이에 충돌이 일어날 수 있다는 것이다. 이런 경우엔 충돌을 해결해줘야 한다. 

 

한 가지 전략은 클라이언트에서 변경 사항을 먼저 적용하고, 서버에서 받은 모든 변경사항을 그 위에 적용하는 방법이다. 하지만 이렇게 하면 충돌하는 변경사항 때문에 '깜빡임' 현상이 생길 수 있다. 즉, 우리가 보낸 변경사항이 잠시 적용되었다가 서버의 변경사항으로 덮어씌워진다는 것이다. 이 '깜빡임' 현상을 피하기 위한 다른 전략은 서버에서 받은 변경 사항 중에서 우리가 보낸 변경사항과 충돌하는 부분을 무시하는것인데, 왜냐하면 우리가 보낸 변경사항이 가장 최근의 것이고(최근의 것이라고 믿고), 따라서 '최고의 예측'이라고 생각하기 때문이다. 이럴 때는 사용자 경험이 향상되지만, 충돌 해결을 위한 추가적인 로직이 필요하다.

 

두 클라이언트 사이에서의 충돌에서 flickering을 방지하는 방법, 충돌하는 부분 무시

 

---

Syncing object creating and removal

객체 생성과 객체 삭제는 명시적으로 동작하는데, 먼저 객체를 삭제하게 되면 해당 객체에 대한 모든 데이터, 즉 모든 속성이 서버에서 삭제된다. 서버에서 삭제된 대신 이 데이터는 삭제를 수행한 클라이언트의 undo 버퍼에 저장되고, 그 클라이언트가 삭제를 취소하려면 삭제된 객체의 모든 속성을 복원해야하는 책임이 있다. (정확히는 있다고 봄)

생성에 있어서는 두 개의 클라이언트가 동일한 객체 ID를 가지면 안되므로, 모든 클라이언트에게 고유한 ID를 할당하고 새로 생성된 객체 ID의 일부로 클라이언트 ID를 포함시켜 중복을 방지할 수 있다.

 

 

Syncing trees of objects

객체는 최종적으로 일관된 트리 구조로 정립되어 있어야 한다. 트리 구조를 설계할 때 목표로 한 아래 두 가지를 살펴보면 어떻게 동작해야할지 유추할 수 있다.

 

1. 객체의 속성 변경과 reparenting (구조 변경, 부모 재조정)이 충돌해서는 안된다. 누군가가 객체의 색상(속성의 예시)을 변경하는 동안 다른 사람이 객체를 reparenting하는 경우, 이 두 작업은 모두 성공해야 한다. (각각의 노드는 고유하다) 

2. 동시에 동일한 객체에 대한 두 개의 reparenting 작업은 트리의 다른 위치에 두 개의 복사본이 생성되는 일이 결코 없어야 한다. (reparenting 작업은 충돌 발생이 가능한 경우, resolve 해주고 각각 클라이언트가 가지고 있는 복사본은 서로 같은 상태를 가지고 있어야 한다.)

 

reparenting할 때 보통 상태 자체를 저장하고 원래 객체를 삭제, 새 ID로 다른 위치에 재생성하는 방식으로 나타낼 수도 있지만 이는 객체의 식별이 변경되므로 동시 편집이 깨질 수 있다는 문제가 있다. 대신 부모-자식 관계를 저장함으로써 기존 식별 정보를 보존하고 동시편집을 유지할 수 있다.

 

그러나 이는 방향이 있는 그래프를 형성할 수 있게 된다. (사이클이 없는 유효한 트리라는 것을 보장할 수 있는 방법이 없음, 한 클라이언트가 A를 B의 자식으로 만들고 다른 클라이언트가 B를 A의 자식으로 만드는 동시편집의 경우를 예로 들 수 있음) 그러면 A와 B는 서로 상호적으로 부모가 되어 사이클을 형성해 트리가 아니게 되는 문제가 발생한다. 

 

Figma의 멀티플레이어 서버는 순환을 일으킬 수 있는 부모 속성 업데이트를 거부하므로, 이 문제는 서버에서는 발생하지 않을 수도 있다. 하지만 클라이언트에서 여전히 발생할 수 있는데, 클라이언트는 서버에서의 변경을 거부할 수 없기 때문이다. 왜냐하면 문서의 최종 형태에 대한 권한은 서버가 우선시되기 때문이다. 그러므로 클라이언트는 B를 A의 자식으로 하는 변경을 서버에 보내고 아직 확인되지 않은 상태에서 서버에서 A를 B의 자식으로 하는 변경을 받는 상태에 놓일 수 있다. (이 경우가 받아들여지는 경우는 속성에 대한 충돌이 아니어서 둘다 수용 가능한 변경이기 때문) 클라이언트의 변경은 순환을 형성하므로 서버에서 거부될 것이지만, 클라이언트는 아직 이것을 모른다.

 

(일단 순환을 만든 것이 클라이언트에 반영되고, 그 다음 불가능한 상황이라는 신호가 클라이언트로 나중에 전달되는 상황이 아래 그림과 같음) 

 

<문제상황>

An animation of a reparenting conflict

 

<해결책> 

 

해결책은 이러한 객체들을 일시적으로 서로의 부모로 만들고, 서버가 클라이언트의 변경을 거부하고 객체가 그것이 속한 곳으로 다시 부모화될 때까지 트리에서 제거하는 것이다. 이 해결책은 객체가 일시적으로 사라지게 된다는 단점이 있지만, 이는 잘 일어나지 않을 부분에 대한 문제 해결이므로 더 복잡한 방법을 시도할 필요를 느끼지 않았다고 한다. (common case에 더 집중하는 모습인듯)

 

(참고: 트리를 구성하려면 주어진 부모의 자식들의 순서를 결정하는 방법도 필요하다. Figma는 이를 위해 "fractional indexing"라는 기법을 사용한다. 하이레벨에서 보면, 객체의 위치는 부모의 자식 배열에서 0과 1 사이의 분수로 표현될 수 있다. 객체의 자식들의 순서는 숫자 크기에 따라 정렬될 수 있고, 다른 두 객체 사이에 객체를 삽입할 수도 있다. (삽입은 두 객체 간의 평균을 이용해 새로운 객체의 표현값을 정할 수 있다.))

 

 

Implementing undo 

멀티플레이어 상황에서 undo처리는 꽤 복잡할 수 있다. 

undo에 대한 행동 정의는 싱글 플레이어 모드에 대해서는 꽤 자연스럽지만 멀티플레이어 환경에서의 undo 과정은 어떤 행동을 해야하는지도 꽤 혼란스러울 수 있을 것 같다. 만약 다른 사람들이 우리가 편집하고 실행 취소한 같은 객체를 편집했다면, 무슨 일이 일어나야 할까? 우리의 이전 편집이 그들의 나중 편집 위에 적용되어야 할까? 혹은 재실행에 대해서는 어떻게 할까? 

 

정하기 나름이라고 생각하지만, 일단 내가 한 action에 대해서만 undo와 redo를 행하는 게 주요하다고 생각했다. 내가 한 것을 되돌리는 것!

An animation showing undo and redo history modification

 

• 실행 취소는 내가 방금 실행한 action의 reverse 버전을 적용하는 것
• 만약 실행 취소로 인해 객체가 이동하게 되면, 그 객체는 원래의 부모로 되돌아가는 것이 아니라 그것이 이동되기 전에 있었던 위치로 되돌아간다. (1 action에 대한 undo)

예를 들어, 우리가 어떤 텍스트를 작성하고 다른 사람이 그 텍스트의 색상을 변경했다고 생각할 수 있는 상황에서 우리가 '실행 취소'를 하면 내가 작성한 텍스트가 사라지지만, 색상 변경은 그대로 남아있을 것이다. 그리고 만약 당신이 '재실행'을 한다면, 당신이 작성한 텍스트가 상대방이 변경한 색상과 함께 다시 나타나게 될 것이다. 여기서 중요한 것은 '실행 취소'나 '재실행'이 다른 사람의 편집을 덮어쓰지 않는다는 것이고, 이렇게 함으로써, 여러 사람이 동시에 작업하더라도 일관성을 유지할 수 있겠다.

 

클라이언트의 각 편집에 대한 변경 사항을 추적하고, 이를 undo 스택에 추가한다. 그런 다음 사용자가 실행 취소를 선택하면, 클라이언트는 undo 스택의 가장 위에 있는 항목을 선택하고, 각 변경에 대해 이전 값을 복구하려고 시도한다.