Database Index 탐구: Hash, B+-Tree, LSM Tree

Index 탐구: 예제 Log Structured 저장소

이전에 DB 인덱스 개념에 대해 다뤘었다. 더 나아가 인덱스에 대해 공부해보았다. 이를 설명하기 위해 Mac 터미널 환경에서 bash 함수를 사용하여 기본적인 key-value 저장소를 만들었다.

#!/bin/zsh

db_set(){
   echo "$1, $2" >> database
}

db_get() {
   grep "$1," database | sed -e "s/^$1,//" | tail -n 1
}

 

해당 파일은 append-only만 가능한 로그 저장소이다. 그러면 중복된 key가 들어갈 경우에는 'tail -n 1' 명령어로 인해 가장 마지막에 추가된 key의 value가 조회된다. 

> db_set 1234 '{"name":"aaa"}'
> db_get 1234
 {"name":"aaa"}

> db_set 5678 '{"name":"bbb"}'
> db_get 5678
 {"name":"bbb"}
 
 > db_set 1234 '{"name":"ccc"}'
> db_get 1234
 {"name":"ccc"}
 
> cat database
1234, {"name":"aaa"}
5678, {"name":"bbb"}
1234, {"name":"ccc"}

 

데이터 추가는 간단하지만, 조회 연산은 매우 비효율적으로 동작한다. 특히 대규모 데이터 셋일수록 더 취약해진다. db_get 작업은 database 파일의 전체 디스크 스캔이 필요하며 중복 키의 경우 특히 비용이 많이 든다. 바로 이 지점에서 인덱스의 필요성이 생긴다.

 

인덱스는 데이터를 더 빠르게 검색할 수 있도록 하여 쿼리 성능을 향상시키는 데이터 구조이다. 시스템은 전체 데이터베이스를 스캔하는 대신 인덱스를 참조하여 데이터를 더 빠르게 찾을 수 있다. 하지만 단점도 있다. 인덱스는 데이터를 보관하는 용도가 아닌 퍼포먼스 향상을 위한 메타데이터이기 때문에 용량을 추가적으로 차지한다는 점과 쓰기 작업에서 부하가 걸릴 가능성이 있다는 점이다.

 

Hash Index 

해시 인덱스는 주로 해시 테이블 또는 해시 맵으로 구현된다. 위에서 구현한 key-value에서 해시 인덱스만 추가해주었다. (현재 index는 인메모리 데이터 구조이자 터미널을 종료하면 사라지는 휘발성 데이터이다.)

#!/bin/zsh

typeset -A index

db_set(){
    # Calculate the byte offset before appending
    offset=$(stat -f "%z" database 2>/dev/null || echo 0)

    # Add or update the index
    index[$1]=$offset

    # Append the key-value to the database
    echo "$1, $2" >> database
}

db_get() {
    # Fetch the byte offset for the key from the index
    offset=${index[$1]}
    
    if [ -z "$offset" ]; then
        echo "Key not found"
        return
    fi

    # Use the byte offset to fetch the value
    tail -c +$((offset+1)) database | grep "^$1," | sed -e "s/^$1,//" | head -n 1
}

db_show_index() {
    echo "Key - Offset"
    for key in "${(@k)index}"; do
        echo "$key - ${index[$key]}"
    done
}

 

이제는 hash map 인덱스를 활용해서 각 key가 disk 어디 위치했는지 바로 찾을 수 있다. '1234'의 경우 첫 데이터의 경우 126으로 저장되어 있다가 중복 key가 쓰여지니깐 168로 덮여쓰여졌다. 이는 구현이 간단하고 set, get 연산이 O(1) 동작해서 빠르다. 

 

Hash Index

 

Segment File과 Compaction

주요 고민은 확장성이다. 덮여쓰여진 이전 key-value 데이터는 더이상 쓸모가 없기 때문에 용량만 차지하게 된다. 이렇게 낭비되는 용량을 줄이기 위해서 Segment File과 Compaction이라는 개념이 추가되었다.

 

Segment File 개념은 일정 사이즈가 되면 새로운 파일을 만든다. 파일이 1, 2, 3 순서대로 만들어진다고 했을 때 이미 다 쓰여진 1, 2 파일은 더이상 바뀌지 않는 immutable 데이터이다. 변하지 않는 데이터 파일이니 관리하기가 더 편해지는 것이다. 여기서 compaction 개념이 들어온다. immutable한 데이터 파일을 스캔하면서 중복되는 key-value 데이터를 제거해준다. 여기서 '1112'를 조회를 하면 최신 테이블부터 순차 탐색으로 Index3 → Index2 → Index1 순대로 조회를 하여 탐색한다. 

 

