같은 문서를 고쳤다고 모두 충돌일까?

가장 조용한 데이터 손실이었습니다

동시 편집 문제는 서버 오류처럼 눈에 띄게 나타나지 않았습니다.

A와 B가 같은 리비전에서 편집을 시작했다고 해보겠습니다.

A는 첫 문단에 설명을 추가하고 먼저 저장했습니다. B는 오래된 편집 화면에서 마지막 문단의 오타만 고쳐 나중에 저장했습니다.

B의 화면에는 A가 추가한 문장이 없습니다. B가 제출한 전체 본문으로 단순 UPDATE하면 A의 수정도 함께 사라집니다.

original
  └─ 처음 두 사람이 본 문서

A의 저장
  └─ 첫 문단 추가

B의 저장
  └─ 마지막 문단 오타 수정

단순 UPDATE
  └─ A의 첫 문단 추가가 사라짐

데이터베이스 오류는 없고 HTTP도 성공입니다. 오히려 모든 로그가 정상이라 문제를 발견하기 더 어렵습니다.

버전 번호를 두고 오래된 리비전에서 시작한 요청을 모두 409 Conflict로 막으면 데이터 손실은 피할 수 있습니다. 하지만 두 사람이 전혀 다른 문단을 수정했는데도 B는 최신 문서를 다시 열고 같은 오타를 한 번 더 고쳐야 합니다.

위키에서 여러 사람이 같은 문서를 편집하는 일은 흔합니다. 실제로 겹친 수정만 충돌로 보여주고, 독립된 변경은 자동으로 합치고 싶었습니다.

그래서 Git이 어떻게 하는지 보기 시작했습니다

동시 편집을 생각하다 보면 자연스럽게 Git의 merge를 떠올리게 됩니다.

Git도 두 브랜치의 최종 파일만 비교하지 않습니다. 두 변경이 갈라지기 전의 공통 원본을 함께 사용합니다.

Rust에서 제가 원하는 방식으로 쓸 수 있는 도구가 마땅치 않아 Git의 xdiff를 FFI로 연결한 threeway-merge-rs를 직접 만들었습니다. Sevenwiki의 blame 기능을 위해 blame-rs도 별도로 만들었고요.

웹 백엔드를 만들다가 갑자기 C 라이브러리의 인터페이스를 보고 Rust crate를 만들고 있는 것이 조금 웃기기도 했습니다. 하지만 이런 작업이 오히려 제가 원래 하던 시스템 프로그래밍에 가까워, 중간중간 재미있는 휴식처럼 느껴졌습니다.

현재 V7은 threeway_merge crate를 이용해 문서 본문과 문서 요약의 3-way merge를 수행합니다.

핵심은 두 문서가 아니라 세 문서를 비교하는 것입니다.

original, proposed, current

3-way merge에는 다음 세 상태가 필요합니다.

original
  사용자가 편집을 시작할 때 본 리비전

proposed
  사용자가 제출한 결과

current
  서버에 지금 저장된 최신 리비전

proposed와 current만 비교하면 서로 다르다는 것만 알 수 있습니다.

original이 있어야 사용자가 어느 부분을 바꿨고, 그 사이 다른 편집자가 어느 부분을 바꿨는지 구분할 수 있습니다.

편집 API가 original_revision_id를 받는 이유입니다. 클라이언트가 임의의 문자열을 원본이라고 주장하게 하지 않고, 서버가 해당 리비전 행과 R2 본문을 직접 읽습니다.

요청한 원본 리비전이 실제로 같은 문서에 속하는지도 확인합니다. 다른 문서의 리비전을 base로 넣어 전혀 관계없는 본문을 합치면 안 되기 때문입니다.

앞 글에서 설명한 immutable 리비전 구조가 여기서 merge base로도 사용됩니다. 과거 기록과 동시성 제어가 따로 떨어진 기능이 아니었습니다.

최신 문서에서 시작했다면 굳이 합치지 않습니다

모든 편집 요청에 3-way merge를 실행하지는 않습니다.

사용자가 편집을 시작한 리비전이 현재 리비전과 같다면, 그 사이 다른 텍스트 편집이 없었던 것입니다.

original == current
  ├─ 본문과 문서 요약이 같음 → NoChanges
  └─ 하나라도 달라짐         → 요청 값을 그대로 준비

original != current
  └─ 3-way merge

평범한 편집 경로를 굳이 복잡한 병합 알고리즘에 넣지 않습니다. 오래된 리비전에서 시작한 경우에만 원본, 제출본, 현재 본문을 읽어 합칩니다.

edit_summary도 병합하지 않습니다. 이것은 사용자가 이번 저장에 붙인 설명이므로 제출한 값을 그대로 유지합니다.

병합 대상은 실제 문서 본문과 문서의 별도 summary입니다.

서로 다른 부분이라면 같이 살렸습니다

현재 구현은 histogram diff를 이용해 변경 구간을 계산합니다.

A가 첫 문단을 바꾸고 B가 마지막 문단을 바꿨다면 두 변경은 서로 겹치지 않으므로 한 결과에 함께 넣을 수 있습니다.

같은 줄이나 같은 범위를 서로 다르게 바꿨다면 자동으로 어느 쪽이 맞는지 판단하지 않습니다. 충돌 표시가 포함된 결과를 사용자에게 돌려줍니다.

<<<<<<< proposed
사용자가 제출한 내용
=======
현재 서버 내용
>>>>>>> current

