분산추적의 샘플링에 대해서 알아보자

APM에서는 어플리케이션의 모든 요청을 다 추적하고 분석하지 않습니다.

추적 데이터는 실제 어플리케이션의 비즈니스 트래픽을 쉽게 초과할 수 있으며, 이는 서비스에 영향을 주게됩니다.

 

요청을 100% 샘플링한다면 대퍼 추적기는 검색 작업에 대해 1.5%의 처리량과 16%의 시간지연 오버헤드가 발생한다고 합니다.

그렇기에 추적 시스템들은 추적의 특정 부분만을 캡쳐하기위해 샘플링을 사용합니다.

만약 추적의 0.01%만 캠쳐하도록 샘플링하면 처리량 오버헤드는 0.06%, 응답시간은 0.20% 감소한다고 합니다.

 

따라서 적절한 양의 요청들을 샘플링하는건 분산추적 어플리케이션에서 매우 중요한 요소입니다.

헤드 기반(head-based) 샘플링

upfront sampling이라고도 하며, 들어오는 각각 추적들에 대해서 매번 샘플링 여부를 결정합니다.

일반적으로 추적은 인프라스트럭쳐, 웹서버를 지나 어플리케이션에 들어온 순간부터 시작됩니다.

헤드 기반 샘플링은 추적 시스템이 특정 추적(Trace)의 모든 스팬을 캡쳐하거나 또는 아무것도 캡쳐하지 않기에 추적(Trace)에 대해 일관적이라는 특징이 있습니다.

 

추적이 어플리케이션에 진입하면 해당 추적이 샘플링 되어야 좋을지, 되지 않아야 좋을지 판단해야하는데,

해당 추적에 대한 정보가 거의 없기에 판단이 어렵습니다.

그렇지만 헤드기반 샘플링은 아직까지도 많은 추적 시스템에서 사용하는 방식입니다.

 

헤드 기반의 반대로는 테일 기반 샘플링이 있습니다.

확률적 샘플링

확률적 샘플링 결정은 특정 확률값을 갖는 랜덤 기반으로 이뤄집니다.

이 샘플링 방식은 헤드 기반 샘플링을 이용한 추적 시스템에서 가장 많이 사용되는 샘플링 방식입니다.

스프링 클라우드 슬루스(Spring Cloud Sleuth)도 확률적 샘플러를 활용합니다.

 

예거(jaegor)는 요청 1000개당 1번의 추적이 만들어지도록 기본 샘플링 확률이 0.001로 설정되어 있습니다.

일정 시간동안 특정 서비스 엔드포인트 X에 대해 100개의 추적을 수집했다고 가정하고,

샘플링 확률 p를 알면, 이 시간 동안 엔드포인트 X에 대한 총 호출 수를 100/p로 확률적 샘플리의 샘플링 데이터 양을 추정 할 수 있습니다.

속도 제한 샘플링

샘플링 방법 중 하나로 속도 제한기(rate limiter)를 사용하는 방법도 있습니다.

보통 레저부아 샘플링 알고리즘을 사용합니다.

속도 제한기(rate limiter)는 초당 10개의 추적 또는 1분당 하나의 추적 등 지정된 시간 간격마다 고정된 수의 추적만 샘플링합니다.

속도 제한 샘플링은 불규칙한 트래픽 패턴을 보이는 MSA에 유용합니다.

 

레저부아 샘플링에 대해서는 다른 포스팅에서 다루었으니 혹시,, 궁금하신분은 아래 글에서 확인할 수 있습니다.

https://jaykos96.tistory.com/104

실시간 대용량 데이터에서 사용되는 알고리즘(Reservoir Sampling, HLL, CMS,Bloom Filter)들에 대해 알아보

처리량 보장 확률적 샘플링

처리량 보장 샘플러(guraranteed-throughput sampler)를 사용해 특정 상황에 트래픽이 급증하는 서비스가 있는 서비스에 적절한 샘플링 방식입니다.

확률적 샘플러와 속도 제한기(rate limiter)를 결합한 것입니다.

기본적으로는 확률적샘플링을 사용합니다, 하지만 서비스가 off-peak 기간이라면 요청이 추적되지 않을 수 있는데,

이를 방지하기 위해 지정된 시간 간격 이후에는  속도 제한기(rate limiter)를 사용해 요청이 하나도 샘플링되지 않는 상황을 방지합니다.

 

