성능과 확장성을 극대화하기 위한 SingleStore의 Skiplist 인덱스

 

관계형 데이터베이스에서 인덱싱에 사용되는 가장 널리 사용되는 데이터구조는 B-Tree (또는 그 변형인 B+Tree)입니다. B-Tree는 다른 여러 balanced tree들에 비해 조회를 위한 디스크 I/O 작업이 적기 때문에 인기가 높습니다. SingleStore는 상용 관계형 데이터베이스로서 최초로 B-Tree가 아닌 Skiplist를 In-Memory Rowstore데이터의 기본 인덱스 데이터구조(backing-data structure)로 사용합니다.

 

2011년에 설립된 SingleStore는 In-Memory Rowstore 데이터베이스로 시작되었습니다. SingleStore의 스토리지 설계는 다음 몇 년 동안 디스크 저장소 데이터를 Columnstore 형식으로 지원하도록 발전했습니다. Universal Storage 프로젝트를 통해 행이 메모리와 디스크 및 Rowstore 또는 Columnstore 형식으로 저장될 때 더 많은 지능이 추가되었습니다. 이 모든 과정에서 Skiplist는 In-Memory Rowstore데이터를 위한 인덱스로 채택되었습니다.

 

많은 연구와 프로토타입이 Skiplist를 사용하기로 결정했습니다. 이 선택에 대한 근거를 제시하고, SingleStore의 Skiplist 구현의 강력함과 상대적 단순성을 보여주기를 바랍니다. 매우 기본적인 데모로 MySQL에 비해 SingleStore에서 8배 이상 빠르게 실행되는 매우 간단한 단일 Thread 테이블 스캔을 비교해 보여 드리겠습니다. (SingleStore는 보다 공격적이고 복잡한 워크로드에서 이보다 훨씬 우수한 성능을 제공합니다). 이 글은 높은 수준에서의 디자인 채택에 대해서만 논하였고, 대부분의 핵심 구현 세부사항은 다른 게시물에 남겼습니다.

 

 

Skiplist란 무엇입니까?

 

B-Trees는 데이터가 디스크에서 대부분의 수명을 유지하고 쿼리를 실행하는데 필요한 만큼만 메모리로 가져와 캐시될 때 데이터베이스에 적합합니다. 반면, B-Trees는 데이터가 메모리에 적재될 때 불필요한 오버헤드인 디스크 I/O를 줄이기 위해 추가 작업을 수행합니다. 메모리 크기가 증가함에 따라 오늘날 In-Memory 데이터에 대해서만 잘 작동하는 인덱스의 지원이 실현 가능해졌고, 디스크에서 데이터를 인덱싱해야 하는 제약으로부터 해방되었습니다. Skiplist는 이러한 유형의 인덱싱에 적합합니다.

 

Skiplist는 비교적 최근에 발명되었습니다. Skiplist의 선구적 논문(seminal paper)은 1990년 윌리엄 푸(William Pugh)에 의해 출판되었습니다."Skiplists: balanced tree들에 대한 확률론적 대안(Skiplists: a probabilistic alternative to balanced trees)". 이로 인해 Skiplist는 1970년대에 처음 제안된 B-Tree보다 약 20년 더 젊습니다.

 

Skiplist는 조회(lookup), 삽입(insertion), 삭제(deletion) 복잡도(complexity)가 O(Log(n))로 예상되는 정렬된 데이터 구조입니다. B-Tree, Redblack Tree 또는 AVL Tree에서 요구하는 복잡한 Tree 밸런싱 또는 페이지 분할이 필요 없이 이 수준의 효율을 제공합니다. 그 결과 구현하기가 훨씬 간단하고 간결한 데이터 구조입니다.

 

