The Case for Learned Index Structures
이 글에서는 SIGMOD 2018 에 게재된 논문인 The Case for Learned Index Structures 를 리뷰 해보려고 합니다. 이 논문은 데이터베이스에서 사용하는 자료구조에 머신러닝을 적용한 실험에 대해 서술하고있습니다.
머신러닝을 시스템에 적용할 때 크게 두가지 여러가지 어려움이 있다고 생각하는데요. 하나는 정확도입니다. 시스템에 쓰이는 대부분의 알고리즘은 확률적이지 않고 항상 정확해야합니다. 예를들어 가상 메모리 주소를 물리 메모리 주소로 변환하는 알고리즘은 항상 정확해야합니다. 99.99% 정확도를 갖는 주소 변환 머신 러닝 모델로 기존 페이지 테이블 워크를 대체한다면 0.01% 확률로 잘못된 주소로 변환하여 이상한 데이터에 접근하거나 segmentation fault 를 일으킬 수 있습니다.
또 다른 하나는 지연시간입니다. 모델의 크기에 따라 다르겠지만 시스템 크리티컬 패스에 들어갈만큼 추론시간이 짧으려면 모델의 크기, 즉 학습 성능이 매우 한정적이게 됩니다. 그래서 100% 정확하지 않아도 되고 추론시간이 숨겨질 수 있는 부분에만 머신러닝을 적용할 수 있을것이라고 생각했습니다. 예를들면 page cache prefetch 처럼 접근될 것으로 예측하는 페이지를 미리 캐시에 올려두는 부분은 머신러닝을 적용하기 알맞은 시스템 컴포넌트라고 생각합니다.
그런점에서 인덱싱은 반대로 머신러닝을 적용하기 어렵지 않을까 싶었는데 과연 어떻게 문제를 극복했을지 궁금해서 이 논문을 읽게 됐습니다.
Introduction
효과적으로 데이터에 접근하려면 인덱싱이 필수적이고 데이터 접근 패턴에 따라 다양한 index structure 를 선택할 수 있습니다. 예를들어, 범위로 데이터를 접근 할 때는 B-tree 로 인덱싱을 하는게 가장 효과적이고, 키로 데이터를 접근할 때는 Hash map, 그리고 데이터 존재여부를 판단할 때는 Bloom filter 를 사용하는것이 가장 효과적입니다.
이런 index structure 는 범용적으로 사용될 수 있게 설계되었기 때문에 특정 데이터 분포를 가정하지 않습니다. 따라서 데이터 분포에 맞게 구조가 변경되지 않습니다. 예를들어 정해진 길이의 레코드를 1부터 100M까지 정수를 키로 갖는 데이터라면 B-tree 를 사용하는것 보다 1차원 배열을 사용하는것이 훨씬 유리합니다.
문제는 이런 데이터 패턴은 미리 알 수 없고 매번 데이터 패턴에 맞는 index structure 를 만드는것도 쉽지 않다는 것입니다. 하지만 머신러닝을 사용한다면 매번 새로운 데이터 패턴에 맞는 index structure 를 설계할 필요 없이 학습을 통해 데이터 분포에 꼭 맞는 index structure 를 만들 수 있습니다.
Range Index
범위 인덱스는 연속된 키의 데이터를 접근하기 위해 B-tree 와 같은 index structure 를 사용합니다. 그래서 한 페이지(노드)에 연속된 여러개의 키가 모여있고 한번의 탐색으로 근접한 키를 동시에 탐색하기에 유리합니다. B-tree 는 주어진 키의 데이터가 위치한 블록(페이지)를 찾을 수 있도록 설계되었습니다. 다시말해서 B-tree 는 키와 키에 해당하는 데이터가 위치하는 블록(페이지)의 시작주소(pos-0)와 블록의 마지막 주소값(pos+pagesize)을 매핑한다고 말할 수 있습니다. 머신러닝 모델 관점에서 본다면 B-tree 는 입력값 키에 해당하는 데이터의 위치(pos)를 예측하는데 항상 min_error=0, max_error=pagesize 인 모델입니다.
그래서 키를 입력하면 데이터 위치를 예측하는 모델을 학습하고 모든 키값을 조회했을때 worst over- and under-prediction 을 min- and max error 로 사용하면 B-tree 와 동일한 semantic guarantees 를 갖게됩니다. B-tree 를 사용할때처럼 키를 입력하고 [pos-min_error, pos+max_error] 에서 키 값에 해당하는 데이터를 찾습니다.
Model Complexity
B-tree 를 learned index 로 대체하려면 B-tree 의 성능을 먼저 알아야합니다. 100M개의 키와 페이지 크기 100 의 B-tree 를 기준으로 B-tree 성능을 분석해보겠습니다. 페이지 크기가 100 이기 때문에 B-tree 노드 하나 당 1/100 의 precision gain 이 있습니다. 루트 노드에서 다음 레벨의 노드로 이동할 때 100M 개의 범위에서 1M 범위로 줄어들게 됩니다. 그리고 그 다음 레벨 노드로 이동하면서 1M 에서 10K 로 줄어들고, 그 다음엔 100 으로 줄어들게 됩니다. B-tree 노드 하나를 순회하는데 대략 50 cycles 이 소요됩니다. Learned index 에서 사용하게될 SIMD 명령어는 1 cycle 당 8–16 번의 산술연산을 수행 가능합니다. 따라서, 50*8=400 산술연산으로 1/100 이상의 precision gain 이 있다면 learned index 가 더 좋은 성능이라고 볼 수 있습니다. 이 비교는 보수적(B-tree 에 유리하고 learned index 에 불리)이라고 볼 수 있는데요. 그 이유는 B-tree 노드 순회 cycle 은 모든 노드가 캐시되어있다고 가정한건데, 만약 캐시미스가 난다면 50–100 cycles 가 더 필요하게됩니다. 또한 CPU SIMD 명령보다 훨씬 더 좋은 성능의 가속기(GPU)가 빠르게 발전하고있는데 CPU branch operation (B-tree 순회에 사용되는 if-statement)은 성능향상이 거의 없기 때문입니다.
Range Indexes as CDFs
어떤 머신러닝 모델로 범위 인덱스를 모델링할지 결정해야합니다. 논문은 데이터가 전부 정렬되어있다고 가정하고 있습니다(FAST 같은 하드웨어 최적화된 B-tree 에서도 동일한 가정을 하고있고 인메모리 데이터베이스에서는 일반적인것이라고 합니다). 이런 가정은 키—데이터위치 관계가 cumulative distribution function(CDF)와 비슷하다고 볼 수 있습니다. 그래서 learned range index 가 CDF 를 approximate 하도록 모델링합니다.
Naïve Learned Index
논문은 위 아이디어를 검증하기 위해 naïve learned index 를 구현하고 실험했습니다. Learned index 는 얕은 fully connected neural network (NN) with 2 layers, 32 neurons per layer, ReLU activation 을 Tensorflow 로 구현하여 200M개의 웹서버 로그 데이터를 사용해 학습했습니다. 성능은 임의로 선택된 키를 조회하는데 걸린 시간으로 측정했습니다.
이 세팅으로 1250 predictions/sec (= 800,000 ns/prediction)의 성능을 확인했습니다. 같은 데이터를 B-tree 를 사용하면 300ns, binary search 를 사용하면 900ns 에 조회하는 것에 비하면 naïve learned index 의 성능은 현저히 떨어집니다. 그 이유 중 하나는 Tensorflow 오버헤드입니다. Tensorflow 는 더 큰 모델을 효율적으로 실행하기 위해 디자인 되었습니다. 또 다른 이유는 하나의 NN 으로 모든 개별 데이터에 오버핏하게 만드는것은 더 많은 CPU 시간이 필요하기 때문입니다. (논문에는 이정도로 설명이 되어있지만, 추측하기로는 naïve learned index 가 어느정도 학습이 되긴했으나 min-error, max-error 를 충분히 줄일만큼 학습시키기에 너무 큰 모델이었다는 뜻인것 같습니다.) 마지막으로 B-tree 는 루트 노드가 항상 캐시에 있기 때문에 훨씬 빠른 성능을 보여줍니다. 이 문제를 해결하기 위해 논문은 learning index framework (LIF) 와 recursive model index (RMI)를 제안합니다.
Learning Index Framework
LIF 는 인덱스 합성 시스템으로서 다양한 인덱스 설정을 생성하고 최적화하며 자동으로 테스트까지 합니다. LIF 는 학습에는 Tensorflow 를 사용하지만 추론에는 절대 Tensorflow 를 사용하지 않습니다. 대신 Tensorflow 로 학습한 weights 를 추출하고 작은 모델에 특화된 C++ 로 구현된 모델로 추론할 수 있도록합니다. 그 결과 간단한 모델 추론시간을 30 ns 까지 줄였습니다.
Recursive Model Index
앞서 얘기했듯이 하나의 모델로 충분히 오버핏하게 만드는것은 어렵습니다. 그래서 논문은 모델을 스테이지별로 나눠서 여러개의 모델이 정확도를 낮춰서 학습하도록합니다. 최상위 모델은 모든 범위의 키를 입력받을 수 있고 다음 스테이지에 어떤 모델을 사용할지 예측하도록 학습합니다. 다음 스테이지 모델은 전체 범위에 대한 키를 학습하지 않고 전체 중 일부분의 키 범위만 학습하고 역시 다음 스테이지 모델을 예측하도록 학습합니다. 이런식으로 하면 한 모델이 한번에 모든 키 범위에 오버핏할 필요가 없습니다.
RMI 의 장점 중 하나는 다양한 모델 조합으로 learned index 를 구성할 수 있다는 점입니다. 예를들어 최상위 레벨에서는 얕은 NN 으로하고 가장 마지막 스테이지에서는 간단한 linear regression 을 사용해서 시간 & 공간 비용을 줄일 수 있습니다. 만약 데이터 학습이 어렵다면 최하위 레벨을 B-tree 로 사용하는 것도 가능합니다.
Search Strategy
기존 범위 인덱스는 찾는 key 에 해당하는 data 가 속한 블록의 첫번째(혹은 마지막) 포지션을 찾고 그 후에 그 위치부터 이진탐색이나 스캐닝을 통해 데이터를 찾습니다. Learned index 가 다른점은 찾는 key 의 데이터 위치를 바로 예측한다는 점입니다. Learned index 는 이 점을 활용하여 탐색합니다. 첫번째 방법은 예측한 위치(pos)을 middle point 사용해서 이진탐색을 하는 방법입니다. 이 때 탐색 범위 [left, right] 는 [min-error, max-error] 입니다. 두번째 방법은 이진탐색처럼 2분할 탐색을 하는 대신 4분할탐색(quaternary search)을 하는것입니다. 이 때 세 기준점은 pos-σ, pos, pos+σ 이고 탐색범위는 마찬가지로 [min-error, max-error] 입니다.
Range Index Results
첫번째 실험은 2-stage RMI models 을 B-tree 와 비교합니다. 사용된 데이터셋은 두개의 실제 데이터셋(Weblogs, Maps)과 인조 데이터셋(Log-normal) 입니다. Weblogs 데이터셋의 크기는 200M이며 learned index 의 최악의 성능을 볼 수 있을만한 데이터 분포입니다. Maps 의 크기도 200M이며 데이터는 선형적이고 고르게 분포되어있습니다. 인조 데이터셋의 크기는 190M이고 log-normal 분포를 따르도록 생성했습니다. Grid search 를 통해 튜닝했고 RMI model 의 첫번째 스테이지는 0–2 hidden layers (8–16 neurons per layer) 가 가장 좋은 성능을 보였습니다. 두번째 스테이지는 linear model 이 좋은 성능을 보였습니다. B-tree 는 128 page size 가 가장 좋은 조회(lookup) 성능을 보였고 이 성능을 기준(회색 음영처리)으로 일반화된 성능을 표시했습니다.
Learned index 거의 모든 설정에서 B-tree 보다 좋은 성능을 보였습니다. 속도는 1.5–3배 빨랐고 메모리도 훨씬 적게 사용했습니다. Learned index 의 성능은 두번째 스테이지의 모델 개수에 따라 큰 차이를 보였습니다. 주목할만한 점은 B-tree 는 어떤 데이터셋에서든 비슷한 성능을 보이지만, learned index 는 데이터 분포를 학습하기 때문에 데이터셋에 따라서도 다른 성능을 보여준다는 점입니다.
Point Index
B-tree 가 range index 에 사용되는 대표적인 데이터구조인 반면 point index 에서는 Hash-map 이 주로 사용됩니다. Hash-map 을 디자인할때 가장 어려운 점은 충돌을 줄이는 것입니다. 예를들어 100M개의 데이터와 크기 100M의 Hash-map 이 있을때 기대 충돌율은 생일역설과 비슷하게 33% 입니다. 충돌이 생기면 separate chain 을 사용하든(closed-addressing) 다른 비어있는 인덱스를 찾든(open-addressing) 해서 충돌을 해소해야합니다. 하지만 이런 방법들은 성능에 영향을 주게됩니다. 놀랍게도 앞서 range index 에서 사용한 CDF approximation 은 충돌이 적은 해시를 만들기 좋은 방법이 될 수 있습니다. Range index 와 다르게 정렬된 데이터의 위치 대신 Hash-map 크기 M 으로 scale 된 값으로 CDF 를 학습하면 CDF 를 hash-function 으로 사용할 수 있습니다. 만약 CDF 를 완전히 배울 수 있다면 충돌이 전혀 없는 Hash-map 을 만들 수 있습니다.
Point Index Result
Learned point index (learned hash function) 평가를 위해 2nd stage 크기가 100K 인 RMI 모델을 사용하고 MurmurHash3 와 충돌률을 비교했습니다. Learned point index 는 최대 77.5% 더 낮은 충돌률을 보였고 실행시간은 25–40ns 정도 소요됐습니다.
Learned hash function 의 실행시간을 비용으로 충돌률을 감소했을 때 얻을 수 있는 이점은 Hash-map 구조에 따라 다릅니다. 예를들어 레코드 크기가 커질수록 더 큰 메모리 오버헤드를 줄여서 공간적 이득을 볼 수 있습니다. 레코드 크기도 작고 수가 많지 안을때는 cukoo-hashing 이 시간적으로도 공간적으로도 더 좋은 성능을 보였지만, 레코드 수가 많아지면 learned hash function 을 사용한 chained-hashmap 이 더 빠른 성능을 보였습니다. 결과적으로 learned hash function 은 hash-map 구조에 따라 비용보다 더 큰 이득을 얻을 수도 있습니다.
Existence Index
Range index, point index 와 더불어 가장 많이 사용되는 인덱스는 existence index 입니다. Existence index 는 Bloom filter 로 구현할 수 있습니다. Bloom filter 는 확률적으로 false positive 가 발생하지만 false negative 는 발생하지 않으며 Hash-map 에 비해 훨씬 공간 효율적이기 때문에 existence index 로 주로 사용됩니다. Bloom filter 는 크기 m 의 비트 배열과 k 개의 hash function 으로 구성됩니다. Bloom filter 에 키를 추가하면 키를 k 개의 hash function 에 넣고 k 개의 결과 포지션의 비트를 set 해줍니다. 조회를 할때는 마찬가지로 k 개의 hash function 을 통해 얻은 k 개의 포지션의 비트가 전부 set 되어있는지 확인합니다.
Learned point index 를 위한 learned hash function 은 모든 키들에 대해 최대한 충돌이 일어나지 않게 학습합니다. 반면에 Learned bloom filter 에서 사용될 learned hash function 은 존재하는 키(key)에 대해서는 최대한 충돌이 일어나지 않지만 존재하지 않는 키(non-key)들은 최대한 충돌이 일어나도록 학습해야합니다. 이런식으로 학습한 결과는 Appendix E 에 소개되고있고 본문에는 hash function 을 학습하지 않고 바로 키 존재 확률을 학습하도록 모델링합니다. Learned bloom filter f 는 존재하는 모든 키에 대해 f(key) = 1 로 학습하고 존재하지 않는 모든 키에 대해 f(non-key) = 0 으로 학습합니다. 모델의 마지막에는 sigmoid activation 이 있어서 추론시 결과가 0 혹은 1이 아니라 확률로 나오게 되는데, 이 값이 역치 τ 보다 크거나 같으면 키가 존재하는 것으로 예측하고 작으면 키가 존재하지 않는 것으로 예측합니다. 문제는 이렇게 학습하게되면 false negative 가 발생하게 됩니다. False negative ratio (FNR) 을 0으로 만들기 위해 overflow Bloom filter 를 사용합니다. 이 때 사용되는 Bloom filter 는 non-key 로 예측된 키들에 대해서만 사용하기 때문에 기존 Bloom filter 보다 훨씬 적은 공간으로도 충분한 false positive ration 를 보장할 수 있습니다.
Existence Index Result
Learned bloom filter 의 성능을 비교하기 위해 170만개의 URL 을 데이터셋으로 사용했습니다. 1% FPR 을 보장하려면 normal Bloom filter 는 비트 배열을 위해 2.04MB 메모리를 필요로합니다. 반면에 Learned Bloom filter 는 비트 배열 대신 0.0259MB 의 학습된 파라메터로 충분합니다. 여기에 overflow Bloom filter 가 더 필요한데 그 크기를 합치면 총 1.31MB 로 normal Bloom filter 에 비해 36% 더 작은 공간으로 동일한 성능을 보였습니다.
Conclusion
논문은 세가지 learned index (range index, point index, existence index)가 데이터 분포를 학습함으로써 기존 index structure 보다 더 효율적인 index structure 가 될 수 있음을 보였습니다.
서두에 머신러닝을 시스템에 적용하기 어려운 점 두가지 정확성과 실행시간을 언급했는데요. 정확성 문제를 어떻게 해결했는지 살펴보겠습니다. Range index 의 경우 모델이 정확한 위치가 아니라 위치의 범위를 학습하는 것이라서 머신러닝을 적용할 수 있었습니다. Point index 의 경우 모델의 결과가 충돌률로 이어지기 때문에 반드시 정확한 결과를 얻어야하는 경우가 아니었습니다. 마지막으로 existence index 는 반드시 0% FNR 을 보장해야하는데 머신러닝 모델만으로는 보장할 수 없기 때문에 머신러닝 모델로 범위를 좁히고 기존 index structure 를 사용해서 정확성 문제를 해결했습니다.
실행시간 문제를 해결하기 위해 기존 머신러닝 프레임워크인 Tensorflow 대신 사용할 Learned index framework 를 만들었습니다. Learned point index 의 경우 실행시간은 더 늘어났지만 공간효율이 더 중요한 index structure 이기 때문에 적은 실행시간 비용(13ns)로 최대 80%의 공간 이득을 얻었습니다. Existence index 는 같은 공간대비 FPR 을 낮출 수 있음을 보임으로써 실행시간을 조금 늘려서 false positive 에 발생하는 비용을 줄일 수 있음을 보였습니다.
