집 >백엔드 개발 >Golang >처음부터 LSM-트리 스토리지 엔진 구축

처음부터 LSM-트리 스토리지 엔진 구축

Barbara Streisand원래의: 2025-01-03 07:37:39570검색

머리말

이 글에서는 LSM-Tree(로그 구조 병합 트리)의 핵심 개념과 구조를 이해하는 방법을 안내합니다. 결국에는 LSM-Tree를 기반으로 처음부터 자신만의 스토리지 엔진을 구축할 수 있게 됩니다.

LSM-트리란 무엇인가요?

기본 개념

LSM-트리(Log-Structured Merge-Tree)는 고처리량 쓰기 작업에 최적화된 데이터 구조입니다. Cassandra, RocksDB, LevelDB 등의 데이터베이스 및 스토리지 시스템에서 널리 사용됩니다.

LSM-Tree의 핵심 아이디어는 먼저 메모리 내 데이터 구조(일반적으로 스킵 목록 또는 AVL 트리와 같은 순서가 지정된 구조)에 작업을 작성하는 것입니다. 나중에 이러한 쓰기는 SSTable로 일괄 처리되고 순차적으로 디스크에 기록되므로 임의 I/O가 최소화됩니다.

기본 구조

Building an LSM-Tree Storage Engine from Scratch

LSM-Tree는 두 가지 주요 구성 요소로 나뉩니다.

인메모리 스토리지
- 메모리의 핵심 구조는 Memtable입니다.
- 모든 쓰기 작업(예: 설정, 삭제)은 먼저 Memtable로 이동하며, Memtable은 이러한 작업을 정렬된 데이터 구조(예: 다이어그램의 정렬된 트리)에 삽입합니다.
- Memtable이 특정 크기 임계값에 도달하면 SSTable(순차적으로 작성됨)로 디스크에 플러시됩니다.
- 새 Memtable에서 새로운 쓰기 작업이 계속됩니다.
디스크 스토리지
- 디스크 스토리지에는 WAL 및 SSTable 파일이 포함됩니다.
- WAL(Write-Ahead Log)은 데이터베이스 충돌 시 최근 쓰기(Memtable에 저장되었지만 아직 디스크에 유지되지 않음)가 손실되지 않도록 보장합니다. Memtable에 대한 모든 쓰기는 WAL에 추가됩니다. 데이터베이스를 다시 시작하면 Memtable을 충돌 이전 상태로 복원하기 위해 WAL의 항목을 재생할 수 있습니다.
- SSTable(Sorted String Table)은 일련의 순서가 지정된 키-값 쌍을 보유하는 데이터 저장 형식입니다.
- Memtable이 크기 임계값에 도달하면 새 SSTable을 생성하고 이를 디스크에 유지합니다. Memtable은 메모리 내 순서가 지정된 데이터 구조를 사용하므로 SSTable을 구성할 때 추가 정렬이 필요하지 않습니다.
- 디스크의 SSTable은 여러 수준으로 구성됩니다. 새로 플러시된 SSTable은 레벨 0에 저장됩니다. 후속 압축 단계에서 L0의 SSTable은 레벨 1 및 상위 레벨
- 레벨 크기가 임계값을 초과하면 SSTable 압축 프로세스가 트리거됩니다. 압축하는 동안 현재 수준의 SSTable은 더 높은 수준으로 병합되어 더 크고 순서가 지정된 파일을 생성합니다. 이렇게 하면 조각화가 줄어들고 쿼리 효율성이 향상됩니다.

일반적으로 SSTable의 구조에는 일련의 순서가 지정된 키-값 쌍(데이터 블록) 이상이 포함됩니다. 또한 인덱스 블록, 메타데이터 블록 및 기타 구성 요소도 포함되어 있습니다. 이러한 세부 사항은 구현 섹션에서 심층적으로 논의될 것입니다.

데이터 쓰기

데이터 쓰기에는 새로운 키-값 쌍을 추가하거나 기존 쌍을 업데이트하는 작업이 포함됩니다. 업데이트는 나중에 압축 프로세스 중에 제거되는 이전 키-값 쌍을 덮어씁니다.

데이터가 기록되면 먼저 Memtable으로 이동하며, 여기서 키-값 쌍이 메모리 내 정렬 데이터 구조에 추가됩니다. 동시에 쓰기 작업은 WAL에 기록되고 디스크에 지속되어 데이터베이스 충돌 시 데이터 손실을 방지합니다.

