시계열 데이터의 압축 - Gorilla Algorithm(고릴라 알고리즘)

사내 데이터베이스에는 엄청나게 많은 시계열 데이터들이 있다.

이 데이터들을 조회하거나 적재할 때 많은 시간이 소요되는데, 이 문제점을 해결해줄 것이 바로 시계열 데이터의 압축(Time-Series Compression)이다. 

 

시계열 데이터의 압축 알고리즘 중, 가장 대중적으로 사용되는 알고리즘인 "고릴라 알고리즘" 에 대해 포스팅을 해 보자.

 

포스팅 전, 1-2주 정도 시간을 가지고 논문과 여러 참고자료를 조사하고 분석했다. 

회사에서 신규 프로젝트로 구현해야 하는 것이 "시계열 평가 데이터 압축 모듈 구현"이라 분석하지 않을 수 없었다.

https://www.vldb.org/pvldb/vol8/p1816-teller.pdf

 

한글로 된 레퍼런스는 거의 보이지 않았고, 영어로 논문에 대해 의견을 내거나 분석한 레퍼런스들이 대부분이었다. (네이버 개발 컨퍼런스, DEVIEW2023에서 언급된 자료를 참고하기도 했다.)

지금까지 분석한 것들 중 가장 참고자료가 없었던 주제이지 않았나 싶다.

1. 고릴라 데이터베이스

페이스북에서 2015년에 고안해낸 고성능이면서 확장 가능한 인메모리 시계열 데이터베이스(TSDB). 

주로 시스템 모니터링 데이터를 실시간으로 수집하고 분석하기 위해 사용되는데, 데이터를 인메모리에 저장하여 빠른 읽기 및 쓰기 성능을 제공하며, 최종적으로 Hbase와 같은 영구 저장소에 데이터를 기록하는 쓰루 캐시(실시간)로 작동한다.

2. 고릴라 데이터베이스의 핵심 알고리즘

고릴라 데이터베이스의 핵심 알고리즘 즉, 고릴라 알고리즘은 크게 두 가지의 알고리즘으로 수행된다.

두 가지 알고리즘 전부 비손실 압축으로, 변화량에 기반한 압축 기법이면서 여러 언어로 구현된 깃허브 프로젝트들이 있다. (검증이 됐는지는 모르겠다)

TimeStamp 압축과 Value(floating) 압축인데, 이 두 개의 압축을 분석하고 이해해 보자.

 

2.1. TimeStamp 압축

고릴라 알고리즘의 TimeStamp 압축은 시계열 데이터의 TimeStamp값을 압축한다.

각 타임스탬프 데이터 포인트는 해당 시간의 타임스탬프 값을 나타내는 64비트 값 쌍으로 구성된다. 

타임스탬프와 값은 이전 값에 대한 정보를 사용하여 개별적으로 압축하는 차분(Delta) 코딩을 활용한다.

 

대부분의 타임스탬프 데이터 소스는 일정한 간격(30초 또는 60초)으로 데이터를 기록한다는 점이 매우 중요한 핵심 부분이다.

때때로 데이터 포인트가 약간 일찍 또는 늦게 기록될 수 있지만, 이러한 값 또한 손실 없이 압축이 가능하다.(당연하게도 오차가 빈번하면 압축률이 저하된다)

 

하지만 이렇게 단순히 차이값만 저장하지는 않는다.

고릴라 알고리즘에서의 TimeStamp 압축은 차이값의 차이값. 즉 델타델타(Delta of Delta) 기법을 사용한다.

 

시계열 데이터 특성상 규칙적으로 특정 시간 만큼 증가되는 형태에서, 타임스탬프의 델타델타를 구하면 세번째 row부터는 값이 일반적으로 0이 나타나게 된다. (아닐 수도 있다. 오차가 있다면 그에 대한 비트 분기처리가 수행됨.)

 

이러한 특성을 이용해서 오차가 없다면 1비트(단일 '0' 비트)로 타임스탭프 값들을 대폭 압축이 가능하다.

 

위 자료를 보면, 첫 번째 데이터는 그대로 저장된다.

두 번째 데이터는 시간 변화량 (위 자료에서는 62초) 만큼 저장이 되고, 

세번째 데이터 부터는 시간 변화량의 변화량(-2초,0초,0초...) 만큼 저장이 된다

 

하지만 방금 말했듯이, 오차에 대한 처리도 추가적으로 해야한다.

 

오차를 처리하기 위해서는 컨트롤 비트가 필요한데, 총 5개의 분기처리가 된다.

 

델타의 델타 값에 따라 컨트롤비트와 데이터를 총 5가지의 분기처리에 맞게 저장하면서 비트 수가 달라지고, 이러한 컨트롤비트는 압축 해제할 때 요긴하게 사용된다.

 

이렇게 해서 어떻게 저장이 되는걸까? 

 

저장이 되는 비트 시퀀스는 아래와 같다.

 

Value는 아래 설명처럼 압축되어 비트 시퀀스에 적재된다.

 

 

 

2.1. Value 압축

고릴라 알고리즘의 Value 압축은 부동 소수점 데이터 (floating data)를 압축한다. 

 

