로그 필터링 성능 저하의 근본 원인과 Aho-Corasick 최적화

제시된 다중 패턴 로그 필터링 시스템의 성능 저하 원인은 패턴 수에 비례하여 작업량이 증가하는 비효율적인 매칭 방식 때문입니다. 근본적인 해결책은 $\text{Aho-Corasick}$ 알고리즘을 도입하고, 그 핵심 자료구조인 $\text{Trie}$를 Redis에 캐싱하여 초기화 비용을 최소화하는 것입니다.

---

1. 성능 저하의 근본 원인 분석

기존 방식은 로그 하나를 처리할 때마다 모든 필터 패턴을 순차적으로 개별 확인합니다.

1.1. 반복적인 $O(\text{K})$ 순회

• 비효율: 로그 텍스트 $\text{L}$에 대해 $\text{K}$개의 패턴을 매칭하는 시간 복잡도는 $O(\text{K} \times \text{L})$입니다. 패턴의 수가 두 배 늘면 처리 시간도 두 배 늘어납니다.
• 낭비: 매칭을 위해 로그와 패턴을 소문자 문자열로 매번 새로 생성하여 가비지 컬렉션 $\text{GC}$ 부하와 메모리 낭비를 유발합니다.

1.2. 첫 번째 개선 시도의 한계

패턴을 미리 분류하는 사전 컴파일은 중복 문자열 생성 문제를 해결했으나, $\text{prefixes}$ 목록이나 $\text{contains}$ 목록을 순차적으로 확인하는 $O(\text{K})$ 순회 문제는 여전히 남아 있어 패턴 수가 많아지면 성능 저하가 발생합니다.

---

2. Aho-Corasick 알고리즘 도입하는 해결책

$\text{Aho-Corasick}$ 알고리즘은 텍스트를 단 한 번 순회하면서 모든 패턴을 동시에 찾는 방식으로, 시간 복잡도를 획기적으로 개선합니다.

2.1. 다중 패턴 매칭의 효율화

구분	기존 방식	$\text{Aho-Corasick}$
시간 복잡도	$O(\text{K} \times \text{L})$	$O(\text{M} + \text{L})$
특징	패턴 수 $\text{K}$에 비례	텍스트 길이 $\text{L}$에만 선형적으로 비례

• $\text{M}$은 모든 패턴 문자열의 총 길이 $\text{Trie}$ 구축 비용
• $\text{L}$은 로그 텍스트 길이 $\text{검색 비용}$

패턴 수 $\text{K}$가 100배 늘어나도 검색 시간은 거의 변하지 않아 시스템의 확장성을 보장합니다.

2.2. Trie와 Failure Link

$\text{Aho-Corasick}$은 Trie 접두사 트리 구조를 사용하여 패턴을 효율적으로 저장하고, Failure Link를 통해 매칭 실패 시 텍스트 전체를 재탐색하는 것을 방지합니다.

2.3. 와일드카드 패턴 처리

$\text{Aho-Corasick}$이 기본적으로 지원하는 $\text{Contains}$ 검색 외에 와일드카드 패턴 $\text{Prefix}$와 $\text{Suffix}$도 매칭된 결과의 위치 정보를 활용하여 처리합니다.

• $\text{Prefix}$ "keyword*": 매칭 $\text{start}$ 인덱스가 0인지 확인
• $\text{Suffix}$ "*keyword": 매칭 $\text{end}$ 인덱스가 텍스트 길이 $- 1$인지 확인

---

3. Redis 캐싱 전략 적용 하기

$\text{Aho-Corasick}$의 $\text{Trie}$ 자료구조를 구축하는 것은 $\text{M}$에 비례하는 초기 비용이 발생합니다. 로그 시스템의 여러 인스턴스에서 이 비용을 반복적으로 지불하지 않도록 Redis를 활용해 $\text{Trie}$ 구조의 컴파일 결과를 캐싱합니다.

3.1. 캐싱 대상과 키

• 캐싱 대상: $\text{Aho-Corasick}$ 라이브러리에서 생성된 직렬화 가능한 $\text{Trie}$ 모델 $\text{CompiledPatternMatcher}$ 객체를 캐싱합니다.
• 캐시 키: 필터 $\text{ID}$와 현재 활성 패턴 목록의 해시값을 조합한 키를 사용합니다. 패턴이 바뀌지 않는 한 $\text{Redis}$에서 캐시된 $\text{Trie}$를 가져와 사용합니다.

3.2. 전체 서비스 흐름

1. 필터 조회: 서비스가 $\text{DB}$에서 현재 활성 필터 $\text{ID}$와 패턴 목록을 가져옵니다.
2. 캐시 키 생성: 필터 $\text{ID}$와 패턴 해시값을 이용해 $\text{Redis}$ 캐시 키를 만듭니다.
3. Redis 확인: 해당 키로 $\text{Redis}$에서 직렬화된 $\text{Trie}$ 모델을 조회합니다.
   • 캐시 히트: 직렬화된 $\text{Trie}$ 모델을 역직렬화하여 $\text{CompiledPatternMatcher}$를 즉시 재사용합니다.
   • 캐시 미스: $\text{Aho-Corasick}$ 빌더를 사용하여 $\text{Trie}$를 새로 구축합니다. 구축이 완료되면 $\text{Trie}$ 모델을 직렬화하여 $\text{Redis}$에 저장합니다.
4. 로그 매칭: 캐싱되거나 새로 구축된 $\text{CompiledPatternMatcher}$의 $\text{matches}$ 함수를 $O(\text{L})$ 복잡도로 실행하여 필터링합니다.

3.3. 이점

• 초기화 비용 분산: $\text{Trie}$ 구축 비용이 모든 서비스 인스턴스에 걸쳐 단 한 번 $\text{Redis}$에 저장될 때 발생하며, 이후에는 $\text{Redis}$ $\text{GET}$ 요청과 역직렬화 $\text{작업}$만 수행하면 됩니다.
• 일관성 유지: 다중 인스턴스 환경에서 모든 서버가 $\text{Redis}$를 통해 동일하고 최신의 $\text{Trie}$ 구조를 공유합니다.

---

4. 최종 결론

시나리오	기존 방식 작업량	$\text{Aho-Corasick}$ 작업량	개선 효과
패턴 100개, 텍스트 20글자	$100 \times 20 = 2000$	$\approx 20$	100배

$\text{Aho-Corasick}$ 알고리즘을 통해 다중 패턴 매칭의 시간 복잡도를 $O(\text{K} \times \text{L})$에서 $O(\text{M} + \text{L})$로 근본적으로 개선했습니다. 여기에 Redis 캐싱 전략을 결합하여, 패턴이 변경될 때 발생하는 초기화 비용 $\text{Trie}$ 구축 비용마저도 네트워크 전반에 걸쳐 효율적으로 관리하여 실시간 로그 처리 시스템의 성능과 안정성을 모두 확보할 수 있습니다.

참고 자료

Aho-Corasick Algorithm (Wikipedia)
Efficient String Matching: An Aid to Bibliographic Search (Original Paper, 1975)
KMP Algorithm - Failure Function의 원리