Memtable에는 정의된 임계값(보통 크기 기준)이 있습니다. Memtable이 이 임계값을 초과하면 읽기 전용 모드로 전환되고 새로운 SSTable으로 변환된 후 디스크에서 레벨 0으로 유지됩니다.

Memtable이 SSTable로 플러시되면 해당 WAL 파일을 안전하게 삭제할 수 있습니다. 후속 쓰기 작업은 새 Memtable(및 새 WAL)에서 진행됩니다.

데이터 삭제

LSM-Tree에서는 데이터가 즉시 삭제되지 않습니다. 대신 삭제는 삭제(일시 삭제와 유사)라는 메커니즘을 사용하여 처리됩니다. 키-값 쌍이 삭제되면 "삭제 표시"로 표시된 새 항목이 기록되어 해당 키-값 쌍이 삭제되었음을 나타냅니다. 실제 제거는 압축 과정에서 발생합니다.

이 삭제 표시 기반 삭제는 LSM-Tree의 추가 전용 속성을 보장하여 임의 I/O를 방지하고 디스크에 순차적 쓰기를 유지합니다.

데이터 쿼리

데이터 쿼리 과정은 Memtable에서 검색하는 것부터 시작됩니다. 키-값 쌍이 발견되면 클라이언트에 반환됩니다. 삭제 표시가 있는 키-값 쌍이 발견되면 요청한 데이터가 삭제되었음을 나타내며 이 정보도 반환됩니다. Memtable에서 키를 찾을 수 없는 경우 쿼리는 레벨 0에서 레벨 N

까지 SSTable을 검색합니다.

데이터 쿼리에는 여러 SSTable 파일 검색이 포함될 수 있고 임의의 디스크 I/O가 발생할 수 있으므로 LSM-Tree는 일반적으로 읽기 집약적인 워크로드보다는 쓰기가 많은 워크로드에 더 적합합니다.

쿼리 성능을 위한 일반적인 최적화 중 하나는 Bloom 필터를 사용하는 것입니다. Bloom 필터는 특정 SSTable에 키-값 쌍이 존재하는지 신속하게 확인하여 불필요한 디스크 I/O를 줄일 수 있습니다. 또한 SSTable의 정렬된 특성을 통해 이진 검색과 같은 효율적인 검색 알고리즘을 사용하여 더 빠른 조회를 수행할 수 있습니다.

데이터 압축

여기에서는 LevelDB와 RocksDB에서 사용하는 레벨 압축 전략을 소개합니다.

또 다른 일반적인 전략은 크기 계층 압축 전략으로, 더 새롭고 작은 SSTable을 더 오래되고 더 큰 SSTable로 연속적으로 병합합니다.

앞서 언급했듯이 SSTable은 키별로 정렬된 일련의 항목을 저장합니다. 레벨 압축 전략에서 SSTable은 여러 레벨(레벨 0에서 레벨 N까지)로 구성됩니다.

레벨 0에서 SSTable은 Memtable에서 직접 플러시되므로 중복되는 키 범위를 가질 수 있습니다. 단, 레벨 1~N에서는 같은 레벨 내의 SSTable은 키 범위가 중복되지 않지만, 서로 다른 레벨의 SSTable 간에는 키 범위 중복이 허용됩니다.

아래에는 (완전히 정확하지는 않지만) 예시가 나와 있습니다. 레벨 0에서는 첫 번째와 두 번째 SSTable의 키 범위가 겹치는 반면, 레벨 1 및 레벨 2에서는 각 레벨 내의 SSTable이 서로 분리된 키 범위를 갖습니다. . 그러나 서로 다른 수준(예: 수준 0과 수준 1, 수준 1과 수준 2) 간의 SSTable에는 중복되는 키 범위가 있을 수 있습니다.

Building an LSM-Tree Storage Engine from Scratch

이제 Leveled Compaction 전략이 어떻게 이러한 조직 구조를 유지하는지 살펴보겠습니다.

레벨 0은 특수한 경우이므로 압축 전략 논의는 두 부분으로 나누어집니다.

0레벨 ~ 1레벨 레벨 0은 SSTable 사이에서 키가 겹치는 것을 허용하므로 압축은 레벨 0에서 SSTable과 함께 키 범위가 겹치는 레벨 0의 다른 모든 SSTable을 선택하여 시작됩니다. 다음으로, 키 범위가 겹치는 레벨 1의 모든 SSTable이 선택됩니다. 선택된 SSTable은 병합되어 하나의 새로운 SSTable로 압축된 후 레벨 1에 삽입됩니다. 압축 프로세스에 포함된 이전 SSTable은 모두 삭제됩니다.
레벨 N ~ 레벨 N 1(N>0) 레벨 1부터는 동일한 레벨 내의 SSTable에 키 범위가 겹치지 않습니다. 압축 중에 레벨 N에서 SSTable이 선택되고, 키 범위가 겹치는 레벨 N 1의 모든 SSTable도 선택됩니다. 이러한 SSTable은 하나 이상의 새로운 SSTable로 병합 및 압축되어 레벨 N 1에 삽입되고 이전 SSTable은 삭제됩니다.

