⚡ electrical engineering

eIRWR: Enhanced Iterative Random Walk with Restart for Scalable Root Cause Analysis in Microservices

이 논문은 의심스러운 노드에 재시작 질량을 집중시키고 전이 확률을 정교화함으로써 대규모 토폴로지에서 기존 베이스라인 대비 현저히 높은 정확도와 낮은 지연 시간을 달성하여 마이크로서비스의 확장 가능한 근본 원인 분석을 개선하는 향상된 반복적 랜덤 워크 위드 리스타트(eIRWR) 알고리즘을 소개한다.

원저자: Saiful Khan, Afrah Farea

게시일 2026-08-11

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Saiful Khan, Afrah Farea

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

인터넷을 수백만 명의 작고 전문화된 일꾼들(‘마이크로서비스’라고 불리는)이 웹사이트를 구축하고, 영상을 스트리밍하며, 온라인 주문을 처리하기 위해 끊임없이 서로에게 쪽지를 전달하는 거대하고 북적이는 도시라고 상상해 보십시오. 모든 것이 제대로 작동할 때, 이는 효율성의 교향곡과 같습니다. 하지만 한 일꾼이 자신의 신발 끈에 걸려 넘어지면, 그 혼란은 파도처럼 번져나가 전체 동네를 마비시키는 연쇄 반응을 일으킬 수 있습니다. 실제로 누가 먼저 발을 헛디뎠는지 찾아내는 것은, 누군가의 재채기 때문에 모두가 기침을 하고 있는 경기장 안에서 단 한 명의 재채기하는 사람을 찾는 것과 같습니다. 이것이 바로 우리의 디지털 삶을 원활하게 유지하기 위한 핵심 과업인 ‘근본 원인 분석(Root Cause Analysis, RCA)’의 세계입니다. 이를 해결하기 위해 과학자들은 종-종 ‘재시작이 있는 무작위 보행(Random Walk with Restart)’이라는 영리한 기술을 사용합니다. 도시의 지도 속을 헤매며 교통 흐름을 따라가는 탐정을 떠올려 보십시오. 탐정이 혼란에 빠지거나 막다른 길에 다다를 때마다, 탐정은 마법처럼 가장 큰 소음이 발생하는 현장으로 순간 이동하여 다시 시작합니다. 이렇게 반복하다 보면, 탐정은 단순히 소음이 가장 큰 곳이 아니라 실제로 문제가 시작된 지점에서 결국 가장 많은 시간을 보내게 될 것이라는 희망을 품는 것입니다.

‘EIRWR’라는 제목의 이 논문은 우리가 어떻게 이 탐정을 훨씬 더 똑똑하게 만들 수 있는지 깊이 파고듭니다. 저자인 사이풀 칸(Saiful Khan)과 아프라 파레아(Afrah Farea)는 기존의 이러한 탐정 보행 방식에 중대한 사각지대가 있다는 것을 발견했습니다. 그들은 기존의 많은 방식이 실수로 탐정을 실제 재채기를 한 사람이 아닌, 혼란의 가장 큰 피해자들(예를 들어 가장 격렬하게 기침을 하는 사람들)에게로 순간 이동시키고 있으며, 이것이 종종 실제 재채기한 사람으로부터 탐정을 멀어지게 만든다는 것을 발견했습니다. 그들은 정밀한 테스트를 통해, ‘회복 탄력성 댐핑(resilience damping)’이라 불리는 인기 있는 기술이—서비스가 장애를 처리하는 방식을 모델링하는 멋진 새로운 방법이라고 생각되었던—사실은 단순히 더 자주 순간 이동하는 것을 수학적으로 위장한 것에 불과하다는 것을 증명했습니다. 그것은 문제의 방향에 대해 탐정에게 새로운 것을 가르쳐주지 못했습니다.

그래서 연구팀은 eIRWR(Enhanced Iterative Random Walk with Restart)이라는 이름의 업그레이드된 탐정 시스템을 구축했습니다. eIRWR는 단순히 가장 큰 소음으로 순간 이동하는 대신, ‘파워 로(power-law)’ 기법을 사용하여 초점을 날카롭게 맞추고, 주변의 잡음을 무시하며 가장 의심스럽고 독립적인 단서에 집중합니다. 또한, 이들은 탐정에게 교통 흐름을 거슬러 상류로 올라가 근원을 찾을 수 있도록 ‘역방향 엣지(backward edges)’가 포함된 특별한 지도를 제공했으며, 진정한 기원으로 보이는 지점에 탐정이 더 오래 머물 수 있도록 ‘자기 루프(self-loops)’를 추가했습니다.

