금칙어 필터링 하기 (Feat. Redis 적용)

Situation

맡고 있는 앱 내 기능 중, 텍스트를 입력하면 AI이미지로 출력해주는 기능이 있다. 이때, 사용자가 비속어 등의 특정 단어를 쓸 경우 선정적이거나 폭력적인 이미지가 나올 수 있어, 입력값에 비속어가 있는지 판별해 필터링하는 로직을 구현해야 했다.

 

기획팀에게 받은 단어는 약 2500개였고, 받은 데이터들을 어디에 저장하는게 좋을지 고민을 하게 되었다.

그래서 생각한 것이 로컬 파일, db, redis서버 이었다.

그 중에서도 캐싱 및 공유 데이터 관리가 가장 용이하다고 들은 redis를 통해 데이터를 저장해보고자 했다.

지금까지 redis서버를 한번도 구축해본 적이 없었고, 사실 redis에 대한 개념도 제대로 잡혀 있지 않았다.

그래서 먼저 redis가 무엇인지부터 알아보았다.

 

결론적으로는 속도 등의 문제로 (아래에 설명), redis가 아닌 local에서 불러오는 식으로 구현하게 됐지만 redis를 직접 연동해본 귀한 경험이 되었다.

 

 

 

Redis란?

Key, Value 구조의 비정형 데이터를 저장하고 관리하기 위한 오픈 소스 기반의 비관계형 데이터 베이스 관리 시스템 (DBMS).

데이터베이스, 캐시, 메세지 브로커로 사용, 인메모리 데이터 구조를 가진 저장소.

 

 

Redis를 사용하는 이유

데이터베이스는 물리 디스크에 데이터를 저장해 서버 문제가 생겨도 데이터가 손실되지 않으나, 사용자가 많아질수록 부하가 생기고 느려질 수 있다. 초기나 소규모 서비스에서는 WEB-WAS-DB 구조로 충분하지만, 사용자가 늘어나면 캐시 서버가 필요하게 되며,

이때 Redis를 사용할 수 있다.

 

캐시는 한번 읽은 데이터를 임의의 공간에 저장하기에, 같은 요청이 여러 번 들어오는 경우 매번 DB를 거치는 것이 아닌, 캐시 서버에서 저장된 결괏값을 바로 내려주기 때문에 서비스의 속도가 느려지지 않는 장점이 있다.

 

• Key, Value 구조.
• String, Lists, Sets, Sorted Sets, Hashes 자료 구조 지원.
• Single Threaded.

 

Look aside cache

1. 클라이언트가 데이터를 요청 ->   웹서버는 Cache 서버에 먼저 확인

2. Cache 서버에 데이터가 있으면 Cache 서버에 있는 값을 클라이언트에게 바로 반환 (Cache Hit)

3. Cache 서버에 데이터가 없으면 DB에 데이터를 조회 -> Cache 서버에 저장하고 값을 클라이언트에게 반환 (Cache Miss)

 

Write Back 

1. 웹서버는 모든 데이터를 Cache 서버에 저장

2. Cache 서버에 특정 시간 동안 데이터가 저장됨

3. Cache 서버에 있는 데이터를 DB에 저장 -> DB에 저장된 Cache 서버의 데이터 삭제

*서버 장애 시 데이터 손실의 위험

 

 

Redis를 구축해보자

생각보다 redis를 실행하는건 간단했다.

 

ubuntu 환경을 기준으로 하게 되면,

sudo apt-get update
sudo apt-get upgrade
sudo apt-get install redis-server

//설치 후 버전확인
redis-server --version

 

mac 기준으로는 `brew install redis`를 해준 후, 아래의 명령어 두개 중 하나를 골라서 하면 됐다.

brew services start redis
redis-server --damonize yes //백그라운드 실행

실행을 한 뒤, `redis-cli ping` 명령어를 실행했을 때, 아래와 같이 응답하면 제대로 실행이 된 상태다.

 

 

다음으로 redis.conf 파일에서, Redis가 사용할 수 있는 최대 사용 메모리양을 정한다.

설정 메모리를 초과하게 됐을 때, 데이터를 어떻게 삭제할지 또한 설정한다.

sudo nano /etc/redis/redis.conf

 

설정 파일에서 maxmemory와 maxmemory-policy를 찾아서 최대 사용 메모리는 1gb, 초과할 경우 가장 오래된 데이터를 지우고 가장 최근에 저장된 데이터를 사용하는 것으로 설정한다.

maxmemory 1g
maxmemory-policy allkeys-lru

 

