PromQL 엔진 내부 구조: 파서부터 실행 엔진까지

PromQL 문자열
    |
    v
+----------+
| Lexer    |  (토큰화)
+----------+
    |
    v
+----------+
| Parser   |  (구문 분석)
+----------+
    |
    v
+----------+
| AST      |  (추상 구문 트리)
+----------+
    |
    v
+----------+
| Analyzer |  (최적화/검증)
+----------+
    |
    v
+----------+
| Engine   |  (평가/실행)
+----------+
    |
    v
결과 (Matrix/Vector/Scalar)

입력: rate(http_requests_total[5m]) > 10

토큰 스트림:
  IDENTIFIER("rate")
  LEFT_PAREN
  IDENTIFIER("http_requests_total")
  LEFT_BRACKET
  DURATION("5m")
  RIGHT_BRACKET
  RIGHT_PAREN
  GTR
  NUMBER(10)

리터럴:
  NUMBER      - 정수/부동소수점 (예: 42, 3.14)
  STRING      - 문자열 리터럴 (예: "hello")
  DURATION    - 시간 범위 (예: 5m, 1h, 30s)

식별자:
  IDENTIFIER  - 메트릭 이름, 레이블 이름
  METRIC_IDENTIFIER - 메트릭 식별자

연산자:
  ADD, SUB, MUL, DIV, MOD, POW
  EQL, NEQ, LSS, GTR, LTE, GTE
  AND, OR, UNLESS

키워드:
  BY, WITHOUT, ON, IGNORING
  GROUP_LEFT, GROUP_RIGHT
  OFFSET, BOOL
  SUM, AVG, MIN, MAX, COUNT, ...

파서 동작 흐름:
1. 토큰 스트림에서 다음 토큰 읽기
2. prefix 파싱 함수 호출 (리터럴, 단항 연산, 괄호 등)
3. 현재 우선순위보다 높은 infix 연산자가 있으면 infix 파싱
4. AST 노드 반환

우선순위 (낮은 것부터):
1. OR
2. AND, UNLESS
3. ==, !=, <, >, <=, >= (비교)
4. +, - (가감)
5. *, /, % (곱나눗셈)
6. ^ (거듭제곱, 우측 결합)
7. 단항 +, -

메트릭이름 뒤에 중괄호가 오면 레이블 매칭 파싱
예: http_requests_total 뒤에 중괄호가 있으면 레이블 셀렉터 파싱

레이블 매칭 연산자: =, !=, =~, !~

IDENTIFIER + LEFT_PAREN -> 함수 호출
등록된 함수 목록에서 이름 확인
인수 개수와 타입 검증

벡터 셀렉터 + LEFT_BRACKET + DURATION + RIGHT_BRACKET
예: http_requests_total[5m]

Expr (표현식 인터페이스)
  |
  +-- NumberLiteral        (숫자 리터럴)
  +-- StringLiteral        (문자열 리터럴)
  +-- VectorSelector       (즉시 벡터 셀렉터)
  +-- MatrixSelector       (범위 벡터 셀렉터)
  +-- AggregateExpr        (집계 표현식)
  +-- BinaryExpr           (이항 연산 표현식)
  +-- UnaryExpr            (단항 연산 표현식)
  +-- Call                 (함수 호출)
  +-- ParenExpr            (괄호 표현식)
  +-- SubqueryExpr         (서브쿼리 표현식)
  +-- StepInvariantExpr    (step 불변 표현식)

AggregateExpr (sum, by=[job])
  |
  +-- Call (rate)
        |
        +-- MatrixSelector
              |
              +-- VectorSelector (http_requests_total)
              +-- Range: 5m

VectorSelector:
  Name: "http_requests_total"
  LabelMatchers:
    - __name__ = "http_requests_total"
    - job = "prometheus"       (사용자 지정)
    - instance =~ ".*:9090"    (정규식 매칭)
  Offset: 0s                   (offset 수정자)
  Timestamp: nil               (@ 수정자)
  OriginalOffset: 0s
  StartOrEnd: 0                (start() 또는 end())

