LSM 트리

LSM 트리는 데이터를 제자리에서 고치지 않는 저장 구조입니다. 새 항목은 먼저 메모리에 있는 작은 트리에 들어갑니다. 그 트리가 정해둔 크기에 닿으면 쌓인 항목의 연속 구간이 디스크에 있는 큰 트리로 병합됩니다. 이 병합은 뒤에서 조금씩 계속 이어집니다.

상세

LSM 트리(Log-Structured Merge-tree, 로그 구조 병합 트리)는 오랜 기간에 걸쳐 레코드 삽입과 삭제가 높은 비율로 일어나는 파일에 낮은 비용으로 인덱스를 대주려고 설계된 디스크 기반 자료구조입니다.

제자리에서 고치지 않는 까닭은 인덱스를 실시간으로 유지하는 값에 있습니다. 원 논문은 B-tree 같은 표준 디스크 인덱스 구조가 이런 인덱스를 실시간으로 유지하면 트랜잭션의 입출력 비용을 사실상 두 배로 만든다고 적습니다. 전체 시스템 비용은 최대 50퍼센트까지 올라갑니다.

그래서 LSM 트리는 인덱스 변경을 미루고 모으는 알고리즘을 씁니다. 모인 변경은 메모리에 있는 컴포넌트에서 하나 이상의 디스크 컴포넌트로 단계적으로 흘러내립니다. 원 논문은 이 흘러내림을 병합 정렬을 떠올리게 하는 방식이라고 적습니다.

컴포넌트가 둘인 LSM 트리는 전부 메모리에 사는 작은 컴포넌트와 디스크에 사는 큰 컴포넌트로 나뉩니다. 앞의 것을 C0 트리, 뒤의 것을 C1 트리라고 부릅니다. C1 은 디스크에 있지만 자주 참조되는 페이지 노드는 평소처럼 메모리 버퍼에 남습니다. 그래서 C1 의 인기 있는 상위 디렉토리 노드는 메모리에 있다고 봐도 됩니다.

flowchart TD
    subgraph MEM["메모리"]
        direction TB
        subgraph C0G["C0 트리 · 전부 메모리에 산다"]
            direction TB
            C0R["C0 루트"]
            C0R --> C0L1["C0 리프 노드"]
            C0R --> C0L2["C0 리프 노드"]
            C0R --> C0L3["C0 리프 노드"]
            C0R --> C0L4["C0 리프 노드"]
        end
        subgraph BUFG["메모리 버퍼 · 자주 참조되는 C1 노드가 여기 남는다"]
            direction TB
            C1R["C1 루트 · 단일 페이지"]
            C1R --> C1D1["C1 상위 디렉토리 노드"]
            C1R --> C1D2["C1 상위 디렉토리 노드"]
        end
    end
    subgraph DISKG["디스크 · C1 트리가 사는 곳"]
        direction TB
        C1F1["C1 리프 노드"]
        C1F2["C1 리프 노드"]
        C1F3["C1 리프 노드"]
        C1F4["C1 리프 노드"]
    end
    C1D1 --> C1F1
    C1D1 --> C1F2
    C1D2 --> C1F3
    C1D2 --> C1F4
    C0G -->|"rolling merge · 항목의 연속 구간"| DISKG

그림에서 C0 트리는 메모리 상자 안에서 닫혀 있습니다. C1 트리는 디스크에 살지만 그 상위 디렉토리 노드가 메모리 버퍼에 남아 두 곳에 걸칩니다. 그래서 조회가 C1 을 뒤질 때도 위쪽 디렉토리 레벨은 대개 디스크를 건드리지 않고 지나갑니다.

이 과정에서 모든 인덱스 값은 조회에 계속 열려 있습니다. 아주 짧은 락 구간만 예외입니다. 조회는 메모리 컴포넌트에서 찾거나 디스크 컴포넌트 가운데 하나에서 찾습니다.

원 논문은 이 구조가 어디에 맞는지도 함께 못 박습니다. 전통적 접근 방식으로 삽입할 때 드는 디스크 암 비용이 저장 매체 비용을 압도하는 영역에서 비용 대비 성능이 나아집니다. 반대로 즉시 응답이 필요한 인덱스 조회는 경우에 따라 입출력 효율을 잃습니다. 그래서 LSM 트리는 항목을 꺼내 오는 조회보다 인덱스 삽입이 더 흔한 곳에서 가장 쓸모가 있습니다. 원 논문은 이력 테이블과 로그 파일이 그런 성질을 흔히 가지는 것으로 보인다고 적습니다.

