Vector Clock to Solve CRDT Causality
키워드 : 분산 시스템, 동시 발생 이벤트, 인과성 있는 이벤트, 논리 시계
CRDT는 분산 환경에서 여러 데이터 변화를 동시에 적용하고 동일한 데이터를 유지하며, 이때 발생하는 충돌을 각 노드에서 처리할 수 있는 데이터 타입임. 목적에 따라 (순서, 정확한 카운팅, 동일한 자료 집합을 유지하는 것이 중요함 등) 자료구조는 바뀔 수 있고, 자료구조에 따라 합병 연산(삽입, 삭제 등) 은 다르나, 데이터의 일치성을 유지하기 위해서는 다음을 먼저 고려해야함.
- 이벤트는 동시에 발생할 수 있음 (concurrency, 동시성)
- 물리적인 시간 동기화가 이루어져도, 동시에 발생한 이벤트에 대해서는 순서를 파악할 수 없는 문제가 있음.
- 이벤트는 발행한 순서대로 도착하지 않을 수 있음 (causality, 인과성)
- 선행하는 이벤트에 의존하는 이벤트를 먼저 수신받았을 경우, 이를 먼저 처리하면 일관성을 잃을 수 있음.
!https://blog.kakaocdn.net/dn/lzwNP/btsCk3GtOaz/49FI7OYV1qvHhFf7tooPck/img.png
일관성을 위협하는 상기 문제들를 해결하기 위해, 논리 시계 중 벡터시계 개념을 도입했음.
벡터시계는 각 노드마다 모든 노드의 수 만큼 논리 시계를 갖고 있으며, 이벤트를 발행할 때 자신의 시계를 함께 담아 전송함. 각 이벤트를 수신한 노드의 id에 해당하는 논리 시계와 비교하여 이벤트의 인과성을 확인할 수 있고, 동시에 발생한 이벤트에 대해서는 LWW (Last-Writer-wins) 정책을 채택하여 해결했음.
또한 순서가 중요한 자료를 처리하기 위한 CRDT는 구현이 매우 복잡함. 그러나 시간은 한정적이며, 시간 내 완성을 위해 축소할 필요가 있었음.
현재 목표로 하는 MVP에서는 자료의 삽입/삭제 가 선행된 후 CRDT를 사용하는 기능으로 전환함. 즉 자료의 전체적인 인덱스 변화가 없음. 이런 특징을 이용하여 집합 자료형(Set)을 사용하고, 각 자료의 위치를 기재하여 순서를 파악할 수 있도록 타협했음.