💻 computer science

A Datalog Framework for Conflict-Free Replicated Data Types

이 논문은 복잡한 동시 협업 애플리케이션의 체계적인 명세, 자동화된 분석 및 속성 기반 테스트를 가능하게 하기 위해 충돌 없는 복제 데이터 타입(CRDT)을 실행 가능한 논리 프로그램으로 모델링하는 선언적 Datalog 프레임워크를 소개한다.

원저자: Elena Yanakieva, Annette Bieniusa, Stefania Dumbrava

게시일 2026-06-01

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Elena Yanakieva, Annette Bieniusa, Stefania Dumbrava

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 거대한 공유 디지털 레고 성을 만드는 팀의 일원이라고 상상해 보세요. 모두가 자신만의 성 복사본을 가지고 있으며, 인터넷에 연결되어 있지 않거나 오프라인 상태일 때도 언제든 브릭을 추가하거나 제거할 수 있습니다. 여기서 발생하는 큰 문제는 다음과 같습니다: 두 사람이 동시에 같은 부분을 수정하려고 하면 어떻게 될까요?

만약 A라는 사람이 빨간 탑을 추가하고, 동시에 B라는 사람이 그 탑의 밑받침을 제거한다면 어떻게 될까요? 탑은 그대로 남을까요? 아니면 사라질까요? 아니면 성 전체가 무너질까요?

이 논문은 설계자들이 실제 소프트웨어를 구축하기 전에 이러한 복잡한 상황에 대한 규칙을 파악할 수 있도록 돕는 CRDTLog라는 새로운 도구를 소개합니다. 이 도구가 어떻게 작동하는지 쉽게 설명하면 다음과 같습니다:

1. 문제점: 디지털 데이터의 "그가 그랬대, 그녀가 그랬대" 현상

과eld에는 컴퓨터가 변경 사항을 만들기 전에 모든 사람이 동의할 때까지 기다려야 했습니다. 하지만 현대의 앱(협업 드로잉 도구나 공유 문서 등)에서는 사람들이 오프라인으로 작업하다가 나중에 동기화할 필요가 있습니다. 이 과정에서 "충돌"이 발생합니다.

개발자들은 보통 CRDT(Conflict-free Replicated Data Types)라고 불리는 미리 만들어진 빌딩 블록을 사용합니다. 이것을 규칙이 내장된 레고 브릭이라고 생각하면 됩니다. 예를 들어, "Set" 브릭에는 "누군가 브릭을 추가하고 동시에 다른 누군가가 그것을 제거한다면, 브릭은 유지된다"와 같은 규칙이 있을 수 있습니다.

문제는 이러한 CRDT 브릭들을 조립하여 복잡한 것들(연결된 노드와 엣지로 이루어진 그래프 등)을 만들 때 발생합니다. 규칙이 의도한 대로 작동할 것이라고 생각했지만, 막상 브릭을 끼워 맞추다 보면 "매달린 엣지"(반대편에 땅이 없는 다리)가 생기거나 예상치 못하게 데이터가 유실될 수 있습니다.

2. 해결책: 논리 기반의 "시뮬레이션 샌드박스"

저자들은 CRDTLog라는 프레임워크를 만들었습니다. 복잡한 코드를 작성하여 이 규칙들을 테스트하는 대신, 매우 엄격한 논리적 레시피와 같은 Datalog를 사용합니다.

Datalog를 데이터의 시뮬레이터 또는 비행 시뮬레이터라고 생각해보세요:

입력값: 시뮬레이터에 이벤트의 "이력"을 입력합니다 (예: "사용자 1이 노드를 추가함", "사용자 2가 엣지를 제거함", "사용자 3이 동시에 엣지를 추가함").
규칙: 데이터가 어떻게 행동해야 하는지에 대한 규칙을 작성합니다 ("이상적인 버전").
테스트: 또한 당신이 선택한 특정 CRDT 브릭 조합이 실제로 어떻게 작동하는지도 작성합니다 ("실제 버전").
결과: 시뮬레이터는 두 버전을 나란히 실행합니다. 만약 "이상적인" 버전과 "실제" 버전이 정확히 같은 성을 만든다면, 당신의 설계는 성공적인 것입니다. 만약 두 버전이 다르다면, 시뮬레이터는 논리가 어디서 깨졌는지 정확히 보여줍니다.

3. 테스트 방법: 그래프 케이스 스터디

