CRDT 학습공유

S062

Sequence CRDT

RGA

RGAList

톰스톤

Logical clock(램포츠), vector clock

• RGASplitTree

OT(Operational Transformation)

---

OT방식은 2006년이전까지 많이 사용했던 방법으로 큰 특징은 다음과 같다.

• 서버가 중앙에서 관리한다.
• 인덱스 기반으로 입력을 관리한다.

입력한 순서에 따라 서버가 이를 적절히 변형해 전달하는 방식이다.

OT는 시간을 근거로 우선순위를 부여하고, 앞에서 적용할 변경사항이 다음 순위의 변경사항을 보정하는 정보로 사용된다.

유저1이 맨앞에 ‘C’를 입력하고,

유저2가 맨앞의 문자(인덱스 0)를 삭제했다고 가정해보자.

유저 1의 이벤트가 먼저기 때문에, ‘C’가 삽입되고, 유저 2의 삭제 인덱스는 한칸씩 밀리게 된다.

하지만, 중앙에서 보정을 해줘야 하는 서버가 필요하다는 단점이 존재하다.

CRDT(Conflict free Replicated Data Types)

---

OT방식을 보완하기 위해 2006년 이후에 등장한 자료구조로, 특징은 다음과 같다.

• 분산 컴퓨팅에서 여러 디바이스에 복제되는 자료구조
• 다른 PC의 복제본을 건들지 않고, 모든 복제본을 독립적으로 동시에 업데이트 가능.
• 자료구조의 알고리즘은 데이터 불일치를 해결

💡

분산 컴퓨팅

분산 컴퓨팅에서 대부분인 concurrent한 복제본의 업데이트를 막는 것에 중점을 두었다.

하지만 낙관적 복제는 concurrnet한 업데이트를 허용하고, 병할할 때, 이를 해결한다.

CRDT는 이를 지원한다.

Types of CRDTs

CRDT는 즉, 최종 일관성에 관심을 가진다. 이를 어떻게 해결하냐에 따라 크게 2가지로 나뉜다.

State-Based CRDTs

CvRDTs라고도 불리며, Local State와 작업을 위한 State로 구분된다.

또한, 3가지의 function을 가지고 있다.

• 초기 상태를 생성하는 함수
• 상태를 병합하는 함수 (merge)
• 상태를 업데이트하는 액션을 적용하는 함수

State-Base CRDT(CvRDT)는 업데이트할 때마다 전체 local state를 복제본으로 보내고, 수신을 받으면 local state에 이를 반영한다.

이때, merge함수는 다음 조건을 만족해야 한다.

• 교환 법칙(commutative): 병합 순서와 상관없이 동일한 결과를 보장.
• 결합 법칙(associative): 병합 그룹화 방식에 상관없이 동일한 결과를 보장.
• 멱등성(idempotent): 동일한 상태를 여러 번 병합하더라도 결과가 변하지 않음.

Operation-Based CRDTs

CmRDT라고도 불리며, merge function없이 정의된다.

상태를 전송하는 대신 업데이트 작업이 복제본으로 전송된다.

일관성은 다음과 같이 적용된다.

• 교환 법칙과 결합법칙을 충족해야 한다.
• 멱등성을 요구하진 않지만, 중복없이 전달되어야 한다는 필요가 있다.

둘간의 비교

상태 기반 CRDT가 구현에 있어서 이점.

Known CRDTs

G-Counter (상태 기반)

payload integer[n] P
    initial [0,0,...,0]
update increment()
    let g = myId()
    P[g] := P[g] + 1
query value() : integer v
    let v = Σi P[i]
compare (X, Y) : boolean b
    let b = (∀i ∈ [0, n - 1] : X.P[i] ≤ Y.P[i])
merge (X, Y) : payload Z
    let ∀i ∈ [0, n - 1] : Z.P[i] = max(X.P[i], Y.P[i])

상태 기반 CRDT는 n 노드들의 클러스터를 위해 counter를 구현한다.

각 노드드 0~n-1의 ID값을 갖는다.

각 node는 array의 하나의 슬롯에 저장된다.

PN-Counter

G-Set

추가만 허용한다. remove는 불가능.

2P-Set

• remove set
• G-set(추가)

G-set에서 remove 기능이 추가된 것이다.

한번 삭제된 element는 re-added가 안된다.

⇒ element e가 tombstone set에 있으면, 쿼리는 true를 리턴하지 않음!

2P-set은 remove win이기에, remove된것이 add보다 우선시 된다.

LWW

LWW는 2P-set에서 각 element들이 timestamp를 가지고 있다.

Element들은 timestamp와 함께 add Set에 추가된다.

또한, 제거이후에 다시 추가가 가능하다.

Merge할 때, timestamp가 동일하다면, 편향성이 적용된다.

⇒ 제거 혹은 추가 쪽으로

💡

timestamp

실제 시간일 수도 있지만, 값이 업데이트 될때마다 증가하는 정수로 표현되는 타임스탬프를 사용함.

⇒ 가장 최근에 작성된 값으로 현재 값을 덮어쓴다.

두 PC간의 시간 동기화 문제 때문에 이런 논리 시계를 사용

