<Spring> Redis 기반 검색어 자동 완성 기능 구현하기

📌 도입 배경

All:Chive 서비스에 태그, 아카이빙 제목을 바탕으로 검색하는 부분이 있다.

네이버나 구글 등에서 검색할 때, 검색어의 일부분을 입력할 경우, 제안된 검색어 목록이 실시간으로 나타나는 자동 완성 기능이 있다.

All:Chive 서비스에도 이를 도입하고 싶었다.

그래서 시작했다.

 

📌 DB 선택

이 서비스를 구현함에 있어서 색인(?) 관련 데이터를 저장해야 했다.

나는 총 3개의 DB를 고려했다.

아래는 내가 왜 이 DB를 선택 혹은 선택하지 않은 이유이다.

 

🔵 Elastic Search

데이터 저장, 검색에 있어서 뛰어난 성능을 가지고 있다고 알려진 DB이다.

이것을 사용하기 위해선 새로운 시스템을 도입해야 했다.

프로젝트를 진행하는 서버 개발자가 1명인 상황에서, 관리 포인트를 하나 늘리는 것이 부담스럽게 다가왔다.

또한 내가 생각했던 로직으로 구현할 수 있을 것 같았다.

 

Elastic Search를 이용하면 훨씬 안정적으로 작동할 수 있을 것이다.

하지만 내 손으로 직접 구현하고 싶었다.

이에 나는 Elastic Search를 사용하지 않았다.

 

🔵 MySQL

이미 서비스 DB로 MySQL을 사용하고 있는 상황이었다.

이에 추가적인 시스템 도입이 필요 없었다.

하지만 나는 이를 선택하지 않았다.

이유는 속도 때문이다.

 

우리는 검색어 자동 완성 서비스를 네이버, 구글에서 흔히 볼 수 있다.

우리가 글자를 타이핑하는 와중에도 값이 빠르게 바뀌는 것을 볼 수 있다.

빠르게 자동 완성 데이터를 제공해 주는 것이다.

이처럼 많은 데이터에 있어서 빠른 조회를 제공하는 것이 중요했다.

이 부분에 있어서 RDB 보다 인메모리 DB가 더 빠른 조회 성능을 가진다.

그러므로 RDB를 사용하지 않았다.

 

🔵 Redis

Redis 또한 서비스에서 사용하고 있었기에, 추가적인 시스템 도입에 대한 우려가 없었다.

인메모리 DB로 RDB보다 더 빠른 조회 성능을 가진다.

또한 자료구조를 선택하여 정렬된 상태로 자료가 저장되도록 할 수 있었다.

이에 Redis를 이용하기로 했다.

 

📌 Redis 기반 검색어 자동 완성 기능

🔵 이용한 원리

ball과 bear라는 데이터가 있다고 하자

b를 검색했을 때는 두 단어 모두가 검색되고, ba를 검색했을 때는 ball만 검색되어야 한다.

이를 어떻게 구현해야 할까?

 

DFS 알고리즘을 통해 어떤 문제에 대한 경우의 수를 구할 수 있다.

이 경우 부모 노드의 값을 누적하여 자식 노드에서 이 값을 이용한다.

위와 같은 방식을 trie에 적용하고, 모든 노드에서 부모 노드와 자신의 값을 합쳐서 출력하도록 하면 어떤 결과가 나올까?

위와 같은 트리가 있을 때, 결과는 아래와 같다. (오름차순 순회 기준)

a

ab

aba

abc

ad

b

ba

bad

bag

이때, trie의 부모 노드와 자식 노드 간 특성을 고려해 보자.

trie의 자식 노드는 리프 노드부터 부모 노드까지의 단어를 접두어로 사용하는 단어이다.

즉, 위 결과 값에서 부모 노드가 자식 노드보다 앞에 출력되므로, 특정 단어가 존재할 때, 이 단어는 뒤에 위치한 단어와 비슷한 단어라고 할 수 있다.

그러므로 이러한 점을 이용하여 단어를 추출하고자 했다.