저자들은 이 도구가 작동함을 증명하기 위해 협업 그래프(점과 선으로 이루어진 네트워크, 예: 지도나 소셜 네트워크)를 대상으로 테스트를 진행했습니다. 그들은 삭제를 처리하는 두 가지 방식을 살펴보았습니다:

시나리오 A (고립 삭제 - Isolate-Delete): 연결된 선이 없는 점만 삭제할 수 있습니다. 만약 누군가 점을 삭제하려 할 때 다른 누군가가 그 점에 선을 추가하려고 한다면, 선이 "승리"하여 점은 유지됩니다.
시나리오 B (분리 삭제 - Detach-Delete): 점을 삭제하면, 누군가 동시에 선을 추가하려고 하더라도 연결된 모든 선이 함께 사라져야 합니다.

그들은 CRDTLog를 사용하여 두 시나리오에 대한 "이상적인 규칙"을 구축했습니다. 그런 다음 표준 CRDT 브릭들을 사용하여 이를 구현하려고 시도했습니다.

발견: "분리 삭제" 시나리오의 경우, 단순한 브릭 조합은 실패했습니다. 이는 "매달린 선"(아무것도 연결되지 않은 선)을 만들어냈습니다.
해결: CRDTLog는 왜 실패했는지 정확히 보여주었습니다. 그들은 선이 올바르게 사라지도록 하기 위해 브릭을 조립하는 방식(다른 변환 규칙 사용)을 변경해야 했습니다.

4. 이것이 중요한 이유

이 논문은 이 접근 방식이 이러한 복잡한 데이터 타입을 프로토타이핑하고 분석하는 데 Datalog를 체계적으로 사용한 첫 번째 사례라고 주장합니다.

설계도 검사: 건물을 짓기 전에 수학적 계산을 확인하는 것과 같습니다. 이 도구는 당신의 데이터 규칙에 대한 "수학"을 검사합니다.
빠른 속도: 저자들은 수천 명의 시뮬레이션된 사용자와 이벤트를 사용하여 테스트했습니다. 이 도구는 이러한 테스트를 자동으로 실행할 수 있을 만큼 충분히 빨랐으며, 이는 값비싼 전체 소프트웨어 시스템을 먼저 구축하지 않고도 복잡한 로직을 검증할 수 있음을 입증합니다.
숨겨진 버그 포착: 표준 빌딩 블록들이 개발자가 기대했던 방식대로 작동하지 않는 미묘한 문제들을 찾아냈습니다.

요약

요약하자면, 저자들은 개발자가 자신의 데이터 규칙을 가지고 "만약 ~한다면?"이라는 가정을 해볼 수 있는 논리 기반 시뮬레이터를 만들었습니다. 이 도구는 선택한 디지털 빌딩 블록 조합이 실제로 원하는 성을 만들어낼지, 아니면 떠 있는 다리와 사라진 벽이 있는 성을 만들게 될지를 미리 보여줍니다. 그들은 복잡한 협업 그래프 애플리케이션을 성공적으로 디버깅함으로써 이 도구의 효용성을 입증했습니다.

기술 요약: CRDT를 위한 Datalog 프레임워크

문제 정의

분산 애플리케이션은 점진적으로 로컬 우선(local-first) 협업에 의존하고 있으며, 이는 여러 사용자가 전역적인 조정 없이 공유 데이터를 동시 업데이트할 수 있도록 합니다. CRDT(Conflict-Free Replicated Data Types)는 결정론적 수렴과 강한 최종 일관성(Strong Eventual Consistency, SEC)을 제공하는 메커니즘을 제공하지만, 이를 통해 복잡한 애플리케이션을 구축하는 것은 여전히 어려운 과제입니다. 개발자들은 더 풍부한 동작을 구현하기 위해 여러 기본 CRDT(예: set, map, sequence)를 조합하여 사용하곤 합니다. 그러나 충돌 해결 정책은 예측 가능하게 결합되지 않습니다. 미묘한 동시성 패턴으로 인해 조합된 CRDT가 의도한 애플리케이션 시맨틱(semantics)을 위반하는 상태로 수렴할 수 있습니다.

