date: 2024-02-19 11:15:00 +0900

- 제목: Introducing Hybrid clock
- 발표자/시간: 백범성 ( 약 20~30분 )
- 목차 :
1. lamport clock, vector clock 간략한 소개
2. Yorkie에서의 Clock
3. vector clock의 필요성과 문제점
1. 필요성
- GC 결함
- crdt 자료구조의 연산
2. 문제점
4. hybrid clock in yorkie
- lamport와 vector clock을 섞어 사용하자
- synced vector map ( p2p )
- 장점과 단점
- version vector ( Centralized System )
5. lamport synced vector clock
- 무엇이 다른가?
- 장점과 단점
6. Discussion & Limitation
- 선행 연구와 증명이 있는가?
- 대상
- Yorkie의 logical clock에 관심이 있으신 분

## Abstract
이 보고서에서는 기존 Yorkie 시스템에 Change간 vector clock을 도입하여, 기존 lamport clock으로 인해 해결하지 못했던 문제를 해결하는 과정을 다룬다. lamport clock과 vector clock의 개념부터, 실제 Yorkie 시스템 내 구현 디자인까지 설명한다. 시스템 도입을 위해 제시된 Synced vector map과 Version vector, Lamport synced vector clock 들의 개념을 제시하고, 관련한 문제점들과 향후 방향에 대해 논의하겠다.
## 1. Lamport clock, Vector clock 간략한 소개

### A. Lamport clock
Lamport clock은 distributed computer system에서 발생한 이벤트간 순서를 결정하기 위한 알고리즘이다. 즉 event간 partial ordereing을 제공한다. 알고리즘의 핵심은 이벤트들의 인과 관계이다. a가 b 이전에 발생했다면, 이벤트에 대응되는 논리 시계는 $C(a) < C(b)$ 를 만족해야 한다.
$$
\begin{eqnarray}
\text{If } a \rightarrow b \\
& \text{then } C(a) < C(b) \ \ \ \text{(where} \rightarrow \text{means happened-before)}
\end{eqnarray}
$$

> C(a) : a 이벤트의 Lamport clock

이를 만족하는 Lamport clock 알고리즘의 pseudo-code는 다음과 같다.

- sending

# event is known
time = time + 1;

# event happens
send(message, time);

- receiving

(message, time_stamp) = receive();
time = max(time_stamp, time) + 1;

receiving 과정에서 max 연산과 +1을 해주는 부분은 동기화를 위함이다. 만약 동기화 과정이 없다면, 다음과 같은 문제가 발생한다. A의 전송은 B의 수신보다 먼저 발생했지만, $C(\text{send from A}) > C(\text{B receive})$ 논리 시계 순서가 역전된 상황이다.

pseudo-code의 receiving 과정을 따른 다면, 다음과 같이 순서화를 할 수 있다.

### B. Vector clock
vector clock은 Lamport clock의 이벤트 사이 partial ordering 기능과 논리 시계로부터 이벤트의 인과 관계를 알 수 있는 알고리즘이다. 각 프로세스는 독립된 논리 시계를 가진다. N개의 프로세스라면, N개의 논리 시계를 담고 있는 vector clock을 이용해 상태를 주고 받는다.


> 이미지 출처 : https://en.wikipedia.org/wiki/Vector_clock

알고리즘을 pseudo-code로 나타낸다면 다음과 같다.

# event is known
vec_i[i] = vec_i[i] + 1

# receiving
forAll_k 
	vec_i[k] = max(vec_i[k], vec_j[k])
vec_i[i] = vec_i[i] + 1

기존의 Lamport clock은 다음의 식을 보장했지만, 그 역은 보장하지 못했다.
$$
\begin{eqnarray}
\text{If } a \rightarrow b \\
& \text{then } C(a) < C(b)
\end{eqnarray}
$$
즉 다음과 같이 Lamport clock이 크다고, 이벤트가 인과관계에 있음을 보장 못한다.
$$
\begin{eqnarray}
\text{If } C(a) < C(b) \\
& \text{then } a \rightarrow b
\end{eqnarray}
$$
Lamport clock으로는 순서화가 가능하나, Lamport clock을 가지고 Event가 동시에 발생했는지, 인과적으로 발생했는지 판단할 수 없다.

