Featured image of post B-Tree VS LSM Tree
DB

B-Tree VS LSM Tree

로그 구조 계열 저장소 엔진과 페이지 지향 계열 저장소 엔진 비교

최근 “데이터 중심 애플리케이션 설계“을 읽으면서 데이터베이스의 저장소 엔진의 처리 방식이 성능에 미치는 영향에 대해 구체적으로 알게 되었습니다.

책에서 해당 부분의 도입부를 읽으며, “데이터를 처리하는 방식에 따라 유리한 형태는 다르고 적절한 방법을 선택 해야 한다“와 같은 조언으로 마무리 될 것으로 예상했었는데요

실제로는 각 스토리지 엔진 구조의 장단점을 설명하면서 최근 인기를 끌고 있는것은 로그 구조화 스토리지 엔진이지만, B-Tree 계열은 오랜 기간 발전하면서 많은 작업 부하에도 대응할 수 있다는 내용이 언급하며, 실제 사용 사례에 적합한지 실제로 테스트 해보는 것도 좋은 방법이라는 언급이 있었습니다.

그런 의미로 이 글에서는 페이지 지향 계열 저장소 엔진(B-Tree)과 로그 구조 계열 저장소 엔진(LSM Tree) 두 가지 주요 저장 구조를 비교 해보고, 어떤 식으로 약점을 개선했는지 자세히 살펴보려고 합니다.

두 저장 구조의 기본 원리

책에서는 B-Tree와 로그 구조 계열 저장소 엔진(대표적으로 LSM Tree)의 쓰기 방식의 차이 주목하고 있습니다.

B-Tree 구조

1
2
3
4
5

       [루트 페이지]
       /    |    \
[페이지1] [페이지2] [페이지3]
  / \      / \      / \
... ...  ... ...  ... ...

B-Tree는 MySQL InnoDB와 같은 대부분의 관계형 데이터베이스에서 사용하는 색인 구조입니다. MySQL의 InnoDB 스토리지 엔진은 기본키(PK)를 B-Tree로 관리하는 클러스터드 인덱스 방식을 사용합니다. B-Tree는 다음과 같은 특징을 가집니다.

  • 균형 잡힌 트리 구조:
    • 모든 리프 노드가 같은 깊이에 위치하여 어떤 키에 대해서도 O(log n) 시간 복잡도로 검색 가능
  • 페이지 단위 저장:
    • 데이터를 고정 크기의 페이지 단위로 디스크에 저장
  • 제자리 갱신(in-place update):
    • 데이터를 삽입, 삭제, 수정할 때 해당 페이지의 내용을 직접 덮어쓰는 방식 사용

이러한 특성으로 인해 InnoDB 에서 처리되는 쓰기 작업(INSERT, UPDATE , DELETE)은 B-Tree의 리프 노드에 달려있는 PK를 통해, 물리 기억 장치의 저장된 위치의 내용을 찾고, 해당 내용을 직접 덮어쓰는 방식으로 처리됩니다.

LSM Tree 구조

1
2
3
4
5

[MemTable(메모리)]  →  [SS테이블1(디스크)]  →  [SS테이블2(디스크)]  →  ...
                          ↓                      ↓
                     [컴팩션 프로세스]        [컴팩션 프로세스]
                          ↓                      ↓
                     [병합된 SS테이블]        [병합된 SS테이블]

LSM Tree(Log-Structured Merge Tree)는 Cassandra, RocksDB, MongoDB의 WiredTiger 등 여러 NoSQL 데이터베이스에서 사용하는 저장 구조입니다. 주요 특징은 다음과 같습니다.

  • 로그 기반 쓰기:
    • 데이터 변경 사항을 로그처럼 디스크에 순차적으로 추가
  • 쓰기 버퍼링:
    • 새로운 데이터를 먼저 메모리 내의 멤테이블(MemTable)에 버퍼링
  • 컴팩션 프로세스:
    • 주기적으로 데이터를 병합하고 압축하는 백그라운드 프로세스 실행

로그 기반 쓰기 특성으로 인해 값을 갱신하는 것이 아닌 최신 내용을 디스크에 추가만 하도록 처리되고, 백그라운드 컴팩션 작업을 통해 최신 내용만 남게되는 방식으로 처리됩니다.

성능 특성 비교

쓰기 방식의 차이로 인해 데이터를 관리하는 방식도 달라지게되고, 이에 따라 요청하는 데이터를 처리하는 방식에도 차이가 있습니다.

읽기 성능

B-Tree의 읽기 성능

  • 균형 잡힌 트리 구조로 인해 어떤 키든 일정한 시간 내에 조회 가능 (O(log n))
  • 실제 환경에서는 대부분 3-4단계 내에 데이터 접근 가능
  • 데이터가 정렬된 상태로 유지되어 범위 쿼리와 정렬된 스캔에 효율적
  • 인덱스가 메모리에 캐시될 경우 매우 빠른 접근 가능