서버는 이 문자열을 그대로 새 리비전으로 저장하지 않습니다. 사용자가 편집 화면에서 충돌을 해결한 뒤 다시 제출해야 합니다.

본문과 문서 요약은 각각 merge하지만 최종 결과는 하나로 판단합니다.

• 둘 다 충돌이 없고 결과가 현재와 다르면 Ready
• 합친 결과가 이미 현재와 같으면 NoChanges
• 둘 중 하나라도 겹치면 Conflict

문서 요약에서 충돌이 났는데 본문만 먼저 저장하거나, 본문 충돌을 무시하고 요약만 바꾸지는 않습니다. 한 번의 저장 요청으로 제출한 두 값을 서로 다른 리비전에 나눠버리면 사용자가 의도한 편집 단위가 깨지기 때문입니다.

merge를 끝냈는데 또 누가 저장했습니다

3-way merge를 계산한 순간과 실제 PostgreSQL 트랜잭션에서 문서를 잠그는 순간 사이에도 다른 편집이 들어올 수 있습니다.

이 경우 준비해둔 merge 결과는 이미 한 단계 오래된 값입니다.

V7은 저장 직전에 현재 리비전을 다시 확인합니다.

리비전 ID만 달라졌고 본문과 문서 요약은 그대로라면 파일만 수정된 리비전일 수 있습니다. 문서의 텍스트 편집과 파일 연결 변경은 서로 다른 축이므로 텍스트 저장을 계속할 수 있습니다.

하지만 본문이 실제로 바뀌었다면 이전 merge 결과를 억지로 저장하지 않습니다. 최신 리비전을 기준으로 다시 시도하도록 합니다.

트랜잭션 안에서 merge를 한 번 더 반복하는 방식도 생각할 수 있습니다. 하지만 문서 잠금을 잡은 상태로 R2에서 여러 본문을 읽고 CPU 계산까지 하면 트랜잭션 길이가 예측하기 어려워집니다.

드물게 두 번째 경쟁이 생기면 재시도를 요구하는 대신, 일반적인 저장 경로의 잠금 시간을 짧게 유지했습니다.

자동 merge를 최대한 많이 해주는 것보다, 오래된 계산 결과를 현재 문서에 적용하지 않는 편을 우선했습니다.

텍스트가 합쳐졌다고 문법도 맞는 것은 아닙니다

현재 3-way merge는 문자열과 줄의 차이를 이해합니다. SevenMark AST의 의미까지 알지는 못합니다.

표의 같은 행을 서로 다른 방식으로 수정하거나, 한 사용자가 중첩 괄호의 시작을 바꾸고 다른 사용자가 끝을 바꾸면 텍스트 구간은 겹치지 않아도 결과 문법이 깨질 수 있습니다.

그렇다면 AST-aware merge를 만들면 되지 않을까요?

가능성은 있지만 새로 정해야 할 것이 많습니다.

• 두 AST 노드가 같은 대상을 수정한 것인지 어떻게 판단할까?
• 사용자가 적은 공백과 표기 방식은 얼마나 보존할까?
• 나무마크 입력과 SevenMark 입력을 합치면 어느 문법으로 출력할까?
• 표의 행 이동과 수정은 어떻게 구분할까?

현재는 이 복잡도를 바로 넣지 않았습니다.

1. 텍스트상 독립적인 수정은 자동으로 합칩니다.
2. 같은 범위가 겹치면 충돌로 반환합니다.
3. 합쳐진 본문도 다른 리비전과 똑같이 SevenMark 후처리를 거칩니다.
4. 실제 문서에서 의미 기반 merge가 필요한 사례가 충분히 쌓이면 다시 검토합니다.

3-way merge를 모든 충돌을 해결하는 마법으로 만들기보다, 오래된 편집을 전부 거부할 때 생기는 불필요한 충돌을 줄이는 데 범위를 뒀습니다.

결과 문자열보다 저장을 허용하는 조건을 테스트했습니다

병합 테스트에서는 예제 문자열 하나가 그럴듯하게 합쳐지는지만 보지 않습니다.

• 본문과 문서 요약의 독립된 변경이 함께 합쳐지는가
• 합친 결과가 현재와 같으면 NoChanges가 되는가
• 본문과 문서 요약의 충돌 개수를 따로 계산하는가
• Conflict 응답에 현재 리비전과 본문이 들어가는가
• 자동 병합 뒤에도 사용자가 적은 edit_summary가 남는가
• 다른 문서의 리비전을 원본으로 사용할 수 없는가

동시성 코드에서 중요한 것은 알고리즘이 한 샘플을 합치는 것보다, 어느 시점까지 저장을 허용하는지 명확하게 정하는 일이었습니다.

V7은 merge에 성공했더라도 저장 직전에 권한과 최신 리비전을 다시 확인합니다. 조건이 바뀌었다면 계산한 결과를 버립니다.

같은 문서를 편집했다는 이유로 모든 요청을 충돌시키지는 않지만, 자동화가 사용자의 변경을 잃을 가능성이 생기면 다시 판단을 요청합니다.

처음에는 동시 편집 기능 하나를 넣고 싶었을 뿐인데, 결국 별도의 Rust crate와 리비전 모델, 트랜잭션 직전 재검증까지 이어졌습니다.

다음 글에서는 저장 뒤의 검색과 문서 분석 작업을 처리하기 위해 JetStream을 붙였다가, 왜 Region 내부 작업만 다시 PostgreSQL로 가져오게 됐는지 이야기해보겠습니다.