[LWW Register]

• 하나의 값에서 유용

[LWW Map]

• 공유해야 하는 것이 하나 이상의 값일 때 필요.

OR-Set

OR-Set은 LWW에서 timestamp대신 unique한 tag를 사용한다.

Sequence CRDTs

Sequence CRDT는 OT를 대신해 collaborative real-time editor에 사용할 수 있다.

Sequence CRDT는 Treedoc, RGA, Woot …

Sequence CRDT

---

• P2P(검증 필요)
• ID기반으로 입력을 관리.

💡

OT방식에서의 교환 법칙

OT방식에선 앞선 연산이 뒤의 연산에 영향을 주게 된다. 따라서, 교환 법칙이 성립될 수 없다.

중앙 서버가 필요없고, 편집하는 유저들끼리만 데이터를 교환하면 되기에 속도가 빠르다.

CRDT는 스트림 상의 각 문자에 고유한 id를 부여하고, 이를 기반으로 보정을 정의한다.

CRDT는 변경사항을 보정할 필요 없이 바로 다른 유저의 문서에 적용된다.

시간 순서에 대한 우선순위 없이 정확한 위치에 문자를 삽입할 수 있다.

유저 1이 ‘C’를 맨앞에 추가하는 경우, 새로운 아이디를 부여하고, 문자를 id가 1인 문자의 위치에 추가한다.

이때, 만약 두 유저가 동일한 위치의 문자를 삭제하더라도, id를 기반으로 하기에 중복 삭제 걱정이 없다.

충돌

만약 Hello라는 문자열이 있다.

A라는 유저가 ‘l’과 ‘o’사이에 문자열 ‘p’를 추가해본다고 가정하자.

또한, B라는 유저가 ‘l’과 ‘o’사이에 문자열 ‘k’를 추가해본다고 가정하자.

그렇다면 인덱스가 겹치게 되어 충돌 현상이 발생한다.

따라서, 이를 해결하기 위한 다른 알고리즘을 사용하게 된다.

Reference

https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type

https://blog.stackademic.com/understanding-crdts-and-lww-with-swift-a-deep-dive-dc98205e3aae

https://fireheal.tistory.com/118

https://junghan92.medium.com/%EB%B2%88%EC%97%AD-crdt%EC%97%90-%EB%8C%80%ED%95%9C-%EC%9D%B8%ED%84%B0%EB%9E%99%ED%8B%B0%EB%B8%8C-%EC%9E%85%EB%AC%B8-818403128cca

https://jsonjoy.com/specs/json-crdt/model-document/crdt-algorithms

S008

Sequence CRDTs

데이터의 순서를 유지해야 하는 환경에서 사용되는 CRDT 유형이다. 주로 동시 작업을 처리하기 위해 사용되며 각 작업이 고유하게 식별된다.

특징

• Identifier 기반: 각 작업은 고유한 식별자를 가짐.
• 순서 보장: 작업 순서를 논리적으로 유지.
• 작업 통합: 서로 다른 노드에서 발생한 변경사항이 충돌 없이 병합.

→ RGA (Replicated Growable Array)가 여기에 속한다.

RGA (Replicated Growable Array)

같은 순서가 중요한 데이터를 다루기 위한 Sequence CRDT이다.

Array 가 붙어 있지만, 실제 구현은 대부분 연결 리스트 구조를 사용한다. 이는 배열보다 요소간의 삽입/삭제가 용이하기 때문이다.

방식

• 각 요소는 고유 식별자(Identifier)를 가진다.
• 삽입: 새로운 요소는 기존 요소의 참조를 기준으로 삽입한다.
• 삭제: tombstone(묘비)을 남겨 다른 노드에서도 동일한 삭제를 적용할 수 있다.
• 노드 간 변경사항 동기화 시, 각 노드가 RGA 규칙에 따라 충돌 없이 병합한다.

특징

• 간단한 구조로 순서를 유지.
• 삭제된 요소를 Tombstone으로 추적해 일관성을 유지.

[GitHub - pfrazee/crdt_notes at 68c5fe81ade109446a9f4c24e03290ec5493031f]

RGA List

RGA의 일반화된 형태로, 리스트 형태의 데이터를 관리한다. 리스트에서의 요소 추가/삭제를 RGA의 원리로 관리하여 일관성과 동기화를 유지한다.

Sequence를 Linked List로 구현한 경우 RGA List라 부른다.

특징

• v 요소 다음에 a 원소를 가지고 있는 새로운 요소를 추가하는 addRight(v, a) 기능을 제공한다.
• 각 요소는 고유 식별자(Identifier)를 가진다.
• 만약 두 호출이 t와 t’를 모두 리턴한다면, 이는 t가 t’ 보다 먼저 발생했기 때문이다.
• 같은 위치에 있는 두 개의 다운스트림 삽입은 타임스탬프의 반대 순서로 정렬된다.
• 정점을 제거하면 동시 추가 작업을 수용하기 위해 timestamp가 남는다.