Engine:
  +-- queryable      (TSDB 스토리지 인터페이스)
  +-- maxSamples     (최대 샘플 수 제한)
  +-- timeout        (쿼리 타임아웃)
  +-- activeQueries  (활성 쿼리 카운터)
  +-- maxConcurrency (최대 동시 쿼리 수)

요청: GET /api/v1/query?query=up&time=1609459200

처리:
1. AST 생성
2. time=1609459200에서 한 번 평가
3. 결과: Vector (각 시계열에 대한 단일 값)

요청: GET /api/v1/query_range?query=up&start=1609455600&end=1609459200&step=60

처리:
1. AST 생성
2. start부터 end까지 step(60초) 간격으로 반복 평가
3. 각 step에서 instant query처럼 평가
4. 결과: Matrix (각 시계열에 대한 시간별 값 배열)

query: rate(http_requests_total[5m])
start: T0, end: T0+300s, step: 60s

Step 평가:
  T0:      rate(samples from T0-5m to T0)
  T0+60:   rate(samples from T0+60-5m to T0+60)
  T0+120:  rate(samples from T0+120-5m to T0+120)
  T0+180:  rate(samples from T0+180-5m to T0+180)
  T0+240:  rate(samples from T0+240-5m to T0+240)
  T0+300:  rate(samples from T0+300-5m to T0+300)

평가 시점: T
lookback delta: 5m

샘플 검색 범위: (T - 5m, T]

동작:
1. T 이전 5분 이내의 가장 최근 샘플을 찾음
2. 해당 샘플이 stale marker가 아니면 결과에 포함
3. 5분 이내에 샘플이 없으면 해당 시계열 제외

중요: 정확히 T 시점의 샘플이 없어도 됨
      lookback delta 내의 가장 최근 샘플 사용

함수 등록 정보:
  Name:       "rate"
  ArgTypes:   [ValueTypeMatrix]     (인수 타입)
  ReturnType: ValueTypeVector       (반환 타입)
  Call:       funcRate              (실제 구현 함수)
  Variadic:   0                     (가변 인수 수)

rate(counter[5m]) 평가:

1. 5분 범위의 샘플 추출: [s1, s2, s3, ..., sN]
2. Counter 리셋 감지 및 보정:
   - 값이 감소하면 이전 값을 누적에 더함
3. 보정된 총 증가량 계산:
   resultValue = (last - first) + counterCorrection
4. 외삽(extrapolation):
   - 범위 시작/끝을 넘어서는 시간 비율 계산
   - durationToStart = first.time - rangeStart
   - durationToEnd = rangeEnd - last.time
   - 외삽 비율 적용
5. 초당 증가율:
   result = extrapolatedIncrease / rangeDurationSeconds

histogram_quantile(phi, buckets) 평가:

1. le 레이블로 버킷 정렬
2. 각 버킷의 누적 카운트 수집
3. phi(예: 0.95) * total_count = target_count 계산
4. target_count를 포함하는 버킷 찾기
5. 해당 버킷 경계 사이에서 선형 보간:
   bucketStart + (bucketEnd - bucketStart) *
   (target - countBelow) / (countInBucket)

주의사항:
- le="+Inf" 버킷은 반드시 있어야 함
- 버킷이 비어있으면 NaN 반환
- 버킷 경계가 실제 분포와 맞지 않으면 부정확

sum by (job) (metric) 평가:

1. metric의 모든 시계열 수집
2. job 레이블 값별로 그룹핑
3. 각 그룹 내에서 값 합산
4. 결과 시계열: job 레이블만 유지

내부 구현:
- 해시맵으로 그룹 관리
- 레이블 셋의 해시를 키로 사용
- 충돌 시 정확한 레이블 비교

metric_a + metric_b

매칭 알고리즘:
1. 양쪽 벡터의 시계열을 레이블 셋으로 인덱싱
2. 매칭 레이블 셋이 동일한 쌍을 찾음
3. 연산 수행 (여기서는 값 더하기)
4. 결과 시계열에 왼쪽 레이블 셋 사용

성능:
- 해시 조인 방식으로 O(n+m) 시간 복잡도
- 작은 쪽을 해시 테이블로 구성

metric_a * on(job) group_left metric_b

