Sorted Set vs Top-K for Real-time Ranking System

실시간 랭킹 시스템을 구축할 때 Redis의 Sorted Set(ZSET)을 활용하는 방식은 많이 알려진 방식이다.

• Redis: Real-Time Leaderboard & Ranking Solutions
• AWS: Build a real-time gaming leaderboard with Amazon ElastiCache for Redis

Sorted Set은 자료 구조 자체가 단순하고 지원되는 기능이 많으며 무엇보다 사용이 어렵지 않기 때문에 쉽게 랭킹 시스템을 구축할 수 있다.

 

또한 Redis는 시간이 지나면서 여러 기능과 모듈들이 생겼고 그러한 모듈 중 하나인 RedisBloom 모듈을 통해 몇 가지 확률적 자료구조를 지원하는데,

RedisBloom 모듈은 Sorted Set과 마찬가지로 실시간 랭킹 시스템에 적용할 수 있는 Top-K 자료구조를 제공한다.

 

 

Redis의 Top-K 발표 자료에서 Top-K에 대한 소개뿐만 아니라 Sorted Set과 Top-K의 성능에 대해 비교한다.

 

https://redis.com/blog/meet-top-k-awesome-probabilistic-addition-redisbloom/

 

위 벤치마크는 책 전쟁과 평화의 단어를 데이터로 사용하여 성능을 측정한 결과이다.

그래프에서 볼 수 있다시피 Top-K는 매우 가볍고(RAM usage, y축은 로그 스케일이다) 빠르며(Time usage) 또한 준수한 정확도(Accuracy usage)를 가진다.

하지만 Sorted Set의 정확도는 모든 경우에서 100%의 정확도를 가지는 반면 Top-K는 설정에 따라 100%에 못미치는 정확도를 갖는다.

즉, 성능과 정확도에 있어서 어느정도 trade-off가 생긴다는 것이다.

 

자료구조의 복잡성, 사용 방법, 찾을 수 있는 자료를 고려했을 때,

일반적인 경우라면 Sorted Set을 사용하여 랭킹 시스템을 구현하는게 유지보수의 측면에서 좋을 것 같고,

많은 데이터를 다루되 정확도보다도 실시간 성이 보다 중요한 경우(예를 들어 수십, 수백만명의 유저가 즐기는 게임의 랭킹 시스템, 방대한 양의 텍스트 데이터) Top-K 사용을 고려할 것 같다.