효율적인 프리페칭(prefetching)은 현대 저장 시스템에서 I/O 지연을 줄이고 캐시 적중률을 향상시키는 데 필수적이며, 특히 어려운 접근 패턴에서 더욱 그러하다. 대부분의 프리페칭 알고리즘에서 시간적 국소성(temporal locality)은 지배적인 기반이 되어 왔지만, 실제 저장 워크로드는 종종 긴 스택 거리(long stack distances, LSD)를 보이며, 여기서 블록은 수백만 번의 다른 접근 이후에야 재사용된다. 이러한 패턴은 강한 공간적 국소성(spatial locality)이 존재하더라도 기존 프리페처의 효과를 약화시킨다. 본 논문에서는 공간적 국소성을 적응적 클러스터링(adaptive clustering)을 통해 활용하는 새로운 프리페칭 프레임워크 CAPSULE(Clustering-Assisted Prefetching Scheme Utilizing Locality Exploration)을 제안한다. CAPSULE은 논리 블록 주소(logical block addresses, LBAs)를 동적으로 그룹화하고 인접 클러스터 전반에 걸쳐 프리페칭을 수행함으로써, 시간적 국소성만을 기반으로 하는 접근법이 남긴 격차를 효과적으로 메운다. 우리는 MSR, CloudPhysics, Tencent CBS, Alibaba Block, Meta Tectonic의 5개 주요 벤치마크 스위트에서 추출한 729개의 실제 워크로드를 대상으로 CAPSULE을 평가하며, 클라우드 스케일 환경의 다양성을 반영한다. CAPSULE은 캐시 적중률을 최대 6.1배 향상시키고, 작업 완료 시간(task completion time)에서 최대 1.89배의 속도 향상을 달성함으로써 전통적 프리페처뿐 아니라 학습 기반 프리페처도 능가한다. 본 연구 결과는 대규모 워킹셋과 시간적 국소성의 침식(temporal locality erosion)이 점차 표준이 되고 있는 현대 클라우드 저장 시스템에 CAPSULE이 특히 잘 적합함을 보여준다.

건너뛰기 목록(skip list)은 현대 데이터베이스 시스템에서 널리 사용되는 대표적인 주기억(in-memory) 인덱스이다. 건너뛰기 목록은 여러 수준의 리스트를 유지하므로 정렬된 데이터를 순회(traversing)하는 데 효율적이다. 또한 트리 기반 구조에서 발생하는 재구성(restructuring) 오버헤드를 피하면서 데이터의 삽입과 삭제에 대해 유연하다. 그러나 기존 건너뛰기 목록 설계에는 상당한 어려움이 있다. 첫째, 연결 리스트(linked list) 구조는 캐시(cache), 파이프라인(pipeline), 그리고 SIMD(Single Instruction Multiple Data) 기능과 같은 마이크로아키텍처 특성을 활용하는 데 한계가 있다. 둘째, 건너뛰기 목록은 새 노드의 레벨(level)을 무작위로 선택한다. 즉, 건너뛰기 목록은 데이터 분포가 아니라 확률에 기반하여 동작하며, 이로 인해 탐색(lookup) 성능이 최적이 아닐 수 있다. 균형 잡힌 트리 구조와 달리, 건너뛰기 목록의 최악의 경우 탐색 성능은 O(n)으로 유지된다. 본 논문에서는 DASL(Deterministic Arrayed Skip List)이라 불리는 새로운 데이터 구조를 제안한다. DASL은 건너뛰기 목록의 알고리즘을 따르면서도 배열(array)과의 통합을 매끄럽게 수행하고, 유연성, 마이크로아키텍처 친화성(microarchitecture-friendliness), 그리고 꼬리 지연(tail latency) 감소를 얻기 위한 새로운 결정론적(deterministic) raise 연산을 고안한다. 구체적으로, DASL의 노드는 단일 원소 대신 다수의 원소를 갖는 배열 구조로 구성되어, 배열을 리스트 구조에 활용한다. 또한 raise 연산은 확률적(probabilistic) 방식이 아니라 결정론적으로 수행되어, 여러 리스트들에서 데이터가 보다 균형 있게 분포되도록 한다. 더 나아가, utilization-based adaptive intra-node search and uneven split operation이라는 두 가지 최적화 기법을 설계하였다. 다양한 합성 및 실제 워크로드에 대한 실험 결과는 DASL이 건너뛰기 목록, B+tree, ART를 포함한 다른 최신 주기억 인덱스들보다 우수한 성능을 보임을 입증한다.

