건너뛰기 목록(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를 포함한 다른 최신 주기억 인덱스들보다 우수한 성능을 보임을 입증한다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.