레벨 0에서 레벨 1 압축과 레벨 N에서 레벨 N 1(N>0) 압축의 주요 차이점은 하위 레벨(레벨 0 또는 레벨 N).

다중 SSTable 압축 및 병합 프로세스는 아래에 설명되어 있습니다. 병합 중에는 각 키의 최신 값만 유지됩니다. 최신 값에 "삭제 표시" 표시가 있으면 키가 삭제됩니다. 구현에서는 k-way 병합 알고리즘을 사용하여 이 프로세스를 수행합니다.

Building an LSM-Tree Storage Engine from Scratch

압축 프로세스에 대한 위의 설명은 높은 수준의 개요만을 제공한다는 점에 유의하는 것이 중요합니다. 실제 구현 중에 많은 세부 사항을 해결해야 합니다.

예를 들어 LevelDB에서 압축 중에 레벨 N 1에 대한 새 SSTable을 생성할 때 새 SSTable이 레벨 N 2의 10개 이상의 SSTable과 겹치면 프로세스가 다른 SSTable 생성으로 전환됩니다. 이는 단일 압축과 관련된 데이터 크기를 제한합니다.

구현

위의 LSM-Tree 개요를 바탕으로 이제 LSM-Tree에 대한 기본적인 이해와 구현에 대한 몇 가지 아이디어를 가지셨으리라 믿습니다. 다음으로 LSM-Tree를 기반으로 스토리지 엔진을 처음부터 구축하겠습니다. 아래에서는 핵심코드만 소개하겠습니다. 전체 코드는 https://github.com/B1NARY-GR0UP/originium을 참조하세요.

LSM-Tree의 구현을 다음과 같은 핵심 구성요소로 나누어 하나씩 구현하겠습니다.

스킵 목록
월
멤테이블
SS테이블
K-Way 머지
블룸필터
레벨 압축

건너뛰기 목록

데이터 쓰기를 소개하는 과정에서 LSM-Tree가 먼저 메모리 내 정렬된 데이터 구조에 데이터를 쓴다고 언급했습니다. 일반적인 순서의 데이터 구조와 해당 작업의 시간 복잡도는 다음과 같습니다.

Data Structure	Insert	Delete	Search	Traverse
Skip List	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)
AVL Tree	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)
Red-Black Tree	O(log⁡n)	O(log⁡n)	O(log⁡n)	O(n)

우리가 건너뛰기 목록을 선택한 이유는 두 가지입니다. 구현 및 유지 관리가 더 간단하고(KISS 원칙) 기본 연결 목록 구조가 순차적 순회를 촉진하여 메모리 내 데이터를 디스크에 더 쉽게 유지할 수 있다는 것입니다.

핵심 구조

스킵 목록의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go에서 확인할 수 있습니다.

스킵 목록은 기본 연결 목록과 그 위에 구축된 여러 수준의 색인으로 구성됩니다. 대규모 데이터 세트의 경우 인덱스 레이어는 검색 경로를 크게 단축합니다.

우리 구현에서 건너뛰기 목록의 핵심 구조는 다음과 같이 정의됩니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

maxLevel: 건너뛰기 목록의 최대 수준 수(기본 연결 목록에는 1개 수준이 있음).
레벨: 건너뛰기 목록의 현재 레벨 수.
p: 노드가 더 높은 레벨로 승격될 확률입니다. 예를 들어 p = 0.5인 경우 기본 수준에 10개의 노드가 있는 연결 목록은 다음 수준의 인덱스에 약 5개의 노드를 갖습니다.
rand: p와 비교하는 데 사용되는 난수 생성기
size: Skip List에 저장된 키-값 쌍의 수로, Memtable이 크기 임계값을 초과하는지 확인하는 데 사용됩니다.
head: 각 레벨의 첫 번째 노드에 대한 참조를 보유하는 헤드 노드입니다.

Skip List에 저장되는 요소의 구조는 다음과 같이 정의됩니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

types.Entry는 키, 값 및 삭제할 삭제 표시 플래그를 포함하여 스토리지 엔진의 키-값 쌍을 나타냅니다.
다음: 각 수준의 다음 요소에 대한 포인터를 포함합니다.