이러한 점을 이용하여 구현하고자 했다.

 

기능 구현은 크게 두 부분으로 나뉜다.

1. 검색어 자동 완성 데이터 저장
2. 검색어 자동 완성 데이터 불러오기

아래는 이에 대한 자세한 설명이다.

 

🔵 검색어 자동 완성 데이터 저장

저장은 Redis의 Sorted Set을 이용했다.

Sorted Set은 key, member, score로 구성된다.

이때, score 순으로 정렬되며, score가 같은 경우 member로 정렬된다.

그러므로 score를 동일하게 한 상태에서 단어를 저장할 경우, 자동적으로 중복 없이 사전순으로 배치가 된다.

이 점을 데이터 저장과 조회에 이용했다.

 

데이터 저장은 삭제 -> 새로운 데이터 저장 순서로 진행된다.

데이터 저장에 있어서 새로운 데이터가 생겼을 때, 즉시 데이터를 업로드하는 것이 아니라 스케줄러로 작업을 처리했다.

검색어 자동 완성 데이터의 경우 실시간으로 제공되는 데이터가 필요 없다고 생각했기 때문이다.

실시간성을 보장하기 위해 시스템에 부하를 늘리는 방법보단, 시스템을 안정적으로 운영하는 것에 초점을 맞췄다.

그래서 이 작업에는 스케줄러 cron 잡을 이용 했다.

 

1. 기존 데이터 삭제

우선 Key 값을 이용해 기존 데이터를 삭제한다.

 

2. 새로운 데이터 저장

검색어의 특성상, 입력값이 완벽한 단어가 아닐 가능성이 높다.

그럼에도 불구하고 그에 비슷한 단어를 반환해줘야 하므로, 앞서 설명한 아이디어를 이용했다.

단어를 처음부터 글자 하나씩 늘려가며 저장한다.

ball의 경우, b ba bal ball 순으로 저장한다는 말이다.

이때, 완벽한 단어 ball, bear의 경우 맨 뒤에 *를 붙여서 저장한다.

아래는 bear, ball 두 단어가 저장된 형태이다

b
ba
bal
ball*
be
bea
bear*

Sorted Set 이므로 중복된 b는 한 번만 저장되고, 다른 단어들은 정렬되어 저장된다.

 

이를 모든 과정을 코드로 구현하면 아래와 같다.

@UseCase
@Slf4j
@RequiredArgsConstructor
public class RenewalSearchDataUseCase {
    private final ArchivingAdaptor archivingAdaptor;
    private final TagAdaptor tagAdaptor;
    private final RedisTemplate<String, String> redisTemplate;

    @Scheduled(cron = "0 0 3 * * *")
    @Transactional(readOnly = true)
    public void executeSchedule() {
        log.info("renewal title scheduler on");
        renewalData();
        log.info("renewal title scheduler off");
    }
    
    private void renewalData() {
        redisTemplate.delete(SEARCH_KEY);
        renewalArchiving();
        renewalTag();
    }

    private void renewalTag() {
        Set<Tag> tags = new HashSet<>(tagAdaptor.findAll());
        tags.forEach(
                tag -> {
                    redisTemplate.opsForZSet().add(SEARCH_KEY, tag.getName().trim() + ASTERISK, 0);
                    for (int index = 0; index <= tag.getName().length(); index++) {
                        redisTemplate
                                .opsForZSet()
                                .add(SEARCH_KEY, tag.getName().trim().substring(0, index), 0);
                    }
                });
    }

    private void renewalArchiving() {
        Set<Archiving> archivings =
                new HashSet<>(archivingAdaptor.findAllByPublicStatus(Boolean.TRUE));
        archivings.forEach(
                archiving -> {
                    redisTemplate
                            .opsForZSet()
                            .add(SEARCH_KEY, archiving.getTitle().trim() + ASTERISK, 0);
                    for (int index = 0; index <= archiving.getTitle().length(); index++) {
                        redisTemplate
                                .opsForZSet()
                                .add(
                                        SEARCH_KEY,
                                        archiving.getTitle().trim().substring(0, index),
                                        0);
                    }
                });
    }
}

 

