[Loki] memory.Bitmap 슬라이싱 지원: 비정렬 오프셋 처리

PR 링크: grafana/loki#20699 상태: Merged | 변경: +415 / -57

들어가며

비트맵은 대량의 boolean 값을 메모리 효율적으로 저장하는 자료구조입니다. Loki의 memory.Bitmap은 쿼리 엔진에서 필터 결과를 표현하는 데 사용됩니다. 이 PR은 비트맵의 서브셋을 새 할당 없이 참조할 수 있는 슬라이싱 기능을 추가합니다.

핵심 코드 분석

비트맵에 오프셋 필드 추가

type Bitmap struct {
    data []uint8
    len  int  // 비트 수 (오프셋 반영)
    off  int  // 첫 번째 워드 내 시작 오프셋
}

func (bmap *Bitmap) AppendUnsafe(value bool) {
    bitutil.SetBitTo(bmap.data, bmap.off+bmap.len, value)
    bmap.len++
}

Bytes()가 오프셋을 함께 반환

Before:

func (bmap *Bitmap) Bytes() []byte { return bmap.data }

After:

func (bmap *Bitmap) Bytes() ([]byte, int) {
    return bmap.data, bmap.off
}

모든 비트 연산 커널에 오프셋 반영

Before (logical_kernels.go):

bitutil.BitmapAnd(
    left.Bytes(), right.Bytes(),
    0, 0,   // offset 항상 0
    out.Bytes(),
    0,
    int64(left.Len()),
)

After:

leftBytes, leftOffset := left.Bytes()
rightBytes, rightOffset := right.Bytes()
outBytes, outOffset := out.Bytes()

bitutil.BitmapAnd(
    leftBytes, rightBytes,
    int64(leftOffset), int64(rightOffset),
    outBytes,
    int64(outOffset),
    int64(left.Len()),
)

Clone 시 정규화

// Clone은 새 할당자로 비트맵을 복사하며
// 비정렬 오프셋을 0으로 정규화합니다
clonedValidity := srcValidity.Clone(nil)
dstValidity, dstOffset := clonedValidity.Bytes()
if dstOffset != 0 {
    panic("cloned bitmap should be aligned")
}

왜 이게 좋은가

• 비트맵의 일부분을 새 할당 없이 참조할 수 있어 쿼리 엔진에서 필터 결과를 효율적으로 전달합니다
• 슬라이스의 capacity를 length로 잘라 슬라이스에 append하면 새 할당이 발생하게 하여 원본 데이터가 오염되는 버그를 방지합니다
• capacity를 초과하여 Grow할 때 자동으로 오프셋이 정규화되어 성능 저하를 누적시키지 않습니다
• Clone에 allocator를 지정할 수 있어 메모리 관리가 유연해졌습니다
• 벤치마크에서 비정렬 오프셋 처리 비용은 약 1%에 불과합니다

참고 자료

• Apache Arrow Bitmap 구현
• 비트 조작 기법