설정이 적용되도록 Redis를 재시작한다.

$ sudo systemctl restart redis-server.service

 

Redis의 기본포트는 6379이다. Redis가 6379 포트를 쓰고 있는지 확인한다.

$ netstat -nlpt | grep 6379

 

 

Solution

문자열에서 금칙어가 있는지 판별하는 방법 두가지 중에 고민을 하게 됐다.

첫번째 방법은 redis에 금칙어를 모두 집어넣고, 문자열을 순회하며 해당 문자열을 redis의 exists메서드를 통해 판별하는 법,

두번째 방법은 금칙어 array를 순회하며, KMP알고리즘을 적용한 메서드 안에 매개변수 값으로 해당 금칙어를 넣어 존재유무를 판별하는 법이었다.

위에서 설명한 것 처럼, redis는 캐시를 사용하기 때문에 속도 측면에서 두번째 방법보다 빠를지도 모르겠다는 생각이 들었고 두 가지 방법의 성능을 측정해봤다.

 

결과는 놀라웠다.

	redis 적용	KMP알고리즘 적용
시간 (1000자 기준) /ms	750 ~ 850	30

생각했던 것과는 달리, 1000자 기준으로 KMP알고리즘을 적용한 코드가 약 25배 차이 나는 퍼포먼스를 보여줬다.

 

 

 

 

두 방법의 코드를 분석한 결과는 다음과 같다.

	Redis 적용	KMP알고리즘 적용
알고리즘	중첩 루프를 사용한 브루트포스 방식	KMP (Knuth-Morris-Pratt) 알고리즘
기능	모든 부분 문자열을 생성하고,  각 부분 문자열이 Redis에 존재하는지 확인	주어진 문장에서 금칙어 목록과 일치하는 부분 문자열 찾음
특징	중복된 서브스트링 검사를 피하기 위해 checkedSubStrings 배열을 사용	LPS (Longest Prefix Suffix) 배열을 사용하여 패턴 내의 부분 일치를 효율적으로 관리
시간복잡도	O(n^2)	O(n+m)

 

Redis 적용 (브루트포스)

public class ForbiddenWordsFilter {
    private Jedis redis;
    
    public ForbiddenWordsChecker() {
        redis = new Jedis("localhost");
    }

    public boolean checkForbiddenWordsRedis(String sentence) {
        int length = sentence.length();
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j <= length; j++) {
                String subString = sentence.substring(i, j);
                if (redis.exists(subString))
                    return false; // 금칙어가 문장에 포함되어 있을 경우 false 반환
            }
        }
        return true; // 금칙어가 없으면 정상 리턴
    }
}

 

KMP 알고리즘 적용

public class ForbiddenWordsFilter {
    private static final List<String> forbiddenWords = List.of("word1", "word2"); // 금칙어 목록

    public boolean checkForbiddenWords(String sentence) {
        for(String word : forbiddenWords) {
            if(kmpSearch(word, sentence))
                return false; // 금칙어가 문장에 포함되어 있을 경우 false 반환
        }
        return true; // 금칙어가 문장에 포함되어 있지 않을 경우 true 반환
    }

    private boolean kmpSearch(String pattern, String text) {
        int[] lps = computeLPSArray(pattern);
        int i = 0, j = 0;
        while (i < text.length()) {
            if(pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if(j == pattern.length())
                return true; // 패턴이 일치
            if(i < text.length() && pattern.charAt(j) != text.charAt(i))
               j = (j != 0) ? lps[j - 1] : 0;
        }
        return false;
    }

    private int[] computeLPSArray(String pattern) {
        int length = 0, i = 1;
        int[] lps = new int[pattern.length()];
        while(i < pattern.length()) {
            if(pattern.charAt(i) == pattern.charAt(length)) lps[i++] = ++length;
            if (length != 0) length = lps[length - 1];
            else lps[i++] = length;
        }
        return lps;
    }
}

 

 

결과적으로 KMP 알고리즘은 패턴의 부분 일치를 활용하여 불필요한 비교를 줄이므로, 브루트포스 방식에 비해 효율적이다.

브루트포스 방식 코드는 모든 부분 문자열을 생성하고 Redis에서 확인하는 작업을 수행하므로, KMP 코드보다 더 많은 연산을 필요로 했다.

물론 브루트포스 방식이 직관적이고 구현이 간단했지만, 긴 문자열에 대해 훨씬 효율적인 KMP 알고리즘을 최종적으로 적용했다.

 

 

참고자료

문자열 필터(채팅필터)

알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