Cassandra: CRDT

https://aphyr.com/posts/294-jepsen-cassandra

카산드라의 write loss 에 대해서 다루고 있는 글.

CRDT, Vector clocks, Isolation Levels 등의 개념에 대해 접할 수 있었고,

CRDT를 만족하는 CQL을 쓰면 write loss를 없앨 수 있음.

CRDT: semi-lattice의 조건을 만족할때 충돌 없이 Replicated 시킬 수 있는 개념. 

* semi-lattice는 결합법칙 & 교환법칙 & 멱등성

---- 

일찍이 카산드라에서는 vector clocks를 구현하지 않기로 결정했는데, 이유는 속도 저하 때문이었음. 

last-write-win을 모든 케이스에 적용하고, causality graph 를 무시하면서 write를 위한 round trips 횟수를 2에서 1로 줄일 수 있었지만 .. cell을 변경할 안전한 방법은 없음

ConsistencyLeve.QUORAUM or ALL을 이용해서 완벽하게 셀을 동기화할 수 있다고 주장하는 사람들이 있음. 그리고 공식문서에도 아래와 같이 쓰여있음.

```

r/w를 위해서 QUORUM consistency 레벨을 사용하고 있고, replication factor이 3이라고 한다면, 2개 노드는 항상 written, 2개 노드는 항상 read임을 보장할것.

(nodes_written + nodes_read) > replication_factor

```

근데 이것은 정확하지 않다. 테스트해보니깐 28% loss 있었음

CQL에서 merge function이 associative & commutative하면 safe함.

----

CRDT가 뭔지 몰라서 적당히 정리하면서 봤다.

https://medium.com/@istanbul_techie/a-look-at-conflict-free-replicated-data-types-crdt-221a5f629e7e

# Conflict-Free Replicated Data Types(CRDT)

분산시스템에서 쓰는 개념

간단히, 비싼 동기화/컨센서스 없이 오브젝트를 업데이트할 수 있고, 모든 컨커런트 업데이트들이 상호적이고, 모든 업데이트들이 각 replica에 실행될 수 있다면 수렴함을 보장함

이를 보장하기 위해 몇가지 조건을 만족해야되고, 이에 대해 말하려고 한다. 더 자세한 내용은 Marc Shapiro의 논문을 살펴볼 것

그의 논문에는 CRDTs(CvRDT, CmRDT)에 기반한 state-based, operation-based 접근에 대해 설명하고 있다.

CvRDT: convergent replicated data type

CmRDT: commutative replicated data type

State-based replication:

레플리카에 업데이트가 있으면, 로컬 상태를 업데이트하고, 그 레플리카의 full state를 다른 레플리카에 보냄. 

그러므로 종종 모든 레플리카는 full state를 다른 레플리카에 보낸다.

다른 레플리카에서 상태를 받으면 local state 와 merge함. 이 레플리카는 다시 다른 레플리카로 상태를 보냄. 모든 업데이트는 즉시 모든 레플리카로 도달 할 수 있다. 

semi-lattice이고, 업데이트가 증가하는 중이고, 만약 merge function 이 least upper bound라면, 레플리카는 같은 값으로 수렴함을 보장한다. 

가능한 상태가 semi-lattice이기 위해서, merge function은 멱등법칙, 결합법칙, 교환법칙을 보장해야함.

monotonic semi-lattice를 만족할때 우리는 CvRDT라고 부름. 

semi-lattice: algebratically associative, commutative, idempotent binary operations 를 충족할때

Operation-based replication:

이 접근 방식에서는 모든 스테이트를 다른 스테이트로 보내는 비용이 큰 방식은 사용하지 않음. 대신, 변경을 모든 다른 replica들에게 sends/broadcast 하고, update를 리플레이하도록 기대함(state machine replication과 비슷함). 이 broadcast 연산때문에, 두 업데이트가 있을때, 이 업데이트가 다른 순서로 레플리카들에 전달될 수 있음. 그렇다면 어떻게 이걸 converge할까? 업데이트가 교환법칙commutative을 성립할때 업데이트를 할 수 있음, 다시 말해 순서와 상관없이 적용가능할때, 결과가 같을 것이라는 것. 업데이트가 전부 모든 레플리카에 broadcast될때, CmRDT라고 부른다. 

디자인에 의해서 CRDT는 consensus를 사용하지 않기 때문에 strong limitation을 가짐. CRDT는 모든 가능한 update operations가 교환법칙이 성립될때만 해결할 수 있음. 

그래서 상태가 단조증가 monotonically increasing 인 예제를 들어서 설명하고 있음.