LSM 트리란

LSM 트리 ( Log Structured Merge Tree )

• LSM 트리는 2개 이상의 tree 로 구성될 수 있는데, 1개의 tree 를 제외하고 나머지 tree 는 디스크에 위치한다
• 메모리에 위치한 자료구조를 C0 tree, 디스크에 위치한 자료구조를 C1 tree라고 표현한다

LSM-tree에서 쓰기 요청 처리

1. 쓰기 작업이 요청된다
2. 시스템 다운 시 복구를 위해 별도의 로그성 파일에 데이터를 기록한다 (sequential log)
3. 메모리의 C0 tree에 해당 쓰기 요청 반영 / C0 tree는 메모리에서만 존재하기 때문에 디스크를 위한 최적화는 필요하지 않다
4. C0 tree가 임계치 이상의 크기에 도달하면 rolling merge를 실시하며
   Rolling merge를 통해 C0 tree의 연속되는 메모리 영역을 디스크 상의 C1 tree와 병합한다 → 병합을 통해 C0이 사용할 수 있는 메모리 공간을 확보한다

• Rolling merge
  • Rolling merge의 시작은 디스크상의 C1 tree에 위치한 leaf node 데이터를 multi-page block 단위로 메모리에 적재한다
  • 메모리에 적재된 C1 tree의 leaf node 데이터를 disk page 크기 단위로 읽고 이를 C0 tree의 left node데이터와 병합하여 새로운 leaf node를 생성한다
  • 생성된 leaf node는 C1의 parent node가 가리킴으로써 병합과정이 완료된다
  • 메모리에서 병합된 데이터를 디스크로 플러쉬할 때 기존 데이터의 위치에 덮어쓰지 않고 새로운 위치에 저장한다
    

• log-structured (데이터를 순차적으로 로그에 기록) 형식으로 데이터를 저장하면, 항상 파일에 추가만 해야하니까 디스크 공간이 부족해진다
• SS 테이블의 형식으로 디스크에 key-value 데이터를 저장하는 색인 방식
  • log-structured 데이터 형식에 “모든 key-value 쌍을 키를 기준으로 정렬 한다” 라는 요구사항을 추가한 형식 : SS 테이블
  • SS 테이블은 LSM 트리에서 실제로 데이터를 저장하는 단위 로, 디스크 상에 정렬된 세그먼트 파일이다
  • 새로운 데이터가 쓰기 동작으로 인해 메모리에 먼저 쓰여지고 나중에 디스크에 저장될 때 SS 테이블이 형성된다
    
  • SS 테이블은 주기적인 병합 작업을 통해, 데이터를 특정 크기의 segment 로 나누고, 주기적으로 compaction (중복된 키를 버리고 각 키의 최신 값만 유지하는 것) 을 수행한다
  1. 쓰기가 들어오면 인메모리 균형 트리(balanced tree) 데이터 구조(ex. red-black tree)에 추가한다
     • 트리가 이미 키로 정렬된 키-값 쌍을 유지하므로 효율적인 수행이 가능하다
     • 이러한 인메모리 트리를 멤테이블(memtable)이라고 한다
       • 멤테이블의 크기가 임계값(보통 수 MB)보다 커지면 SS테이블 파일로 디스크에 기록한다
       • 메모리의 휘발성 특성 때문에 주기적으로 디스크에 기록되거나 SS 테이블로 이동된다
  2. 새로운 SS 테이블 파일은 DB 에서 가장 최신 세그먼트가 되고, SS 테이블을 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록된다
  3. 읽기 요청을 처리하려면 먼저 멤테이블에서 키를 찾고, 디스크상의 최신 세그먼트부터 찾는다. (인메모리 해시맵이나 bloom filter 를 사용하여 탐색 시간을 줄일 수 있다.)
  4. 백그라운드에서 지속적으로 컴팩션 과정을 수행한다

LSM-tree 에서 조회

• C0, C1, ... Cn 순서로 수행한다
• C0 tree (메모리) 에서 원하는 데이터를 찾을 수 없다면 C1 tree를 찾고, 이후에도 데이터를 찾을 수 없다면 다음 tree를 확인한다
  • C0를 제외한 나머지 tree는 디스크에 위치하기 때문에 다수의 tree를 탐색해야 한다면 B-Tree와 비교하여 조회 성능이 안 좋을 수 있다
  • Bloom filter : LSM 트리와 같은 DB 시스템에서 사용되는 확률적 자료구조
    • 확률적인 자료 구조 “존재할 것이라고 판단되면 실제로는 존재하지 않을 가능성이 있다” 는 오류 발생 가능성이 있다
    • 불필요한 디스크 액세스 감소 : 특정 데이터가 어떤 레벨의 트리에 있을 지 확률적으로 판단하여 불필요한 디스크 액세스를 줄인다
    • 데이터 조회 최적화 : 특정 데이터 존재 여부를 확률적으로 판단하므로, 실제 존재하지 않는 데이터 조회를 빠르게 거부 가능하다 (읽기 성능 향상)
    • 메모리 효율성 : 비트 배열로 구성되어 메모리 사용량이 적다