본문으로 건너뛰기

[loki] Loki logline 인덱스에 OR-aware 힌트 needle 도입: 불리언 구조를 보존하는 쿼리 플래닝

PR 링크: grafana/loki#25425 상태: Merged | 변경: +804 / -485

들어가며

Grafana Loki의 logline 인덱스는 n-gram 기반 needle을 이용해 쿼리가 읽어야 할 청크 범위를 좁히는 힌트 시스템입니다. 그런데 기존 플래너는 사실상 AND 전용이었습니다. 다음과 같은 쿼리를 생각해 봅시다.

{app="api"} |= "timeout" or "deadline exceeded"
{app="api"} |~ "(GET|POST) /api/users"
{app="api"} | json | level="error" or level="fatal"

이런 쿼리에서 OR 구조를 표현할 수 없으면, 플래너는 OR 전체를 포기하거나(좁히기 실패) 잘못된 방식으로 일부 branch를 버려야 합니다. 후자는 false negative, 즉 실제로 매칭되는 로그를 놓치는 치명적 버그로 이어집니다.

이 PR(스택의 네 번째 PR)은 각 필터를 컴파일되지 않은 needle.Expr로 만들고, 이를 needle.And/Or로 조합한 뒤 마지막에 단 한 번 Compile(maxConjunctions)를 호출해 DNF(OR of ANDs) 형태의 needle.Conjunctions를 얻는 구조로 바꿉니다.

{app="api"} |= "seed text" |= "option_a" or "option_b"

max_conjunctions: 1 (default):
{SEED TEXT}

max_conjunctions: 4 (explicit opt-in):
{OPTION_A, SEED TEXT} OR {OPTION_B, SEED TEXT}

코드 분석

1. hintprovider 생성자: cap을 명시적 인자로

가장 눈에 띄는 기계적 변경은 NewLoglineHintProvider 시그니처입니다.

// Before
hintProvider, err := hintprovider.NewLoglineHintProvider(indexStore, cfg.NgramLength, 0, nil, logger, reg)

// After
hintProvider, err := hintprovider.NewLoglineHintProvider(indexStore, cfg.NgramLength, 0, 0, nil, logger, reg)

SupportedMetricQuery도 마찬가지로 cap 인자를 받습니다.

// Before
require.NotEmpty(t, hintprovider.SupportedMetricQuery(got.expr, 6))
// After
require.NotEmpty(t, hintprovider.SupportedMetricQuery(got.expr, 6, 0))

여기서 0은 "요청 cap이 없음"을 의미하며, querier는 이 경우 항상 1을 사용합니다. PR 설명에 따르면 별도의 hint-provider 기본값이나 공유 exported 상수를 두지 않았습니다. 기본값의 소유권을 frontend 한 곳에 두어 "로컬 설정이 큰 cap을 상속받는" 사고를 원천 차단한 설계입니다. 실제로 lookup 테스트가 "zero request cap이 더 큰 local planning cap을 상속하지 않는다"는 것을 검증합니다.

2. AGENTS.md: 불변식(invariant)으로 문서화된 의미론

이 PR의 핵심 의미론은 pkg/logline/hintprovider/AGENTS.md에 불변식으로 기록되어 있습니다. 가장 중요한 것은 새로 추가된 17번입니다.

17. **A leaf we cannot look up is TRUE, never dropped**
    - Under AND, dropping a filter and treating it as TRUE are the same thing.
      Under OR they are not: `|= "abcdef" or "ab"` must pass through, because
      lines with only `ab` are real results. A TRUE branch makes its whole OR
      TRUE.

이 한 문단이 OR-aware 플래닝의 정확성 핵심입니다. AND 세계에서는 "모르는 필터는 무시"가 안전했지만, OR 세계에서 "ab"(n-gram 길이보다 짧음)를 버리면 "abcdef"만 lookup하게 되어 ab만 포함한 로그를 놓칩니다. 그래서 lookup 불가능한 leaf는 TRUE로 승격되고, X OR TRUE = TRUE가 되어 해당 OR 전체가 제약 없음으로 처리됩니다. TRUE leaf 목록도 명시됩니다: ip(), negative filter, pattern filter, 짧은 literal, "", non-verbatim post-parser 값, =/=~ 이외 matcher, 예약 __* 라벨, 숫자/duration/bytes 필터, required literal이 없는 regex.

빈 문자열에 대한 처리도 흥미롭습니다.

    - An or chain with a `""` branch anywhere is skipped. Loki runs it
      differently depending on where `""` sits (`|= "" or "" or "a"` keeps
      every line, `|= "a" or "" or ""` does not), so we plan nothing for it

LogQL 자체의 의미가 위치 의존적으로 일관되지 않으니, 플래너는 추측하지 않고 해당 체인을 계획에서 제외합니다. 보수적이지만 올바른 선택입니다.

3. Line filter: LogQL AST 구조 그대로 미러링

   - `collectLineFilters` returns whole stages, with their `Left` and `Or`
     chains, so `lineFilterStage` can mirror `LineFilterExpr.Filter`: the
     `Left` chain is ANDed, and a node with an `Or` chain is an OR of its
     branches. Branches of a chain all take the operator of the first one.

플래너가 실제 실행 경로(LineFilterExpr.Filter)와 같은 구조로 needle 식을 만들기 때문에, "인덱스가 생각하는 의미"와 "엔진이 실행하는 의미"가 어긋날 여지가 줄어듭니다.

