수렴만으로는 부족하다: Automerge의 한계와 라이브 시스템 병합의 문제
Convergence Is Not Enough
Livelymerge 프로젝트에서 우리는 모든 객체, 클래스, 메서드가 Automerge 문서인 시스템을 구축 중이다. Automerge는 수렴을 보장하지만, 실행 중인 프로그램의 힙을 병합할 때 불변식이 깨질 수 있다. 예를 들어, 두 클라이언트가 연결 리스트를 동시에 수정하면 리스트가 잘리거나 순환이 생길 수 있다. 이는 Automerge가 의도가 아닌 쓰기 효과를 재생하기 때문이다. 우리는 병합 인식 데이터 타입이라는 방향을 탐구 중이며, Kleppmann 등의 move 연산과 Coln 프로젝트가 관련 작업이다.
수렴은 충분하지 않다.
HN 토론
12- wim
우리는 문서/플래닝용 멀티플레이어 IDE[1]를 만들고 있는데, 문서가 트리/그래프여야 합니다(아웃라이닝, 참조, 트랜스클루전 등을 지원하기 위해).
우리는 어떤 타입의 연산이든 무조건 리플레이해서 병합할 수 없습니다. 예를 들어 트리 사이클이 생길 수 있기 때문입니다. 연결 리스트처럼 특정 연산은 오프라인 클라이언트에게는 로컬로 유효할 수 있지만, 수렴된 순서에서는 전역적으로 유효하지 않을 수 있습니다.
우리의 동기화 엔진은 연산 타입을 구분합니다: 무조건 연산(unconditional operations)과 보호 연산(guarded operations).
무조건 연산은 구조적/데이터 모델 불변식을 위반할 수 없습니다. 예를 들어 SetCompleted(task_guid, true) 같은 것. 단순한 LWW(마지막 쓰기 승리)입니다.
보호 연산은 토폴로지를 변경할 수 있습니다. 예를 들어 InsertMove(node_guid, parent_guid, after_guid) 같은 것. 이들은 생성 당시의 상태가 아니라 현재 상태에 대해 검사됩니다. 리플레이 중에 우리는 먼저 낙관적 로컬 연산을 되돌리고 들어오는 정규 연산을 순서대로 리플레이합니다. 각 연산의 뮤테이터 함수는 적용 전에 현재 상태를 검증하고, 조건을 위반하면(예: 다른 클라이언트가 그 사이에 다른 이동을 만들어 사이클이 생기는 경우) 결정적으로 거부됩니다. 우리의 경우 권위 있는 서버도 있으므로, 데이터 구조를 넘어 권한 같은 조건에도 동일한 보호 연산을 사용할 수 있습니다. 예를 들어 AddUser(workspace_guid, user_guid) 뮤테이터 함수가 먼저 권한 상태를 검사할 수 있습니다.
- alexisread
격자 타입(BloomL)에 관한 관련 논문:
https://dsf.berkeley.edu/papers/UCB-lattice-tr.pdf
이에 더해, 동시 편집을 순서화하기 위해(하나를 버리는 대신) 인과 레지스터(키별 Merkle 클록)가 필요할 것입니다.
마지막으로, 의미론적 병합을 처리하려면 Pijul 스타일의 VCS가 필요할 것입니다.
- Animats
이것은 분명히 Automerge[1]에 기반한 것입니다. 정말 좋은 아이디어처럼 들립니다. MMO 게임 클라이언트와 서버를 동기화하기에 충분히 좋은 아이디어인가요?
2012년 논문, 마지막 Automerge 사이트 업데이트는 2025년. 왜 이게 어디에나 있지 않나요?