(논문) Building a Bw-Tree Takes More Than Just Buzz Words (4. Component Optimization)

원본 논문

• 이 글은 Building a Bw-Tree Takes More Than Just Buzz Words, SIGMOD’18 논문을 읽고 정리한 글입니다.
• 별도의 명시가 없으면, 본 논문에서 그림을 가져왔습니다.

#draft 본 문서는 부분적으로 완료된 상태입니다.

• 정리 완료된 항목: 4.2.

4.2. Garbage Collection §

• 일단 Bw-Tree 에서는 epoch-based GC 를 하는데, 이놈의 가장 핵심적인 목표는 사용하지 않는 node 를 GC (reclaim, 즉 free) 하되, 어떤 thread 도 접근하지 않는 시점에 수행하는 것이다.

• 오리지널 버전에서의 작동 방식은 Centralized 방식이라고 부르는데 이것에 대해 먼저 간단하게 설명해 보면
  • 일정한 주기 (가령 40ms) 를 갖는 매 epoch 마다 Epoch object 가 생성되어 linked list 형태 (Global epoch objects) 로 주렁주렁 달리게 된다.
    • 새로운 Epoch object 를 추가하는 것은 (비록 이름이랑 잘 안어울리기긴 하지만) GC tread ($t_{gc}$) 가 수행한다.
  • Tx 처리 thread 는 우선 최신 (tail) 의 epoch object 에 자신을 추가한 뒤에, Index 에 접근하고, 접근을 마친 뒤에는 이 epoch 에서 자신을 제거하는 작업을 한다.
    • 자신을 추가하는 것은 저 그림에서 Counter 값을 조정하는 것으로 수행된다.
  • 그리고 thread 가 어떤 node 를 삭제하고자 한다면, thread 는 자신이 추가되어 있는 epoch object 에 이 node 를 주렁주렁 매달아 놓는다.
  • 마지막으로 $t_{gc}$ 는 counter 가 0이 된 epoch object 를 GC 하면서 여기에 달려있던 node 들도 다 GC 한다.
• 하지만 이것은 좀 비효율적이다; Epoch object 에 추가하는 것을 atomic counter 를 올리는 것으로 수행하고 있기 때문에 thread 수가 많아지면 bottleneck 이 된다고 한다.
  • 구체적으로는 cache coherent traffic 문제때문에 그렇다고 한다.
  • 이게 뭔지 (아직은) 모르겠지만 많은 thread 가 한번에 atomic counter 를 변경하기 때문에 마치 lock 이 걸리는 듯한 효과가 난다고 이해해 두자.
• 따라서 OpenBwTree 에서는 반대로 한놈만 epoch 을 올리고 나머지 thread 들은 그걸 읽어가기만 하는 방법을 취한다.

• 이 방식을 Decentralized (Cooperative) 라고 한다. 이걸 좀 더 자세히 알아보자.
  • 우선 Global epoch ($e_{global}$) 이 있고, 이놈은 DBMS 의 어떤 backgound thread 가 올린다.
    • 위 사진에서는 $t_{gc}$ 가 올리는데, 계속 읽어보면 알겠지만 이 방식에서는 별도의 background GC thread 가 필요하지는 않다.
    • 따라서 굳이 $t_{gc}$ 일 필요는 없고, 그냥 아무나 한명만 이걸 올리고 있기만 하면 될듯.
  • 그리고 thread 가 생성되어 index 에 접근하면, 이 $e_{global}$ 을 자신한테 복사해 온다 ($e_{local}$).
    • 그림에서 Thread Local 이 index 에 접근한 thread 라고 생각하면 된다.
  • 각 thread 는 자신만의 GC list ($l_{local}$) 를 가지고 있고, 자신이 삭제하려고 하는 node 를 여기에 매달아 놓는데, 매다는 시점에 $e_{global}$ 을 복사해와 해당 node 에 적어 놓는다 ($e_{delete}$).
  • 마지막으로 thread 가 index 접근을 종료하는 시점에 또다시 $e_{global}$ 을 $e_{local}$ 에 복사해온 뒤, GC 를 수행한다.
    • GC 를 수행할 때는 모든 thread 들로부터 $e_{local}$ 을 복사해와 가장 작은 $e_{local}$ 을 찾는다.
    • 그리고 이것보다 작은 node 를 GC 하게 되는 것.
• 위의 예시로 이 과정을 부연설명해보면,
  • 지금 살아있는 thread 는 $t_1$ 하나뿐이고, 따라서 thread local 1 과 3 은 이미 종료되었다.
  • Thread local 1 이 종료된 시점에의 $e_{local}$ 최소값은 thread local 3 번의 것인 100 이고, 따라서 $e_{delete}=98$ 과 $e_{delete}=99$ 의 node 는 GC 된다.
  • 근데 $e_{delete}=100$ 인 놈은 thread local 3 번 때문에 GC 되지 못하고 남아있게 되는 것이다.