원본 논문

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 () 가 수행한다.
    • Tx 처리 thread 는 우선 최신 (tail) 의 epoch object 에 자신을 추가한 뒤에, Index 에 접근하고, 접근을 마친 뒤에는 이 epoch 에서 자신을 제거하는 작업을 한다.
      • 자신을 추가하는 것은 저 그림에서 Counter 값을 조정하는 것으로 수행된다.
    • 그리고 thread 가 어떤 node 를 삭제하고자 한다면, thread 는 자신이 추가되어 있는 epoch object 에 이 node 를 주렁주렁 매달아 놓는다.
    • 마지막으로 는 counter 가 0이 된 epoch object 를 GC 하면서 여기에 달려있던 node 들도 다 GC 한다.
  • 이것에 대해 좀 더 개념적으로 설명해 보면 다음과 같다.

  • 이 그림에서 저 Epoch tableEpoch 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 () 이 있고, 이놈은 DBMS 의 어떤 backgound thread 가 올린다.
      • 위 사진에서는 가 올리는데, 계속 읽어보면 알겠지만 이 방식에서는 별도의 background GC thread 가 필요하지는 않다.
      • 따라서 굳이 일 필요는 없고, 그냥 아무나 한명만 이걸 올리고 있기만 하면 될듯.
    • 그리고 thread 가 생성되어 index 에 접근하면, 이 을 자신한테 복사해 와서 위 그림에서 Thread Local 라고 되어 있는 자료구조에 복사해 둔다 ().
    • Thread Local 에는 자신만의 GC list () 를 가지고 있고, 자신이 삭제하려고 하는 node 를 여기에 매달아 놓는데, 매다는 시점에 을 복사해와 해당 node 에 적어 놓는다 ().
      • 즉, consolidation 이 끝난 다음 mapping table 까지 바꿔서 더이상 이놈을 추가적으로 참조할 수 없는 상태로 만들고, 그 다음에 여기에 매달고 를 설정해놓는 것이다.
    • 마지막으로 thread 가 index 접근을 종료하는 시점에 또다시 에 복사해온 뒤, GC 를 수행한다.
      • GC 를 수행할 때는 모든 thread 들로부터 을 복사해와 가장 작은 을 찾는다.
      • 그리고 이것보다 작은 node 를 GC 하게 되는 것.
  • 위의 예시로 이 과정을 부연설명해보면,
    • 지금 살아있는 thread 는 하나뿐이고, 따라서 thread local 1 과 3 을 사용하던 thread 들은 이미 종료되었다.
    • Thread local 1 의 thread 가 종료된 시점에의 최소값은 thread local 3 번의 것인 100 이고, 따라서 의 node 는 GC 된다.
    • 근데 인 놈은 thread local 3 번 때문에 GC 되지 못하고 남아있게 되는 것이다.