(논문) Building a Bw-Tree Takes More Than Just Buzz Words (2. Bw-Tree Essentials)

원본 논문

• 이 글은 Building a Bw-Tree Takes More Than Just Buzz Words, SIGMOD’18 논문을 읽고 정리한 글이고, 추가적으로 서울대 정형수 교수님 빅데이터 및 지식 관리 시스템 2 강의 (Spring 2025) 강의 내용을 추가했습니다.
• 별도의 명시가 없으면, 본 논문과 강의에서 그림을 가져왔습니다.

2.0. Prologue §

Arbitrary section

• 그냥 2.1. 직전의 내용이고, 논문에는 별도 section 으로 numbering 되어 있지는 않습니당

• Bw-Tree 는 DBMS 의 Index 로서 thread pool 과 같이 생성되고, 따라서 여러개의 thread 들이 동시에 접근하게 된다.
• 또한 (original Bw-Tree 는) GC 를 위한 별도의 background thread 가 돌아간다.
• B+ Tree 와의 주된 차이점은 node 를 직접적으로 변경하는 것이 금지되어 있다는 것이다.
  • 이것은 (1) cache line invalidation 을 막기 위함 과 (2) lock 을 사용하지 않기 위함 이다.
• 이것을 달성하는 주된 아이디어 두개는 다음과 같다:
  • Delta chain: Node 를 변경하는 것은 직접적으로 변경하는 것이 아닌 per-node delta node chain 을 이용한다.
  • Indirection layer:
    • Parent node 에서 가리키는 child node 의 주소가 delta node 가 생성됨에 따라 변경될 수 있다 (이해가 안된다면 일단 넘어가자).
    • 이 parent node 에 적힌 child node 의 주소를 변경하는 것 또한 node 자체를 변경하는 것이기에, logical ID 를 이용한 indirection 으로 이 문제를 해결한다.
    • 즉, child 의 physical addr 가 바뀌어도 이놈에 대한 logical ID 매핑만 변경해 주면 parent node 에서는 동일한 logical ID 로 해당 node 를 (논리적으로) 가리키게 할 수 있다.
• 이렇게 하는 이유는, 기존의 B+ Tree 에서는 SMO 를 할 때 여러개의 pointer 를 고쳐야 하고 SMO 의 영향이 어디까지 갈지 (가령 어느 parent 까지 split 되어야 하는지 등) 을 알기 힘들기 때문에 tree traversal 을 할때 latch 를 잡으며 내려와야 했었다.
  • 즉, 이런 latch 가 필요했던 이유는 여러개의 pointer 를 atomic 하게 고쳐야 하기 때문이었기에, delta chain 과 indirection 을 넣어서 indirection mapping table 에 한번의 atomic pointer operation 으로 mapping 을 바꿔주기만 하면 모든 연결관계가 바뀌도록 한 것이다.

• 위의 그림이 전체적인 architecture 를 그린 것인데,
• (Physical 하게) “Node” 는 총 세가지 종류가 있다.
  • Leaf node: 실제 data 가 담기는 node (B+ Tree 와 동일)
  • Inner node: Guidepost node (B+ Tree 와 동일, intermediate node 임)
  • Delta node: Leaf, Inner node 에 대한 변경사항 (delta) 를 담는 node
  • Bw-Tree 를 초기화할 때는, Leaf node 하나와 Inner node 하나가 생성된다고 한다.
• 그리고 logical 하게 묶어보면, 이 “node” 들은 다음과 같이 분류할 수 있다.
  • Base node: Leaf node 와 Inner node
    • 둘 다 “원본” 이라는 공통점으로 묶었다고 생각하면 된다.
  • Logical node (Virtual node): Base node 와 Delta node
    • Delta node 들은 이 Base node 에 대한 변경사항이므로
• 이때 모든 physical node 는 logical ID 를 갖고 있고, 이것과 physical addr 와의 매핑은 Mapping Table 에서 관리한다.

• Parent node 는 key 에 대한 route 를 physical addr 가 아닌 logical ID 로 저장한다.
  • 따라서 parent-child 간에는 logical link 가 형성되고, node-maptable 간에는 physical link 가 형성된다.
  • 다른 관점에서는 위처럼 됨: Virtual node 끼리는 logical link 로, virtual node 내에서는 physical link 로 연결된다.