이 구조는 추상적으로 보일 수 있으므로 예를 들어 설명하겠습니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

이 3레벨 건너뛰기 목록에서 헤드 노드의 다음 포인터는 각 레벨의 첫 번째 노드를 참조합니다. 요소 3과 6은 각 레벨의 다음 요소를 저장합니다.

예를 들어 레벨 2에서 요소 19의 다음 노드를 찾으려면 e19.next[2-1]을 사용합니다.

세트

func (s *SkipList) Set(entry types.Entry)

LSM-Tree는 삭제를 수행하기 위해 삭제 표시를 사용하므로 건너뛰기 목록 구현에서는 삭제 메서드가 필요하지 않습니다. 요소를 삭제하려면 항목의 Tombstone을 true로 설정하면 됩니다. 따라서 Set 메소드는 새로운 키-값 쌍 삽입, 기존 쌍 업데이트 및 요소 삭제를 처리합니다.

Set 메소드의 구현을 살펴보겠습니다. 가장 높은 것부터 각 레벨의 노드를 순회하여 설정할 키보다 작은 마지막 요소가 업데이트 슬라이스에 저장됩니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

이 순회가 끝나면 curr는 최하위 연결 목록에서 설정할 키보다 작은 마지막 요소를 가리킵니다. 따라서 curr의 다음 요소가 우리가 설정하려는 키와 동일한지 확인하기만 하면 됩니다. 일치하면 요소가 이미 삽입된 것입니다. 기존 요소를 업데이트하고 반환합니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

요소를 찾을 수 없으면 새 요소로 삽입됩니다. RandomLevel을 사용하여 이 요소의 인덱스 수준을 계산합니다. 건너뛰기 목록의 현재 수준 수를 초과하는 경우 업데이트 슬라이스에 헤드 노드를 추가하고 s.level을 새 수준 수로 업데이트합니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

다음으로 삽입할 요소를 구성하고 각 레벨의 다음 포인터를 업데이트하여 삽입을 완료합니다.

func (s *SkipList) Set(entry types.Entry)

얻다

스킵 목록은 여러 계층의 인덱스를 사용하여 빠른 검색 작업을 수행할 수 있습니다. 구현에서 중첩된 for 루프는 인덱스 기반 검색 작업을 나타냅니다. 최종적으로 해당 요소가 하위 연결리스트에서 발견되면 반환됩니다.

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

모두

우리가 스킵 리스트를 선택한 이유 중 하나는 하위 연결 리스트를 순회하는 것만으로 가능한 편리한 순차 순회입니다.

// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

월

WAL의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go에서 확인할 수 있습니다.

앞서 언급했듯이 WAL(Write-Ahead Logging)의 목적은 데이터베이스 충돌로 인해 Memtable의 데이터 손실을 방지하는 것입니다. 따라서 WAL은 Memtable에 대한 작업을 기록하고 데이터베이스가 다시 시작될 때 WAL 파일에서 Memtable을 복구해야 합니다.

핵심 구조

WAL의 핵심 구조는 다음과 같습니다. 여기서 fd는 WAL 파일의 파일 설명자를 저장합니다.

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

쓰다

Memtable에 작업을 기록해야 하므로 기본적으로 각 작업(설정, 삭제)을 WAL에 항목으로 작성하는 작업이 포함됩니다. Write 메소드의 정의는 다음과 같습니다.

e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

이러한 항목을 파일에 쓸 때 WAL 파일 형식을 표준화해야 합니다. 여기서 사용하는 형식은 길이 데이터입니다. 먼저 Entry를 직렬화한 다음 직렬화된 데이터의 길이를 계산하고 마지막으로 길이와 직렬화된 데이터를 순차적으로 WAL 파일에 씁니다.

핵심 코드는 다음과 같습니다.

func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
    curr := s.head

    for i := s.maxLevel - 1; i >= 0; i-- {
        for curr.next[i] != nil && curr.next[i].Key < key {
            curr = curr.next[i]
        }
    }

    curr = curr.next[0]

    if curr != nil && curr.Key == key {
        return types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        }, true
    }
    return types.Entry{}, false
}

읽다

WAL 파일 형식인 길이 데이터를 사용하기 때문에 읽는 동안 먼저 8바이트(int64)를 읽어 데이터의 길이를 얻은 다음 이 길이를 기준으로 데이터를 읽고 역직렬화합니다. 항목을 검색합니다.

핵심 코드는 다음과 같습니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

멤테이블

