랭킹 시스템 자료구조 짜기

Question

안녕하세요, redis의 캐싱 관련해서 친구가 이것저것 얘기해주다가 저한테 미션을 하나 주더라고요.
1. 유저가 N명이 있고, 총 5명의 랭킹이 보여야한다.
2. 실시간으로 유저들의 score가 바뀐다.

친구는 redis의 Sorted set에 대해 이미 공부를 하고 저한테 물은 상태였습니다.
Sorted set은 insert가 O(log N)이더라고요.
 저는 고민하다가 
1. hash map을 통해 userID와 score를 저장 
2. 랭킹 5명은 따로 배열을 만든다. [ID, score]
3. 값이 바뀔 때 5명 중 최약체의 score보다 바뀐 값이 크다면 갈아치우는 형태를 얘기했습니다.
제 방식에 의하면 insert는 O(1)이고, 5명에 대한 값 변동 처리는 어차피 5명이니까 O(5^2)를 줘도 사실 O(1)이라 봐도 무방합니다.

저는 제 방식이 더 효율적인 것 같은데 어떻게 생각하시나요?

🫠😵‍💫😇 · Answer

insert만 있으면 괜찮은데 기존 score에 대한 업데이트가 있다면 못 쓰죠..

김형준 · Answer

성능/로직 복잡도 Trade Off인 상황으로 보이네요.
각각 장단점이 다르므로 현재 상황(요구사항)에 더 적절한 방법을 선택하면 될 것 같아요.
A 방법으로 시작해서 (혹은 C), 시간이 지남에 따라 B 방법으로 개선될 것 같아 보이네요.

요구사항 (가정)
1. 사용자가 N명이 있고, 총 5명의 랭킹이 보여야 한다.
2. 실시간으로 유저들의 score가 바뀐다.
3. (추가) 전체 사용자 점수를 저장할 필요 없음

- A 방법 = 로직이 단순함, 준수한 수준으로 성능이 보장됨
- B 방법 = 로직이 상대적으로 복잡함, 성능(시간)이 더 좋음
- C 방법 = 로직이 상대적으로 복잡함, 성능(시간, 공간)이 더 좋음

A) sorted set을 사용
- 대부분 요구사항 변경에 대해서 큰 수정 없이 대처 가능

B) TOP 5 점수만 따로 저장
- A 방법에 비해 로직이 복잡함
-- 기존 TOP 5 에 포함된 점수인지 확인 & 처리
-- 가장 낮은 점수보다 높은지 확인 & 처리
-- TOP 5 목록 & 전체 목록 업데이트

C) TOP 5 에 대한 점수만 sorted set에 저장
- A+B 방법 ?
- 전체 사용자 점수를 저장할 필요 없음 이라고 가정하면 사용 가능
- 저장 공간도 절약