absl::PeriodicSampler — 적응형 샘플링·jitter 회피

#한 줄 요약

absl::profiling_internal::PeriodicSampler는 N번에 한 번 true를 반환하는 atomic 카운터 기반 sampler다. 단순 modulo 분기와 달리 geometric distribution으로 다음 sampling 시점을 결정해 phase-lock과 cache miss bias를 피한다. tcmalloc의 sampling, Abseil의 hashtable instrumentation, gRPC의 trace sampling 등이 모두 이 메커니즘이다.

#동기

샘플링이 필요한 상황은 흔하다.

• 모든 malloc을 추적하지 못한다(비용). N번에 한 번만 stack trace.
• 모든 RPC를 trace하지 못한다. 1% 정도만.
• 모든 hashtable insert에 instrumentation을 걸 수 없다.

가장 단순한 sampler는 counter + modulo다.

1
// 회피 — 단순하지만 문제 다수
2
std::atomic<uint64_t> counter{0};
3

4
bool Sample() {
5
  return (counter.fetch_add(1) % 1024) == 0;
6
}

문제 세 가지:

1. Bias: 호출 빈도가 주기와 공명하면 같은 곳만 sampled. 예를 들어 한 함수가 1024번에 한 번 hot path를 지나면 그 path만 항상 sample.
2. Cache contention: counter atomic이 모든 thread의 hot path에 있어 cache line ping-pong.
3. Rate 변경 비용: sample rate를 바꾸려면 modulo 분기를 다시 컴파일.

PeriodicSampler가 이 셋을 해결한다.

#API와 사용법

absl/profiling/internal/periodic_sampler.h에 정의.

1
#include "absl/profiling/internal/periodic_sampler.h"
2

3
class MallocSampler
4
    : public absl::profiling_internal::PeriodicSampler<MallocSampler, 1024> {
5
 public:
6
  static int64_t period() { return GetSampleRate(); }
7
};
8

9
ABSL_PER_THREAD_TLS_KEYWORD MallocSampler sampler_;
10

11
void* Malloc(size_t n) {
12
  if (sampler_.Sample()) {
13
    RecordStackTrace(n);
14
  }
15
  return RawMalloc(n);
16
}

PeriodicSampler는 CRTP. 템플릿 인자로 default period를 받고 *정적 멤버 period()*로 런타임 변경 가능한 rate를 정의한다.

각 thread의 sampler 인스턴스가 thread-local로 stride를 유지하므로 atomic contention이 사라진다.

#내부 구현

1
template <typename Tag, int64_t default_period>
2
class PeriodicSampler {
3
 public:
4
  bool Sample() noexcept {
5
    // 빠른 경로 — 99.9%
6
    if (ABSL_PREDICT_TRUE(--stride_ > 0)) {
7
      return false;
8
    }
9
    return SubtleConfirmSample();
10
  }
11

12
 private:
13
  bool SubtleConfirmSample() noexcept;
14
  void Init();
15

16
  int64_t stride_ = 0;   // thread-local
17
};
18

19
template <typename Tag, int64_t default_period>
20
bool PeriodicSampler<Tag, default_period>::SubtleConfirmSample() noexcept {
21
  int64_t current_period = Tag::period();
22
  if (current_period <= 0) {
23
    stride_ = INT64_MAX;
24
    return false;
25
  }
26
  stride_ = NextStride(current_period);
27
  return true;
28
}

핵심은 두 가지.

#1. fast path — 단순 decrement

호출 99% 이상이 --stride_ > 0 한 줄이다. branch predictor가 거의 항상 맞춘다. cache line은 thread-local이라 다른 thread와 공유 없음.

#2. NextStride — geometric distribution

1
int64_t NextStride(int64_t mean_period) {
2
  // exponential distribution sample
3
  // E[X] = mean_period
4
  double u = RandomDouble();          // (0, 1)
5
  return static_cast<int64_t>(-std::log(u) * mean_period) + 1;
6
}

다음 sampling까지의 간격을 지수 분포에서 뽑는다. 평균은 period지만 실제 간격은 임의. 호출 빈도와 공명하지 않는다 — Poisson process의 성질.

geometric/exponential distribution은 memoryless property를 가진다. “이미 1000회 호출했다”는 사실이 다음 sample까지 남은 횟수에 영향을 주지 않는다. 이게 bias-free의 통계적 보장.

#활용 사례

#tcmalloc — heap profiling

