LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data

Presentation on theme: "LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data"— Presentation transcript:

1 LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data
Xingbo Wu ATC 2015 Lee, Kangmin

2 어플리케이션의 요구사항 방대한 양의 데이터가 요구되는 어플리케이션이 증가
SNS E-commerce Online game 기존의 관계형 데이터베이스(ex: mysql)보다 빠른 성능의 Key-Value Store가 각광을 받고 있음

3 Key-Value Store Key와 Value로만 이루어진 데이터베이스 단순한 인터페이스
Value는 오직 하나의 Key에 의해서만 접근이 가능 단순한 인터페이스 Put(key, value) Get(key) Delete(key) 데이터간의 비교가 불가능한 대신, 읽기/쓰기 속도가 매우 빠름

4 Key-Value Store의 특징 요구되는 용량이 점점 증가 Value의 크기는 작음
TB단위의 데이터 메타데이터의 크기도 무시할 수 없음 Value의 크기는 작음 페이스북의 경우 99%의 item이 68B 이하 메타데이터의 증가가 성능에 큰 영향을 미침 캐시량이 줄어들음 Warm-up 시간 증가 Disk R/W 횟수 증가

5 LevelDB의 구현 LSM-tree(Log-Structured Merge-Tree)
Google BigTable, Cassandra에서 사용하는 자료구조 B+ Tree에 비해 쓰기 성능이 우수 MemTable, SSTable, Commit Log라는 3개의 저장 공간을 사용 SSTable(Sorted String Table) MemTable이 가득 차게 되면, 디스크에 SSTable을 생성 변하지 않는(immutable) 파일 내부 데이터는 key를 기준으로 정렬 되어짐 Index block을 배치하여 원하는 block을 이진탐색으로 검색 Bloomfilter 지원 여러 SSTable을 통합(compaction) 할 수 있음

6 Compaction 각 레벨의 크기가 꽉 차면 새로운 레벨에 SSTable을 merge- sort 하는 작업
비용이 작지 않고, 레벨이 증가함에 따라 쓰기 확장(Write Amplification) 이 크게 증가함

7 SET Throughput 저장하는 수가 늘어날수록 쓰기 성능이 크게 감소
100B - KV item이 10TB 있을 때, 메타데이터의 크기는 155GB

8 Goals 크기 확장을 줄이고 small data에 최적화된 Key-Value Store 소개
LevelDB의 LSM-tree를 기반으로 한 LSM-trie LevelDB에 비해 R/W throughput 20배 향상

9 Trie String set의 각 위치의 문자로 트리를 구성 접두사 트리(prefix tree)라고도 불림
길이가 M인 N개의 문자열 집합의 탐색은 O(MlgN)인것에 비해, Trie를 사용하면 O(M)에 찾을 수 있음

10 LSM-trie KV를 sha-1로 해싱하여 비트단위로 쪼개고, N개의 비트로 묶은 트리를 구성하여 해당하는 위치에 저장

11 LSM-trie Compaction Compaction은 자식노드에 선형적으로 쌓이기 때문에 확장이 적게 발생함

12 LSM-trie HTable 노드에서 특정 KV를 찾기 위해 해시 테이블을 제공 각 버켓의 default 값은 4KB
크기가 초과된 버켓은 다른 작은 버켓으로 이동됨(정렬)

13 LSM-trie Cache 메타데이터는 각 버켓마다 이동된 KV에 대한 정보(8B)만을 담음
평균적으로 1.01 번의 disk read가 발생 1TB의 데이터에 필요한 메모리는 약 400MB

14 BloomCluster 같은 해시를 갖는것끼리 모든 블룸필터를 모음 결과적으로 GET 명령에 한번의 read가 필요

15 PUT Performance

16 WA Comparison

17 Read Performance

18 Read Performance

19 Conclusion 작고 많은 데이터를 관리하기위한 LSM-trie 구현 쓰기 확장 비율 감소
디스크상의 메타데이터 연산에도 빠른 성능

20 thanks