현재는 특정 동시 실행 결과가 왜 발생하는지를 설명할 수 있는 명시적이고 분석 가능한 사양(specification)이 부족합니다. 개발자들은 협업 그래프에서의 고립된 에지(dangling edge) 부재와 같은 불변량(invariant)을 다룰 때, 특정 CRDT 조합이 의도한 애플리케이션 로직을 충실히 실현하는지 검증하는 데 어려움을 겪습니다. 정식 검증(Formal verification)은 비용이 너무 많이 들고 전문가 수준의 지식을 요구하는 경우가 많으며, 임시적인 테스트(ad-hoc testing)는 복잡한 동시성 예외 사례를 놓칠 수 있습니다.

방법론

저자들은 CRDT의 시맨틱을 명세화, 프로토타이핑 및 분석하기 위해 Datalog(구체적으로 Soufflé 엔진)로 구현된 선언적 프레임워크인 CRDTLog를 제안합니다. 핵심 방법론은 CRDT 시맨틱을 연산 컨텍스트(operation contexts) 상의 실행 가능한 논리 프로그램으로 모델링하는 것입니다.

1. 연산 컨텍스트 (Operation Contexts)

본 프레임워크는 Burckhardt의 복제 데이터 타입 모델을 채택하고 일반화합니다. 연산 컨텍스트 $C = (E, op, vis, ar)$는 다음과 같이 정의되는 유한한 이벤트 그래프입니다:

$E$ 는 이벤트의 집합입니다.
$op$는 이벤트를 연산 세트로 매핑합니다(이벤트당 여러 연산의 원자적 실행을 허용함).
$vis$는 비순환 가시성 관계(happens-before)입니다.
$ar$은 전체 중재 순서(total arbitration order)입니다(last-writer-wins과 같이 시맨틱이 요구하는 경우에만 사용됨).

복제 데이터 타입 $F_X$ 는 연산과 컨텍스트를 입력받아 반환 값을 생성하는 결정론적 함수입니다. Datalog에서 이러한 컨텍스트는 입력 관계(setEvent, vis, ar)로 인코딩되며, 결과 상태는 출력 관계로 도출됩니다.

2. 사양 워크플로우 (Specification Workflow)

프레임워크는 개발자를 위해 두 계층의 워크플로우를 지원합니다:

사양 수준 시맨틱 (Specification-Level Semantics, SLS): 특정 CRDT 설계와 독립적으로, 의도한 애플리케이션 동작을 정의하는 고수준의 선언적 정의입니다. 이는 연산 컨텍스트 상의 Datalog 규칙으로 직접 작성됩니다.
구현 수준 조합 시맨틱 (Implementation-Level Compositional Semantics, ICS): 기본 또는 중첩된 CRDT의 조합을 사용하여 애플리케이션을 구현하는 과정입니다. 여기에는 애플리케이션 수준의 연산을 구성 요소 수준의 연산으로 매핑하는 **변환 규칙(transformation rules)**을 정의하는 작업이 포함됩니다.

이 프레임워크는 **속성 기반 테스트(property-based testing)**를 가능하게 합니다. 생성된 동시 실행(연산 컨텍스트) 세트가 주어지면, 시스템은 ICS가 SLS와 동일한 상태로 수렴하는지 확인합니다. 만약 두 결과가 일치하지 않으면, 해당 분해(decomposition)를 수정합니다.

3. 중첩 및 복합 CRDT 처리

프레임워크는 다음을 지원합니다:

중첩된 CRDT (Nested CRDTs): Map⟨Set⟩과 같은 구조입니다. Soufflé와 같은 Datalog 엔진은 동적 모듈 인스턴스화를 지원하지 않으므로, 프레임워크는 키(key)가 범위 식별자(scope discriminator) 역할을 하는 인덱싱된 세트를 사용하여 중첩 구조를 인코딩합니다.
복합 CRDT (Composite CRDTs): 복잡한 애플리케이션(예: 협업 그래프)은 더 단순한 CRDT(예: 노드를 위한 Set과 에지를 위한 Map)로 분해하고, 충돌 유도(conflict induction)를 처리하는 변환 규칙을 정의함으로써 모델링됩니다(예: 에지 추가가 동시적인 노드 삭제를 무효화하도록 보장).

주요 기여

