키워드 672개를 contains로 훑고 있습니다 (Aho-Corasick과 71배 차이, 그런데 아직 안 바꿨어요)

[배경 - 게시판 단위로는 부족하다는 피드백]

아주이벤트는 원래 게시판 단위로만 구독할 수 있었습니다. 소프트웨어학과 공지를 구독하면 그 게시판의 새 글이 전부 오는 식이에요.

사용자에게 이런 얘기를 들었습니다. 게시판 전체는 너무 많고, “장학금” 이 들어간 공지만 받고 싶다고요. 그래서 키워드 구독을 붙였습니다. 지금 운영 중인 키워드는 672건이에요.

구현은 단순했습니다. 새 공지가 들어오면 등록된 키워드를 하나씩 돌면서 제목에 들어 있는지 보는 거예요. 그런데 키워드가 늘어나는 걸 보면서 이게 언제까지 괜찮은지 궁금해졌습니다.

[문제 상황 분석 - contains를 N번 도는 비용]

지금 코드는 이렇습니다

public List<Keyword> findMatchingByClubEvent(Topic topic, ClubEventCommand command) {
    return keywordRepositoryPort.findByTopic(topic).stream()
        .filter(keyword -> {
            String kw = keyword.getKoreanKeyword().toLowerCase();
            return (command.title() != null && command.title().toLowerCase().contains(kw))
                || (command.content() != null && command.content().toLowerCase().contains(kw));
        })
        .toList();
}

키워드 하나마다 contains 를 부릅니다. 등록 키워드가 N개, 검사할 텍스트 길이가 M이면 최악 O(N×M)이에요.

String.contains 는 내부적으로 indexOf 를 부르고, JDK의 indexOf 는 단순 비교 기반입니다. 문자 하나가 어긋나면 시작 위치를 한 칸 밀어서 다시 비교해요. KMP 같은 전처리가 없습니다.

그러니까 이 코드는 같은 텍스트를 키워드 수만큼 반복해서 읽습니다. 672개면 672번 훑는 거예요.

눈에 걸리는 게 하나 더 있어요. title().toLowerCase() 가 필터 안에 있습니다. 키워드마다 제목 소문자 변환이 다시 일어나요. 문자열이 새로 할당됩니다. 이건 알고리즘을 바꾸기 전에 밖으로 빼기만 해도 줄어드는 비용입니다.

Aho-Corasick 은 텍스트를 한 번만 읽습니다

여러 패턴을 동시에 찾는 고전 알고리즘이 있습니다. Aho-Corasick이에요. 구조는 두 부분입니다.

Trie. 키워드들을 글자 단위로 트리에 넣습니다. “장학금” 과 “장학생” 은 “장” 과 “학” 을 공유해요.

        (root)
          │
          장
          │
          학
         ╱ ╲
        금   생
       [끝] [끝]

Failure Link. 매칭이 중간에 깨졌을 때 어디로 돌아갈지 미리 계산해둔 포인터입니다. 이게 핵심이에요.

“장학사업” 이라는 텍스트를 읽는다고 해봅시다. “장”, “학” 까지 따라가다가 “사” 에서 막혀요. 여기서 처음으로 돌아가 다시 시작하면 O(N×M)과 다를 게 없습니다. Failure Link는 “장학” 의 접미사 중에 다른 키워드의 접두사인 것이 있는가” 를 미리 계산해두고 그리로 점프해요.

덕분에 텍스트의 각 문자를 한 번씩만 읽고 지나갑니다. 전체 비용이 O(N + M + K)가 돼요. N은 전체 키워드 길이 합, M은 텍스트 길이, K는 찾은 개수입니다.

대신 대가가 있습니다. 키워드가 추가되거나 삭제되면 오토마톤을 다시 만들어야 해요. 전처리 기반이라 그렇습니다.

[해결 방법 - 일단 재보기로 했습니다]

바꾸기 전에 얼마나 차이가 나는지부터 재보기로 했어요. 실제 코드에 넣고 재는 대신 별도 하네스를 만들었습니다.

조건은 이렇습니다.

• JDK 25.0.2
• 공지 제목 1,000건, 평균 길이 40자
• 키워드는 학과명, 어간, 접미사를 조합해 생성 (실제 등록 키워드가 아닌 합성 데이터)
• 각 방식을 5회 워밍업 후 20회 반복해 평균
• Aho-Corasick 은 Trie와 Failure Link를 직접 구현

측정하다가 걸린 게 하나 있어요. 첫 실행에서 두 방식의 매칭 수가 어긋났습니다. 100개 기준으로 709 대 718이었어요.