위 설명처럼 어떤 키 값도 O(log n) 시간 복잡도로 조회가 가능하고, 정렬된 상태로 키 값이 관리되기 때문에 B+Tree를 사용하게 되는 경우 Range Scan 작업도 빠르게 처리될 수 있습니다.

특히 인덱스가 조회하려는 데이터를 모두 가지고 있는 Covering Index로 처리될 수 있다면, 읽기가 메모리 내에서만 처리될 수 있기 때문에 매우 빠르게 처리될 수 있습니다.

LSM Tree의 읽기 성능

  • 특정 키를 찾기 위해 여러 SS테이블을 차례로 검색해야 할 수 있음
  • 메모리의 멤테이블부터 최신 SS테이블까지 순차적으로 확인 필요
  • 블룸 필터(Bloom Filter)와 같은 최적화를 통해 불필요한 SS테이블 검색을 줄일 수 있음
  • 컴팩션 작업 중에는 일시적으로 읽기 성능이 저하될 수 있음

같은 키를 가지는 새로운 데이터를 갱신하는 것이 아닌 파일에 추가하는 방식으로 처리되기 때문에, 메모리 상의 멤테이블에 데이터가 없다면, 가장 최신 SS테이블부터 해당 키를 가지는 데이터를 찾을 때 까지 모든 SS테이블을 확인해야합니다.

이런 상황은 해당 키를 가지는 데이터가 존재하지 않는 경우 모든 SS테이블에 데이터가 없다는 것을 확인해야하기 때문에 성능이 많이 떨어질 수 있습니다.

이런 경우를 대비하여 블룸 필터를 통해 최악의 경우는 회피하는 방식으로 최적화가 되어있습니다.

블룸 필터 Bloom filter
원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료구조.
어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것은 가능하지만, 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로 원소가 집합에 속하는 부정 오류는 절대 발생하지 않는다.

쓰기 성능

B-Tree의 쓰기 성능

  • 데이터 수정 시 해당 페이지를 직접 덮어써야 함 (무작위 I/O 발생)
  • 균형 유지를 위한 페이지 분할 작업이 발생할 수 있음
  • 인덱스가 여러 개인 경우 모든 관련 인덱스 업데이트 필요
  • WAL(Write-Ahead Log)을 통한 안전한 데이터 변경으로 추가적인 I/O 발생

위에서 살짝 언급한 것 처럼 데이터 수정이 필요할 경우 PK를 통해서 해당 페이지를 찾고 직접 덮어 써야 하기 때문에 무작위 I/O가 많이 발생하게 됩니다.

그리고 데이터베이스에 따라 테이블에 여러 개의 보조 인덱스를 추가하는 경우 해당 인덱스(B-Tree) 갱신을 위해 추가적인 작업이 발생할 수 있습니다.

또한 데이터 갱신 중 비정상적인 처리(종료)로 인해 데이터 변경 요청이 손실되는 것을 막기 위해 추가적인 쓰기 작업이 추가되는 경우도 있습니다(WAL).

LSM Tree의 쓰기 성능

  • 데이터를 순차적으로 추가하므로 디스크 쓰기 효율이 높음
  • 메모리 버퍼링을 통해 디스크 I/O 횟수를 크게 줄임
  • 기존 데이터를 덮어쓰지 않으므로 페이지 분할 같은 구조 재조정이 필요 없음
  • 백그라운드 컴팩션이 필요하지만 쓰기 성능에 직접적인 영향은 적음

기본적으로 데이터 순차 쓰기 방식으로 처리되기 때문에 운영체제 수준에서 최적화가 잘 되어 Random I/O보다 훨씬 빠르게 처리될 수 있습니다.

그리고 경우에 따라서 이 마저도 효과적으로 수행할 수 있도록 버퍼링을 통해 데이터를 모아 처리하는 방식으로 최적화 하기도 합니다.

실제 구현에서의 최적화 기법

지금까지의 내용만 본다면, B-Tree 기반 데이터베이스는 쓰기에 불리하고 로그 기반 데이터베이스는 읽기에 불리한 것 처럼 느껴집니다. (사실 일반적으로 그렇게 생각되는 경우가 많은 것 같습니다.)

그렇지만 불리한 성능을 개선하기 위해 여러 최적화가 적용되어 있습니다.

B-Tree 기반 시스템의 주요 최적화 (InnoDB 사례)

MySQL의 InnoDB 스토리지 엔진은 데이터를 갱신해야함으로 발생하는 Random I/O로 인한 병목을 개선하기 위해 여러 아이디어를 적용했습니다.

InnoDB 아키텍처