Memtable의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go에서 확인할 수 있습니다.

Memtable은 클라이언트 작업을 건너뛰기 목록에 기록하고 이를 WAL에 기록하는 역할을 담당합니다. 데이터베이스가 시작될 때 WAL에서 데이터를 복구할 수도 있습니다.

핵심 구조

Memtable의 핵심 구조는 Skiplist와 wal의 두 가지 주요 구성 요소를 포함하여 다음과 같습니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

세트

Set 작업을 수행할 때 건너뛰기 목록과 WAL을 동시에 업데이트해야 합니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

얻다

값을 검색하려면 건너뛰기 목록의 Get 작업 결과를 반환하면 됩니다.

func (s *SkipList) Set(entry types.Entry)

다시 덮다

WAL 파일에서 Memtable을 복구하려면 먼저 WAL 파일을 읽은 다음 WAL 파일의 Entry 레코드를 Memtable에 순차적으로 적용하고 마지막으로 복구된 WAL 파일을 삭제해야 합니다.

WAL 파일 목록 검색:

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

WAL을 읽고 Memtable을 복구하세요.

// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

SS테이블

LevelDB SSTable

이전 소개에서는 "SSTable(Sorted String Table)은 일련의 순서화된 키-값 쌍을 유지하는 데이터 저장 형식"이라고만 언급했습니다. 여기서는 SSTable의 구조에 대해 좀 더 자세히 설명하겠습니다.

레벨DB에서 SSTable은 다양한 목적을 가진 여러 블록으로 구성됩니다. 개략도는 다음과 같습니다.

Building an LSM-Tree Storage Engine from Scratch

데이터 블록: 순서가 지정된 키-값 쌍의 시퀀스를 저장합니다.
메타 블록: 필터와 통계의 두 가지 유형이 포함됩니다. 필터 유형은 Bloom 필터에 대한 데이터를 저장하고, 통계 유형은 데이터 블록에 대한 통계 정보를 저장합니다.
MetaIndex Block: 메타 블록에 대한 인덱스 정보를 저장합니다.
인덱스 블록: 데이터 블록에 대한 인덱스 정보를 저장합니다.
바닥글: 길이가 고정되어 있으며 MetaIndex Block과 Index Block의 인덱스 정보와 매직넘버를 저장합니다.

인덱스 정보는 본질적으로 BlockHandle이라는 포인터 구조로, 해당 블록을 찾는 데 사용되는 오프셋과 크기라는 두 가지 속성을 포함합니다.

우리의 SSTable

SSTable 구현에서 LevelDB SSTable 구조를 단순화했습니다. 개략도는 다음과 같습니다.

Building an LSM-Tree Storage Engine from Scratch

데이터 블록: 순서가 지정된 키-값 쌍의 시퀀스를 저장합니다.
메타 블록: SSTable에 대한 일부 메타데이터를 저장합니다.
인덱스 블록: 데이터 블록에 대한 인덱스 정보를 저장합니다.
바닥글: 길이가 고정되어 메타 블록과 인덱스 블록의 인덱스 정보를 저장합니다.

SSTable의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/tree/main/sstable에서 확인할 수 있습니다.

데이터 블록

데이터 블록의 구조는 다음과 같이 정의되며, 순서대로 항목을 저장합니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

우리는 데이터 블록에 대해 세 가지 기본 방법을 구현했습니다.

인코드: 데이터 블록을 바이너리 데이터로 인코딩합니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

접두사 압축을 사용하여 키-값 시퀀스를 인코딩합니다. 버퍼에는 공통 접두사의 길이, 접미사의 길이, 접미사 자체, 값의 길이, 값, "tombstone" 표시를 순차적으로 작성합니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

마지막으로 s2를 사용하여 데이터를 압축합니다.

S2는 Snappy 압축 알고리즘의 고성능 확장입니다.

func (s *SkipList) Set(entry types.Entry)

디코드: 바이너리 데이터를 데이터 블록으로 디코딩합니다.

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

디코딩 중에는 프로세스가 단순히 반대로 진행됩니다. 전체 키-값 쌍은 접두사와 접미사를 사용하여 재구성됩니다.

// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

검색: 이진 검색을 사용하여 키-값 쌍을 찾습니다.

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

인덱스 블록

인덱스 블록의 구조는 다음과 같이 정의됩니다. 해당 데이터 블록의 BlockHandle과 함께 각 데이터 블록의 첫 번째 및 마지막 키를 저장합니다.

e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

