키워드 초성 검색 기능 개선 과정

[요구 사항]

• 매칭 시 유저의 닉네임을 검색하는 기능 요구. 단, 유저의 닉네임 단어 일부를 검색하면 자동으로 키워드를 완성
• 반려견 프로필 등록 시 견종을 검색하는 기능 요구. 단, 반려견의 견종 일부를 검색하면 자동으로 키워드를 완성
  • 반려견 견종이 없는 경우에는 유저가 직접 입력하여 등록
  • 직접 입력한 데이터는 견종 데이터 자동 완성 키워드에 출력되지 않음

 

 

[기능 구현방식 선정]

구현 방식에 대해서는 세 가지 방법이 있었습니다.

1. MySQL에 데이터를 저장하고 LIKE %keyword%를 사용한 검색

2. Elastic Search를 사용한 형태소 단위 검색

3. Redis의 ZSet

 

[각 방식의 장/단점]

1. MySQL 과 LIKE 함수 활용

 

1번의 과정은 견종 데이터를 정적 테이블에 삽입하고, 조회 시에는 LIKE 쿼리를 사용하여 조회하면 방식으로 장점으로는 '원래 사용하던 MySQL을 사용하여 간편하게 구현을 할 수 있다'이나 그에 비해 Table을 Full Scan 하는 방식이기에 데이터가 점점 늘어날수록 성능이 좋지 못할 수 있겠다는 생각이 들었다.

 

2. Elastic Search를 사용한 검색 엔진 구현

Elastic Search라는 기능을 사용하여 형태소 단위로 데이터를 분리하고 토큰으로 저장하여 색인하는 쿼리를 날리는 과정을 구현해야 했다. 아직 한 번도 안 써본 기술 이기에 러닝 커브가 존재했지만 구현한다면 매우 좋은 성능을 보일 것이라 생각이 들었다.

 

3. Redis의 ZSet을 사용한 키워드 검색

Redis는 인메모리 방식으로 DISK까지 I/O작업을 수행하지 않아도 된다는 성능적인 부분에서 큰 장점이 있었다. 하지만 ZSet구조의 단점은 중간단어로 검색을 하지 못한다는 점이었다. 이 부분은 기획자 및 팀원과 이야기하여 정책적인 부분을 논의해야 했다.

 

이 당시에는 빠르게 1차 MVP 모델을 완성시키는 것을 목표로 하였기에 이전에 사용해본 경험이 있는 MySQL과 Redis 두 가지 방식 중 하나를 고려해 보기로 했고, 이 과정에서 기획자와 논의하여 중간 단어 검색을 제외한 키워드의 첫 단어를 기준으로 검색을 할 수 있는 기능을 구현하기로 했다. 그리고 중간 단어를 이용한 키워드 완성 기능은 1차 이후 모델에서 추가하는 것을 고려해 보자고 논의를 마쳤다.

 

[성능 측정]

아직 구글 앱 스토어에 배포하기 전이였고 실유저가 없기에 10만개 정도의 더미데이터를 넣고 테스트해 보았다.

또한 유저의 데이터를 DB에 저장하는 과정은 공통적으로 필요한 과정이기에 제외하였다. Redis를 사용한다 하여도 정합성의 문제를 발생시킬 수 있기 때문에 MySQL에 저장하고 Cache Miss에 대비하기 위해 필요한 과정이었다.

성능 측정은 Jmeter를 사용하였고 1000명의 유저에게 10번의 루프 카운트를 적용시켰으며 9만 개의 데이터에 대해 조회한 결과이다. 아래는 그에 대한 결과 보고서이다.

 

1. 평균 응답 시간

mySQL은 평균 18,409ms, Redis는 12,660ms로 더 빠른 성능을 보였다.

 

2. 최대 응답 시간

MySQL은 평균 33,889ms, Redis는 24,586mx으로 응답 일관성은 Redis가 더 높았다.

 

3. 95th Percentile(상위 5% 요청)

MySQL은 25,501.90 ms, Redis는 19,240.90ms로 상위 5% 요청에도 상대적으로 빨랐다.

 

아래 사진은 응답 시간 변화 그래프이다.

 

1. 결과 해석

