Redis 를 사용 하여 실시 간 차 트 기능 구현

게임 에는 게이머 의 등급 순위,점수 순위 등 다양한 순위 가 존재 합 니 다.게이머 들 이 차 트 에서 의 순 위 는 그 실력 의 상징 이다.차 트 선두 에 있 는 게이머 들 은 가상 세계 에서 무한 한 영광 을 가지 기 때문에 순위 도 핵심 게이머 들 의 추구 목표 가 된다.
전형 적 인 게임 차 트 는 다음 과 같은 흔 한 기능 을 포함한다.
1.각 유저 의 점 수 를 기록 할 수 있 습 니 다.
2.유저 의 점 수 를 갱신 할 수 있 습 니 다.
3.각 유저 의 점수 와 순 위 를 조회 할 수 있 습 니 다.
4.랭 킹 상위 N 명의 유 저 를 순위 별로 조회 할 수 있 음;
5.지 정 된 유저 의 앞 뒤 M 명 을 조회 할 수 있 습 니 다.
더 나 아가 위의 조작 은 모두 짧 은 시간 안에 실시 간 으로 완성 해 야 차 트 의 효용 을 최대한 발휘 할 수 있다.
한 유저 의 순위 가 x 위 를 올 리 면 x+1 명의 유저 의 순위 에 변화 가 생 길 수 있 기 때문에(이 유 저 를 포함)전통 적 인 데이터 베이스(예 를 들 어 MySQL)를 사용 하여 차 트 를 실현 하면 게이머 수가 많 을 때 데이터 베 이 스 를 빈번하게 수정 하고 성능 이 충분 하지 않 기 때문에 우 리 는 다른 방법 을 생각 할 수 밖 에 없다.
Redis 는 NoSQL 의 일원 으로서 최근 몇 년 동안 광범 위 하 게 응용 되 었 다.Memcached 에 비해 Redis 는 더 많은 데이터 형식 과 조작 인 터 페 이 스 를 가지 고 더 큰 적용 범 위 를 가진다.그 중에서 질서 있 는 집합(sorted set,zset 라 고도 함)은 차 트 구축 에 매우 적합 하 다.다음은 간략하게 요약 하 겠 습 니 다.
\#\#1\.Redis 설치
Ubuntu 에서 Redis 를 설치 하 는 것 은 매우 간단 합 니 다.다음 명령 을 실행 하면 됩 니 다.
> $ sudo apt-get install redis-server
설치 가 완료 되면 명령 행 클 라 이언 트 redis-cli 를 실행 하면 로 컬 redis 서버 에 접근 할 수 있 습 니 다.
> $ redis-cli > redis 127.0.0.1:6379>
최신 버 전 을 사용 하려 면 Redis 홈 페이지([http://redis.io](http://redis.io/)최신 코드 를 다운로드 하여 자체 컴 파일,절차 약.
\#\#2\.ZSet 의 상용 명령
질서 있 는 집합 은 먼저 집합 이 고 그 구성원(member)은 유일 성 을 가진다.그 다음 에 모든 구성원 이 하나의 점수(score)를 연결 하여 구성원 들 이 점수 에 따라 순 서 를 정할 수 있 도록 한다.질서 있 는 집합 에 대한 소개[http://redis.io/topics/data-types#sorted-sets](http://redis.io/topics/data-types#sorted-sets),그 명령 은[http://redis.io/commands#sorted_set](http://redis.io/commands#sorted_set)。
다음은 차 트 에 사용 할 수 있 는 몇 가지 명령 을 소개 합 니 다.
lb 를 차 트 이름 으로 가정 하고 user 1,user 2 등 은 게이머 의 유일한 표지 이다.
\#\#\#\#1)zadd―유저 점수 설정
명령 형식:**zadd 랭 킹 이름 점수 유저 표식**시간 복잡 도:O(log(N))
아래 에 4 명의 유저 의 점 수 를 설정 하 였 습 니 다.만약 유저 의 점수 가 이미 존재 한다 면 이전의 점 수 를 덮어 씁 니 다.
> redis 127.0.0.1:6379> zadd lb 89 user1
> (integer) 1
> redis 127.0.0.1:6379> zadd lb 95 user2
> (integer) 1
> redis 127.0.0.1:6379> zadd lb 95 user3
> (integer) 1
> redis 127.0.0.1:6379> zadd lb 90 user4
> (integer) 1
\#\#\#\#2)zscore―유저 점수 보기
명령 형식:**zscore 랭 킹 이름 유저 표식**시간 복잡 도:O(1)
다음은 user 2 라 는 유저 가 lb 랭 킹 에서 의 점 수 를 살 펴 보 겠 습 니 다.
> redis 127.0.0.1:6379> zscore lb user2 > “95”
\#\#\#\#3)zrevrange―순위 별로 차 트 보기
명령 형식:**zrevrange 차 트 이름 시작 위치 끝 위치[withscores]**시간 복잡 도:O(log(N)+M)
차 트 는 일반적으로 점수 가 높 은 것 에서 낮은 것 으로 정렬 되 기 때문에 우 리 는 zrevrange 를 사용 하고 zrange 는 점수 가 낮은 것 에서 높 은 것 으로 정렬 하도록 명령 합 니 다.
시작 위치 와 끝 위 치 는 0 으로 시 작 된 색인 이 며 모두 포함 되 어 있 습 니 다.종료 위치 가-1 이면 전체 차 트 를 볼 수 있 습 니 다.
with scores 를 착용 하면 유저 점수 가 반 환 됩 니 다.
다음은 모든 유저 점 수 를 보기 위 한 것 입 니 다.
> redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores
> 1) “user3”
> 2) “95”
> 3) “user2”
> 4) “95”
> 5) “user4”
> 6) “90”
> 7) “user1”
> 8) “89”
다음은 상위 3 명의 유저 점 수 를 조회 합 니 다.
> redis 127.0.0.1:6379> zrevrange lb 0 2 withscores
> 1) “user3”
> 2) “95”
> 3) “user2”
> 4) “95”
> 5) “user4”
> 6) “90”
\#\#\#\#4)zrevrank―유저 의 순 위 를 봅 니 다.
명령 형식:***zrevrank 랭 킹 이름 유저 표식**시간 복잡 도:O(log(N))
zrevrange 와 유사 합 니 다.zrevrank 는 점수 가 높 은 것 에서 낮은 것 으로 게이머 순 위 를 되 돌려 줍 니 다.(실제 0 으로 시 작 된 색인 을 되 돌려 줍 니 다)대응 하 는 zrank 는 점수 가 낮은 것 에서 높 은 것 으로 순 위 를 되 돌려 줍 니 다.
다음은 유저 user 3 와 user 4 의 순 위 를 조회 합 니 다.
> redis 127.0.0.1:6379> zrevrank lb user3
> (integer) 0
> redis 127.0.0.1:6379> zrevrank lb user1
> (integer) 3
\#\#\#\#5)zincrby―유저 점수 증감
명령 형식:**zincrby 랭 킹 이름 점수 증가 유저 표식**시간 복잡 도:O(log(N))
어떤 차 트 는 변경 시 유저 의 점 수 를 다시 설정 하고,또 다른 차 트 는 증분 방식 으로 유저 의 점 수 를 수정 하 며,증 가 는 플러스 마이너스 가 될 수 있 습 니 다.zincrby 를 실행 할 때 유저 가 차 트 에 없 으 면 원시 점수 가 0 이 고 zdd 를 실행 하 는 것 과 같다 고 생각 합 니 다.
다음은 user 4 의 점 수 를 6 으로 늘 려 1 위로 올 렸 다.
> redis 127.0.0.1:6379> zincrby lb 6 user4
> “96”
> redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores
> 1) “user4”
> 2) “96”
> 3) “user3”
> 4) “95”
> 5) “user2”
> 6) “95”
> 7) “user1”
> 8) “89”
\#\#\#\#6)zrem―어떤 유 저 를 제거 합 니 다.
명령 형식:**zrem 랭 킹 이름 유저 표식**시간 복잡 도:O(log(N))
유저 user 4 를 제거 합 니 다.
> redis 127.0.0.1:6379> zrem lb user4
> (integer) 1
> redis 127.0.0.1:6379> zrevrange lb 0 -1 withscores
> 1) “user3”
> 2) “95”
> 3) “user2”
> 4) “95”
> 5) “user1”
> 6) “89”
\#\#\#\#7)차 트 삭제
명령 형식:**del 차 트 이름***
차 트 대상 은 zadd 나 zincrby 를 처음 호출 할 때 만 들 어 졌 습 니 다.삭제 하려 면 redis 에서 통용 되 는 명령 del 을 호출 하면 됩 니 다.
> redis 127.0.0.1:6379> del lb
> (integer) 1
> redis 127.0.0.1:6379> get lb
> (nil)
같은 점수 문제
공짜 방안 에는 항상 그렇게 완벽 하지 못 한 것들 이 있다.앞의 예 에서 볼 수 있 듯 이 user 2 와 user 3 는 같은 점 수 를 가지 고 있 지만 점수 역순 으로 정렬 할 때 user 3 은 user 2 앞 에 있다.실제 응용 장면 에서 우 리 는 user 2 가 user 3 앞 에 있 는 것 을 보고 싶 습 니 다.user 2 가 user 3 보다 먼저 차 트 에 가입 하기 때 문 입 니 다.즉,user 2 가 먼저 이 점수 에 도착 한 것 입 니 다.
그러나 레 디 스 는 점 수 를 만 났 을 때 집합 구성원 자체 의 사전 순서에 따라 순 서 를 매 긴 다.여 기 는'user 2〃와'user 3〃라 는 두 문자열 에 따라 순 서 를 매 긴 다.역순 으로 순 서 를 매기 면 user 3 는 자 연 스 럽 게 앞 에 선다.
이 문 제 를 해결 하려 면 점수 에 시간 스탬프 를 넣 는 것 을 고려 할 수 있다.계산 공식 은 다음 과 같다.
>타임스탬프 가 있 는 점수=실제 점수*1000000000+(9999999999 C timestamp)
timestamp 우 리 는 시스템 이 제공 하 는 time()함수,즉 1970 년 1 월 1 일 이후 의 초 수 를 사용 합 니 다.우 리 는 32 비트 의 시간 스탬프(이것 은 2038 년 까지 버 틸 수 있 습 니 다)를 사용 합 니 다.32 비트 의 시간 스탬프 는 10 비트 10 진 정수(최대 치 4294967295)이기 때문에 우 리 는 시간 스탬프 가 10 비트(10 진 정수)를 차지 하고 실제 점 수 는 10^10 배 확대 합 니 다.그리고 두 부분 을 더 한 결 과 를 zset 의 점수 로 합 니 다.시간 에 따라 거꾸로 배열 해 야 한 다 는 점 을 감안 하여 시간 스탬프 라 는 부분 을 뒤 바 꿔 야 한다.이것 이 바로 99999999 로 시간 스탬프 를 뺀 이유 다.우리 가 유저 의 실제 점 수 를 읽 으 려 면 후 10 자리 만 제거 하면 됩 니 다.
초보 적 으로 보면 이 방안 은 그런대로 괜 찮 은 것 같 지만,이 안 에는 두 가지 문제 가 있다.
첫 번 째 문 제 는 작은 문제 입 니 다.초 를 시간 스탬프 로 사용 하면 구역 의 점수 가 부족 할 수 있 습 니 다.만약 에 같은 초 에 두 개의 점수 가 똑 같은 것 이 나타 나 면 앞의 문제 가 발생 할 수 있 습 니 다.물론 우 리 는 정밀도 가 높 은 시간 스탬프 를 선택 할 수 있 지만 실제 장면 에서 같은 초 에 누가 앞 에 서 는 지 는 중요 하지 않 습 니 다.
두 번 째 문 제 는 큰 문제 입 니 다.Redis 의 점수 유형 은 double 이 고 64 비트 의 더 블 정밀도 부동 소수점 은 52 비트 의 유효 숫자 만 있 기 때문에 정확하게 표현 할 수 있 는 정수 범 위 는-2^53 에서 2^53 이 고 최고 16 비트 10 진법 정수(최대 치 는 9007199254740992 이 며 사실은 16 비트 도 완전 하 게 표시 하지 못 합 니 다)를 나 타 낼 수 있 습 니 다.앞 시간 스탬프 가 10 위 를 차지 하면 점수 가 6 위 밖 에 남지 않 는 다 는 것 이다.이 는 일부 차 트 점수 로 는 부족 하 다 는 것 이다.우 리 는 2015 년 1 월 1 일부 터 시간 을 재 는 등 시간 스탬프 수 를 줄 이 는 것 을 고려 할 수 있 지만,이것 은 여전히 몇 자리 증가 하지 않 는 다.또는 구역 분 도 를 줄 이 고 분,시간 을 시간 스탬프 단위 로 한다.
레 디 스 의 점수 유형 이 int 64 라면 우 리 는 위의 고민 이 없다.여기까지 말 하면 레 디 스 는 int 64 유형의 ZSet 을 추가 로 제공 해 야 하지만 현 재 는 자신 이 소스 코드 를 바 꾸 지 않 는 한 환상 일 수 밖 에 없다.
레 디 스 도 차 트 문 제 를 완벽 하 게 해결 하지 못 하 는 만큼 전문 적 인 차 트 데이터 구 조 를 스스로 실현 할 필요 가 있 지 않 을 까?실제 응용 에서 의 차 트 는 최적화 할 수 있 는 부분 이 많 기 때문에 게이머 보다 피라미드 분 포 를 나타 내 고 낮은 단계 의 게이머 수량 이 많 을 수록 같은 점 수 는 대량의 유 저 를 가 집 니 다.게이머 가 1 점 을 증가 하면 많은 유 저 를 뛰 어 넘 을 수 있 습 니 다.이것 은 최적화 에 가능성 을 제공 합 니 다.
레 디 스 를 이용 한 실시 간 차 트 기능 구현 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.레 디 스 실시 간 차 트 에 관 한 더 많은 내용 은 저희 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 읽 어 주시 기 바 랍 니 다.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!