사용자별 점수가 샤드에 완전히 분할된 경우 샤드별 상위 K명만으로 전역 상위 K명을 구할 수 있나요?

사용자가 샤드에 겹치지 않게 배정되어 있고, 각 샤드가 같은 집계 버전의 완전한 사용자 점수를 갖고 있으며, 정렬 규칙도 동일하다면 샤드별 top-K만 모아 전역 top-K를 구할 수 있습니다. 어떤 사용자가 자기 샤드에서 K위 밖이면 그 샤드 안에 이미 K명이 그보다 앞에 있으므로 전역 K위 안에 들어갈 수 없기 때문입니다. 그러나 점수 조각이 여러 샤드에 나뉘어 합산된다면 이 결론은 깨집니다.

스냅샷과 부분 결과를 구분합니다

샤드마다 K명을 반환하고 이들을 하나의 후보 집합으로 병합한 뒤 전역 정렬을 수행합니다. 샤드 수가 S라면 후보는 최대 S×K명이고, 결과를 크기 K 힙으로 유지하거나 후보를 정렬할 수 있습니다. 같은 사용자가 여러 후보에 나타나는 구조라면 중복 제거가 먼저 필요합니다. 동점자를 K명만 자를지 동일 점수 전원을 반환할지도 계약으로 고정해야 합니다. 이 방식은 분산 top-K 병합(distributed top-K merge)이라고 부릅니다.

반례는 사용자 점수가 샤드별 조각으로 나뉘는 경우입니다. 사용자 X가 A 샤드에서 60점, B 샤드에서 60점을 받아 합계 120점이 되지만 각 샤드에서 단독으로는 top-K 밖이라면, 샤드별 후보를 모아도 X를 발견할 수 없습니다. 이때는 사용자별 전체 합산, 각 샤드의 점수 상한·하한, 반복적인 후보 확장 같은 추가 정보가 필요합니다. 샤드가 사용자 기준으로 나뉘었다고 말해도 점수 집계가 다른 키로 분할됐는지 확인해야 합니다.

정확도와 시점을 별도로 표시합니다

샤드 응답을 서로 다른 시각에 읽으면 각 샤드 내부에서는 정확해도 전체 결과가 한 시점의 스냅샷이 아닐 수 있습니다. 실시간 화면은 잠정 결과와 약간의 지연을 허용할 수 있지만, 보상·정산은 마감 버전이나 공통 watermark를 사용해야 합니다. 한 샤드가 늦거나 실패하면 결과를 정확한 전역 top-K로 표시하지 않고 부분 결과·오래된 결과·계산 불가 상태를 구분하겠습니다.

검증은 한 샤드에 점수가 몰리는 경우, 동점 경계, 분할 점수 반례, 조회 중 갱신, 중복 사용자, 늦은 샤드를 포함합니다. 작은 데이터는 전체 합산 후 정렬한 기준 결과와 비교하고, 병합 힙의 후보 수·네트워크 전송량·메모리·정확도 상태를 함께 측정하겠습니다.

사용자가 샤드에 겹치지 않게 배치되고 각 샤드의 점수가 완전하다면, 샤드에서 K명 밖인 사용자는 자기 샤드에 이미 K명이 앞서므로 전역 K위가 될 수 없습니다. 그래서 S개 샤드의 후보 최대 S×K명을 같은 비교자로 병합하면 됩니다. 반대로 한 사용자의 점수 조각이 여러 샤드에 나뉘면 각 조각은 top-K 밖이어도 합산 후 상위가 될 수 있어 후보가 누락됩니다.

점수가 계속 갱신되는 동안 병합하면 샤드별 읽기 시점이 달라질 수 있으므로 집계 버전이나 watermark를 요청에 포함합니다. 동점자 전원을 반환하면 후보 K개 상한이 사라져 경계 후보를 추가로 읽거나 전체 집계를 선택해야 합니다. 한 샤드가 실패했는데 낮은 점수로 간주하면 정확한 전역 결과가 아니므로 잠정·부분·확정 상태를 구분하고, 보상은 마감 버전에서 재계산하겠습니다.

샤드별 목록이 이미 내림차순이면 S개 목록의 첫 후보를 최대 힙에 넣고 하나를 꺼낼 때 그 샤드의 다음 후보를 채우는 다중 병합도 가능합니다. K명을 뽑는 병합 자체는 보통 O(S+K log S), 힙 공간은 O(S)입니다. 이는 전송·샤드 조회·버전 검증 비용을 제외한 수치이며, 샤드 점수가 완전하고 동일한 전체 비교 순서를 사용한다는 앞의 조건이 필요합니다.