Segment File과 Compaction

 

우선 해당 방식은 존재하는 모든 key가 인덱스 메모리에 1대1로 매핑되어 들어가야 한다. 메모리 제약으로 인해 디스크에 저장해야 할 경우 속도, 리소스면에서 매우 비효율적으로 동작한다. 그리고 range 쿼리 어렵다. 해시 맵은 키가 정렬되어 있지 않기 때문에 범위(ex: 'k100' ~ 'k999')를 쉽게 스캔할 수 없다. 해시 맵 구조를 개조해야 한다. 

 

LSM(Log Structured Merge) Tree

LSM Tree는 SST(Sorted String Table)을 사용해서 여러 문제들을 개선시켜준다. Segment File과 비슷하지만 이는 Key가 정렬되어있다. 그런데 append-only 구조인데 어떻게 정렬시킬 수 있을까? 이미 '5678'을 넣고 뒤에 '1117' key가 들어온다고 해서 삭제 추가하는 작업을 해주면 매우 비효율적일 것이다. 

 

데이터 저장

새로운 key-value 데이터를 추가할 때 디스크에 있는 SST가 아니라 우선 메모리에 있는 이진 트리에 추가한다. 여기서 이진 트리는 RB 트리와 같은 self balanced 트리이고 이 메모리 저장소를 memtable이라고 부른다. 

• 이 memtable에 입력되는 값들을 보관하고 있다가 일정 사이즈가 되면 SSTable에 flush한다. key가 이미 정렬되어있기 때문에 빠르게 작업할 수 있다. 만약 쓰기 전에 Crash가 날 경우를 대비해서 지속성을 위해 디스크 로그 파일에 해시 맵에서 했던 방식대로 단순 쓰기를 하여 보관한다.
• Cash Recovery: 그리고 이 파일은 memtable이 SSTable에 flush할 때 같이 파기한다. 이로서 DB가 중단되거나 재시작되더라도 해당 로그 파일을 통해 쉽게 복구가 가능하다. 

 

LSM Tree - insert

 

데이터 읽기

데이터 읽기는 세그먼트 파일과 유사하고 읽기 작업을 더 빠르게 하기 위해서 인덱스 테이블을 사용한다. 해시 인덱스랑 거의 유사하지만 지금 디스크에 쓰여진 SSTable은 정렬된 key라는 점을 활용하여 인덱스 테이블을 더 효율적으로 개선할 수 있다. 해시 인덱스는 디스크 쓰여진 모든 key를 메모리에 저장했어야 했다면 이제는 필요한 축약된 데이터로만 인덱스를 관리할 수 있다.

1. 우선 읽기 요청이 들어오면 그 key가 현재 작업중인 memtable에 있는지 확인한다.
2. 없는 경우 가장 최신 SSTable을 확인하고 순차대로 마지막 SSTable까지 탐색하게 된다.

 

만약 '1256'을 찾고 싶다고 했을 때 '1122' ~ '2342'에 속해있는 것을 알기 떄문에 적은 비용으로 값을 스캔할 수 있다. 

 

LSM Tree - index

 

merge 하는 이유는 SSTable이 많으면 많아질수록 확인해야 할 테이블의 수가 늘어나서 읽기 퍼포먼스가 저하될 수 있기 때문이다. 

LSM Tree Structure(왼), compaction-merge 예시(오)

 

장점 

• 데이터 쓰기 작업 빠름
• Index 테이블에 축약된 데이터의 정보만 저장해서 공간 활용 좋음
• key가 정렬되어 있어서 range 쿼리 효율 좋음

단점

• compaction 과정에서 SSD 쓰기 증폭으로 인해 오버헤드 발생 
• SSD의 쓰기 증폭을 줄이기 위해서 compaction을 최소화 할 것인가 읽기 최적화를 위해서 compaction을 자주할 것인가에 대한 고민 필요

 

B-Tree

이진트리의 자료구조와 유사하지만 B 트리는 효율적으로 데이터를 저장할 수 있는 특징을 가지고 있다. 한 노드에 여러 정보를 들고 두 개 이상의 자식 노드를 가질 수 있다. 그리고 이는 정렬된 상태로 저장되기 때문에 검색에 용이하다. 다만 아래와 같은 구조에서 '1'~'7'의 값을 범위 검색을 하기 위해서는 여러 개의 노드를 찾아서 검색해야 한다는 단점이 있다. 

 

B-Tree

장점