MySQL과 Redis에서 모두 낮은 응답시간을 보였다. 하지만 시간이 지남에 따라 MySQL 응답 시간은 18,000~20,000ms에서 유지되며 상대적으로 높다.  Redis 응답 시간은 12,000~13,000 ms 수준에서 유지되며, MySQL보다 약 6초 빠른 모습을 볼 수 있었다.

 

[기능 선정]

아직 더 자세하게 Jmeter를 사용하지 못해 기본적인 성능 테스트만 사용하여 결과를 분석하여 봤지만 충분희 유의미한 결과였다. 

결론적으로 Redis를 사용한 자동단어완성 기능을 구현하기로 결정하였다. 

 

 

[기능 선정 이후의 어려웠던 점]

Redis의 ZSet과 Trie 알고리즘을 사용하여 자동완성검색 기능을 수행하며 고려해야 했던 과정들에 대해서도 함께 기록하려고 한다.

다음 내용에서는 정합성 전략 설정, ZSet에서 Trie 알고리즘을 적용하여 성능 개선, 데이터 초기화 중복 수행 방지의 내용을 담았다.

 

[어려웠던 점 1 - 데이터 정합성 전략 설정] 

유저의 닉네임 데이터와 견종 데이터에 대한 자동완성 기능을 구현 이후에 데이터에 대한 정합성 개념을 공부하고, 내 프로젝트에는 해당 전략을 고려하지 않고 구현에만 집중했구나 하는 성찰을 하게 되었다. 그래서 Redis의 캐시 미스를 대비하기 위한 레디스의 정합성 전략들에 대해 공부하였고, 내 프로젝트에 적절한 전략을 적용하기로 하였다.

 

그 과정에서 유저의 닉네임 데이터와 견종 데이터는 유사한 전략을 사용하지만 약간의 다른 로직이 필요했다. 우선 견종 데이터를 다뤄보려고 한다. 

 

1.  정합성 전략

우선 견종 데이터는 한번 등록해 두면 크게 수정할 일이 없기 때문에 쓰기에 대한 작업보다 읽기에 대한 작업이 위주로 이어졌다. 그래서 견종 대한 정보를 최초에 DB에 저장(write Around)하고 애플리케이션 초기화 단계에서 MySQL의 데이터를 Redis에서 가져와 저장하고 조회하는 방식을 사용했다. 이 방식을 통해 데이터는 MySQL에 저장되어 Redis의 휘발성문제를 해결할 수 있고, MySQL의 데이터를 최신화시키면 Cache Miss가 발생할 일도 없었다.

또한 초기화 시에 중복적으로 Redis에 데이터를 저장할 수 있는 문제를 방지하기 위해 이미 초기화가 되어 있는 상태인지 확인하는 메서드를 먼저 수행하도록 구현했다.

@PostConstruct
    public void init() {    // 이 Service Bean이 생성된 이후에 검색어 자동 완성 기능을 위한 데이터들을 Redis에 저장 (Redis는 인메모리 DB라 휘발성을 띄기 때문)
        if (redisSortedSetService.isinitializedDogBrreds()) {
            log.info("Redis already contains autocomplete data. Skipping initialization.");
            return;
        }
        
        List<String> dogBreedList = dogRepository.findAllBreedData();
        
        log.info("Breed data size: {}", dogBreedList.size());
        
        saveAllSubstring(dogBreedList);
    }

 

2. 유저 데이터의 정합성 전략

정적인 데이터인 견종 데이터와는 달리 유저 데이터는 새로운 유저 또는 유저의 닉네임 수정 시 해당 데이터를 중간중간 업데이트해야 했다. 유저의 이전 정보를 들고 있으면 안 되기 때문에 새로운 유저가 프로필을 등록하거나 기존 유저가 닉네임을 변경하는 경우 DB의 데이터를 수정하고 Redis에서 음절을 분리한 키워드를 저장하는 로직을 한 번 수행시켜야 했다. 이 과정에서 DB에 쓰기, Redis에서는 쓰기 및 읽기가 진행되었다. Redis에만 데이터를 저장하고 이후 유저가 활동을 하지 않는 새벽에 Batch를 수행하여 데이터를 최신화시킬까도 고민했지만 Redis서버에 어떤 문제가 생길지 모르기 때문에 기존의 방법을 선택했다. 왜냐하면 Redis에 해당 서비스뿐만 아니라 채팅에 관련된 데이터들이 저장되기도 하며 프리티어를 사용 중이기 때문에 얼마든지 부하의 위험이 발생할 수 있다고 생각했기 때문이다.(이 또한 부하테스트를 거친 후 서비스 안정성을 고려할 예정이다)

