Facebook 모니터링팀은 2015년 기준으로 초당 1,200만 개의 데이터 포인트가 쏟아지는 상황에서, 포인트당 16바이트였던 저장 공간을 평균 1.37바이트까지, 12배로 줄인 인메모리 시계열 DB Gorilla를 VLDB 2015에 발표했어요. 이 12배 압축 중 값(value) 압축은 XOR 연산이 맡고, 타임스탬프 압축은 완전히 다른 아이디어인 “델타의 델타(delta-of-delta)“가 맡는데, 값 압축은 별도 포스트에서 다루고 여기서는 이 타임스탬프 압축 알고리즘만 파고들어요. 60초마다 한 번씩 찍히는 흔한 시계열 타임스탬프를, Gorilla는 대체 어떻게 1비트짜리 정보로까지 줄인 걸까요?
왜 타임스탬프도 따로 압축해야 하나
시계열 데이터 포인트 하나는 64비트 타임스탬프와 64비트(배정밀도 부동소수점) 값의 쌍으로 이루어지는데, 이 둘을 압축하지 않고 그대로 저장하면 포인트 하나에만 16바이트가 들어가요. Facebook의 운영 데이터 저장소(ODS)가 초당 1,200만 개의 포인트를 받는다고 하면 압축 없이는 하루에만 16TB에 달하는 RAM이 필요한 규모였고, 이는 실제 서비스에 투입하기엔 지나치게 무거운 수준이었어요. 그래서 Gorilla 연구팀은 타임스탬프와 값을 완전히 독립된 스트림으로 나눠 각각 압축했는데, 값 쪽은 이전 값과의 XOR 연산을 활용하는 반면 타임스탬프 쪽은 전혀 다른 성질, 즉 “시계열 데이터는 대개 일정한 간격으로 수집된다”는 특성을 파고들었어요. 논문은 실제로 ODS에 들어오는 타임스탬프 대다수가 60초 같은 고정 주기로 찍히고, 가끔 1초 정도 앞뒤로 밀리는 지터만 존재한다는 점을 근거로 들었어요.
1차 차분: 델타부터 계산한다
델타(delta)는 인접한 두 타임스탬프 사이의 시간 간격, 즉 현재 타임스탬프에서 바로 이전 타임스탬프를 뺀 값이에요. 예를 들어 타임스탬프가 02:01:02, 02:02:02, 02:03:02처럼 정확히 60초 간격으로 들어온다면 델타는 계속 60, 60, 60으로 이어져요. 절대 타임스탬프 값 자체는 2015년 3월 24일 기준으로도 32비트를 훌쩍 넘는 큰 정수지만, 델타는 보통 수십에서 수백 수준의 작은 정수로 줄어들기 때문에 이 시점에서 이미 상당한 압축 효과가 생겨요. 하지만 Gorilla 팀은 여기서 멈추지 않았는데, 델타 자체가 매번 60이라는 값을 반복해서 저장해야 한다는 점에 주목했어요.
델타의 델타: 진짜 압축이 시작되는 지점
델타의 델타(delta-of-delta)는 현재 델타에서 바로 직전 델타를 한 번 더 뺀 2차 차분값으로, 타임스탬프가 일정한 간격을 유지하는 구간에서는 이 값이 0으로 수렴한다는 게 핵심이에요. 논문은 이를 세 번째 타임스탬프 $t_n$에 대해 $D = (t_n - t_{n-1}) - (t_{n-1} - t_{n-2})$라는 공식으로 정의하는데, 직전 두 델타가 똑같이 60이었다면 $D$는 정확히 0이 돼요. Figure 2에 실린 논문의 예시를 그대로 가져오면, 02:00:00·02:01:02·02:02:02·02:03:02 네 개의 타임스탬프에서 델타는 각각 62, 60, 60으로 계산되고 이때 세 번째 델타의 델타는 60 − 60 = 0, 반면 두 번째 델타의 델타는 60 − 62 = −2가 돼요. 여기서 끝이 아니에요 — 데이터 포인트 하나가 중간에 누락돼도 이 구조는 여전히 잘 버텨요. 논문은 60초 간격 시계열에서 포인트 하나가 빠지면 델타가 60, 60, 121, 59처럼 나오고 이때의 델타의 델타는 0, 61, −62가 되어, 여전히 작은 범위 안에 값이 들어온다는 점을 예로 들었어요.
가변 길이 비트로 인코딩하는 구체적 알고리즘
Gorilla는 블록 하나(2시간 단위)의 맨 앞에서만 완전한 타임스탬프를 저장하고, 그 이후로는 전부 델타의 델타 값을 다음 규칙에 따라 가변 길이 비트로 인코딩해요. 블록 헤더에는 2시간 경계에 맞춰 정렬된 시작 타임스탬프 $t_{-1}$을 그대로 저장하고, 블록의 첫 번째 실제 데이터 포인트 $t_0$은 $t_{-1}$과의 델타를 14비트로 저장해요(2시간, 즉 7,200초를 표현하기에 14비트면 충분하다는 계산에서 나온 값). 세 번째 포인트부터는 델타의 델타 $D$의 크기에 따라 다섯 가지 경우로 나눠 인코딩하는데, 순서대로 정리하면 다음과 같아요.
- $D = 0$: 컨트롤 비트 없이
0한 비트만 저장한다. - $D \in [-63, 64]$:
10두 비트를 붙이고 7비트로 값을 저장한다 (총 9비트). - $D \in [-255, 256]$:
110세 비트를 붙이고 9비트로 값을 저장한다 (총 12비트). - $D \in [-2047, 2048]$:
1110네 비트를 붙이고 12비트로 값을 저장한다 (총 16비트). - 그 외의 경우:
1111네 비트를 붙이고 $D$ 전체를 32비트로 저장한다 (총 36비트).
이 다섯 개 구간은 논문이 실제 프로덕션 시계열 샘플을 분석해 정한 값인데, 각 구간의 상한이 조금씩 여유를 두고 있는 이유도 나와 있어요. 예컨대 [-255, 256] 구간은 4분 간격으로 찍히는 시계열에서 포인트 하나가 통째로 빠지는 흔한 사례까지 커버하도록 일부러 넉넉하게 잡은 범위예요. 앞쪽 비트(0, 10, 110, 1110, 1111)가 뒤에 이어지는 값의 비트 폭을 알려주는 일종의 헤더 역할을 하기 때문에, 디코더는 이 프리픽스만 읽고도 몇 비트를 더 읽어야 할지 정확히 알 수 있어요.
실제 데이터에서는 얼마나 압축되나
Gorilla 논문은 실제 ODS 운영 데이터에서 뽑은 44만 개의 타임스탬프 샘플을 대상으로 델타의 델타 분포를 직접 측정했고, 결과는 압도적으로 한쪽에 쏠렸어요. Figure 3에 따르면 전체 타임스탬프의 96.39%는 델타의 델타가 정확히 0이라 단 1비트로 압축됐고, 0.19%는 9비트([-63,64] 구간), 3.35%는 12비트([-255,256] 구간), 나머지 0.06% 정도만 16비트 이상(그중 상당수는 최악의 경우인 36비트)을 사용했습니다. 다시 말해 100개의 타임스탬프 중 96개는 압축 후 정확히 1비트짜리 정보로 남고, 원래 64비트였던 정수가 평균적으로는 그보다 훨씬 작은 크기로 줄어드는 셈이에요. 이 수치는 시계열 압축에서 값(XOR)보다 타임스탬프(delta-of-delta) 쪽이 오히려 더 극단적으로 잘 먹힌다는 걸 보여주는 결과이기도 해요.
블록 크기가 압축률과 조회 성능의 균형점을 정한다
Gorilla가 압축 블록을 2시간 단위로 자르는 이유는 압축률을 최대로 끌어올리는 지점과 조회 시 디코딩 비용이 지나치게 커지지 않는 지점 사이의 균형을 맞추기 위해서예요. 블록이 커질수록 헤더(완전한 타임스탬프)에 들어가는 고정 비용의 비중이 줄어 압축률은 계속 좋아지지만, 논문에 실린 실험(Figure 6)에 따르면 블록 크기를 2시간 이상으로 늘려도 데이터 포인트당 평균 압축 크기가 1.37바이트 선에서 더 줄지 않는 것으로 나타났어요. 반대로 블록이 지나치게 크면 특정 짧은 구간의 데이터를 읽을 때도 블록 전체를 처음부터 순차적으로 디코딩해야 하는 비용이 커지는 트레이드오프가 있는데, Gorilla는 이 지점에서 2시간을 실용적인 절충점으로 선택했어요.
오늘날 홈랩 모니터링 스택에서도 살아있는 아이디어
Prometheus의 TSDB는 Gorilla 논문에서 직접 영감을 받아 값에는 XOR 인코딩을, 타임스탬프에는 지금까지 설명한 것과 동일한 delta-of-delta 인코딩을 적용하고 있어요. Grafana와 Prometheus로 홈랩 모니터링 대시보드를 구성해본 적이 있다면, node_exporter가 15초나 60초 같은 일정한 스크레이프 주기로 지표를 밀어 넣을 때마다 내부적으로는 이 논문에서 설명한 것과 같은 원리로 타임스탬프 대부분이 1비트로 압축되고 있었던 셈이에요. Gorilla의 전체 아키텍처(TSmap, ShardMap 같은 인메모리 구조)나 XOR 기반 값 압축의 세부 구현은 다른 포스트와 Prometheus TSDB와의 비교에서 더 깊이 다루니 함께 참고하면 좋아요.
결론
델타의 델타는 복잡한 수학이 아니라 “시계열은 대개 일정한 간격으로 찍힌다”는 아주 단순한 관찰 하나로 시작된 아이디어예요. 그런데 이 관찰 하나가 44만 개 샘플 중 96.39%를 단 1비트로 줄이는 결과로 이어졌다는 사실이, Gorilla 논문이 지금까지도 Prometheus를 비롯한 여러 시계열 DB의 설계에 인용되는 이유를 잘 보여줘요. 결국 Gorilla가 타임스탬프를 1비트로 압축한 방법은 특별한 하드웨어나 복잡한 수식이 아니라, 데이터가 가진 규칙성을 있는 그대로 읽어내고 그 규칙성이 깨지는 소수의 예외만 가변 길이 비트로 별도 처리한 것뿐이었어요.
자주 묻는 질문
Q1. Delta-of-delta 인코딩이 정확히 뭔가요?
Delta-of-delta는 연속된 두 타임스탬프 델타(간격) 사이의 차이를 다시 한번 계산해 저장하는 2차 차분 압축 기법이에요. 타임스탬프가 60초처럼 거의 일정한 간격으로 찍히면 이 값이 대부분 0이 되기 때문에, 원본 64비트 정수 대신 단 1비트로 표현할 수 있어요.
Q2. 왜 델타를 한 번 더 계산하나요? 델타만 저장하면 안 되나요?
델타(1차 차분)만 저장해도 정보량은 줄지만 값 자체는 수집 주기(예: 60)만큼 여전히 크게 남아 매번 여러 비트가 필요해요. 반면 델타의 델타는 간격이 일정한 구간에서 0에 수렴하기 때문에, 1차 차분보다 한 단계 더 작은 숫자로 표현할 수 있어 압축 효율이 훨씬 높아져요.
Q3. 타임스탬프가 정확히 일정한 간격이 아니고 1~2초씩 흔들리면 어떻게 되나요?
그래도 대부분 문제없이 작동해요. Gorilla 논문은 델타의 델타 값을 -63~64, -255~256, -2047~2048처럼 여러 범위로 나눠 가변 길이 비트로 인코딩하기 때문에, 약간의 지터가 있어도 값이 여전히 작은 범위 안에 들어가 몇 비트만 추가로 쓰면 돼요.
Q4. 실제로 타임스탬프가 몇 비트로 압축되나요?
Gorilla 논문이 ODS 운영 데이터 44만 개 타임스탬프 샘플을 분석한 결과, 전체의 96.39%가 단 1비트로 압축됐고, 0.19%는 9비트, 3.35%는 12비트, 나머지 0.06%만 16비트 이상을 사용했어요.
Q5. 왜 하필 2시간 단위로 블록을 나누나요?
Gorilla는 압축 블록을 2시간 단위로 잘라 블록 헤더에만 완전한 타임스탬프를 저장하고, 이후 값은 전부 델타의 델타로 이어가요. 논문에 실린 실험에서 블록 크기를 2시간보다 더 늘려도 압축률 개선이 미미했기 때문에, 압축 효율과 조회 시 디코딩 비용 사이의 균형점으로 2시간을 선택했어요.
Q6. Prometheus도 이 알고리즘을 그대로 쓰나요?
네, Prometheus의 TSDB는 Gorilla 논문에서 영감을 받아 값에는 XOR 인코딩을, 타임스탬프에는 동일한 delta-of-delta 인코딩을 적용해요. 스크레이프 주기가 15초처럼 일정하게 유지되는 한 대부분의 타임스탬프가 1비트로 압축되는 효과를 실제 운영 환경에서도 그대로 볼 수 있어요.
관련 글