• 이 mapping table entry 를 변경하는 것은 Compare and Swap (CaS) instruction 으로 수행한다.
  • 이것은 atomic instruction 으로, logical-physical mapping 이 atomic 하게 변경되므로 node-node link 도 atomic 하게 변경된다.
  • 또한 이 instruction 를 사용하면 mapping table entry 를 변경하는 것도 atomic 하게 처리할 수 있게 해준다고 한다.

2.1. Base Nodes and Delta Chains §

• 변경사항은 delta node 에 담겨서 delta chain 의 head 에 들어간다.
  • 즉, 최신의 delta 가 head 에 들어가고 오래된 delta 는 tail 쪽에 위치하는 “시간순” 배치를 가진다. (Chronological)
• 이 delta chain 의 tail delta node 을 (parent) base node 가 logical link 로 가리키고 있고, head delta node 는 base node 를 physical link 로 가리키고 있으며, 중간의 delta node 는 그 이전의 delta node 를 physical link 로 가리키고 있다.
  • 즉, 이렇게 되면 virtual node 안에서는 모두 physical 하게 연결되고, virtual node 밖에서는 모두 virtual 하게 연결되는 것이다.
• Base node 와 delta node 에는 모두 metadata (attribute) 가 저장되는데, 이놈은 해당 시점에의 Virtual node 의 “상태” 를 기록하는 역할을 한다.
  • 여기에는 다음의 여섯가지 값이 담긴다:
  1. Low-key: 해당 Virtual node 에의 가장 작은 key
     • 이놈은 기본적으로는 predecessor (이전의 delta 혹은 base node) 의 것을 그대로 상속받는다.
     • 하지만 split 이 발생하면, split 되어 쪼개진 양쪽 node 중 오른쪽의 Low-key 는 split key 로 설정된다.
  2. High-key: 해당 Virtual node 의 right sibling 에 대한 Low-key
     • 즉, ”Virtual node 에의 가장 큰 key” 의 다음 key 이다.
     • Split 이 발생하면 split 되어 쪼개진 양쪽 node 중 왼쪽의 High-key 가 split key 로 설정된다.
     • Merge 시에는 오른쪽의 High-key 가 merge 이후의 High-key 가 된다.
  3. Right-sibling: 말 그대로 해당 Virtual node 의 right sibling virtual node 의 logical ID 가 담긴다.
  4. Size: Virtual node 에 담긴 key 의 갯수
  5. Depth: 해당 node 부터 base node 까지의 거리. 따라서 base node 는 이 값이 0이고, delta node 는 1씩 증가하는 값을 가진다.
  6. Offset: 변경된 값의 위치
     • 라고 말하면 뭔소린가 하는데, 몇번째 key 가 변경되었는지에 대한 값이다.
     • 즉, 위의 예시에서 $K_1$ 에 대한 $\Delta delete$ record 에 대해서는, 첫번째 key 이므로 offset 은 0이 되는 것.
  • 이 값은 thread 가 record 를 추가할 때 계산되어 저장되고, tree 를 traverse 할 때 사용된다.
• 따라서, delta node append 를 하는 것은 CAS 로 수행될 수 있다. 좀 더 자세히 보면 아래와 같다.

• 우선 txn 는 새로운 delta node 를 다음과 같이 만든다.

• 그리고 이놈의 next pointer 에다가는 현재 mapping table 을 통해 얻어낸 physical address 를 넣어 delta chain 을 연결한다.

• 그리고, mapping table 에다가는 기존에 알아놓은 physical address 가 지금도 유효한지 (즉, 아직도 그 값인지) 검사하고, 유효하다면 새로 만든 delta node 의 address 로 세팅하도록 한다.
• 이 과정에서 CAS 가 사용되는 것이다. 유효성 검사와 새로운 address setting 이 atomic 하게 이루어져야 하기 때문.
• 따라서 만약에 두놈이 동시에 들어오게 되면 다음과 같이 수행된다.

