[데이터 중심 애플리케이션 설계] 3장 2. LSM 트리와 B 트리

해시 색인의 한계를 없앤 색인 구조를 살펴보자.

SS 테이블과 LSM 트리

그림 3-3에서 로그 구조화 저장소 세그먼트는 키-값 쌍의 연속이다.

여기에 일련의 키-값 쌍을 키로 정렬해보자. 이런 형식을 정렬된 문자열 테이블 또는 SS테이블 이라고 부른다.

 

<해시 색인을 가진 로그 세그먼트>보다 나은 <SS 테이블>의 장점

• 세그먼트가 정렬되어 있기 때문에 병합 정렬이 가능하다.
• 특정 키를 찾기 위해서 메모리에 모든 키의 색인을 유지할 필요가 없다. 이미 정렬이 되어있기 때문에 키 B의 오프셋을 몰라도 A와 C의 오프셋 위치만 알면 그 사이에서 B를 찾으면 된다.
• 읽기 요청은 해당 레코드들을 블록으로 압축할 수 있다. 디스크 공간을 절약하고 I/O대역폭 사용도 줄일 수 있다.

 

디스크 상에 정렬된 구조를 유지하는 일은 가능하지만, 메모리에 유지하는 편이 훨씬 쉽다.

임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 읽는 과정

쓰기: '멤테이블(인메모리) 균형 트리 데이터 구조에 추가 → 멤테이블이 임곗값보다 커지면 SS테이블 파일로 디스크에 기록' (트리가 이미 키로 정렬된 상태라 효율적)

읽기: '멤테이블에서 키 찾기 → 디스크 상의 최신 세그먼트에서 찾기’

(백그라운드) 가끔 병합 + 컴팩션 과정 수행

 

하지만 멤테이블에 쓰기 과정 중, 데이터베이스가 고장나면 멤테이블의 쓰기 데이터가 손실된다.

따라서 ‘분리된 쓰기 데이터(로그 파일)를 디스크 상에 유지 → 멤테이블을 SS테이블로 디스크에 저장 → 디스크에서 로그 파일 제거'와 같은 순서로 데이터의 손실을 막는다.

 

LSM 트리

위 처럼 SS 테이블의 형식으로 디스크에 key-value 데이터를 저장하는 색인 방식을 LSM 트리라고 부른다. LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS 테이블을 병합하는 것이다. 데이터가 정렬된 순서로 저장돼 있다면 범위 질의를 효율적으로 줄일 수 있다.

 

LSM 트리의 성능 최적화 방법

1. 블룸 필터(Bloom filter) 추가

                - LSM 트리 알고리즘은 데이터베이스에 존재하지 않는 키를 찾을 경우 느릴 수 있다. (멤테이블을을 확인하고 가장 오래된 세그먼트까지 거슬러 올라가야 한다.)

                - 이럴 경우, 블룸 필터를 추가하면 키가 데이터베이스에 존재하지 않음을 알려준다.

 

2. 사이즈 계층 컴팩션과 레벨 컴팩션

SS 테이블을 압축하고 병합하는 순서와 시기를 결정하는 전략

   2-1. 사이즈 계층 컴팩션(size-tiered compaction)

                - 좀 더 새롭고 작은 SS테이블을 오래되고 큰 SS테이블에 병합

   2-2. 레벨 컴팩션(leveled compaction)

                - SS 테이블은 여러 단계(level)로 구분되고 단계가 높아질수록 테이블의 크기가 커진다.

                - 상대적으로 좀 더 새롭고 작은 SS 테이블을 상대적으로 오래됐고 큰 SS 테이블에 연이어 병합한다. 한 레벨의 SS 테이블 파일들끼리는 키가 겹치지 않는 특징 때문에 데이터를 찾기 위해서 level 수만큼만 쿼리하면 된다.

 

 

B 트리

LSM 트리 색인이 보편화되고는 있지만 아직 가장 널리 사용되는 색인 구조는 B 트리이다.

LSM 트리와 B 트리의 공통점

• 정렬된 키-값 쌍을 유지하기 때문에 범위 질의에 효율적이라는 점만 비슷하다.

LSM 트리와 B 트리의 차이점

• LSM 트리는 데이터베이스를 가변 크기의 세그먼트로 나누고 순차적으로 기록한다.
• B 트리는 고정 크기(4KB) 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기/쓰기를 한다.

출처 : https://devpress.csdn.net/mysqldb/62e3a07d6bd6933f4e7dc3d6.html

B트리는 트리라는 단어처럼 맨 위의 루트 페이지와 루트 페이지가 참조하는 여러 리프 페이지로 구성되어 있다. 각 페이지는 하위 페이지들의 주소(ref)를 가지고 있고 하위 페이지를 참조하는 개수를 분기계수라고 한다. 색인에서 키를 찾으려면 루트 페이지에서 시작한다.

B 트리에서 키의 값을 갱신하려면?

해당 키를 포함하고 있는 리프 페이지를 검색 → 페이지의 해당 키 값을 바꾸기 → 그 페이지를 디스크에 다시 기록

B 트리에서 키를 추가하려면?

새로운 키의 범위인 페이지를 찾아 추가

