문자열 탐색 성능 개선

필자는 웹메일 업체에서 스팸 차단 솔루션 개발을 담당하고 있다.

스팸 차단 솔루션의 특성상 관리자/사용자가 등록한 필터들을 활용한 많은 문자열 탐색이 일어난다.

이 기능을 개선하면 솔루션의 성능이 크게 향상될 것이라고 판단하여 진행하게 되었다.

 

우선 결론부터 말하자면 패턴 매칭의 성능 개선은 진행되지 못하였다.

허나 누군가가 나와 같은 고민을 하고 있을 경우 도움을 받을 수 있도록, 또 나와 같은 실수를 하지 않도록 하기 위해 기록하고자 한다.

---

시작 - 어떻게 개선하려 하였는가?

우선 회사에서 열심히 놀고 있는 도중 우아한형제 블로그의 아래 글을 보게 되었다.

https://techblog.woowahan.com/15764

고르곤졸라는 되지만 고르곤 졸라는 안 돼! 배달의민족에서 금칙어를 관리하는 방법 | 우아한형

 

배민에서 금칙어 시스템을 어떻게 개선했는지에 대한 이야기였는데 그중 금칙어 찾아내기 부분의 내용을 보다 흠칫했다.

 

 

현재 우리 솔루션에서는 문자열 탐색은 String.contains(== String.indexOf)를 통하여 진행하고 있었고 성능이 좋지 않다는 것도 이미 알고 있었다.

따라서 배민에서 진행한 내용을 참고하여 아호코라식 알고리즘을 적용해 개선하고자 하였다.

---

1차 시도 - 아호코라식 알고리즘

아호코라식 알고리즘이란?

존재 여부를 확인할 문자열(이하 패턴)들을 Trie로 만들어둔 후

검사 대상 문자열(이하 원문)이 Trie를 따라가며 일치, 불일치 여부를 확인하는 것이다.

출처 : https://techblog.woowahan.com/15764

 

기존 패턴 매칭의 경우 패턴 하나당 한 번씩 원문과 매칭을 진행하므로 시간복잡도가 O(m(n1+n2+n3...))이다.

반면 아호코라식으로 진행할 경우 원문을 생성해 둔 Trie에 한 번만 대입하면 되므로 O(m+n1+n2+n3...)이 된다.

 

마침 자바에 아호코라식 라이브러리가 존재하여 이를 활용하였고

본문의 길이가 21397자인 메일 원문을 기준으로 100개의 문자열을 포함여부에 대해 테스트해 보았다.

 

기존(String contains)

 

 

아호코라식

 

기존의 방식은 36ms가 소요되었고 아호코라식을 활용할 경우 5ms가 소요되어 약 7배의 정도 성능이 더 좋았다.

 

---

여기까지 테스트하고 이제 적용하려 하였으나......

기존에 자주 논의되었던 복합 조건 필터 기능이 갑자기 프로젝트에서 필수 지원 기능으로 포함되어 성능 개선보다 우선적으로 작업하게 되었다...

 

복합 조건 필터 작업의 내용은 아래와 같다.

 

작업 전
각 필터당 하나의 조건으로 문자열 검사 진행 - 하나의 조건만 충족되면 해당 필터에 매칭
ex) 1번 조건(제목에 Test가 포함되는 경우) => 차단

작업 후
각 필터 당 여러 개의 조건으로 문자열 검사 진행 - 필터에 있는 모든 조건이 충족해야 해당 필터에 매칭
ex) 1번 조건(제목에 Test가 포함되는 경우), 2번 조건(아이디가 potwings로 시작되는 경우) => 1, 2번 모두 충족해야 차단

 

이전의 구조에서는 필터 하나에 조건이 하나 있어, 메일이 하나의 조건에만 충족할 경우 해당 조건을 가지고 있는 필터에 탐지된 것으로 처리하면 되었다.

따라서 "특정 문자를 포함하면"인 조건들로만 Trie를 생성하면 되었다.

허나 변경된 구조에서는 필터 하나에 여러 개의 조건이 있어, 특정 조건에 부합하는 경우에만 그다음 조건을 검사해야 한다.

 

예시를 통하여 설명해 보자, 아래와 같이 세 가지 조건을 가진 필터가 있다고 생각해 보자

1. 제목에 "subject"를 포함
2. 아이디에 "test"와 일치
3. 본문 "naver.com"을 포함

 

우선 제목에 대한 패턴들로 만들어 Trie를 통하여 1번 조건에 충족되었다 하자

그럼 그 후 2번 조건에 의해 아이디에 대해서는 test와 일치하는지 확인해야 하고 그다음 3번 조건으로 확인해야 한다.

따라서 본문 "naver.com"을 포함 조건은 1번, 2번 조건을 충족하는 경우에만 확인을 진행해야 하므로 Trie에 포함시킬 수 없다.

 

1번 조건들로만 Trie를 생성하면 어떨까? 도 생각하였으나.

1번 조건에 "포함하면"이 아닌 다른 조건들이 오는 경우가 많아 효율적이지 못하다 판단해 진행하지 않았다.

 

