scalalang2

NVMe SSD의 등장이 키-밸류 데이터베이스 성능에 미칠 영향에 관하여

이번 포스팅에서는 NVMe SSD환경에서 대표적인 키-밸류 데이터베이스인 LevelDB의 성능을 높이기 위해 어떤 설계를 할 수 있는지 소개하려고 한다. 이더리움과 비트코인은 그 자체로 분산 데이터베이스이지만 내부적으로는 LevelDB를 이용하고 있다. 이번 포스팅에서는 블록체인의 단일 노드의 트랜잭션 처리량을 높이는 방법을 탐구하고자 LevelDB 자체의 성능을 높이는 방법에 대해 서술하고 이것이 블록체인에 미칠 영향에 대해 소개한다.

이번 포스팅에서는 먼저 LevelDB의 주요 자료구조인 LSM을 소개하고 그리고 HDD에서 NVMe SSD로 오기까지 주요 변화와 NVMe SSD 환경에서 LevelDB의 성능을 개선한 KVell 데이터베이스[1]를 소개하고 마지막으로는 이 변화가 블록체인의 성능과 어떤 상관 관계가 있는지 탐구하는 순서로 기술한다.

구성

Log-Structured Merge Tree (LSM)

구글에서 개발한 Level-DB는 내부적으로는 Log-Structured Merge Tree(이하 LSM)구조로 이루어져 있다. LSM은 저장-집중형 데이터베이스에서 자주 쓰이는데 실시간으로 저장 하는 데이터가 많은 경우 사용하는 목적으로 설계되어 있기 때문에 쓰기에 대해서 O(1)로 굉장히 빠른 속도를 가지고 있다. 반면 탐색은 O(n)으로 매우 느리다. 아래 [그림 1]은 Level-DB의 대략적인 구조를 보여준다.

[그림 1] Level-DB의 LSM 트리 구조

Level-DB는 아래와 같은 순서와 원리에 의해 동작한다.

지금까지 조금 길게 Level-DB에 대해서 설명하였는데 다음으로는 HDD, SATA SSD, NVMe SSD 순서로 저장장치가 발전하면서 어떤 차이점이 있고 성능 차이가 얼마나 나는지 간단하게 소개하려고 한다. 본 포스팅에서 설명하는 Level-DB는 이 링크의 자료를 많이 참조하였다. MemTable에서 사용하는 데이터 구조인 Skip-list 등 추가 설명이 필요하면 해당 자료를 참고하면 좋을 것 같고 CURG의 이전 글에서도 조금 다루었기 때문에 해당 글을 보아도 좋다.

마그네틱 기반 저장장치에서 NVMe SSD까지

SSD가 등장하고 나서 지금은 대부분의 전자기기에서 SSD를 저장장치로 이용하고 있다. 지금 부터는 크게 4개의 저장장치 종류를 소개하려고 한다. 아래 표는 각 저장장치의 특징과 성능을 도표로 나타낸 것이다.

[표 1] 저장장치별 특징과 성능

위 도표에 적힌 수치는 커뮤니티에서 보고된 수치를 참고하였으며 모두 CrystalDiskMark라는 성능 측정 프로그램을 이용하였다[3][4]. 이 수치와 특징은 오늘 소개할 논문[KVell]에서 보여주는 내용과 크게 다르지 않다.

KVell : 그 동안의 노력이 이제는 발목을 잡고있다.

이번 포스팅의 주인공은 ACM SOSP 2019에 게재된 KVell이다. KVell은 고성능의 키-밸류 데이터베이스의 구현과 설계 내용을 서술한 논문이다. 바로 위 파트에서 서술했듯이 최신 SSD에서는 Sequential I/O와 Random I/O의 차이가 적기 때문에 Level-DB의 Compaction 과정을 제거하고 순수하게 디스크 성능에 의존한다면 성능이 더 나아지지 않을까? 하는 단순한 아이디어에서 출발하였다. 이 내용을 증명하기 위해 논문에서는 Level-DB와 Mongo-DB의 성능을 시간에 따른 변화량을 측정하였는데 결과는 아래 [그림 2]와 같다.

[그림 2] LSM 트리와 B 트리 기반 데이터베이스의 성능

위 [그림 2]에서 빨간색 점선은 측정한 SSD의 최대 성능을 말한다. 즉, 이론적인 최대 성능이 아니라 실제 측정한 최대 성능이다. 그리고 검은 실선은 데이터베이스를 사용하였을 때 데이터 저장 처리량을 말한다. 기본적으로 SSD의 최대 성능을 내지 못할 뿐 아니라 시간이 갈수록 처리량이 급격하게 떨어지는 구간이 발생하는 것을 알 수 있다.

이는 디스크 I/O를 발생하기 전에 CPU 자원을 사용하는 Compaction 작업으로 인해 병목이 발생하는 것으로 진단하였다. 본 논문에서는 이 결과를 보고 과거에는 CPU가 빠르고 저장장치가 느려서 성능이 느렸다면 현재는 오히려 CPU가 저장장치 성능의 발목을 잡고 있다고 평가하였다. 그래서 KVell의 저자는 새로운 설계 방식을 고안하였는데 이 방식은 CPU의 오버헤드를 최대한 줄여서 디스크의 최대 성능을 내는 것을 목표로 하고 있다. 그리고 이 CPU 오버헤드의 주 원인인 Compaction 과정을 제거하였다.

KVell : 새로운 설계