The Replicated Growing Array (RGA) implements a sequence as a linked list (a linear graph). It supports operations addRight(v,a), to add an element containing atom a immediately after element v. An element’s identifier is a timestamp, assumed unique and ordered consistently with causality, i.e., if two calls to now return t and t', then if the former happened-before the latter, then t < t'. If a client inserts twice at the same position, as in addRight(v,a); addRight(v,b), the latter insert occurs to the left of the former, and has a higher timestamp. Accordingly, two downstream inserts at the same position are ordered in opposite order of their timestamps. As in Add-Remove Partial Order, removing a vertex leaves a tombstone, in order to accommodate a concurrent add operation.

RGA Split Tree

RGA를 개선한 구조로, 텍스트 편집과 같은 매우 세밀한 동작이 필요한 환경에 적합하다.

차별점

• 트리 구조: RGA의 리스트 구조 대신 트리를 사용하여 성능을 최적화한다.
• 효율성: 연산 복잡도를 줄이고, 많은 요소를 동적으로 관리가 가능하다.
• 트리 기반으로 요소를 관리하여 노드 삽입/삭제의 효율성이 증가한다.

특징

• 성능 최적화(특히 대규모 데이터 편집 환경에서 유리).
• 삽입/삭제 연산의 효율적 관리.

CRDT Tombstone

요소가 삭제되었음을 나타내기 위한 마커이다. Tombstone을 사용하는 이유는 데이터의 일관성을 유지하고, 다른 노드에서 동기화할 때 삭제 작업을 인식하도록 하기 위함이다.

즉, 삭제된 요소는 리스트에서 물리적으로 제거되지 않으며, tombstone으로 표시되어 동기화 시 삭제 상태가 유지된다.

단, Tombstone은 영구적으로 유지되지 않고, 일정 조건에서 Garbage Collection으로 제거된다. (필요 시) (예를 들어, tomstone 정보가 모두 동기화가 되었다고 확인되었을 때)

작동 방식

• 요소가 삭제되면 tombstone으로 표시한다.
• tombstone은 여전히 다른 노드에서 전파되고, 삭제된 요소는 무시된다.
• 특정 시점에서 tombstone은 garbage collection을 통해 제거 가능하다.

장점

• 삭제 정보를 유지하며 충돌 방지.
• 동기화 과정에서 삭제된 요소를 정확히 처리.

단점

• tombstone이 많아지면 메모리 사용량 증가.
• Garbage collection이 필요.

구조

• Element ID: 삭제된 요소의 고유 식별자.
• Timestamp: 삭제된 시점을 나타내는 타임스탬프(논리적 또는 물리적 시간).

Logical Clock (by Leslie Lamport)

분산 시스템에서 이벤트 간의 순서 관계를 유지하기 위한 기법이다. 물리적 시간 대신 이벤트의 순서를 비교할 수 있는 논리적 시간값을 제공한다.

Vector Clock 알고리즘의 기반을 제공하며, 분산 운영 체제에는 글로벌 클록이 없기 때문에 램포트의 논리 시계가 필요하다.

즉, 분산 시스템에서 물리적 시간은 정확하지 않을 수 있으므로, 논리적 순서를 나타내는 값으로 이벤트를 추적한다. 이때 각 이벤트는 정수 값으로 표현된 타임스탬프를 가진다.

Lamport Timestamp

• 각 이벤트는 숫자로 표현된 타임스탬프를 가진다.
• 이벤트가 발생할 때마다 해당 타임스탬프를 증가시킨다.
• 메시지가 전송되면, 수신자는 자신의 타임스탬프를 보낸 타임스탬프와 비교하여 더 큰 값을 채택하고 1 증가시킨다.

특징

• 단순하고 계산 비용이 낮음.
• Causal Order(원인-결과 관계)를 보장.

한계

• 동시 발생한 이벤트를 구별하지 못함.

연산 기준

• 동일한 프로세스의 벡터 클록에서 A가 B 보다 먼저 발생했다면, 특정 프로세스에서 A의 시간은 B 보다 짧다.
• 이때, A의 클록 값은 B 보다 작다.
• 아래 링크 참고

[Lamport's logical clock - GeeksforGeeks]

구현 규칙에 따른 결과 예시

• 프로세스 A의 Clock 값: 5
• 프로세스 B의 Clock 값: 3
• A에서 B로 메시지 전송: 메시지의 Clock 값은 6(A의 Clock 값 증가 후 전송).
• B는 메시지를 받고 자신의 Clock 값을 max(3, 6) + 1 = 7로 업데이트.

Vector Clock

Logical Clock의 단점을 보완하여 분산 시스템에서 정확한 동시성 정보를 유지할 수 있도록 한다.

구조

• 각 노드는 자신의 타임스탬프를 포함한 벡터를 유지.
• 벡터의 길이는 네트워크 내 노드의 수와 같음.
• 이벤트 발생 시, 해당 노드의 타임스탬프를 증가.
• 메시지 전송 시, 벡터를 함께 보내고, 수신자는 벡터를 병합하여 업데이트.

장점

• 동시성 관계를 명확히 알 수 있음.
• Partial Order(부분 순서) 유지 가능.

단점

• 네트워크 노드가 많을수록 벡터 크기가 커짐.
• 추가 메모리와 계산 비용이 필요.