Lock-Free Skiplist 구현은 최근에 개발되었습니다. Mikhail Fomitchev와 Eric Ruppert가 2004년에 발표한 문서인 Lock-Free Linked Lists and Skiplists를 참조하시기 바랍니다. 이러한 구현은 잠금(Lock)이 필요한 Thread-safe B-Tree보다 동시 읽기/쓰기 워크로드에서 더 나은 병렬처리로 Thread-safe를 제공합니다. 여기서는 Lock-Free Skiplist를 구현하는 방법에 대한 자세한 내용을 다루지 않지만, 어떻게 수행되는지에 대한 아이디어를 얻으려면 Lock-Free 알고리즘 작성의 일반적인 함정(common pitfalls in writing Lock-Free algorithms), 이 블로그 게시물을 참조하시기 바랍니다.

 

Skiplist는 tower들에 붙어 있는 element들로 구성됩니다. Skiplist의 각 tower는 각 tower 레벨에서 동일한 높이의 다음 tower에 연결되어 Skiplist의 각 레벨마다 하나씩 Linked-list 그룹을 형성합니다. element가 Skiplist에 insert되면, 연속적인 코인플립(동전던지기)을 통해 tower 높이가 무작위로 결정됩니다.(높이 n의 tower는 2^n 번에 한 번 발생).

높이가 결정되면 element는 Skiplist의 각 레벨에서 Linked-list에 연결됩니다. tower는 가장 높은 tower에서 시작하여 맨 아래로 작업함으로써 이진검색을 지원합니다. tower 링크를 사용하여 언제 목록에서 앞으로 가야 할지 또는 tower 아래로 이동해야 할지를 확인합니다.

 

 

SingleStore를 위해 Skiplist 인덱스가 필요한 이유

 

Skiplist가 SingleStore에 가장 적합한 이유는 여러 가지가 있습니다. 메모리가 최적화되고 단순하며 (적은 라인의 코드로도 구현 가능), Lock-Free 방식으로 빠르고 유연하게 구현할 수 있기 때문입니다.

 

1) Memory-optimized

SingleStore는 Rowstore 및 Columnstore 테이블 저장소를 모두 지원합니다. Rowstore는 메모리에 저장된 데이터에 고속으로 빠르게 액세스할 수 있도록 설계되었습니다. Columnstore는 많은 양의 데이터를 빠르게 스캔하고 집계하기 위해 설계되었습니다. Columnstore는 디스크로 저장되지만 최근 작성된 데이터는 Columnstore 형식의 디스크에 저장하기 전에 Rowstore 형식으로 계속 저장됩니다.

또한, Columnstore는 파일에 대한 모든 메타데이터를 In-Memory Rowstore 메타데이터 테이블 (예 : 각 열의 최대/최소값, 삭제된 행의 비트맵과 같은 메타데이터)에 저장합니다. 이 데이터는 쿼리 실행 시 필터에서 전체 파일에 대한 엑세스를 없애고 빠르고 쉽게 액세스하기 위해 사용됩니다. Columnstore에대한 자세한 내용은 설명서를 참조하시기 바랍니다.

이 두 가지 스토리지 유형은SingleStore Universal Storage프로젝트에 의해 수렴되었습니다. 두 테이블 유형의 이점을 최대한 활용하여 스토리지 설계를 작성하는 동시에 애플리케이션 설계 및 관리 시에 스토리지 선택의 세부 사항을 고려할 필요가 없습니다. 따라서 향후 SingleStore 테이블 형식의 이상적인 디자인과 마찬가지로 SingleStore의두 가지 테이블 형식 모두 메모리에 최적화된 Rowstore 인덱스가 필요합니다. (참조 : Eric Hanson(에릭핸슨)의 a deep dive on SingleStore, Rick Negrin(릭 니그린)의 웹비나 our current and future implementation of SingleStore)

메모리에 최적화되었다는 것은 인덱스가 indirection할 필요 없이 행의 포인터를 자유롭게 사용할 수 있음을 의미합니다. 기존 데이터베이스에서는 디스크가 기본 스토리지이므로 메모리에 대한 포인터 이외의 다른 방법으로 행을 처리할 수 ​​있어야 합니다. 이 indirection은 일반적으로 특정 행의 메모리 내 주소를 찾거나 필요한 경우 디스크에서 메모리로 읽어 들이기 위해 참조되는 메모리 상주 페이지(버퍼풀이라고도 함)의 캐시 형태를 취합니다.

