<문서를 읽기 위해 전제하고 있는 배경 지식>
(1) Log-Structured Merge (LSM) Tree 와 Hash 자료구조에 대한 이해
(2) System Software 에 대한 기본 지식
원본 문서 링크: https://ieeexplore.ieee.org/abstract/document/9458602?casa_token=yQsjzZM6nDwAAAAA:bG5GWRHLDvAI3kognFzHkMtQ9tL_Jxu_JTEN_PUBle9dQxpAli1qlyEEBiTKclrqwcCQgnQS
WipDB 에서 언급한 Well-designed Key-Value Store (KV-Store) 를 위한 조건들과 이를 위한 LSM-tree 자료구조
Key-Value Store (KV-Store) 라는 것은 컴퓨터가 다루는 어떤 데이터를 Key-Value 라는 인터페이스를 통해 CRUD (Create, Read, Update, Delete) 기능을 제공하고 유저 수준의 응용 프로그램이 데이터의 사전 정의된 (pre-defined) key 값을 통해 다양한 크기의 데이터를 접근할 수 있도록 하는 데이터베이스 스토리지 엔진이다.
Well-designed (매우 잘 설계된) KV-Store 의 조건과 이를 달성하기 위한 노력들
본 논문에서는 저자들은 KV-Store 가 다음의 요구 조건을 만족시켜야 Well-designed (잘 설계된) 상태가 된다고 주장한다.
- 스토리지의 저장 포맷에 비해 상대적으로 작은 크기의 KV 데이터를 저장하는 경우에도 성능 보장
- 범위 기반 탐색 (Range query) 질의 기능 제공 (KV 데이터가 key 를 기준으로 정렬되어 있어야 하는 조건임)
- 낮은 Read Amplification Factor (RAF)
- 낮은 Write Amplification Factor (WAF)
이 조건들을 다 만족 시킬 수 있는 대응책이 Log-Structured Merge (LSM) Tree 라고 과거 연구에서부터 알려져오고 있었다. 그러나 저자들은 LSM-tree 자료구조 자체만으로 위 조건들을 동시에 충분히 만족시키기 어렵다고 주장한다. 특히, WAF 를 낮출 수 있는 방안으로써 LSM-tree 자체만으로는 한계가 있다는 비관적인 입장을 내세운다.
위 조건들에 대한 부연 설명은 다음과 같다. Block Storage Device (예: SSD)가 만약 4KB block 단위로 데이터를 저장하는 상황에서 오직 몇 바이트 안되는 KV 데이터들이 굉장히 많이 존재한다고 가정해보자. 그렇다고 했을 때, 여러 KV 데이터들이 하나의 Disk block 에 저장되고 각 KV 데이터가 Storage 내의 어떤 block 과 offset 에 존재하는지에 대한 정보 (일종의 Indexing 정보) 를 모든 KV 데이터마다 개별적으로 관리되어진다면 인덱스 크기가 어마어마하게 커질 것이다. 그래서 모든 인덱스 정보를 메모리 상에 저장할 수 없어서 특정 KV 데이터를 읽기 위해서는 먼저 인덱스를 읽는 작업이 수반되어야 하고 그 다음 인덱스 정보를 기반으로 실제 KV 데이터를 읽는 과정 (두 종류의 디스크 읽기) 이 필요한 경우가 매우 많을 것이다. 즉, 읽기 성능 오버헤드가 존재한다.
그렇다면 이번에는 모든 KV 데이터를 key 를 기준으로 정렬(sort) 한 상태로 disk block 에 저장한다면 어떻게 될까? KV-Store 스토리지 엔진은 사실 특정 disk block 이 어떤 key 범위에 해당하는 데이터들을 저장하고 있는지와 이 disk block 의 offset 만을 인덱싱 정보로 하여 여러 KV 데이터를 관리할 수 있게 된다. 이 때문에 인덱스 정보 크기가 상대적으로 작아지고 메모리에 전부 유지시킬 가능성이 커져 오직 KV 데이터를 위한 읽기 1번만 필요로 하게 된다. 이러한 방식은 위에서 언급한 읽기 성능 오버헤드를 해소할 수 있고, 동시에 KV 데이터가 정렬되어 있으니 범위 기반 탐색 (Range query) 기능도 가능하다는 장점이 있다. 그런데 이 방식의 부작용은 Write Amplification Factor (WAF) 가 낮아지지 않는다는 것이다. 지속적으로 KV 데이터가 들어오게 되었을 때, Sorting 해주는 작업이 존재하는 이상 WAF 를 낮추는데 한계가 있다. 예를 들어보면, Disk 에 M 개의 완전 정렬된 KV 데이터가 있고, N 개의 KV 데이터가 들어온다고 가정했을 때, Sorting 작업은 M 만큼 Disk 읽기, M+N 만큼 Sorting 후 Disk 쓰기를 필요로 한다. 따라서, WAF 는 (M+N)/N 이다. 이 식을 보아서도 알 수 있듯, M 자체가 커지면 WAF 가 커지고, M/N (N 대비 M 의 양) 상대적인 차이가 커져도 WAF 가 증가함을 알 수 있다.
Log-Structured Merge (LSM) Tree 간략한 소개와 약점 (여전히 높은 WAF)
LSM-tree 는 본래 스토리지에 존재하는 데이터를 순차적 (Sequential) 하게 읽거나 쓰기 위해서 설계된 Disk-centric 자료구조로 고안되었고, 지금에 이르러서는 위 WAF 설명에서의 M/N 의 상대적 비율을 줄이는 역할로도 자리매김하였다. LSM-tree 자료구조의 중요한 컨셉은 데이터를 Logging (Append instead of updating) 하면서 점진적으로 merge-sort (Compaction) 해나가는 방식으로 데이터 간 정렬을 지원하고 이 정렬된 데이터를 여러 계층적 (hierarchical) 구조로 저장된다는 컨셉이다. LSM-tree 에서는 초기에 KV 데이터가 들어오게 되면, MemTable 이라는 메모리 자료구조에 KV 데이터들을 잠시 버퍼링을 한 후, 충분한 양이 쌓이면 Level 0 에 SSTable 이라는 포맷으로 데이터를 저장한다. 이 Level 이라는 것이 LSM-tree 의 계층 컨셉이 형상화가 된 것이다. 만들어진 SSTable 내의 KV 데이터는 정렬된 상태이지만, Level 0 의 다른 SSTable 들과는 정렬이 되어 있지 않은 상태가 된다. 그 이후, Level 0 에도 SSTable 역시 충분한 양이 쌓이면, 인접한 Level (Level 1) 의 SSTable 과 함께 Compaction 이라는 절차를 진행한다. Compaction 은 Level 0 와 1 의 SSTable 을 스토리지로부터 읽고, Merge-sort 를 진행한 후, 스토리지로 다시 Re-write 하는 과정이다. 아래 그림의 왼쪽과 같이, 회색 음영 색칠된 SSTable (66-98), (66-78), 그리고 (80-91) 이 Compaction 과정을 거치게 된다면, 아래 그림의 오른쪽과 같이 새로운 SSTable (66-73) 그리고 (74-98) 이 만들어진다.
그러나 단순한 LSM-tree 로는 인접한 Level 간에 일어나는 Compaction 때문에 WAF 를 줄이는데 한계가 있다는 점을 저자들은 지적하고 있다. LSM-tree 기반 KV-Store 에서 여전히 WAF 가 크다고 말하는 이유는 이미 디스크에 저장된 KV 데이터와 새롭게 저장되는 KV 데이터를 함께 고려하여 Sorting 을 하고 디스크에 다시 쓰기 (Re-write) 를 해야 하기 때문이다. 이렇게 높은 WAF 를 보이는 Sorting 과 Re-write 이 작업들이 KV-Store 의 전반적인 성능에 악영향을 끼치게 되는데 그 이유는 즉각적인 Sorting 을 위한 KV 데이터 읽기와 결과물에 대한 쓰기 때문에 Disk I/O 를 필요로 하니 스토리지 대역폭을 잡아먹고 Sorting 을 위한 CPU 점유로 인해 포그라운드 유저 I/O 수행도 간섭되어 지연이 생길 수 있기 때문이다.
LSM-tree 기반 KV-Store 에 WAF 를 더욱 낮추려는 의도로 Approximate Sorting 적용하기
그럼 도대체 어떻게 WAF 를 더욱 낮출 수 있을지 저자들은 고민한 결과가 본 논문의 시작이다. 본 논문에서는 Approximate sorting 이라는 기존에 있었던 테크닉을 LSM-tree 에 적용하려는 시도를 한다. 이 Approximate sorting 방식이 데이터를 완전 정렬하지 않고도 KV Store 의 효율성을 어느 정도 향상 시킬 수 있는 대안이라고 저자들은 보고 있기 때문이다. 본 섹션에서는 Approximate Sorting 의 정의부터 살펴보고, 이를 단순하게 LSM-tree 에 적용한 방식에 대한 고찰이 기술되어 있다.
Approxmiate Sorting 이란?
Approximate Sorting 이란 전체 데이터를 정렬하는 것이 아니라, Bucket 이라는 데이터의 논리적인 그룹 단위를 만들어놓고, 각 Bucket 내의 데이터는 정렬되어 있지 않지만, Bucket 간의 데이터 범위는 정렬된 상태를 보장하는 테크닉이다. 예를 들어, 정수형 데이터를 무작위로 담고 있는 한 리스트 [71, 10, 5, 22, 1, 68, 24] 가 있고, Bucket 의 개수가 2개 라고 한다면 그리고 두 Bucket 이 데이터를 균등하게 나눠 갖는다고 할 때, Approximate Sorting 을 수행하면 다음과 같은 최종 결과가 있다. $$ \therefore Bucket_1 = [10, 5, 1], Bucket_2 = [71, 22, 68] $$
저자들은 이러한 Approximate Sorting 을 LSM-tree 기반 KV-Store 에 도입한다고 했을 때 왜 WAF 를 더욱 낮출 수 있다고 본 것일까? 이는 KV 데이터 추가 시, 전체 정렬 대신 새로운 데이터만 Bucket 에 추가하거나 부분 정렬하기 때문에 Re-write 하는 양이 적어지기 때문이다. 이와는 별도로 Bucket 내부의 데이터가 정렬이 되어 있지 않다 하더라도, Bucket 의 크기를 Block Storage Device 의 4KB block 크기와 맞추게 된다면 인덱싱 정보도 여전히 낮게 유지할 수 있고, Bucket 간에는 정렬 상태를 유지하니까 범위 기반 탐색도 어느 정도 지원 가능하다고 볼 수 있다 (Disk Block 을 Bucket 으로 볼 때, block 한 번 읽음으로써 안에 있는 KV 데이터를 다 가져올 수있으니 그 때 범위 조건 체크를 수행하면 된다).
참고로 이러한 특징이 발견되었으니, 저자들이 이 특징을 기반으로 Well-designed KV-Store 의 조건들을 만들어 앞단에서부터 설명하여 Approximate Sorting 의 타당성을 설명하는 논리 뒷받침 도구로 활용한 숨은 의도를 파악할 수 있는 대목이다.
Approximate Sorting 을 LSM-tree 에 적용하면, 먼저 모든 KV 데이터의 key 공간 (Key space) 을 파악한 후 이 전체 key 공간을 여러 Bucket 으로 분할한다. 이때 각 Bucket 은 고유한 key 공간을 할당받게 된다. 이 방식의 핵심은 Bucket 간에는 정렬이 유지되지만, Bucket 내부의 데이터는 완전히 정렬되지 않거나 부분적으로만 정렬된다는 점이다. 위 그림에서 회색 음영 색칠된 부분(21-35 와 22-31) 그리고 L1 의 21-38 까지의 KV 데이터들이 하나의 Bucket 안에 있는 상태이다. 이 Bucket 안에서는 완전히 정렬된 상태는 아니지만, 다른 Bucket 간에는 정렬되어 있는 상태이다. Approximate Sorting 을 사용하게 되면 LSM-tree 의 Level size 는 지수적으로 증가하더라도 tree 의 깊이는 낮게 조절되고 동시에 같은 Level 에 존재하는 데이터를 Re-write 할 필요가 없기 때문에 WAF 가 낮아질 수 있는 대안이라고 소개한다.
Approxmiate Sorting 를 적용한 기존의 LSM-tree 시도들과 한계
기존 LSM-tree 는 특정 Level 안에서는 KV 데이터가 Sort 된 상태 (Horizontally sorted), Level 간에는 KV 데이터가 Sort 되지 않은 상태 (Vertically unsorted) 였다. 반면, Approximate Sorting 을 적용하게 된 경우에는 각 Level 에 대해서 Bucket 단위로 KV 데이터를 파티셔닝하고 Bucket 간에는 Sort 된 상태 (Intra-Bucket sorted), Bucket 내부에서는 Sort 되지 않은 상태 (Inter-Bucket unsorted) 를 나타낸다. 이러한 경우 각 Level 안에 Key range 를 중첩하여 갖게 되는 Bucket 들이 다수 존재할 수 있으며 이 상태에 놓여있는 Level 을 “Approximately sorted” 되어 있다고 한다.
이러한 접근법과 유사한 PebblesDB(SOSP' 17) 와 LSM-trie(USENIX ATC' 15)의 기존 연구들이 존재한다. 이들의 아키텍쳐 상 LSM-tree 의 Level 이 컨셉적으로 Approximately sorted 라 볼 수 있다. 왜냐하면 Compaction 동안 같은 Level 에 있는 데이터에 대해서 Re-write 하는 과정이 없기 때문이다. 구체적 흐름으로는 본질적으로 다음의 로직이 동작한다.
- 특정 $Level_i$ 의 한 Bucket 의 KV 데이터를 정렬
- 다음 $Level_{i+1}$ 의 Bucket 들의 Key Range 체크
- $Level_i$ 의 Bucket 을 어떻게 나눌지를 $Level_{i+1}$ 의 Bucket 들의 Key Range 를 기반으로 파티셔닝하여 $Level_{i+1}$ 의 새로운 Bucket 으로써 Append 수행.
이러한 아키텍쳐에서는 읽기 성능 저하를 개인적으로 예상했다. 왜냐하면 찾고자 하는 Key 가 존재하는 Key 범위가 하나의 Level 에서도 다수 존재할 수 있으니 LSM-tree 에서 찾아봐야 할 Sorted runs (SSTable) 이 많아지기 때문이다. 그러나 저자들은 더 견고한 bloom filter 를 쓰면 큰 걱정이 아니라고 언급만하고 넘어갔다.
사실 $Level_{i+1}$ 의 Bucket 들의 Key Range 를 벗어난 KV 데이터를 Append 해야 한다면 새로운 Bucket 을 만들수도 있고, 마지막 Bucket 의 Key range 를 조정해줄 수 있다.
Approximate Sorting 이 적용한 기존 연구 접근법들의 한계
Approximate Sorting 을 효과적으로 하려면 각 Bucket 으로 저장되는 KV 데이터가 균등하게 고루 분배 되어야 한다. 그렇지 않다면 특정 Bucket 에 KV 데이터가 몰리게 된다면 M/N 의 상대적 비율을 줄이는 본래 목적에 실패하게 된다. 따라서, 각 Bucket 이 균등하게 KV 데이터를 나눠 갖도록 key 공간을 분할해야 하는데 LSM-trie 연구는 독특한 접근법을 취하고 있다. 우선, 사용자가 제공한 (user-supplied) key 에 암호화 함수(예: SHA-1) 를 적용하여 해시 값을 생성하고, 이 해시 값을 기반으로 트리에 데이터를 균등하게 분산시킨다. 이 방식은 데이터 분산 측면에서는 효과적이지만, 범위 쿼리(Range query) 를 지원하기 어렵다는 심각한 제약이 있다. 해시 함수는 원래 키의 순서 정보를 파괴하기 때문에, 연속된 범위의 키들이 저장 공간에서는 전혀 연관성 없는 위치에 저장된다. 이는 저자들이 처음에 설정한 '잘 설계된 KV 저장소(Well-designed KV Store)'의 원칙에 부합하지 않는 결과를 가져온다고 말하고 있다. PebblesDB 는 LSM-trie 의 한계를 극복하기 위해 다른 방향을 취했다. 우선, 사용자 key 를 정렬된 상태로 저장하여 범위 쿼리를 지원하고, 동시에 Guard 라는 개념을 도입해서 Approximate Sorting의 이점을 유지하려고 한다. 여기서 Guard는 특정 레벨 내 KV 데이터의 key 공간 (Key space)을 분할하는 지점이 되고, KV 데이터의 일부 key 값이 Guard 역할을 할 수 있으며, Guard로 분할된 각 키 공간은 하나의 버킷에 대응된다.
<Guard 선택 과정>
특정 레벨 (Level_i) 에 m 개의 Guard 를 생성하는 과정은 다음과 같다:
1. KV 데이터가 저장될 때 정해진 샘플링 규칙 (예: 10% 확률) 에 따라 key 값을 추출한다.
2. 추출된 n 개의 key 값들을 정렬한다: [k₁, k₂, ..., kₙ]
3. 균일 분포 (Uniform distribution) 에 따라 n/m 간격으로 key 값을 선택하여 최종 Guard로 지정한다.
<구체적인 예시>
key 집합 = [10, 15, 20, 25, 30, 35, 40, 45, 50, 55] 이 있고, Guard 개수(m)가 3으로 설정된 경우:
1. 랜덤 샘플링 후 선택된 key 가 [15, 20, 45, 50, 55] 총 5개 (n) 라고 가정.
2. 일정 간격 (n/m ≈ 2) 으로 Guard 를 설정하면 20 과 50 이 Guard 로 선택된다.
3. 최종적으로 Bucket 은 다음과 같이 구성된다: Bucket 1: [10 ≤ k < 20] Bucket 2: [20 ≤ k < 50] Bucket 3: [50 ≤ k ≤ 55]
그러나 PebblesDB 역시 한계가 있는데 이는 저장되는 KV 데이터의 key 분포에 따라 Guard 위치가 변화할 수 있다는 점이다. 데이터 분포가 변하면 PebblesDB 는 Guard 를 결국 분할 (Splitting) 해서 조정해야 하고, 이는 같은 레벨에 존재하는 KV 데이터에 대한 Re-write 작업을 다시 필요로 한다. 구체적으로, 각 Bucket 은 하나의 파일로 저장되기 때문에, 새로운 Guard 가 생성되면 새로운 Bucket 구성에 맞게 파일을 재작성해야 한다. 이러한 Re-write 과정은 Approximate Sorting 을 통해 얻으려던 WAF 감소 효과를 상쇄시킨다.
Approxmiate Sorting 을 위한 키 분포 안정성 확인 실험과 WipDB 의 접근법
PebblesDB 사례에서도 봤듯, Approximate Sorting 을 통해 WAF 를 낮추는데에 있어 핵심은 key 분포 (Key Distribution) 의 안정성에 달려있다. 저자들은 Key Distribution 의 불안정성이 있고 이러한 상황에서 Approximate Sorting 접근을 하려고 했던 PebblesDB 를 비판하고자 아래 실험을 진행했다.
LevelDB 에서 db_bench 로 매 50K 만큼의 KV 데이터가 저장될 때마다 Level 1, 2, 3 에 대해서 Guard 를 설정하도록 하여 Guard 를 몇 개 만들어두고, 100 Byte 크기의 10억개 만큼의 KV 데이터를 더 삽입하면서 이 Guard 의 위치가 새롭게 삽입되는 KV 데이터의 Key 분포에 따라 어떻게 달라지는지를 추적 실험했다.
KV 데이터가 삽입되면서 Compaction 이 진행되고 이에 따라서, 기존에 설정된 Guard 가 어떤 Key 값으로 달라지는지에 대한 Guard Position 을 전체 Level 키 분포 대비 백분율로 표현한 그래프임.
KV 데이터가 삽입되면서 Compaction 이 진행되고 이에 따라서, 기존에 설정된 Guard 가 어떤 Key 값으로 달라지는지에 대한 Guard Position 을 전체 Level 키 분포 대비 백분율로 표현한 그래프임.
위 실험에 따르면, 세 Level 에서 전부 Guard 위치가 달라지는 것을 볼 수 있는데, 특히, Level 3 은 Level 1 과 2에 비해 안정성이 있는 키 분포가 오는 것으로 해석할 수 있어보이고, Level 1 같은 경우는 Guard 가 굉장히 크게 변동하고 있으므로, Approximate Sorting 이 효과가 덜한 것으로 볼 수 있다. 이렇게 Level 3 까지 내려와서 저장되는 KV 데이터들은 보통 KV 데이터가 몇 주, 몇 달, 몇 년에 걸쳐서 저장되는 데이터들이기 때문에 상위 레벨의 데이터들에 비해서 Long-term stable distribution 을 갖는다고 볼 수 있다.
이에 저자들은 안정적인 일부 키 공간 분포를 활용하기 위해 LSM-tree 의 구조를 변형한 새로운 접근 방식인 WipDB 를 설계하는데 이르렀고 다음의 세 가지 특징을 고안해냈다. 우선, 기존 LSM-tree 의 상위 레벨을 제거한다. 일반적인 LSM-tree 는 여러 Level 이 있지만, WipDB 는 상위 레벨들을 없애고 마지막 레벨에 집중한다. 둘째, 키 공간을 균등한 용량의 버킷으로 분할한다. 워크로드의 장기적인 키 분포에 따라 키 공간을 균등한 용량의 Bucket 으로 나눈다. 이는 특정 Bucket 에 데이터가 몰리는 현상을 방지한다. 마지막으로, 각 버킷 내부는 소형 LSM-tree 로 구성된다. 각 Bucket 은 그 자체로 작은 LSM-tree 구조를 가진다.
WipDB 아키텍쳐 디자인
WipDB 에서는 LSM-tree 에서 top-level 부분 (E.g., Level 1 or 2) 을 제거하고, 마지막 Level (E.g., Level 3) 만 남기고 이 Level 에서 저장되는 KV 데이터를 Long-term stable key distribution 에 따라서 파티셔닝을 수행한다. 파티셔닝된 각 Bucket 은 LSM-tree 의 미니어쳐처럼 동작한다. Stable Key Distribution 에 따라서 파티셔닝되는 KV 데이터들이 어떻게 분리되어 어떤 Bucket 으로 들어가는지가 정해져서 저장되기 때문에 한 번에 올바른 Bucket 을 찾아 저장한다는 의미로 Write-In-Place (Wip) 라고 시스템을 명명하였다. 각 Bucket 마다 별도의 MemTable 이 있고 (E.g., a few thousands), 이 MemTable 은 디폴트로 Hash 로 구현된다. 몇 가지의 특징을 중심으로 WipDB 를 살펴보면 다음과 같다.
MemTable 이 디폴트로 Hash 자료구조를 사용하는 이유
- KV 데이터가 삽입되는 순간, 본래대로 Skip List 로 구현했을 때는, Skip List 에 대한 Lookup 이 필요하다. 왜냐하면 삽입 위치를 찾아야 하기 때문이다. 그러나, 여러 개의 Bucket 이 존재하고 이에 따라 여러 개의 Skip List 가 있게 되는데, Lookup 을 여러 Bucket 의 Skip List 에 대해 번갈아가면서 수행하면, CPU 의 Locality 에 따른 캐싱 효과를 얻지 못하게 되기 때문이다. 구체적으로, 계속적으로 다른 Bucket 의 Skip List 를 읽어들이려면 Cache Miss 가 발생하고, CPU 가상 메모리 주소를 물라 주소로 변환한 정보가 캐싱된 TLB 또한 데이터가 자주 바뀌어 TLB Miss 가 발생하게 된다.
- 아래 그림은 저자들이 실험한 것으로, Linux 에서 제공하는 Huge Page 를 사용하여 Hash 를 저장한 Hash-Huge 와 그냥 Page 를 사용하여 Hash 를 저장한 Hash, Bucket 마다 Skip List 를 갖도록 설계한 SkipLists, 모든 Bucket 이 하나의 Skip List 를 공유하도록 한 1-SkipList 를 Cache Miss, TLB Miss, Put Throughput 을 비교한 실험이다.
MemTable 의 구체적 Design
- WipDB 는 구체적으로 Hash Table 을 사용하여 MemTable 을 구현했는데, 아래 그림과 같이, 각 Bucket 마다 64 Byte 의 엔트리를 갖는 MemTable 이 있고, 이는 Cacheline 크기와 동일한 크기이다.
- Cacheline 이란 CPU 캐시의 메모리 관리 단위이다. 프로세서가 메모리 데이터를 캐시에 저장하거나 가져올 때 데이터를 효율적으로 처리하기 위해 고정된 크기의 데이터 블록을 사용하는데 이 고정된 블록이 Cacheline 이다.
- 각 엔트리는 2 Byte 의 Hash Tag 와 6 Byte 의 KV 데이터가 저장된 페이지에 대한 가상 주소가 저장되어 있고, 만약 엔트리가 꽉 찼다면 freeze 시키고 다음 엔트리 하나 또 만들어서 데이터 삽입 수행을 지속한다. 그 후에 Minor compaction 을 통해 Disk 에 저장되는 순간에 KV 데이터들을 정렬한다.
WipDB 의 On-disk Data Structure 인 LevelTable
- MemTable 에서 Disk 로 저장될 때, WipDB 는 LevelTable 로 저장하는데 하나의 bucket 의 sub-level (a file) 이 LevelTable 이다. PebblesDB 나 LSM-trie 처럼, 어느 한 Level 에서 KV 데이터가 많아져서 Guard 를 더 두는 것처럼 데이터를 Split 하는 것이 WipDB 에서는 수행하지 않고, 대신 Bucket 크기를 최대한 줄일 수 있을 만큼 줄여두었다 (e.g., 최대 1GB 이고 각 Level 은 수 MB 정도). 대신 필요할 때마다 새로운 Bucket 자체를 만드는 방식을 취한다.
Range Query 의 효율성 문제
- 여러 Bucket 이 여러 sub-level 을 갖고 KV 데이터를 저장하기 때문에, 큰 Range 에 대한 Range Query 가 요청되게 되면, 굉장히 큰 I/O intensive 한 Task 를 처리하도록 동작한다.
- WipDB 는 정렬이 불가능한 Hash 기반의 MemTable 을 갖고 있으므로 MemTable 에 대한 Range query 수행도 사실 상 어렵다. 대신, WipDB 에서는 MemTable 을 실험적으로 적절하게 줄일 수 있는 만큼 줄여 (E.g., a few thousand KV items per MemTable) sort 할 전체 양 자체를 조절한 흔적도 보이며, 만약 특정 Time 윈도우 동안 여러 Range query 가 들어오게 되었을 때, Hash 를 전부 읽어서 Skip List 로 바꿔놓고, 여러 번의 Range query 를 수행하고 다시 Hash 로 돌려놓는 기법을 갖추었다.
- 여러 Bucket 에 대해서 Range query 수행하는데 다른 thread 로부터 KV 데이터가 저장되게 되는 경우에는 LevelDB 와 RocksDB 와 같이, KV 데이터에 단조증가 (감소하지않는) 하는 sequence number 를 부여하여 Range Query 가 실행되기 직전의 sequence number 를 갖는 KV 데이터에 대해서만 고려한다.
Bucket 분할과 병합
- 초기 WipDB 는 Bucket 의 개수가 한 개로 시작한다. 그러나 점차 KV 데이터가 쌓일수록 Bucket 은 커자개 되는데 당연히 Hash Table 의 scheme 처럼 각 Bucket 의 크기 조절을 WipDB 에서도 하고 있다. 어느 한 Bucket 의 모든 Level (총 L 개) 에서 T 개 (미리 정해둔 임계값) 만큼의 최대 LevelTable 개수를 갖게 되는 경우엔 해당 Bucket 는 분할을 시작한다. 분할 시 미리 정해둔 값인 N 개의 Bucket 으로 분리된다. 분할이 시작될 때 분할의 대상이 되는 Victim Bucket 은 Read-only 가 되고 N 개의 새로운 Bucket 에 대한 MemTable 이 In-memory 자료구조로써 준비되어 포그라운드 쓰기도 다른 thread 를 통해 동시처리를 수행할 수있다. 기존의 PebblesDB 가 Guard 를 추가함으로써 파티셔닝된 데이터를 더욱 분할하는 매커니즘은 특정 Level 의 전체 KV 데이터에 대해서 분할하는 반면, WipDB 에서는 더 적은 KV 데이터에 대한 분할이라는 점을 하나의 강점이라고 드러내고 있다.
- 구체적인 분할 과정은 다음과 같다. Victim Bucket 을 N=4 개의 Bucket 으로 분할하는 시나리오이다. 총 Level 은 L = 3개이며 각 Level 마다 존재하는 LevelTable 은 5개이며 T 값이라 가정한다.
Step0: N 개의 MemTable 우선 생성
E.g., 여기서 4 개의 Bucket 이 만들어질 것이므로 4 개의 MemTable 생성
Step1: Victim Bucket 의 모든 Level 의 LevelTable 을 읽어서 Key Distribution 을 확인.
E,g., 여기서는 간단하게 Min / Max 로 키 분포 확인한다고 하면, Min_key = 1, Max_key = 1000 일 때 ⇒ Victim Bucket 의 Key range = [1, 1000]
Step2: (N-1) 개의 splitter (분할 지점) 을 만들기 위해 총 (L x T) 개 만큼의 sub-level 들에 대해서 (N-1) 개의 Key 데이터 샘플링 수행.
E.g., 총 4개의 분할을 만들어내기 위해 3개의 Splitter 가 필요하고 총 3x5 = 15 개 만큼의 sub-level 에 대해서 3 개의 Key 데이터 샘플링 수행.
E.g., Sampling Sub-level 1: [250, 500, 750], Sampling Sub-level 2: [300, 550, 600], … , Sampling Sub-level 15: [310, 570, 820]
Step3: Sampling 된 Splitter 를 하나의 List 로 정렬.
E.g., [250, 300, 310, 500, 550, …, 600, 750, 820]
Step4: 각 Bucket 에 들어갈 KV 데이터가 균등하게 분배되도록 최종 (N-1) 개를 다시 선택.
E.g., [300, 570, 750]
Step5: 최종 분할 지점에 따라 데이터 재분배 하여 N 개의 Bucket 에 마지막 Level 의 LevelTable 로써 (file) 디스크 Write 수행.
- 반대로 Bucket 병합은 사실 안해도 되는 작업이나, Memory footprint 가 커질 우려가 있어 Bucket 의 크기 자체가 정해둔 임계값보다 낮으면 병합할 수 있으나 안해도 그 오버헤드가 무시할만하다고 언급됨.
- 그럼 이 설계에서의 WAF 를 구해보자면 한 Bucket 당 허용되는 Level 개수를 $L_{max}$라고 하고, 하나의 Bucket 크기가 1 이라고 했을 때 WAF 는 $L_{max}$ 가 되고, N 개의 Bucket 으로 균등하게 분할된다면 각 Bucket 의 크기는 1/N 이 된다. 새롭게 만들어진 각 Bucket 에 대해서도 (1 - 1/N) 만큼의 KV 데이터가 다시 쌓여 크기가 1 이 된다고 했을 때 WAF 는 $L_{max}(1 - 1/N)$ 이 된다. 계속 Split 된다고 했을 때에도 마찬가지로 WAF 가 $L_{max}(1 - 1/N)$ 이기 때문에 Bucket 개수나 실제 KV Store 의 크기와 무관하게 WipDB 의 총 WAF 는 $O(L_{max})$ 에 수렴한다고 볼 수 있고, 실험적으로 밝혀낸 $L_{max}$ 값은 3 이고, N 의 값은 8 일 때 WAF 가 4.15 를 넘지 않는다는 것을 확인했다.
Power Failure 로 인한 데이터 손실을 막기 위한 WipDB 의 WAL 쓰임새
- WipDB 의 자료구조와 새 매커니즘에 맞춰진 WAL 쓰임새 변형에 대한 마이너한 내용으로 추가적인 내용 확인은 논문 참조.
Read-aware Compaction Scheduling
- WipDB 에서는 Bucket Split 이 일어난 직후 얼마간 Read 성능이 떨어질 가능성이 존재한다. 왜냐하면 항상 새로 생겨난 Bucket 의 마지막 Level 에 데이터를 관리하기 때문이다. 또한 기존 LSM-tree-based KV Store 가 Level 이 많아질수록 Search 비용이 커지고, Intensive Compaction 은 동시적으로 Read 를 수행하려고 하는 thread 의 Task 수행을 느리게 만든다는 문제가 있는데, WipDB 는 이러한 부분들에 대한 최소한의 대응으로써 Read-aware Compaction Scheduling 을 제시했다.
- 이 스케쥴링은 컨셉적으로 쓰기와 읽기가 같은 Bucket 안에 동시적으로 들어오지 않는 이상, read-intensive 한 Bucket 에 대해서 Compaction 을 우선적으로 수행할 수 있도록 가중치를 둔 라이트한 스케쥴링 하나를 추가했고 구체적인 수식은 논문 참조.
시스템 평가 (Evaluation)
- System Comparison Group
- WipDB, LevelDB, RocksDB, PebblesDB
- Major Observation Points
- WipDB 의 Write 성능 향상 정도 체크
- WipDB 의 새로운 MemTable 디자인 성능 체크
- 워크로드의 Key Distribution 이 바뀔 때의 WipDB 의 대응 성능 체크
- Experimental Setup
- 실험을 위한 하드웨어 환경 세팅
- Dell T440 server with two 4-core Intel Xeon Gold 5122 CPUs and 64GB DRAM
- Hyper-threading Disabled
- OS: 64-bit Linux (v.4.20.0)
- FS: Ext4
- Storage: Intel 750 SSD (PCIe 1.2TB)
- 1200 MB/s sequential write throughput, 440K IOPS for random 4KB reads
- 실험을 위한 소프트웨어 환경 세팅
- WipDB with 2MB MemTable for each Bucket
- LevelDB, RocksDB, PebblesDB use 64MB MemTable
- $L_{max}$= 3, $T$=8, $N$=8
- 1000 Write requests are logged as a batch
- 실험을 위한 하드웨어 환경 세팅
주요 성능 평가1: 실질적인 WAF 감소에 따른 Write Throughput 변화 관찰
사용된 워크로드는 Write-intensive Workload (In-house synthetic workload 처럼 보임) 이고, Key & Value 크기와 개수는 총 8 billion KV requests (16 Byte & 100 Byte with uniform distribution) 이다.
- 관찰 포인트 1: WipDB 가 기본적으로 성능이 좋은데, MemTable 을 최대 1.6G 만큼 사용해서 다른 KV Store 보다 많이 사용하니, RocksDB 가 1.6G 의 MemTable 을 사용하는 시스템 (RocksDB-1.6G) 도 포함해서 실험해봤더니 WipDB 의 성능이 우수하다는 것 관찰 (WipDB-S 는 MemTable 을 Skip List 로 구현한 버전임).
- 관찰 포인트 2: 반대로, MemTable 크기를 단순히 늘리는게 성능 향상을 만들어내지 못한다는 점도 관찰 가능했음. KV Store 들이 I/O 에 더 큰 성능 의존성이 있다는 추측이 가능함.
- 관찰 포인트 3: PebbelsDB 의 Approximate Sorting (Guard-based Key range overlapping) 방식은 Guard 가 계속 생겨나게 되는데 이 Guard 가 생겨난다는 것은 기존에 Disk 에 저장된 SSTable 에 대해서 KV 데이터를 Split 해서 새롭게 정의된 Guard 사이에 새로운 SSTable 로 다시 re-write 하는 것이므로 WAF 가 WipDB 보다 커서 성능이 떨어짐.
- 관찰 포인트 4: WipDB 가 일관적으로 낮은 WAF 를 보여주고 처리량 변화 자체가 안정적인 상태를 유지하는 것처럼 보이기도 하는데 KV 데이터가 많이 들어오게 되어 Compaction 되더라도 Bucket 으로 안에 일부 KV 데이터에 대해서만 Compaction 이 진행되니까 성능 저하를 덜 일으킬 수 있는 특징으로 저자들은 해석하고자 함.
- 관찰 포인트 5: Skip List 로 구현한 WipDB 는 Sorting 상태를 유지하기 때문에 CPU Cache miss 가 Hash 기반 WipDB 보다 많아서 성능이 낮음.
주요 성능 평가2: Key Distribution 변화 대응 관찰
워크로드는 위 실험과 같은 Write-intensive Workload 처럼 보이고, Key & Value 크기와 개수는 Total 4 billion KV requests (16 Byte & 100 Byte with uniform, exponential, normal, exponential-reverse distribution, each 1 billion KV requests) 이다.
- 관찰 포인트 1: WipDB 의 Bucket 이 1 개로 시작해서 점차 Bucket Split 되어지고 Key 분포가 달라짐에 따라서도 일관적으로 낮은 WAF 로 시스템 운용 가능하다는 것을 볼 수 있음.
- 관찰 포인트 2: Key 분포가 달라지는 경계에서는 Throughput 이 조금 저하되는 것도 볼 수 있는데 기존의 Bucket 에 대해서 새로운 Key 분포를 찾고 거기서 Bucket Spliiter (분할 지점) 이 되는 Key 값을 샘플링 하는 것이 단순한 로직이 아닌 것 같음. 키 분포에 따라 조금씩 영향 받는 로직이 있기 때문에 Throughput loss 가 매우 조금 발생하는 것 같음.
'Middleware System Softwares' 카테고리의 다른 글
| YCSB를 위한 가이드 (1) | 2025.04.14 |
|---|