마찬가지로 인덱스 블록은 인코드, 디코드, 검색의 세 가지 기본 방법을 구현합니다. Encode 및 Decode 메소드의 구현 아이디어는 기본적으로 동일하므로 Search 메소드

에 중점을 두겠습니다.

데이터 블록의 검색 방법은 단일 데이터 블록에 저장된 정렬된 키-값 시퀀스 내에서 특정 키-값 쌍을 찾도록 설계되었습니다. 반면, Index Block의 Search 메소드는 전체 SSTable 내에서 주어진 키를 포함하는 Data Block을 찾는 데 사용됩니다.

func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
    curr := s.head

    for i := s.maxLevel - 1; i >= 0; i-- {
        for curr.next[i] != nil && curr.next[i].Key < key {
            curr = curr.next[i]
        }
    }

    curr = curr.next[0]

    if curr != nil && curr.Key == key {
        return types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        }, true
    }
    return types.Entry{}, false
}

메타 블록 및 바닥글

func (s *SkipList) All() []types.Entry {
    var all []types.Entry

    for curr := s.head.next[0]; curr != nil; curr = curr.next[0] {
        all = append(all, types.Entry{
            Key:       curr.Key,
            Value:     curr.Value,
            Tombstone: curr.Tombstone,
        })
    }

    return all
}

이 두 블록의 구현은 매우 간단하며 둘 다 Encode 및 Decode 메서드만 필요합니다.

짓다

SSTable에 모든 블록을 도입한 후 SSTable을 구성하려면 키-값 쌍을 기반으로 각 블록을 단계별로 구축하면 됩니다. 마지막으로 인메모리 인덱스와 인코딩된 SSTable이 반환됩니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

K-웨이 머지

K-Way Merge의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway에서 확인할 수 있습니다.

개념 부분에서는 여러 SSTable을 압축하고 병합하는 과정을 다이어그램을 통해 설명합니다. 이 프로세스는 k-way 병합 알고리즘을 사용하여 수행됩니다.

k-way 병합 알고리즘은 k개의 정렬된 시퀀스를 O(knlogk)의 시간 복잡도로 단일 정렬된 시퀀스로 병합하는 방법입니다.

이 알고리즘의 구현 중 하나는 최소 힙을 보조 구조로 사용합니다.

각 시퀀스의 첫 번째 요소를 힙에 삽입합니다.
힙에서 가장 작은 값을 팝하여 결과 세트에 추가합니다. 팝된 요소의 시퀀스에 여전히 더 많은 요소가 있는 경우 해당 시퀀스의 다음 요소를 힙에 삽입하세요.
모든 시퀀스의 모든 요소가 병합될 때까지 이 과정을 반복합니다.

더미

표준 라이브러리는 컨테이너/힙에서 힙 구현을 제공합니다. heap.Interface를 구현하면 최소 힙을 구축할 수 있습니다.

먼저 최소힙의 기본 구조를 정의합니다. 슬라이스는 요소를 저장하는 데 사용됩니다. 각 요소에는 항목뿐만 아니라 이 요소가 어떤 정렬된 시퀀스에서 시작되었는지 나타내는 LI도 포함됩니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

힙의 요소를 정렬하려면 sort.Interface 메서드를 구현하세요. Less 메소드에는 특별한 주의가 필요합니다. 요소의 LI를 비교하여 요소가 동일한 키를 가질 때 이전 시퀀스의 요소가 먼저 정렬되도록 합니다. 이는 요소를 결과 세트에 병합할 때 중복 제거를 용이하게 합니다. 이 요구 사항은 또한 k-way 병합 알고리즘을 사용할 때 정렬된 시퀀스가 가장 오래된 것부터 최신 순서로 정렬되어야 함을 의미합니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

마지막으로 Push 및 Pop 메서드를 구현합니다. Push는 슬라이스 끝에 요소를 추가하는 반면 Pop은 슬라이스에서 마지막 요소를 제거합니다.

func (s *SkipList) Set(entry types.Entry)

병합

Merge 메소드의 함수 정의:

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

k-way 병합 알고리즘 프로세스를 따릅니다.

먼저, 정렬된 각 시퀀스의 첫 번째 요소를 최소 힙에 삽입합니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

최소 힙에서 요소를 반복적으로 팝하여 결과 대기열에 추가합니다. 팝된 요소의 시퀀스에 여전히 더 많은 요소가 있는 경우 해당 시퀀스의 다음 요소를 힙에 삽입합니다. 여기서는 결과 시퀀스 대신 맵이 사용됩니다. 맵은 자동으로 중복 제거를 처리하며 최신 키는 항상 이전 키를 덮어씁니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

