[ EnjoyDelivery ] 이슈 2. 장바구니 메뉴 조회 시 redis의 O(N) values 명령어를 O(1) hscan 명령어로 변경

Dayeon myeong·2021년 11월 1일

Enjoy Delivery

목록 보기

2/4

장바구니에 담은 모든 메뉴를 조회하는 로직에서 hash 의 values 명령어가 O(N) 시간복잡도를 가져 해당 values 명령어가 수행될 동안 다른 redis 명령어는 수행되지 못하고 대기하는 문제가 발생합니다.

그 이유는 redis 는 싱글 스레드라서 한번에 하나의 명령어 수행만이 가능하기 때문입니다.

redis 문서를 찾아본 결과 대부분의 명령은 O(1)의 시간복잡도를 가져 빠른 처리가 가능합니다. 하지만 O(N)의 명령의 경우에는 명령어를 빠르게 처리하지 못하고 대기하는 문제가 발생하게 될 것입니다.

values 명령어는 key를 인자로 사용하며, key와 일치하는 모든 hash value를 검색하는 명령어입니다. 즉, value 개수인 N만큼의 시간복잡도를 가집니다. 현재 프로젝트에는 value에 장바구니에 담긴 메뉴를 담고있습니다.

만약 여러 서버에서 Redis에 이 O(N)의 명령어를 수행하게 된다면, 레디스는 싱글스레드이기 때문에 다른 명령어들이 대기하는 문제가 발생합니다.

Redis scan을 사용하는 이유

이러한 O(N) 상황에서, redis는 SCAN이라는 방식을 통해 문제를 해결합니다.

SCAN cursor [MATCH pattern] [COUNT count]

하나의 명령으로 values처럼 모든 value를 한번에 가져오는 것이 아니라, SCAN을 이용하면 여러번 명령을 쪼개 설정한 count 개수만큼 value를 읽어옵니다.

cursor 값이 0일 때 SCAN이 순회를 시작하고, 이어지는 순회에 사용할 cursor 값과 지정한 패턴(pattern)과 일치하는 키를 최대 지정한 개수(count)만큼 반환합니다. 반환된 cursor 값이 0이면 순회가 종료됩니다. 이 과정을 전체 순회 full iteration이라고 합니다.

redis 127.0.0.1:6379> scan 0 <-- cursor 값 0으로 순회 시작.
1) "17" <-- 다음 순회에 사용될cursor 값
2)  1) "key:12"
    2) "key:8"
    3) "key:4"
    4) "key:14"
    5) "key:16"
    6) "key:17"
    7) "key:15"
    8) "key:10"
    9) "key:3"
   10) "key:7"
   11) "key:1"
redis 127.0.0.1:6379> scan 17 <-- 앞의 scan 명령의 응답으로 반환된 cursor 값
1) "0" <-- 반환된 cursor 값이 0이면 순회 종료
2) 1) "key:5"
   2) "key:18"
   3) "key:0"
   4) "key:2"
   5) "key:19"
   6) "key:13"
   7) "key:6"
   8) "key:9"
   9) "key:11"

SCAN 명령의 결과에 따라 이어지는 SCAN 명령에 사용할 cursor 값이 바뀌고, 이 cursor 값이 0일 때 순회를 종료합니다.

이 방식을 사용하게 된다면, 한번의 명령으로 모든 value를 가져오는 것보다는 여러번 나눠서 처리하기 때문에 시간이 오래걸릴 수 있지만, block 되지 않기 때문에 그 사이 사이에 다른 요청들을 redis에서 처리해줄 수 있을 것입니다.

Hash의 HSCAN을 사용 시 주의점

SCAN 명령어의 종류에는 Hash에서 사용할 수 있는 HSCAN이 있습니다. 따라서 다음의 명령어를 사용할 수 있을 듯합니다.

HSCAN key cursor [MATCH pattern] [COUNT count]

하지만, redis scan의 문서에 따르면 hash의 내부구조가 hash table이 아닌 ziplist로 구현되어있을 경우 한번의 명령어 호출로 모든 value를 검색한다고 합니다. 즉, 이 경우에는 SCAN을 사용해도 한번에 처리해버리는 것을 얘기합니다.

redis의 hash에서는 ziplist와 hash table 둘 중 하나의 방식의 자료구조가 사용됩니다.

저장된 데이터가 적은 경우라면 ziplist를, 큰 경우라면 hash table을 사용하도록 설정되있습니다.

그 이유는 redis의 hash table 자료구조의 경우에는 키를 관리하는 해시테이블과, 필드와 value를 관리하는 해시테이블로 총 2개의 해시테이블이 구성되어있기 때문입니다.

적은 데이터만을 저장해야될 경우 2개의 해시테이블을 사용하는 것보다, 메모리 사용이 적도록 ziplist를 사용하도록 설정해놨습니다.