본 논문은 계층형 저장(tiered storage)을 Log-Structured Merge(LSM)-tree에 통합하여 Key–Value Store(KVS)의 성능과 저장 비용 간의 트레이드오프를 균형 있게 조정하는 접근법을 제시한다. 구현은 수직 및 수평 저장 정렬(storage alignment) 전략을 각각 적용하거나 두 전략을 조합하여, LSM-tree 기반 KVS 아키텍처에 계층형 저장을 적용하는 데 중점을 둔다. 또한 이러한 구성들은 키–값(KV) 분리(key–value separation)를 활용하여 성능을 추가로 향상시킨다. 본 실험 결과, 이 접근법은 저장 재정 비용을 절감하는 동시에 쓰기 및 읽기 성능에서의 트레이드오프를 제공함을 확인하였다. 쓰기 집약적 워크로드에서는, 고속 NVMe 솔리드 스테이트 드라이브(SSD)만을 사용하는 접근법에 비해 경쟁력 있는 성능을 달성하면서도 데이터의 96%를 보다 저렴한 SATA SSD에 저장한다. 또한 BlobDB와 견줄 만한 조회(lookup) 성능을 보이며, NVMe SSD에서 RocksDB 대비 범위 질의(range query) 성능을 1.8배 향상시킨다. 종합적으로, 이 접근법은 NVMe SSD에서 RocksDB 및 BlobDB에 비해 저장 재정 비용을 49.5% 감소시킨다. 선택적 KV 분리의 통합은 이러한 개선을 한층 더 진전시키며, LSM-tree 계층형 저장 시스템에서 원격 데이터를 오프로딩(offloading)하는 향후 연구의 기반을 마련한다.

이 논문의 목적은 학습된 인덱스(learned index) 개념에 기반한 SLR(Segmented Linear Regression) 탐색이라는 새로운 탐색 메커니즘을 제안하는 것이다. 본 연구는 선행 연구에서 수집·활용된 대규모 데이터의 상당수가 선형성(linearity) 성질을 가진다는 관찰에 의해 동기를 얻었다. 즉, 키와 그에 저장된 위치가 강한 선형 상관관계를 보인다. 이러한 관찰은 주어진 키로부터 위치를 식별하기 위해 널리 알려진 머신러닝 알고리즘인 선형 회귀(linear regression)에 분할(segmentation)을 적용하는 방식으로 SLR 탐색을 설계하도록 이끌었다. 우리는 예측 정확도와 분할 오버헤드(segmentation overhead) 모두를 고려하여 두 가지 분할 기법, 즉 동일 크기(equal-size)와 오류 인지(error-aware) 기법을 고안하였다. 제안한 방법을 Google의 키-값 저장소인 LevelDB에 구현하고, 탐색 성능을 최대 12.7%까지 향상시킬 수 있음을 검증하였다. 또한 동일 크기 기법은 학습에서의 효율성을 제공하는 반면, 오류 인지 기법은 노이즈가 있는 데이터에 대해 허용 가능함을 확인하였다.