복잡도

원 논문은 이 구조의 비용을 차수 표기가 아니라 디스크 입출력 비용 공식으로 냅니다. 그래서 세는 대상을 먼저 밝힙니다.

M 은 항목 크기와 두 컴포넌트 리프 레벨의 크기 비로 정해집니다.

M = (Sp / Se) · (S0 / (S0 + S1))

C0 가 C1 에 견주어 클수록 M 이 커집니다. 원 논문은 S1 이 S0 의 40배이고 디스크 페이지당 항목 수 Sp/Se 가 200 인 구현을 흔한 예로 듭니다. 그러면 M 은 5 입니다.

B-tree 삽입과의 비용비

대조군이 되는 B-tree 삽입 비용은 다음과 같습니다.

COSTB-ins = COSTP · (De + 1)

리프 레벨 페이지까지 키 값 검색으로 내려가는 데 De 번의 입출력이 듭니다. 그 리프 페이지를 고쳐 내려쓰는 데 한 번이 더 듭니다. 이 계산은 잇따르는 삽입이 리프 레벨의 랜덤한 자리로 간다고 가정합니다. 키 값이 계속 커지는 오른쪽 삽입은 이 가정을 따르지 않고, 그 경우는 B-tree 가 이미 상당히 효율적으로 처리한다고 원 논문이 적습니다.

두 값의 비는 이렇게 갈립니다.

COSTLSM-ins / COSTB-ins = K1 · (COSTπ / COSTP) · (1 / M)

K1 은 2/(De + 1) 로 거의 상수입니다. 논문이 다루는 인덱스 크기에서는 대략 0.67 입니다. 이 식은 두 배치 효과가 각각 비용비에 곧바로 비례한다는 것을 보입니다. 하나는 멀티 페이지 블록 안의 페이지 입출력과 랜덤 페이지 입출력의 비용비이고, 다른 하나는 1/M 입니다. 원 논문은 이 두 비의 곱이 보통 거의 두 자릿수, 곧 100배에 가까운 비용비 개선을 준다고 적습니다. 다만 그런 개선은 B-tree 로 뒀을 때 인덱스의 온도가 비교적 높은 영역에서만 가능하다고 못 박습니다.

최악이 오는 자리

최악은 조회 쪽에 옵니다. 컴포넌트를 K+1 개로 늘리면 즉시 응답이 필요한 인덱스 조회가 때때로 모든 컴포넌트 트리에서 꺼내 와야 합니다. 컴포넌트를 늘리는 데는 추가 rolling merge 를 도는 CPU(Central Processing Unit, 중앙처리장치) 비용과 그 병합의 노드를 버퍼링하는 메모리 비용도 붙습니다. 원 논문은 이런 사정이 적절한 컴포넌트 개수에 강한 제약을 건다고 적습니다. 실무에서 보게 될 컴포넌트는 아마 세 개가 최대일 것이라고도 적습니다.

원 논문은 조회를 평균과 최악으로 갈라 적지 않습니다. 컴포넌트를 하나씩 훑는다는 것, 그리고 그 개수가 실무에서 세 개를 넘기 어렵다는 것까지가 원 논문이 대는 값입니다.

예시

이 구조의 부품을 부르는 이름은 구현마다 다릅니다. LevelDB 공식 구현 문서는 메모리에 있는 사본을 memtable 이라 부르고, 그것을 내려쓴 정렬된 파일을 sstable, 레벨 사이에서 파일을 합치는 일을 컴팩션이라고 부릅니다.

LevelDB 의 레벨과 컴팩션

로그 파일 *.log 가 최근 갱신을 순서대로 담습니다. 갱신은 현재 로그 파일 끝에 붙습니다. 로그 파일이 미리 정한 크기에 닿으면 정렬된 테이블로 변환되고 새 로그 파일이 만들어집니다. 현재 로그 파일의 사본은 memtable 이라는 메모리 구조로 유지됩니다. 이 사본은 모든 읽기에서 참조됩니다. 그래서 읽기가 기록된 갱신을 전부 반영합니다.

로그 파일이 정해진 크기를 넘으면 새 memtable 과 새 로그 파일을 만들어 이후 갱신을 그쪽으로 보냅니다. 백그라운드에서는 네 걸음이 돕니다. 이전 memtable 의 내용을 sstable 로 쓰고, memtable 을 버리고, 옛 로그 파일과 옛 memtable 을 지우고, 새 sstable 을 레벨 0 에 넣습니다.