만약 장바구니 hash에 아이템을 담을 경우 데이터 크기가 작아 ziplist 방식으로 구현되어있다면, SCAN을 사용해도 이전처럼 한번에 명령어 처리한 것과 동일할 것입니다. 즉, O(N) 문제가 그대로 발생합니다.

위 사진은 ziplist가 되는 기준을 보여주는 사진입니다.

entries는 필드 개수로 필드 개수가 512개 이하면 ziplist 자료구조가 사용되고, 초과되면 hash table 이 사용됩니다.
value는 값의 바이트 수로 바이트 수가 64바이트 이하면 ziplist를, 초과되면 hash table에 저장됩니다.

entires와 value 둘 중 하나라도 초과되면 hash의 자료구조가 hash table 이 됩니다.

장바구니에 하나의 메뉴를 넣었을 때의 key와 value의 바이트 수를 조회해보니, 기준점인 64 바이트를 넘는 것을 확인했습니다.

따라서 SCAN명령어를 사용해도 한번의 처리가 되지는 않다는 것을 알았고 사용해도 될 듯합니다.

리팩토링 전 코드



  public List<OrderItem> findAllByUserId(Long userId) {
    String key = getHashKey(userId);

    List<Object> values = redisTemplate.opsForHash().values(key); //O(N)의 시간복잡도를 가짐.
    return values.stream()
        .map(o -> objectMapper.convertValue(o, OrderItem.class))
        .collect(Collectors.toList());
  }

리팩토링 후 코드



  public List<OrderItem> findAllByUserId(Long userId) {

    RedisSerializer keySerializer = redisTemplate.getKeySerializer();
    RedisSerializer hashValueSerialier = redisTemplate.getHashValueSerializer();
    String key = getHashKey(userId);
    List<Object> result = new ArrayList<>();

    redisTemplate.execute(
        new RedisCallback<Object>() {
          public Object doInRedis(RedisConnection connection) throws DataAccessException {
            ScanOptions scanOptions = ScanOptions.scanOptions().match("*").count(100).build();
            Cursor<Entry<byte[], byte[]>> cursor = connection.hashCommands().hScan(
                keySerializer.serialize(key), scanOptions);

            while(cursor.hasNext()) {
              Entry<byte[], byte[]> entry = cursor.next();

              result.add(hashValueSerialier.deserialize(entry.getValue()));
            }
            return result;
          }
        });


    return Optional.ofNullable(result)
        .orElse(new ArrayList<>())
        .stream()
        .map(o -> objectMapper.convertValue(o, OrderItem.class))
        .collect(Collectors.toList());
  }

스프링에서 사용시에는 redisTemplate의 execute 명령어와 redis callback을 사용했습니다. 이 방식은 같은 connection에서 여러 명령어를 실행할 수 있도록 보장합니다. 또한, hscan과 같은 명령어를 쓸 수 있기 때문에 사용했습니다.

만약 ziplist 자료구조 방식으로 hscan이 제대로 동작하지 않으면?

ziplist로 scan을 하게되면 기존 values와 똑같이 O(n)을 가집니다.
여러 서버에서 이 명령어를 하나의 redis에 요청할 경우
명령어 하나가 처리될 동안 다른 명령어들은 block되는 문제가 발생합니다.

아예 그러면 redis를 여러개 쓰는 다중화하는 방식도 고려해볼 수 있을 듯 합니다.

Replication : 쓰기용 master redis , 읽기용 slave redis를 사용하게 된다면 읽기용 redis 를 여러개 두어서 부하를 분산하여 여러 명령어가 병렬적으로 처리 될 수 있습니다. 하지만 Replication은 데이터 정합성 문제나 데이터량이 늘어나는 문제가 있습니다.
Sharding : 데이터를 여러 redis에 나눠담는 방법입니다. 중요한 것은 샤딩 키를 정하는 것입니다. 샤딩키를 통해 데이터가 어떻게 분산될지 정해주기 때문입니다.
현재 장바구니의 경우에는 user별 장바구니가 존재합니다. userid별로 샤딩을 할 수 있을 듯 합니다. 하지만 샤딩은 데이터가 한쪽 샤드에 쏠리는 문제가 발생합니다. 이를 해결하기 위해서는 샤딩키를 consistency hash?같은 방식으로 키를 해싱한 값으로 샤딩하여 고르게 데이터가 분배되도록 할 수 있습니다.
하지만 샤딩은 특정 샤드에 요청 쿼리가 집중되어 부하가 발생할 수 있고, 샤딩을 할 수록 네트워크 비용이 발생합니다. 연산하려는 데이터가 멀리 있을수록 시스템 성능은 떨어지게 됩니다.