색인(index)의 두 가지 형태 : LSM 트리 & B 트리

‘데이터 중심 애플리케이션 설계 by Martin Kleppmann’ 책의 3장(저장소와 검색)의 일부 내용을 정리한 글입니다. 부족하다고 생각되는 부분은 내용을 덧붙였으며 제 개인적인 생각이 중간중간 첨가되어 있습니다.

If you keep things tidily ordered, you’re just too lazy to go searching.
항상 주변을 단정히 정돈하는 사람은 단지 찾기를 너무 귀찮아하는 사람이다.
- 독일 속담

가장 기본적인 수준에서 데이터베이스는 크게 두 가지 작업을 수행한다.

• 데이터를 받아서 저장한다.
• 데이터를 요청받으면 다시 데이터를 반환한다.

데이터베이스가 위의 기본적인 작업을 효율적으로 처리하기 위해 어떤 도구와 방법들을 활용하는지 살펴보자.

데이터베이스의 내부 작동 방식을 애플리케이션 개발자가 굳이 알아야할까? 우리는 대부분 데이터베이스 엔진을 직접 구현하기 보다는 시중에 구현된 여러 엔진 중에 우리 애플리케이션에 적합한 것을 선택하기 마련이다. 우리 비즈니스 애플리케이션의 특정 작업부하(workload) 유형에 알맞은 데이터베이스를 선택하고 또 좋은 성능을 내게끔 엔진을 조정하려면 데이터베이스가 내부적으로 작업을 어떻게 처리하는 지 대략적으로는 알아야 할 필요가 있다.

데이터베이스가 사용하는 다양한 데이터 구조

데이터베이스에서 특정 데이터를 효율적으로 찾기 위해서는 데이터 그 자체와는 별개로 다른 데이터 구조가 필요하다. 바로 색인(Index)이다. 이번에 다양한 색인 구조를 살펴보고 그 특징을 비교해보자.

색인

• 색인은 기본 데이터(primary data)에서 파생된 추가적인 데이터 구조이다.
• 색인의 추가와 삭제는 기본 데이터의 내용에는 영향을 미치지 않는다.
• 단지 질의 성능에만 영향을 준다.
• 색인을 잘 선택했다면 색인의 추가는 읽기 성능을 높이고 쓰기 속도를 떨어트린다.
• 이런 이유 때문에 데이터베이스는 보통 자동으로 모든 데이터를 색인하지 않는다.
• 애플리케이션 개발자는 필요 이상으로 오버헤드를 발생시키지 않으면서 애플리케이션에 가장 큰 이익을 안겨주는 색인을 선택해야한다.

해시 색인

가장 기본적인 key-value 데이터 색인을 살펴보자. 보통 해시 맵(hash map)으로 구현하는데, 인메모리 데이터 구조를 위한 해시 맵이 이미 있으니 디스크 상의 데이터를 색인하기 위해 이를 사용하는건 어떨까?

키를 디스크상의 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지하는 전략을 써보자. 값을 조회하려면 해시 맵을 사용해 데이터 파일에서 오프셋을 찾아 위치를 구하고 값을 얻는다.

이 단순한 방식은 보통 해시 맵을 전부 메모리에 유지하는 것을 조건으로 사용한다. 고성능으로 읽기, 쓰기를 보장하기 때문이다. 그래서 키 자체가 많지는 않지만 키당 쓰기 수가 많은 작업부하에 적합하다.

하지만 위 같은 Log-structured 형식으로 데이터를 저장하면 항상 파일에 추가만 하기 때문에 결국 디스크 공간이 부족해진다. 이를 해결하기 위해 데이터를 특정 크기의 세그먼트(segment)로 나누고 주기적으로 컴팩션(compaction)을 수행할 수 있다. 컴팩션이란 중복된 키를 버리고 각 키의 최신 값만 유지하는 것을 말한다.

이렇게 하면 해시 맵은 각 데이터의 오프셋과 키를 매핑하고 각 오프셋이 가리키는 값은 최신 값임을 보장할 수 있다.

해시 색인은 간단한 만큼 단점 또한 확실하다.

• 해시 맵을 메모리에 저장해야 하므로 키가 너무 많으면 문제가 된다. 디스크에 해시 맵을 유지할 수는 있지만 디스크 상의 해시 맵에 좋은 성능을 기대하기는 어렵다. 무작위 접근 I/O가 많이 필요하기 때문이다.
• 해시 맵은 범위 질의(range query)에 굉장히 비효율적이다. 해시 맵에서 모든 키를 개별적으로 조회해야 한다.

