Sorted Sets으로 리더보드 구현

1. 리더보드(Leaderboard)의 특성

게임이나 경쟁에서 상위 참가자의 랭킹과 점수를 보여준다. 그룹 상위 랭킹 혹은 특정 대상의 순위를 나타낸다. 

 

최다 구매 상품, 리뷰 순위 등의 순위로 나타낼 수 있는 다양한 부분에서 응용이 가능하다. 구매 상품의 뷰, 댓글 등을 계산할 수 있다.

 

2. API 관점에서 리더보드의 동작

점수 생성 및 업데이트를 구할 때 SetScore로 점수를 구하거나, 상위 랭크 조회 시 범위 기반으로 getRange를 사용하던가, 아니면 특정 대상 순위 조회를 할 때 값 기반 조회로 getRank를 사용한다.

 

리더보드의 핵심은 빠른 업데이트와 빠른 조회이다. 관계형 DB 등의 레코드 구조를 사용했을 때 데이터 구조와 성능에 문제가 발생한다.

 

업데이트 시 한 행에만 접근하기에 비교적 빠르다. 그러나 랭킹 범위나 특정 대상의 순위 조회 시에 데이터를 정렬하거나, COUNT() 등의 집계 연산을 수행해야 하기에 데이터가 많아질수록 속도가 느려진다. 그래서 리더보드를 구성할 때 관계형 DB는 적합하지 않다.

 

 

리더보드의 구현 시 Redis를 사용했을 때의 장점은 첫 번째는 순위 데이터에 적합한 sorted-set 자료구조를 사용하면 자동으로 정렬된다는 점. 두 번째는 용도에 특화된 오퍼레이션(set 삽입 및 업데이트) 이 존재하여 사용이 간단하다. 세 번째는 자료구조의 특성으로 범위 검색이나 특정 값 순위 검색 등의 데이터 조회가 빠르다. 네 번째는 인메모리 DB라 빈번한 액세스에 유리하다.

 

3. Redis로 Leaderboard 구현.

 

Sorted sets 명령어로 구현할 예정이기에 모르면 링크 참조.

 

패키지 구조는 contoller와 service이다. 

 

package com.example.pratice.leaderboard.service;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.ZSetOperations;
import org.springframework.stereotype.Service;

@Service
public class RankingService {

    private static final String LEADERBOARD_KEY ="leaderBoard";

    @Autowired
    StringRedisTemplate redisTemplate;

    public boolean setUserScore(String userId, int score){
        ZSetOperations zSetOps =redisTemplate.opsForZSet();
        zSetOps.add(LEADERBOARD_KEY,userId,score);

        return true;
    }

    public Long getUserRanking(String userId){
        ZSetOperations zSetOps =redisTemplate.opsForZSet();
        Long rank = zSetOps.rank(LEADERBOARD_KEY, userId);

        return rank;
    }

    public List<String> getTopRank(int limit){
        ZSetOperations zSetOps = redisTemplate.opsForZSet();
        Set<String> rangeSet = zSetOps.reverseRange(LEADERBOARD_KEY, 0, limit - 1);

        return new ArrayList<>(rangeSet);
    }

}

sortedSet을 다룰 거라 ZSetOperations 인터페이스를 사용했다. 각각 점수 설정, 랭킹 획득, 상위 랭킹 목록 확인 메서드이다.

 

메서드들을 보면 생각보다 단순한 걸 확인할 수 있다. 이전 포스팅에서도 말했듯이 Redis의 가장 큰 장점은 과거 별도로 구현해야 했던 공통적 기능들을 Redis를 사용하면 쉽게 구현한다. 

 

package com.example.pratice.leaderboard.controller;

import com.example.pratice.leaderboard.service.RankingService;
import java.util.List;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;
import org.springframework.web.bind.annotation.RestController;

@RestController
public class ApiController {

    @Autowired
    private RankingService rankingService;

    @GetMapping("/setScore")
    public Boolean setScore(
            @RequestParam String userId,
            @RequestParam int score
    ){
        return rankingService.setUserScore(userId,score);
    }

    @GetMapping("/getRank")
    public Long getUserRank(@RequestParam String userId){
        return rankingService.getUserRanking(userId);
    }

    @GetMapping("/getTopRanks")
    public List<String> getTopRanks(){
        return rankingService.getTopRank(3);
    }
}

Service 계층의 메서드를 활용하기 위한 Api Controller를 만들었다. 

 

http://localhost:8080/setScore?userId=Kim&score=10 임의로 점수를 설정해봤다. 

 

근데 만약 같은 id에 score를 변경하면 어떻게 될까?  

 

