하이퍼코어(Hypercore) 압축 방식 이해하기

하이퍼코어(Hypercore) 압축 방식 이해하기

TimescaleDB에서 데이터를 행 저장소(rowstore)로부터 컬럼 저장소(columnstore)로 변환할 때, 데이터 타입에 따라 서로 다른 압축 알고리즘을 써요. 이 페이지에서는 하이퍼코어(Hypercore)가 실제로 사용하는 압축 방법들을 깊게 살펴봐요. 크게 정수형 압축, 부동소수점 압축, 그리고 데이터 타입에 구애받지 않는 압축으로 나뉘는데, 각각 어떤 데이터에 왜 좋은지 하나씩 짚어볼게요.

출처: 공식문서 - Compression methods in hypercore

데이터 타입별 압축 방식

  • 정수·타임스탬프·불리언 등 정수형 타입: 델타 인코딩(delta encoding), 델타-오브-델타(delta-of-delta), simple-8b, 런-렝스 인코딩(run-length encoding)을 조합해서 써요.
  • 반복 값이 많지 않은 컬럼: XOR 기반 압축에 사전 압축(dictionary compression)을 일부 결합해요.
  • 그 밖의 모든 타입: 사전 압축을 사용해요.

정수 압축의 simple-8b는 데이터를 역순으로도 풀 수 있게 확장되어 있어요. 시계열 워크로드에서 역방향 스캔 쿼리가 흔한데, 이런 쿼리가 훨씬 빨라져요.

정수 압축

델타 인코딩 (Delta encoding)

델타 인코딩은 데이터 객체를 통째로 저장하는 대신, 이전 값과의 **차이(델타)**만 저장해 필요한 정보량을 줄이는 방식이에요. 중복 정보가 많은 데이터에서 효과가 좋아서, 버전 파일 시스템 같은 워크로드에서 자주 쓰여요. 시계열 데이터에 적용하면 데이터 포인트마다 이전 포인트와의 차이만 저장하니까 더 적은 바이트로 표현할 수 있어요.

예를 들어 CPU, 여유 메모리, 온도, 습도를 시간에 따라 수집한 데이터셋이 있다고 해볼게요. 시간 컬럼을 UNIX 에포크 이후 초 단위 정수로 저장하면, 델타 인코딩 후에는 각 값이 이전 값에서 얼마나 변했는지만 저장하면 되죠.

time cpu mem_free_bytes temperature humidity
2023-04-01 10:00:00 82 1,073,741,824 80 25
5 seconds 16 -214,748,365 1 0
5 seconds 0 -88,876 0 0

대부분의 시계열 데이터셋은 무작위가 아니라 천천히 변하는 값이라서, 변화가 적거나 아예 없는 수백만 행에서는 저장 공간 절약이 상당해요.

델타-오브-델타 인코딩 (Delta-of-delta encoding)

델타-오브-델타는 델타 인코딩한 결과에 다시 델타 인코딩을 적용하는 거예요. 규칙적인 간격으로 수집되는 시계열 데이터셋이라면 시간 컬럼에 이 방식을 적용해서 0만 연속으로 저장하면 돼요. 델타 인코딩이 데이터의 1차 도함수를 저장한다면, 델타-오브-델타는 2차 도함수를 저장하는 셈이에요.

앞의 예시에 적용하면, 두 번째 행 이후 시간 컬럼의 5초 간격이 계속 일정하므로 전부 0으로 줄어들어요. 8바이트(64비트)짜리 전체 타임스탬프를 단 1비트로 줄이니까 64배 압축 효과가 나와요.

Simple-8b

델타 인코딩으로 저장할 자릿수를 크게 줄여도, 그 작아진 정수를 효율적으로 저장할 방법이 필요해요. 단순히 표준 정수 타입을 쓰면 0 값이라도 여전히 64비트를 소비하니까 실제로는 아무것도 아낀 게 아니죠. Simple-8b는 가변 길이 정수를 저장하는 가장 단순하고 작은 방법 중 하나로, 정수를 고정 크기 블록들로 저장해요. 각 블록 안의 모든 정수는 그 블록에서 가장 큰 정수를 표현하는 데 필요한 최소 비트 길이로 저장되고, 블록의 첫 비트들이 그 최소 비트 길이를 나타내요.

블록당 길이 정보를 정수마다가 아니라 블록마다 한 번만 저장하면 되고, 블록 크기가 고정이라 저장하는 정수 개수도 크기로부터 유추할 수 있어요. 가령 온도 델타 값들이 1, 10, 11, 13, 9, 100, 22, 11이라면 두 자릿수 5개짜리 블록과 세 자릿수 3개짜리 블록으로 나눠 저장할 수 있죠.

{2: [01, 10, 11, 13, 09]} {3: [100, 022, 011]}

Simple-8b는 이 방식 그대로 십진수 대신 이진수를 쓰고, 대개 64비트 블록을 사용해요. 일반적으로 정수가 길수록 블록 하나에 담기는 정수 개수는 줄어들어요.