• 저기서 DELETE K8 이 순간적으로 먼저 CAS 를 했다고 해보자. 그럼 mapping table 에다가는 DELETE K8 의 address 가 들어가게 될 것이고, 따라서 조금 더 늦게 CAS 를 한 INSERT K6 은 mapping table 의 값이 달라졌으므로 CAS 에 실패한다.

• 따라서 이때에는 retry 를 한다. 결과적으로 위 그림과 같은 (저기서 INSERT K5 는 오타고 INSERT K6 이 맞다) 형태가 된다.

2.2. Mapping Table §

• Bw-Tree 는 B-link Tree 처럼 sibling 끼리 link 되어 있고, 따라서 하나의 (base) node 는 두개의 inbound pointer 가 연결된다: 하나는 parent 로 부터 연결된 것, 그리고 나머지 하나는 왼쪽 sibling 으로부터 연결된 것.
• 기존의 B-link Tree 에서는 이들을 atomic 하게 변경하려면 HW 의 도움을 받거나 복잡한 SW 구현이 필요했는데, Bw-Tree 에서는 mapping table 을 구성해 이들을 indirection 하는 방식으로 간단하게 atomic 하게 처리할 수 있다.
• 이 atomic instruction 이 Compare-and-Swap (CaS) 이고, 이놈은 거의 모든 architecture 에서 지원한다.
• 다만 CaS 는 실패할 수가 있는데 이때 thread 는 작업을 전부 취소하고 다시 시작한다.
  • 즉, root 부터 시작해서 다시 traverse 하는 것.
• 이것은 어찌 보면 overhead 이고, root 가 아닌 다른 곳에서부터 시작하도록 optimize 가 가능하지만 굳이 그럴 필요는 없다고 한다.
  • 어차피 tree node 들이 L1 cache 에 다 올라와 있을 것이기 때문.
• 이 아이디어는 F2FS 에서와 비슷한 접근이다.
  • F2FS 에서도 File 을 update 하는 것이 insert 로 바뀌기 때문에 LBA 가 변경되는 것이 Inode, Directory 에도 전파되는 문제를 indirection layer 로 해결하는데,
  • 여기에서도 마찬가지로 이 delta chain append 가 parent node 의 변경으로 propagation 되는 것을 이 mapping table 이 막아주고 있는 것.

2.3. Consolidation and Garbage Collection §

• Delta chain 은 점점 늘어나고, 이것은 당연히 문제가 된다.
  • 메모리 사용량도 커지거니와
  • 방문하는 node 의 수가 커지기 때문에 traverse time 도 늘어난다.
• 따라서 이 delta chain 을 다시 base 로 합치는 Consolidation 작업을 worker thread 가 해주게 된다.
  • 이 작업을 하는 조건은 오리지널 Hekaton 버전 Bw-Tree 에서는 delta chain length 가 8이 될때 해주는 것이 가장 좋다고 적어놓았는데,
  • OpenBwTree 에서는 이것을 inner node 와 leaf node 에 따라 다르게 가져가는 것이 좋다고 한다.
• Consolidation 을 하는 것은 간단하다.
  • 그냥 base node 를 복사해다가 delta node 를 쭉 적용한 뒤에, 이 메모리 공간을 mapping table 에 업데이트만 해주면 된다.
  • 그리고 이렇게 해서 쓸모없어진 node 들은 GC (reclaim) 되는데, 당연히 이것은 이 node 에 아무도 접근하지 않을 때 수행해야 한다.
  • 이 GC 시점을 잡는 것은 Section 4.2. 에 설명하는 epoch-based GC 방식을 사용한다.
• 즉, 그림으로 보면 아래와 같다.

• 위와 같은 형태로 chain 이 연결되어 있다고 했을 때,

• 이놈을 전부 consolidation 해서 새로운 base node 로 만든 다음에

• 동일하게 CAS 로 mapping table 을 바꿔주며 기존의 것들은 GC 가 되게 한다.

2.4. Structural Modification §

