[Redis] Redis Sorted Set을 활용하여 랭킹 기능 구현하기

들어가며

현재 사이드 프로젝트 겸 플레이 그라운드 프로젝트에 랭킹 기능을 도입하려고 합니다. 해당 랭킹 기능은 미션 별 step 내림차순입니다.

위 기능을 구현하는 도중 레디스의 Sorted-Set 자료구조를 이용하면 key-value 중복 제거 기능으로 간편하게 구현할 수 있으며, 조회 성능은 폭발적으로 증가시킬 수 있을 것 같았습니다.

참고로 미리 구현한 기능의 응답 시간입니다. 유저 한 명의 요청을 처리하는 데 389ms의 시간이 걸리는 상황입니다.

Redis Sorted Set(Zset)

레디스는 다양한 형태의 자료 구조를 제공합니다. 기본적으로 key-value 형태의 구조를 띄며, value가 사용하는 자료 구조에 따라 기능을 사용할 수 있습니다.

Sorted Set은 이름에서 알 수 있듯이 중복되지 않은 데이터를 가지는 Collection입니다. 가중치(Score)를 가지고 있기 때문에 해당 가중치에 따라 정렬된 순서로 저장합니다. 만약 score 값이 중복되면 value의 사전 순으로 정렬합니다.

Sorted Set을 최적화하기 위한 자료구조

결론부터 이야기 하자면, 레디스의 Sorted Set은 Skip List라는 자료구조로 구현되어 있습니다. Skip List라는 자료구조는 꽤나 생소하게 느껴질 수 있는데, Linked List에서 파생된 자료구조입니다.

그럼 레디스는 왜 Skip List를 사용하는걸까요? Skip List는 Linked List에서 조회 성능을 높히기 위한 목적으로 만들어진 자료구조입니다. Linked List는 다음 노드의 주소 정보가 담겨져 있습니다.

Linked List

배열과 Linked List는 흔히 비교되는 자료구조 형태인데, 배열의 경우에는 배열 각 칸들이 물리적으로 한 곳에 모여있으므로, 크기를 한 번 정하면 늘리거나 줄일 수 없습니다.

반면, Linked List의 경우 데이터를 중간에 삽입하는 것이 가능합니다. 예를 들어 A노드와 C노드 사이에 B 노드를 추가하려면 A -> C 연결을 끊고, A -> B -> C와 같은 형태로 연결하면 되기 때문입니다.

하지만 Linked List는 주소를 일일이 찾아야하기 때문에 배열보다 검색 속도가 느릴 수 있습니다. 반면, 위에서 본 것 처럼 데이터를 중간에 추가하거나 삭제해야 할 경우 해당 위치의 주소 값만 변경하면 되므로 배열보다 용이합니다.

이처럼 Linked List는 길이가 정해지지 않은 데이터를 핸들링 할 때 유용한데, 단점으로는 노드의 주소 값들을 순차적으로 따라가야 하기 때문에 시간복잡도가 O(N)입니다.

Skip List

Linked List의 조회 속도 문제를 해결하기 위해 등장한 자료구조가 Skip List입니다. Skip List는 Linked List 노드의 검색 작업을 O(logN)의 시간 복잡도로 처리할 수 있습니다.

Linked List에서 빠른 검색을 위해 두 칸씩 건너뛰는 링크를 두 개의 노드마다 하나씩 추가한다면, 검색시간은 N/2로 줄어들게 됩니다. 세 개의 노드를 건너뛰는 링크를 추가한다면 검색시간은 N/3으로 줄어들게 됩니다.

Head에서 가장 높은 레벨(4)의 Link를 타고 88로 이동합니다.
하지만 찾고자 하는 20은 88보다 작기 때문에 다시 Head로 돌아갑니다.
이전에 이동했던 Link 레벨 - 1(3)의 Link로 이동합니다.
레벨 3의 링크를 타고 16으로 이동합니다.
16은 20보다 작기 때문에 다시 레벨 3링크를 타고 다음 노드로 이동합니다.
20은 88보다 작기 때문에 다시 16으로 돌아갑니다.
이전에 이동했던 Link 레벨 - 1(2)의 Link로 이동합니다.
72는 20보다 크기 때문에 다시 16으로 돌아갑니다.
이전에 이동했던 Link 레벨 - 1(1)의 Link로 이동합니다.
20 검색을 성공합니다.