원인은 두 방식의 의미가 다르기 때문이었습니다. contains 는 “있다/없다” 를 돌려주는데, Aho-Corasick의 탐색은 출현 위치를 전부 돌려줘요. 같은 키워드가 제목에 두 번 나오면 두 번 세집니다.

그래서 제목당 결과를 HashSet 으로 접어서 의미를 맞췄습니다.

static long ahoRun(Automaton ac, List<String> titles) {
    long hits = 0;
    for (String title : titles) {
        // contains() 와 같은 의미로 맞추려면 제목당 키워드 1회로 접어야 한다.
        hits += new HashSet<>(ac.search(title.toLowerCase())).size();
    }
    return hits;
}

이건 실제 적용할 때도 그대로 걸리는 문제예요. 발송 대상을 뽑을 때 같은 키워드가 두 번 잡히면 푸시가 두 번 나갑니다.

[성과 - 개선 전후 비교]

공지 1,000건을 훑는 데 걸린 시간입니다.

매칭 결과 개수는 네 구간 모두 두 방식이 일치했습니다.

읽는 법이 두 갈래예요.

증가 곡선을 보면 예상대로입니다. contains는 키워드 수에 정비례해서 늘어나요. 10에서 5,000으로 500배 늘리니 시간도 0.92ms에서 293.41ms로 약 319배가 됐습니다. Aho-Corasick은 0.43ms에서 0.67ms로 거의 안 움직여요. 텍스트를 한 번만 읽으니 키워드 수와 무관합니다.

절대값을 보면 이야기가 달라집니다. 이 표는 공지 1,000건 기준이에요. 아주이벤트는 공지가 들어올 때마다 한 건씩 처리합니다. 그러니까 672개 키워드 기준으로 공지 한 건당 0.04ms 예요.

그리고 실제 코드는 findByTopic(topic) 으로 그 게시판의 키워드만 가져옵니다. 672개 전체를 도는 게 아니에요. 게시판이 50여 개니까 실제 N은 훨씬 작습니다.

즉 71배라는 숫자는 사실이지만, 0.04ms를 0.0006ms로 줄이는 71배입니다.

[결론]

그래서 아직 안 바꿨습니다.

이걸 명확히 적어두고 싶어요. 이력서에는 Aho-Corasick으로 전환했다고 썼는데, 저장소 코드는 여전히 contains 반복입니다. 알고리즘을 검토하고 측정한 것과 적용한 것은 다른 일인데 제가 그걸 뭉개서 적었어요.

측정하고 나서 안 바꾸기로 한 이유는 이렇습니다.

첫째, 현재 규모에서 병목이 아닙니다. 공지 한 건에 0.04ms입니다. 같은 흐름에서 DB 조회와 FCM 발송이 수백 ms를 쓰는데, 여기를 줄여도 눈에 안 띄어요.

둘째, 재빌드 비용을 어디에 둘지 안 정했습니다. 키워드는 사용자가 실시간으로 추가하고 지웁니다. 그때마다 오토마톤을 다시 만들어야 하는데, 5,000개 빌드가 6ms니까 빌드 자체는 싸요. 문제는 이 오토마톤을 어디에 두고 누가 갱신하느냐입니다. 인스턴스가 여러 대면 각자 다른 오토마톤을 들고 있게 돼요.

셋째, 본문까지 검사하는 경로를 안 쟀습니다. 제 측정은 40자짜리 제목 기준이에요. 실제 코드는 content 도 봅니다. 본문이 수천 자면 M이 커지고 contains 쪽이 훨씬 불리해져요. 이 조건에서 다시 재야 판단이 정확해집니다.

바꾸는 게 맞다고 볼 조건도 정리해뒀어요.

• 키워드가 게시판당 수천 개로 늘어날 때
• 본문 전체 검색이 기본 경로가 될 때
• 공지를 배치로 몰아서 처리하는 경로가 생길 때

지금은 셋 다 아닙니다.

남은 문제도 있어요. 두 방식 모두 부분 문자열 매칭이라 오탐이 납니다. “경영학과” 를 등록한 사람은 “경영학과대학원” 공지에도 알림을 받아요. 형태소 단위로 끊거나 경계를 보는 처리가 필요한데, 이건 알고리즘을 바꾼다고 해결되지 않습니다. Aho-Corasick으로 갈아타도 똑같이 남아요.

정리하면, 이 글에서 제가 실제로 한 일은 알고리즘 교체가 아니라 교체하지 않을 근거를 만든 것입니다. 71배라는 숫자를 얻고도 안 바꾸는 게 맞다고 판단하는 데 시간이 좀 걸렸어요. 숫자가 크면 그걸 쓰고 싶어집니다.