이 indirection 비용은 비싸고 일반적으로 페이지 레벨(예 : SQL Server에서 한 번에 8K)에서 수행됩니다. SingleStore는이 오버헤드가 없습니다. 이것은 Skiplist처럼 포인터에 의해 임의로 행을 참조하는 데이터구조를 가능하게 합니다. 포인터의 indirection은 버퍼풀에서 페이지를 찾는 것보다 훨씬 저렴합니다.

 

2) Simple

SingleStore의skiplist 구현은 주석을 포함하여 약 1500 줄의 코드입니다. 최근에 SQL Server 및 Innodb의 B-Tree 구현은 코드가 50배에 가깝고, 파트의 이동도 더 많습니다. 예를 들어, B-Tree는 페이지 분할 및 페이지 압축을 처리해야 하지만, Skiplist는 이 같은 작업이 없습니다. 일반적으로 사용 가능한 첫 번째 SingleStore 빌드는빌드 및 안정화에 1년이 조금 넘게 걸렸습니다. 보다 복잡한 인덱싱 데이터구조로는 이러한 위업을 달성할 수 없었을 것입니다.

 

3) Lock-Free

Lock-Free 또는 Non-block 알고리즘은 모든 Thread의 실행이 OS에 의해 인터리브(Interleave)되는 방식에 관계없이 일부 Thread가 항상 진행될 수 있는 알고리즘입니다. SingleStore는많은 코어가 있는 하드웨어에서 실행되는 고도의 동시 워크로드 지원을 위해 설계되었습니다. 이러한 목표는 SingleStore를위한 Lock-Free 알고리즘들을 가치있게 만듭니다. (참조 : 블로그 our original blog post on Lock-Free algorithms및 글 our description of sync replicationby Nate Horan.)

Thread-safe하고 Lock-Free한 Skiplist를 작성하는 알고리즘은 이제 학계에서 해결된 문제입니다. 지난 10년 동안이 주제에 관한 많은 논문이 발표되었습니다. 경합이 적을 때 (즉, 다른 동시 작업이 실행되지 않고 전체 Skiplist을 반복하는 단일 Thread) Lock-Free Skiplist의 성능을 향상시키는 것이 훨씬 어렵습니다. 이 사례를 최적화하는 것이 보다 활발한 연구 분야입니다. 이 특정 문제를 해결하는 것은 우리의 차기 과제입니다.

반면에 B-Tree는 Thread-safe를 달성하기 위해 복잡한 잠금장치를 사용해야 했습니다. 이 문제를 피하기 위해 BWtree와 같은 일부 최신 Lock-Free B-Tree와 유사한 데이터구조가 최근 제안되었습니다. 다시, BWTree 데이터구조의 복잡성은 Skiplist 또는 심지어 전통적인 B-Tree의 복잡성을 훨씬 능가합니다. BWTree는 B-Tree보다 더 복잡한 압축 알고리즘이 필요하며 해당 페이지를 유지하기 위해 로그-구조 스토리지(log-structured storage) 시스템에 의존합니다. Skiplist의 단순성은 Lock-Free 구현에 적합합니다.

 

4) Fast

Skiplist의 속도는 대부분 단순성에서 비롯됩니다. SingleStore는다른 데이터베이스에 비해 삽입(insert), 삭제(delete), 검색(search), 또는 반복(iterate)하는 명령(instruction)이 적습니다.

 

5) Flexible

Skiplist는 또한 쿼리 처리에 유용하고 Balanced-tree에서 쉽게 구현할 수 없는 몇 가지 추가 작업을 지원합니다.

예를 들어, Skiplist는 두 element 사이의 element 수를 로그(대수) 시간으로 추정할 수 있습니다. 일반적인 생각은 tower를 사용하여 Tree에서 동일한 높이로 서로 연결된 두 element 사이에 몇 개의 행이 있는지 추정하는 것입니다. 노드가 연결된 tower 높이를 알면 해당 높이에서 예상되는 tower 분포를 알기 때문에 이러한 element 사이에 몇 개의 element가 있을 것으로 예상되는지 추정할 수 있습니다.