flowchart TD
    MT["memtable · 메모리"]
    MT -->|"sstable 로 내려쓴다"| L0G
    subgraph L0G["레벨 0 · 파일끼리 키 범위가 겹칠 수 있다(특례)"]
        direction TD
        S01["sstable"]
        S02["sstable"]
        S03["sstable"]
    end
    subgraph L1G["레벨 1 · 크기 한계가 레벨 0 의 열 배"]
        direction TD
        S11["sstable"]
        S12["sstable"]
        S13["sstable"]
    end
    subgraph L2G["레벨 2 · 크기 한계가 레벨 1 의 열 배"]
        direction TD
        S21["sstable"]
        S22["sstable"]
        S23["sstable"]
    end
    L0G -->|"컴팩션"| L1G
    L1G -->|"컴팩션"| L2G

레벨은 아래로 갈수록 크기 한계가 열 배씩 커지는 계단입니다. memtable 이 내려앉는 자리는 언제나 맨 위 레벨 0 이고, 아래 레벨로는 컴팩션이 옮깁니다.

레벨 L 의 크기가 한계를 넘으면 백그라운드 스레드가 그 레벨을 컴팩션합니다. 컴팩션은 레벨 L 에서 파일 하나를 고르고, 다음 레벨 L+1 에서 겹치는 파일을 전부 고릅니다. 레벨 L 파일이 레벨 L+1 파일의 일부만 겹치더라도 그 L+1 파일 전체가 컴팩션 입력이 되고 컴팩션 뒤에 버려집니다. 레벨 0 은 특별합니다. 그 안의 파일끼리 서로 겹칠 수 있어서, 레벨 0 에서 레벨 1 로 가는 컴팩션은 서로 겹치는 레벨 0 파일을 여러 개 고를 수 있습니다.

컴팩션은 고른 파일들의 내용을 합쳐 레벨 L+1 파일의 열을 만듭니다. 현재 출력 파일이 목표 파일 크기 2MB 에 닿으면 새 레벨 L+1 파일로 넘어갑니다. 현재 출력 파일의 키 범위가 레벨 L+2 파일 열 개보다 많이 겹칠 만큼 커져도 새 출력 파일로 넘어갑니다. 뒤의 규칙은 나중에 그 레벨 L+1 파일을 컴팩션할 때 레벨 L+2 에서 너무 많은 데이터를 끌어오지 않게 합니다. 옛 파일은 버려지고 새 파일이 서비스 상태에 들어갑니다.

특정 레벨의 컴팩션은 키 공간을 돌아가며 진행합니다. 레벨마다 마지막 컴팩션이 끝난 키를 기억해 두고, 다음 컴팩션은 그 키 뒤에서 시작하는 첫 파일을 고릅니다. 그런 파일이 없으면 키 공간의 처음으로 돌아갑니다.

RocksDB 의 write_buffer_size

cf_options.write_buffer_size = 64 << 20;

컬럼 패밀리에 쓰이는 최대 쓰기 버퍼 크기입니다. 정렬된 온디스크 파일로 변환하기 전에 메모리에 쌓아 둘 데이터의 양을 나타냅니다. 디스크의 정렬되지 않은 로그가 그것을 받쳐 줍니다. RocksDB 공식 위키는 기본값을 64MB 로 적습니다. 같은 문서는 최악의 경우 메모리 사용량의 두 배를 예산으로 잡으라고 적습니다. 그만한 메모리가 없으면 이 값을 줄여야 한다고 적습니다. 그렇지 않다면 이 옵션은 바꾸지 않기를 권한다고도 적습니다.

동작

flowchart TD
    A["새 항목이 들어온다"] --> B["순차 로그 파일에 복구용 레코드를 적는다"]
    B --> C["메모리의 C0 트리에 인덱스 항목을 넣는다"]
    C --> D{"C0 가 임계 크기에 닿았나"}
    D -->|아니오| A
    D -->|예| E["rolling merge 가 C0 의 연속 구간을 C1 로 병합한다"]
    E --> A

새 이력 행이 생길 때마다 이 삽입을 복구할 로그 레코드가 평소처럼 순차 로그 파일에 먼저 적힙니다. 그다음 그 행의 인덱스 항목이 메모리에 사는 C0 트리에 들어갑니다. C0 트리에 인덱스 항목을 넣는 연산에는 입출력 비용이 없습니다. 항목은 시간이 지나면서 디스크의 C1 트리로 이주합니다. C0 의 항목이 C1 으로 나가기까지는 지연이 있어서, 크래시 전에 디스크로 못 나간 인덱스 항목은 복구 대상이 됩니다.