이런 제한이 없는 색인 구조도 살펴보자.

SS 테이블 & LSM 트리

위에서 봤던 세그먼트 파일의 형식에 요구사항 딱 하나만 추가해보자.

• 모든 key-value 쌍을 키를 기준으로 정렬한다.

이를 반영한 Log-structured 데이터 형식을 Sorted String Table 혹은 SS 테이블이라고 부른다.

SS 테이블은 해시 색인을 가진 로그 세그먼트보다 몇 가지 큰 장점이 있다.

• 세그먼트 병합이 보다 효율적이다. 세그먼트가 정렬되어 있기 때문에 merge sort 가 가능하다.
• 파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요가 없다. 아래 그럼처럼 일부 키 색인만 있으면 충분하다. (대략 수 킬로바이트당 키 하나)

데이터를 키로 정렬하는 방법

디스크 상에 정렬된 구조를 유지하는 일은 가능하지만 메모리에서 정렬하고 디스크로 내려보는 편이 훨씬 쉽다. 쓰기와 읽기 과정을 간략하게 정리하면 다음과 같다.

1. 쓰기가 들어오면 인메모리 균형 트리(balanced tree) 데이터 구조(e.g. red-black tree)에 추가한다. 이 인메모리 트리를 멤테이블(memtable)이라고 부른다.
2. 멤테이블의 크기가 임계값(보통 수 MB)보다 커지면 SS테이블 파일로 디스크에 기록 (트리가 이미 정렬되어 있기 때문에 효율적)
3. 읽기 요청을 처리하려면 먼저 멤테이블에서 키를 찾는다. 그 다음 디스크상의 최신 세그먼트부터 찾는다. (인메모리 해시맵이나 bloom filter 를 사용하여 탐색 시간을 줄일 수 있다.)
4. 백그라운드에서 지속적으로 컴팩션 과정을 수행한다.

LSM 트리 (Log-Structured Merge-Tree)

위 처럼 SS 테이블의 형식으로 디스크에 key-value 데이터를 저장하는 색인 방식을 LSM 트리라고 부르며, LSM 트리는 1996년 패트릭 오닐(Patrick O’Neil)의 논문 The Log-Structured Merge-Tree (LSM-Tree)에서 처음 발표되었다. 데이터를 append-only 로그 형식으로 저장하고 지속적으로 merge sort를 수행하니 LSM 트리라는 이름이 붙었지 싶다.

LSM 트리가 성능을 최적화한 방법

• 블룸 필터 (Bloom Filter)

블룸 필터는 원소가 특정 집합에 속하는지 여부를 확률적으로 알아낼 수 있는 자료구조로, 이를 활용하면 키가 데이터베이스가 존재하는지 유무를 알 수 있다. 블룸 필터를 통해 데이터가 없다고 판단되었을 경우, 실제로도 찾으려는 데이터가 디스크에 존재하지 않음이 보장되기 때문에 추가적인 디스크 읽기를 아낄 수 있다. 다만, 블룸 필터는 데이터가 있다고 판단했지만 실제 디스크에는 데이터가 없는 False Positive 가 발생할 수 있다.

• 레벨 컴팩션 (Leveled Compaction)

SS 테이블을 여러 단계(level)로 구분한다. 단계가 높아질수록 테이블의 크기가 커진다. 상대적으로 좀 더 새롭고 작은 SS 테이블을 상대적으로 오래됐고 큰 SS 테이블에 연이어 합치는 방식이다. 한 레벨의 SS 테이블 파일들끼리는 키가 겹치지 않는 특징 때문에 데이터를 찾기 위해서 level 수만큼만 쿼리하면 된다.

• Skip List

멤테이블에 데이터를 효율적으로 쓰고 읽기위해 멤테이블을 skip list 로 구현하는 경우도 있다. (Rocks DB, Level DB)

B 트리

LSM 트리 색인이 보편화되고는 있지만 아직 가장 널리 사용되는 색인 구조는 B 트리(B-tree)로 그 구조가 LSM 트리와는 상당히 다르다. 정렬된 키-값 쌍을 유지하기 때문에 범위 질의에 효율적이라는 점 빼고는 사실상 모두 다르다.

