High-Dimensional Bayesian Optimization with Multi-Task Learning for RocksDB

• RocksDB는 general-purpose embedded key-value store를 사용
• 본 논문에서는 10개의 파라미터를 다양한 범위로 auto-tuning해서 Throughput을 개선한다.
• 보통 optimizer들은 고차원 문제와 많은 training sample 요구를 한다.
• 이 문제를 해결하기 위해 multi-task modeling과 clustering을 통한 차원 감소를 진행한다.
  • 일반적으로 최적화하는 것은 수렴 속도가 빠른 것과 다른 tuner들이 찾기 못하는 복잡한 세팅을 찾으려는 것이 목적
    • but, 계산량이 많아
    • 그래서 사전지식과 Bayesian Optimization loop를 사용해서 throughput을 최대화 하는 파라미터를 찾는다.

1. Introduction

• RocksDB를 튜닝하는 것의 문제점
  • RocksDB는 30개가 넘는 파라미터를 가지고 있어서 configuration 조합들은 사용자에게 너무 많다
  • 하드웨어는 사용자가 선택한 configuration에 큰 영향을 준다.
  • 각 Application은 독특한 접근 패턴을 가지고 있다.
• Auto-tuning으로 이러한 문제를 해결하려 함
  • 하지만 많은 training sample이 필요한데 이 training sample들은 restart and execution을 해야 함
  • 따라서 굉장히 효율적인 Bayesian Optimization(BO)를 사용. Process는 아래 그림과 같음

• BO의 단점으로는 curse of dimensionality 때문에 고차원에서는 사용하기 어렵고, 계산량이 비싸다는 것이 단점이다.

  • 따라서 전문가의 지식을 추가해서 이 문제를 해소하고자 한다.
  • multiple target을 통한 최적화, sub-task decomposition을 통해 고차원 문제를 줄일 수 있다.

• multiple target 통해 최적화 하는 것은 다양한 내부 component에 성능을 영향을 받기 때문에 이득이 있음

  • 예를 들어 RocksDB에서는 write throughput은 IO stalls에 bottleneck이 있지만 지연시간을 줄여서 향상 가능

• 하지만 target을 늘리는 것은 계산량을 증가시키기 때문에 decomposition을 사용하도록 한다.

  • 모든 파라미터들을 한번에 다 고려하는 것이 아닌 일부 subset으로 decompose하고 target을 최적화함

    

• 기여도는 다음과 같다.

  • BO에 structural knowledge를 주입해서 수렴속도를 낮춤
  • manual task decomposition을 사용해서 차원 문제를 해결함
  • default보다 최대 1.45배 향상시킴

2. Background

2.2 Bayesian optimization

• Black-box function 최적화 문제를 해결하려는 효율적인 최적화 framework
• 미지의 목적 함수(Surrogate Model)을 만들고 평가를 통해 최적의 하이퍼파라미터 조합을 탐색하는 것.
  • 즉 확률적인 추정을 수행하는 모델
  • 이 함수로 GP, Additive Kernel, TPE, RF를 사용하도록 한다.
• Acquisition Function은 확률적 추정 결과를 바탕으로 유용한 다음 입력값 후보를 추천해 주는 함수를 지칭

3. Structured multi-task optimization

3.1 Overview

• 메커니즘을 통해 전문가의 지식을 model에 넣고, 사용하들은 main objective를 최적화할 수 있는 low-level metrics를 확인할 수 있다.
• multi-task learning을 통해 system component 간의 상호작용을 알 수 있고, 샘플에서 더 많을 것을 배워서 수렴에 필요한 관찰을 줄일 수 있다.
• 파라미터의 manual grouping을 통해 최대 차원을 줄였고 수렴 속도를 빠르게 했다.

3.2 Problem space and assumptions

• GP를 사용할 때, multivariate Gaussian distribution이고, 모든 점에서 미분 가능하다.

• modeling space에서 랜덤하게 선택된 500개의 독립된 실험을 수행

• 그 결과는 아래 그래프와 같음

  

3.3 Multi-task learning

3.3.1 Tasks