사실 현재 이 방식은 현재 거의 사용되지 않으나, 이 샘플링을 토대로 적응형 샘플링이 만들어졌습니다.

적응형 샘플링

서비스의 API들이 받는 트레픽은 다양합니다.

자주 사용하는 API는 트레픽이 많을 것이고, 어떤 API는 요청이 적을 것 입니다.

 

그렇기에 각 상황에 맞게 적응하는 샘플링 방식이 필요합니다.

적응형 샘플링은 기본적으로 수집한 처리량이 목표량을 넘어서면 샘플링 확률을 낮추는 방식입니다.

샘플링 확률은 동적으로 변경되며 각 서버에서 환경설정 파라미터를 읽어서 적용합니다.

 

적응형 샘플링은 각 서비스의 트래픽에 따라 자동으로 샘플링 비율을 조절하여,

아래 목표들을 안정적으로 달성하고자 합니다.

서비스의 특징에 따라 추구하는 목표의 우선순위가 다를 수 있습니다.

1. TPS ((Traces per Second))

• 서비스 인스턴스당 평균 초당 몇 개의 트레이스를 수집할지 목표를 설정합니다.

2. SPS ((Spans per Second))

• 스팬 수의 양을 고려하여 목표를 설정합니다.

3. BPS ((Bytes per Second))

• 스팬 크기를 고려하여 목표를 설정합니다.

적응형 샘플링 이론

예거(jaegor)의 샘플링을 가지고 샘플링에 대해 알아보겠습니다.

예거의 샘플링은 고전적인 PID ((proportional-integral-derivative)) 제어기와 유사합니다.

아키텍쳐적인 개념만 어느정도의 비슷하다고 생각하면 될 것 같습니다.

출처 : https://yunslog.tistory.com/78

PID는 현재 output y((t))) , 프로세스 값을 관찰하고, output은 Process 처리되기 전에 보정신호 u((t)) 로 인해 변경됩니다.

최초 입력인 원하는 프로세스 값과 output 사이의 오차(Error)를 최소화하기 위해 PID는 비례식(P), 적분 항(I), 미분 항(D)로 구성된 제어기의 가중치의 합계로 보정신호 u((t))가 계산됩니다.

 

이런 PID의 개념을 샘플링에 적용해 보면

• y((t))는 실측값, 특정 시간 동안 모든 인스턴스를 대상으로 특정 서비스에 대해 샘플링된 추적의 수, 최종 Output TPS입니다.
• r((t))는 허용추적률, 어플리케이션에서 오버헤드 수준과 추적 백엔드의 용량을 고려해 허용 가능하다고 생각하는 TPS, 원하는 Input TPS입니다.
• u((t))는 알고리즘으로 계산하는 샘플링 확률입니다.
• 오류는 e((t)) = r((t))-y((t)), 목표값 - 현재값으로 계산합니다.

예거(Jaeger)의 적응형 샘플링

카운터(Counter)는 수집기가 수집한 모든 루트 스팬을 받아서 루트 스팬의 카운트 수를 집계합니다.

일정 시간 동안 카운트 수를 수집하고, 이후 데이터베이스의 Counts 테이블에 저장합니다.

즉 샘플링 여부와 상관없이 전체 요청수를 저장하는 위한 테이블입니다.

 

m분 동안 수집한 Counts 테이블 데이터들을 사용해 각 엔드포인트에 대한 y((t)), TPS를 계산합니다.

m은 loopback period 인데 보통 10분으로 설정합니다.

m, loopback period 값을 사용하는 이유는, 순간적인 트레픽의 증가와 같은 상황을 평균화해서 이후 적용될 샘플링 확률이 부드럽게 조정되도록 할 수 있기 때문입니다.

 

y((t))를 이후 Input TPS와 비교하여 개별 서비스나 엔드포인트에 대한 보정 신호((샘플링 확률)) u((t)) 계산 후 Targets 테이블에 저장합니다.

 

이후 제어기(Controller)는 Targets 테이블에서 계산된 샘플링확률을 읽어 메모리에 캐시한 다음 각 추적기로 전송합니다.

추적기는 주기적으로 수집기를 폴링하여 샘플링 전략을 가져옵니다.

예거(Jaeger)의 리더 선출

샘플링 확률을 계산하는 리더 노드는 하나여야합니다.