• LSM 트리는 수 메가바이트 이상의 가변 크기를 가진 세그먼트 단위로 데이터를 기록하고 이는 항상 순차적이다.
• B 트리는 보통 4KB 고정 크기의 페이지 단위로 읽기 또는 쓰기를 수행한다. 이는 근본적으로 하드웨어와 조금 더 밀접한 관련이 있다.

한 페이지가 B 트리의 루트(root) 페이지로 지정되고 색인에서 키를 찾으려면 이 루트 페이지에서 시작해야한다. 하나의 페지이는 여러개의 키와 하위 페이지의 참조를 포함한다.

최종적으로는 리프(leaf) 페이지에 도달하고 리프 페이지는 각 키의 값이나 값을 찾을 수 있는 페이지의 참조를 갖고있다.

B 트리의 한 페이지가 갖고있는 하위 페이지 참조 수를 분기 계수(branching factor)라고 부른다. 위 그림에서 분기 계수는 6 이다. 대부분의 데이터베이스는 수백 개 정도로 지정한다.

B 트리에 존재하는 키의 값을 갱신하려면 해당 키를 포함하고 있는 리프 페이지를 검색하고 페이지의 해당 키 값을 바꾼 다음 그 페이지를 디스크에 다시 기록한다. 이때 페이지에 대한 모든 참조는 계속 유효하다는 것에 유의하자.

새로운 키-값 쌍을 추가하려면 새로운 키를 포함하는 범위의 페이지를 찾아서 해당 페이지에 추가한다. 해당 페이지에 여유 공간이 없다면 페이지를 두개의 반쪽짜리 페이지로 나누고 상위 페이지가 새로운 두 페이지를 가리킬 수 있게 갱신한다.

위 알고리즘을 통해 B 트리는 계속 균형을 유지할 수 있음을 보장한다. 이는 곧 B 트리는 균형 트리(Balanced Tree)임을 보장하는 말이기도하다. 이 때문에 n 개의 키를 가진 B 트리는 트리의 깊이(height)가 항상 O(log n) 이며, 이는 탐색 시간복잡도가 O(log n) 이라는 뜻이다.

현재 주로 쓰이는 대부분의 데이터베이스는 B 트리의 깊이가 3~4 단계 정도면 충분하므로 탐색을 위해 페이지 참조를 많이 할 필요가 없다.

분기 계수 500, 페이지 크기 4KB인 4단계 B 트리는 256TB 까지 저장할 수 있다.

B 트리의 부가적인 요소들

• 데이터베이스가 고장 상황에서 스스로 복구할 수 있도록 디스크 상에 쓰기 전 로그(write-ahead-log, WAL)라고 하는 데이터 구조를 추가해 B 트리를 구현한다. WAL 은 트리 페이지에 변경된 내용을 적용하기 전에 먼저 변경 내역을 기록해놓은 추가 전용 파일이다. 이 로그는 고장 이후 복귀될 때 일관성 있는 상태로 B 트리를 다시 복원하는 데 사용한다.
• WAL 대신 일부 데이터베이스는 쓰기 시 복사(copy-on-write)를 사용하기도 한다. 변경된 페이지를 다른 위치에 기록하고 부모 페이지의 새로운 버전을 만들어 변경된 자식 페이지를 가리키게 하는 방법이다.
• 일반적으로 페이지는 디스크 상의 어디에나 위치할 수 있지만 이는 범위 스캔에서 비효율적이다. 그래서 B 트리 구현에서 리프 페이지들을 디스크 상에 최대한 연속된 순서로 나타나게끔 시도한다. LSM 트리는 세그먼트 병합 과정에서 세그먼트를 디스크에 다시 쓰기 때문에 키를 연속적으로 가깝게 위치하기가 쉽다.
• 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지게 하여 상위 페이지로 이동하지 않고도 순서대로 키를 스캔할 수 있게한다.
• B 트리의 변형인 프랙탈 트리(fractal tree)의 경우 디스크 IO를 줄이기 위해 Log Structured 개념을 일부 빌렸다.

LSM 트리 vs. B 트리

B 트리가 LSM 트리보다 구현 성숙도가 더 높다고 알려져있고 실제로도 B 트리가 훨씬 많이 쓰이고 있지만, 요즘 LSM 트리도 그 성능적인 특성 때문에 많은 관심을 받고있다.

