이 블로그 글은 ProseMirror에서 사용되는 협업 편집 기술을 설명합니다. ProseMirror에 대한 소개는 여기에서 확인할 수 있습니다.
협업 편집의 문제점
실시간 협업 편집 시스템은 여러 사람이 동시에 같은 문서를 편집할 수 있음을 의미합니다. 이 시스템은 문서가 동기화 상태를 유지하도록 보장합니다. 즉, 한 사용자가 문서에 가한 변경 사항은 다른 사용자에게 전송되어 해당 사용자의 문서에 반영됩니다.
이러한 시스템의 복잡성은 네트워크를 통해 변경 사항을 전송하는 데 시간이 걸리기 때문에 동시 업데이트를 처리하는 방식에 있습니다. 한 가지 해결책은 사용자가 현재 문서(또는 문서의 일부)를 잠그어 다른 사용자가 동시에 문서를 변경하지 못하도록 하는 것입니다. 그러나 이 메커니즘은 사용자로 하여금 잠금에 대해 고민하게 만들며, 잠금이 없는 경우(즉, 다른 사용자가 편집 중일 때) 계속 기다려야 합니다. 우리는 이를 원하지 않습니다.
동시 업데이트를 허용하는 경우, 사용자 A와 B가 동시에 문서를 변경하고 서로의 변경 사항을 인지하지 못한 상태에서 최종적으로 문서를 어떻게 업데이트할지 협의해야 하는 상황이 발생합니다. A와 B의 행동은 서로 영향을 주지 않을 수도 있습니다(예: 문서의 다른 부분을 동시에 편집하는 경우). 또는 서로 영향을 줄 수도 있습니다(예: 같은 단어를 변경하려고 시도하는 경우).
Operational Transformation(OT, 작업 변환)
이 문제에 대한 많은 연구가 있습니다. 저는 많은 논문을 읽었지만 이 연구를 전혀 이해하지 못했음을 인정합니다. 만약 제가 어떤 내용을 오해했거나 흥미로운 참고 문헌을 누락했다면, 저에게 이메일을 보내 알려주시면 매우 기쁠 것입니다.
이 문제에 대한 대부분의 연구는 사실 분산 시스템에 관한 것입니다. 즉, 중앙 제어 노드 없이 메시지를 교환하는 노드 집합에 관한 것입니다. 이 문제를 해결하기 위한 고전적인 방법은 「Operational Transformation」라고 불리는 분산 알고리즘입니다. 이 알고리즘은 변경 사항을 설명하는 방법을 정의하며, 두 가지 속성을 가집니다:
-
다른 변경 사항에 상대적으로 변경 사항을 변환할 수 있습니다. 예를 들어, 사용자 A가 부모 오프셋 1에 문자 "O"를 삽입하는 동시에 사용자 B가 오프셋 10에 문자 "T"를 삽입하면, 사용자 A는 B의 변경 사항을 자신의 변경 사항에 상대적으로 변환할 수 있습니다. 즉, B의 변경 사항 오프셋 앞에 추가 문자가 삽입되었으므로 "T"를 오프셋 11에 삽입하는 것입니다.
-
동시 변경 사항이 문서에 적용되는 순서와 관계없이 모든 사용자가 최종적으로 동일한 문서를 가지게 됩니다. 이는 A가 자신의 변경 사항에 상대적으로 B의 변경 사항을 변환하고, B도 유사하게 A의 변경 사항을 변환할 수 있도록 하여 두 사용자가 서로 다른 문서를 얻지 않도록 합니다.
Operational Transformation(OT) 시스템은 로컬 변경 사항을 즉시 로컬 문서에 적용한 다음 변경 사항을 다른 사용자에게 브로드캐스트합니다. 다른 사용자는 브로드캐스트된 변경 사항을 받아 변환하고 적용합니다. 원격 변경 사항을 정확히 어떤 로컬 변경 사항을 통해 변환해야 하는지 알기 위해, 시스템은 변경 사항을 브로드캐스트할 때 문서 상태 표현을 함께 전송해야 합니다.
이 과정은 상당히 간단하게 들립니다. 그러나 구현은 악몽과 같습니다. “삽입” 및 "삭제"와 같은 여러 사소한 변경 사항을 지원하기 시작하면, 어떤 순서로든 변경 사항을 적용한 후 동일한 문서가 생성되도록 보장하는 것이 극도로 어려워집니다.
Google Wave에서 일했던 엔지니어 Joseph Gentle는 이렇게 말했습니다…
불행히도 OT를 구현하는 것은 매우 고통스럽습니다. 수백만 가지의 알고리즘 중에서 선택해야 하며, 이들 대부분은 학술 논문에만 존재합니다. 이 알고리즘들을 올바르게 구현하는 것은 매우 어렵고 시간이 많이 걸립니다.
중앙화
OT 메커니즘의 복잡한 설계 결정은 대부분 변경 사항을 어떻게 배포할지에 대한 요구 사항에서 비롯됩니다. 분산 시스템은 실제로나 전략적으로 훌륭한 특성을 가지며, 개발 과정에서 종종 흥미롭습니다.
그러나 "변경 사항을 처리하는 중앙"을 도입하면 복잡성을 크게 줄일 수 있습니다. 솔직히, Google이 Google Docs(중앙화된 시스템)에서 OT를 사용한 것은 저에게 매우 의아합니다.
ProseMirror의 알고리즘은 중앙화되어 있습니다. 모든 사용자가 연결된 단일 변경 처리 센터가 변경 사항을 적용할 순서를 결정하기 때문입니다. 이는 협업 편집 시스템을 상대적으로 쉽게 구현하고 이해할 수 있게 합니다.
사실 저는 이 “중앙화” 특성이 분산 방식으로 OT 알고리즘을 실행하는 데 큰 장애물이 된다고 생각하지 않습니다(즉, OT의 분산 알고리즘의 어려움과 장애물은 중앙화에 있지 않습니다). [Raft](https://en.wikipedia.org/wiki/Raft_(computer_science)와 같은 합의 알고리즘을 사용하여 중앙화된 서비스 대신 중재자를 선택할 수도 있습니다. (하지만 제가 실제로 이 방법을 시도해 본 것은 아닙니다)
ProseMirror의 협업 알고리즘
OT와 마찬가지로 ProseMirror는 변경 기반 어휘를 사용하고 변경 사항을 상호 변환합니다. 그러나 OT와 달리, 다른 순서로 변경 사항을 적용해도 동일한 문서가 생성되도록 보장하려고 하지 않습니다.
중앙 집중식 서비스를 사용하면 모든 클라이언트가 동일한 순서로 변경 사항을 적용하도록 쉽게 만들 수 있습니다. 코드 버전 관리 시스템에서 사용되는 메커니즘과 유사한 방식을 활용할 수 있습니다. 클라이언트가 변경 사항을 가지면, 해당 변경 사항을 서버로 _push_하려고 시도합니다. 서버가 이 변경 사항이 현재 최신 버전을 기반으로 한 것으로 판단하면 변경 사항이 수락됩니다. 그렇지 않으면, 클라이언트는 먼저 다른 클라이언트의 변경 사항을 _pull_한 다음, 서버로 다시 push하기 전에 자신의 변경 사항을 _rebase_해야 합니다.
git과 달리, 이 모델에서 문서의 기록은 선형적이며, 문서의 특정 버전은 간단히 정수로 표현될 수 있습니다.
또한 git과 다른 점은, 모든 클라이언트가 지속적으로 문서의 새로운 변경 사항을 pull(또는 push하고 수신)하며, 네트워크가 허용하는 한 최대한 빠르게 서버의 상태를 따라가려고 한다는 것입니다.
유일한 어려운 부분은 다른 사람의 변경 사항을 자신의 변경 사항에 rebase하는 것입니다. 이는 OT(Operational Transformation)가 수행하는 변환과 매우 유사합니다. 하지만 이는 클라이언트 _자신_의 변경 사항을 통해 이루어지며, 원격 서버의 변경 사항이 아닙니다.
위치 매핑
그러나 OT는 _다른 사람의 변경 사항_에 상대적으로 변경 사항을 변환하는 반면, ProseMirror는 position map(위치 매핑)이라는 파생 데이터 구조를 사용하여 이를 변환합니다. 문서에 변경 사항을 적용할 때마다 새로운 문서와 위에서 언급한 매핑을 얻게 되며, 이 매핑은 이전 문서의 위치를 새 문서의 해당 위치로 변환하는 데 사용될 수 있습니다. 매핑의 가장 두드러진 사용 사례는 커서를 동일한 “개념적” 위치에 유지하도록 조정하는 것입니다. 만약 커서 앞에 문자가 삽입되면, 커서는 주변 텍스트와 함께 한 위치 앞(오른쪽)으로 이동해야 합니다.
변경 사항의 변환은 완전히 위치 매핑을 기반으로 수행됩니다. 이는 실제로 매우 유용하며, 특정 변경 유형에 대한 변환 코드를 작성할 필요가 없음을 의미합니다. 각 변경 사항은 from, to, at로 표현되는 하나에서 세 개의 위치 정보와 관련이 있습니다. 주어진 다른 변경 사항에 상대적으로 변경 사항을 변환할 때, 이러한 위치는 다른 변경 사항의 위치 매핑을 통해 매핑됩니다.
예를 들어, 위치 5에 문자가 삽입되면, "위치 10에서 14까지 삭제"하는 변경 사항은 "위치 11에서 15까지 삭제"로 변환됩니다.
각 변경 사항의 위치는 처음 적용된 문서 버전이 동일한 경우에만 의미가 있습니다. 위치 매핑은 변경 전후 두 문서 버전 간의 위치 매핑을 정의합니다. 변경 사항을 다른 버전에 적용하려면, 해당 버전과 대상 버전 사이의 변경 사항을 통해 단계별로 매핑해야 합니다.
(간단함을 위해 예제는 위치 표현으로 정수를 사용합니다. ProseMirror에서 실제 위치는 문서 트리 내의 경로와 함께 단락 내의 정수 오프셋으로 구성됩니다)
위치 리베이스
한 클라이언트가 여러 개의 아직 원격으로 푸시되지 않은 로컬 변경 사항을 가지고 있을 때 흥미로운 일이 발생합니다. 다른 사람의 변경 사항이 들어오면, 모든 로컬 커밋되지 않은 변경 사항은 이러한 변경 사항을 기반으로 변환되어야 합니다. 로컬 변경 사항 _L1_과 _L2_가 있고, 이를 원격 변경 사항 _R1_과 _R2_에 리베이스한다고 가정해 보겠습니다. 여기서 _L1_과 _R1_은 동일한 문서 버전에서 변경되었습니다.
먼저, R1과 R2를 원본 문서 버전에 적용합니다(클라이언트는 현재 표시 중인 문서 버전–푸시되지 않은 변경 사항 포함–과 이러한 변경 사항이 포함되지 않은 원본 버전을 추적해야 합니다). 이 작업은 두 매핑 _mR1_과 _mR2_를 생성합니다.
역자 주: 아래 내용은 이해하기 어려울 수 있으며, 독자가 그림을 그려보는 것이 더 직관적일 수 있습니다. 간단히 말해, L2는 L1이 문서를 수정한 후 위치 매핑(위치 조정)을 거쳐 문서를 수정한 것입니다. L2를 올바르게 리베이스하려면 먼저 L1 및 L1 이전(즉, R1과 R2)의 문서 수정 사항이 영향을 미치는 위치를 모두 매핑(조정)해야 합니다. 이렇게 해야 L2가 올바른 위치 매핑을 얻고, 올바른 위치에서 문서 수정을 시작할 수 있습니다.
_L1_을 _mR1_과 _mR2_를 통해 매핑된 버전인 *L1**로 간단히 매핑할 수 있습니다. 그러나 L2는 초기 문서 버전에서 L1이 수정된 후의 문서를 기반으로 수정되었으므로, L2에 대해 먼저 mL1(L1을 적용하여 생성된 매핑)을 통해 역매핑(즉, 역사 롤백, mL1의 역연산)해야 합니다. 이제 문서는 R1이 시작될 때의 문서와 동일해지며, mR1과 mR2를 통해 L2를 매핑한 다음, mL1*–앞서 간단히 적용한 *L1**에서 생성된 매핑–을 통해 다시 매핑할 수 있습니다. 이제 *L2**를 얻었으며, 이를 *L1**이 적용된 문서에 적용할 수 있습니다. 보세요, 우리는 두 변경 사항을 다른 두 변경 사항에 리베이스했습니다.
번역자 주: 아래 문단에서 "위치 5에 두 문자 삽입"은 위의 L1에 해당하고, "두 문자 사이(위치 6)에 삽입"은 위의 L2에 해당합니다. 따라서 L2를 리베이스할 때는 mL1을 통해 L2의 삽입 위치를 초기 문서로 롤백해야 하지만, 이때 문서에는 L2가 매핑될 위치가 존재하지 않습니다. 해당 위치가 아직 존재하지 않기 때문입니다.
삭제 작업 매핑과 역방향 매핑(역사 롤백–번역자 주) 삽입 작업은 정보 손실을 일으킵니다. 위치 5에 두 문자를 삽입한 후 다른 사람이 위치 6(이전에 삽입된 문자 사이)에 삽입하면, 역방향 매핑(역사 롤백, 앞서 언급한 L2–번역자 주)을 수행한 다음 초기 삽입 작업을 통해 순방향 매핑하면 삽입된 두 문자 앞이나 뒤 위치에 놓이게 됩니다. 아직 존재하지 않는 문서는 이 두 문자 사이 위치를 표현할 수 없기 때문입니다(아직 삽입되지 않을 문자들의 정확한 위치를 어떻게 표현할까요?–번역자 주).
번역자 주: 아래 문단은 본문의 핵심으로, 매핑 시 추가적인 반대 방향 매핑 정보를 제공함으로써 역방향 매핑(역사 롤백) 시 존재하지 않는 위치로 매핑해야 할 경우 해당 위치 내용을 먼저 복원(해당 매핑의 미러 사용)한 후 매핑을 수행합니다. 이전 매핑이 완료된 후에는 이 매핑을 직접 건너뜁니다(이미 내용 복원 시 매핑이 완료되었기 때문). 매핑 미러와 매핑 내용은 반드시 동일한 크기를 유지해야 합니다(당연한 말이지만, 그렇지 않으면 위치 계산이 틀어집니다).
이 문제를 해결하기 위해 ProseMirror 협업 시스템은 매핑 파이프라인(mapping pipelines)을 사용합니다. 이는 단순한 일련의 매핑뿐만 아니라 어떤 매핑이 서로의 미러인지에 대한 정보도 저장합니다. 위치가 이 파이프라인을 통과할 때 주변 내용을 삭제하는 매핑을 만나면, 시스템은 파이프라인을 역방향으로 스캔하여 해당 매핑의 미러를 찾습니다. 이러한 매핑을 찾으면 순방향 매핑으로 이동하여(일반적인 위치 조정–번역자 주) 해당 위치를 사용하고, 삭제된 내용의 상대적 오프셋을 이용해 이 매핑이 삽입한 내용 내 위치를 복원합니다. 삭제 작업의 매핑 미러는 삽입 작업의 매핑 미러와 동일한 내용 크기를 유지해야 합니다.
매핑 방향
내용을 삽입할 때마다 이 명확한 삽입 지점을 두 가지 다른 위치(둘 다 의미 있는 위치)로 매핑할 수 있습니다: 삽입 내용 앞이나 뒤. 때로는 전자가 적합하고 때로는 후자가 적합합니다. ProseMirror의 위치 매핑 시스템은 개발자가 원하는 방향을 선택할 수 있도록 합니다.
번역자 주: 아래 문단은 문서가
abc일 때, a 뒤 b 앞 위치에 문자 x를 삽입하면 변경된from와to모두 1이 됨을 설명합니다. 삽입 내용 뒤에서from은 순방향(왼쪽) 매핑 시 여전히 1로 유지되고,to은 역방향(오른쪽) 매핑 시 2가 됩니다.
이것이 변경과 관련된 위치에 여러 다른 위치 정보가 포함되는 이유입니다. 변경에 from과 to 위치 정보가 있는 경우, 예를 들어 삭제나 문서 내용 스타일 설정 시 해당 위치 앞이나 뒤에 내용이 있다면 이 내용은 변경 범위에 포함되지 않아야 합니다(이 내용은 변경 발생 후 위치 매핑만 필요합니다–번역자 주). 따라서 from 위치는 순방향(왼쪽)으로 매핑되어야 하고, to 위치는 역방향(오른쪽)으로 매핑되어야 합니다.
변경이 이를 완전히 포함하는 매핑을 통해 매핑될 때, 예를 들어 위치 5에 문자를 삽입한 후 2에서 10까지 삭제로 생성된 변경을 통해 매핑하면, 위치 5의 문자 삽입 전체 작업은 단순히 버려집니다. 해당 컨텍스트가 더 이상 존재하지 않기 때문입니다.
변경 유형
ProseMirror에서 원자적 변경을 step(단계)라고 합니다. 사용자 관점에서 단일 변경으로 보이는 일부 변경은 실제로 여러 단계로 분해됩니다. 예를 들어, 텍스트를 선택한 후 enter 키를 누르면 편집기는 선택 텍스트 삭제를 위한 delete 단계를 생성한 다음 현재 문단 분할을 위한 split 단계를 생성합니다.
다음은 ProseMirror에 존재하는 단계 유형입니다:
addStyle와removeStyle은 문서에 인라인 스타일을 추가하거나 제거합니다.split는 하나의 노드를 두 개로 분할합니다. 예를 들어, 사용자가 엔터 키를 눌렀을 때 단락을 나누는 데 사용할 수 있습니다. 단일at위치 정보만 필요합니다.join은 인접한 두 노드를 연결합니다. 이 단계는 동일한 유형의 콘텐츠를 포함하는 노드에만 유효합니다. 연결할 두 노드의 끝과 시작 위치를 각각 가리키는from과to위치 정보가 필요합니다(예상된 노드가 올바르게 연결되도록 보장하기 위함입니다. 만약 이 과정에서 두 노드 사이에 콘텐츠가 삽입되면 연결 단계는 무시됩니다).ancestor는 노드의 유형을 변경하거나 조상 노드를 추가/제거하는 데 사용됩니다. 목록을 감싸거나 단락을 제목으로 변환할 때 활용할 수 있습니다. 노드의 시작과 끝 위치를 가리키는from과to위치가 필요합니다.replace는 문서의 일부를 0개 이상의 노드로 교체하며, 필요한 경우 호환 가능한 노드를 자른 가장자리 부분에 결합할 수 있습니다. 삭제할 범위를 정의하는from과to위치와 새 노드가 삽입될 위치를 지정하는at위치가 사용됩니다.
위에서 설명한 유형 중 마지막이 가장 복잡합니다. 처음에는 이를 제거와 삽입 두 단계 유형으로 분리하려 했습니다. 하지만 교체 단계에서 생성되는 위치 매핑은 모든 교체 콘텐츠를 원자적으로 처리해야 하기 때문에(위치는 모든 교체 콘텐츠에서 계산되어야 함), 단일 단계로 처리하는 것이 더 나은 결과를 가져왔습니다.
작업의 의도
실시간 협업 편집 시스템의 필수 속성은 변경의 의도를 보존하려는 노력입니다. 변경의 "병합"이 자동으로 발생하며 사용자 상호작용 없이 이루어지기 때문에, 문서 변경이 리베이스 과정에서 원하지 않는 결과로 변할 때 큰 불편을 초래할 수 있습니다.
이러한 수정 단계와 리베이스 방식을 정의할 때, 리베이스 시 이상하지 않도록 노력했습니다. 대부분의 경우 변경 사항이 서로 겹치지 않아 상호작용이 필요 없습니다. 하지만 변경 사항이 겹치는 경우, 병합 결과가 정상적이도록 보장해야 합니다.
때로는 변경 사항을 단순히 버려야 할 때도 있습니다. 예를 들어, 단락에 텍스트를 입력하는 동안 다른 사용자가 해당 단락을 삭제하면, 입력한 콘텐츠의 의미 있는 문맥이 사라지고, 해당 위치에 삽입되는 것은 무의미한 문서 조각을 생성할 뿐입니다.
두 목록을 연결하려는 시도 중간에 다른 사용자가 단락을 삽입하면, 원하는 작업을 수행할 수 없게 됩니다(인접하지 않은 노드는 연결할 수 없음). 따라서 해당 작업은 버려집니다.
다른 시나리오에서는 변경 사항이 수정되더라도 여전히 의미가 있습니다. 위치 5부터 10까지의 문자를 굵게 표시하는 동안 다른 사용자가 위치 7에 문자를 삽입하면, 최종 결과는 위치 5부터 11까지 굵게 표시됩니다.
마지막으로, 일부 변경 사항은 서로 영향을 주지 않고 겹칠 수 있습니다. 예를 들어, 한 사용자가 단어에 하이퍼링크를 설정하는 동안 다른 사용자가 동일한 단어를 굵게 표시하면, 두 변경 사항 모두 원본 문서에 적용됩니다.
오프라인 작업
실시간 협업 편집에서는 변경 사항을 조용히 수정하거나 일부를 버리는 것이 큰 문제가 되지 않습니다. 이 경우 피드백이 거의 즉각적이기 때문입니다—편집 중인 단락이 사라지는 것을 보면, 다른 사용자가 삭제했음을 알 수 있고, 따라서 자신의 변경 사항도 사라졌음을 이해하게 됩니다.
반면 오프라인 편집(중앙 서버에 연결되지 않은 상태에서의 편집)이나 분기된 작업 흐름에서는, 이 모델(OT도 마찬가지)이 효과적이지 않습니다. 오랜 시간 동안 많은 편집 작업을 수행한 후, 그 동안 다른 사용자가 문서를 수정/삭제/삽입한 내용과 병합해야 할 때, 이 모델은 많은 편집 작업을 조용히 삭제하거나(편집 문맥이 이미 삭제된 경우), 두 사용자가 같은 문장을 다른 방식으로 편집했을 때 이상한 텍스트 조합을 생성할 수 있습니다.
이러한 시나리오에서는 diff 기반 구현이 더 적합할 수 있습니다. 자동 병합은 불가능할 수 있으며—충돌을 식별하여 사용자가 해결하도록 해야 합니다. Git이 사용자에게 요구하는 방식과 유사합니다.
실행 취소 기록
협업 편집 시스템에서 실행 취소 기록은 어떻게 구현되어야 할까요? 널리 받아들여지는 답변은 단일 공유 기록을 사용해서는 안 된다는 것입니다. 편집을 취소할 때는 문서의 마지막 변경 사항이 아니라, 자신이 마지막으로 수행한 편집 작업을 취소해야 합니다.
이는 단순히 이전 상태로 롤백하는 문서 기록 방식으로는 달성할 수 없음을 의미합니다. 자신의 변경 사항을 취소했을 때(다른 사용자의 변경 사항이 있는 경우) 이전에 존재하지 않았던 새로운 상태가 생성됩니다.
이를 구현하기 위해, 반전 가능한 변경 사항(여러 단계)을 정의해야 했습니다. 이 반전은 원본 단계의 효과를 상쇄하는 새로운 단계를 생성합니다.
ProseMirror의 실행 취소 기록은 반대 단계를 누적하고, 현재 문서 버전과의 모든 위치 매핑도 추적합니다. 현재 문서 버전으로 역매핑하기 위해서는 이 과정이 필수적입니다.
하지만 불리한 점은 사용자가 변경을 수행한 후 유휴 상태가 되고, 그 동안 다른 사람이 문서를 변경한 경우, 이 사용자의 변경 사항을 현재 버전의 문서 위치로 매핑하는 과정이 무한정 쌓이게 된다는 것입니다. 이 문제를 해결하기 위해 기록은 주기적으로 _압축_되어, 반전된 변경 사항을 앞으로 매핑하여 다시 현재 문서부터 편집할 수 있도록 합니다. 이 과정에서 중간 단계의 위치 매핑은 버려집니다.
블로거의 말:
저는 인생의 중요한 선택의 기로에 섰을 때, 누군가 최선의 방법을 알려주어 소중한 시간을 헛되이 보내지 않기를 바라곤 합니다. 그런 마음으로 저는 자주 블로그를 쓰며, 광활한 인터넷의 이 작은 구석에 제게는 단 한 번뿐인 인생 경험을 기록하여 도움이 필요한 분들에게 도움이 되기를 바랍니다.