런-렝스 인코딩 (Run-length encoding)

같은 값이 아주 많이 반복된다면 런-렝스 인코딩으로 더 큰 압축을 얻을 수 있어요. 값이 자주 변하지 않거나, 앞선 변환이 변화를 없앤 경우에 효과적이에요. 시계열 데이터의 수십억 개 연속 0, 혹은 백만 개가 똑같이 반복되는 문자열 문서 같은 곳에서 아주 잘 동작하는 고전적인 압축 알고리즘이에요.

가령 온도 델타 값이 11, 12, 12, 12, 12, 12, 12, 1, 12, 12, 12, 12라면, 각 값을 다 저장하는 대신 "몇 번 반복인지(런)"만 담아 {run; value} 쌍으로 표현할 수 있어요.

{1; 11}, {6; 12}, {1; 1}, {4; 12}

이 방식은 11자리만 쓰면 되는데, 가변 길이 정수 12개를 최적으로 저장해도 23자리가 필요하니까 큰 절약이죠. 런-렝스 인코딩은 Simple-8b RLE처럼 더 고급 알고리즘의 구성 요소로도 쓰여요. TimescaleDB는 64비트 값과 RLE를 처리하기 위해 표준과 다른 크기를 쓰는 Simple-8b RLE 변형을 구현해요.

부동소수점 압축

반복 값이 많지 않은 컬럼에는 XOR 기반 압축을 사용해요. 표준 XOR 기반 압축도 역순으로 풀 수 있게 확장되어, 역방향 스캔 쿼리가 훨씬 빨라져요.

XOR 기반 압축

부동소수점은 보통 정수보다 압축이 어려워요. 고정 길이 정수는 앞쪽에 0이 많지만, 부동소수점은 특히 십진수에서 이진수로 정확히 표현할 수 없어 변환된 값이라면 가용 비트를 대부분 사용하거든요. 델타 인코딩 같은 기법은 비트를 충분히 줄이지 못해서 부동소수점엔 잘 맞지 않아요.

손실 없는 부동소수점 압축 중 단순하고 빠른 몇 안 되는 알고리즘이 XOR 기반 압축인데, Facebook의 Gorilla 압축 위에 구축되어 있어요. XOR은 배타적 논리합(exclusive or) 이진 함수예요. 이 알고리즘은 연속된 부동소수점 숫자를 XOR로 비교해서, 차이가 있는 경우에만 비트를 저장해요. 첫 데이터 포인트는 압축 없이 저장하고, 이후 포인트는 XOR된 값으로 표현해요.

데이터 타입 무관 압축

정수도 부동소수점도 아닌 값에는 **사전 압축(dictionary compression)**을 사용해요.

사전 압축

가장 오래된 손실 없는 압축 알고리즘 중 하나인 사전 압축은, 값을 직접 저장하는 대신 나타날 수 있는 값들의 목록(사전)을 만들고 그 안의 고유 값에 대한 인덱스를 저장해요. 데이터 타입과 무관하게 쓸 수 있고, 반복이 잦은 제한된 값 집합에서 특히 잘 동작해요.

예를 들어 측정별 도시 컬럼에 New York, San Francisco, San Francisco, Los Angeles가 있다면, 도시 이름 전체를 저장하는 대신 아래처럼 사전을 만들고 컬럼에는 인덱스만 저장해요.

{0: "New York", 1: "San Francisco", 2: "Los Angeles"}
City
0
1
1
2

반복이 많은 데이터셋이라면 상당한 압축을 얻는데, 도시 이름은 평균 11바이트인 반면 인덱스는 최대 4바이트라서 공간이 약 3배로 줄어요. TimescaleDB는 이 인덱스 목록을 Simple-8b+RLE로 한 번 더 압축해서 저장 비용을 더 줄여요. 다만 반복 값이 거의 없다면 사전이 원본과 비슷한 크기가 되는데, TimescaleDB는 이 경우를 자동으로 감지해서 사전을 쓰지 않고 폴백해요.

JSONB 압축

JSONB 컬럼은 두 층으로 압축해요.

  1. TimescaleDB 사전 압축: JSONB 데이터에 자체 사전 압축을 먼저 적용하되, JSONB 값이 고유하거나 거의 고유하면 효과가 떨어져요.
  2. PostgreSQL TOAST 압축: 사전 압축이 효과가 없으면 압축을 건너뛰고 PostgreSQL이 TOAST(Oversized-Attribute Storage Technique) 압축으로 처리하게 해요. 기본적으로 PostgreSQL은 pglz 압축을 쓰는데, lz4 같은 더 현대적인 압축 알고리즘을 쓰려면 default_toast_compression 구성 파라미터를 설정하면 돼요.

현재 TOAST 압축 설정을 확인하려면:

SHOW default_toast_compression;

더 알아보기 (Learn more)