원본 논문
- 이 글은 DIVA: Making MVCC Systems HTAP-Friendly (SIGMOD’22) 논문을 읽고 정리한 글입니다.
- 별도의 명시가 없으면, 본 논문에서 그림을 가져왔습니다.
#draft 본 글은 abstract 상태입니다.
- 지금은 핵심 아이디어만 정리되어 있는데, 각 section 별로 정리된 full review 작성해야 됨.
Epoch-Based Interval Tree
- 일단 EBI Tree 의 전체적인 구조는 위와 같다.
- 고정된 interval 인 epoch 들이 tree leaf 에 쭉 깔리고,
- Inner node 는 child node 두개의 interval range 를 커버하도록 되어 있다.
- 즉, leaf node (epoch) 바로 위의 parent node 는 child epoch 두개의 interval 을 합친 interval 을 가지게 된다.
- 이때, 어떤 txn 이 시작되면 자신이 속한 epoch 의 ref count 를 올리고 (bind), 이놈이 commit 되거나 abort 되면 이 epoch 의 ref count 를 내린다 (unbind).
- 그리고 각 epoch 과 parent node 에 대해서는 별도의 segment file 이 생성되는데, 만약 어떤 version 이 생성되면 이 version 의 lifetime 을 아우를 수 있는 가장 작은 interval 에 해당하는 epoch 혹은 node 에 대한 segment file 에 저장된다.
- 여기서 lifetime 은 어떻게 구할 수 있냐 라고 생각할 수 있는데, 기본적로 DIVA 는 SIRO Versioning 을 사용하고 있고 여기에서 튕겨져 나온 old version 만이 version storage 로 들어와 이 EBI tree 를 통해 관리되기 때문에 당연히 저 SIRO Versioning 논문에 나온 방법과 동일하게 lifetime 을 구할 수 있다.
- 또한, GC 는 다음과 같이 수행된다.
- Epoch 에 대해서는, 이놈에 대한 ref count 가 0 이 되면 (그리고 아마 이놈이 가장 최신의 epoch 이 아니라면) 이 epoch 에 속하는 txn 이 하나도 없고, 더 이상 이 epoch 에 매달릴 수 있는 txn 도 없다는 의미이기 때문에 이 epoch 및 연관된 segment file 을 지운다.
- 그리고 parent node 에 대해서는, child node 가 둘 다 지워지면 이 node 및 연관된 segment file 이 지워진다.
- 이러한 방식으로 개별 tuple 에 대한 lifetime 을 매번 추적해서 GC 하지 않아도 dead zone 에 낀 dead version 들을 깔끔하게 지울 수 있다.
- 그리고 만약 어떤 version 이 생성되었는데 이놈이 들어갈 epoch 이나 node 가 없다면, 이 말은 이미 이 version 을 볼 수 있는 txn 이 없다는 의미가 된다. 이에 따라 vDriver 의 1st pruning 처럼, 이놈은 저장할 필요도 없이 버려버릴 수 있다.
- 이 Tree 는 위 그림처럼 epoch 이 추가되면서 오른쪽으로 grow 하고
- 이전의 epoch 들은 차례차례 종료되며 왼쪽부터 collapse 하는 형태로 변한다.
- 따라서, 한쪽으로는 grow 하고 반대편에서는 collapse 하는 형태이기 때문에 별도의 rebalancing 은 필요하지 않다.
- 또한 LLT 가 있으면 위 그림처럼 가운데는 모두 collapse 하고 양 끝만 남아있는 기형적인 형태도 가능하다.