인플럭스DB(InfluxDB) #6 - In-Memory Indexing과 TSM(Time-Structured Merge Tree)

728x90

이번 포스팅은 요즘 핫한 InfluxDB에 대하여 작성하도록 하겠습니다.

InfluxDB 역시 작년 기상청 프로젝트에서 전국에서 관측되는 데이터를 효과적으로 처리하기 위하여 검토되었고 그때 자료조사를 한 내용입니다.

순서는

2020/06/11 - [분류 전체보기] - InfluxDB #6 - In-Memory Indexing과 TSM(Time-Structured Merge Tree)

으로 진행되며 도입 검토 차원에서 이루어진 조사라서 실무적용 보다는 InfluxDB란 어떤 것인지 파악하는 정도로만 생각하시면 될듯합니다.

1. InfluxDB 스토리지 엔진과 TSM(Time-Structured Merge Tree)

InfluxDB 스토리지 엔진은 LSM 트리와 매우 유사합니다.
그것은 미리 쓰기 로그와 LSM 트리의 SSTables와 개념이 유사한 읽기 전용 데이터 파일 모음을 가지고 있습니다.
TSM 파일에는 정렬·압축된 시리즈 데이터가 들어있습니다.
InfluxDB는 각 블록에 대해 shard를 만듭니다.
예를 들어 보존 기간이 제한되지 않은 보존 정책이 있는 경우 7일 단위로 차단 목록이 생성됩니다.
이러한 각 조각은 기본 저장소 엔진 데이터베이스에 매핑됩니다.
이러한 각 데이터베이스에는 고유한 WAL 및 TSM 파일이 있습니다.

2. Storage engine

스토리지 엔진은 여러 구성 요소를 함께 묶고 시리즈 데이터를 저장하고 쿼리하기 위한 외부 인터페이스를 제공합니다.
각각 특정 역할을 수행하는 여러 구성 요소로 이루어져 있습니다.

- In-Memory Index: 인 메모리 인덱스는 측정, 태그 및 시리즈에 빠르게 액세스 할 수 있는 샤드(shard)의 공유 인덱스입니다. 인덱스는 엔진에서 사용하지만, 저장소 엔진 자체에만 국한되지는 않습니다.

- WAL: WAL은 쓰기에 최적화된 저장 형식으로 내구성이 있지만 쉽게 쿼리 할 수는 없습니다. WAL에 대한 쓰기는 고정된 크기의 세그먼트에 추가됩니다.

- Cache: 캐시는 WAL에 저장된 데이터의 메모리 내 표현입니다. 런타임시 조회되고 TSM 파일에 저장된 데이터와 병합됩니다.

- TSM Files: TSM 파일은 압축 된 시리즈 데이터를 컬럼 형식으로 저장합니다.

- FileStore: FileStore는 디스크의 모든 TSM 파일에 대한 액세스를 조정합니다. 기존 파일이 대체 될 때 TSM 파일이 자동 설치되고 더 이상 사용되지 않는 TSM 파일은 제거됩니다.

- Compactor: Compactor는 덜 최적화 된 Cache 및 TSM 데이터를 더 읽기 최적화된 형식으로 변환합니다. 이 작업은 시리즈를 압축하고, 삭제된 데이터를 제거하고, 인덱스를 최적화하고, 작은 파일을 더 큰 파일로 결합하는 방식으로 수행됩니다.

- Compaction Planner: 압축 계획은 압축을 위해 준비된 TSM 파일을 판별하고 여러 동시 압축이 서로 간섭하지 않도록 합니다.

- Compression: 압축은 특정 데이터 유형에 대한 다양한 인코더 및 디코더에 의해 처리됩니다. 일부 인코더는 상당히 정적이며 항상 동일한 유형의 같은 방식으로 인코딩됩니다. 다른 인코더는 데이터의 모양에 따라 압축 전략을 전환합니다.

- Writers/Readers: 각 파일 유형(WAL 세그먼트, TSM 파일, 삭제 표시 등)에는 형식 작업을 위한 작성자 및 독자가 있습니다.

3. WAL(Write Ahead Log)