select 문에서 선택적인 다른 필터의 수를 계산할 때 임의의 목록 범위에 있을 것으로 예상되는 element 수를 아는 것은 쿼리 최적화에 매우 유용합니다. 기존 데이터베이스는 쿼리 최적화 프로그램에서 이러한 유형의 추정을 지원하기 위해 별도의 히스토그램을 작성해야 합니다.

 

 

Skiplist에 대한 몇 가지 일반적인 문제 해결

 

SingleStore는메모리 오버헤드, CPU 캐시 효율성 및 역 반복(reverse iteration)과 같은 Skiplist 목록에 대한 몇 가지 일반적인 문제를 해결했습니다.

 

메모리 오버헤드

Skiplist의 가장 잘 알려진 단점은 메모리 오버헤드입니다. Skiplist tower는 각 tower의 각 레벨에 포인터를 저장해야 합니다. 평균적으로, 각 element는 tower 높이가 2입니다. 즉, 각 element는 Skiplist tower에 대해 평균 16바이트의 오버헤드를 갖습니다.

이 오버헤드가 차지하는 비중은 목록에 저장되는 element의 크기에 따라 다릅니다. SingleStore에서저장된 element는 일부 사용자 테이블의 행입니다. 관계형 데이터베이스의 평균 행 크기는 수백 바이트인 경향이 있어 Skiplist의 메모리 오버헤드 비중은 약화됩니다.

B-Tree에는 자체 메모리 오버헤드 문제가 있어 Skiplist와 직접 비교하기 어렵습니다. B-Tree가 페이지 분할을 수행한 후 두 분할 페이지는 일반적으로 50%만 채워집니다. (일부 데이터베이스에는 다른 휴리스틱(heuristics 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있는 어림짐작의 방법)이 있지만 분할의 결과는 빈 공간이 있는 페이지입니다.)

워크로드의 쓰기 패턴에 따라 B-Tree는 이러한 분할로 인해 B-Tree 전체에서 조각난 페이지로 끝날 수 있습니다. 이 낭비된 공간을 되찾기 위한 압축 알고리즘이 필요하지만 종종 사용자가 수동으로 트리거 해야 합니다. 그러나 완전히 압축된 B-Tree는 Skiplist보다 메모리 효율성이 높습니다.

SingleStore가기존 데이터베이스와 비교하여 메모리 사용을 개선할 수 있는 또 다른 방법은 보조 인덱스를 구현하는 방법입니다. 보조 인덱스에는 기본키(PK) 행에 대한 포인터만 있으면 됩니다. 보조 B-Tree 인덱스처럼 키 열에 데이터를 복제할 필요가 없습니다.

 

CPU 캐시 효율성

Skiplist는 검색 중에 포인터를 순회하면 메모리에서 무작위로 점프할 수 있기 때문에 메모리 위치가 그리 좋지 않습니다. 이 효과의 영향은 작업 부하에 따라 다르며 정확하게 측정하기가 어렵습니다.

대부분의 쿼리에서 나머지 쿼리를 실행하는 비용(정렬, 수식 실행, 쿼리 결과를 반환하기 위한 프로토콜 오버헤드)은 검색 중에 tower 포인터를 통과하는 비용을 지배합니다. 메모리 지역성(memory locality: 메모리에서 읽기가 동일한 위치를 반복적으로 요청하거나 이전 요청 근처의 메모리 위치를 요청하는 경향) 문제는 대부분 프리페치 명령(Intel 프로세서의 mm_prefetch)을 사용하여 극복할 수 있습니다. Skiplist tower는 테이블 스캔 작업 전에 미리 읽고 행을 CPU 캐시에 로드하는데 사용될 수 있어, 그것이 끝나면 스캔에 의해 빠르게 액세스할 수 있습니다.

 

역 반복(Reverse Iteration)

대부분의 skiplist 구현은 역방향 포인터 (목록 element의 이중 링크)를 사용하여 목록에서 역방향 반복을 지원합니다. 역방향 포인터는 메모리 오버헤드와 구현 복잡성을 늘립니다. Lock-Free Double-Linked-list는 구현하기가 어렵습니다.

