- CRDT는 interface일 뿐, 추상화를 하는 방식은 다양함.
https://www.bartoszsypytkowski.com/operation-based-crdts-registers-and-sets/
Strong eventual consistency
- 동일한
update operation set을 가진 노드(ex: client)들은 update Operation의 순서에 상관 없이 최종적으로 같은 상태로 수렴. - updated operation 발생시 replica에게 state 전파
따라서, 아래의 명제들로 확장할 수 있다.
1. 교환법칙과 결합 법칙이 성립(Operation 순서에 상관이 없기 때문)
2. Duplicated operation 허용한다면 멱등성(Idempotent) 성립X. (무효화한다면 멱등성 성립)
+a 교환법칙, 결합법칙이 성립하는 이유
- CRDT는 기본적으로 라티스의 join(semi-lattice) 구조를 따른다.
- Counter 기반 설계의 경우, 각 replica의 카운터를 더하는 덧셈 연산을 join으로 사용하기 때문이다.
이는 interface일 뿐, 결국
1. Data type 설계
2. Operation merge 전략
에서 교환법칙, 결합법칙, 멱등성의 조건을 만족하도록 추상화 하는 것이 본질로 보인다.
P: 이벤트의 수신 순서에 따라 교환 법칙이 깨지는 경우
하지만 수신받은 Operation의 "순서"가 교환법칙에 위배되는 경우가 있다. 이벤트의 인과관계나 context가 존재하는 경우가 그것이다.
즉, 단순 commutativity만으론 동시 삽입이 어느 순서로 반영돼야 할지 결정할 수 없다.
이는 Operation Event 안에, Vector Clock을 추가하여 해결할 수 있다.
예를 들어, 노드가 수신한 update Operation stack이 [<1,0,0,2>, <1,0,0,0>, <1,0,0,1>]와 같은 경우, 수신 순서와 무관하게 [<1,0,0,0>, <1,0,0,1>, <1,0,0,2>] 순서로 정렬할 수 있음