빅데이터의 보급은 데이터의 다양성과 규모 모두에서 두드러진 증가를 초래했다. 그 결과, 두 가지 상이한 기술의 등장과 발전이 촉진되었는데, 바로 비정형 데이터 관리와 데이터 용량 감축이다. Google의 LevelDB와 Meta의 RocksDB와 같은 키–값 저장소는 간단한 키–값 추상화를 통해 다양한 데이터 유형을 처리할 수 있다는 점에서 비정형 데이터를 관리하기 위한 인기 있는 해결책으로 부상했다. 동시에 다수의 데이터 관리 도구들이 Snappy 및 Zstd와 같은 압축 기법을 적극적으로 채택하여 데이터 용량을 효과적으로 줄이고 있다. 본 연구의 목적은 이러한 두 기술이 서로에게 미치는 영향을 탐구하는 것이다. 이를 위해 먼저 압축 기법의 분류를 살펴보고, 특히 현대의 키–값 저장소가 채택한 기법들을 중심으로 각각의 강점과 약점을 논의한다. 또한 키–값 저장소의 특성을 파악하기 위해 배치 쓰기 및 컴팩션(compaction)과 같은 내부 구조와 동작을 조사한다. 다음으로 RocksDB에서 다양한 압축 기법, 블록 크기, 값 크기, 작업 부하(workloads)를 적용하여 압축률과 성능을 정량적으로 평가한다. 평가 결과, 압축은 저장 공간을 절감할 뿐 아니라 컴팩션 오버헤드도 감소시키는 것으로 나타났다. 또한 압축 기법마다 고유의 상충관계가 존재함을 보여주는데, 어떤 기법은 더 나은 압축률을 제공하는 반면 다른 기법은 더 우수한 압축 성능을 산출한다. 본 평가를 바탕으로 추가 연구를 위한 여러 잠재적 연구 방향이 확인되었다. 그 예로 압축을 고려한 컴팩션 메커니즘의 탐색, 선택적 압축, 그리고 압축의 세분성(granularity)을 재검토하는 방안 등이 포함된다.

Learned Index는 기계 학습을 데이터 인덱스 구조에 적용하여 데이터 분포를 학습하고 탐색 성능을 향상시키는 기법이다. 기존 Learned Index는 데이터 분포 변경 시 모델 재학습이 필요해 실시간 업데이트를 지원하지 못하는 한계가 있어, Updatable Learned Index 연구가 활발히 진행되고 있다. 본 논문은 In-place 방식에 집중하며, 이는 인덱스 생성 시 리프 노드에 여유 공간을 미리 할당하고 삽입 데이터를 이 공간에 기록하는 방식으로 동작한다. 이러한 설계는 삽입 성능을 향상시키지만 인덱스 크기를 증가시키는 요인이 된다. ALEX는 공간 효율성을 중시하여 인덱스 크기를 작게 유지하는 반면, LIPP는 더 많은 공간을 사용하여 삽입 성능을 개선하는 구조를 채택한다. 본 연구는 두 인덱스의 구조적 차이를 분석하고, 동일한 인덱스 크기 조건에서 성능을 비교하여 인덱스 크기와 성능 간의 상충관계를 정량적으로 평가한다.

기계 학습 기반의 Learned Index는 전통적 인덱스 기법의 한계를 극복하기 위해 등장했다. 본 논문에서는 읽기 전용 RMI와 수정 가능한 ALEX의 탐색 성능을 분석하고, 오차 보정 과정에서 발생하는 오버헤드를 줄이기 위한 SIMD 기반 최적화 기법을 제안한다. Learned Index는 키의 분포를 학습해 예측과 오차 보정의 두 단계로 탐색을 수행하는데, 오차 보정이 전체 탐색 시간의 최대 80%를 차지할 수 있음이 확인되었다. RMI에서는 오차가 클 때 탐색 범위를 빠르게 줄이는 SIMD Branchless Binary Search, 작을 때 모델 예측 기반의 SIMD Linear Search가 효과적이었다. 반면, ALEX는 일정한 오차 범위를 유지하는 특성으로 인해 단순한 SIMD Linear Search가 가장 효율적이었다. 이를 통해 데이터셋의 오차 범위, 인덱스 크기 및 밀도에 따라 적절한 탐색 알고리즘을 선택하는 것이 성능 최적화에 중요함을 제시한다.

