<style>
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Gowun+Dodum&display=swap" rel="stylesheet">

body {
font-family:'Gowun Dodum', sans-serif;
}
</style>

### 0. 문제가 성립할 수 있는 가?

- 벡터를 이용한다 -> 실행된 op 버전을 op의 actor로 나누어 관리하겠다.
- **change를 보낼 땐 자신의 최신 벡터를 보낸다**.
- peer간 change를 주고 받으며 상대의 상태를 벡터를 통해 알 수 있다.
- GC 룰
- **다른 모든 노드들이 해당 이벤트를 받은 경우에만 GC를 진행한다**.
- 이는 다른 노드들의 change의 vector clock을 통해 확인
- **GC는 현존하는 peer들의 모든 벡터를 가지고 있는 상태에서 진행되어야 한다**.
- 현존하는 peer의 기준은 무엇인가?
- attach되어 있고, activated된 client
- attach 함수는 presense를 put하기에 다른 peer들은 attach된 client의 벡터를 가짐을 보장 ( snap shot 예외 )
- attach 룰
- **attach시 presense change에 자신의 초기 벡터를 서버에 푸시**
- detach
- **자신이 나간다는 표시를 change에 남겨야한다**.
- **이후 자신의 벡터를 제외한 나머지 벡터 제거하면 안된다.** ( GC가 돌아버려 다시 attach시 문제)

### 1. [이슈](https://github.com/yorkie-team/yorkie/issues/723) 구체화



### 2. 실제 구현에서의 vector clock

- update 및 sync 과정


- document 생성과 attach


- detach
- 어떻게 다른 클라이언트의 detach 정보를 알려줄 것인지?


- 이슈의 테스트 코드의 도식화

// gc_test.go
t.Run("should not garbage collection", func(t *testing.T) {
    ctx := context.Background()
    d1 := document.New(helper.TestDocKey(t))
    err := c1.Attach(ctx, d1)
    assert.NoError(t, err)

    d2 := document.New(helper.TestDocKey(t))
    err = c2.Attach(ctx, d2)
    assert.NoError(t, err)

    err = d1.Update(func(root *json.Object, p *presence.Presence) error {
        root.SetNewText("text").Edit(0, 0, "a").Edit(1, 1, "b").Edit(2, 2, "c")
        return nil
    }, "sets text")
    assert.NoError(t, err)
    err = c1.Sync(ctx)
    assert.NoError(t, err)
    err = c2.Sync(ctx)
    assert.NoError(t, err)

    err = d2.Update(func(root *json.Object, p *presence.Presence) error {
        root.GetText("text").Edit(2, 2, "c")
        return nil
    }, "insert c")
    assert.NoError(t, err)

    err = d1.Update(func(root *json.Object, p *presence.Presence) error {
        root.GetText("text").Edit(1, 3, "")
        return nil
    }, "delete bd")
    assert.NoError(t, err)
    assert.Equal(t, 2, d1.GarbageLen())
    assert.Equal(t, 0, d2.GarbageLen())

    err = c2.Sync(ctx)
    assert.NoError(t, err)
    err = c2.Sync(ctx)
    assert.NoError(t, err)
    err = c1.Sync(ctx)
    assert.NoError(t, err)
    err = c1.Sync(ctx)
    assert.NoError(t, err)
    assert.Equal(t, 2, d1.GarbageLen())
    assert.Equal(t, 0, d2.GarbageLen())

    err = d2.Update(func(root *json.Object, p *presence.Presence) error {
        root.GetText("text").Edit(2, 2, "1")
        return nil
    }, "insert 1")
    assert.NoError(t, err)

    err = c2.Sync(ctx) // GC purge 4@A node
    assert.NoError(t, err)
    err = c2.Sync(ctx)
    assert.NoError(t, err)
    assert.Equal(t, 2, d1.GarbageLen())
    assert.Equal(t, 0, d2.GarbageLen())

    err = c1.Sync(ctx)
    assert.NoError(t, err)
    assert.Equal(t, 2, d1.GarbageLen())
    assert.Equal(t, 0, d2.GarbageLen())
})


### 3. Snap shot 관련 서버의 Latest synced vector 컨셉

- 주황색 <- 서버의 누적된 벡터 (synced된 vector들 중 가장 최근의 벡터이다.)
- 오른쪽 아래 client c가 attach시, change와 snap shot을 교환하고, 서버의 Latest synced vector를 가져와 vector clock을 업데이트.

#### 3-1. 실제 구현


- 서버는 snap shot으로부터 document를 빌드할 때 synced vector map 또한 같이 만든다.
- 이후 pull 시 snapshot을 받는 상황이라면, snap shot으로 부터 만들어진 synced vector map을 pack에 담아 보내준다.

> snapshot으로부터 pull할 때
- pullSnapshot( )
- BuildDocumentForServerSeq( )
- NewInternalDocumentFromSnapshot( ) -> snapshot을 이용해 doc 만든다.
- 기존 snapshot의 synced vector map을 가져온다.
- snapshot과 서버 sequence 사이 change를 apply하며 synced vector map을 업데이트한다.
- request의 change를 apply
- request를 한 client의 vector clock이 document에 만들어진다.
- initActorID와 request Actor ID가 synced vector map에 공존하는 상태
- doc.syncedVectorMap을 반환

> storeSnapshot / snapshot저장
- 기존 가까운 snapshot을 찾는다.
- NewInternalDocumentFromSnapshot( ) -> snapshot을 이용해 doc 만든다.
- 기존 스냅샷이 만약 없다면 synced vector map은 InitialSyncedVectorMap로 세팅
- 현재 snapshot ~ serverSeq 까지 change를 가져온다. -> doc 에 apply
- CreateSnapshotInfo 를 통해 저장

> snapShot은 initialID를 이용해 synced vector map을 만들어 나간다.

### 4. 마이그레이션
- 문제다.

### 5. GC, Edit 기준

A. garbage collect

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

B. Edit (deleteNodes)

1. Edit 연산시 actor의 vectorClock을 Edit operation에 포함
- vectorClock : Edit 연산의 lamport를 업데이트한 상태
2. Execute시 다음의 기준을 따라 노드를 keep

latestWhenEdit < node.CreatedAt

> latestWhenEdit (time ticket)
- Lamport : vector[node.CreatedAt.ActorID]
- Delimiter : Max delimiter
- ActorID : editedAt.ActorID // 연산을 발생시킨 Actor


#### 6. On going

- [x] text edit에서 삭제되는 부분의 latestCreatedAtMapByActor를 vector clock 이용하게 수정
- [ ] tree edit, style edit도 작업
- [x] gc_test 코드 수정 -> 기존 방식과 달리 gc가 조금 빨리 발생
- [x] snap shot -> document build 할 때 최신의 벡터로 초기화하도록 수정
- [ ] 기존 min synced ticket 부분 서버에서 걷어내기
- [ ] detach 케이스 고려

#### 7. synced vector map을 어떻게 저장할 것인가?

| |200 | 300회 |
| -------- | -------- | -------- |
| json.marshal -> string | 136.229s | 396.534s |
| json.marshal + detach | | 360.606s |
| protobuf | 153.032s | 455.499s |

- json.marshal -> string으로 저장
- 200회
- 300회

- protobuf -> []byte로 저장

- 200회
- 300회

- json.marshal string + detach
- 300회