Dostoevsky, LSM-tree의 불필요한 병합을 제거해 더 나은 시공간 트레이드오프를 제공하다

Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores [pdf]

LSM-tree 기반 키-값 저장소는 업데이트 I/O 비용과 조회 I/O 비용 및 저장 공간 사이에서 최적이 아닌 트레이드오프를 수행한다. 그 이유는 조회가 확인해야 할 run 수를 제한하고 오래된 항목을 제거하기 위해 모든 레벨에서 동일하게 비용이 많이 드는 병합을 수행하기 때문이다. Harvard의 Niv Dayan과 Stratos Idreos는 가장 큰 레벨을 제외한 모든 레벨에서 병합을 제거하는 Lazy Leveling과 전체 설계 공간을 아우르는 Fluid LSM-tree를 도입하고, 이를 기반으로 워크로드와 하드웨어에 따라 적응적으로 병합을 제거하는 Dostoevsky를 제안한다. RocksDB에 구현된 Dostoevsky는 최신 설계보다 성능과 저장 공간 모두에서 우수하다.