KVell은 새로운 키-밸류 데이터베이스를 설계하면서 네 가지 주요 변경사항을 제안한다.

위 네가지 설계 원칙이 적용되면 데이터베이스 구조는 [그림 3]과 같이 될 것이다. 그림을 보면 LSM에 비해 되게 단순하게 돌아간다. 아래 그림에 표현된 내용 외에도 페이지 캐시 등 기타 작업이 있긴 하지만 최대한 단순하게 설명하기 위해 핵심 개념을 설명하기 위한 내용만 그려두었다.

[그림 3] KVell 데이터베이스의 구조를 도식화한 그림

위 [그림 3]에서 put과 delete그리고 get/scan 작업은 서로 다르게 동작하는 것을 보여주기위해 인위적으로 어색하게 띄어두었다. KVell은 데이터를 쓸 때는 디스크의 마지막 기록위치에 데이터를 바로 저장하고 그 위치를 B-Tree에 저장한다. 이 때 B-Tree에 저장하기 때문에 O(log n)의 추가적인 작업량이 들어가지만 B-Tree를 이용하면 일정한 성능을 기대할 수 있고 B-Tree는 키의 크기가 작고 보유한 메모리 크기에 알맞게 들어가기만 하면 높은 성능을 기대할 수 있다. KVell의 트리 구조에서는 하나의 아이템당 19 bytes크기의 데이터만 트리를 구성하는데 사용하고 1억개의 데이터를 저장하는데 1.7GB의 메모리를 사용하도록 설계하였다.

그리고 각 쓰레드별로 키 범위에 따라 저장하는 공간이 다르고 각 쓰레드는 상태를 공유하지 않기 때문에 병렬성을 증대하였다. 논문에서는 Level-DB나 MongoDB에서는 이런 병렬성을 도입하는 구현 난이도가 어려웠다고 회자하면서 새로운 설계 덕분에 병렬성 처리를 더 간편하게 했다고 말한다. 위 매커니즘에 따르면 scan (범위 탐색)을 수행할 때만 쓰레드가 동기화가 필요하다. 이 때 scan 성능이 크게 떨어질 것으로 예상되었지만 실험 결과, 그렇지도 않았다. 아래 [그림 4]은 위 설계에 따른 구현체를 실험한 내용이다. KVell DB의 소스 코드는 여기 깃허브에서 찾아볼 수 있다.

[그림 4] KVell 데이터베이스의 성능

YCSB는 야후 리서치팀에서 개발한 No-SQL 데이터베이스 표준 성능 평가 지표이다. 이를 토대로 LevelDB를 개선한 버전인 RocksDB와 MongoDB (WiredTiger) 그리고 KVell의 성능을 비교하였다. [그림 4]의 우측 그림에서 검은색 막대가 Kvell의 처리량을 나타내는데 다른 데이터베이스와 비교하여 처리량이 큰 폭으로 증가하는 것을 알 수 있다. [YCSB E]는 scan 요청이 95% 비율인 경우를 나타내는데 이 경우에만 RocksDB가 근소한 차이로 앞서고 있다. 그리고 아래 [그림 5]는 시간에 따른 처리량 변화량을 보여준다. 데이터로 사용한 키를 선택할 때는 일양 분포(Uniform Distribution)와 지프의 법칙(Zipf’s law)에 따라 키를 선택하였다[5].

[그림 5] 시간에 따른 처리량 변화

위 그림에서는 주황색으로 표시된 부분이 KVell의 성능을 나타내는데 여기서 중요하게 볼 점은 KVell은 시간에 따른 처리량 요동(fluctuation)이 발생하지 않는다. 반면, RocksDB와 MongoDB는 시간에 따라 처리량이 요동치는 부분이 발생하는데 이는 Compaction 작업으로 인해 Write-Lock이 발생한 지점으로 분석하고 있다.

Level-DB의 성능이 블록체인 성능에 영향을 미칠까?

지금까지 Level-DB의 간략한 소개와 Modern-SSD에서 Level-DB의 성능을 높이는 연구인 KVell에 대해 짧게 소개하였다. 현재 블록체인을 연구하고 있는 사람으로써 다음 질문에 대해 생각해보고자 이 논문을 준비하였다.

블록체인의 다른 연구를 보아도 위 질문에 대한 명확한 정답을 얻지 못했기 때문에 당분간 이 분야로 조금 연구를 할 것 같다.

결론

오늘은 블록체인 보다 KV 데이터베이스에 대한 내용을 주로 다루었다. 현재 이더리움의 성능 향상을 위한 샤딩, 오프-체인, 라이트닝 네트워크 등 레이어-2 솔루션들이 활발히 논의되고 있지만 개인적으로 이런 레이어-2 솔루션 보다 온-체인만으로 성능을 높일 수 있다면 가장 합리적인 개선책이라고 생각하기 때문에 이런 쪽으로 성능을 높이는 방향을 생각 하고 있었다. 앞으로도 이렇게 타 분야의 연구와 블록체인을 함께 생각할 수 있는 논문이 있다면 다음 회차 때 다시 다루어보도록 하겠다.

레퍼런스

[1] KVell: the design and implementation of a fast persistent key-value store
[2] GearDB A GC-free Key-Value Store on HM-SMR Drives with Gear Compaction
[3] SATA HDD vs SATA SSD vs NVMe SSD CrystalDiskMark results
[4] Intel Optane SSD 905P 960GB Drive Review
[5] Zipf’s law [Wiki]