CRDT

CRDT

분산 환경에서 이뤄지는 동시 작업에 대해서 최종 일관성을 보장하는 데이터 타입 또는 알고리즘

OT(Operational Transforms)

• 중앙 서버를 이용해 동시 작업에서 데이터 일관성 문제를 해결하는 방법
  1. 여러 클라이언트에서 동시에 생성된 작업들을 중앙 서버로 전송
  2. 모인 작업들을 서버에서 순차적으로 실행
  3. 각 작업을 변경된 상태에 맞춰 변환
  4. 변환된 작업을 각 클라이언트에게 전달
• 대표적으로 Google Doc, MS Office 등에 적용됨

CRDT’s Approach

• 동시 변경 작업의 결과가 작업 집합의 실행 순서에 의존하지 않도록 함
• 작업의 실행 순서와는 상관 없이 같은 작업의 집합을 실행 했다면 결과는 하나로 수렴함

List of CRDT Algorithms

WOOT

TreeDoc

Logoot

RGA

RADT

• ADT의 확장된 형태이며, 특정 작업(OPTYPE)의 집합을 가진 자료구조
• RADT의 상태를 수정하는 작업에 지연된 일관성(Eventual Consistency)을 보장
• 이를 위해 로컬과 원격 알고리즘이 달라야 함
• 동작 방식

  flowchart LR
    subgraph Local
      direction TB
      t1[로컬 작업]
      t2[로컬 RADT]
      t3{수정되었는가?}
      endpoint((끝))
  
      t1-->|로컬 알고리즘|t2
      t2-->t3
      t3-->|No!|endpoint
    end
  
    subgraph Remote
      direction TB
      t4[원격 작업]
      t5[원격 RADT]
  
      t3-->|Yes!|t4
      t4-->|원격 알고리즘|t5
    end
  

  Loading

RADT 목록

• RFA (fixed-size array)
  • 고정된 요소 개수
  • OPTYPE = {Write, Read}
  • 실행 순서의 차이에 의한 불일치 발생
• RHT (hash table)
  • 해시 테이블을 기반으로 고유키를 해싱하여 슬롯 안의 공유된 객체에 접근
  • OPTYPE = {Put, Remove, Read}
  • RFA의 불일치에 더해, Put과 Remove가 슬롯을 동적으로 생성하거나 제거하므로 불일치가 발생
  • 이를 해결하기 위해 객체 컨테이너를 실제로 제거하는 대신 보이지 않게 하는 Tombstone 개념이 필수적
  • Tombstone을 사용하더라도 원격 알고리즘과 로컬 알고리즘이 같다면 불일치 발생
• RGA (growable array)
  • (지금까지의 연구들이 그랬기 때문에) 정수 인덱스로 객체에 접근하는 가변 길이 배열 (논문과 우리의 주요 관심사)
  • OPTYPE = {Insert, Delete, Update, Read}
  • RFA와 RHT의 불일치 문제를 동일하게 가지며, 여기에 작업 순서에 따라 객체 순서가 달라지거나 인덱스가 변경되어 의도하지 않은 작업이 되어버리는 불일치가 존재

작업 교환성(Operation commutativity)

작업 사이에는 두 가지 종류의 관계가 있다.

• Happened-before relation(→): 작업 사이에 순서가 있음
• Concurrent relation(—): 순서에 상관 없이 작업 가능

이를 통해 각 작업을 그래프로 나타낸 것이 CEG(Causally Excutable Graph)이다.

flowchart TD
  o1((O1))
  o2((O2))
  o3((O3))
  o4((O4))
  o5((O5))

  o1 --- o2
  o1 --- o3
  o1-->o4
  o1 --- o5
  o2 --- o3
  o2-->o4
  o2-->o5
  o3-->o4
  o3 --- o5
  o4 --- o5

Loading