만약 20이라는 값을 찾고 싶다면 위와 같은 방식으로 동작합니다. 이렇게 Skip List를 사용하면 모든 노드를 순회하지 않고도 레벨을 이용하여 노드들을 Skip하며, 원하는 값을 찾을 수 있습니다.

기본 사용법

ZADD <Key><Score><Value>
- 이미 존재하는 Key라면 Score만 변경된다.
ZRANGE <Key><StartIndex><EndIndex>
- 해당 Index 범위 값을 모두 돌려줌
- Zrange testkey 0 -1
  - 모든 범위를 가져온다.
Sorted Set의 Score는 double 타입이기 때문에 값이 정확하지 않을 수 있다.

Redis 의존성 및 설정

우선 레디스 의존성을 주입받고, 관련 설정을 해주어야 합니다.

implementation 'org.springframework.boot:spring-boot-starter-data-redis'

그다음 레디스를 컨테이너로 관리하기 위해 docker-compose.yml을 작성해 줍니다.

version: '3'

services:
  mysql:
    container_name: mysql
    image: mysql/mysql-server
    environment:
      MYSQL_DATABASE: techhub
      MYSQL_ROOT_HOST: '%'
      MYSQL_ROOT_PASSWORD: root
      TZ: 'Asia/Seoul'
    ports:
      - 13306:3306
    command:
      - "mysqld"
      - "--character-set-server=utf8mb4"
      - "--collation-server=utf8mb4_unicode_ci"

  redis:
    container_name: redis
    image: redis:alpine
    command: redis-server --port 6379
    hostname: localhost
    labels:
      - "name=redis"
      - "mode=standalone"
    ports:
      - 16379:6379

그다음으로는 yml에 docker-compose에 지정했던 포트를 사용해 주면 됩니다.

spring:
  data:
    redis:
      host: localhost
      port: ${REDIS_OUT_BOUND_PORT}
  main:
    allow-bean-definition-overriding: true

마지막으로 Spring에서 Redis를 빈으로 등록하기 위해 RedisConfig를 설정해 줍니다.

@Configuration
@EnableRedisRepositories
public class RedisConfig {

    @Value("${spring.data.redis.host}")
    private String host;

    @Value("${spring.data.redis.port}")
    private int port;

    @Bean
    public RedisConnectionFactory redisConnectionFactory() {
        return new LettuceConnectionFactory(host, port);
    }
    
    @Bean
    public RedisTemplate<String, String> redisTemplate(final RedisConnectionFactory redisConnectionFactory) {
        final RedisTemplate<String, String> redisTemplate = new RedisTemplate<>();
        redisTemplate.setConnectionFactory(redisConnectionFactory);
        redisTemplate.setKeySerializer(new StringRedisSerializer());
        redisTemplate.setValueSerializer(new StringRedisSerializer());
        return redisTemplate;
    }

    @Bean
    public RedisCacheManager redisCacheManager(final RedisConnectionFactory redisConnectionFactory) {
        final RedisCacheConfiguration redisCacheConfiguration = RedisCacheConfiguration.defaultCacheConfig()
                .serializeKeysWith(RedisSerializationContext
                        .SerializationPair.fromSerializer(new StringRedisSerializer()))
                .serializeValuesWith(RedisSerializationContext
                        .SerializationPair.fromSerializer(new GenericJackson2JsonRedisSerializer()));
        return RedisCacheManager.RedisCacheManagerBuilder
                .fromConnectionFactory(redisConnectionFactory)
                .cacheDefaults(redisCacheConfiguration)
                .build();
    }
}

여기서 고려해야 할 사항은 Redis의 Client를 선택하는 것입니다. 필자는 Lettuce를 사용했는데, 그 이유는 Lettuce가 요청을 비동기로 처리하기 때문에 Jedis에 비해 성능이 빠르다는 장점이 있기 때문입니다.

key-value(유저 닉네임, step)을 다루기 위해 Sorted-Set 구조를 사용하기 위해 redisTemplate을 직접 등록해 주고, 캐시 용도로도 사용하기 위해 CacheManager도 등록해 줍니다.