위와 같은 이유들로 인해 아호코라식을 적용할 수 없게 되었다.

 

---

2차 시도 - KMP 알고리즘

진행해야 하는 작업이 일대다 패턴 매칭이라 아호코라식보다는 성능이 좋지는 않으나

KMP 알고리즘을 활용하면 일대일 매칭에서 String의 contains(브루트 포스)보다는 성능이 좋다 하여 고려해 보았다.

KMP 알고리즘이란?

문자열 비교 시 효율적인 인덱스 조정을 통해 이미 비교했던 문자열을 최대한 다시 비교하지 않도록 하여 성능을 개선한 문자열 탐색 알고리즘이다.

 

KMP 알고리즘의 자세한 내용은 아래 글에 따로 정리해 두었다.

https://potwings.tistory.com/65

KMP - 문자열 탐색 알고리즘 (By Java)

 

KMP 알고리즘은 자체의 index 조절 방식을 통하여 비교를 횟수를 줄이기 때문에 성능이 더 좋을 것이라 예상하였다.

허나 테스트 결과는 예상과 달리 String contains의 성능이 더 좋았다.

 

String contains보다 수행 시간이 무려 10배나 늘어났다.

 

왜 그럴까?

1. 혹시 String의 contains는 브루트 포스가 아닌 성능이 더 좋은 방식을 사용할까?

 

아니다 String의 contains(== indexOf)는 브루트포스 방식으로 비교하고 있었다.

// 브루트포스 방식으로 비교 진행중
public static int indexOf(byte[] value // 검사 대상 , int valueCount, byte[] str // 패턴, int strCount, int fromIndex) {
    byte first = str[0]; // 패턴의 처음 문자
    int max = (valueCount - strCount); // 둘의 길이 차이의 최대
    for (int i = fromIndex; i <= max; i++) {
        // Look for first character.
        if (value[i] != first) { // 패턴의 처음 문자와 일치하지 않는 경우 일치하는 문자가 나올 때까지 skip
            while (++i <= max && value[i] != first); 
        }
        // 패턴의 처음 문자를 찾을 경우 다음 매칭 진행
        if (i <= max) {
            int j = i + 1; // 패턴의 두번째 문자부터 비교 진행
            int end = j + strCount - 1; // 패턴과 비교해야하는 부분 문자열 마지막 인덱스
            for (int k = 1; j < end && value[j] == str[k]; j++, k++); // j,k를 증가시키며 비교 진행 불일치하면 중단
            if (j == end) {
                // 위의 반복문에서 패턴의 끝까지 비교가 완료되었을 경우 시작 인덱스 반환
                return i;
            }
            // 만일 도중에 불일치 발생했을 경우 다시 i를 증가시키며 비교 진행
        }
    }
    return -1;
}

 

 

2. KMP 알고리즘은 존재 여부만 판단할 경우 오히려 성능이 안 좋다.

 

만일 존재 여부만 판단하면 전체 문자열을 확인할 필요 없이 문자열 일치가 발생하면 탐색을 중단하면 된다.

허나 KMP의 경우 탐색을 진행하기 전 전체 문자열을 확인하여 lps 배열을 생성한다.

이때 불필요한 작업이 발생하기 때문에 오히려 contains보다 성능이 저하되는 것이었다.

 

허나 여기서 이상한 점이 있었다.

원문이 패턴을 포함하고 있지 않은 경우 전체 탐색을 진행하므로 KMP가 성능이 더 좋아야 하는데도 성능이 contains보다 떨어지는 경우가 발생하였다.

그래서 원인을 더 찾아봤는데...

 

3. JIT 컴파일러가 String의 indexOf의 성능을 향상시켜준다.

 

JIT(Just-In Time Compiler) 컴파일러란?

초기의 자바는 모든 바이트 코드를 실행 전 직접 기계어로 번역 후 실행해 성능이 떨어졌다.

이를 개선하기 위해 JIT 컴파일러가 등장하였고, 자주 쓰이는 메소드는 바이트 코드를 번역해 실행하는 것이 아닌 기계어로 캐싱해 둔 코드를 실행하여 성능을 개선하였다.

 

String의 contains에서 사용하는 indexOf는 여러 메소드에서도 이미 불러와 사용하고 있는 상태였고, 그로 인하여 JIT 컴파일러에 등록되어 있어 더 좋은 성능으로 실행될 수 있었던 것이다.

 

---

마치며

비록 이번에는 성능 개선을 이루지는 못했지만, 생각으로만 가지고 있던 "좋은 알고리즘을 활용하여 성능을 이렇게 개선할 수 있겠다"는 것을 직접 시도해 볼 수 있는 좋은 경험이었다.

향후 다른 기능에 적절한 알고리즘을 접목시킬 기회가 있다면, 확실한 결과물을 남길 수 있기를 기대한다.

 

추가로 글로 작성해 보니 작업할 땐 미처 생각하지 못했던 부분들에 대해 고려해 볼 수 있어 좀 더 많은 것들을 공부할 수 있었다. 앞으로도 꾸준히 기록하는 습관을 가져야겠다.