기본적으로 InnoDB 스토리지 엔진은 버퍼풀을 통해 메모리 영역에 당장 활용되어야 하는 데이터들을 캐싱하고, 변경 내용들을 버퍼링(더티 페이지)하여 주기적인 플러싱(flushing)으로 백그라운드 작업을 통해 디스크에 실제로 반영하게 됩니다.

이러한 내용들을 요약해보면 아래와 같습니다.

버퍼링과 지연 쓰기

  • 버퍼풀:
    • 자주 접근하는 데이터 페이지를 메모리에 캐싱하여 I/O 감소
  • 변경 버퍼(Change Buffer):
    • 보조 인덱스 변경 사항을 메모리에 버퍼링하여 나중에 적용
  • 쓰기 지연:
    • 변경 사항을 즉시 디스크에 쓰지 않고 더티 페이지로 유지하다가 효율적으로 일괄 처리

로깅과 복구 최적화

  • 리두 로그:
    • 변경 사항을 순차적인 로그에 먼저 기록하여 I/O 효율성 향상
  • 그룹 커밋:
    • 여러 트랜잭션의 커밋을 묶어 처리하여 I/O 오버헤드 감소
  • 이중 쓰기 버퍼:
    • 데이터 무결성을 보장하면서도 순차적 쓰기를 통해 I/O 효율성 향상

동시성 향상 기법

  • MVCC(다중 버전 동시성 제어):
    • 읽기 작업이 쓰기 작업을 차단하지 않도록 하여 전반적인 동시성 향상
  • 버퍼풀 인스턴스 분할:
    • 내부 잠금 경합을 줄이고 병렬 처리 효율 향상
  • 백그라운드 처리:
    • 페이지 클리너 스레드가 더티 페이지를 비동기적으로 디스크에 기록

LSM Tree 기반 시스템의 주요 최적화 (Cassandra 사례)

LSM Tree 기반 시스템 처리

카산드라는 아래와 같은 순서로 쓰기 작업이 수행됩니다.

  • 커밋 로그에 데이터 기록하기
  • 멤테이블에 데이터 쓰기
  • 멤테이블에서 데이터 플러시하기
  • SSTables의 디스크에 데이터 저장

처음 커밋 로그에 데이터를(내구성 보장을 위해) 기록하고 멤테이블에 데이터를 쓰게되는데, 멤테이블은 쓰기를 버퍼링하고 데이터 파티션을 캐싱하는 역할도 함께 수행하게 됩니다.

멤테이블은 지정한 크기에 도달할 때 까지 정렬된 순서를 유지하며 쓰기를 캐싱하고, 한계에 도달하면 디스크에 플러시되어 SS테이블로 저장됩니다.

SS테이블은 변경 불가능하므로 데이터가 업데이트되거나 삭제될 때 이전 데이터를 삽입 또는 업데이트로 덮어쓰거나 SS테이블에서 제거하지 않습니다.

대신 새 타임스탬프가 있는 업데이트된 데이터로 새 SS테이블이 만들어지고 이전 SS테이블은 삭제 표시가 됩니다. (삭제된 데이터 조각을 툼스톤이라고 함)

컴팩션 전략 최적화

이러한 특성으로 인해 여러 버전의 행을 여러 SS테이블에 기록할 수 있고, SS테이블이 많아지면 전체 행을 검색하기 위해 점점 더 많은 SS테이블에 액세스해야 할 수 있습니다.

이로 인해 읽기 성능이 떨어지는 것을 막기 위해 주기적으로 SS테이블을 병합하고 오래된 데이터를 폐기하는데, 이를 컴팩션이라고 합니다.

컴팩션은 백그라운드로 수행되긴 하지만 쓰기 작업을 발생시키므로 이를 최적화하는 방법들이 있습니다.

  • 레벨 컴팩션(Leveled Compaction):
    • 데이터를 여러 레벨로 구성하여 컴팩션 비용 분산
  • 사이즈 단계별 컴팩션(Size-Tiered Compaction):
    • 비슷한 크기의 SS테이블끼리 병합하여 효율성 향상
  • 컴팩션 스로틀링:
    • 컴팩션이 다른 작업에 미치는 영향을 제한하여 일관된 성능 유지

읽기 성능 향상 기법

컴팩션 외에도 읽기 성능을 향상시키는 기법들도 존재합니다.

  • 블룸 필터:
    • 특정 키가 SS테이블에 없다는 것을 효율적으로 확인하여 불필요한 디스크 접근 감소
  • 파티셔닝:
    • 데이터를 파티션으로 나누어 병렬 처리 및 검색 범위 축소
  • 인덱스 요약(Index Summary):
    • 각 SS테이블의 키 범위 정보를 메모리에 유지하여 검색 효율 향상

쓰기 최적화