1
class HeapSampler : public PeriodicSampler<HeapSampler, ...> {
2
 public:
3
  static int64_t period() { return Static::sample_rate(); }
4
};
5

6
void* tc_malloc(size_t size) {
7
  void* p = inner_malloc(size);
8
  if (size > 0 && sampler_.Sample()) {
9
    profiling::RecordAlloc(p, size, CaptureStackTrace());
10
  }
11
  return p;
12
}

1 MB당 평균 1회 sample 같은 rate. heap profile은 대용량 alloc일수록 높은 확률로 sample되도록 size-weighted geometric을 사용한다.

#Swiss Table — load factor 통계

absl::flat_hash_map은 production에서 random subset의 instance만 통계 수집해 hash quality를 모니터링한다. PeriodicSampler로 1000 인스턴스당 1개를 추적.

#gRPC — trace sampling

grpc_core::Sampler는 같은 메커니즘으로 RPC 1%만 OpenTelemetry trace로 export.

#코드 리뷰 포인트

1. modulo 기반 sampler 발견 → 교체 후보

1
// 회피
2
if (counter.fetch_add(1) % rate == 0) Sample();
3

4
// Good
5
if (sampler_.Sample()) Sample();

counter 기반 sampler는 contention + bias 양쪽 문제가 있다.

2. CRTP Tag::period() 통한 동적 rate

1
class MySampler : public PeriodicSampler<MySampler, 1024> {
2
 public:
3
  static int64_t period() {
4
    return absl::GetFlag(FLAGS_my_sample_rate);   // 런타임 변경 가능
5
  }
6
};

flag 하나로 production에서 rate를 조정할 수 있다. 코드 재빌드 불필요.

3. thread-local 보장

1
// 회피 — atomic stride (contention)
2
class BadSampler { std::atomic<int64_t> stride_; };
3

4
// Good — thread-local (PeriodicSampler 기본)
5
ABSL_PER_THREAD_TLS_KEYWORD MySampler sampler_;

per-thread instance가 핵심. 잘못 shared singleton으로 만들면 의미가 사라진다.

4. 매우 낮은 rate에서 정확도

geometric distribution은 표본 수가 적으면 분산이 크다. 1만 호출에 1번 sample하면 실제 호출 수와 sample 수의 편차가 클 수 있다. 통계 분석 시 Horvitz-Thompson estimator나 weighted sample을 적용한다.

#std / Folly와의 비교

folly에는 folly::CoreCachedSharedPtr 등 sampling 도구가 있지만 geometric distribution + thread-local의 조합은 abseil이 가장 정제되어 있다.

#자주 보는 안티패턴

hot path에 RandomDouble() 직접 호출

1
// 회피 — 매 호출 RNG cost
2
if (RandomDouble() < 0.001) Sample();

RNG는 비용이 있다. PeriodicSampler는 RNG를 slow path에서만 호출하고 fast path는 단순 decrement.

stride 공유

1
// 회피 — global stride
2
static int64_t shared_stride;
3
if (--shared_stride <= 0) { ... }   // race condition

per-thread만이 답.

sample 안에서 sample

1
if (sampler_.Sample()) {
2
  HeavyOperation();   // 그 안에서 또 sampler 호출 → 통계 오염
3
}

sampler가 재진입되면 통계가 왜곡된다. sampling block 안에서는 sampler 호출 회피.

#정리

• PeriodicSampler는 thread-local + geometric distribution으로 bias-free.
• fast path는 단순 decrement, slow path만 RNG 호출.
• CRTP의 Tag::period()로 런타임 rate 변경.
• tcmalloc, Swiss Table, gRPC 등의 sampling 기반.
• modulo + atomic 기반 sampler를 발견하면 거의 항상 교체 가치.

#다음 편

Abseil Code Review 시리즈는 여기까지다. Folly 시리즈에서 대응 도구를 비교하거나 EMC++ 시리즈에서 함수 객체·자원 관리의 표준을 더 깊이 본다. Google C++ Style Guide (embedded/standards)에서 사내 코딩 규약과의 연결을 확인할 수 있다.

#관련 항목

• Part 16-02 — CRC32C
• Part 16-01 — Stacktrace / Symbolize
• Part 8-01 — BitGen — RNG 기반
• Part 6-01 — Mutex — 동시성 primitive
• Folly Part 9-03 — sampling — Meta 대응
• Tip of the Week #93: Using absl::Span