• 하나의 노드에 여러 정보를 담을 수 있어 데이터 공간 활용 좋음 (N차 트리)
• 자체 밸런스 조정으로 데이터 읽기 성능 좋음
• 데이터 동시 쓰고 읽는 시스템에 적합

단점

• 여러 노드를 액세스하는 range 쿼리 취약
• 데이터 쓰기/삭제 SSD 쓰기 증폭으로 인한 오버헤드 발생 

 

B+ Tree

B+ 트리는 모든 레코드가 leaf 노드에 저장되고 중간 노드에는 인덱스가 저장되는 특징을 가지고 있다. 이는 B 트리의 범위 검색에 대한 단점을 보완해주는데, 이는 leaf 노드들이 모두 링크드 리스트로 연결되어 있기 때문이다. 

 

데이터 저장

한 번 데이터를 쓰는 데 B+ Tree 구조로 인해 여러 디스크 write가 필요할 때가 있다. 이를 write amplication(쓰기 증폭)이라고 한다. 이러한 특징으로 인해 쓰기하는 도중에 DB Crash 장애가 발생하는 경우 데이터가 손상될 가능성이 있다. 그래서 대부분 디스크 영역에 WAL 로그(redo 로그라고도 불림)에 어떤 write를 할지 미리 영구적으로 써놓고 B+Tree 쓰기 작업한다. (LSM Tree의 Log File과 같은 역할) 이로써 데이터베이스의 내구성을 보장한다.

 

루트 노드에는 인덱스가 존재하고 [1,2,3,7] 데이터가 리프 노드 3개가 존재하고 있을 때, 데이터 6을 추가로 삽입하였는데 B+ 트리 노드가 3개가 더 추가된 모습을 볼 수 있다.

 

B+Tree 데이터 추가

 

장점

• 리프 노드들이 모두 연결되어 있어서 B-Tree에 비해 range 쿼리 효율 좋음
• 모든 레코드가 리프 레벨에 상주하므로 B-트리보다 공간 활용 좋음

단점

• B+ 트리는 리프 수준에 추가된 구조로 인해 구현하기가 더 복잡
• B-Tree와 마찬가지로 쓰기 증폭 발생으로 인한 오버헤드 발생

 

LSM vs B+ Tree

일반적으로 B+Tree 는 데이터 읽기, LSM Tree는 데이터 쓰기에 각 강점을 지니고 있다. 

 

데이터 읽기(Read)

• B+Tree는 트리를 따라서 내려가면 최대 O(logN)안에 조회된다. (최대 높이 O(logN))
• LSM Tree는 memtable 에 없는 데이터일 경우 여러 개의 SSTable을 확인해야 한다. 또한 백그라운드 작업 (comaction)이 영향을 줄 수 도 있다. 

 

쓰기 증폭(Write Amplification)

• LSM Tree는 memtable과 log-file (+ merge) 쓰면 된다. (sorting, 순차 쓰기 및 merge 등 시간 별로 안걸림)
• B+ Tree는 여러 번의 Disk Write이 필요할 수 있다 (+ WAL 로그) (+ 페이지 분리 작업이 다소 까다로움)
• 따라서, LSM 트리가 상대적으로 B+ Tree보다 쓰기 증폭이 더 낮다.

 

Fragmentation

• LSM은 주기적으로 compaction 작업을 해주어서 압축률이 좋다. 그래서 B+Tree보다 디스크에 더 적은 파일 생성한다.
• B+Tree는 파편화로 인해 사용하지 못하는 공간 일부 존재한다.

 

동시성 제어

• B+Tree는 데이터가 한 곳에만 존재하여 관리가 쉽다. 
• LSM Tree는 각기 다른 세그먼트에 다중 복사본 존재할 수 있다. 높은 쓰기 처리량에서 (logging + sst로 flushing)과정과 백그라운드 compaction 과정이 공유되어야 하는데, 여기서 유입 속도를 못따라가서 중복 발생할 수 있다.
• 그래서 ACID 트랜잭션 기능을 중시하는 데이터는 B+Tree를 주로 사용한다.

 

resources

Martin Kleppmann, 데이터 중심 애플리케이션 설계, 정재부, 김영준, 이도경 옮김, Ch2. 데이터 모델과 질의 언어 

 

Yifan Qiao, Rensselaer Polytechnic Institute; Xubin Chen, Google Inc.; Ning Zheng, Jiangpeng Li, and Yang Liu, ScaleFlux Inc.; Tong Zhang, Rensselaer Polytechnic Institute and ScaleFlux Inc. Closing the B+-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression

 

O’Neil, Patrick; Cheng, Edward; Gawlick, Dieter; O’Neil, Elizabeth. "The log-structured merge-tree (LSM-tree)