PACTree: A High Performance Persistent Range Index Using PAC Guidelines

개요

Pmem을 잘사용하기 위해선, 다음과 같은 조건을 Inforcement 하여야 한다.

FH1: Read/Write 속도가 DRAM과 달리 다르다. 즉 Write이 Read보다 느리다.
FH2: Write이 Latency가 크고 Bandwidth가 작기 떄문에 bottleneck이 된다.
FH3: Sequential NVM access는 이러한 단점을 커버한다. (Sequential read가 random read보다 빠르다.)
FH4: Persistence를 지키는 것은 cache line invalidation, flushing을 일으키기 때문에 생각보다 느리다.
FH5: Cache coherence protocol은 NUMA머신의 scalability를 방해한다. 이는 Directory coherence protocol에서 기원하는데, directory write이 느린 NVM속도때문에 더욱 과장되어 보이기 때문이다.

GS1: Crash consistency operations들을 자주 사용하는 것은 큰 write overhead를 부르기 때문에 속도 저하의 주범이 된다. 따라서 Memory allocation, 혹은 write과 같은 NVM state를 바꾸는 작업들은 NVM lag + Crash consistency를 위한 속도 저하를 극복해야 한다.
GS2: Persistent memory allocation은 NUMA장치를 신경써서 작성해야 한다. 이는 NUMA장치에서 write lag가 더욱 크게 보이기 때문이다.

GA1: Lookup operation은 대다수의 IO operation을 차지하는 경향이 있는데, 이 Lookup operation을 효율적으로 작성하여 NVM의 read latency가 보이지 않도록 하여야 한다.
GA2: Lookup 그리고 Scan operation은 Read를 하게 되는데, 이는 Directory cache protocol의 사용을 만들어서 NVM에 특정 write log을 시키기도 한다. 이러한 write lag에서 오는 속도저하도 무시할 수 없다.
GA3: Write operation을 위하여 자주 NVM allocation하게 되면 Atomic allocate를 위한 logging에 대한 lag가 심해짐으로 latency가 커질 수 있다. 즉 최대한 NVM memory allocation을 하는 횟수를 줄여야 한다.
GA4: Persistent write operation의 수를 줄여야 한다. 즉 logging위하여 저장되어야 하는 필수적인 요소의 수를 줄여야 한다.
GA5: Scan operation과 같은 경우에는 Sequential하게 실행되어야 한다.

GC1: Concurrent access를 통해서 NVM에 대한 다중접근이 가능하도록 하여야 한다.
GC2: NVM에 저당되는 자료구조에서 Strutural modification operation즉 merge나 split에 드는 시간을 줄여야 한다. 이는 이러한 연산이 필연적으로 Blocking이라는 점에서 기인하는데 이는 NVM에서 DRAM보다 더욱 두드러진 성능저하의 요소로 보이게 된다.
GC3: NVM은 저장하는 단위가 큰 만큼, persistent memory에서 data 사이즈로 인한 성능저하가 있으면 안된다. 예를 들어서 cache size보다 큰 데이터의 경우에는 cache miss를 지속적으로 부를 수 있는데, NVM에서는 이러한 성능저하가 더욱 큼으로 신경써서 작업해야 한다.

요약 하자면, write/read 가 느리기 때문에 효율적으로 접근해야 하고, consistency를 유지하기 위한 비용이 비싸며, 이러한 performance down은 특히 NUMA머신에서 심하게 일어난다, 로 정리할 수 있다.

위해서 제시한 여러 법칙을 최대한 이용하는 PACTree란 자료구조를 저자들은 만들었다. PACTree에서는 search layer와 data layer가 분리되어 있다.

Search Layer: Radix trie구조의 Seach layer는 Key-value pair로 저장되는 Data의 Key를 부분적으로 받아서 (Anchor key라고 불리며 데이터가 유지되는한 절대로 불변하는 특징을 가지고 있다.) Searching하는 역활을 한다. 이 과정은 GA1즉 Lookup operation을 효율적으로 처리하여 read operation의 수를 최대한으로 줄였다. 또한 Trie자료구조는 partial key만을 비교하는데 이를 통해서 read하는 양또한 줄일 수 있었다. 즉 NVM의 read latency를 효과적으로 줄일 수 있게 되었다.

Data Layer: Doulbe linked list구조의 b+ tree구조의 leaf node를 사용하였다. 이 노드들을 key-value pairs들을 가지고 있다. 이 slot에 insert하고 delete하고 update하는 것은 expensive persistent memory allocation즉 GA3를 줄이는 효과가 있다. 따라서 최소한의 allocation으로 할당하며 sequential read GA5를 가능하게 하는 효과를 주었다.

Concurrency Control: Data layer과 search layer은 Optimistic version lock을 이용함으로써, concurrent한 작업을 가능하게 하였다. read-optimized lock은 NVM에 존재하는 Lock의 State을 바꾸지 않아서 additional write가 생기지 않는 장점이 있다 (GA2).; PACTree에서 SMO즉 strutual modification operation에 의한 lag을 줄이기 위해서, logging을 사용하여 SMO작업을 처리하였다. 이는 SMO작업을 Block시키기보다 비싼 코스트가 드는 Search layer update를 log를 통하여 분리된 thread가 처리하게 함으로써 극복하였다.

Crash Consistency: Mostly log-free구조를 채택하였다. 즉 Log를 쓰기보다 valid bitmap을 사용하여 data node의 어느 부분이 valid한지 체크하도록 하였다. 특히 전에 설명한 SMO는 merge/split을 crash와 분리하는 log로도 사용하였다.; 또한 Data node에서 key-value에 관한 부분만을 consistency에 한정함으로써 log에 적용해야 하는 범위또한 줄였다.

PDL-ART: Persistent Durable Linearizable ART란 컨셉을 제시하여 여러 문제들을 해결하였다. ART는 https://db.in.tum.de/~leis/papers/ART.pdf에 소개된 바와 같이 Trie의 일종으로 space oprimization을 수행한 버전이다. 우선 optimistic version lock을 통하여 read와 write가 exclusive하게 실행되도록 하였다. 특히 Exclusive한 Lock의 사용은 crash consistency에서 시스템이 행한 write순서와 같은 순서로 작업하는 것으로 대체할 수 있도록 하였다. 만약 node가 만들어진뒤 할당되는 과정에서 crash가 나면 memory leak이 발생하게 된다. 이러한 상황을 극복하기 위해서 PDL-ART와 같은 경우에는 NVM에 작은크기의 Allocation logs을 유지하고 있으면서 crash recovery에서 할당되었으나 접근할 수 없는 영역을 복구하도록 하였다.