만약 페이지에 새로운 키를 추가할 여유 공간이 없다면, 기존 페이지를 두 페이지로 나누고 상위 페이지가 이 두 페이지를 참조하도록 갱신

⇒ 균형을 유지한다.

 

신뢰할 수 있는 B트리 만들기

B트리의 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다.

B트리의 한계와 해결책

• 고아 페이지 발생
  • 삽입이 많아 페이지를 나누는 상황에서 데이터베이스가 고장나면 부모관계가 없는 고아 페이지가 발생할 수 있다.
  • ⇒ 디스크에 쓰기 전 로그(WAL = 재실행 로그)를 추가해 모든 B트리의 변경 사항을 기록한다. 데이터베이스가 복구될 때 B트리를 일관성있는 상태로 복원하는 데 사용한다.

• 다중 스레드 접근에 대비한 동시성 제어
  • 다중 스레드로 같은 페이지를 갱신하는 작업은 일관성을 깨뜨릴 수 있다.
  • ⇒ 래치(latch)(가벼운 lock)로 트리의 데이터 구조를 보호한다.

 

B 트리 최적화 기법

• 쓰기 전 로그(WAL) 대신 일부 데이터베이스는 쓰기 시 복사(copy-on-write)를 사용한다. 변경된 페이지를 다른 위치에 기록하고 부모 페이지의 새로운 버전을 만들어 변경된 자식 페이지를 가리키게 하는 방법이다.
• 페이지에 키를 축약해 쓰면 공간을 줄일 수 있다.
• 일반적으로 페이지는 디스크 상의 어디에나 위치할 수 있지만 이는 범위 스캔에서 비효율적이다. 따라서 B 트리 구현에서 리프 페이지를 디스크 상에 최대한 연속된 순서로 나타나게끔 시도한다. (+ LSM 트리는 세그먼트 병합 과정에서 세그먼트를 디스크에 다시 쓰기 때문에 키를 연속적으로 가깝게 위치하기가 쉽다.)

 

LSM 트리와 비교

LSM 트리는 쓰기에서 더 빠른 반면 B 트리는 읽기에서 더 빠르다.

 

LSM 트리 장점: 쓰기 성능 비용

B트리 색인은 쓰기 전 로그와 트리 페이지에 한번씩 기록해야 한다. LSM 트리는 SS테이블의 반복된 컴팩션과 병합으로 인해 여러 번 데이터를 다시 쓴다. (이렇게 쓰기 한번이 디스크에 여러 번 쓰기를 야기할 때를 쓰기 증폭이라 한다.)

하지만 LSM 트리가 B 트리보다 쓰기 증폭이 낮고 여러 페이지를 덮어쓰는 것이 아니라 순차적으로 SS 테이블 파일을 쓰기 때문에 B트리보다 쓰기 처리량이 높다.

 

LSM 트리 장점: 압축률

LSM 트리는 압축률이 좋아 B 트리보다 디스크에 더 적은 파일을 생성한다. LSM 트리는 페이지 지향적이지 않고 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하기 때문에 저장소 오버헤드가 더 낮다.

 

LSM 트리 단점: 컴팩션의 성능 예측 어려움

LSM 트리의 컴팩션 과정은 때로 진행 중인 읽기, 쓰기 성능에 영향을 준다. 디스크에서 비싼 컴팩션 연산을 하는 동안 요청이 대기해야 하는 상황이 발생할 수 있다. 이와 반면에 B 트리의 성능은 예측하기 쉽다.

 

LSM 트리 단점: 컴팩션의 높은 쓰기 처리량

빈 데이터베이스에 쓰는 경우 전체 디스크 대역폭은 초기 쓰기만을 위해 사용할 수 있지만, 데이터베이스가 점점 커질수록 컴팩션을 위해 더 많은 디스크 대역폭이 필요하다.

 

B 트리 장점: 동시성 제어

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

 

용어정리

단일 칼럼 색인 (하나의 키만 값에 대응하는 색인들)

보조 색인: 조인을 수행하는데 결정적인 역할을 하며, 기본키 색인과의 차이는 키가 고유하지 않다는 점이다.

힙 파일: 색인에서 키는 질의가 검색하는 대상, 값은 질문의 실제 로우거나 다른 곳에 저장된 로우를 가리키는 참조이다. 후자의 경우 로우가 저장된 곳을 힙 파일이라 한다.

클러스터드 색인: 색인 안에 모든 로우 데이터를 저장하기

비클러스터드 색인: 색인 안에 데이터의 참조만 저장하기

커버링 색인 || 포괄열이 있는 색인: 색인 안에 테이블의 칼럼 일부를 저장한다.

 

다중 칼럼 색인 (테이블의 다중 칼럼에 동시에 질의)

결합 색인: 하나의 칼럼에 다른 칼럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순히 결합한다. ex. (성, 이름)-key, 전화번호 -value

다차원 색인: 한 번에 여러 칼럼에 질의한다. ex. 위도와 경도 / 날짜와 온도 질의

 

유사한 키에 대해 질의

전문 검색 || 퍼지검색: 특정 단어에 대해 동의어로 질의를 확장한다.