Pinterest의 실시간 시계열 이상 탐지 시스템
Tech Review of Pinterest #2
지난 리뷰
https://brunch.co.kr/@andrewhwan/59
원문 정보
제목 : Building a real-time anomaly detection system for time series at Pinterest
글쓴이 : Kevin Chen (Software Engineer Intern, Visibility), Brian Overstreet (Software Engineer, Visibility)
위 원문을 번역하였습니다. 이해를 위해 의역한 부분도 포함되어 있습니다. 핵심 주제인 'Anomaly'라는 단어는 '이상' 또는 '이상 상황'으로 번역하였습니다.
이번 포스트에서는 Pinterest의 핵심 시계열 운영 지표에 대한 실시간 대용량 이상 탐지 시스템의 기반이 되는 알고리즘과 인프라스트럭쳐를 공유할 것이다. 우리가 얻은 교훈과 앞으로의 계획을 소개한다.
배경
Pinterest는 자체 개발한 지표들과 Statsboard라는 대시보드 시스템으로 각 개발팀이 서비스들의 상태를 실시간으로 확인할 수 있도록 만들었다. 엔지니어들은 Statsboard를 사용하여 시계열 지표에 대한 공통적인 동작들을 간단히 표현하는 한 언어를 통해 경보를 설정할 수 있다. 이 경보들은 다음과 같은 것들을 포함한다.
정적 경보 기준 (Static thresholds): 시스템이나 서비스에 문제가 있을 때 알 수 있도록 설정한 경보 발생 기준 (예: CPU 사용률 95%)
주간 변화량 (Week over week differences): 이번 주와 지난주를 비교했을 때 일정 비율 이상 지표가 낮아지면 발생하는 주기적인 경보 (예: 10% 감소)
그러나, Pinterest의 외적인 성장과 트래픽 지표들은(예: 사이트 요청 수, 사용자 로그인 수) 복잡 다양한 패턴을 나타내기 때문에 특정한 규칙 기반으로 경보를 설정하기가 어렵다. 이렇게 복잡한 지표들을 다룰 수 있는 이상 탐지 시스템이 없으면, 사용자들은 크게 세 종류의 골치 아픈 경보 상황을 겪게 된다.
시간대 변화를 반영하지 못함(Temporal invariance): 주기적으로 변하는 지표(예: 웹 트래픽)에 대한 정적인 '감소' 기준은 지표가 자연스럽게 줄어들 수밖에 없는 밤 시간 동안 거짓 양성 경보를 발생시킬 것이다. 이렇게 시간에 따라 달라지는 지표들의 움직임을 정확하게 잡기 위해서, 우리의 경보도 시간대에 따라 다르게 동작해야 한다.
규칙 예외 상황들(Rule edge cases):우리의 경보 기준이 오직 아침 8시부터 저녁 8시까지만 동작한다고 가정해보자. 만약 저녁 8시 1분에 이슈가 발생한다면 아무런 경보도 울리지 않을 것이다. 규칙 기반 시스템에서는 이렇게 경계에 걸친 예외 케이스들이 사각지대와 추가적인 복잡성을 만들어낸다.
비정상인 상황을 정상으로 판단(Interpreting anomalies as normal): 만약 우리가 어느 수요일에 사이트 전체 지표가 감소하는 장애를 겪었다면, 그다음 주 수요일에는 '지난주에 비해 지표가 증가했다.'는 내용의 경보 폭탄을 받을 수도 있을 것이다. 비정상적인 지표를 정상 지표로 다루지 않도록 조심하지 않으면 오히려 상황이 정상화되었을 때 거짓 경보를 많이 받게 된다.
이상 탐지 방법론들
Twitter의 AnomalyDetection이나 Linkedin의 Luminol과 같은 오픈소스 패키지부터 학계에서 작성된 Rob Hyndmans의 feature-based anomaly detection 논문에 이르기까지, 세상에는 이상 탐지와 관련된 수많은 자료들이 존재한다. 우리는 가장 인기 있는 시계열 이상 탐지 기법들을 크게 네 종류의 분류로 나누어 보았다. (물론 겹치거나 누락된 기법들이 존재할 수 있다.)
상태 공간 모델 (State space models): exponential smoothing, Holt-Winters, ARIMA
분해 (Decomposition): 고전적인 분해 기법들, STL
딥러닝: RNN
차원 감소 (Dimensionality reduction): RPCA, SOM, discords, piecewise linear
우리 경험에서는 분해 방식의 모델들이 가장 좋은 성능을 보여주었다. 이상 탐지에서는 수많은 기계 학습 모델들의 성능이 좋지 않았는데, 왜냐하면 이 방법들은 학습 데이터에 너무 과적합(overfit)되는 경향이 있기 때문이다. 이상 탐지의 특성상, 어떤 '이상 상황'이 과거에 한 번도 발생한 적이 없더라도 잘 구분되고 추출될 수 있어야 한다. 분해 방식의 모델들은 시계열 데이터에서 서로 연관된 요소들을 (Seasonality: 주기성, Trend: 경향성) 명시적으로 제거해주기 때문에 이런 작업에서도 잘 동작하였다. 그래서 우리는 이상 지표의 원래 속성을 유지하면서 잔차(Residual)에 가우시안 가정을 적용시켜보는 통계적 테스트를 해볼 수 있게 되었다.
'nottem' 데이터에서 주기성과 경향성을 분해한 사례관측 가능성(Observability)을 위한 이상 탐지의 요구 사항
관측 가능성을 제공하는 이상 탐지 시스템을 만들기 위해서, 우리는 다음과 같은 요구사항들을 명심해야 한다.
거짓 양성 경보 최소화: 거짓 양성 경보는 졸리거나 화난 엔지니어들이 경보에 둔감해지게 만들어서, 미래에 발생할 장애를 놓치거나 제대로 대응하지 못하게 할 수 있다. 이를 피하려면, 우리는 꼭 심각한 이상 상황에서만 경보를 발생시켜야 하고, 필요할 때는 각자 경보 규칙을 세밀하게 조절할 수 있도록 만들어야 한다.
경보는 수 분 안에 발생: 어떤 문제가 발생했을 때의 영향을 최소화하려면 on-call 담당 엔지니어가 가능한 한 빠르게 상황을 알아차릴 수 있게 해야 한다. 우리는 모든 데이터 입수를 실시간으로 처리하고, 들어온 지 1분 안에 이상인지 아닌지 판단한다.
수백만 개의 시계열에도 적용 가능: 우리의 관측 시스템은 매 초마다 수억 개의 시계열 스트림 데이터 값을 다룬다. 분해 알고리즘은 이미 대부분의 기계 학습 방식에 비해 더 효율적이지만, 우리는 여기서 성능을 더 쥐어짜기 위해 몇 가지 개선을 추가하였다. 또한, Teletraan을 사용하여 요청이 늘어났을 때 예측 워커 수를 자동으로 늘리도록 하였다.
Pinterest에서 자체 개발한 배포 시스템 Teletraan이상 상황에 대한 올바른 대처 (Be Robust to anomalies): 이상 상황이 발생했을 때, 우리의 시스템은 이 데이터 포인트들을 정상 상황의 통계 값에 포함시켜서는 안 된다. 우리는 이를 피하기 위해 강력한 통계치와(3주 정도에 해당하는) 긴 데이터 윈도우를 사용한다.
데이터 누락에 대한 올바른 대처 (Be robust to missing data): 지표에서 종종 몇몇 데이터 포인트들이 누락될 수도 있다. 일반적으로 많이 사용되는 분해 알고리즘의 구현체(R's STL)에서는 이런 누락된 지표들을 따로 처리해주지 않기 때문에, 우리가 직접 이런 차이를 메워주었다.
대응 필요성 고려: 어떤 이상 상황들은 다른 상황에 비해 훨씬 중요하고 당장 대응할 수 있는(actionable) 경우가 있다. 우리의 사용자 정의 규칙들을 사용하면 당장 대응이 가능한 이상 상황들을 나머지 상황에서 걸러낼 수 있다.
다음으로, 우리 모델을 실시간으로 적용하기 위해 겪어야 했던 여러 가지 난관들을 소개하겠다.
모델을 어떻게 실시간으로 업데이트할 것인가?
많은 이상 탐지 방법들은 정해진 데이터셋 안에서 회고적 방식으로(retrospective) 이상 상황을 찾아낸다. 예를 들어, LBFGS나 Nelder-Mead와 같은 비선형 최적화 방법으로 모델을 만든 다음, 학습 데이터에서 이상 상황을 골라내는 식이다.
그러나, 만약 실시간으로 이상을 탐지해내고 싶다면 한 번만 학습하는 것은 충분하지 않다. 우리는 지표의 최근 움직임을 적용하기 위해 계속해서 모델을 업데이트하여야 한다. 그래서, 우리는 시간의 흐름에 따라 모델의 parameter들을 업데이트해주는 네 가지 접근 방식 중 하나를 선택해야 한다.
1. 무차별 업데이트: 가장 간단한 해결책으로, 새로운 데이터가 들어올 때마다 최근 데이터 윈도우의 parameter들을 다시 계산한다. 그러나, 만약 윈도우의 모델을 계산하는 방식이 복잡할 경우 적용할 수 없다.
2. 시간 지정 업데이트: 모델의 parameter들을 특정 시간 동안 캐싱해둔다. 예를 들어, 24시간 정도 캐싱하고, 한 주기가 끝나고 새 데이터가 들어오면 다시 모델을 학습시킨다. 그러나, 만약 정해진 시간이 지나지 않은 상태에서 지표 패턴이 변화하면 과도한 거짓 양성 경보가 발생할 수 있다.
3. 이벤트 기반 업데이트: 만약 최신 데이터에서 예측의 오차가 큰 것이 감지되면, 그것을 우리의 parameter 계산이 다시 필요하다는 신호로 사용할 수 있다. 이벤트 기반의 업데이트는 예측이 불가능하기 때문에 나중에 운영 상 까다로운 문제를 일으킬 수도 있다.
4. 온라인 업데이트: 몇몇 알고리즘들은, 온라인 상황에서 바로바로 재계산이 가능한 경우가 있다. 연속적으로 새로운 데이터를 읽으면서 효율적으로 각 데이터에 대한 parameter를 업데이트하는 것이다.
우리는 시간 지정 업데이트나 이벤트 기반 업데이트 방식은 얻을 수 있는 이득에 비해 디버깅의 고통이 너무 크다는 것을 알게 되었다. 그래서 온라인 업데이트 방식이 적용 가능한 경우에는 적용하고, 안 되는 경우에는 그냥 무차별 업데이트를 수행했다. 우리의 알고리즘을 온라인 방식에 적용하기 위해서 Online Gradient Descent를 Optimizer로 사용하였다.
loss 표면의 gradient descent 시각화주기성과 경향성 추정
STL이라 불리는 요즘 가장 많이 사용되는 분해 방식에서는 Loess라는 회귀 절차를 사용한다. Loess는 데이터의 부분집합에 대해 낮은 차수의 다항식을 반복적으로 fit 시키는 방식이다. 불행하게도, 이 방식을 실시간 분석에 적용하면 확장성이 떨어진다.
Loess를 반복하여 주기성을 추정하는 대신에, 우리는 그냥 fourier와 historical sampling과 같은 효율적인 주기성 추정 기법들을 몇 가지 조합해서 사용하고 있다. 또한, Twitter의 S-H-ESD 이상 탐지 알고리즘에서 영감을 얻어서 STL의 경향성 요소도 median으로 교체하였다.
예측 범위
정규 분포에서 68-95-99.7 규칙은, 평균 주변 값들의 비율을 쉽게 계산하게 해 준다.한번 예측을 하고 나면, 우리는 예측 지점으로부터의 거리 기반으로 어느 데이터가 이상 상황인지 아닌지 판단하게 된다. 이를 위해 우리는 3 시그마 규칙을 사용하는데, 이는 정규분포 상에서 99.73%의 값들이 평균으로부터 3 시그마 범위 안에 들어온다는 가정이다. 만약 새로 들어온 데이터가 우리 예측에서 3 표준편차 이상 벗어난다면, 이 데이터 포인트를 이상 상황이라고 합리적으로 의심할 수 있을 것이다.
만약 데이터가 정상적이지 않다면(예를 들어 시계열 데이터에 이상 값이 포함되어 있다면), 우리는 정상 데이터셋의 회복을 위해 누승 변환(power transformation)을 적용해볼 수 있다. 이 방법이 동작하지 않더라도 과거 에러에서 sample을 가져오는 등의 방법으로 값을 추정해볼 수 있다.
이렇게 범위를 만들고 나면, 우리는 이것을 UI 상에서 시각적인 밴드로 표현하여 사용자들이 쉽게 해석할 수 있게 해 줄 수 있다.
이제 이 알고리즘들을 뒷받침하는 인프라스트럭쳐를 살펴보자.
이상 탐지 구조
Statsboard의 실시간 지표들보다 한 발 앞서서 예측을 수행하고 우리의 시계열 데이터베이스(TSDB)에 전달해주는 예측 서버가 있다.
이 예측 서버는 매 분마다 예측 작업을 생성하는 스케쥴러와 작업 큐를 가진 서버 하나와 확장 가능한 워커들도 구성되어 있다. 배치 작업의 경우 network와 I/O 사용을 최소화하기 위해 겹치는 데이터 윈도우에 대한 요청들을 미리 합쳐둔다. 우리는 이상 탐지 생성기와 경보, 대시보드를 제공하기 위하여 기존 Statsboard UI와 경보 인프라스트럭쳐에 이 서버를 통합하였다.
요약
고전적인 경보 방식으로는 모델링할 수 없는 복잡한 지표들에 대한 가시성을 얻는다는 측면에 있어서 이상 탐지는 매우 중요한 역할을 한다. 한 번도 본 적 없는 이상 상황들이 실시간으로 대시보드에 등장하고, 무엇인가 잘못되고 있을 때 관련자들에게 경보를 발송한다.
강력하고 확장 가능하고 해석할 수 있는 알고리즘들을 활용하여, 우리의 이상 탐지 시스템은 문제가 발생하자마자 엔지니어들이 바로 알아차리고 대응할 수 있게 하여, Pinterest의 사업과 Pinner들에게 주는 영향을 최소화하고 있다.
