Earticle

초록

한국어

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

영어

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.

목차

요약
Abstract
1. 서론
2. 관련 연구
2.1 Skip List 자료 구조
2.2 RocksDB
3. Skip list 시간 측정 및 분석 방법론
3.1 Skip list 시간 측정을 위한 고정된 구조 생성
3.2 시간 측정 신뢰성
4. 실험 결과
4.1 실험 환경
4.2 검색 패턴에 따른 Skip list 응답 시간
4.3 응답 시간 분포 및 데이터셋 크기에 따른 영향
4.4 Skip list 노드 수에 따른 영향
4.5 Skip list 검색 응답 시간 수식화
5. 결론
Acknowledgements
참고문헌

저자

• 신호진 [ Hojin Shin | 단국대학교 컴퓨터공학과 ]
• 유시환 [ Seehwan Yoo | 단국대학교 컴퓨터공학과 ]
• 최종무 [ Jongmoo Choi | 단국대학교 컴퓨터공학과 ] 교신저자

참고문헌