만약 서비스를 사용하는 유저가 많아지고 성능에 저하가 발생한다면 해당 전략을 변경하고자 한다.

@PostConstruct
public void init() {   
    if (redisSortedSetService.isInitializedUserNickname()) {
        log.info("Redis already contains autocomplete data. Skipping initialization.");
        return;
    }
    List<String> nicknames = userRepository.findAllNicknames();
    
    log.info("size={}", nicknames.size());
    
    saveAllSubstring(nicknames);

}

private void saveAllSubstring(List<String> userNickName) { 

    for (String name : userNickName) {
        redisSortedSetService.addToSortedSetFromMate(name + suffix);   //완벽한 형태의 단어일 경우에는 *을 붙여 구분

        for (int i = name.length(); i > 0; --i) { 
        
            redisSortedSetService.addToSortedSetFromMate(name.substring(0, i));
        }
    }
}

 

[어려웠던 점 2 - ZSet과 Trie자료구조 성능 비교]

이전에 수행했던 Jmeter 수행 결과를 보니  ZSet의 성능이 지연되면 최대 19초까지 지연된다는 점에서 사용자가 몰리게 될 경우 경험에 불편함을 느낄 수도 있다고 생각하여 다른 방법이 없는지 찾아보았다.

그 과정에서 ZSet은 score를 사용하여 순위를 매기고 인기 있는 키워드들을 추출할 수 있는데 특화되었으며 시간 복잡도가 O(logN+K)을 갖는다는 것을 알 수 있었다. 하지만 그에 비해서 Trie알고리즘은 O(N)의 시간 복잡도를 가지며 더 빠른 성능을 낼 수 있으며 키워드자동완성 검색기능에 더 특화되어 있음을 알 수 있었다. 그 외에도 Trie알고리즘을 쓰면 데이터를 Redis에 저장할 필요가 없으므로 추가적인 I/O작업을 하지 않아도 된다는 장점이 있었다.

아래는 표로 정리한 두 구조의 장단점이다.

Trie VS ZSET

	Trie	ZSet
시간 복잡도	삽입: O(n) / 검색: O(n)	삽입: O(log N) / 검색: O(log N + k)
공간 복잡도	공통 접두사 노드를 공유해 효율적이다	모든 문자열을 별도로 저장해 공간이 더 필요하다
기능	접두사 검색에 특화	정렬 및 빈도 기반 추천이 가능하다
적용 사례	빠른 접두사 검색, 자동완성	빈도 기반 추천 및 정렬된 검색 결과

 

다음은 다시 한번 성능을 전체적으로 측정해 보았다. 각각 1만 번의 요청을 기준으로 9만 개의 데이터를 조회하여 검색하였다. 

1. 평균값, 상위 5% 요청

Trie 알고리즘 > Redis 키워드 검색 > mySQL 키워드 검색 순으로 더 높은 성능을 보였다.

 

2. 트랜잭션

redis > Trie > mySQL 순으로 redis와 Trie가 유사한 속도를 보였고 mySQL이 가장 느렸다.

 

3. 수신

redis > Trie > mySQL 순으로 redis가 압도적으로 빠른 속도를 보여줬지만 Trie는 노드 경로와 검색 결과를 함께 처리하기 때문에 네트워크 사용량이 높아진다는 특징이 있다.

 

다음은 응답률이다. 다른 그래프에 Trie는  월등히 안정적이고 빠른 응답속도를 보여주고 있다.

 

결론적으로 메모리 비용은 더 소모하지만 사용자입장에서 더 빠른 응답을 반환해 줄 수 있는 Trie구조로 변경하기로 하였다.

 

[결론]

Trie 알고리즘을 사용하여 평균 검색속도 18.85초에서 7.02초로 약 11초를 단축시키는 성능 개선을 가져왔다.

현재는 모든 결괏값을 반환하는 시간을 측정하여 결괏값들이 높게 나왔지만 5개~10개 이내의 결과를 가져오는 조건을 걸면 더 빠른 속도의 결괏값도 반환이 가능할 것이다.

이후에는 Trie알고리즘보다 더 효율적인 방법이 없는지 성능적으로 고민해보려 한다.