Operational transformation

하나 이상의 리더 노드가 있는 분산 시스템의 자동 충돌 해결 알고리즘은 흥미로운 연구 분야다. 이 포스트에서는 Google Docs와 같은 공동 편집 애플리케이션에서 충돌을 해결하는것을 목표로 하는 Operational transformation(OT) 기술을 간략히 알아본다.

OT는 문서에 적용된 작업 이력을 추적하는 방식으로 작동한다. 새로운 작업이 수행되면 이력과 비교해 이전 작업과 충돌하는지 확인한다. 충돌하는 경우 이전 작업과 호환되도록 작업이 변환된다. 변환에는 포함과 제외라는 두 가지 주요 유형이 있다. 포함은 두 작업의 효과를 병합하는 반면 제외는 한 작업의 효과를 다른 작업에서 제외한다.

OT의 기본 아이디어는 아래와 같은 간단한 텍스트 편집 시나리오를 사용해 설명할 수 있다. 두 협력 사이트에서 복제된 문자열 “abc”가 있는 텍스트 문서가 주어지고 두개의 동시 작업이 실행된다.

1. O1 = Insert[0,’x’]
2. O2 = Delete[2,’c’]

1과 2의 작업은 두 명의 사용자가 명령한다. 두 작업이 O1과 O2의 순서로 실행된다고 가정하자. O1을 실행하면 문서는 “xabc”가 된다. 그 다음에 O2를 실행하려면 O2가 O1이 실행한 변환 작업에 대해 작업을 Delete[3,'c']로 만들어야 한다. “xabc”에서 O2를 실행하면 올바른 문자열인 c가 삭제되고 “xab”로 만든다. 변환 없이 O2를 실행할 경우 c가 아닌 b라는 잘못된 문자가 삭제된다. OT의 기본 개념은 이전에 실행된 동시 작업의 효과에 따라 편집 작업의 매개변수를 변환하여 변환된 작업이 올바른 효과를 얻고 문서 일관성을 유지할 수 있도록 하는 것이다.

OT의 설계 전략 중 하나는 이를 세 부분으로 분할하는 것이다.

1. Control Algorithms : 작업이 변환 준비가 된 시기, 변환해야 하는 작업 및 변환을 수행해야 하는 순서를 결정
2. Properties and conditions : 참조 작업의 영향에 따라 대상 작업에 대한 실제 변환 수행을 담당
3. Transformation Functions : 변환 제어 알고리즘과 기능 간의 관계를 정의하고 OT 알고리즘 정확성 요구 사항으로 사용