키의 분포를 색인 구조에 내장함으로써, 학습형 인덱스는 인덱스 크기를 최소화하고 조회 성능을 최대화할 수 있다. 그러나 현재의 학습형 인덱스가 직면한 문제 중 하나는 인덱스 구축 시간이 길다는 점이다. 기존의 학습형 인덱스는 전체 데이터셋을 완전히 순회해야 하므로, 전통적인 인덱스에 비해 실용성이 떨어진다. 본 논문은 학습형 인덱스를 실용적으로 만들기 위해 구축 시간의 효율성을 문제 삼는다. 구축 시간 효율적인 학습형 인덱스를 위한 우리의 접근은 샘플링 학습을 활용하는 것이다. 본 논문에서는 오차 경계를 만족하는 두 가지 샘플링 방식인 Sample EB-PLA와 Sample EB-Histogram을 제시한다. 샘플링이라는 개념은 단순하지만, 이를 실용적으로 만들기 위해 고려해야 할 사항들이 여러 가지 존재한다. 예를 들어 샘플링 간격, 오차 경계(오차 허용성), 인덱스 하이퍼파라미터는 서로 연관되어 있으며, 구축 시간, 인덱스 크기, 정확도 및 조회 지연 사이에 복잡한 트레이드오프를 형성한다. 여섯 개의 실제 데이터셋에 대한 광범위한 실험을 통해, 우리의 샘플링 방식은 인덱스 구축 시간을 한 자릿수(orders of magnitude) 수준으로 효율적으로 줄일 수 있음을 보인다. 결과는 샘플링이 구축 시간뿐 아니라 조회 성능 및 인덱스 크기를 포함하여 학습형 인덱스의 설계 공간을 확장함을 보여준다. 우리의 파레토 분석은 샘플링을 통해 학습형 인덱스를 전통적인 인덱스보다 더 효율적으로 구축할 수 있음을 시사한다.

빅데이터의 출현은 데이터의 다양성과 규모 모두에서 유의미한 증가를 동반하였고, 이에 따라 더 빠르고 신뢰할 수 있는 저장 솔루션의 개발이 촉진되었다. 본 연구의 주요 목적은 다양한 저장 매체의 지연(latency) 차이가 RocksDB의 대표적인 KVS 성능에 미치는 영향을 조사하고, 하위 레벨에서 저비용 저장 매체를 활용하는 것이 효율적인 공간 활용과 비용 절감으로 이어질 수 있는지 확인하는 데 있다. 우리는 다양한 구성을 사용하는 데 따른 트레이드오프를 분석하기 위해 RocksDB에 계층형(티어드) SSD 저장을 구현하였다. 분석 결과, 지연의 차이가 존재함에도 불구하고 RocksDB는 지연 변동의 영향을 완화하는 데 있어 두드러진 회복탄력성을 보였다. 또한 더 나은 저장 활용을 도모하기 위해, 계층형 저장에서 서로 다른 압축 기법을 그 특성을 고려하여 활용함으로써 RocksDB의 유연성을 적극 활용하였다. 그 결과, 본 전략은 Optane SSD의 성능을 극복하지는 못하나, 쓰기 및 읽기 처리량(write and read throughput) 측면에서 NVMe SSD와의 차이가 미미한 것으로 나타났다. 하이브리드 압축(hybrid compression)을 SATA SSD와 비교했을 때, 계층형 저장은 쓰기 워크로드에서 13.8 MBps, 읽기 워크로드에서 3.86 MBps의 차이를 보였다. 또한 이는 SATA SSD와 유사한 수준의 비용으로, 성능은 NVMe SSD와 견줄 만한 비용 효율적인 저장 옵션을 제공한다. 본 연구는 데이터베이스 효율성을 유지하면서 저장 인프라를 최적화하고 저장 업그레이드 비용을 절감하려는 조직에 유용한 지침을 제공한다.