🔵 검색어 자동 완성 데이터 불러오기

위에서 저장한 값을 이용해 데이터를 가져와 클라이언트로 반환해 주는 과정이다.

특정 단어 이후에 위치한 단어 중 완성된 단어를 가져오면 이를 수행할 수 있다.

여기서 가장 중요한 과정은 rank()를 이용해 입력값과 가장 비슷 혹은 같은 글자의 Index를 구하는 것이다.

이 index 값 뒤에 있는 값은 해당 단어와 유사도가 높은 단어들이다.

그러므로 해당 단어 뒤에서 값을 자동 완성 데이터로 사용할 수 있다.

이에 아래와 같은 방식을 구현했다.

 

1. 입력 값과 가장 비슷한 혹은 같은 글자의 Sorted Set 내에서의 Index 값을 구한다.

rank() 함수를 통해 입력값과 유사한 값의 index를 가져온다

 

2. Index ~ Index + 100에 해당하는 단어를 가져온다.

최대 5개이지만 왜 여러 글자를 가져올까?

앞에서 데이터를 저장한 형식을 보자.

한 단어를 잘라서 저장했다. 

그러므로 5개만 가져올 경우, 그 5개의 단어에 완벽한 단어가 없을 수 있다.

그러므로 100개의 데이터를 가져오도록 했다.

 

저장할 데이터의 최대 길이가 20이었다.

데이터 저장 시 최악의 경우는 데이터 간 서로 연관이 없는 경우이다.

단어 5개를 저장했을 때. 위와 같은 상황이 벌어질 경우, 저장된 데이터는 5 * 20개 즉, 100개이다.

그러므로 100개를 조회했을 때, 5개의 데이터를 조회할 수 있다는 점이 보장된다.

그래서 100개의 데이터를 조회했다.

 

3. 완벽한 단어를 최대 5개 필터링한다.

데이터를 저장할 때, 완벽한 단어의 경우 *를 뒤에 붙여서 저장했다.

그러므로 가져온 데이터 중 *이 붙은 단어 5개만 추려내면 된다.

 

아래는 이를 구현한 코드이다.

@UseCase
@RequiredArgsConstructor
public class GetRelativeSearchListUseCase {
    private final RedisTemplate<String, String> redisTemplate;

    @Transactional
    public SearchListResponse execute(String word) {
        validateExecution(word);
        ZSetOperations<String, String> zSetOperations = redisTemplate.opsForZSet();
        List<String> autoCompleteList = new ArrayList<>();
        Long rank = zSetOperations.rank(SEARCH_KEY, word);
        if (rank != null) {
            Set<String> rangeList = zSetOperations.range(SEARCH_KEY, rank, rank + 100);
            autoCompleteList = getAutoCompleteList(rangeList, word);
        }
        return SearchListResponse.from(autoCompleteList);
    }

    private void validateExecution(String word) {
        StringParamUtil.checkEmptyString(word);
    }

    private List<String> getAutoCompleteList(Set<String> rangeList, String keyword) {
        return rangeList.stream()
                .filter(value -> value.endsWith(ASTERISK) && value.startsWith(keyword))
                .map(value -> StringUtils.removeEnd(value, ASTERISK))
                .limit(5)
                .toList();
    }
}

 

이러한 방식으로 Redis를 이용해 검색어 자동 완성 기능을 구현할 수 있었다.

 

📌 마무리

이 구현에 있어서 몇 가지 한계점이 존재한다.

1. 키 하나에 많은 수의 데이터가 저장된다.
   키 하나에 많은 데이터가 저장된다면, 데이터 조회 성능이 떨어진다.
   'a'를 검색했을 때, 'b'로 시작하는 데이터를 볼 필요 없으므로, 알파벳 첫 글자로 키를 분리한다면 더 효율적이지 않을까 생각한다.