데이터 등록하기

이제 레디스에 데이터를 등록해 줄 차례입니다. redisTemplate의 opsForZSet().add() 함수를 사용하면 redis에 Sorted Set 형태로 값을 저장할 수 있습니다.

@Service
@Transactional
@RequiredArgsConstructor
public class PullRequestService {

    private final RedisTemplate redisTemplate;
    private final StepRepository stepRepository;
    private final PullRequestRepository pullRequestRepository;

	...(생략)
    
    private void isNotExistSave(final Long missionId, final List<PullRequest> newPrs) {
        for (PullRequest newPr : newPrs) {
            if (!pullRequestRepository.existsByStepIdAndTitle(newPr.getStepId(), newPr.getTitle())) {
                redisTemplate.opsForZSet().add(missionId + " ranking", newPr.getTitle(), newPr.getStepId());
                pullRequestRepository.save(newPr);
            }
        }
    }
}

PR에 데이터 변경이 발생할 때마다 레디스의 ranking key의 value를 업데이트해줍니다. key에 missionId를 prefix로 붙이는 이유는 미션별 랭킹을 매기기 위함입니다.

@Service
@RequiredArgsConstructor
@Transactional(readOnly = true)
public class PullRequestQueryService {

    private final RedisTemplate redisTemplate;

    public List<PullRequestRankingResponse> getPrsSortBy(final Long missionId) {
        final String key = missionId + " ranking";
        ZSetOperations<String, String> stringStringZSetOperations = redisTemplate.opsForZSet();
        Set<ZSetOperations.TypedTuple<String>> typedTuples = stringStringZSetOperations.reverseRangeWithScores(key, 0, 10);
        return typedTuples.stream()
                .map(tuple -> PullRequestRankingResponse.toResponse(tuple))
                .toList();
    }

}

마지막으로 조회 메서드에 Repository를 사용하는 대신 redisTemplate을 사용하여 조회해 주면 됩니다. 기존 Querydsl을 사용하고 있었는데, 2번의 조인과 정렬 기준을 찾는 등 번거로움이 사라졌습니다.

특히 레디스에 들어있는 데이터를 인메모리 기반으로 조회하기 때문에 훨씬 빠른 성능이 체감됩니다. 기존 성능 대비 10배가량 빨라졌습니다.

마무리하며

레디스를 적절하게만 사용한다면 너무나도 좋은 캐싱 솔루션이자 외부 라이브러리이지만, 아래와 같은 사항들은 레디스의 성능과 직접적인 연관이 있으므로 주의 깊게 볼 필요가 있습니다.

하나의 Collection에 너무 많은 데이터를 담으면 좋지 않다.
- 10,000개 이하 몇 천 개 수준으로 유지하는 게 좋다.
Expire는 Collection의 item 개별로 걸리지 않고 전체 Collection에 대해서만 걸림
- 즉 해당 10,000개의 아이템을 가진 Collection에 expire가 걸려있다면 그 시간 후에 10,000개의 데이터 모두 삭제
메모리가 부족하다면 기존에 있는 데이터를 줄이거나 더 좋은 성능의 레디스로 마이그레이션 해야 한다.
- 만약 마이그레이션을 하기로 결정했다면, 데이터의 정합성을 위해 메모리 사용률이 75% 내 일 때 이관하는 것이 좋다.
기본적으로 Collection들은 다음과 같은 구조로 사용해야 한다.
- Hash -> HashTable을 하나 더 사용
- SortedSet -> Skiplist와 HashTable을 사용
- Set -> HashTable 사용
Ziplist를 고려하자
- 데이터의 개수가 많지 않은 경우(몇 천 개, 몇 만개) 내부적으로 포인터를 사용하지 않는 Ziplist를 사용하는 것이 더 빠르다.
O(N) 관련 명령어는 주의하자
- Redis는 Single Thread 구조이기 때문에 동시에 처리할 수 있는 요청의 수는 1개이다. 따라서 오래 걸리는 명령어는 사용하지 않는 것이 좋다.
- 대표적인 O(N) 명령어
  - KEYS, FLUSHALL, FLUSHDB, Delete COILECTIONS, Get All Collections..