FIGMA는 어떻게 동시편집을 구현했을까?-1
| topics | 403 시스템 설계 |
| references | |
| types | 레퍼런스 |
피그마는 동시편집을 가능케하기 위해 어떤것을 고려했고 어떻게 설계했는지를 피그마의 기술블로그와 기본개념을 익히며 정리해보았음.
FIGMA는 왜 CRDT를 사용했을까
동시 편집 - OT,CRDT 여기에 간단하게 OT,CRDT개념을 적어놓았다.
동시문서편집 흐름
- 문서가 열린다
- 파일사본을 다운로드한다
- 해당 문서에 대한 업데이트를 WebSocket연결로 동기화한다.
- CRDT를 이용해 오프라인 편집도 가능하고 추후에 온라인 시 업데이트를 동기화한다.
- 댓글 사용자 팀 프로젝트 등 문서 그 자체의 동기화 외에는 다른 시스템을 을 사용(데이터는 postgres에 저장)
- 성능 보안 등의 트레이드오프가 다르기에 별도의 시스템을 가져갔다고 한다.
그래서 왜 CRDT?
OT는 연산이 전파된다.
즉 추후 상태가 추상적이고 예측하기 어렵다는 단점이 있다.
CRDT는 독립적이며 다양한 환경(온라인,오프라인)에서의 구애를 덜 받는다.
그리고 알고리즘을 통해 병합하면서 불일치를 자동으로 해결한다. 결국 상태가 수렴한다.
하지만 FIGMA는 로그인기반 어플리케이션이고 사용자 문서의 권한 등등을 중앙집권식으로 관리해야한다. 때문에 CRDT를 변형하며, 다중 CRDT구조로 진행되어 있다고한다.
문서편집기와 FIGMA의 CRDT비교
원자성의 기준차이 각 원자성 기준에 id값이 붙는다.
문서편집기
- 각 문자의 변경이 원자성을 가진다
FIGMA
- 각 객체의 각 속성(key)이 원자성을 가진다.
- 예시
객체1{ position: {x:10,y:10}, text : "hihi" }update 객체1[position] = {x:20,y:30}이런 각 이벤트에 id값이 붙는다
피그마의 다중사용자 시스템 구현
객체 생성,제거 동기화
- 객체 id생성, 변경사항에 대한 ID생성(CRDT특징)은 클라이언트가 진행
- 오프라인에서 진행해야하기 클라이언트의 ID생성은 필수적
- 생성과 삭제는 last-writer-win알고리즘 사용
- last-writer-win알고리즘 : 마지막 사람껄 반영
- 삭제시 객체를 서버에서 완전히 삭제
- 크기가 계속 커지는 것을 방지
- 단, UNDO REDO등을 위해 클라이언트의 실행취소 버퍼에 해당 데이터를 저장
객체 속성 동기화
속성 원자성
각 객체에서는 다양한 속성(key)이 있다 머 예로 position, color등이 있을 수 있다. FIGMA에서는 속성에 대해서 원자적임을 택했다.
// 사용자1
TEXT객체{
value : "AB",
}
//사용자2
TEXT객체{
value : "BC",
}
속성값에 대해 원자적이기에 AB나 BC가 값이 된다 ABC가 절대 되지않는다.
변경사항 즉시 반영
빠르게 적용되기 위해 서버의 승인을 받지 않고 클라이언트에서 즉시 적용한다.
BUT 즉시 적용될시 플리커(깜빡임)이 발생할 수 있다
자신의 값이 전파되기 전의 값은 무시한다
자신 변경이전에 변경된 값이기에 last-writer-win에 의거해서 말이다.
객체 트리 동기화
FIGMA는 기본적으로 객체들이 DOM처럼 트리형태로 계층적인 형태를 이루고 있다.
트리 동기화에서는 부모를 다시 설정하는것이 메인 포인트이다.
목표
- 객체의 부모 설정은 해당 객체의 관련 없는 속성 변경과 충돌하지 않아야한다.
- 즉 색상 변경과 부모 재설정은 동시에 이뤄저야함
- 동시에 객체의 부모설정을 할때 객체가 복제되면 안된다(여러개 되면 안된다.)
- A> B일 때 B객체를 C>B , D>B로 두사람이 동시에 이동하여 부모재설정을 진행하였을 때 B객체가 두개가 되면 안되고 한곳에만 있어야 한다.
목표를 달성하기 위한 객체 트리 표현
FIGMA는 부자관계를 중첩으로 표현하지않고 속성으로써 표현했다.(2번 방법을 썼다.)
중첩 객체 표현
{ "id": 1, "children": [ { "id": 2, "children": [...] } ] }- 이동시 해당 객체를 삭제하고 새로 생성해야 함 이때 목표 1번이 위배된다.
부모Id와 같은 속성으로 트리를 표현
{ "id": 1, "parentId": null } { "id": 2, "parentId": 1 } { "id": 3, "parentId": 1 }- 부모이동은 속성변경과 같음
객체 순환 문제
parentID는 방향성을 갖는 간선이다. 따라서 B>C ,C>B의 변경이 들어오면 사이클 생길 수 있다.
이때 서버에서는 사이클이 생기는지 판단하고 클라이언트의 변경을 거부할 수 있다. 하지만 앞서 속성값변경에서 그래했듯 FIGMA는 UX를 위해 클라이언트 변경을 즉시 반영한다. 따라서 클라이언트에서 일시적으로 순환문제가 발생할 수 있다.
그리고 서버가 변경을 거부한 것을 확인하고 다시 정상적인 트리로 복구된다.
이렇게 클라이언트에서 순환이 생기면 문제가 되는 이유는 FIGMA는 DOM과 비슷한 형태로(트리형태로) UI를 그리기 때문이다.
해결방법
- 클라이언트에서도 사이클을 판별한다.
- 클라이언트에서 사이클을 판별할 시 해당부분을 렌더링 트리에서 빼버린다(화면에 안보이게 한다)
- 서버의 거부를 통해 사이클이 해결되면 다시 렌더링 트리에 보이게 한다.
FIGMA팀은 해당 해결책은 일시적인 문제에 대한 간단한 해결책으로 ,주기를 깨는 것과 같은 복잡한 작업을 시도할 필요성을 느끼지 못했다고 한다
객체 자식의 순서 결정
객체 간의 부모자식 순서 뿐아니라 자식들끼리의 순서도 중요하다.
WHY? 피그마에서는 순서에 따라 Z-index가 바뀐다.
분수 인덱싱 사용
자녀순서를 결정하기 위해 분수 인덱싱을 사용했다고 한다.
분수인덱싱은 A,B에 C가 들어간다고 할때 C의 순서는 A+B/2가 되는 것이다.
즉 A: 0.1, B : 0.2면 C : 0.15 가 되는 것이다.
왜 정수가 아닌 분수인덱스를 사용했을까?
예를 들어보자
자식 A,B,C가 순서 1,2,3을 가지고 있다고 해보자.
D를 A,B사이에 넣으면 B,C의 순서를 +1 업데이트해야한다, 이와동시에 B,가 삭제되거나, 다른 편집이 들어온다고 한다면 충돌과 연산이 많이 질 수 밖에 없다.
분수 인덱싱의 단점은 없는가?
코딩언어들은 기본적으로 2진수로 숫자를 나타낸다 그러다보니 오차가 발생한다.1.1+0.1 != 1.2처럼 말이다. 자세한 내용은 https://www.youtube.com/watch?v=-GsrYvZoAdA 코딩애플 유튜브 보면 쉽게 설명해주신다.
그래서 FIGMA는 부동소수점 수( 64-bit doubles)대신 arbitrary-precision fraction(제한없는 분수)를 사용한다.
arbitrary-precision fraction는 ASCII 전체를 써서 문자열 사이의 평균을 계산한다.
이거는 예를들면 A,C 중간은 B가 될테고 A,B사이를 나타낼때는 A뒤에 문자를 붙여서 진행한다.즉 일반적으로 순서는 사전 순을 따른다.