삽입의 결과로 C0 트리가 할당된 최대치에 가까운 임계 크기에 닿을 때마다, 진행 중인 rolling merge 가 C0 트리에서 연속된 항목 구간을 지우고 그것을 디스크의 C1 트리로 병합합니다.

rolling merge 한 걸음

C1 트리는 순차 디스크 접근에 맞춰져 있습니다. 노드가 100퍼센트 차 있고, 루트 아래 각 레벨의 단일 페이지 노드들이 연속된 멀티 페이지 디스크 블록에 묶여 있습니다. 루트 아래 노드를 담는 멀티 페이지 블록 크기로는 256KB 를 상정합니다. 루트 노드는 정의상 언제나 단일 페이지입니다. 멀티 페이지 블록 입출력은 rolling merge 와 긴 범위 조회에 쓰이고, 단일 페이지 노드는 인덱스 조회에 쓰여 버퍼 요구를 줄입니다.

rolling merge 는 일련의 merge step 으로 움직입니다.

1. C1 트리의 리프 노드를 담은 멀티 페이지 블록을 읽으면 C1 의 항목 범위가 버퍼에 올라옵니다
2. 각 merge step 은 그 블록에 버퍼링된 C1 리프 노드 하나를 읽고, C0 트리의 리프 레벨에서 가져온 항목과 병합해 새 C1 리프 노드를 만듭니다. 이때 C0 의 크기가 줄어듭니다
3. 병합 전의 옛 C1 노드를 담은 버퍼 블록을 emptying block 이라 부르고, 새 리프 노드는 filling block 이라는 다른 버퍼 블록에 씁니다
4. filling block 이 새로 병합된 리프 노드로 꽉 차면 디스크의 새 빈 영역에 씁니다

block-beta
columns 4
  EB["emptying block · 256KB · 병합 전의 옛 C1 리프 노드"]:4
  e1["리프 노드"] e2["리프 노드"] e3["리프 노드"] e4["…"]
  MS["merge step · 옛 C1 리프 노드 하나와 C0 리프 레벨의 항목을 병합한다"]:4
  FB["filling block · 256KB · 새로 병합된 C1 리프 노드"]:4
  f1["새 리프 노드"] f2["새 리프 노드"] f3["아직 빈 자리"] f4["…"]

두 블록은 서로 다른 블록이고, merge step 은 앞의 것에서 읽어 뒤의 것에 씁니다. 어느 쪽이든 단일 페이지 리프 노드들이 한 멀티 페이지 블록 안에 연속으로 묶여 있습니다.

이어지는 merge step 들은 C0 와 C1 의 인덱스 값 구간을 키워 가며 맞물립니다. 최대값에 닿으면 rolling merge 가 가장 작은 값에서 다시 시작합니다.

조회와 삭제가 갈리는 자리

인덱스 항목을 찾는 검색은 언제나 C0 를 먼저 보고 그다음 C1 을 봅니다.

삭제는 삽입과 지연·배치의 성질을 나눠 가집니다. 인덱스가 걸린 행이 지워질 때 해당 키 값 항목이 C0 트리의 알맞은 자리에 없으면, 그 자리에 delete node entry 를 놓습니다. 이것도 키 값으로 색인됩니다. 지울 행 식별자를 함께 적어 둡니다. 실제 삭제는 나중에 rolling merge 가 진짜 인덱스 항목을 만났을 때 이뤄집니다. delete node entry 는 병합을 따라 더 큰 컴포넌트로 이주하다가 짝이 되는 항목을 만나면 그것을 소멸시킵니다.

그 사이 조회 요청은 delete node entry 를 거쳐 걸러져야 지워진 레코드를 가리키는 참조를 돌려주지 않게 됩니다. 이 걸러 내기는 해당 키 값을 찾는 도중에 쉽게 이뤄집니다. delete node entry 가 항목 자신보다 앞선 컴포넌트의 알맞은 키 값 자리에 놓이기 때문입니다. 많은 경우 이 필터는 어떤 항목이 지워졌는지 판정하는 오버헤드를 줄여 줍니다.

인덱스가 걸린 값을 바꾸는 갱신은 어떤 종류의 애플리케이션에서도 드뭅니다. 다만 그런 갱신도 삭제 뒤에 삽입이 온 것으로 보면 LSM 트리가 지연 처리할 수 있습니다.

대가