하지만 Vector clock은 다음의 성질들을 만족한다.
$$
\begin{eqnarray}
\text{If } VC(a) < VC(b) \\
& \text{then } a \rightarrow b
\end{eqnarray}
$$
$$
\begin{eqnarray}
\text{If } a \rightarrow b \\
& \text{then } VC(a) < VC(b)
\end{eqnarray}
$$
$$
VC(x) < VC(y) \triangleq \forall{_z}[VC(x)_z \le VC(y)_z] \ \wedge \exists_{z'} [VC(x)_{z'} \lt VC(y)_{z'}]
$$
이것이 가능한 이유는 Vector clock은 Causal histories를 누적한 것이기 때문이다. 즉 각 프로세스들의 logical clock을 기록하고 있고, 이를 포함 관계로 이용할 수 있기 때문이다.


> 참고 자료 : https://queue.acm.org/detail.cfm?id=2917756

## 2. Yorkie에서의 Clock

### A. 이벤트의 단위
yokie에서는 Lamport clock을 이용한다. 정확히는 Lamport clock을 살짝 변형하여 사용한다. 이벤트의 단위는 Update 함수이다. Update 이벤트는 Change로 저장이된다. 이에 Change를 이벤트의 단위로도 볼 수 있다.

> lamport clock은 partial order를 지원한다. 이는 같은 clock을 가진 상황에 대해서는 비교를 못한다. 이런 상황을 막기위해 Lamport clock에 Actor ID를 추가하여 사용한다. 이를 Tie breaker라고 부르며, Total order를 지원할 수 있어진다.

> Actor ID가 들어간 Lamport clock은 비교 순서가 다음과 같다.
> 1. Clock을 비교
> 2. Actor ID를 비교 ( 알파벳 순서 )

### B. 사용처 - CRDT

분산시스템의 중요한 목표중 하나는 일관성을 유지하는 것이다. CRDT는 낙관적 복제(Optimistic replication)를 목표로한다. 연산간 Commutative를 지원하기에 모든 연산을 주고 받으면, 모든 Client는 같은 상태로 수렴한다. 비슷한 용어로 분산시스템에서는 Eventual consistency라고도 부른다. Lamport clock을 이용하면 어떤 이벤트들을 하나의 기준으로 순서화할 수 있다.
위 그림은 섞여있는 Change들을 Lamport clock으로 정렬함을 보여준다. 순서가 다르더라도, 결국 한 가지 상태로 정렬이 가능하다. CRDT에서는 이 점을 이용하여 commutative를 지원하게 된다.

> 다만 이벤트 단위가 아닌 노드 단위로 위의 내용이 적용된다. yorkie에서는 Time Ticket이라는 구조체가 사용되며, Lamport clock, actor ID, delimiter로 구성되어 사용된다.

잠시 분산시스템의 용어를 살펴보면, Consistency와 반대되는 용어가 존재한다. Split brain이라는 용어이다. 분산시스템의 알고리즘은 이 Split brain을 잡아내는 것이 중요한 목표 중 하나이다.

### C. 사용처 - Garbage collect

Garbage collect는 Tombstone들을 제거해주는 역할을 한다. 이때 제거 범위의 기준은 최소로 동기화된 상태까지이다. 최소로 동기화된 상태의 기준을 현재는 Change의 Lamport clock으로 정하고 있다.

서버는 각 Client들이 Change를 얼마나 적용했는지 기록한다. 이를 이용하면 최소로 동기화된 지점을 찾을 수 있다.

그림을 보면 서버에 받은 Change들을 Lamport clock을 이용해 나열할 수 있다. Client가 모두 가져간 Change까지 Garbage collect을 하기에 A@3 Change까지 GC가 돌게된다.

## 3. vector clock의 필요성

### A. GC 이슈

기존의 Lamport clock를 이용한 garbage collect는 결함이 존재했다. 서버에서 MinSyncedSeq라는 개념을 이용하여 GC할 노드를 판단했었다. 위 그림을 보면 4@B와 4@A를 비교해서 4@A가 MinSyncedSeq가 되고, 4@A 이하의 노드들은 garbage collect된다. 이 판단의 근거는 4@B가 4@A를 적용했을 것이라는 전제 하에 있다.
$$
\begin{eqnarray}
\text{If } \text{4@A} < \text{4@B} \\
& \text{then } A \rightarrow B
\end{eqnarray}
$$
위에서 언급한 바와 같이 Lamport clock은 이를 보장하지 않는다. 실제로 client B는 4@A 이벤트를 실행하지 않은 상태이고, 4@A는 garbage collect되면 안된다.


### B. crdt 자료구조

Text edit이나 Tree edit 연산이나 향후 필요한 기능들에서도 vector clock이 필요하다.
Logical clock을 이용해 event간 인과 관계인지 동시에 발생한 것인지 판단이 필요하기 때문이다. 예로 Text edit을 보면 5@B인 지우는 연산은 동시에 발생한 이벤트인 4@A연산은 제외하고 실행되어야 한다. 하지만 5@B 연산을 받은 client A는 $\text{4@A} < \text{5@B}$ 이므로, 4@A의 event가 5@B의 event보다 선행되었다고 판단한다. 이에 지워버렸고, 이는 Eventual Consistency를 파괴하게 된다. 이를 기존에는 LatestCreatedAtMapByActor라는 구조를 이용해 해결하였다. 하지만 Vector clock이 도입된다면, 이런 상황들을 묶어서 해결할 수 있다.

### C. Vector clock은 GC문제를 해결하는가?

위 그림은 vector clock을 이용하여 아까의 문제 상황이다. Vector clock을 이용하여 서버의 Change들을 정렬하면 [4,3]과 [2,4]는 정렬이 되지 않음을 확인할 수 있다. Vector clock에서는 이 상황을 두 이벤트가 Concurrent하다고 판단한다.

> Partial order이기에 모든 요소가 비교 가능하진 않다.

그렇기에 최소로 동기화된 이벤트를 정확하게 찾을 수 있고, GC 문제를 해결할 수 있다.

### D. 메모리 사용량의 문제점

Vector clock의 가장 큰 문제점은 메모리 사용이다. 위 그림은 GC 문제를 Vector clock을 도입해서 해결한 것이다. 기존 Yorkie는 노드 단위로 Time Stamp를 저장하였다. 이것이 Vector clock으로 바뀌게 되어 노드마다 Vector clock이 존재함을 확인할 수 있다. 하지만 이로 인해 메모리 사용량이 상당히 증가한다. contents보다 meta data가 너무 커지는 문제로 인해 Vector clock은 직접적으로 도입하기가 어렵다.

$$
N(\text{number of nodes}) \times M(\text{sizeOf Vector clock})
$$

## 3. Hybrid clock in yorkie

### A. Lamport clock & Vector clock 섞어 사용하자
Vector clock으로 인한 과도한 메모리 사용을 줄이고, 인과 관계 파악을 위한 방법으로 Hybrid clock이 제시되었다. 이 방법은 기존의 Lamport clock을 그대로 유지하며, Document에서 Vector clock을 관리한다. 즉 노드 단위에서는 Lamport clock이 존재하며, Operation 단위에서 Vector clock이 존재한다.

어떤 연산이 수행되어 Lamport clock이 증가하면, 자신의 Vector clock또한 증가 시킨다.
Change가 생성되면, 그 시점의 Vector clock을 Change에 Copy하여 저장한다.

여기서 Vector clock은 Synced Vector Map이라는 2차원 행렬에 저장된다. 이는 다른 Client들의 Vector clock을 tracking 하기 위함이다. tracking 하는 이유는 garbage collect를 판단하기 위함이다.


위의 그림은 Hybrid clock 컨셉으로 해결한 GC 문제이다. 마찬가지로 Text edit문제 또한 다음과 같이 해결할 수 있다.

Hybrid clock은 문서 전체에서 latestCreatedAtMap를 가지고 있는 것과 비슷하다.

### B. Synced vector map ( p2p )
#### Implementation
위에서 제시된 Hybrid clock의 내부 구현에 대해 설명하겠다. 과정은 필요한 자료구조, Attach, Update, Detach 연산이 발생했을 때, GC가 작동하는 경우, SnapShot의 순서로 설명하겠다.

- Data structures
Document에서는 Synced vector map을 가지고 있는다. 이는 actorID를 key로, Vector clock value로 가진 Map이다. 자신의 vector clock 또한 저장한다. Change에는 해당 Change가 발생했을 때의 Vector Clock이 저장된다. Change의 역할은 다른 client들이 Change's actor의 Vector clock를 업데이트하도록 정보를 준다. Change에는 Detach flag 또한 필요하다.

<img src="https://hackmd.io/_uploads/r11yxO42p.png" width="400" height="200">

- Attach


기본적으로 Attach가 발생하면 Document의 Synced vector map의 initial Actor ID를 서버로부터 받은 ID로 전환한다. 만약 서버에 연결 없이 Document를 편집한다면, initial Actor ID를 기준으로 Synced vector map이 업데이트된다.

전환한 뒤 Change를 서버에 Push하고 Pull한다. Pull한 경우 받아온 Change들을 root에 적용하며 Synced Vector Map을 업데이트한다. 만약 snap shot을 받은 경우, snap shot의 Synced vector map을 자신의 Synced vector Map로 전환한다.

다른 Client P2는 Client A의 Change를 통해 Synced vector Map을 업데이트한다.

- Update


ctx 생성 시에 자신의 Vector를 Synced vector map에서 복사하여 주입한다. 이때 복사하고, 복사본의 Lamport를 증가시킨다. 로컬 operation이 적용될 때마다 Synced vector clock의 자신의 Vector를 업데이트한다. 이후 Change에 자신의 Vector를 복사하여 주입한다.

서버는 Change를 저장한다.

받아온 Change를 적용하는 경우 두 가지 작업을 진행한다. 우선 자신의 vector의 Change의 ID가 Key인 value를 change의 Lamport 값으로 업데이트한다. 그리고 Synced vector map의 Change의 ID가 key인 value를 Change의 vector로 교체한다.

SyncedVectorMap[self][change's ID] = change.Lamport
SyncedVectorMap[change's ID] = change.Vector_clock

- Garbage collect

Garbage collect는 다음과 같이 진행된다. 만약 행렬의 빈 값이 있다면 0으로 만든다.

1. min synced vector(msv)를 구한다.
- synced vector map의 각 actor의 min 값
2. 다음 기준에 따라 purge한다.

node.RemovedAt <= minTicket    

> minTicket
> - Lamport : msv[node.RemovedAt.ActorID]
> - Delimiter : Max delimiter
> - ActorID : node.RemovedAt.ActorID

<img src="https://hackmd.io/_uploads/B10ZgdEn6.png" width="400" height="250">

- Detach
Detach를 한 경우 Synced vector map에서 해당 actor의 vector를 지워야 한다.
이를 위해 Detach된 경우 마지막 Chage의 Detach flag를 true로 설정한다. 이 Change를 받은 다른 Client들은 Synced vector map에서 해당 Vector를 지운다.


- SnapShot
snap shot은 build하는 과정과 pull하는 과정이 있다. build시 Synced vector map을 만들어 데이터베이스에 같이 저장한다. 이후 pull하는 과정에서는 이를 반환해준다. Client는 자신의 Synced vector map을 서버로부터 받은 것으로 교체한다.


#### 장점과 단점

- 장점
p2p 구현이 가능하다.

- 단점
메모리 오버헤드가 너무 크다.
#### 동시 편집자 수에 따른 SVM 공간 복잡도 문제

- `Document`에 SVM(SyncedVectorMap)이 저장되어 있음
- `SVM`은 특정 ActorID 기준에서 다른 ActorID의 Clock이 있는 Map
- 공간 = `O(n^2)`, ActorID = `n`, `actorID = 900` 일때, SVM: `810,000`
- SVM은 Document 편집 중에 Change들 간에 Concurrent or Causal 를 구분하기 위해서 필요함
- SVM은 다음과 같은 물리적인 크기를 갖음
- string key
- unit 크기: 32바이트, lamport 8바이트, actorID 24바이트
- ActorID = 900, 25920000 := 24 MiB
- bytes key
- unit 크기: 20바이트, lamport 8바이트, actorID 12바이트
- ActorID = 900, 16200000 := 15 MiB

- 최적화 A. VectorClock의 Key를 string에서 bytes로 변경
- unit 크기 32 바이트에서 20 바이트로 축소

- 최적화 B. Snapshot으로 Document 빌드 시, SVM 최종 값만 생성
build 할 때는 Synced vector map의 자신의 벡터만 데이터베이스에 저장한다. pull하는 경우에도 만들어진 root와 함께 자신의 벡터만 server pack에 담아 Client에 전달한다. Synced vector map을 전달하지 않는 이유는 오버헤드를 줄이기 위함이다. 이 벡터를 Latest vector clock이라 부른다. 이를 받은 Client는 Synced vector map을 빌드하여, 이전 Synced vector map을 교체한다. 그 과정은 다음 그림과 같다.


다만 다른 클라이언트에 대한 Vector Clock을 모르기 때문에, GC 효율이 떨어진다. GC 효율 문제는 다른 클라이언트의 편집을 받아야 해결된다.

### C. Version vector ( Centralized System )

#### Implementation
기존의 Synced vector map 방식은 전체적으로 메모리를 많이 사용하기에 다른 방향으로 디자인을 전환하였다. Client가 Synced vector map을 관리하는 것이 아닌, 서버가 이를 가지고 Minimum version vector라는 것을 Client에게 보내주어 Garbage collect를 하도록 만들었다. 이를 현재는 Version Vector라고 부른다.

<img src="https://hackmd.io/_uploads/r19BxOEnp.png" width="400" height="400">

이제부터 Client는 Version vector 하나만 관리한다. 어디까지 이벤트를 적용했는지를 나타낸다. Change에는 만들어진 당시의 Version vector가 복사되어 들어간다.


서버에서는 받은 Change를 ChangeInfo로 바꾸어 데이터베이스에 저장한다. 이때 Document Info의 Latest version Vector를 가져와 업데이트하고, 다시 Document Info와 ChangeInfo에 저장한다.


서버는 Client가 어디까지의 Change를 가져갔는지 tracking한다. 이를 ServerSeq라고 정의하고, SyncedSeq column에 클라이언트 별로 저장된다. 이를 이용해 Client가 마지막으로 적용한 Change를 찾을 수 있고, Change의 Latest version vector를 통해 Client의 상태를 알 수 있다.

> Change에 저장되는 Latest version vector는 첫 Change부터 그 Change까지 적용했을 때 만들어지는 version vector를 의미한다.


최소로 동기화된 Latest version vector를 Minimum version vector라고 부른다. 이는 Client들의 가장 낮은 Server Seq의 Change의 Latest version vector이다. 서버는 Minimum version vector를 Change Pack에 담아 Client가 Garbage collect에 이용하도록 한다.

<img src="https://hackmd.io/_uploads/BJTYx_42T.png" width="300" height="400">

SnapShot의 경우 version vector 또한 같이 저장한다. 이를 Latest version vector라는 이름으로 Change Pack에 담아 Client가 자신의 version vector를 replace하도록 만든다.

#### Concurrent vs Causal Event

이벤트 간의 상관 관계를 나타낸 그림이다. 이벤트간 관계를 비교할 때는 Change의 Version vector와 Client가 가지고 있는 Version vector를 이용한다.

Client B의 Server seq가 가장 낮기에 Minimum latest version vector는 B의 Server seq의 Latest version vector가 된다.

#### GC 문제 적용

잘 작동한다. 다만 이 그림은 client가 pull한 기준으로 Server Seq를 정의한 경우이다. 실제 구현에서는 push기준으로 Server Seq가 정의된다. 그림과 동일한 상태를 만들기 위해서는 Sync를 두 번씩 해주면 된다.

## 4. Lamport synced Version(vector) clock
지금까지 사용된 Version vector(Vector clock)은 formal한 알고리즘이 아니다. Lamport clock과 동기화된 vector clock이다. 아래는 TLA+/PlusCal을 이용해 작성된 Vector clock의 스펙이다. 현재 고안된 디자인은 다른 Client의 vector clock을 받고 Merge하는 과정에서 빨간색 부분의 식으로 교체된 버전이다.


알고리즘을 저렇게 수정한다면 Lamport와 Synced vector clock은 동기화 된 상태로 돌아가게 된다. 아래의 그림을 참고하면 Lamport와 Vector clock의 이벤트 업데이트가 동일함을 알 수 있다. (초록색 칠해진 부분)

#### 장점
이로 인한 장점은 vector clock과 lamport clock을 바로 비교할 수 있다는 장점이 있다.
만약 동기화되지 않았다면, causal관계를 확인하기 위해 해당 노드의 vector clock 정보가 필요하다. 이는 추가 메모리와 복잡한 로직을 필요로한다.
#### 단점
큰 단점은 증명이 되지 않은 방법이다. 선행 연구나 사례를 찾아봤지만 찾지 못하였다. 어디선가 사용되고 있을 수 있지만, 논문이나 formal한 검증이 되지 않은 방법이다.