아래와 같은 방법들이 도움이 될 수 있습니다.

  • WAL 최적화:
    • 로그 압축, 그룹 커밋 등을 통한 로깅 효율성 향상
  • 멤테이블 구현 최적화:
    • 효율적인 자료구조(스킵 리스트 등) 사용으로 메모리 내 작업 속도 향상
  • 직접 I/O:
    • 운영체제 캐시를 우회하여 데이터베이스가 자체적으로 메모리 관리 가능

어떤 상황에 어떤 저장 구조가 적합한가?

완벽하게 적합한지 결정하기는 어렵지만, 일반적으로 아래와 같은 상황에 맞는 저장 구조를 활용하면 좋다고 알려져 있습니다.

B-Tree가 적합한 상황

  • 복잡한 트랜잭션이 필요한 경우:
    • ACID 속성이 중요한 금융, 전자상거래 애플리케이션
  • 다양한 인덱싱과 복잡한 쿼리가 필요한 경우:
    • 다중 인덱스, 조인, 집계 함수 등을 활용하는 분석 시스템
  • 읽기 작업이 쓰기보다 훨씬 많은 경우:
    • 데이터 변경이 적고 조회가 빈번한 시스템
  • 데이터 크기가 메모리에 대부분 캐싱될 수 있는 경우:
    • 데이터셋이 상대적으로 작은 시스템

LSM Tree가 적합한 상황

  • 대규모 쓰기 워크로드:
    • 로그 수집, IoT 센서 데이터, 클릭스트림 추적 등 초당 수만에서 수십만 건의 삽입이 필요한 경우
  • 스키마리스 데이터 모델이 필요한 경우:
    • 빠르게 변화하는 비즈니스 요구사항에 대응해야 하는 시스템
  • 수평적 확장성이 중요한 경우:
    • 샤딩을 통해 쉽게 확장해야 하는 분산 시스템
  • 압축률이 중요한 경우:
    • 저장 공간 효율성이 중요한 대용량 데이터 시스템

선택 시 고려사항

적합한 저장 구조를 선택할 때 아래와 같은 내용을 고려한다면 조금 더 쉽게 결정할 수 있습니다.

워크로드 특성

  • 읽기/쓰기 비율:
    • 읽기가 주로 필요하면 B-Tree, 쓰기가 많으면 LSM Tree 고려
  • 쿼리 패턴:
    • 복잡한 조인과 트랜잭션이 필요하면 B-Tree, 단순 키-값 조회가 주된 작업이면 LSM Tree 적합
  • 데이터 크기와 성장 속도:
    • 대용량 데이터와 빠른 성장이 예상되면 LSM Tree의 압축률과 확장성이 유리

하드웨어 환경

  • 스토리지 유형:
    • HDD 환경에서는 순차적 I/O에 최적화된 LSM Tree가 유리, SSD에서는 차이가 줄어듦
  • 메모리 용량:
    • 대용량 메모리가 가능한 환경에서는 B-Tree의 캐싱 효과가 극대화됨
  • CPU 자원:
    • LSM Tree의 컴팩션은 추가 CPU 리소스를 소모하므로 CPU 제한 환경에서는 고려 필요

실제 벤치마크 테스트의 중요성

이론적인 성능 특성은 중요한 지침이 되지만, 실제 운영 환경에서는 예상과 다른 결과가 나올 수 있습니다.

  • 실제 데이터와 패턴 사용:
    • 실제 애플리케이션의 데이터 분포와 쿼리 패턴을 반영한 벤치마크 수행
  • 확장성 테스트:
    • 현재 데이터 크기뿐만 아니라 예상되는 미래 데이터 크기에서도 테스트
  • 장기 실행 테스트:
    • 시간이 지남에 따른 성능 변화(단편화, 컴팩션 오버헤드 등) 평가

결론

B-Tree와 LSM Tree는 각각 고유한 장단점을 가진 저장 구조입니다. 전통적으로 B-Tree는 읽기에, LSM Tree는 쓰기에 최적화되어 있다고 여겨지고 일반적으로 그렇지만, 현대적인 데이터베이스 엔진들은 다양한 최적화를 통해 이러한 문제들을 보완하고 있습니다.

이전 직장에서도 다양한 유형의 워크로드를 RDBMS 만으로도 처리했었고, 쓰기 작업이 불리하다고 여겨지는 RDBMS가 실제 사용했을 때 큰 문제가 발생하지 않는 이유를 살펴보니, 극단적으로 많은 처리가 필요한 상황이 아니라면 “적합한 데이터베이스 선택"과 같은 문제는 사소한 문제인걸까? 라는 생각도 들었습니다.

더 나아가서 새로운 기술들을 적용하는 것 자체가 대부분의 상황에서 불필요할 수도 있겠다는 회의감도 새삼스럽게 드는 것 같습니다.

이러한 고민을 적용해 볼 수 있는 곳에서 꼭 일해보고 싶네요! 끝까지 읽어주셔서 감사합니다😊