시뮬레이션 결과는 인상적입니다. 최대 25,000개의 서비스를 가진 거대한 디지털 도시 지도에서 테스트했을 때, 새로운 eIRWR 탐정은 단서가 중간 정도로 명확할 때 1.0점 만점에 0.75점의 점수로 실제 근본 원인을 찾아냈는데, 이는 기존의 가장 우수한 방식들보다 거의 3배나 높은 수치입니다. 단서가 매우 명확할 때는 0.94점에 도달했습니다. 아마도 실제 사용 측면에서 가장 중요한 점은, 이 시스템이 17,000개의 노드를 가진 그래프에서 25밀리초 미만의 시간 안에 모든 계산을 수행했다는 것입니다. 즉, 시스템이 실행 중인 동안 즉각적으로 사용할 수 있다는 의미입니다. 논문은 근본 원인을 항상 완벽하게 볼 수는 없지만(특히 그것이 완전히 숨겨져 있는 경우), 우리가 탐색을 ‘재시작’하는 방식을 재설계하는 것이 불똥이 튄 무고한 행인들과 진짜 범인을 구별하는 핵심 열쇠라고 결론짓습니다.

기술 요약: eIRWR – 확장 가능한 근본 원인 분석을 위한 강화된 반복적 재시작 랜덤 워크 (Enhanced Iterative Random Walk with Restart)

1. 문제 정의

마이크로서비스 아키텍처에서 단일 서비스의 결함은 동기식 호출 체인을 통해 연쇄적으로 전파되어, 수백 개의 상호 의존적인 서비스 전체에 걸쳐 지연 시간 급증 및 에러 폭증을 유발할 수 있습니다. 근본 원인 분석(Root Cause Analysis, RCA)의 목표는 서비스 의존성 그래프와 관찰된 이상 징후 벡터(예: 집계된 지연 시간 또는 에러율)가 주어졌을 때, 결함이 발생한 기점인 서비스(근본 원인)를 식별하는 것입니다.

핵심 과제는 근본 원인이 반드시 가장 높은 이상 징후 점수를 가진 서비스는 아니라는 점입니다. 하류(downstream)의 "희생자(victim)" 서비스들은 연쇄 장애의 누적으로 인해 실제 소스보다 더 크고 뚜렷한 증상을 나타내는 경우가 많습니다. Personalized PageRank(PPR) 및 MicroRCA와 같은 기존의 그래프 기반 방식들은 의존성 그래프를 통해 이상 징후 증거를 전파하지만, 소스와 희생자를 구분하는 데 종종 실패합니다. 이들은 원시 이상 징후 벡터로부터 랜덤 워크를 재시작하는데, 이 벡터는 이러한 시끄러운 하류 희생자들에 의해 지배됩니다. 이로 인해 확률 질량이 근본 원인이 아닌 증상에 정착하게 됩니다. 또한, 본 논문은 전이 행렬(transition matrix)을 전치하거나 균일한 회복력 감쇠(resilience damping)를 적용하는 등의 기존 문헌의 일반적인 "개선책"들이 실제로 국지화 성능을 개선하는 것이 아니라, 단순히 재시작 확률을 높이는 것과 수학적으로 동일하다고 주장합니다.

2. 방법론

본 논문은 근본 원인 위치에 확률 질량을 집중시키기 위해 설계된 세 가지 특정 메커니즘을 통해 표준 이상 징후 시드 기반 랜덤 워크를 정교화한 eIRWR (Enhanced Iterative Random Walk with Restart) 방식을 제안합니다.

2.1 베이스라인 및 이론적 통찰

저자들은 먼저 **반복적 재시작 랜덤 워크(Iterative Random Walk with Restart, IRWR)**를 사용하여 베이스라인을 설정합니다. 이들은 통제된 절제 연구(ablation study)를 통해 다음을 입증했습니다:

