Facebook 모니터링 팀이 2015년 VLDB에 발표한 Gorilla 논문은 초당 1200만 개씩 쏟아지는 데이터 포인트를 전부 메모리에 올려두겠다는, 당시로선 꽤 대담한 목표에서 출발했어요. 16바이트짜리 데이터 포인트를 그대로 저장하면 하루치만 16TB에 달해 메모리로 감당이 안 됐는데, 논문 저자들(Pelkonen 등, Facebook Inc.)은 여기서 XOR 연산 하나로 값을 평균 1.37바이트까지 줄이는 압축 스킴을 재설계해 문제를 풀었습니다. 연속된 실수값 사이의 XOR 연산 하나가 어떻게 12배에 가까운 압축률을 만들어내는 걸까요?
Gorilla가 실수값 압축에서 노린 것은 무엇일까?
Gorilla의 값 압축은 같은 시계열 안에서 연속된 값이 대체로 크게 변하지 않는다는 관찰에서 출발해요. 논문은 ODS(Operational Data Store) 운영 데이터를 분석한 결과 “대부분의 시계열에서 값이 이웃한 데이터 포인트와 비교했을 때 유의미하게 변하지 않았고, 많은 데이터 소스는 정수만 저장했다”고 밝히고 있어요. 부호, 지수부, 가수부 앞자리까지 거의 동일한 두 값이 연달아 들어오는 경우가 흔하다는 뜻인데, 저자들은 이 특성을 살려 기존에 과학 계산용 데이터에 쓰이던 무거운 예측 기반 압축 대신, 현재 값과 직전 값을 그냥 XOR하는 훨씬 가벼운 방식을 택했다고 설명해요. 두 값이 같으면 XOR 결과는 64비트가 전부 0이 되고, 값이 조금만 달라져도 실제로 달라진 가수부 몇 비트만 1로 남는 희소한 패턴이 만들어지는 게 핵심이에요.
XOR 압축 알고리즘은 정확히 어떻게 동작할까?
Gorilla의 값 압축은 새 값이 들어올 때마다 직전 값과 XOR한 뒤, 그 결과가 얼마나 “비어 있는지”에 따라 세 가지 경우로 나눠 비트를 씁니다. 논문 4.1.2절이 명시한 인코딩 규칙은 이렇습니다.
- 첫 번째 값: 압축 없이 64비트 그대로 저장한다.
- XOR 결과가 0인 경우: 직전 값과 완전히 같다는 뜻이므로 단 1비트(
0)만 기록한다. - XOR 결과가 0이 아닌 경우: 먼저 제어 비트
1을 쓰고, 그 XOR 값의 선행 0(leading zero) 개수와 후행 0(trailing zero) 개수를 계산해 다시 두 갈래로 나눈다.- 제어 비트
10: 새 XOR 값의 “의미 있는 비트 블록”이 직전에 저장했던 블록 범위 안에 그대로 들어간다면(즉 선행 0과 후행 0이 직전 값 이상이라면), 블록 위치 정보를 재사용하고 의미 있는 비트만 곧바로 이어 쓴다. - 제어 비트
11: 그렇지 않다면 선행 0의 개수를 5비트로, 의미 있는 비트의 길이를 6비트로 각각 새로 기록한 다음, 그 뒤에 의미 있는 비트 자체를 이어 쓴다.
- 제어 비트
11 경우의 오버헤드를 계산해보면 제어 비트 2개(1+1) + 선행 0 길이 5비트 + 의미 있는 비트 길이 6비트로, 실제 값 비트를 쓰기 전에만 13비트가 고정으로 붙어요. 그래서 값이 매번 들쭉날쭉 바뀌는 시계열보다, 어느 정도 패턴이 있는 시계열에서 압축 효율이 훨씬 좋게 나옵니다.
실제 숫자로 따라가 보는 인코딩 예시
논문 Figure 2는 12.0에서 24.0으로 값이 바뀌는 상황을 그대로 예시로 보여줘요. 12.0의 64비트 표현은 0x4028000000000000이고 24.0은 0x4038000000000000인데, 이 둘을 XOR하면 0x0010000000000000이 나옵니다. 이 값은 앞쪽에 0이 11개 이어지고 그다음 딱 1비트만 1이며, 그 뒤로는 다시 0으로 채워진 형태예요. 즉 “선행 0이 11개, 의미 있는 비트는 1개”인 셈이죠.
이걸 인코딩하면 제어 비트 11(2비트) + 선행 0 개수 11을 담는 5비트 + 의미 있는 비트 길이 1을 담는 6비트 + 실제 값 비트 1(1비트)로, 총 14비트에 이 값 하나가 담깁니다. 64비트 실수값이 14비트로 줄었으니 이 한 건만 놓고 보면 약 4.6배 압축이에요. 논문은 같은 그림에서 타임스탬프 압축까지 합쳐 48바이트(=384비트)짜리 원본 데이터 3건을 167비트, 그러니까 21바이트가 채 안 되는 크기로 줄인 전체 예시를 함께 보여주는데, 타임스탬프를 압축하는 델타의 델타 인코딩은 이 시리즈의 다른 글(시계열 델타의 델타 인코딩)에서 따로 다룰 예정이라 이 글에서는 값 압축에만 집중했어요.
논문이 실측한 압축률은 얼마나 될까?
Gorilla 논문은 실제 운영 데이터를 샘플링해 XOR 압축의 효과를 수치로 제시하고 있어요. Figure 5에서 160만 건의 실제 값을 샘플링한 결과, 전체 값의 59.06%가 단 1비트로 압축됐고(직전 값과 동일했다는 뜻), 28.30%는 평균 26.6비트인 10 제어 비트 경우로, 나머지 12.64%는 평균 39.6비트인 11 제어 비트 경우로 압축됐다고 보고합니다. 이 세 경우를 전부 가중 평균 내면 64비트였던 값 하나가 한 자릿수 비트 대로 줄어드는 셈이니, 얼마나 많은 실측 데이터가 “직전 값과 똑같거나 거의 비슷한” 패턴을 보이는지 짐작할 수 있어요.
여기서 끝이 아니에요. 논문은 값과 타임스탬프를 합친 전체 압축 결과도 별도로 제시하는데, Figure 6에서 압축 블록(윈도우) 크기를 늘려가며 측정한 결과 블록 크기가 2시간에 도달하면 데이터 포인트 하나당 평균 1.37바이트로 수렴하고, 그 이상 블록을 늘려도 추가 이득이 거의 없었다고 밝히고 있어요. 16바이트였던 원본 대비 정확히 12배 축소이자, 논문 초록에 나온 “Gorilla’s storage footprint를 10배 줄였다”는 표현보다도 더 구체적인 수치예요. 다만 이 1.37바이트는 값과 타임스탬프 압축을 합친 결과이므로, XOR 압축 자체의 기여도는 Figure 5의 비트 분포로 따로 확인해야 정확합니다.
Prometheus는 이 알고리즘을 그대로 가져다 썼다
Prometheus의 TSDB는 청크 인코딩에 Gorilla 논문의 XOR 압축 기법을 사실상 그대로 채택했어요. Prometheus 저장소의 tsdb/chunkenc/xor.go가 이 XOR 인코딩을 구현한 코드이고, Grafana + Prometheus 홈랩 모니터링에서 다뤘던 그 Prometheus가 내부적으로는 여기서 설명한 선행 0·후행 0·의미 있는 비트 블록 로직을 그대로 쓰고 있는 거예요. 결론부터 말하면 홈랩에서 Prometheus나 Netdata로 CPU 사용률, 온도, 네트워크 트래픽 같은 지표를 몇 달씩 쌓아도 디스크가 생각보다 덜 차는 이유 중 하나가 바로 이 XOR 압축이에요. 값이 완만하게 오르내리는 지표일수록 연속된 값의 XOR 결과가 0에 가까워지고, 그만큼 저장 공간도 적게 씁니다.
Gorilla와 Prometheus TSDB가 값을 압축하는 세부 자료구조까지 동일하지는 않지만, “인접한 실수값을 XOR해서 선행/후행 0 블록으로 가변 길이 인코딩한다”는 핵심 알고리즘은 그대로예요. 이 알고리즘이 왜 나왔고 Gorilla 전체 아키텍처에서 어떤 위치를 차지하는지는 같은 시리즈의 Gorilla 인메모리 TSDB 아키텍처 글에서, Prometheus와 Gorilla의 압축 결과를 직접 비교하는 내용은 Prometheus TSDB vs Gorilla 압축률 글에서 각각 이어서 다룰 예정이에요.
결론
Gorilla 논문의 XOR 압축은 복잡한 예측 모델 없이도 “인접한 값은 비슷하다”는 단순한 관찰 하나로 실수값을 64비트에서 평균 한 자릿수 비트대까지 줄여낸 사례예요. 선행 0과 후행 0을 세어 가변 길이로 인코딩하는 이 방식은 발표된 지 10년이 지난 지금도 Prometheus 같은 현역 오픈소스 TSDB의 핵심 압축 로직으로 그대로 살아있고, 결국 홈랩에서 지표를 오래 쌓아도 디스크 걱정을 덜어주는 실질적인 이유가 되고 있어요. 처음 질문으로 돌아가면, 연속된 값의 XOR이 대부분 0으로 채워진다는 사실 하나가 12배에 가까운 압축률의 진짜 원천이었던 셈이에요.
참고 자료
- Pelkonen, T. et al. “Gorilla: A Fast, Scalable, In-Memory Time Series Database.” Proceedings of the VLDB Endowment, Vol. 8, No. 12, 2015. 원문 PDF
- Prometheus TSDB
chunkenc/xor.go소스
자주 묻는 질문
Q1. Gorilla의 XOR 압축은 정확히 무엇을 압축하나요?
시계열 데이터 포인트의 실수(double precision) 값 부분만 압축해요. 같은 데이터 포인트의 타임스탬프는 델타의 델타(delta-of-delta) 방식이라는 별도 알고리즘으로 압축되며, 이 둘은 서로 독립적으로 인코딩돼요.
Q2. 왜 하필 XOR 연산을 쓰나요?
같은 시계열 안에서 연속된 값은 부호, 지수부, 가수부 앞자리가 거의 동일한 경우가 많아서예요. 두 값을 XOR하면 같은 비트는 전부 0으로 사라지고 실제로 달라진 부분만 1로 남기 때문에, 그 결과 대부분의 비트가 0으로 채워진 희소한(sparse) 값이 만들어져요.
Q3. Gorilla 논문이 실제로 보고한 압축률은 얼마인가요?
16바이트였던 데이터 포인트 하나(타임스탬프+값)를 평균 1.37바이트로 줄여 12배 압축을 달성했다고 논문 4장에서 밝히고 있어요. 이 수치는 타임스탬프 압축과 값 압축을 합친 전체 결과예요.
Q4. 값 압축만 따로 떼어놓고 보면 압축률이 얼마나 되나요?
논문 Figure 5에 따르면 실제 운영 데이터 160만 건을 샘플링했을 때 59.06%의 값이 단 1비트로, 28.30%는 평균 26.6비트로, 나머지 12.64%는 평균 39.6비트로 압축됐다고 보고하고 있어요.
Q5. 이 압축 알고리즘을 실제로 쓰는 오픈소스가 있나요?
네, Prometheus의 TSDB가 청크 인코딩에 Gorilla 논문의 XOR 압축을 그대로 채택해 `tsdb/chunkenc/xor.go`에 구현해뒀고, 델타의 델타 타임스탬프 압축과 함께 써서 논문과 동일한 평균 1.37바이트/샘플 수준의 압축률을 달성한다고 밝히고 있어요.
Q6. 압축 단위(블록 크기)를 늘리면 압축률이 계속 좋아지나요?
아니요. 논문 Figure 6에 따르면 압축 윈도우를 2시간 이상으로 늘려도 압축률 개선 폭이 거의 없어서, Gorilla는 2시간 단위 블록을 실질적인 최적점으로 채택했어요.
관련 글