WAL은 여러 개의 파일로 구성되어 있습니다.
(_000001.wal) 파일 번호는 단조롭게 증가하며 WAL 세그먼트라고합니다.
세그먼트의 크기가 10MB에 도달하면 세그먼트가 닫히고 새 세그먼트가 열립니다.
각 WAL 세그먼트는 여러 개의 압축 블록을 저장하고 삭제합니다.
쓰기가 들어 오면 새 포인트에 일련번호를 붙이고, Snappy을 사용하여 압축되어 WAL 파일에 기록됩니다.
파일은 fsync되고, 성공이 반환되기 전에 데이터는 메모리 내 인덱스에 추가됩니다.
높은 처리 성능을 달성하려면 batch point를 함께 사용해야 합니다.(최적의 배치 크기는 배치 당 5,000-10,000 포인트)
WAL의 각 항목은 항목 유형(쓰기 또는 삭제)을 나타내는 단일 바이트, 압축된 블록의 길이에 대한 4바이트의 uint32, 압축된 블록과 함께 TLV(Type-length-value)표준을 따릅니다.

4. Cache

캐시는 현재 WAL에 저장된 모든 데이터 포인트의 메모리 내 사본입니다.
포인트는 키, 즉 측정, 태그 세트 및 고유 필드로 구성됩니다.
각 필드는 고유한 시간 순서대로 유지됩니다. 캐시 데이터는 메모리에 있는 동안 압축되지 않습니다.
스토리지 엔진에 대한 쿼리는 캐시의 데이터를 TSM 파일의 데이터와 병합합니다.
쿼리는 쿼리 처리 시 캐시에서 만들어진 데이터의 복사본에 대해 실행됩니다.
이 방법은 쿼리가 실행되는 동안에는 결과에 영향을 주지 않습니다.
캐시로 전송된 삭제(Deletes)는 주어진 키 또는 지정된 키의 특정 시간 범위를 지웁니다.
캐시는 스냅샷 동작에 대한 몇 가지 컨트롤을 제공합니다.
두 가지 가장 중요한 컨트롤은 메모리 제한입니다.
lower bound인 cache-snapshot-memory-size를 넘으면 TSM 파일에 대한 스냅샷을 트리거하고 해당 WAL 세그먼트를 제거합니다.
또한, upper bound인 cache-max-memory-size를 초과하면 캐시가 새로운 쓰기를 거부하게 됩니다.
이러한 구성은 메모리 부족 상황을 방지하고 인스턴스가 유지할 수 있는 것보다 빠르게 데이터를 쓰는 클라이언트에게 억압을 가하는 데 유용합니다. 메모리 임계값에 대한 검사는 모든 쓰기에서 발생합니다.
다른 스냅샷 컨트롤은 시간 기반입니다.
유휴 임계값 cache-snapshot-write-cold-duration은 지정된 간격 내에 쓰기를 수신하지 않는 경우 캐시가 TSM 파일에 스냅샷 하도록 합니다.
메모리 내 캐시는 디스크의 WAL 파일을 다시 읽음으로써 재시작 시 다시 생성됩니다.

5. TSM 파일

TSM 파일은 메모리 맵핑 된 읽기 전용 파일의 콜렉션입니다.
이 파일의 구조는 LevelDB 또는 다른 LSM Tree 변형의 SSTable과 매우 유사하게 보입니다.

- TSM 파일은 Header, Blocks, Index 및 Footer의 네 부분으로 구성됩니다.

Header

5 bytes

Blocks

N bytes

Index

N bytes

Footer

4 bytes

- 헤더는 파일 형식과 버전 번호를 식별하는 Magic 번호입니다.

Header

Magic

4 bytes

Version

1 byte

- 블록은 CRC32 체크섬 및 데이터 쌍의 시퀀스입니다. 블록 데이터는 파일에 불투명합니다. CRC32는 블록 레벨 오류 감지에 사용됩니다. 블록의 길이는 색인에 저장됩니다.

Blocks

Block 1

Block 2

Block N

CRC

4 bytes

Data

N bytes

CRC

4 bytes

Data

N bytes

CRC

4 bytes

Data

N bytes

- 블록 다음에는 파일의 블록 Index가 있습니다. Index는 키에 의해 사전식으로 순서화된 색인 항목의 순서로 구성됩니다.

- 키에는 측정 이름, 태그 세트 및 하나의 필드가 포함됩니다.

- 포인트 당 여러 필드는 TSM 파일에 다중 색인 항목을 작성합니다.

- 각 색인 항목은 Key 길이와 Key, 블록 유형 (float, int, bool, string) 및 그 키에 이어지는 색인 블록 항목 수의 순서로 시작됩니다.

