[Loki] Bitmap 디코더 최적화: 처리량 93.5% 개선

PR 링크: grafana/loki#20467 상태: Merged | 변경: +269 / -379

들어가며

Loki의 dataobj 모듈에서 페이지 리더는 값의 존재 여부(presence)를 비트맵으로 관리합니다. 기존 구현은 범용 []Value 슬라이스에 uint64 값으로 0/1을 저장했는데, 실제로 이 인코딩은 presence bitmap에만 사용되므로 boolean 전용으로 특수화할 수 있었습니다.

핵심 코드 분석

페이지 리더의 presence 버퍼를 Bitmap으로 교체

Before (page_reader.go):

type pageReader struct {
    presenceBuf []Value  // uint64 값 0 또는 1을 Value 래퍼로 저장
    // ...
}

// presence 값을 하나씩 순회하며 타입 체크
for _, p := range pr.presenceBuf[:count] {
    if p.Type() != datasetmd.PHYSICAL_TYPE_UINT64 {
        return n, fmt.Errorf("unexpected presence type: %s", p.Type())
    }
    if p.Uint64() == 1 {
        presentCount++
    }
}

After:

type pageReader struct {
    presenceBuf memory.Bitmap  // 비트 단위로 packed
    // ...
}

// 비트 단위로 직접 접근
for i := range count {
    if pr.presenceBuf.Get(i) {
        presentCount++
    }
}

디코더를 boolean 전용으로 특수화

Before:

type bitmapDecoder struct {
    r         streamio.Reader
    runValue  uint64
    setWidth  int    // 비트 너비 (범용)
    set       []byte // 가변 크기 set
}

After:

type bitmapDecoder struct {
    data     []byte  // 직접 바이트 슬라이스 참조
    off      int     // 바이트 오프셋
    runValue bool    // bool로 단순화
    set      byte   // 1바이트에 8개 값 (LSB-first)
}

왜 이게 좋은가

벤치마크 결과가 극적입니다:

시나리오	개선율
RLE, batch 256	-95.63% (265μs → 11.6μs)
RLE, batch 1024	-98.80% (244μs → 2.9μs)
RLE, batch 4096	-99.67% (249μs → 0.8μs)
Mixed, batch 256	-64.39%
Mixed, batch 4096	-65.48%
기하평균	-93.50%

• []Value 대신 memory.Bitmap을 사용하여 메모리 사용량이 8배 이상 줄어들었습니다 (값당 24+ bytes → 1 bit)
• streamio.Reader 인터페이스 대신 직접 바이트 슬라이스를 참조하여 함수 호출 오버헤드가 제거되었습니다
• boolean 전용이므로 비트 너비 계산, 타입 체크 등 범용 로직이 모두 제거되었습니다

참고 자료

• Bitmap 인코딩 최적화
• RLE (Run-Length Encoding)