효율적인 프리페칭(prefetching)은 현대 저장 시스템에서 I/O 지연을 줄이고 캐시 적중률을 향상시키는 데 필수적이며, 특히 어려운 접근 패턴에서 더욱 그러하다. 대부분의 프리페칭 알고리즘에서 시간적 국소성(temporal locality)은 지배적인 기반이 되어 왔지만, 실제 저장 워크로드는 종종 긴 스택 거리(long stack distances, LSD)를 보이며, 여기서 블록은 수백만 번의 다른 접근 이후에야 재사용된다. 이러한 패턴은 강한 공간적 국소성(spatial locality)이 존재하더라도 기존 프리페처의 효과를 약화시킨다. 본 논문에서는 공간적 국소성을 적응적 클러스터링(adaptive clustering)을 통해 활용하는 새로운 프리페칭 프레임워크 CAPSULE(Clustering-Assisted Prefetching Scheme Utilizing Locality Exploration)을 제안한다. CAPSULE은 논리 블록 주소(logical block addresses, LBAs)를 동적으로 그룹화하고 인접 클러스터 전반에 걸쳐 프리페칭을 수행함으로써, 시간적 국소성만을 기반으로 하는 접근법이 남긴 격차를 효과적으로 메운다. 우리는 MSR, CloudPhysics, Tencent CBS, Alibaba Block, Meta Tectonic의 5개 주요 벤치마크 스위트에서 추출한 729개의 실제 워크로드를 대상으로 CAPSULE을 평가하며, 클라우드 스케일 환경의 다양성을 반영한다. CAPSULE은 캐시 적중률을 최대 6.1배 향상시키고, 작업 완료 시간(task completion time)에서 최대 1.89배의 속도 향상을 달성함으로써 전통적 프리페처뿐 아니라 학습 기반 프리페처도 능가한다. 본 연구 결과는 대규모 워킹셋과 시간적 국소성의 침식(temporal locality erosion)이 점차 표준이 되고 있는 현대 클라우드 저장 시스템에 CAPSULE이 특히 잘 적합함을 보여준다.

건너뛰기 목록(skip list)은 현대 데이터베이스 시스템에서 널리 사용되는 대표적인 주기억(in-memory) 인덱스이다. 건너뛰기 목록은 여러 수준의 리스트를 유지하므로 정렬된 데이터를 순회(traversing)하는 데 효율적이다. 또한 트리 기반 구조에서 발생하는 재구성(restructuring) 오버헤드를 피하면서 데이터의 삽입과 삭제에 대해 유연하다. 그러나 기존 건너뛰기 목록 설계에는 상당한 어려움이 있다. 첫째, 연결 리스트(linked list) 구조는 캐시(cache), 파이프라인(pipeline), 그리고 SIMD(Single Instruction Multiple Data) 기능과 같은 마이크로아키텍처 특성을 활용하는 데 한계가 있다. 둘째, 건너뛰기 목록은 새 노드의 레벨(level)을 무작위로 선택한다. 즉, 건너뛰기 목록은 데이터 분포가 아니라 확률에 기반하여 동작하며, 이로 인해 탐색(lookup) 성능이 최적이 아닐 수 있다. 균형 잡힌 트리 구조와 달리, 건너뛰기 목록의 최악의 경우 탐색 성능은 O(n)으로 유지된다. 본 논문에서는 DASL(Deterministic Arrayed Skip List)이라 불리는 새로운 데이터 구조를 제안한다. DASL은 건너뛰기 목록의 알고리즘을 따르면서도 배열(array)과의 통합을 매끄럽게 수행하고, 유연성, 마이크로아키텍처 친화성(microarchitecture-friendliness), 그리고 꼬리 지연(tail latency) 감소를 얻기 위한 새로운 결정론적(deterministic) raise 연산을 고안한다. 구체적으로, DASL의 노드는 단일 원소 대신 다수의 원소를 갖는 배열 구조로 구성되어, 배열을 리스트 구조에 활용한다. 또한 raise 연산은 확률적(probabilistic) 방식이 아니라 결정론적으로 수행되어, 여러 리스트들에서 데이터가 보다 균형 있게 분포되도록 한다. 더 나아가, utilization-based adaptive intra-node search and uneven split operation이라는 두 가지 최적화 기법을 설계하였다. 다양한 합성 및 실제 워크로드에 대한 실험 결과는 DASL이 건너뛰기 목록, B+tree, ART를 포함한 다른 최신 주기억 인덱스들보다 우수한 성능을 보임을 입증한다.