- 각 인덱스 블록 항목은 블록의 최소 및 최대 시간, 블록이 위치한 파일의 오프셋 및 블록의 크기로 구성됩니다.

- 키가 들어있는 TSM 파일의 각 블록에 대해 하나의 인덱스 블록 항목이 있습니다.

- 인덱스 구조는 모든 블록에 효율적으로 액세스 할 수 있을 뿐 아니라 주어진 키에 액세스하는 것과 관련된 비용을 결정할 수 있습니다.

- 키와 타임스탬프가 주어지면 파일에 해당 타임스탬프의 블록이 포함되어 있는지 확인할 수 있습니다.

- 블록을 검색하기 위해 블록이 상주하는 위치와 읽어야 하는 데이터의 양을 결정할 수도 있습니다.

- 블록 크기를 알면 IO문을 효율적으로 프로비저닝 할 수 있습니다.

Index

Key Len

2 bytes

Key

N bytes

Type

1 byte

Count

2 bytes

Min Time

8 bytes

Max Tim

8 bytes

Offset

8 bytes

Size

4 bytes

.......

- 마지막 섹션은 인덱스 시작 오프셋을 저장하는 Footer입니다.

Footer

Index Ofs

8 bytes

6. Compression

쿼리 할 때 각 블록을 압축하여 저장 공간과 디스크 IO를 줄입니다.
블록은 주어진 시리즈와 필드에 대한 타임스탬프와 값을 포함합니다.
각 블록은 압축된 타임스탬프 다음에 압축된 값이 오는 1바이트 헤더를 가집니다.

Type

1 Bytes

Len

VBytes

Timestamps

N Bytes

Values

N Bytes

타임스탬프와 값은 데이터 유형과 모양에 따라 인코딩을 사용하여 별도로 압축되고 저장됩니다.
이들을 독립적으로 저장하면 타임스탬프 인코딩을 모든 타임스탬프에 사용할 수 있고 다른 필드 유형에 대해 다른 인코딩을 사용할 수 있습니다.
예를 들어, 일부 포인트는 run-length 인코딩을 사용할 수 있지만 다른 포인트는 그렇지 않을 수 있습니다.
각 값 유형에는 나머지 바이트에 대한 압축 유형을 나타내는 1바이트 헤더가 들어있습니다.
4개의 상위 비트는 압축 유형을 저장하고 4개의 하위 비트는 필요한 경우 인코더가 사용합니다.
Timestamps

- 타임스탬프 인코딩은 적응적이며, 인코딩된 타임스탬프의 구조를 기반으로 합니다.

- 그것은 델타 인코딩, 스케일링 및 simple8b run-length 인코딩을 사용하여 압축의 조합을 사용하고, 필요하다면 압축하지 않아도 됩니다.

- 타임스탬프 해상도는 가변적이지만 압축되지 않은 상태로 저장하려면 최대 8바이트가 필요한 나노초만큼 세분화될 수 있습니다.

- 인코딩 중에 값은 먼저 델타 인코딩됩니다.

- 첫 번째 값은 시작 타임스탬프이며 후속 값은 이전 값과의 차이입니다.

- 이것은 보통 값을 압축하기 쉬운 아주 작은 정수로 변환합니다.

- 많은 타임스탬프 또한 단조롭게 증가하고 심지어 매 10초와 같이 시간의 경계에 있습니다.

- 타임스탬프가 이 구조를 가질 때, 10의 인수인 최대 공약수로 조정됩니다.

- 이것은 매우 큰 정수 델타를 압축률이 작은 델타로 변환하는 효과가 있습니다.

- 이러한 조정 된 값을 사용하여 모든 델타가 동일한 경우, 시간 범위는 run-length 인코딩을 사용하여 저장됩니다.

- run-length 인코딩이 불가능하고 모든 값이 (1<<60)-1(nanosecond resolution에서 ~36.5년) 미만인 경우 타임스탬프는 simple8b 인코딩을 사용하여 인코딩됩니다.

- Simple8b 인코딩은 다중 정수를 단일 64비트 단어로 묶는 64비트 워드 정렬 정수 인코딩입니다.

- 값이 최댓값을 초과하면 델타는 블록에 대해 각각 8바이트를 사용하여 압축되지 않은 상태로 저장됩니다.

- 이후의 인코딩은 패치된 프레임 참조(PFOR)와 같은 패치 된 구성표를 사용하여 outlier를 보다 효과적으로 처리할 수 있습니다.

Floats