2. 서비스를 제공하지 못하는 순간이 존재한다.
   삭제된 데이터를 검색어에서 지우기 위해선 전체 리뉴얼이 필요하다
   하지만 데이터 양이 많았지만, 데이터 리뉴얼에 시간이 많이 소요될 것이고, 이는 서비스 제공 불가능 시간이 길어짐을 의미한다.
3. 수많은 쿼리가 발생한다.
   싱글 스레드이므로 많은 수의 쿼리가 발생하면, 결국 쿼리들 때문에 시스템의 부하가 발생할 수 있을 것이다.
   bulk 작업으로 대체해도 될 것이라 생각한다.
4. 서로 연관성이 떨어지는 답이 나온다.
   데이터 양이 적다면, ba를 검색했을 때 결과 값으로 cat이 나올 수 있다.

이러한 점에 있어서 개선이 필요할 것이라 생각한다.

 

📌 서비스 개선

이전에 언급했던 한계점을 개선해 봤다.

@UseCase
@Slf4j
@RequiredArgsConstructor
public class RenewalSearchDataUseCase {
    private final ArchivingAdaptor archivingAdaptor;
    private final TagAdaptor tagAdaptor;
    private final RedisTemplate<String, String> redisTemplate;

    @Scheduled(cron = "0 0 3 * * *")
    @Transactional(readOnly = true)
    public void executeSchedule() {
        log.info("renewal title scheduler on");
        renewalData();
        log.info("renewal title scheduler off");
    }

    @Transactional(readOnly = true)
    public void executeForce() {
        renewalData();
    }

    private void renewalData() {
        delete();
        renewalArchiving();
        renewalTag();
    }

    private void delete() {
        redisTemplate.executePipelined((RedisCallback<Object>)
                redisConnection -> {
                    for (char c = 'A'; c <= 'Z'; c++) {
                        String key = SEARCH_KEY + c;
                        redisConnection.del(key.getBytes());
                    }

                    for (int index = 0; index < 19; index++) {
                        String key = SEARCH_KEY + KOREAN_ALPHA[index];
                        redisConnection.del(key.getBytes());
                    }

                    for (int index = 0; index < 9; index++) {
                        String key = SEARCH_KEY + index;
                        redisConnection.del(key.getBytes());
                    }

                    redisConnection.del((SEARCH_KEY + '?').getBytes());
                    return null;
                });
    }

    private void renewalTag() {
        int pageNum = 0;
        while (true) {
            PageRequest pageRequest = PageRequest.of(pageNum, BULK_SIZE);
            Slice<Tag> slicedTags = tagAdaptor.querySliceTag(pageRequest);
            Set<Tag> tags = new HashSet<>(slicedTags.getContent());
            redisTemplate.executePipelined(
                    (RedisCallback<Object>)
                            redisConnection -> {
                                tags.forEach(
                                       tag -> {
                                            String key;
                                            if (StringUtil.isKorean(
                                                    tag.getName().trim().charAt(0))) {
                                                key = SEARCH_KEY + StringUtil.extractKoreanInitial(
                                                                tag.getName()
                                                                        .trim()
                                                                        .charAt(0));
                                            } else {
                                                key = SEARCH_KEY + tag.getName()
                                                                .trim()
                                                                .toUpperCase()
                                                                .charAt(0);
                                            }
                                            redisConnection.zSetCommands()
                                                    .zAdd(key.getBytes(),
                                                            0,
                                                            (tag.getName().trim() + ASTERISK).getBytes());
                                            for (int index = 0; index <= tag.getName().length(); index++) {
                                                redisConnection.zSetCommands()
                                                        .zAdd(key.getBytes(),
                                                                0,
                                                                tag.getName()
                                                                        .trim()
                                                                        .substring(0, index)
                                                                        .getBytes());
                                            }
                                        });
                                return null;
                            });

            if (!slicedTags.hasNext()) {
                break;
            }
            pageNum++;
        }
    }