• B+ Tree 에서와 마찬가지로, 이놈도 overflow 되어 split 되거나 underflow 되어 merge 하는 작업이 수행된다.
• 이런 구조 변경 작업을 Structural Modification Operation (SMO) 라고 하는데, Bw-Tree 에서의 SMO 를 간단히 설명해 보면 다음과 같다.
• SMO 작업은 (1) 다른 thread 에게 SMO 를 진행한다는 것을 알리기 위한 delta 를 추가하는 Logical phase 와 (2) 실제로 SMO 를 적용하는 Physical phase 두 단계로 나뉜다.
  • Logical phase 에서는:
    • 일단 high-key 나 right-sibling 등의 node attribute 를 변경하여 “논리적” 으로 두 node 를 합치거나 쪼갠다.
    • 다만 이 node attribute 를 변경하는 것도 delta node 를 추가하는 것으로 수행되는데, 이때의 delta node 는 $\Delta split$ 이나 $\Delta merge$ type 이다 ¹.
    • 이렇게 node attribute 를 먼저 변경함으로써 SMO 가 진행되는 와중에도 일관된 virtual node 의 상태를 바라볼 수 있게 해준다.
      • 즉, SMO 의 결과 상태로 node attribute 를 선-변경하는 것.
  • Physical phase 에서는:
    • 사실상 이것은 delta record 들을 consolidation 해주는 과정과 동일하다: 실제로 작업을 한 다음에 mapping table 을 바꿔준다.
    • 이것은 logical phase 를 수행한 thread 가 해도 되고 딴놈이 해도 된다고 한다.
• 이 작업은 delta chain 과 indirection layer 를 활용하기에 마찬가지로 lock-free 하지만, CaS fail 에서 자유로울 수는 없다.
  • 만약 CaS fail 상황에서 여러 thread 가 협력하여 SMO 를 진행하는 Help-along protocol 도 있다고 한다.
• 이 SMO 를 좀 더 자세히 알아보자. 우선 $\Delta split$ (Split Delta Record) 는 원본 node 에 delta node 로 붙어, 이 원본 node 가 현재 split 되어 지금은 두개로 쪼개져있다는 것을 나타낸다.
• 또한 $\Delta separator$ (Separator Delta Record) 도 있는데, 이놈은 parent node 에 deleta node 로 붙어 child node 가 split 되었을 때, child fanout 이 하나 더 있다고 알려주는 역할을 한다.
• 아래의 예시를 보자.

• 위 그림에서 103 을 split 해서 K5 와 K6 을 별도로 뺀다고 해보자.

• 그럼 이제 105 를 먼저 만든 뒤에 mapping table 에 105 를 넣어준다.
  • 하지만 이렇게 해도 저 105 를 logical pointer 로 연결짓는 놈이 없기 때문에 아직까지는 이놈은 visible 하지 않다.

• 그리고, $\Delta split$ 을 생성한 뒤에, 이놈에 대해 CAS 를 하면 아래와 같이 바뀐다.

• 그럼 이때부터 parent (101) 은 먼저 $\Delta split$ 을 만나게 되고, split 된 105 에 접근할 수 있게 된다.
• 근데 매번 이렇게 접근할 수는 없다. 105 로 가고 있는 유일한 길이 $\Delta split$ 이기 때문에, 이놈이 consolidation 되면 101 에서 105 로 바로 갈 수 있는 길이 없기 때문.
• 그래서, 101에 새로운 child 가 추가되었다고 알려주는 것이 $\Delta separator$ 이다. 이건 아래 그림처럼 된다.

• 우선 $\Delta separator$ 를 생성하여 101 의 delta chain 에 연결해주고, logical pointer 로는 105 를 가리키도록 한다.

• 이후 101 의 mapping 을 $\Delta separator$ 로 바꿔주면, 이때부터는 101 에 접근한 애들은 저 $\Delta separator$ 를 먼저 보고 101 에 child node 가 하나 더 있음을 인지하게 된다.
• 따라서, 이때부터는 저 $\Delta split$ 이 consolidation 되어도 아무런 문제가 없는 것.

Footnotes §

1. 논문에서는 INSERT 나 REMOVE type 도 말하는데, 이건 어떻게 사용되는건지는 잘 모르겠음 ↩