회복력 감쇠(Resilience Damping): 전이 행렬에 균일한 "회복력" 인자를 적용하여 이를 부분 확률적(sub-stochastic)으로 만드는 것은 대수적으로 표준 PPR에서 재시작 확률( $\alpha$ )을 높이는 것과 동일합니다. 따라서 비교는 단순히 기본 설정이 아닌, 재시작이 튜닝된 PPR과 이루어져야 합니다.
역방향 가로지르기(Backward Transversal): 의존성 행렬의 실제 전치 행렬(호출자에서 피호출자로 전파) 위에서 걷는 것은 역효과를 낳으며, 확률을 루트(root)가 아닌 리프(leaf) 서비스 쪽으로 밀어냅니다.

2.2 eIRWR 알고리즘

eIRWR은 반복적 거듭제곱법(power-iteration) 프레임워크를 유지하면서, 근본 원인 위치에 머물도록 유도하는 세 가지 구조적 및 알고리즘적 개선 사항을 도입합니다:

멱법칙 텔레포테이션 샤프닝 (Power-Law Teleportation Sharpening):
원시 이상 징후 벡터를 기반으로 균일하게 재시작하는 대신, eIRWR은 믿음 벡터(belief vector)에 멱법칙 변환( $v \propto b^q$ )을 적용합니다. 이는 텔레포테이션 질량을 "날카롭게(sharpening)" 만들어, 가장 의심스러운 노드에 질량을 집중시키고 노이즈가 섞인 배경 서비스로의 재시작을 억제합니다. 적응형 지수 $q$ 가 사용되며, 신호 대 잡음비(SNR)가 높을수록 샤프닝 효과가 커집니다.
구조적 증강 (Self-Loops 및 Backward Edges):
전이 행렬을 수정하여 워커(walker)가 잠재적 근본 원인에 오래 머물도록 유도합니다:

셀프 루프 (Self-Loops): 믿음 점수가 최대 출력 전이 가중치를 초과하는 노드에 추가되어, 워커가 소스에 머물도록 권장합니다.
역방향 엣지 (Backward Edges): 의존성 그래프에 직접적인 엣지가 없더라도 노드에서 그 호출자(caller)로 향하는 엣지를 추가하여, 워커가 상류(upstream) 서비스를 탐색할 수 있도록 합니다. 이는 근본 원인이 가장 눈에 띄는 증상의 상류에 있을 때 필수적입니다.

외부 루프 믿음 정교화 (Outer Loop Belief Refinement):
eIRWR은 어떤 노드가 의심스러운지에 대한 "믿음"을 점진적으로 정교화하는 외부 루프를 채택합니다. 믿음 벡터는 원시 이상 징후 관측값과 이전 반복 결과의 모멘텀 가중 조합입니다. 이 정교화된 믿음은 (이상 징후 조건부 회복력을 통한) 전이 행렬과 샤프닝된 텔레포테이션 벡터 모두에 영향을 미쳐, 알고리즘이 소스와 희생자를 반복적으로 분리할 수 있게 합니다.

2.3 복잡도

이 방법은 희소 행렬(sparse matrices)에서 작동합니다. 사건당 계산 비용은 $O(n_{outer} \cdot (K_{inner} \cdot |E| + |E|))$ 이며, 여기서 $|E|$ 는 엣지의 수입니다. 구조적 증강에도 불구하고, 이 방법은 빠르게 수렴하며(통상 65회 반복 이내) 낮은 메모리 오버헤드를 유지합니다.

3. 주요 기여

베이스라인의 재평가: 본 논문은 "회복력 감쇠"된 워크가 재시작이 튜닝된 PPR과 동일하다는 엄격한 수학적 증명과 경험적 검증을 제공합니다. 저자들은 이러한 방식들의 우월성에 대한 기존의 주장이 제대로 튜닝되지 않은 베이스라인과 비교한 결과물(artifact)이라고 주장합니다.
eIRWR 알고리즘: 멱법칙 텔레포테이션 샤프닝, 셀프 루프/역방향 엣지 증강, 그리고 믿음 정교화를 결结合하여 근본 원인 타겟팅을 구체화한 구조적 강화 워크를 제안합니다.
대규모 평가: Alibaba 마이크로서비스 트레이스 데이터셋에서 유도된 세 가지 대규모 토폴로지(12K ~ 25K 노드)에서 8개의 집계 지표 베이스라인과 eIRWR을 비교하는 포괄적인 평가를 수행했습니다.