• RocksDB 구조의 이해를 바탕으로 3개의 추가적인 objective를 선정함.
• 이 objective들은 직접적으로 혹은 간접적으로 IOPS에 영향을 준다.
• 선정한 3개는 다음과 같다.
  • WriteAmplification
  • ReadBlockGetP99
  • Level0Tolevel1P99

3.3.2 Intrinsic coregionalization model

• 이 3가지 task를 더함에 따라 GP의 kernel 함수를 변경해야 한다.

  • Intrinsic Coregionalization Model kernel을 사용한다.

    

    • k_x은 covariance kernel, k_T는 task similarity kernel을 의미한다.
      • 따라서 서로 연관성을 파악하기 좋음
    • 각 output은 BO loop에서 최적화된다.

  • task간의 지식을 공유하는 능력과 각 task 별 충분한 sample이 있으면 수렴 속도를 빠르게 할 수 있다.

• 수행하는 알고리즘은 다음과 같다.

• scaling하고 normalizing 한다.
  • 이 것이 분포를 smooth하게 해서 더 쉽게 할 수 있도록 함

3.3.3 ICM challenges

• ICM이 뭘 제공하긴 하는데 모르겠고, 이는 확장성에 문제가 있다고 함
  • 일반적으로 GP는 O(n³)인데, task가 생기면 O(Tn³)임
  • 그래서 Decomposition이 필요하다.

3.4 Decomposability through clustering

3.4.1 Decomposability in RocksDB

• RocksDB의 large parameter space는 *"차원의 저주"* 와 높은 계산량을 발생시킨다.
  • multi-task 방법을 사용하면 계산량을 증가시켜서 차원의 저주 문제를 일부 해소 시킨다.
• 계산량 문제를 줄이기 위해 RocksDB의 구조를 이용한다.
  • final observed metric = sum of multiple internal components performance. (functional decomposability)
  • 이는 차원을 줄이는 역할도 수행할 수 있다.

3.4.2 Manual clustering

• 복잡도는 차원과 연관있기 때문에 이를 줄이도록 하자.
• 500개의 random configuration trace를 이용하여, IOPS와 517 observable metric간의 correlation과 파라미터간의 correlation을 계산한다.
  • 이를 통해 cluster pool을 30개로 줄였고, 그 중 전문가 지식과 독립된 실험을 통해서 그림의 구조에 도달할 수 있었다.
• parameter space를 decompose했고, 각 parameter cluster에 독립적인 GP를 사용했음
  • ICM Kernel을 사용한 GP로 지식을 공유하도록 했음

3.4.3 Unsupervised clustering

• unsupervised clustering을 적용해서 이러한 cluster를 찾는다.
• pass

4. Evaluation

4.1 Setup

• IOPS를 최대화 하기 위해 10개의 RocksDB 파라미터를 튜닝한다.
• parameter의 범위는 다음 표와 같다.

4.1.1 Experiment goals

• tuner가 수렴 속도가 빠르고, IO throughput을 잘 하는 것이 중요하다.
• Decomposability를 이용하는 cluster 기반의 multi-task의 효율성을 강조할 것이다.

4.1.2 Benchmark

생략

4.1.3 Libraries

생략

4.1.4 Hardware

생략

4.1.5 Baselines

4.2 IOPS performance

• 제한된 계산량으로 IOPS를 최대화 하고 싶기 때문에 100개의 최적화 step만을 부여한다.

• MultiTask를 사용할 때 1.38 ± 0.06 만큼의 성능 향상을 보였다.

4.3 Convergence

• Multi-task와 cluster multi-task가 좀 더 빠르게 찾아냈다.
• clustered MT는 10개의 iteration만에 1.3배의 향상을 보이는 config를 찾았다.(non-cluster-based는 60개의 iter가 걸림)
  • 대신 60 iter 후에는 더 좋은 것들을 찾을 수 있었지만 unstable 함
• 일반 GP보다는 GP(BoTorch)가 더 좋음

5. Related work

pass

6. Conclusion

• 이전에 tuning하는 과정은 고차원이라는 것이 문제였음.
• 따라서 alternative observable metrics와 structural decomposability를 이용해서 수렴 속도를 빠르게 하고, 고차원을 줄임