earticle

영어

The Skip list is a probabilistic data structure, being an essential component that manages in-memory key-value pairs in a key-value store such as RocksDB. This paper presents a methodology for analyzing behaviors of the skip list structure and several analysis results. Our methodology consists of not only basic functionalities including workload generation with diverse patterns and measurement, but also extended ones including consistent comparisons required in a probabilistic structure, enhanced measurement precision, and CPU microarchitecture consideration. Analysis results using our methodology reveal that the search overhead of the skip list depends on both the location of a key-value pair in the structure and the total size of workload. In addition, the overhead is affected by reference patterns. Specifically a CPU cache friendly pattern, Zipfian pattern, shows better performance than others, which implies that CPU microarchitecture such as cache and TLB (Translation Lookaside Buffer) give a substantial impact on the performance of the skip list structure.

한국어

Skip list는 확률적인 자료 구조로써 RocksDB와 같은 키-밸류 스토어에서 메모리상에 존재하는 키-밸류 쌍을 관 리하는 핵심 구성 요소로 사용된다. 이 논문에서는 skip list를 분석하기 위한 방법론과 이를 활용한 분석 결과를 제시한다. 제시한 방법론은 다양한 패턴의 워크로드(workload) 생성과 측정이라는 기본 기능뿐만 아니라 확률적 자료 구조에서 필요한 일관된 비교 방법, 시간 측정의 정밀도 향상, CPU 내부 마이크로아키텍처 고려 등과 같은 확장 기능으로 구성된다. 제안된 방법론을 이용한 실험 결과 skip list의 검색 부하는 키-밸류 쌍의 구조상에서 위 치와 워크로드 크기에 의존하는 것으로 분석되었다. 이뿐만 아니라 검색 부하는 참조 패턴에도 영향을 받았다. 구체 적으로 Zipfian 패턴과 같은 CPU 캐시(cache) 친화적인 패턴은 다른 패턴에 비해 더 좋은 성능을 보였으며, 이것 은 skip list의 검색 부하가 캐시나 TLB (Translation Lookaside Buffer) 같은 CPU 내부의 마이크로아키텍처 영향도 받는 것을 의미한다.