4. 실험 결과

평가는 다양한 "근본 원인 가시성(visibility, $v$ )" 수준에서 시뮬레이션된 이상 징후 사건을 포함하여 세 가지 Alibaba 호출 그래프 토폴로지(CG84, CG136, CG297)에서 수행되었습니다.

중간 가시성 ( $v=0.3$ )에서의 성능: eIRWR은 0.75의 평균 역수 순위(Mean Reciprocal Rank, MRR)를 달성하였으며, 이는 최적의 집계 지표 베이스라인(MonitorRank/Corr-Fusion, MRR $\approx$ 0.27)보다 2.8배 향상된 수치입니다. 또한 베이스라인의 PR@1이 0.17인 것에 비해 0.58의 Precision@1을 달성했습니다.
높은 가시성 ( $v=0.5$ )에서의 성능: eIRWR은 MRR 0.94, PR@1 0.90에 도달하여, 90%의 사건에서 근본 원인을 최상위 순위 서비스로 정확히 식별했습니다.
절제 연구 (Ablation Studies):
- 기본 IRWR(회복력 감쇠만 사용)은 재시작이 튜닝된 PPR과 동일한 성능을 보였으며, 이는 감쇠만으로는 새로운 국지화 능력을 제공할 수 없음을 확인시켜 줍니다.
- 성능 향상의 상당 부분(MRR 0.50 $\to$ 0.75 at $v=0.3$ )은 전적으로 eIRWR의 개선 사항(샤프닝 및 구조적 증강) 덕분인 것으로 나타났습니다.
확장성 및 효율성:
- 17,000개의 노드를 가진 그래프에서 eIRWR은 25ms 미만(22.6ms)에 실행되어 온라인 배포에 적합합니다.
- 외부 루프와 구조적 증강으로 인해 기본 PPR보다는 약 4배 느리지만, CloudRanger와 같은 스토캐스틱 샘플링 방식(약 12초 소요)보다는 수십 배 빠릅니다.
- 메모리 사용량은 낮게 유지됩니다 (17K 노드 기준 7.2 MB).

5. 의의 및 주장

본 논문은 기존의 집계 지표 기반 RCA 방법의 주요 한계가 전이 행렬 자체가 아니라 **재시작 분포(restart distribution)**에 있다고 주장합니다. 기존 방식들은 가장 시끄러운 증상(희생자)에서 재시작하므로, 랜덤 워크가 잘못된 노드를 강화하게 만듭니다.

eIRWR의 의의는 랜덤 워크의 재시작 지점을 재설계하여, 하류의 영향이 아닌 가장 의심스럽고 독립적인 이상 징후(소스)에 확률을 집중시킬 수 있다는 점에 있습니다. 이러한 구조적 수정(셀프 루프 및 역방향 탐색)과 결합함으로써, eIRWR은 근본 원인의 신호가 일부 가려져 있는 상황에서도 효과적으로 소스와 희생자를 분리해 냅니다.

저자들은 다음과 같은 점을 인정하며 신중한 입장을 유지합니다:

가시성이 제로인 경우(근본 원인이 신호를 전혀 내보내지 않는 경우), 모든 집계 지표 방식은 성능 한계에 부딪히며, 트레이스 레벨 방식(요청당 데이터를 요구하는 방식)이 여 ยัง 우위에 있습니다.
시뮬레이션된 사건들은 유익하지만, 부분적 실패나 재시도와 같은 실제 세계의 복잡성을 모두 포착하지 못할 수 있습니다.
기본 PPR보다 높은 계산 비용은 극도로 지연 시간에 민감한 환경에서 제약이 될 수 있습니다.

궁극적으로 eIRWR은 마이크로서비스를 위한 확장 가능한 온라인 RCA를 위해서는, 근본적인 결함 전파 모델을 수정하는 것보다 랜덤 워크가 어디서 그리고 어떻게 재시작되는지를 정교화하는 것이 더 중요하다는 것을 보여줍니다.