마지막으로 맵을 탐색하여 결과 대기열에 요소를 추가하고 "삭제 표시"로 표시된 키-값 쌍을 제거합니다. 맵은 순서가 없기 때문에 결과 큐를 정렬한 후에 반환해야 합니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

블룸 필터

블룸 필터의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go에서 확인할 수 있습니다.

블룸 필터는 요소가 집합의 구성원인지 여부를 효율적으로 확인하는 데이터 구조입니다.

비트 배열과 다중 해시 함수를 사용합니다.
요소를 추가할 때 요소는 비트 배열의 다른 위치에 매핑되고 해당 위치를 1로 설정하는 여러 해시 함수를 사용하여 해시됩니다.
쿼리 중에 해시 함수에 의해 매핑된 모든 위치가 1이면 해당 요소가 존재할 수 있습니다. 위치가 0이면 해당 요소는 확실히 존재하지 않는 것입니다.

삽입 및 쿼리 작업 모두의 시간 복잡도는 O(k)입니다. 여기서 k는 해시 함수의 개수입니다. 오탐이 발생할 수 있습니다(블룸 필터는 요소가 집합에 있다고 예측하지만 그렇지 않음). 그러나 오탐은 발생할 수 없습니다(블룸 필터는 요소가 집합에 없다고 예측합니다). 세트에 있지만 실제로는 그렇습니다).

진긍정(TP): 시스템은 이벤트를 "긍정적"으로 예측하며 이는 실제로 긍정적입니다.
오탐지(FP): 시스템에서는 이벤트를 '양성'으로 예측하지만 실제로는 음성입니다.
진음성(TN): 시스템은 이벤트를 "부정적"으로 예측하며 실제로는 부정적입니다.
False Negative(FN): 시스템은 이벤트를 "부정적"으로 예측하지만 실제로는 긍정적입니다.

핵심 구조

블룸 필터의 핵심 구조에는 비트 배열(uint8을 사용하도록 최적화 가능)과 여러 해시 함수가 포함됩니다.

func (s *SkipList) Set(entry types.Entry)

새로운

블룸 필터 인스턴스를 생성하는 방법은 n(예상 요소 수)과 p(원하는 거짓양성률)의 두 가지 매개변수를 허용합니다.

먼저 매개변수가 검증됩니다. 그런 다음 특정 공식을 사용하여 비트 배열의 크기(m)와 해시 함수의 개수(k)를 계산합니다. 마지막으로 m과 k를 기반으로 비트 배열과 해시 함수를 초기화합니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

추가하다

요소를 추가할 때 모든 해시 함수는 키의 해시 값을 계산하는 데 사용됩니다. 그런 다음 이 값은 비트 배열의 인덱스에 매핑되고 해당 위치는 true로 설정됩니다.

type Element struct {
    types.Entry
    next []*Element
}

// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
    Key       string
    Value     []byte
    Tombstone bool  
}

포함

키가 세트에 있는지 확인하기 위해 해시 함수는 해시 값을 계산하고 이를 비트 배열의 인덱스에 매핑합니다. 이러한 위치 중 하나라도 true가 아닌 경우 해당 요소는 집합에 포함되지 않으며 false가 반환됩니다.

Level 3:       3 ----------- 9 ----------- 21 --------- 26
Level 2:       3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26
Level 1:       3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26

next of head [ ->3, ->3, ->3 ]
next of Element 3 [ ->6, ->6, ->9 ]
next of Element 6 [ ->7, ->9 ]

수평 다짐

레벨 압축의 전체 구현은 https://github.com/B1NARY-GR0UP/originium/blob/main/level.go에서 확인할 수 있습니다.

K-Way Merge 및 Bloom Filter와 같은 구성 요소를 구현한 후 LSM-Tree 스토리지 엔진에서 가장 중요한 SSTable 압축 프로세스인 구현의 마지막 부분을 완료할 수 있습니다. 이 구현은 "데이터 압축" 섹션에 설명된 레벨 압축 전략을 따릅니다.

레벨 압축 전략에서 SSTable은 여러 레벨(레벨 0 - 레벨 N)로 구성됩니다. 이 정보를 저장하고 다양한 수준에서 SSTable을 관리하는 구조가 필요합니다.

그래서 우리는 levelManager라는 구조를 구현했습니다. []*list.List를 사용하여 각 레벨에 대한 SSTable 정보를 저장합니다. 여기서 슬라이스의 인덱스는 레벨에 해당합니다. 슬라이스의 각 요소는 특정 수준의 모든 SSTable에 대한 정보를 보유하는 이중 연결 목록인 list.List입니다.

