[Go] kv 파일 스토리지를 골라보자! (부제: LSM Tree와 B Tree)

[요약]

1. kv storage는 LSM tree로 구현된 것과 B tree로 구현된 것으로 나뉜다
2. LSM tree는 쓰기가 빠르고 B tree는 읽기가 빠르다
3. Go의 KV 파일 스토리지 구현체는 badger, pebble, bbolt가 있다
4. badger와 pebble은 동일 db에 read 프로세스와 write 프로세스가 접근하면 에러가 발생한다. bbolt는 행이 걸린다

이 글에서는 Key-Value 쌍을 KV라고 칭합니다.

Go 어플리케이션에 단순한 KV 스토리지가 필요한 경우가 있다. 정말 단순한 기능만 필요해도 수 백, 수 천만의 데이터를 관리해야 하고 여러 고루틴이 접근한다면 직접 구현하기 까다롭다.

이번 글은 KV 스토리지에 많이 쓰이는 자료구조인 LSM tree와 B tree를 비교하고, Go로 구현된 KV 스토리지 구현체는 무엇이 있는지 알아볼 것이다.

LSM Tree

아주 단순한 자료구조를 생각해보자.

• KV가 입력되면 단순히 파일의 끝에 추가한다
• 파일이 너무 커지면 새로운 파일을 생성해 추가한다(세그먼트 파일)
• 여러 파일이 생기면 병합을 한다(각 key의 최신 값만 유지)
• 키와 바이트 오프셋을 매핑해 제공하는 해시 테이블 색인을 사용한다

위 자료구조는 꽤 쓸만한 KV 스토리지다. 하지만 KV가 많아지면 문제가 생긴다. 메모리에 유지해야할 해시 테이블 색인이 너무 커지기 때문이다.

LSM Tree는 위 자료구조에 KV을 Key로 정렬하고, 각 세그먼트 파일에서 키는 한번만 나타낸다. 키로 정렬된 형식을 SS 테이블(Sorted Sorting Table)이라고 한다.

SS테이블을 사용하면 세그먼트 파일을 병합할 때 merge sort와 유사한 알고리즘을 사용할 수 있어 효율적이다. 또한 색인도 모든 키를 가지고 있을 필요가 없다. 키 "A"의 오프셋과 키 "C"의 오프셋을 알고 있다면 키 "B"의 오프셋은 "A"와 "C" 오프셋 사이라는 것을 알 수 있어 드문 드문 가지고 있어도 충분하다.

그런데 KV를 쓸 때 어떻게 정렬된 상태로 계속 유지하면서 쓸까? 디스크 상에 정렬된 상태로 유지하는 것은 비용이 매우 비쌀 것이다. 그래서 메모리에 레드 블랙 트리나 AVL 트리와 같이 임의 순서로 키를 삽입해도 정렬된 순서를 유지할 수 있는 자료구조를 둔다. 이 인메모리 트리를 멤테이블(memtable)이라고 한다. 멤테이블의 크기가 임계값을 넘으면 그때 SS테이블로 디스크에 기록한다.

DB가 고장나면 아직 디스크에 쓰여지지 않은 멤테이블이 사라지기 때문에 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지한다. 이 로그는 복구할 때만 사용하기에 정렬할 필요가 없다.

• 읽기 요청: 멤테이블 확인 -> 없으면 첫 번째 SS테이블 확인 -> 없으면 두 번째 SS테이블 확인 ... (실제로는 최적화를 위해 블룸 필터 및 레벨 컴팩션 등을 사용한다)
• 쓰기 요청: 메모리의 멤테이블에 쓰기

B Tree

B Tree는 보통 4KB 고정 크기의 블록 및 페이지로 나누어 한 번에 하나의 페이지에 읽기 또는 쓰기를 한다.

각 페이지는 주소나 위치를 이용해 식별할 수 있어 하나의 페이지가 다른 페이지를 참조할 수 있다. 포인터와 다른 점은 이 페이지들은 디스크에 있다는 점이다.

기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어 쓰는 것이다. 덮어쓰기가 페이지 위치를 변경하지 않는다고 가정해 해당 페이지에 대한 참조는 그대로 살아 있다. LSM Tree가 파일에 추가만 하는 것과 대조된다.

DB가 고장나면 WAL(Write Ahead Log) 데이터 구조를 사용해 B Tree를 복구한다.

• 키 갱신: 키를 포함하는 리프 페이지를 검색하고 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록한다.
• 키 삽입: 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가. 여유 공간이 없다면 페이지를 둘로 나눈다.

LSM Tree vs B Tree

보통 LSM Tree은 쓰기가 더 빠르고 B Tree는 읽기가 더 빠르다.

• LSM Tree가 읽기가 더 느린 이유는 각 컴팩션 단계에 있는 여러 가지 데이터 구조와 ss테이블을 확인해야 하기 때문이다.

쓰기 비교

• B Tree 색인은 모든 데이터를 로그에 한번, 트리 페이지에 한번 총 두번 기록한다.
• LSM Tree는 ss 테이블의 반복된 컴팩션 및 병합으로 여러 번 데이터를 다시 쓰게 된다(write amplication)

컴팩션

• LSM Tree는 쓰기 처리량이 높고 압축률도 좋다. B 트리는 페이지 내 사용하지 않는 디스크 공간 일부가 남게 된다.
• LSM Tree는 주기적으로 파편화를 없애기 위해 ss 테이블을 다시 기록한다. 다만 이 컴팩션이 읽기와 쓰기 성능에 영향을 줄 수 있다.

데이터 중복

• B 트리는 각 키가 색인의 한 곳에 정확하게 존재한다. 반면 LSM은 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있다.

Go의 KV 스토리지 구현체

위에서 KV 스토리지를 구현할 수 있는 주요 자료구조 두 개를 알아봤다.

필자는 Go로 구현된 KV 스토리지가 필요해 오픈 소스들을 조사해봤는데, 괜찮아 보이는 프로젝트들은 다음 3개가 있었다.

Badger

• 라이센스: Apache
• Pure Go로 작성됨
• LSM Tree로 구현됨

Pebble

• 라이센스: BSD-3
• Pure Go로 작성됨
• LSM Tree로 구현됨
• go 1.17 버전 이상 요구
• Cgo 사용

bbolt

• 라이센스: MIT
• Pure Go로 작성됨
• B+ 트리로 구현됨
• 위 두 개의 프로젝트에 비해 업데이트가 느리다.
• Bolt DB를 포크한 프로젝트(현재 아카이브 상태)
• etcd에 사용되고 있다.
• 100만개 이상 key-value를 한번에 쓸 수 있다

위 3개의 스토리지를 두고 어떤 스토리지를 사용할 지 고민을 많이 하였다. 고민의 결과는 의외로 싱겁게 끝났다. 필자가 작성하는 프로그램은 여러 프로세스가 하나의 DB에 접근을 해야 했는데, 이를 보장하는 DB가 bbolt 밖에 없었다. Badger와 Pebble은 read 프로세스와 write 프로세스가 같이 접근하면 에러를 발생시켰다. 반면 bbolt는 하나의 프로세스가 다른 프로세스가 끝날 때까지 hang이 걸렸다.

이 선택 기준은 특이 케이스이다. 일반적으로 스토리지에 접근하는 프로세스는 하나로 제한하여 사용해야 한다.

이 글을 보는 사람들은 3개의 프로젝트의 docs를 꼼꼼히 읽고 직접 실험을 해서 자신이 사용하려는 목적에 알맞는지 꼭 확인을 해보기 바란다.

Reference

데이터 중심 어플리케이션 설계