선언적 프레임워크: Datalog로 구현된, CRDT 및 협업 애플리케이션 시맨틱을 명세하기 위한 확장된 프레임워크를 제공합니다.
CRDTLog 구현: 기본, 중첩 및 복합 CRDT에 대한 사양 라이브러리와 연산 컨텍스트를 생성하고 시맨틱 결과를 비교하는 도구를 갖춘 Soufflé 기반 시스템을 구축했습니다.
협업 그래프에 대한 케이스 스터디: 두 가지 그래프 변형에 대한 상세 분석을 수행했습니다:
- Isolate-Delete (ID): 노드는 격리된 경우에만 제거될 수 있습니다.
- Detach-Delete (DD): 노드를 제거하면 모든 인접 에지가 제거됩니다.
  이 연구는 프레임워크가 어떻게 비직관적인 동시성 동작을 드러내는지 보여줍니다. 예를 들어, Map⟨Set⟩을 사용하는 나이브한 DD 그래프 분해는 업데이트 승리(update-wins) 시맨틱의 충돌로 인해 dangling edge를 발생시킬 수 있으며, 이를 해결하기 위해 평탄한 에지 튜플 세트(flat set of edge tuples)를 사용하는 특정 변환 전략이 필요함을 보여줍니다.
경험적 평가: ID 및 DD 그래프 애플리케이션을 사용하여 속성 기반 테스트를 통한 체계적인 평가를 수행했습니다.

실험 결과

저자들은 ID 및 DD 그래프 애플리케이션을 사용하여 프레임워크를 평가했습니다:

시맨틱 등가성 (RQ1): 8가지 구성(복제본 및 이벤트 수 변화)에 대해 1,000개의 독립적인 실행을 수행한 결과, ICS와 SLS는 동일한 관찰 가능한 상태를 생성하였으며, 이는 CRDT 조합의 정확성을 입증합니다.
확장성 (Scalability):
- 그래프 크기: 노드와 에지의 수가 증가함에 따라 ICS 구현이 SLS보다 현저히 빨라졌습니다(대규모 그래프의 경우 최대 10배 차이). 이는 분해가 규칙의 복잡도와 조인(join) 크기를 줄이기 때문입니다.
- 동시성: 복제본 수를 늘려도(2개에서 16개로) 런타임에 미치는 영향은 미미했습니다. 이는 복제본 수가 규칙 평가의 복잡성보다는 주로 가시성 관계의 구조에 영향을 미치기 때문입니다.
- 이벤트 볼륨: 평가 비용은 주로 연산 컨텍스트 내의 이벤트 수에 따라 결정됩니다.
증분성 (Incrementality): 증분 Datalog 엔진인 DDlog으로 인스턴스화했을 때, 프레임워크는 대화형의 단계별 검증을 지원했습니다. 배치 프로세싱을 위한 Soufflé보다는 느리지만, 탐색적 설계를 위한 중소규모 컨텍스트에는 실용적인 수준이었습니다.

의의 및 주장

본 논문은 복잡한 CRDT 및 그 조합을 프로토타이핑하고 분석하기 위해 Datalog를 기초로 사용한 첫 번째 연구라고 주장합니다.

이 연구의 의의는 개별 CRDT의 정확성을 검증하는 것(Peepul 등의 연구)에서서 벗어나, 조합 전반에 걸친 애플리케이션 수준의 시맨틱을 검증하는 데 초점을 맞추었다는 점에 있습니다. 의도한 동작과 CRDT 조합 사이의 시맨틱 불일치를 명시적이고 실행 가능하며 반증 가능하게 만듦으로써, 개발자는 다음과 같은 이점을 얻을 수 있습니다:

실제 분산 구현에 착수하기 전에 대안적인 CRDT 분해 방식을 탐색할 수 있습니다.
동시적 상호작용의 예외 사례를 체계적으로 테스트할 수 있습니다.
충돌 해결의 시맨틱 핵심을 프로토콜 및 엔지니어링 선택 사항으로부터 분리하여 고립시킬 수 있습니다.

저자들은 본 프로토타입이 Soufflé를 사용하지만, 접근 방식 자체는 많은 엔진에서 사용 가능한 표준 Datalog 기능(재귀, 계층적 부정, 집계)에 의존하고 있음을 밝히며 신중한 입장을 유지합니다. 또한 분산 애플리케이션의 정식 검증은 여전히 전문가 수준의 영역임을 인정하며, 본 연구가 설계 단계에서 사용할 수 있는 가볍고 체계적인 테스트 대안을 제공한다고 설명합니다. 향후 과제로는 기계가 검증 가능한 증명을 위해 CRDTLog을 정리 증명기(theorem prover)로 공식화하는 것을 포함합니다.