리더 선출을 위해 리더 임대(leader lease) 정책을 사용하는데,

각 수집기에서 일정주기로 카산드라(Cassandra)의 compare-and-set 연산으로 리더 임대(leader lease) 튜플 ((N,T)) 을 저장합니다.

여기서 N은 경쟁자의 이름 또는 ID이고 T는 임대 만료 시간입니다.

 

수집기는 리더 임대 튜플을 사용해 통해 T시간 까지 자신((N))이 리더를 하겠다는 의도를 전달합니다.

만약 튜플을 전달했을 때 그 기간에 리더가 없으면 튜플을 보낸 노드가 리더가 됩니다.

 

리더 임대 방식은 완전한 리더 선출 알고리즘((Paxos, Raft 등))에 비해서는 불완전합니다.
네트워크 지연이나 타이밍 이슈로 인해 잠시 동안 두 수집기가 동시에 리더가 될수도 있습니다.

그러나 적응형 샘플링의 목적은 트래픽 기반의 확률 조정이며, 수 초 단위의 오차는 큰 문제가 되지 않는다고 판단하기에, 현실적인 해결책입니다.

샘플링 확률 u((t)) 계산법

계산기(Calculator)가 m, loopback period 기간에 대한 누적 카운트 수를 읽었을 때

y((t))의 현재 값을 얻기 위해 이들을 모두 합하고 (m)으로 나눕니다.

u((t))의 예상값은 아래와 같이 계산합니다.

 

\[
u'(t) = u(t - 1) \times q,\quad q = \frac{r(t)}{y(t)}
\]

 

u'((t))은 새로 계산된 식, q는 보정계수, u((t-1)) 이전에 가지고 있던 보정값

(t)는loopback period의 시간 인덱스입니다.

 

\[
q = \frac{r(t)}{y(t)} = \frac{10}{20} = \frac{1}{2}
\Rightarrow
u'(t) = u(t-1) \times q = \frac{u(t-1)}{2}
\]

 

위와 같은 수식은 r((t))=10TPS이고 현재 속도는 y((t))=20TPS라고 가정합니다.

이러한 상황에서는 보정계수 q는 1/2가 되고,

이는 현재 서비스에서 사용중인 샘플링 확률이 너무 높아서 절반으로 줄인다는 의미입니다.

 

위와 같은 상황이 된다면 과다한 샘플링을 하고 있다고 판단한 것이고, 추적 벡엔드에 과부하가 걸렸던 상황이기에 가능한 한 빠르게 적용하며 어플리케이션의 특이사항 없이 적용됩니다.

 

\[
q = \frac{r(t)}{y(t)} = \frac{20}{10} = 2
\Rightarrow
u'(t) = u(t-1) \times q = 2 \times u(t-1)
\]

 

반면 위 처럼 r((t))=20TPS이고 현재 속도는 y((t))=10TPS이 된다면, 기존보다 샘플링해야하는 추적이 2배가 되고,

보정값 q가 증가하게되면, 몇가지 문제가 발생할 수 있습니다.

 

간단한 예로 어플리케이션에 많은 양의 데이터가 들어오는 30분 단위의 batch 작업이 있다고 해봅시다.

batch 시간이 아닐때는 추적이 거의 없으므로 샘플링 확률을 올려서 더 많은 추적을 샘플링하려 합니다.

이 때 갑자기 배치가 실행되면 올라간 샘플링 확률과 배치의 데이터가 맞물려 많은양의 추적이 발생하게되고 이는 서비스에 대한 지연으로 발전 할 수 있습니다.

 

그렇기에 적응형 샘플링에서는 p > 1이면 샘플링값을 바로 계산하지 않고 댐핑 함수(damping function) (B)를 사용합니다.

이를 통해 PID의 제어기의 도함수 항처럼, 샘플링 확률값의 급증을 늦츨 수 있습니다.