Gorilla 압축 알고리즘의 Value 압축은 두 가지 핵심 개념이 있다. 바로 부동소수점과 배타논리합(XOR) 연산이다.

학부생때 고정 소수점과 부동 소수점에 대해 공부한 기억이 있지만 그때처럼 부동 소수점 연산까지 수행하지는 않고, 이미 부동소수점화된 float(단정밀도)와 double 데이터(배정밀도)를 압축하는 것이다.

 

배타논리합 연산은 비트가 같으면 0, 다르면 1을 output하는 연산이다. (엄청 쉽게 설명한 것임)

 

일단, 먼저 가장 초기 값을 이진화하여 비트 시퀀스에 저장한다.

두번째 Value부터는 이진화된 값을 바로 저장하는것이 아니라 이전 값과의 XOR연산을 한다.

 

 

위 자료를 보면, 선행 0비트와 meaningful bit, 후행 0비트라고 써있는 0의 개수가 중요하다.

 

이전 값으로부터 변화량이 적다면 배타논리합 연산의 특징으로 0의 개수가 많아지게 되는데, 그 개수를 단순히 숫자로 표현한다는 것이다.

당연하게도 이런 식으로 연산하게 된다면 변화량이 적은 부동소수점 값들은 압축률이 상당히 좋을 것이다. (변화량이 없으면 더 좋고)

이러한 압축 알고리즘도 차분 코딩에 속한다. (변화량에 기반한 압축이니깐) 그래서 XOR Based Delta Coding이라고도 부른다고 한다.

 

그리하여 XOR연산이 완료된 저 값을 어떻게 저장하느냐가 관건이다. 이 부분이 이해하는데 가장 어려움이 있지 않았나 생각이 든다.

아래의 자료를 보자.

실 개발 시에는 전부 2진수로 표현하여 연산해야 한다. 위 자료는 가독성을 위해서 16진수와 2진수를 혼합해서 표기한 것(컨트롤비트는 2진수로 표현했다.)

 

먼저 이전 XOR값을 알고 있어야 한다. 세 가지로 분기 처리가 되는데, 

 

1. 값이 완전히 똑같아서 XOR연산의 결과가 0이라면 단일 '0'비트를 저장한다.

2. 비트 범위가 일치한다면 컨트롤비트 10과 meaningful bit를 저장한다.

3. 비트 범위가 일치하지 않다면 컨트롤비트 11과 선행 0비트 개수, meaningful bit 길이, meaningful bit를 저장한다.

 

선행 0비트 개수와 meaningful bit 길이를 알아야 다음 데이터를 압축할때 비트 범위가 일치한지, 일치하지 않는지를 체크할 수 있다. 그리고 압축을 해제할때도 사용할 수 있다.

 

여기에서 컨트롤 비트는 크기가 2 고정이고, 선행 0비트 개수 비트도 5비트 고정, meaningful 비트 길이 비트도 6비트 고정이다. 

가변인 것은 meaningful bit 뿐이다.

 

그럼  두번째 값은 어떻게 비트 범위를 체크하는거지?

첫 번째 값은 이진화한 그대로의 값을 저장하고, 두번째 값에 컨트롤 비트를 할당하려고 하는데 여기서 이전 XOR값을 알 수가 없다. (처음으로 XOR연산을 했으니 당연히 알 수 없다)

그렇게 되면 비트 범위가 일치하지 않는 11 컨트롤비트를 가진 비트들로 저장하면 되는 것이다.(생각해 보면 당연한 것.. 원본이랑 비트범위가 일치할 리가 없다.)

 

실제 연산 결과 표를 보자

 

이렇게 BITS OUT처럼 압축이 되는 것이다. 중간중간 중복되는 데이터가 있으면 단일 0비트를 저장하게 되기 때문에 압축 효율이 좋아질 것이다.

 

3. 성능그래프

페이스북에서 공개한 논문의 성능 그래프를 보자.

TimeStamp는 엄청 좋은 성능, Value는 준수한 성능을 보여준다.

 

4. 마치며

처음으로 논문을 분석하면서 연구해보았는데, 꽤 좋은 경험이었다.

비트 단위 연산과 압축으로 성능을 어떻게 개선하는지에 대해 감을 충분히 잡았고, 다음 포스팅으로는 이걸 자바로 구현하는 작업을 해볼 예정이다. 

 

-----------2024.09.03 추가----------

https://wn1331.tistory.com/277

데이터 압축을 위한 Gorilla 알고리즘 적용 사례: 사내 솔루션 개발기 및 회고

 

 

5. 참고한 자료 / 논문

1. Gorilla: A Fast, Scalable, In-Memory Time Series Database. https://www.vldb.org/pvldb/vol8/p1816-teller.pdf

 

2. https://blog.acolyer.org/2016/05/03/gorilla-a-fast-scalable-in-memory-time-series-database/

Gorilla: A fast, scalable, in-memory time series database | the morning paper

 

3. https://clemenswinter.com/2024/04/07/the-simple-beauty-of-xor-floating-point-compression/

The Simple Beauty of XOR Floating Point Compression

 

4. https://docs.timescale.com/use-timescale/latest/compression/compression-design/

Timescale Documentation | Designing your database for compression