From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees
Introduction
지난번 포스팅에서는 The Case for Learned Index Structures 논문을 통해 machine learning 을 B-tree, Hash, Bloom filter 와 같은 index structures 에 적용한 learned index 에 대해 알아봤습니다. 이번에는 From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees (Bourbon) 논문을 통해 Log-Structured Merge Tree (LSM) 에 어떻게 machine learning 을 적용할 수 있을지 알아보겠습니다.
Log-Structured Merge Tree
LSM 은 B-tree 만큼이나 널리 쓰이는 index structure 입니다. 90년대에 처음 소개되었고 BigTable, LevelDB 에서 사용된 이후로 주요 index structure 가 되었습니다.
먼저 LSM 구조를 간단히 살펴보겠습니다. LSM 은 메모리와 디스크에 각각 다른 구조로 인덱스 정보를 저장합니다. Insert 요청이 들어오면 메모리에 트리구조로 되어있는 memtable 에 먼저 key-value 데이터를 저장합니다. Memtable 이 가득 차면 디스크에 있는 sstables 의 최상위 레벨에 flush 하는데, 이 때 데이터는 정렬되어 하나의 파일로 저장됩니다. (최상위 레벨(Level 0) 파일들의 키는 서로 overlapping 할 수 있습니다.) 최상위 레벨이 가득차면 그 다음 레벨로 compaction 하게 되는데 이 과정은 merge soft 와 유사합니다. (Level 1 부터는 sstable 파일끼리 overlapping 하지 않습니다.) 인접한 두 레벨(상위, 하위)의 파일을 병합하여 새로운 파일을 만들고 하위 레벨에 저장합니다.
Update 요청이 들어오면 sstable 에서 key-value 를 찾아서 수정하지 않습니다. 대신 처음 insert 처럼 memtable 에 먼저 저장되고 마찬가지로 compaction 됩니다. 따라서 하나의 key 에 대해 여러 key-value 가 LSM 에 존재할 수 있습니다. 이 때, 가장 최신 key-value 는 가장 최상위 레벨에 있는 데이터입니다. 그래서 Lookup 요청이 들어오면 최상위 레벨부터 해당 key-value 데이터를 찾아내려갑니다.
좀 더 자세히 lookup 과정을 보면, 찾는 key 가 존재할 수 있는 sstable file 을 찾고 (①FindFiles), 해당 파일의 index block, filter block 을 load(②LoadIB+FB) search 하고(③SearchIB, ④SearchFB), key가 존재하면 data block 을 load(⑤LoadDB), search하고(⑥SearchDB) value 를 읽습니다(⑦ReadValue). 이 과정을 internal lookup 이라고 부릅니다. Internal lookup 에서 key-value 를 찾으면 positive internal lookup, 못찾으면 negative internal lookup 이라고 부릅니다. Internal lookup 은 두 스텝으로 나눠볼 수 있습니다. Indexing step (①FindFiles, ③SearchIB, ④SearchFB, ⑥SearchDB) 은 key 를 찾기위해 file, block 들을 조회하고, data-accessing step (②LoadIB+FB, ⑤LoadDB, ⑦ReadValue) 은 데이터를 디스크로부터 읽어옵니다.
Motivation
Learned index 를 LSM 에 적용한다면 indexing step 시간을 줄일 수 있습니다. 그래서 만약 전체 lookup 처리시간 중 indexing step 시간이 차지하는 부분이 많다면, learned index 로 성능을 향상시킬 수 있습니다. 논문에서는 indexing step 이 전체 lookup 중 차지하는 부분이 얼마나 되는지 알아보기위해 Baseline(WiscKey) 를 분석합니다.
위 Figure 에서 볼 수 있듯이 dataset 이 전부 메모리에 캐시되어있다면 learned index 로 개선할 수 있는 부분이 충분히 많습니다. 메모리에 캐시되어있지 않더라도 스토리지 성능이 좋아질 수록 indexing 이 차지하는 비율이 높아져서 learned index 로 성능 향상을 기대해볼 수 있습니다.
기존 Learned index 는 월등한 읽기 성능을 보였지만 쓰기 작업은 재학습을 필요로 하기 때문에 지원하지 않았습니다. LSM 도 역시 쓰기 작업이 수행되면 구조가 바뀌게됩니다. 하지만 대부분은 불변으로 남아있고 일부분만 변경이 됩니다. sstable 파일은 불변이기 때문에 한번 학습하면 이 파일이 다른 sstable 파일로 교체될때까지 재학습할 필요는 없습니다. 만약 오래동안 교체되지 않고(긴 수명) 많은 lookup 을 서빙(높은 효율성)하는 sstable 파일이 있다면 learned index 를 적용하여 큰 이득을 볼 수 있습니다. 논문은 이러한 파일이 얼마나 존재하는지 확인하기 위해 실험을 설계하고 그 결과를 보여줍니다.
먼저 sstable 의 수명을 측정하기 위해 2.56 억 key-value 를 로드하고 2억개의 요청을 수행하고. 각 레벨별 sstable 파일의 평균 수명과 평균 수명의 누적 분포도를 측정합니다. 실험 결과를 통해 세 가지 특징을 관측할 수 있습니다.
• 관측 #1 — 낮은 레벨 파일의 평균수명이 높은 레벨 파일의 평균수명보다 깁니다.
• 관측 #2 — 쓰기 비율이 낮아지면 높은 레벨 파일의 평균수명도 꽤 길어집니다.
• 관측 #3 — 쓰기 비율이 증가할수록 평균수명이 줄어들지만, 쓰기 비율이 높아도 낮은 레벨의 파일은 긴 시간동안 살아있습니다.
이 관측을 통해 두 가지 학습 가이드라인을 도출할 수 있습니다.
• 학습 가이드라인 #1 — 낮은 레벨의 파일 학습을 선호하라.
• 학습 가이드라인 #2 —학습하기 전에 기다려라.
다음으로 sstable 의 효율성을 측정합니다. 이 실험을 통해 세 가지 관측 결과를 얻을 수 있습니다.
• 관측 #4 — 대부분의 데이터가 낮은 레벨에 있지만, 레벨이 높을수록 internal lookup 수가 증가한다.
• 관측 #5 — 요청이 특정 키들에 몰려있으면 높은 레벨에서도 positive internal lookup 이 많이 발생한다.
이 관측 결과로 다음의 학습 가이드라인을 만들 수 있습니다.
• 학습 가이드라인 #3 — 높은 레벨 파일 학습을 간과하면 안된다.
• 학습 가이드라인 #4 — 요청 키 분포를 알아야한다.
Bourbon Design
이제 위 학습 가이드라인을 활용하여 Bourbon 이라고 명명한 LSM 기반의 data store 를 디자인합니다. 파일 학습에 사용된 모델은 piecewise linear regression (PLR) 입니다. 파일 안의 데이터는 정렬 되어있기 때문에 부분별로 여러 직선으로 학습하는 PLR 은 적절한 선택입니다. PLR 은 데이터의 위치를 에러 범위와 함께 예측합니다. 즉, 실제 데이터 위치 d 는 예측된 위치의 에러범위 d_pos ± δ 안에 있습니다. PLR 을 학습하기 위해 Greedy-PLR 알고리즘을 사용했습니다.
단명하는 파일 혹은 장수해도 활용이 안되는 파일은 학습 비용이 득보다 더 클 수 있습니다. 그래서 그래서 Bourbon 은 득실을 따져서 득이 될걸로 예측될 때만 학습합니다.
먼저 단명하는 파일은 학습하지 않습니다. 비용을 들여 학습을 했는데 금방 사라진다면 실이 더 크다고 볼 수 있습니다. 그래서 Bourbon 은 파일이 T_wait (50ms) 보다 오래 살아있어야 학습합니다.
파일이 오래 지속되더라도 모든 파일을 학습하지 않고 득실을 따져보고 학습해야합니다. 득실을 따지기 위해서 학습 비용(실)과 lookup 시간 감소(득)를 평가할 수 있어야합니다. 먼저 학습 비용(C_model)은, 보수적인 관점으로 학습 시간동안 다른 프로세스들이 간섭을 받는다고 가정하고, 학습 시간(T_build)으로 설정합니다. 학습 시간은 파일의 데이터 포인트 양에 선형 비례하기 때문에, 미리 데이터 포인트 당 평균 학습시간(T_data)을 계산해두고 파일의 데이터 포인트 양(T_data)을 곱해서 계산합니다.
학습을 통해 얻을 수 있는 이득(B_model)을 계산하는 건 조금 더 복잡합니다. 학습 이득은 Baseline 대비 lookup 시간 감소량으로 계산합니다. Lookup 시간은 positive lookup 인지 negative lookup 인지에 따라 다르기 때문에 positive, negative 를 구분하여 계산합니다. Baseline 과 Bourbon 의 평균 positive, negative lookup 시간(T_p.b, T_n.b, T_p.m, T_n.m)을 예측하기 위해 Analyzer 가 같은 레벨의 다른 파일들의 통계를 이용합니다. 얼마나 많은 lookup 이 발생할지(N_n, N_p)도 통계를 통해 계산합니다.
Bourbon 은 초반에 충분한 통계 데이터를 쌓기위해 항상 모델을 학습하도록 작동합니다 (T_wait 시간 대기는 여전히 동작합니다). 충분한 통계 데이터가 쌓이면 득실을 따져서 득이 될 것 같은 (B_model > C_model) 파일만 학습합니다.
위 그림은 Bourbon 의 lookup 과정을 Baseline 과 비교하여 보여줍니다. LoadIB+FB 후에 학습된 모델이 있다면 index block 을 조회(SearchIB)하는 것 대신 모델로 데이터 위치(d_pos)와 에러 범위(δ)를 예측(ModelLookup)합니다. 그 다음 Bourbon, Baseline 둘 다 filter block 을 조회해서 d_pos ± δ 범위의 data chucnk (혹은 Baseline 의 경우 data block) 이 로드 되어있는지 검사하고 없다면 로드합니다. 그리고 Key 를 찾고 value 를 읽습니다.
Evaluation
Bourbon 의 성능을 평가하기위해 다양한 데이터 분포의 인위적 데이터(Linear, Seg-1%, Seg-10%, Normal)와 실제 데이터(Amazon reviews (AR), New York OpenStreetMaps (OSM))를 사용합니다.
먼저 Bourbon 과 Baseline 의 lookup 시간을 분석하여 어느 부분에서 성능 향상이 있었는지 보여줍니다. 위 평균 지연시간 분석 Figure 를 보면, Search 지연시간이 2.9×, 2.4× 줄어든 것을 볼 수 있습니다. (Bourbon 은 Search = ModelLookup + LocateKey, Baseline 은 SearchIB + SearchDB 입니다.) LoadData 에서도 성능향상이 되었는데요. 그 이유는 Bourbon 은 더 좁은 범위(d_pos ± δ)의 byte 만 로드 하기 때문입니다.
Bourbon 은 모든 데이터셋에서 WiscKey 보다 좋은 성능을 보이지만 데이터셋에 따라 성능 향상의 정도(1.23–1.78×)가 다릅니다. 성능 향상의 차이는 PLR 의 segment 수가 적을수록 높은 것을 알 수 있습니다. 그 이유는 segment 가 많으면 ModelLookup 이 느려지기 때문인데요. ModelLookup 은 PLR model 을 추론할때 lookup key 가 해당하는 segment 를 찾아야하는데, segment 가 많을수록 segment 를 찾는데 더 많은 시간이 소요됩니다.
위 Figure 는 데이터 로딩에 따른 성능변화를 보여줍니다. 데이터 로딩 순서는 최상위 sstable 파일 overlapping 에 영향을 줍니다. 데이터를 key 순서대로 입력하게되면 overlapping 이 발생하지 않고, 임의의 순서로 입력하면 overlapping 이 발생할 수 있습니다. Overlapping 이 많아지면 candidate file, negative lookup 이 많아지고 불필요한 Search 로 인해 성능이 악화됩니다.
Bourbon 은 Cost-benefit analyzer 로 학습의 득실을 분석해서 학습여부를 결정합니다. 이번 실험은 Cost-benefit analyzer 의 성능 기여도를 측정하기 위해 Bourbon(cba)을 두 가지 다른 설정(offline, always) 그리고 Baseline 과 비교합니다. Bourbon-offline 은 최초 로딩된 데이터로 학습된 모델을 그대로 유지하고 쓰기 작업이 발생해도 모델을 재학습하지 않습니다. Bourbon-always 는 쓰기 작업이 발생하면 항상 모델을 재학습합니다. Bourbon-cba 는 cost-benefit analyzer 로 재학습 여부를 결정합니다.
먼저 (a) lookup 과 insert 에 소요된 시간을 보면 Bourbon 이 WiscKey 보다 항상 더 적은 시간을 소요하고 쓰기 비율이 늘어날 수록 그 차이가 줄어드는 것을 볼 수 있습니다. 쓰기 비율이 높아질수록 파일의 수명이 줄고 성능개선을 할 수 있는 부분이 줄어들기 때문입니다. 쓰기 비율이 높아질수록 Bourbon-always 이 Bourbon-cba 보다 좋은 성능을 보이는데, Bourbon-always 는 항상 재학습하기 때문에 lookup 에서 최적화된 성능을 보여줍니다. 하지만 성능 향상에 대한 비용 또한 증가합니다. (b) 는 쓰기 비율이 높아질수록 Bourbon-always 의 학습비용이 증가하는 것을 보여줍니다. 그래서 결국 최종 성능(c)에서 WiscKey 보다 안좋은 성능을 보여줍니다. 이 결과는 Bourbon 의 cost-benefit analyzer 가 의도대로 동작하고 있음을 보여줍니다. 쓰기 비율이 높아질수록 Bourbon-offline 의 최종 성능(c)은 WiscKey 에 수렴합니다. 그 이유는 (d) 에서 볼 수 있듯 Bourbon-offline 의 lookup path 가 baseline 의 path 와 거의 동일해지기 때문입니다.
위 Figure 는 Bourbon 을 YCSB 의 다양한 워크로드 그리고 SOSD 의 다양한 데이터셋에 대해 평가를 보여줍니다. 앞서 분석했던 실험 결과에 일관되게 Bourbon 은 Read 비율이 높아질수록 더 높은 처리량을 보여줍니다. 또한 모든 SOSD 데이터셋에서 WiscKey 보다 낮은 지연시간을 보여줍니다.
Conclusion
Bourbon 논문은 LSM 을 분석하여 어느 부분이 학습으로 개선될 수 있을지 분석하고 분석을 기반으로 어떻게 학습을 적용할지 학습 전략을 수립하는 과정을 보여줍니다. 또한 Bourbon 을 다양한 실험을 통해 설계 의도대로 동작하는지 철저히 분석했습니다. 기존에 읽기 작업만 지원하던 learned index 와는 다르게 쓰기 작업이 발생해도 cost-benefit analyzer 를 이용해 재학습 여부를 판단하면 다양한 워크로드와 데이터셋에서 Baseline 보다 좋은 성능을 낼 수 있음을 보였습니다.