http://localhost:8080/setScore?userId=Kim&score=20

 

score를 20으로 설정하면 점수가 20으로 덮어써진다.

 

 

위의 URL로 여러 userId와 점수를 임의로 지정해 보자. (나는 편의상 4개로 설정했다.)

(Kim:20, Hongn:95, Yoon:70, Son: 40으로 설정.)

 

 

http://localhost:8080/getTopRanks로 순위를 확인해 봤더니 

 

위의 사진처럼 나왔다. 

 

http://localhost:8080/getRank? userId=Yoon으로 

Yoon의 순위를 확인해 보니 2로 나왔다. 

 

 

Rank가 오름차순이라 순위가 이상하게 나와서 내림차순으로 바꿔보겠다. 

 

    public Long getUserRanking(String userId){
        ZSetOperations zSetOps =redisTemplate.opsForZSet();
        Long rank = zSetOps.reverseRank(LEADERBOARD_KEY, userId);

        return rank;
    }

기존 rank를 reverseRank로 바꿔줬다. 

 

정상적으로 순위가 출력된 걸 확인할 수 있다. 

 

참고로 0은 순위 1위라고 볼 수 있다. 배열의 index를 생각하면 이해가 쉽다. 

 

4. 성능 테스트

그러면 Redis가 leaderBoard에 얼마나 속도가 빠른지 측정해 보겠다.  

 

테스트 위치는 위와 같다.

package com.example.pratice;

import com.example.pratice.leaderboard.service.RankingService;
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayList;
import java.util.Collections;
import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
@Slf4j
public class RankingSimpleTest {

    @Autowired
    private RankingService rankingService;

    @Test
    @DisplayName("기존 순위 테스트")
    void inMemorySort(){
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<1000000;i++){
            int score = (int)(Math.random()*1000000);
            list.add(score);
        }

        Instant before = Instant.now();
        Collections.sort(list);
        Duration elapsed = Duration.between(before,Instant.now());

        System.out.println("경과 시간 :" + elapsed.getNano()/1000000 +"ms");
    }
}

테스트로 데이터를 백 만개 넣어봤다. 일반 sort 정렬이라 시간 복잡도는 nlogn이다. 

 

시간을 측정했더니 632ms 걸렸다.

 

그러면 이제 Redis의 sorted set에 들어가면 어찌 될지 테스트해 보겠다.

 

    void insertScore(){
        for(int i=0;i<1000000;i++){
            int score = (int)(Math.random()*1000000);
            String userId = "user_"+i;
            rankingService.setUserScore(userId,score);
        }
    }

먼저 값을 넣어봤다. 100만 개의 데이터를 Redis에 넣다 보니 시간이 좀 오래 걸릴 수가 있다.

ZCount로 0부터 백만까지 값이 얼마나 들어있는지 확인했다. (4개는 이전에 넣은 데이터이다.)

 

데이터가 정상적으로 들어왔다면 테스트를 시작해 보자. 2가지의 경과 시간 케이스를 구할 예정이다. 

 

1) user_100의 랭크를 확인해 보고, 경과 시간을 확인해 보자. 

 

2) 상위 랭커 10인을 가져오는 데 걸리는 시간을 측정해 보자.

 

 

    @Test
    void getRanks(){
        rankingService.getTopRank(1);

        Instant before = Instant.now();
        Long userRank = rankingService.getUserRanking("user_100");
        Duration elapsed = Duration.between(before,Instant.now());

        System.out.println(String.format("User_100's Ranking : %d - 경과 시간 %d ms",userRank, elapsed.getNano()/1000000));

        before = Instant.now();
        List<String> topRankers = rankingService.getTopRank(10);
        elapsed = Duration.between(before,Instant.now());

        System.out.println(String.format("10명의 Top Rank - 경과 시간 %d ms",elapsed.getNano()/1000000));
    }

네트워크 최초 연결하는 데 비용이 들어갈 수 있기에 순수 측정 시간을 못구할 수 있다. 

 

그러므로 rankingService.getTopRank(1); 처음에 무의미한 함수 호출로 제대로 시간이 측정되게끔 만들었다.

 

순위를 측정하니 위의 결과대로 나왔다. 참고로 Rank보다 Range가 빠른 이유는 Range는 끝에서 가져오면 되기에 데이터의 헤드나 테일에서 바로 원하는 데이터를 잡기 때문이다. 

 

 

이렇게 처음 측정한 632ms에서 98.9% 감소한 걸 확인할 수 있다. 검증을 통해 Redis가 성능 상에 얼마나 이점이 많고, leaderBoard에 적합한지 확인할 수 있었다.