    private void renewalArchiving() {
        int pageNum = 0;
        while (true) {
            PageRequest pageRequest = PageRequest.of(pageNum, BULK_SIZE);
            Slice<Archiving> slicedArchivings =
                    archivingAdaptor.querySliceArchivingByPublicStatus(pageRequest, true);
            Set<Archiving> archivings = new HashSet<>(slicedArchivings.getContent());
            redisTemplate.executePipelined(
                    (RedisCallback<Object>)
                            redisConnection -> {
                                archivings.forEach(
                                        archiving -> {
                                            String key;
                                            if (StringUtil.isKorean(
                                                    archiving.getTitle().trim().charAt(0))) {
                                                key = SEARCH_KEY + StringUtil.extractKoreanInitial(
                                                                archiving.getTitle()
                                                                        .trim()
                                                                        .charAt(0));
                                            } else {
                                                key = SEARCH_KEY + archiving.getTitle()
                                                                .trim()
                                                                .toUpperCase()
                                                                .charAt(0);
                                            }
                                            redisConnection.zSetCommands()
                                                    .zAdd(key.getBytes(),
                                                            0,
                                                            (archiving.getTitle().trim() + ASTERISK).getBytes());
                                            for (int index = 0; index <= archiving.getTitle().length(); index++) {
                                                redisConnection.zSetCommands()
                                                        .zAdd(key.getBytes(),
                                                                0,
                                                                archiving.getTitle()
                                                                        .trim()
                                                                        .substring(0, index)
                                                                        .getBytes());
                                            }
                                        });
                                return null;
                            });

            if (!slicedArchivings.hasNext()) {
                break;
            }
            pageNum++;
        }
    }
}

 

1번은 위에서 설명한 내용을 구현했다.

key + 첫 글자를 키로 하여 저장했다.

한글의 경우 '가'라는 단어를 사용하는 것이 아니라 'ㄱ'를 키에 사용하도록 했다.

이렇게 구성하더라도 한 키에 집중될 가능성이 존재한다.

하지만 모든 글자를 한 키에 넣는 것보단 덜 집중될 것이다.

또한 이를 통해 4번을 개선할 수 있었다.

단어의 앞 글자를 기준으로 저장, 조회하므로, 앞서 설명한 상황은 발생하지 않는다.

하지만 문제를 완벽히 해결된 것은 아니다.

b... 를 검색했을 때 c... 가 안 나올 뿐, ba... 를 검색했을 때, bz... 가 여전히 검색될 수 있다.

 

3번의 경우 redis pipeline을 이용했다.

pipeline은 많은 요청을 한 번에 보낼 수 있는 방법이다.

현재 개선한 방식은 데이터를 불러올 때 100개씩 불러와서 요청 100개를 만들어 보내는 방식이다.

이때 pipeline을 이용함으로써 100개의 요청을 1번으로 처리할 수 있게 되었다.

 

위를 통해 2번을 개선할 수 있었다.

아래는 개선 전과 후의 데이터 리뉴얼 처리 시간이다.

로컬 환경에서 도커로 DB를 띄워서, archiving과 tag 데이터 row의 총합에 따라 로직 처리 시간을 비교해 봤다.

rows	200	4000	9000
이전 코드	318ms	5479ms	11684ms
개선안	287ms	1912ms	3784ms

row 수가 많아질수록 작업 속도 차이가 커졌다.

많은 데이터에 빠르게 대응할 수 있도록 개선했다.

하지만 여전히 서비스가 중단되는 것을 막을 순 없었다.

 

실제 운영 중인 서비스의 강제 데이터 리뉴얼 시 시간을 측정해 봤다.

다음과 같은 개선을 보였다.

동시성 처리 없이 1개의 스레드가 100개의 요청을 보내도록 했다.

882ms에서 105ms로 줄었다. 

로컬 디비와는 달리, DB I/O 시간이 더 걸리는 서버의 특성이 반영된 것 같다. 

I/O 횟수를 줄임으로써 시간을 대폭 줄일 수 있었다.