[Grafana Loki] 루프 언롤링된 Uvarint 디코더로 delta 인코딩 최적화

PR 링크: grafana/loki#20824 상태: Merged | 변경: +15 / -4

들어가며

Grafana Loki의 데이터 오브젝트 시스템에서 binary.Varint가 특정 시점에 전체 CPU의 3.5%를 차지하는 것이 관찰되었습니다. Go 표준 라이브러리의 Varint 구현은 범용적이지만 루프 기반이라 분기 예측 실패와 루프 오버헤드가 있습니다. 이 PR은 루프를 언롤링한 dennwc/varint 패키지를 도입하여 delta 디코딩 성능을 최대 51% 개선합니다.

핵심 코드 분석

Before: 표준 라이브러리 Varint

import "encoding/binary"

// value.go
val, n := binary.Varint(data[n:])

// value_encoding_delta.go
delta, n := binary.Varint(buf[off:])

Go의 binary.Uvarint는 바이트 단위 루프로 구현되어 있습니다:

// 표준 라이브러리 구현 (간략화)
func Uvarint(buf []byte) (uint64, int) {
    var x uint64
    var s uint
    for i, b := range buf {
        if b < 0x80 {
            return x | uint64(b)<<s, i + 1
        }
        x |= uint64(b&0x7f) << s
        s += 7
    }
    return 0, 0
}

After: 루프 언롤링된 Uvarint

import dennwc "github.com/dennwc/varint"

// 커스텀 varint 함수 — dennwc/varint는 unsigned만 제공
func varint(buf []byte) (int64, int) {
    ux, n := dennwc.Uvarint(buf)  // 루프 언롤링된 빠른 구현
    x := int64(ux >> 1)
    if ux&1 != 0 {
        x = ^x
    }
    return x, n
}

dennwc/varint의 Uvarint는 루프를 펼쳐서 각 바이트에 대한 조건 분기를 제거합니다. 이를 기반으로 signed varint(varint)를 ZigZag 디코딩으로 구현합니다.

Delta 디코딩에서의 적용

// value_encoding_delta.go
for i := range count {
    delta, n := varint(buf[off:])  // 표준 라이브러리 → dennwc 교체
    // ...
}

delta 인코딩에서는 모든 값이 이전 값과의 차이로 저장되므로, 각 값을 읽을 때마다 varint 디코딩이 호출됩니다. 배치 크기가 클수록 호출 횟수가 많아지므로 단위 호출 비용 절감의 효과가 누적됩니다.

벤치마크 결과

                                                     │   before    │      after       │
_deltaDecoder_Decode/sequential/batchSize=256         148.9µ ± 1%   137.8µ ± 0%   -7.43%
_deltaDecoder_Decode/sequential/batchSize=1024        138.1µ ± 1%   126.4µ ± 1%   -8.42%
_deltaDecoder_Decode/sequential/batchSize=4096        135.0µ ± 1%   123.6µ ± 0%   -8.47%
_deltaDecoder_Decode/largest_delta/batchSize=256      508.2µ ± 0%   252.9µ ± 0%  -50.23%
_deltaDecoder_Decode/largest_delta/batchSize=1024     494.0µ ± 1%   242.0µ ± 0%  -51.02%
_deltaDecoder_Decode/largest_delta/batchSize=4096     489.3µ ± 0%   239.4µ ± 1%  -51.07%

• 순차적 데이터: 약 78% 개선 (delta 값이 작아 12바이트로 인코딩)
• 최대 delta 데이터: 약 50% 개선 (delta 값이 커 10바이트까지 사용, 루프 언롤링 효과 극대화)

왜 이게 좋은가

1. 루프 언롤링의 원리

Varint는 최대 10바이트(uint64의 경우)까지 사용합니다. 루프 버전은 매 바이트마다 "계속 읽을지" 분기합니다. 언롤링 버전은 10개의 바이트 처리를 조건부 코드로 펼쳐, CPU의 분기 예측 실패를 줄이고 명령어 파이프라인을 더 효율적으로 활용합니다.

2. Loki의 데이터 모델에 최적

Loki는 로그 타임스탬프를 delta 인코딩으로 저장합니다. 타임스탬프의 delta는 보통 일정하지만, 로그 유실이나 버스트 시 큰 delta가 발생합니다. 이런 "largest delta" 시나리오에서 51% 개선은 실제 운영 환경에서 의미 있는 차이입니다.

3. 최소한의 코드 변경

외부 패키지 의존성 하나를 추가하고, signed varint 래퍼 함수 하나를 작성한 것이 전부입니다. 15줄의 변경으로 핫 패스의 3.5% CPU 사용을 절감했습니다.

참고 자료

• Optimizing Varint Decoding — DoltHub Blog — Varint 루프 언롤링의 상세 분석
• dennwc/varint GitHub — 루프 언롤링된 Go Varint 구현
• Protocol Buffers Encoding — Varint 인코딩 명세