- 플로트는 Gorilla: A Fast, Scalable, In-Memory Time Series Database 논문의 구현을 사용하여 인코딩됩니다.

- 인코딩은 연속된 값을 함께 XOR하여 값이 서로 가깝게 되면 작은 결과를 생성합니다.

- 델타는 제어 비트를 사용하여 저장되어 XOR 값에 선행0과 후행0을 표시합니다.

- 우리의 구현은 종이에 설명된 타임스탬프 인코딩을 제거하고 float 값만 인코딩합니다.

- 48바이트의 값과 타임스탬프가 21바이트/167비트 바로 아래로 압축됩니다.

Integers

- 정수 인코딩은 압축되지 않은 데이터의 값 범위에 따라 두 가지 전략을 사용합니다.

- 인코딩 된 값은 먼저 ZigZag 인코딩을 사용하여 인코딩됩니다.

- 이는 양의 정수 범위에서 양수 및 음수 정수를 끼워 넣습니다. 예를 들어 [-2, -1, 0, 1]은 [3, 1, 0, 2]가 됩니다.

- 모든 ZigZag 인코딩 값이 (1<<60)-1보다 작으면 simple8b 인코딩을 사용하여 압축됩니다.

- 값이 최댓값보다 큰 경우 모든 값은 블록에 압축되지 않은 상태로 저장됩니다.

- 모든 값이 동일하면, run-length 인코딩이 사용됩니다.

- 이것은 자주 일정한 값에 대해 잘 작동합니다.

Booleans

- 부울은 각 부울이 1비트를 사용하는 간단한 비트 패킹 전략을 사용하여 인코딩됩니다. 인코딩 된 부울의 수는 블록의 시작 부분에 가변 바이트 인코딩을 사용하여 저장됩니다.

Strings

- 문자열은 Snappy 압축을 사용하여 인코딩합니다. 각 문자열은 연속적으로 압축되며 하나의 큰 블록으로 압축됩니다.

7. Compactions

압축은 쓰기 최적화된 형식으로 저장된 데이터를 읽기 최적화된 형식으로 데이터 이전을 반복하는 프로세스입니다. 샤드가 글쓰기에 hot 상태일 때 일어나는 여러 단계의 압축이 있습니다.

Snapshots

- 캐시 및 WAL의 값은 TSM 파일로 변환되어 WAL 세그먼트에서 사용되는 메모리 및 디스크 공간을 확보해야 합니다.

- 이러한 압축은 캐시 메모리 및 시간 임계값을 기반으로 발생합니다.

Level Compactions

- 레벨 압축(레벨1-4)은 TSM 파일이 커짐에 따라 발생합니다.

- TSM 파일은 스냅샷에서 레벨1 파일로 압축됩니다.

- 멀티 레벨1 파일이 압축되어 레벨2 파일이 생성됩니다.

- 파일이 레벨4에 도달하고 TSM 파일의 최대 크기에 도달할 때까지 프로세스가 계속됩니다.

- 삭제, 인덱스 최적화 압축 또는 전체 압축을 실행해야 하는 경우가 아니면 압축되지 않습니다.

- 하위 레벨 압축은 블록 압축 해제 및 결합과 같은 CPU 집중적인 활동을 피하는 전략을 사용합니다.

- 보다 높은 수준의(덜 빈번한) 압축은 블록을 완전히 다시 압축하여 압축 비율을 높이기 위해 블록을 다시 결합합니다.

Index Optimization

- 레벨4 TSM 파일이 많이 누적되면 내부 인덱스가 더 커지고 액세스하는 데 많은 비용이 듭니다.

- 색인 최적화 압축은 일련의 색인을 하나의 TSM 파일로 정렬하여 일련의 색인을 새로운 TSM 파일 세트로 분할합니다.

- 색인 최적화 전에는 각 TSM 파일에는 대부분의 또는 모든 시리즈에 대한 포인트가 들어 있으므로 각각에는 동일한 시리즈 색인이 들어있습니다.

- 색인 최적화 후에는 각 TSM 파일에 시리즈에 대한 최소한의 포인트가 들어있으며, 파일 간에는 시리즈 중복이 거의 없습니다.

- 따라서 각 TSM 파일에는 전체 시리즈 목록의 사본 대신 작은 고유한 시리즈 색인이 있습니다.

- 또한, 특정 시리즈의 모든 포인트는 여러 TSM 파일에 분산되어 있지 않고 TSM 파일에 인접해 있습니다.