4. Regex: cap과 무관한 regexliteral.Needles

// Before
13. **A regex contributes only the literals every match contains**
    - ... go through `regexliteral.Literals`, never a local AST walk.

// After
13. **A regex contributes the needles every match satisfies**
    - ... `regexliteral.Needles(pattern)`, never a local AST walk. Regex extraction
      uses fixed internal enumeration limits, not the query's DNF cap.

이전에는 regex가 "모든 매치가 포함하는 literal 집합(AND)"만 기여했습니다. 이제 (GET|POST) /api/users 같은 alternation도 needle 식으로 표현됩니다. 열거 한계는 내부 고정값을 쓰고 쿼리의 cap과 분리되어 있어, regex 추출 결과가 설정에 따라 흔들리지 않습니다.

짧은 literal의 처리도 바뀌었습니다.

// Before
    - Its literals are unfiltered. `SupportedQuery` drops those shorter than
      `ngramLength`, and a regex with none left contributes nothing.
// After
    - ... A literal shorter than
      `ngramLength` becomes TRUE, so a set left empty makes the regex TRUE.

"drop"에서 "TRUE"로 — 불변식 17과 동일한 원칙의 적용입니다.

5. Post-parser 값: fragment는 원래 OR branch 안에서 AND

JSON/logfmt 디코딩은 \/를 /로, 잘못된 UTF-8을 공백으로 바꾸므로 값을 /와 공백에서 분할합니다. 이때 MapAll이 fragment들을 원래 OR branch 안에서 AND로 유지합니다.

alphaone/betaone OR alphatwo/betatwo
    → {ALPHAONE, BETAONE} OR {ALPHATWO, BETATWO}

fragment를 평탄화해 {ALPHAONE, BETAONE, ALPHATWO, BETATWO}로 섞으면 상관관계가 깨집니다. 매핑을 collapse 이전에 수행하는 것이 포인트입니다.

6. maxConjunctions와 컴파일 한 번

18. **`maxConjunctions` bounds the needle sets**
    - `SupportedQuery` builds a factored `needle.Expr` with uncapped `And` and
      `Or`, maps literals before collapse, and calls `Compile(maxConjunctions)`
      once on the complete requirement. ... Over the limit an operand or union
      collapses to its implied existing literals.

DNF 변환은 OR 절의 곱(product)이 지수적으로 커질 수 있습니다. 중간 단계마다 cap을 적용하면 정보가 일찍 손실되므로, factored 형태로 끝까지 구성한 뒤 한 번만 컴파일하고, 한계를 넘으면 "모든 branch가 공통으로 함의하는 literal"로 collapse합니다. 예시의 cap=1에서 {SEED TEXT}만 남는 이유가 이것입니다.

결과 타입 needle.Conjunctions는 String()을 가진 named [][]string이며, 빈 외부 slice는 unconstrained를 의미하고 len으로 검사합니다. accessor 복사 없이 slice를 그대로 쓰는 대신 "goroutine 간 공유 slice를 mutate하지 말 것"을 불변식 16에 명시했습니다.

리뷰에서 나온 논의

  • hundredwatt: logqltest 스택이 cap=1로 돌고 있으니 >1 값으로 조정해야 한다는 지적. 기본값이 1이라 OR 경로가 통합 테스트에서 사실상 커버되지 않는 맹점을 짚은 유의미한 피드백입니다.
  • hundredwatt: (?i) 하에서 ſ(U+017F)·Kelvin sign(U+212A) 등 일부 non-ASCII 룬이 ASCII 문자와 매칭되지만 인덱스는 non-ASCII 바이트를 separator로 취급하므로, databaſe timeout 같은 줄을 놓칠 수 있다는 기존(#24800) 허용 갭이 남아 있음을 명시했고, 개발 중인 v5에서 해결 예정이라고 답했습니다. strings.ToUpper 대신 upperASCII를 쓰는 규칙도 같은 맥락입니다.

왜 이게 좋은가

  1. 정확성 우선의 확장: OR 지원을 추가하면서도 "모르는 것은 TRUE" 원칙으로 false negative를 구조적으로 막았습니다.
  2. 안전한 롤아웃: 기본 cap=1로 기존 동작 유지, 구 querier는 새 필드를 무시하고 구 frontend는 0을 보내 새 querier가 1로 처리합니다. 혼합 배포에서도 의미가 바뀌지 않습니다.
  3. 지연 컴파일: uncapped 식을 끝까지 만든 뒤 한 번만 bound/prune하므로 조기 정보 손실이 없습니다. 성능 비교(소규모 workload 회귀 포함)는 #25414에 기록되어 있다고 합니다.

일반적 교훈: AND 전용 시스템에 OR를 도입할 때 "필터를 버린다"와 "TRUE로 둔다"는 더 이상 같은 연산이 아닙니다. 불리언 대수의 항등원/흡수원을 명시적으로 모델링하고, 실행 엔진의 AST 구조를 그대로 미러링하며, 비용 제한은 마지막에 한 번 거는 것 — 이것이 인덱스 기반 쿼리 플래닝을 안전하게 확장하는 방법입니다.

참고 자료

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.

댓글

관련 포스트

PR Analysis 의 다른글