(논문) 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 논문을 읽고 정리한 글이고, 추가적으로 서울대 정형수 교수님 빅데이터 및 지식 관리 시스템 2 강의 (Spring 2025) 강의 내용을 추가했습니다.
• 별도의 명시가 없으면, 본 논문과 강의에서 그림을 가져왔습니다.

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

• 정리 완료된 항목: 4.2.

4.2. Garbage Collection §

• 일단 Bw-Tree 에서는 epoch-based GC 를 하는데, 이놈의 가장 핵심적인 목표는 사용하지 않는 node 를 GC (reclaim, 즉 free) 하되, 어떤 thread 도 접근하지 않는 시점에 수행하는 것이다.
• 흔한 Epoch-based Reclamation (EBR) 을 사용하는 것인데, 다음의 세 과정으로 요약될 수 있다.
  1. 우선 지우려고 하는 node 를 mapping table 을 통해 더 이상 추가적으로 접근하지 못하게 만든다.
  2. 그리고, 이 node 에 현재 epoch 을 적어둔다.
  3. 나중에, 현재 작동하고 있는 다른 thread 들의 epoch 을 보고 이 epoch 들의 최소값이 node 에 적어둔 epoch 보다 크다면 더 이상 이놈을 볼 수 있는 방법이 없다는 것이므로 이놈을 지운다.
• 그럼 오리지널 버전에서는 이 EBR 을 어떻게 수행하고 있나 보자.

• 오리지널 버전에서의 작동 방식은 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 table 이 Epoch object 라고 생각하면 되고, 여기에 들어있는 저 CPU (즉, worker) 의 개수가 Epoch object 의 counter 라고 생각하면 된다.
• 그래서 지금은 CPU1 이 이 epoch 에 속하고 이놈이 지금 consolidation 을 하고 있는 것이다.

• 이후에 CPU2 가 등장했다고 해보자.

• CPU1 은 consolidation 을 완료하고, mapping 을 바꾼 후 기존의 놈을 Epoch table 에 넣어둔다.

• 마지막으로 이 Epoch table 에서 모든 CPU 가 빠지면 안에 있던놈이 GC 되게 된다.
• 하지만 이것은 좀 비효율적이다; Epoch object 에 추가하는 것을 atomic counter 를 올리는 것으로 수행하고 있기 때문에 thread 수가 많아지면 cache coherent protocol 때문에 bottleneck 이 된다.
• 따라서 OpenBwTree 에서는 반대로 한놈만 epoch 을 올리고 나머지 thread 들은 그걸 읽어가기만 하는 방법을 취한다.

• 이 방식을 Decentralized (Cooperative) 라고 한다. 이걸 좀 더 자세히 알아보자.
  • 우선 Global epoch ($e_{global}$) 이 있고, 이놈은 DBMS 의 어떤 backgound thread 가 올린다.
    • 위 사진에서는 $t_{gc}$ 가 올리는데, 계속 읽어보면 알겠지만 이 방식에서는 별도의 background GC thread 가 필요하지는 않다.
    • 따라서 굳이 $t_{gc}$ 일 필요는 없고, 그냥 아무나 한명만 이걸 올리고 있기만 하면 될듯.
  • 그리고 thread 가 생성되어 index 에 접근하면, 이 $e_{global}$ 을 자신한테 복사해 와서 위 그림에서 Thread Local 라고 되어 있는 자료구조에 복사해 둔다 ($e_{local}$).
  • 이 Thread Local 에는 자신만의 GC list ($l_{local}$) 를 가지고 있고, 자신이 삭제하려고 하는 node 를 여기에 매달아 놓는데, 매다는 시점에 $e_{global}$ 을 복사해와 해당 node 에 적어 놓는다 ($e_{delete}$).
    • 즉, consolidation 이 끝난 다음 mapping table 까지 바꿔서 더이상 이놈을 추가적으로 참조할 수 없는 상태로 만들고, 그 다음에 여기에 매달고 $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 들은 이미 종료되었다.
  • Thread local 1 의 thread 가 종료된 시점에의 $e_{local}$ 최소값은 thread local 3 번의 것인 100 이고, 따라서 $e_{delete}=98$ 과 $e_{delete}=99$ 의 node 는 GC 된다.
  • 근데 $e_{delete}=100$ 인 놈은 thread local 3 번 때문에 GC 되지 못하고 남아있게 되는 것이다.