텍스트 충돌 병합 알고리즘

텍스트 충돌 병합 알고리즘

CRDT(Confict-free Replicated Data Types)

중앙 서버가 필요없고, 문서 편집하는 유저들끼리 데이터를 교환
각 문자에 고유한 id를 부여하고 이를 기반으로 보정
고유한 id 값을 저장하는 메모리와 이를 관리하기 위핸 트리구조 메모리가 필요
Peer-to-Peer 통신이 항상 가능하지 않음
실시간성이 모호해지며 동기화 결과 문자열이 섞여 의도하지 않은 결과물이 나올 가능성 존재
index 대신 unique id(timestamp, actor id) 사용

• Optimistic Replication(local first, sync later)

  • 다수의 복제본을 가지고 있고 복제본의 내용이 달라지는 것을 허용

• Eventual Consistency(convergence)

  • 최종적으로 문서의 상태 동일
  • operaction의 교촨 법칙이 성립해야함

• Text.Stylce Operation

  • 스타일이 추가될 때는 두 문자 사이에 있는 모든 범위에 있는 텍스트에 적용되어야 한다
  • 텍스트가 삽입될 때는 기존에 있던 문자 스타일을 이어받는다

OT(Operational Transformation)

편집 시간과 인덱스를 기반으로 변경사항 보정
중앙 집중 처리 방식
변경사항을 서버에서 모두 받고 알맞게 변경하여 각 클라이언트에게 변경사항 전달