읽기와 쓰기 속도를 비교하자면, 경험적으로 LSM 트리가 쓰기에서 더 빠른 반면 B 트리는 읽기에서 더 빠르다고 말한다. (그 이유는 뒤에서 설명하겠지만 먼저 곰곰히 생각해보자.)

하지만 위 말을 절대적인 기준으로 여기지는 말자. 벤치마크는 절대 결정적이지 않고 특정 작업부하의 세부사항에 민감하다. 개발자 본인이 구현할 애플리케이션에 필요한 작업부하로 직접 테스트해보고 결정하자.

쓰기 증폭

데이터베이스가 한 번의 쓰기 요청을 처리하는 동안 실제 디스크에는 여러 번의 쓰기를 야기하는 효과를 쓰기 증폭(writde amplification)이라 부른다. 특히 SSD의 경우 블록 쓰기 횟수가 제한되기 때문에 쓰기 증폭은 더욱 중요한 관심사이다.

B 트리는 모든 데이터를 최소한 두 번 기록해야 한다. WAL 로그 한 번과 트리 페이지에 한 번(페이지가 분리되면 또 한 번)이다. 해당 페이지 내 몇 바이트만 바뀌어도 한 번에 전체 페이지를 모두 다시 기록해야 하는 오버헤드도 있다.

LSM 트리 또한 SS 테이블의 반복된 컴팩션, 병합 작업으로 인해 여러 번 데이터를 다시 쓴다.

하지만 LSM 트리가 상대적으로 B 트리보다 쓰기 증폭이 더 낮다. 여러 페이지를 매번 덮어쓰는 것이 아니라 순차적으로 컴팩션된 SS 테이블 파일을 쓰기 때문이다. 이 차이는 특히 자기 디스크에서 중요한데, 자기 디스크는 순차 쓰기가 임의 쓰기보다 훨씬 빠르기 때문이다.

파편화

LSM 트리는 압축률이 좋아서 보통 B 트리보다 디스크에 더 적은 파일을 생성한다. B 트리는 파편화로 인해 사용하지 않는 디스크 공간 일부가 남는다. LSM 트리는 페이지 지향적이지 않고(세그먼트 단위 기록) 주기적으로 SS테이블을 다시 기록하기 때문에 파편화가 훨씬 적다. Leveled Compaction 을 사용하면 특히나 더 그렇다.

성능 예측의 어려움

LSM 트리의 단점은 백그라운드의 컴팩션 과정이 때로는 진행 중인 읽기과 쓰기의 성능에 영향을 준다는 점이다. 물론 저장소 엔진은 컴팩션의 영향이 최대한 없도록 수행하려 하지만 이는 한계가 있다. 디스크에서 비싼 컴팩션 연산이 끝날 때 가지 요청이 대기해야 하는 상황이 발생할 수 있다. 반면 B 트리의 성능은 LSM 트리 보다 예측하기 쉽다.

동시성 제어

B 트리는 각 키가 색인의 한 곳에만 정확하게 존재한다. 반면 LSM 트리의 경우 각기 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있다. 이런 측면 때문에 강력한 트랜잭션 시맨틱(semantic)을 제공해야하는 데이터베이스에는 B 트리가 훨씬 매력적이다.

덮어쓰기

B 트리가 LSM 트리와 크게 다른점 중 하나는 쓰기 동작 시 새로운 데이터를 디스크 상의 페이지에 덮어쓴다는 것이다. 덮어쓰기는 페이지 위치를 변경하지 않는다고 가정하기 때문에, 페이지를 수정하더라도 페이지를 가리키는 모든 참조는 온전하게 남는다. 새로운 데이터를 계속 이어서 쓰고 병합을 수행하는 LSM 트리와는 아주 대조적인 점이다.

B 트리는 많은 데이터베이스 아키텍처에 깊이 뿌리내렸고, 많은 작업부하에 대해 지속적으로 좋은 성능을 제공해왔다. 하지만 요즘 새롭게 생겨나는 데이터베이스에서는 LSM 트리와 같은 Log-Structured 색인이 점점 인기를 얻고 있다.

앞에서도 말했지만 본인이 개발할 애플리케이션에 적합한 저장소 엔진을 선택함에 있어서 시중의 벤치마크를 절대적인 기준으로 여길 필요까지는 없다. 실제 작업부하로 직접 테스트해보고 경험적으로 결정하는 방법도 나쁘지 않다.