Full Compactions

- 전체 압축은 샤드가 장기간 쓰기가 차가워지거나 샤드에서 삭제된 경우 실행됩니다.

- 전체 압축은 최적의 TSM 파일 세트를 생성하고 레벨 및 색인 최적화 압축의 모든 최적화를 포함합니다.

- 조각이 완전히 압축되면 새로운 쓰기 또는 삭제가 저장되지 않으며 다른 압축이 실행되지 않습니다.

8. Writes

쓰기는 현재 WAL 세그먼트에 추가되며 캐시에도 추가됩니다.
각 WAL 세그먼트는 최대 크기를 가집니다.
현재 파일이 가득 차면 새 파일로 roll over를 씁니다.
캐시는 크기가 제한되어 있습니다.
스냅샷이 만들어지고 캐시가 너무 꽉 차있을 때 WAL 압축이 시작됩니다.
인바운드 쓰기 속도가 일정 기간 WAL 압축률을 초과하면 캐시가 가득 차게 되어 스냅샷 프로세스가 중단될 때까지 새로운 쓰기가 실패합니다.
WAL 세그먼트가 채워지고 닫히면 Compactor는 캐시를 스냅샷하고 새 TSM 파일에 데이터를 기록합니다.
TSM 파일이 성공적으로 기록되고 작성 및 fsync되면, FileStore에 의해 로드되고 참조됩니다.

9. Updates

업데이트(이미 존재하는 지점에 대해 더 새로운 값을 씀)는 normal write와 같이 발생합니다.
캐시 된 값은 기존 값을 덮어쓰므로 newer writes가 우선합니다.
쓰기가 이전 TSM 파일의 한 포인트를 겹쳐 쓸 경우, 포인트는 조회 런타임에서 병합되고 newer writes가 우선됩니다.

10. Deletes

삭제는 측정 항목 또는 시리즈에 대해 WAL에 삭제 항목을 쓰고 캐시 및 FileStore를 업데이트하여 발생합니다.
캐시는 모든 관련 항목을 제거합니다.
FileStore는 관련 데이터가 들어있는 각 TSM 파일에 대해 tombstone 파일을 작성합니다.
이러한 tombstone 파일은 시작 시 삭제된 항목을 제거하기 위해 압축하는 동안뿐만 아니라 블록을 무시하기 위해 사용됩니다.
부분적으로 삭제된 시리즈에 대한 조회는 압축이 TSM 파일에서 데이터를 완전히 제거할 때까지 query time 처리됩니다.

11. Queries

Query가 스토리지 엔진에 의해 실행되면, 그것은 본질적으로 특정 시리즈 키 및 필드와 연관된 주어진 시간에 대한 탐색입니다.
먼저 데이터 파일을 검색하여 검색어와 일치하는 시간 범위가 포함된 파일을 찾고 일치하는 시리즈를 포함합니다.
데이터 파일을 선택하고 나면 시리즈 키 인덱스 항목의 파일에서 위치를 찾아야 합니다.
각 TSM 색인에 대해 binary search를 실행하여 색인 블록의 위치를 찾습니다.
일반적으로 블록은 여러 TSM 파일에서 겹치지 않으며 인덱스 항목을 선형으로 검색하여 읽을 시작 블록을 찾습니다.
겹치는 시간 블록이 있는 경우 색인 항목이 정렬되어 더 새로운 쓰기가 우선 적용되고 쿼리 실행 중에 순서대로 블록을 처리할 수 있습니다.
인덱스 항목을 반복할 때 블록은 블록 섹션에서 순차적으로 읽혀집니다. 블록이 압축 해제되고 특정 지점을 찾습니다.

728x90

저작자표시

'개발관련 자료' 카테고리의 다른 글

인플럭스DB(InfluxDB) #8 - TSI(Time Series Index) 세부 정보 (0)	2020.06.11
인플럭스DB(InfluxDB) #7 - TSI(Time Series Index) 개요 (0)	2020.06.11
인플럭스DB(InfluxDB) #5 - Schema설계 및 데이터Layout (0)	2020.06.11
인플럭스DB(InfluxDB) #4 - SQL DB와 비교 (0)	2020.06.11
인플럭스DB(InfluxDB) #3 - 용어 정리 (0)	2020.06.11

안드로이드 발자취

인플럭스DB(InfluxDB) #6 - In-Memory Indexing과 TSM(Time-Structured Merge Tree)