(논문) DIVA: Making MVCC Systems HTAP-Friendly (4. Provisional Version Indexing)

원본 논문

• 이 글은 DIVA: Making MVCC Systems HTAP-Friendly (SIGMOD’22) 논문을 읽고 정리한 글입니다.
• 별도의 명시가 없으면, 본 논문에서 그림을 가져왔습니다.

4.1. A Homage to the UNIX Philosophy §

4.1.1. Honoring tradition. §

Summary for adopting UNIX Inode

• Section 3.3. 에서 설명한 내용을 좀 끌고와 보자면,
• Version 은 ephemeral 하기 때문에 이를 묶어주는 version index 가 차지하는 공간은 가변적으로 변하고,
• 이런 가변 공간을 handling 하기에 inode 만한 자료구조가 없기 때문에 이것을 활용하는 것이다.

• UNIX Inode 는 진자루 오래된 자료구조이고, 그의 효율성을 오랜 기간 동안 입증받아왔다.
• 이놈은 metadata 와 data 를 분리시킨다는 점에서 DIVA 의 “Separation” 철학과 많이 닮아 있다.
• 따라서 Provisional version index 에서도 이놈과 비슷하게,
  • Direct 및 single indirection 으로 version data 를 가리키게 해놓았고,
  • 많은 FS 에서 미리 공간을 확보해 놓고 사용하는 것처럼 여기에서도 shared index node pool 을 사용한다.

4.1.2. Paving new paths. §

• 기존의 inode 와의 차이점은 다음의 두 가지이다:
  1. Index array 의 사이즈가 가변 (Multi-granularity) 이다.
     • 우선 Index array 는 Inode 에서 direct, indirect 에 사용되는 array 에 대응되는 개념이라 생각하면 된다.
     • 가변 사이즈를 사용하는 것은 fixed-size array 는 internal fragmentation 이 발생할 수 있기 때문.
     • 이것은 OLTP query 의 경우에는 lifetime 이 작고 (short-lived), 따라서 작은 version window 를 필요로 하고
     • OLAP query 의 경우에는 lifetime 이 크기 (long-lived) 때문에 긴 version window 를 필요로 하기 때문이다.
  2. Version space 는 node reboot 시에 empty 된다는 것이다.
     • 당연히 reboot 시에는 해당 version 을 필요로 하는 transaction 이 다 죽었으니까 이 version 들은 전부 필요 없기 때문.
     • 즉, 이 부분에 대해서는 crash consistency 가 필요 없다는 것이다.

4.2. Architecture §

4.2.0 Prologue §

• 일단 Index file 을 pagination 해서 여러 page 들로 나눈다.
  • 이 page 를 Index page 혹은 Provisional-leaf page (P-leaf page) 라고 부른다.
  • 이름을 Provisional 라고 지은 것은 일시적으로는 이놈이 Primary index 를 넘어 version storage 를 커버하기 때문이다.
    • 이 말이 이해가 안된다면, version index 하나는 primary index 의 leaf 와 그놈에 대한 version 들 (version storage) 에 접근할 수 있게 해주는데
    • 결국에는 version 은 operation fail 시 사라지는 놈이기에 “일시적인” (Provisional) leaf page 라고 할 수 있는 것.
• 각 page 안에는 동일한 크기의 array (equal-size index array) 여러개를 생성해 Index array pool 을 마련한다.
  • 이 array pool 의 array 들 중 어떤 것이 사용되고 있는지는 bitmap 으로 관리된다.
• 이 array 의 size 는 index page 마다 다를 수 있다 (array capacity may differ).
  • 즉, array 의 size 는 한 index page 내에서는 동일하지만, index page 간에는 다를 수 있다는 것.
  • 위에서 말한 Multi-granularity 가 이 의미이다.
• 그리고 이 entry 하나는 Version ID, Lifetime info., Version locator 세 가지 정보가 담기게 된다.
  • 여기서 Version locator 는 다른놈을 가리키는 것 (즉, pointer) 이다.
  • 마치 inode 처럼 이놈도 어떤 Version 을 가리키거나 (direct) 혹은 다른 Index page 를 가리킬 수 있다 (indirect).

4.2.1. Multigranular index arrays. §

• Ext4 의 경우에는 최대 file size 가 16TiB 까지 늘어날 수 있지만, 보통 p-leaf page 에서는 그정도로 늘어날 일이 없다.
• 그래서 p-leaf page 에서는 $2^2$ ~ $2^8$ 사이의 size 를 가지는 array 들이 배치될 수 있다.
  • 물론 위에서 말한 것처럼 array size 는 한 p-leaf page 내에서는 통일되어 있고, 다른 p-leaf page 간에는 size 가 달라질 수도 있다는 의미이다.
• 따라서 (single indirect 의 경우) p-leaf page 하나에서는 최대 $(2^8{)}^2=2^{16}$ 개의 version 에 접근할 수 있다.
• 또한 indirect 의 경우 다른 p-leaf page 를 가리키므로 이 hierarchy 에 속한 p-leaf page 간에도 다른 array size 를 가질 수 있다.
• 다만 이론상으로는 이 indirection 에는 제한이 없지만, single indirection 을 넘어서는 경우는 없기 때문에 version 하나를 찾아가는데 최대 2번의 p-leaf page IO 면 충분하다.

4.2.2. Quasi-durable index space. §

• 위에서 말한 대로, version 은 failure 시 사라지기에 이 version index 도 permanent 할 필요가 없다.
  • 이 말은 즉, version index 는 logging 을 하거나 recovery 를 할 필요도 없고
  • Crash consistency 를 위한 metadata 를 가지고 있을 필요도 없으며
  • Update 순서를 조정하는 등의 짓거리를 하지 않아도 된다.
• 유일하게 필요한 것은 memory 가 작은 환경에서 잦은 memory swap 이 일어났을 때에도 disk 로 swap 된 p-leaf page 에 잘 연결될 수만 있으면 된다는 것이다.
• 또한 이에 따라 p-leaf page 의 free list 를 관리하기 위해서 concurrent stack 하나면 충분했다고 한다.
  • Concurrent stack 이 뭔지 자세히는 설명되어있지 않지만, 그냥 thread-safe stack 이라고 생각해도 된다.

4.3. Managing Version Index Space §

4.3.0. Prologue §

• 여기에서는 Provisional version index 를 관리하는 방법들 (가령 index concurrency) 에 대해 살펴보자.

4.3.1. Resource allocation §

4.3.2. Space compaction. §

4.3.3. Managing concurrency. §