CRDT의 의문점과 문제점
지난번 글은 CRDT 소개, 그리고 장/단점을 간단하게 소개해주셨는데 이번 칼럼은 수학적인 부분에서 CRDT의 특성을 설명해주셨습니다.
CRDT는 탄탄한 수학적 기반을 가진 충돌 없는 자료구조 로 묘사되는 것을 깊게 들여다 보셨는데, 결국 실제 설계단계에서 숨어있는 전제 (이 이론을 구현하려면 100%는 아니고 유사하게 구현 할 수 있다)를 말씀해 주셨습니다.
CRDT의 설계적 모순
CRDT의 노드가 가지는 연산,교환법칙, 멱등 법칙등이 성립할 수 있는 조건을 달성하려면, 상태집합이 semilattice여야 하고, 메세지의 순서 보장이 필요없이 별도의 전역 시계가 필요 없다 가 조건이지만, 실제로는 추가 삭제가 아닌, 추가와 tombstone의 방법을 사용하며 병합은 단순히 합집합의 개념을 사용한다고 말합니다.
semilattice : 합치기만 해도 언제나 일관된 순서로 커지는 구조 (CRDT의 기본 구성 설계 네요)
그리고 많이 쌓인 tombstone을 지울때 로컬 시계만 보고 지우면 수렴이 깨질 수 있다고 말합니다.
(다른 유저들의 문서상태와 달라 질 수 있다는 말 같네용..)
그리고 원인-결과 정보를 내부에 넣는 것인데, (client와 clock으로 id를 결정) 이때 내부 노드 작성에 쓰이는 clock이 15라고 할때 작성된 id가 13이면, 이미 내가 작성한 시점보다 이전에 작성 되어진 글자라고 판단하기에 안전하게 삭제 할 수 있다 라는 설계가 들어간다고 합니다.
이런걸 중첩 반격자 모델링이라고 부른다고 하네요 .
중첩 반격자 모델링: 여러 개의 반격자(semilattice)를 ‘하나의 큰 반격자’로 겹겹이 포갠 구조를 설계
(마치 우리가 text를 렌더링 하는 방식 같다)
연산기반 CRDT도 특별한건 없다
결국 상태역시 operation의 집합이고 연산끼리 교환법칙을 만족하도록 설계한다고 생각하면 반격자 모델이라고 합니다.
반격자 = semilattice
네트워크 인과에 조심
네트워크가 인과관계를 보장한다면, clock을 생략할 수도 있지만, 보장이 깨지는 순간 증명이 모두 무너지기 때문에 의존 대상을 정확히 이해해야 한다고 합니다.
(실제로 crdt A유저와 B유저의 문서상태가 달라지는 버그는 굉장히 많이 경험했었다.)
정리
CRDT는 결국 semilattice인 반격자 이여야 한다.
부분순서를 잘 지켜라
반격자에서 필요한 모든 가정을 모델링 해야한다 (삭제,추가,병합 등등)
CRDT요소를 하위 요소에 보낼때 정확한 설계가 된 곳에 보내줘야한다.
후기
조금 어려운 내용이였는데 결국 수학적 이론과 근거에서 벗어나지 말고 CRDT를 바라보고 구현해야한다 라는 것 같습니다.
CRDT를 구현할꺼면 모든 요소에 성질을 적용시켜라.
잘 구현해라! 를 말씀해 주시는 것 같네요.
가령 구현하면서 충돌이 일어나지 않는 데이터 타입이라면, 이런식으로 동작하겠지 ? 라면서 CRDT의 수학적 근거에서 벗어나는 것을 조심하라 라고 말하는 글 같습니다!
