순서가 지정된 시퀀 (새 탭에서 열림)
Figma는 실시간 협업에서 여러 사용자가 객체의 순서를 동시에 변경해도 모든 클라이언트가 동일한 최종 상태에 도달하도록 해야 했다. 처음에는 Operational Transformation(OT)을 고려했지만, 텍스트 편집에 필요한 고급 기능과 구현 복잡도가 Figma에는 과도하다고 판단했다. 대신 각 객체에 순서를 나타내는 분수형 인덱스를 부여하고 정렬하는 방식을 사용해, 단순성과 안정성을 확보했다. ## 실시간 순서 편집의 문제 - Figma의 문서, 그룹, 컴포넌트 등은 자식 객체의 순서가 있는 목록을 가진다. - 사용자는 객체를 삽입·삭제하거나 드래그해 순서를 변경할 수 있다. - 각 클라이언트는 편집을 즉시 로컬에 적용한 뒤 서버로 전송한다. - 네트워크 상황에 따라 각 클라이언트가 작업을 서로 다른 순서로 받을 수 있다. - 따라서 작업 적용 순서가 달라도 모든 클라이언트의 문서가 동일해지는 eventual consistency가 필요하다. ## Operational Transformation의 접근법 - OT는 동시 작업이 서로의 위치와 의미를 깨뜨리지 않도록 작업을 변환한다. - 예를 들어 텍스트 `bcde`에 대해 한 사용자가 앞에 `x`를 삽입하고 다른 사용자가 `bc`를 삭제하면, 삭제 위치를 삽입만큼 보정한다. - 서버와 클라이언트는 다른 작업을 기준으로 각 연산을 변환해 같은 결과를 만든다. - OT는 오래된 협업 편집 알고리즘이며 텍스트 편집기에서 널리 사용됐다. ### OT의 장단점 - 장점 - 매우 큰 시퀀스에서도 성능과 메모리 효율이 좋다. - 같은 위치에 동시에 삽입된 문자열을 서로 끼워 넣지 않고 연속된 덩어리로 정렬할 수 있다. - 단점 - 구현과 정확성 검증이 어렵다. - 일반적으로 객체 이동을 삭제 후 삽입으로 처리한다. - 연산 종류가 늘어날수록 모든 연산 쌍 간 변환 규칙이 필요해 복잡도가 크게 증가한다. - Figma는 거대한 시퀀스나 삽입 결과의 비인터리빙이 필요하지 않았고, 객체 이동이 빈번했기 때문에 OT를 선택하지 않았다. ## 분수형 인덱싱 - 각 객체에 `0과 1 사이의 위치값`을 부여하고, 이 값을 기준으로 자식 객체를 정렬한다. - 두 객체 사이에 삽입할 때는 양쪽 인덱스의 평균을 새 객체의 인덱스로 사용한다. - 예를 들어 `0.2`와 `0.6` 사이에 삽입하면 `0.4`를 사용할 수 있다. - 인덱스는 64비트 부동소수점 대신 임의 정밀도 분수로 저장해 반복 삽입으로 정밀도가 고갈되는 문제를 피한다. - Figma는 인덱스를 문자열로 저장하고 문자열 조작으로 평균을 계산한다. - 저장 공간을 줄이기 위해 `0.`을 생략하고, 숫자만이 아니라 전체 ASCII 범위를 사용한 base 95 표현을 적용한다. ## 분수형 인덱싱의 장단점 - 장점 - 알고리즘이 단순하고 이해·구현하기 쉽다. - 객체를 이동할 때 위치값 하나만 변경하면 된다. - 이동을 삭제와 삽입으로 나눌 필요가 없다. - 단점 - 반복적인 삽입과 재배치로 인덱스 문자열이 길어질 수 있다. - 여러 클라이언트가 같은 위치에 동시에 삽입하면 새 객체들이 서로 섞일 수 있다. - 동일한 두 인덱스 사이의 평균을 다시 계산할 수 없다. ## 동시 삽입 충돌 처리 - 동일한 위치에 두 클라이언트가 동시에 객체를 삽입하면 두 객체가 같은 인덱스를 가질 수 있다. - 서버가 두 객체에 동일한 위치값이 생기지 않도록 두 번째 삽입에 고유한 위치를 부여한다. - 인덱스 길이 증가는 Figma에서 객체 수와 사용자 활동이 실용적인 범위로 제한되므로 큰 문제가 되지 않는다. - 디자인 문서에서는 동시에 삽입된 객체가 서로 겹치지 않는 경우가 많아, 순서가 일부 인터리빙되는 것도 허용 가능하다. Figma의 사례는 가장 정교한 알고리즘보다 제품의 요구사항에 맞는 단순한 알고리즘이 더 유리할 수 있음을 보여준다. 대규모 텍스트 편집처럼 강한 순서 보장이 필요하지 않다면, 분수형 인덱싱은 구현·유지보수 비용이 낮고 객체 이동에도 효율적인 실용적 선택이다.