상위 K는 현재 경계 안에 들 후보를 빠르게 유지하는 문제이고, 순위와 보상은 탈락한 항목과 과거 시점을 다시 설명해야 하는 문제입니다. 먼저 결과가 한 번의 계산인지 계속 변하는 질의인지, 그리고 결과가 화면인지 권리 확정인지 구분해야 자료구조와 저장 상태를 잘못 축소하지 않습니다.
상위 목록과 전체 순위의 상태 요구
백만 명 중 점수가 높은 100명만 한 번 구하려면 크기 100의 최소 힙이 유용합니다. 루트는 현재 후보 중 가장 낮은 점수이고 더 좋은 항목이 오면 교체합니다. 그러나 임의 사용자의 순위를 묻거나 기존 상위 사용자의 점수가 내려가면, 버려 둔 나머지 후보도 다시 필요합니다.
상위 K 유지, 전체 순위 조회, 마감 시 보상 권리 확정은 서로 다른 상태를 필요로 합니다. 한 힙이 세 요구를 모두 해결한다고 가정하지 않습니다.
실무 선택은 “점수 갱신이 있는가”보다 “탈락한 항목을 나중에 다시 비교해야 하는가”로 시작합니다. 배치 화면에서 한 번 계산하고 버리면 힙으로 충분할 수 있지만, 점수 감소·임의 순위·감사 가능한 마감 결과가 있으면 원본과 버전 또는 정렬 인덱스를 보존해야 합니다.
크기 K 힙과 단일 스캔 비용
K=3, 입력 점수 5·1·8·3·9를 순회합니다. 동점에는 사용자 ID 등 일관된 보조 키를 둔다고 가정합니다.
| 입력 | 후보 점수 집합 | 행동 |
|---|---|---|
| 5,1,8 | {1,5,8} | 세 자리 채움 |
| 3 | {3,5,8} | 최저 1 교체 |
| 9 | {5,8,9} | 최저 3 교체 |
한 번의 전체 스캔은 O(N log K) 시간, 후보 공간 O(K)입니다. K=0은 빈 결과, K>N은 전체 결과로 정할 수 있습니다. 결과를 순위대로 반환하려면 최종 후보 정렬 O(K log K)도 포함합니다.
점수 9가 나중에 0으로 내려가면 현재 후보 {5,8,0}만 보고 탈락했던 3을 복원할 수 없습니다. 전체 원본 재스캔, 정렬 인덱스, 순서 통계 트리 등 요구에 맞는 상태가 필요합니다. 같은 사용자 업데이트를 새 항목처럼 넣어 후보를 중복시켜도 안 됩니다.
샤드별 상위 K 병합의 전제
각 사용자가 정확히 한 샤드에 있고, 사용자 점수는 그 샤드에서 완성되어 있으며, 모든 샤드가 동일한 전순서 비교를 쓴다고 합시다. 어떤 사용자 X가 자기 샤드의 K위 밖이라면 그 샤드 안에 X보다 앞선 사용자가 적어도 K명 있습니다. 따라서 X는 전역 K위 안에도 들 수 없습니다.
이 논리로 각 샤드 상위 K만 모아 전역 K를 구할 수 있습니다. 사용자 점수를 여러 샤드에서 더해야 하거나 같은 사용자가 여러 곳에 있으면 전제가 깨집니다. 낮은 부분 점수들이 합쳐 최상위가 될 수 있고, 중복을 제거하면 K 밖 후보가 필요할 수 있습니다.
그림을 글로 읽기
- 샤드 1 상위 K
- 샤드 2 상위 K
- 전역 후보 병합: 각 목록의 앞 후보부터 비교
- 전역 상위 K
- 샤드 1 상위 K → 전역 후보 병합: 정렬 후보
- 샤드 2 상위 K → 전역 후보 병합: 정렬 후보
- 전역 후보 병합 → 전역 상위 K: K명 선택
병합 비용과 동점 처리 의미
샤드 S개가 각각 K개를 보내면 네트워크 후보 수는 O(SK)입니다. 모두 모아 정렬하면 O(SK log(SK)), 크기 K 힙으로 고르면 O(SK log K)입니다. 각 목록이 이미 정렬됐다면 앞 후보 S개를 최대 힙에 두고 한 명을 꺼낼 때 그 목록의 다음 후보를 넣는 k-way 병합으로 선택 단계 O(S+K log S), 힙 공간 O(S)를 얻을 수 있습니다. 다만 이미 전체 후보를 받았다면 수신 데이터 메모리 O(SK)는 남습니다.
“정확히 K명”과 “K위 점수와 같은 사람 모두”는 다릅니다. 후자는 결과가 K를 크게 넘을 수 있고 샤드가 정확히 K개만 잘라 보내면 동점자를 잃을 수 있습니다. 먼저 전역 경계 점수를 구한 뒤 그 점수 이상을 재조회하는 등 별도 절차가 필요합니다. 같은 사용자 중복은 단순히 한 항목을 버리는 것이 아니라 어느 점수·버전이 권위 있는지 먼저 정해야 합니다.
Redis sorted set 순서와 정밀도
Sorted set의 member는 고유하고 score가 같은 member는 바이트 사전순으로 정렬됩니다. 역순 조회는 동점 member 순서도 뒤집으므로 “점수 내림차순·가입 순서 오름차순” 같은 규칙을 자동으로 제공한다고 생각하면 안 됩니다. 필요한 복합 정렬 기준을 명시하고 member 인코딩·별도 인덱스 또는 애플리케이션 처리를 선택합니다.
score는 IEEE 754 배정밀도 값이므로 모든 정수를 정확히 표현하는 범위는 절댓값 2^53까지입니다. 예를 들어 2^53과 2^53+1을 한 score에 넣어 서로 다른 순위를 표현하려 해도, 후자는 정확히 구별되지 않을 수 있습니다. 큰 시간·점수·사용자 순번을 한 숫자로 밀어 넣으면 다른 값이 같아질 수 있으므로, 점수와 보조 키를 합성하기 전에 범위와 동점 정밀도를 확인해야 합니다.
같은 member에 SET 형태로 점수를 덮는 작업과 증가 연산의 재시도는 다릅니다. 증가 요청을 두 번 보내면 두 번 반영될 수 있으므로 event ID와 도메인 버전을 원자적으로 확인하는 별도 계약이 필요합니다. sorted set 자체의 member 유일성이 논리 이벤트의 중복 반영을 막지는 않습니다.
순위 조회와 보상 확정의 상태 분리
실시간 목록은 여러 샤드의 서로 다른 시점이 섞인 근사 화면일 수 있습니다. 반면 보상은 마감 기준 시각·버전, 늦은 점수 정책, 중복 지급 방지와 정정 원장이 필요합니다. 캐시의 현재 순위를 읽어 바로 반복 지급하면 마감 뒤 변동·재시도로 권리가 달라질 수 있습니다.
| 요구 | 필요한 대표 상태 |
|---|---|
| 한 번의 상위 K 계산 | 원본 스캔 + 크기 K 힙 |
| 빈번한 점수 변경·임의 순위 | 전체 정렬 인덱스·원본 버전 |
| 샤드 전역 상위 K | 분할·동점 계약과 일관된 조회 기준 |
| 마감 보상 | 확정 snapshot·권리 원장·지급 ID |
Redis의 member 유일성·score 정밀도·동점 바이트 비교는 공식 ZADD 문서의 설명을 기준으로 확인했습니다. 이 확인은 Redis 장애·동시 갱신 실험을 실행했다는 뜻은 아닙니다.
작은 사용자 집합을 임의로 샤드에 나눠 후보 병합과 전수 정렬을 비교합니다. 사용자 중복·부분 점수 합산·K위 동점·점수 감소를 넣어 전제가 깨질 때 잘못된 결과가 나오는지 확인합니다. Redis 세부 동작은 운영 버전에서 별도로 시험하고, 큰 정수·동점 문자열·중복 증가 요청을 반드시 포함합니다.