SingleStore의Skiplist는 tower를 사용하여 역 링크 없이 뒤로 반복하는 새로운 역 반복자(Reverse iterator)를 사용합니다. 아이디어는 Skiplist의 끝 또는 특정 노드를 찾는 동안 Skiplist의 각 레벨에서 방문한 마지막 tower 링크를 추적하는 것입니다. 역 반복자(Reverse iterator)가 뒤로 이동할 때마다 사용되는 각 레벨에서 링크를 업데이트하기 때문에 이 링크를 사용하여 각 연속 element 뒤에 있는 element를 찾을 수 있습니다.

이 반복자(iterator)는 역방향 포인터에 필요한 메모리를 절약하지만, 역 반복(reverse-iteration) 실행 비용이 더 높습니다. ORDER BY가 인덱스가 제공하는 순서와 반대인 정렬 순서(즉, 내림차순이 아닌 오름차순)를 원하더라도 ORDER BY로 정렬하지 않고 실행할 수 있으므로, SQL 데이터베이스의 경우 역 반복(reverse-iteration)이 중요합니다.

 

 

성능 비교

 

데이터베이스 및 데이터구조의 성능 벤치마킹은 매우 어렵습니다. 여기서 포괄적인 벤치마크를 제공하지 않겠습니다. 대신, innodb의 B-Tree와 비교하여 Skiplist의 단일 Thread 스캔 성능에 대한 간단한 데모를 보여 드리겠습니다.

5천만 행 이상의 사용자 테이블 상에 SELECT SUM(score) FROM users 을 실행합니다. 테스트는 MySQL을 선호되는 설정으로 설치되었습니다. 이 데모에는 (SingleStore가탁월한) 동시 쓰기 워크로드가 없으며 SingleStore는쿼리 병렬 처리가 비활성화된 상태로 실행됩니다. MySQL과 SingleStore모두 단일 Thread만 사용하여 스캔합니다. Innodb는 전체 테이블을 메모리에 맞추기에 충분한 버퍼 풀로 실행 중이므로 디스크 I/O는 없습니다.

CREATE TABLE `users` ( `user_id` bigint(20) NOT NULL AUTO_INCREMENT, `first_name` varchar(100) CHARACTER SET utf8, `last_name` varchar(100) CHARACTER SET utf8, `install_date` datetime, `comment` varchar(500), `score` bigint(20), PRIMARY KEY (`user_id`) )

 

 

SingleStore의단일 Thread 스캔 성능은 첫 번째 경우 5배, 두 번째 경우에는 8배 더 빠릅니다. SingleStore는위에서 논의한 이유로 행을 읽기 위해 훨씬 적은 CPU 명령(instruction)을 실행합니다. 동시 쓰기와 동시 사용자 수가 많을 때 SingleStore의장점은 실제로 부각됩니다.

 

 

결론

 

SingleStore는In-Memory Rowstore 인덱싱을 위해 Lock-Free Skiplist의 단순성과 성능을 활용합니다. 이 인덱스는 Rowstore 테이블을 백업하고 Columnstore 테이블에 대한 메모리의 행을 버퍼링하고 디스크상의 Columnstore Blob 파일에 대한 메타데이터를 저장하는데 사용됩니다. 그 결과 최근의 데이터구조 개발 및 Lock-Free/Non-block 알고리즘 연구를 기반으로 보다 현대적인 인덱싱 설계가 이루어졌습니다. Skiplist의 단순성은 많은 SingleStore의속도와 확장성의 원천입니다.

 

 

December 17, 2019

 

 

---

https://www.singlestore.com/blog/what-is-skiplist-why-skiplist-index-for-memsql/

 

What is Skiplist & Why a Skiplist Index for MemSQL - SingleStore Blog - MemSQL is Now SingleStore

A skiplist is an ordered data structure providing expected O(Log(n)) lookup, insertion and deletion complexity. Learn more!

www.singlestore.com

 

 

 

※www.a-platform.biz| info@a-platform.biz