쓰기를 모아 내려보낸 값은 세 갈래로 돌아옵니다. RocksDB 공식 위키는 이 셋에 증폭이라는 이름을 붙입니다. 증폭은 사용자의 논리적 요청 크기와 저장 장치로 실제로 나간 요청 크기를 잇는 값입니다. 같은 문서는 컴팩션이 이 셋 사이의 맞바꿈을 바꾸는 열쇠라고 적습니다.

쓰기 증폭이 높으면 작업 부하가 디스크 처리량에 묶일 수 있습니다. 쓰기 증폭이 50 이고 디스크 최대 처리량이 500MB/s 이면 데이터베이스가 견디는 쓰기 속도는 10MB/s 입니다. 쓰기 증폭이 높으면 플래시 수명도 줄어듭니다. 공간 증폭에는 대개 단단한 상한을 걸어 둬야 디스크나 메모리가 바닥나지 않습니다.

백그라운드 병합의 입출력 비용

컴팩션은 공짜로 도는 청소가 아니라 그 자체가 입출력입니다. LevelDB 공식 구현 문서가 그 값을 못 박아 둡니다. 레벨 0 컴팩션은 레벨 0 에서 최대 네 개의 1MB 파일을 읽고, 최악의 경우 레벨 1 파일 전부인 10MB 를 읽습니다. 곧 14MB 를 읽고 14MB 를 씁니다. 레벨 0 이 아닌 곳에서는 레벨 L 에서 2MB 파일 하나를 고릅니다. 최악의 경우 이것이 레벨 L+1 의 파일 약 열두 개와 겹칩니다. 그래서 26MB 를 읽고 26MB 를 씁니다. 디스크 입출력 속도를 100MB/s 로 잡으면 최악의 컴팩션 비용은 대략 0.5초입니다.

이 부하를 줄이려고 백그라운드 쓰기를 조이면 대가가 반대쪽으로 옮겨 갑니다. 전체 속도의 10퍼센트 같은 작은 값으로 조이면 컴팩션 하나가 최대 5초까지 걸릴 수 있습니다. 그동안 사용자가 10MB/s 로 쓰고 있으면 레벨 0 파일이 50개 가까이 쌓일 수 있습니다. 그러면 매 읽기마다 더 많은 파일을 합쳐야 해서 읽기 비용이 크게 늘 수 있습니다.

삭제 표식과 옛 판이 남는 구간

덮어쓰인 값과 삭제 표식은 컴팩션이 그 자리에 올 때까지 디스크에 남습니다. 컴팩션은 덮어쓰인 값을 버립니다. 삭제 표식은 현재 키 범위와 겹치는 파일을 가진 더 높은 번호의 레벨이 하나도 없을 때만 버립니다. 그전까지 그 표식들은 공간을 차지합니다. 읽는 쪽은 그것을 거쳐 걸러야 합니다.

컴포넌트 개수와 버퍼 크기의 양쪽 값

컴포넌트를 늘리면 메모리에 둘 C0 를 줄일 수 있습니다. 대신 추가 rolling merge 를 도는 CPU 비용과 그 병합의 노드를 버퍼링하는 메모리 비용이 붙습니다. 원 논문은 이 메모리 비용이 흔한 비용 구간에서 C0 의 메모리 비용을 압도한다고 적습니다. 여기에 즉시 응답이 필요한 조회가 모든 컴포넌트 트리를 뒤져야 하는 일이 겹칩니다.

메모리에 쌓는 버퍼를 크게 잡는 쪽에도 값이 붙습니다. RocksDB 공식 위키는 쓰기 버퍼 크기를 정할 때 최악의 경우 메모리 사용량의 두 배를 예산으로 잡으라고 적습니다. 그만한 메모리가 없으면 그 값을 줄여야 합니다.

관련 항목

이 구조가 속하는 상위 분류

인덱스

이 구조를 이루는 부품

WAL · memtable · SSTable · 컴팩션 · 락 · delete node entry

이 구조의 병합이 도는 단계

rolling merge · merge step · emptying block · filling block

이 구조와 닮거나 겨루는 다른 정렬·인덱스 기법

B-tree · SB-tree · 병합 정렬

이 구조를 실제로 구현·채택한 사례

LevelDB · RocksDB · Cassandra

이 구조가 비롯된 배경

트랜잭션 · 이력 테이블 · TPC-A(TPC Benchmark A, 계좌 활동 트랜잭션 벤치마크)

이 구조가 치르는 대가를 재는 지표

쓰기 증폭 · 읽기 증폭 · 공간 증폭