처리:
1. on(job)으로 매칭 키 결정
2. metric_b(one 쪽)를 job별 해시맵에 인덱싱
3. metric_a(many 쪽)의 각 시계열에 대해:
   a. job 레이블로 metric_b에서 매칭 항목 검색
   b. 연산 수행
   c. metric_a의 모든 레이블 유지 (group_left)

max_over_time(rate(http_requests_total[5m])[30m:1m])

평가 과정:
1. 외부 함수(max_over_time)가 range vector 필요
2. 서브쿼리 부분: rate(http_requests_total[5m])[30m:1m]
3. 내부 평가:
   - 현재 시점(T)에서 30분 전부터 T까지
   - 1분 간격으로 rate(http_requests_total[5m]) 평가
   - 30개의 instant vector 결과 생성
4. 이를 range vector로 변환
5. max_over_time이 각 시계열의 최대값 계산

서브쿼리 평가의 핵심 최적화:
1. 내부 쿼리의 range vector를 재사용 (동일 시계열)
2. step alignment: 서브쿼리의 step을 외부 step에 정렬
3. resolution이 지정되지 않으면 global evaluation_interval 사용

--query.max-samples (기본 50,000,000)

카운팅 방식:
- 각 step에서 로드/생성된 샘플 수 누적
- range vector의 경우 범위 내 모든 샘플 카운트
- 제한 초과 시 쿼리 즉시 중단

--query.max-concurrency (기본 20)

구현:
- semaphore(세마포어)로 동시 쿼리 수 제한
- 새 쿼리가 세마포어 획득 대기
- 타임아웃 내 획득 실패 시 에러 반환

포인트 풀 동작:
1. 쿼리 시작 시 포인트 슬라이스 풀에서 할당
2. step 평가 간 재사용
3. 쿼리 완료 시 풀에 반환
4. sync.Pool을 사용하여 GC 부담 감소

Native Histogram은 기존 float 샘플과 다른 처리 경로:
1. 히스토그램 스키마(resolution) 정렬
2. 버킷 단위 병합
3. 집계 시 스키마 변환 필요 시 자동 수행

sum(native_histogram_metric) 평가:
1. 각 시계열의 히스토그램 수집
2. 스키마가 다르면 더 낮은 해상도로 통일
3. 버킷별 카운트 합산
4. sum, count 합산

Native Histogram에서의 quantile 계산:
1. 지수 버킷 경계 자동 결정
2. 기존보다 정확한 보간 가능
3. le 레이블 불필요 (내부 구조에서 직접 계산)

여러 블록에 걸쳐 동일 시계열이 존재할 때:
1. 각 블록에서 시계열 집합 검색
2. 병합 정렬(merge sort)으로 통합
3. 청크 레벨에서 시간 범위로 필터링
4. 중복 제거

step에 관계없이 동일한 결과를 반환하는 표현식 감지:
- 숫자 리터럴
- offset이 없는 스칼라 함수
- 특정 집계 결과

감지된 경우:
- 한 번만 평가하고 모든 step에 결과 복사
- 불필요한 반복 평가 제거

최적화 패스:
1. 상수 접기(constant folding): 2 + 3 -> 5
2. 레이블 매칭 최적화: 인덱스 힌트 생성
3. 불필요한 레이블 연산 제거
4. 비어있는 결과 조기 반환

1. "query processing would load too many samples"
   - max-samples 제한 초과
   - 해결: 쿼리 범위 축소 또는 제한 증가

2. "query timed out in expression evaluation"
   - query.timeout 초과
   - 해결: 쿼리 최적화 또는 타임아웃 증가

3. "found duplicate series for the match group"
   - 벡터 매칭에서 다대일 관계인데 group_left/right 미지정
   - 해결: group_left 또는 group_right 추가

4. "many-to-many matching not allowed"
   - 양쪽 모두 다수인 매칭은 지원되지 않음
   - 해결: 집계를 통해 한쪽을 일(one)로 축소

1. 조인 기능 제한: SQL 스타일 조인 불가
2. 문자열 연산 제한: 문자열 비교/조작 불가
3. 정렬 보장 없음: 결과의 시계열 순서가 비결정적
4. 서브쿼리 중첩 제한: 과도한 중첩은 메모리 폭발 위험