본 논문은 계층형 저장(tiered storage)을 Log-Structured Merge(LSM)-tree에 통합하여 Key–Value Store(KVS)의 성능과 저장 비용 간의 트레이드오프를 균형 있게 조정하는 접근법을 제시한다. 구현은 수직 및 수평 저장 정렬(storage alignment) 전략을 각각 적용하거나 두 전략을 조합하여, LSM-tree 기반 KVS 아키텍처에 계층형 저장을 적용하는 데 중점을 둔다. 또한 이러한 구성들은 키–값(KV) 분리(key–value separation)를 활용하여 성능을 추가로 향상시킨다. 본 실험 결과, 이 접근법은 저장 재정 비용을 절감하는 동시에 쓰기 및 읽기 성능에서의 트레이드오프를 제공함을 확인하였다. 쓰기 집약적 워크로드에서는, 고속 NVMe 솔리드 스테이트 드라이브(SSD)만을 사용하는 접근법에 비해 경쟁력 있는 성능을 달성하면서도 데이터의 96%를 보다 저렴한 SATA SSD에 저장한다. 또한 BlobDB와 견줄 만한 조회(lookup) 성능을 보이며, NVMe SSD에서 RocksDB 대비 범위 질의(range query) 성능을 1.8배 향상시킨다. 종합적으로, 이 접근법은 NVMe SSD에서 RocksDB 및 BlobDB에 비해 저장 재정 비용을 49.5% 감소시킨다. 선택적 KV 분리의 통합은 이러한 개선을 한층 더 진전시키며, LSM-tree 계층형 저장 시스템에서 원격 데이터를 오프로딩(offloading)하는 향후 연구의 기반을 마련한다.

이 논문의 목적은 학습된 인덱스(learned index) 개념에 기반한 SLR(Segmented Linear Regression) 탐색이라는 새로운 탐색 메커니즘을 제안하는 것이다. 본 연구는 선행 연구에서 수집·활용된 대규모 데이터의 상당수가 선형성(linearity) 성질을 가진다는 관찰에 의해 동기를 얻었다. 즉, 키와 그에 저장된 위치가 강한 선형 상관관계를 보인다. 이러한 관찰은 주어진 키로부터 위치를 식별하기 위해 널리 알려진 머신러닝 알고리즘인 선형 회귀(linear regression)에 분할(segmentation)을 적용하는 방식으로 SLR 탐색을 설계하도록 이끌었다. 우리는 예측 정확도와 분할 오버헤드(segmentation overhead) 모두를 고려하여 두 가지 분할 기법, 즉 동일 크기(equal-size)와 오류 인지(error-aware) 기법을 고안하였다. 제안한 방법을 Google의 키-값 저장소인 LevelDB에 구현하고, 탐색 성능을 최대 12.7%까지 향상시킬 수 있음을 검증하였다. 또한 동일 크기 기법은 학습에서의 효율성을 제공하는 반면, 오류 인지 기법은 노이즈가 있는 데이터에 대해 허용 가능함을 확인하였다.