func (s *SkipList) Set(entry types.Entry)

컴팩트LN

compactLN 방법은 레벨 N에서 레벨 N 1(N>0) 압축을 담당합니다. LN에서 가장 오래된 SSTable과 이 SSTable과 키 범위가 겹치는 LN 1의 모든 SSTable을 선택합니다.

curr := s.head
update := make([]*Element, s.maxLevel)

for i := s.maxLevel - 1; i >= 0; i-- {
    for curr.next[i] != nil && curr.next[i].Key < entry.Key {
        curr = curr.next[i]
    }
    update[i] = curr
}

선택한 SSTable은 가장 오래된 것부터 최신 것 순으로 처리됩니다. 데이터 블록의 키-값 쌍은 2차원 슬라이스에 추가된 다음 K-Way 병합 알고리즘을 사용하여 병합됩니다.

// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
    s.size += len(entry.Value) - len(curr.next[0].Value)

    // update value and tombstone
    curr.next[0].Value = entry.Value
    curr.next[0].Tombstone = entry.Tombstone
    return
}

병합된 키-값 쌍을 사용하여 새로운 Bloom Filter와 SSTable을 구성합니다. 새로운 SSTable에 대한 관련 정보는 Level N 1의 마지막 부분에 추가됩니다.

// add entry
level := s.randomLevel()

if level > s.level {
    for i := s.level; i < level; i++ {
        update[i] = s.head
    }
    s.level = level
}

마지막으로 기존 SSTable이 삭제되고 새로 구성된 SSTable이 디스크에 기록됩니다.

e := &Element{
    Entry: types.Entry{
        Key:       entry.Key,
        Value:     entry.Value,
        Tombstone: entry.Tombstone,
    },
    next: make([]*Element, level),
}

for i := range level {
    e.next[i] = update[i].next[i]
    update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))

compactL0 메서드는 레벨 0에서 레벨 1까지의 압축을 처리합니다. CompactLN과 달리 L0에서 SSTable을 하나만 선택하는 것이 아니라 L0에서 겹치는 모든 SSTable을 선택합니다. 나머지 과정은 CompactLN과 동일합니다.

찾다

검색 방법은 모든 SSTable에서 해당 키-값 쌍을 찾습니다. L0부터 시작하여 LN까지 각 레벨을 반복합니다. 블룸 필터와 SSTable의 정렬된 구조를 활용하면 원하는 키-값 쌍이 포함되지 않은 SSTable을 효율적으로 건너뛸 수 있습니다.

type SkipList struct {
    maxLevel int
    p        float64
    level    int
    rand     *rand.Rand
    size     int
    head     *Element
}

DB

이를 통해 LSM-Tree 기반 스토리지 엔진의 핵심 구성 요소를 모두 구현했습니다. LSM-Tree 소개에 설명된 대로 이러한 구성 요소를 조합하면 데이터베이스 인터페이스를 완성할 수 있습니다.

전체 코드: https://github.com/B1NARY-GR0UP/originium/blob/main/db.go
문서: https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage

요약

우리는 LSM-Tree를 이해하는 것부터 시작하여 핵심 구성 요소와 클라이언트 요청 처리 프로세스를 숙지했습니다. 궁극적으로 우리는 처음부터 자체 LSM-Tree 스토리지 엔진을 구축했습니다.

물론 이 구현은 프로토타입일 뿐입니다. 프로덕션급 스토리지 엔진에는 더 많은 세부 사항을 고려해야 합니다. ORIGINIUM은 앞으로도 계속해서 최적화와 개선을 받을 예정입니다. 이 기사와 ORIGINIUM이 LSM-Tree에 대한 이해를 높이는 데 도움이 되기를 바랍니다.

이것으로 이 기사에서 다루는 모든 내용을 마칩니다. 오류나 질문이 있는 경우 언제든지 개인 메시지를 통해 연락하거나 댓글을 남겨주세요. 감사합니다!

참조

https://github.com/B1NARY-GR0UP/originium
https://www.cnblogs.com/whuanle/p/16297025.html
https://vonng.gitbook.io/vonng/part-i/ch3#sstables-he-lsm-shu
https://github.com/google/leveldb/blob/main/doc/table_format.md

위 내용은 처음부터 LSM-트리 스토리지 엔진 구축의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명：

이전 기사：Go에서 파일에 텍스트를 추가하는 방법은 무엇입니까?다음 기사：Go에서 파일에 텍스트를 추가하는 방법은 무엇입니까?