예거의 댐핑 함수는 확률값 증가율 (\theta)를 부과합니다. (\theta는 보통 0.5로 설정합니다.

 

\[
\beta(p_{\text{new}}, p_{\text{old}}, \theta) =
\begin{cases}
p_{\text{old}} \cdot (1 + \theta), & \text{if } \frac{p_{\text{new}} - p_{\text{old}}}{p_{\text{old}}} > \theta \\
p_{\text{new}}, & \text{otherwise}
\end{cases}
\]

 

(p_\text{old}) 와 (p_\text{new}) 는 이전 확률 u((t-1))과 새로운 확률 u'((t))를 의미합니다.

예를들어, (p_\text{old})기존값이 0.1이고 (p_\text{new})가 0.35로 증가하는 상황이라면,

 

\[
p_{\text{old}} = 0.2,\; p_{\text{new}} = 0.35,\; \theta = 0.5 \Rightarrow \frac{p_{\text{new}} - p_{\text{old}}}{p_{\text{old}}} = 0.75 > \theta \Rightarrow \beta(p_{\text{new}}, p_{\text{old}}, \theta) = 0.2 \cdot (1 + 0.5) = 0.3
\]

새로운 샘플링 확률 0.35는 급격히 증가한 것이므로, 최종적으로 (\beta)는 0.3이 적용됩니다.

 

따라서 최종 u((t))를 구하는 수식은 아래와 같습니다.

\[
u(t) =
\begin{cases}
\min\left[1,\; \beta\left(u'(t),\; u(t-1),\; \theta\right)\right] & \text{if } u'(t) < u(t-1) \\
u'(t) & \text{otherwise}
\end{cases}
\]

적응형 샘플링의 확장

앞서 살펴본 샘플링 방식은 기본적으로 시간을 기준으로 트래픽 양을 적절하게 유지하는데 목적이 있었습니다.

하지만 경우에 따라 적응형 샘플링은 트래픽 수 뿐만 아니라 초당 스팬 수, 초당 바이트 크기에 대해서도 최적화가 필요합니다.

y((t))를 아래와 같은 식을 사용해 계산하여 스팬 수, 바이트 크기에 대한 비율을 적용할 수 있습니다.

// S: 하나의 추적이 생성하는 스팬의 평균수
// B: 하나의 추적이 생성하는 평균 바이트 크기

(초당 스팬 수) = (초당 추적 수) × S  
(초당 바이트 수) = (초당 추적 수) × B

 

추가로 고려해야할 부분은 하한 속도 계산기(lower-bound rate limiter)입니다.

서비스가 새로운 서비스가 배포 될 때, 해당 서비스의 수집기에서는 대상 샘플링 확률 u((t))를 계산할 데이터가 없습니다.

그렇다면 u((t))는 기본값이 적용되는데, 이는 필요에 따라 보수적으로 매우 낮게 설정되어 있을수도 있습니다.

 

새로운 서비스가 많은 트래픽을 얻지 못하면 적절한 추적 데이터를 얻을 수 없기에,

하한 속도 계산기를 사용해 새로운 서비스의 적응형 샘플러에서 계산할 충분한 데이터를 확보하게 도와줘야합니다.

기존 계산식에 보정치 (r)을 사용하는 방식으로 적용합니다.

u(t)=max(u(t),r)

 

하한속도 보정에 대한 단점도 분명 존재합니다.

만약 하한추적으로 1분에 한 번씩 추적하도록 설정된 서비스가 있을 때, 갑자기 1000개의 인스턴스에 서비스가 배포된다고 가정해봅시다.

그러면 각각 매분 하나의 추적을 샘플링하거나 초당 1000 / 60 = 16.7개의 추적을 샘플링하게 됩니다.

이렇게 되면 하한 속도 계산기(lower-bound rate limiter)에 의해 너무 많은 추적을 얻게 됩니다.

 

이럴 때는 해결 방안으로 해당 수치를 파악할 수 있는 배포 시스템과 통합하는 방법을 고려할수도 있고, 아니면 하한 속도를 계산하는 적응형 알고리즘을 사용하는 방법도 있습니다.

 

또한 서비스의 특정 부분에 주의를 집중시키고 더 높은 빈도로 샘플링해야하는 상황이 있습니다.

예를 들어 서비스의 특정 버전에서 문제가 발생한다면 해당 버전에 대한 샘플링만을 더 높힌다면 더 빠르게 돌발상황에 대처 할 수 있습니다.

그렇기에 추적 시스템에서는 이런 상황에 대처 할 수 있도록, 유연한 기능 메커니즘이 필요합니다.

위와 같은 상황을 대처하기 위해서는 컨텍스트-맞춤형 샘플링을 구현해서 사용해야합니다.

오버샘플링 처리 방법

앞서 계속 살펴보았듯 서비스에서 적절한 샘플링을 적용하는건 어려운일입니다.

하지만 추적 시스템을 사용하는 클라이언트는 아마도 모든 샘플링들을 감지하고 처리하는 추적 시스템을 원할 것 입니다.

 

그렇게 샘플링확률을 올리다보면 오버샘플링이 될 수 있는데,

예거(jaeger)에서는 과부하로부터 서비스를 보호하기 위한 두가지 방법, 다운샘플링과 스로틀링이 존재합니다.

스로틀링과 포스트-컬렉션 다운샘플링

스로틀링 방식은 서비스에서 지나치게 많은 추적이 시작되었다고 판단되면 Drop Policy을 사용해서 추적을 조절하는 방식이며,

다운샘플링은 추적이 수집계층에 도착한 후, 2차 샘플링을 수행해서 오버샘플링을 처리하는 방법입니다.

먼저 traceId를 해시로 변환해서 0~1 사이의 실수로 변경합니다.

이후 지정한 확률보다 작으면 샘플링하고 크면 버립니다.

val downSamplingProbability: Double = 0.1

def downSample(span: Span): Boolean = {
  if (span.isDebug) {
    return false
  }

  val z: Double = hash(span.traceId)
  return z < downSamplingProbability
}

 

테일 기반의 일관성 있는 샘플링

사실 헤드 기반 샘플링은 비정상적인 요청이나 특정 상황에 의미가 있는 요청이 존재할때 해당 요청이 추적되지 않을 확률이 존재합니다.

하지만 테일 기반 샘플링은 일단 모든 추적을 수집한 후 샘플링을 진행합니다.

일종의 pull model과 비슷합니다.

 

반면 모든 트래픽에 대한 추적을 일단 수집해야하기에, 헤드기반에 비해 큰 오버헤드가 발생합니다.

또한 일단 수집된 데이터가 샘플링이 되기 전까지 어딘가에 데이터를 보관해야합니다.

 

보통 어플리케이션에서 헤드 기반과 테일 기반 샘플링은 모두 동일한 비율로 데이터를 샘플링하기에 추가 오버헤드를 피하기 위해 메모리에 추적 데이터를 보관하는게 합리적이라고 합니다.

하지만 서비스 상황에 따라 적절하게 저장소를 활용하는게 중요할 것 같습니다..

 

아래 그림은 2개의 마이크로서비스에서 2개의 요청 T1, T2를 테일기반으로 샘플링하는 상황입니다.

모든 요청은 수집기(Controller)로 전달됩니다. 

 

수집기는 Stateless하기에 수집기에 잠시 저장될 때, TraceId 기반의 데이터 파티션이 필요합니다.

예를들어 'hash(traceId) % 수집기 수'와 같은 방법으로 TraceID를 구분하고,

파티션을 통해 각각의 Span들이 TraceId로 파티션되어 서로 다른 수집기로 가는 상황을 방지합니다.

최종적으로 샘플링 정책을 통해 T2요청만 샘플링되어 저장되며 T1은 버려집니다.

테일 기반에서의 샘플링 전략은 아래와 같습니다.

 

1. 대기 시간 기반 샘플링

추적의 대기 시간(latency)를 기준으로 샘플링합니다.

예를 들어 lantecy가 0ms ~ 2ms 구간에 들어오는 요청은 버리거나 낮은 확률로 샘플링합니다.

반면 100ms 이상 또는 1초 이상 대기가 있던 요청은 중요하게 판단하여 우선으로 샘플링합니다. 

 

2. 에러 여부 기반 샘플링

추적 중 에러가 발생한 트레이스는 무조건 적으로 샘플링합니다.

 

3. 클러스터링 기반 샘플링

유사한 유형의 트레이스, 예를들어 경로, 사용자, 쿼리 등을 클러스터링해서 그룹화된 요청들의 대표값들만 샘플링합니다.

특정 요청에 가중치를 두어 샘플링 할수도 있습니다.

정리

포스팅하면서 찾아보니 Datadog, X-ray와 같은 유명 APM들을 비롯해 많은 APM들은 헤드기반 샘플링에 보조적으로 중요하거나 데이터가 큰 스팬들은 테일기반 샘플링하는 경우가 많은 것 같습니다.

즉 헤드 기반으로 1차로 샘플링하고, 큰 요청이나 오류가 있는 요청들은 테일기반으로 수집해서 구분하여 저장하는 방식인 것 같습니다!