가중치 기반 레저보어 샘플링(weighted reservoir sampling, A-Res)으로 전환한 덕분에, 이제 비디오 홈 페이지를 새로고침할 때마다 24개의 새로운 추천 목록이 표시됩니다. 이번 변경을 통해 이전의 점수 정렬 방식 피드에서 발생했던 "항상 똑같은 그리드만 보이는" 문제를 해결했습니다.

기존 방식이 사용자 경험을 해쳤던 이유

저희는 2시간마다 8개 지역의 최신 트렌딩 비디오를 가져와 SQLite 테이블에 저장합니다. 기존의 단순한 해결책은 전체 세트를 관련성 점수(relevance score)에 따라 정렬한 뒤 상위 24개를 뽑는 것이었습니다. 이 방식은 점수가 가장 높은 항목이 나타나도록 보장하지만, 동시에 그 항목들이 계속 그 자리에 머물게도 만듭니다. 단 하나의 바이럴 영상이 며칠 동안 1위를 독점할 수 있으며, 사용자는 새로고침을 할 때마다 매번 똑같은 그리드만 보게 됩니다.

식상한 경험을 제공하는 것 외에도, 매 요청마다 전체 테이블을 정렬하면 SQLite가 대규모 임시 구조를 메모리에 로드해야 하므로 자원 낭비가 심합니다.

가중치 기반 레저보어 샘플링이 주는 이점

가중치 기반 레저보어 샘플링은 두 가지 문제를 동시에 해결합니다:

  1. 편향성을 갖춘 신선함 – 각 비디오가 선택될 확률은 가중치(예: 관련성 점수)에 비례합니다. 가중치가 두 배인 비디오는 나타날 확률도 두 배가 되지만, 특정 항목이 자리를 차지하는 것이 보장되지는 않습니다.
  2. 메모리 효율성 – 이 알고리즘은 $k$개의 항목으로 구성된 고정된 크기의 "레저보어(reservoir)"만 유지합니다($k = 24$는 저희 피드의 경우). 스트림을 단 한 번의 패스(single pass)로 처리하므로, 후보군이 아무리 많아져도 메모리 사용량은 $O(k)$로 유지됩니다.

핵심 아이디어는 간단합니다. 들어오는 행(row)을 스캔하면서 각 항목에 가중치를 포함한 무작위 키(random key)를 할당한 다음, 가장 높은 키를 가진 $k$개의 항목을 유지하는 것입니다.

실제 알고리즘 적용 방식

각 비디오에 대해 다음 과정을 수행합니다:

  1. 균등 분포 무작위 수 $u \in (0, 1)$를 추출합니다.
  2. 키 $k = u^{(1/\text{weight})}$를 계산합니다.
    (가중치가 높을수록 기대 키 값이 커집니다.)
  3. 현재 상위 $k$개의 키를 저장하는 최소 힙(min-heap)에 항목을 삽입합니다.
    만약 힙의 크기가 $k$를 초과하면, 가장 작은 키를 버립니다.

스트림이 종료되면, 힙에는 표시할 24개의 비디오가 남게 됩니다.

부동 소수점 한계 문제 해결

비디오의 가중치가 매우 클 경우, $u^{(1/\text{weight})}$는 배정밀도(double-precision) 연산에서 1.0과 구별할 수 없는 값으로 수렴하게 됩니다. 이로 인해 가중치가 높은 많은 항목이 동일한 키를 갖게 되어 무작위성을 잃게 됩니다. 해결책은 로그 공간(log space)에서 계산하는 것입니다:

  • 거듭제곱 식 대신 log_key = log(u) / weight를 계산합니다.

로그는 지수 연산을 곱셈 연산으로 바꾸어 주기 때문에, 정밀도 저하 문제를 피하면서도 키의 순서를 그대로 유지할 수 있습니다. 계산 비용도 거의 추가되지 않습니다.

구현 체크리스트

  • 데이터 구조: 크기가 $k$인 최소 힙(우선순위 큐)을 사용하여 가장 큰 키들을 효율적으로 유지합니다($O(\log k)$ per insertion).
  • 수치 타입: $u$와 로그 기반 키에는 64비트 부동 소수점 숫자를 사용합니다. 이는 일반적인 가중치 범위에서 충분한 정밀도를 제공합니다.
  • 통계적 검증: 작은 샘플 세트에 대해 간단한 몬테카를로(Monte-Carlo) 테스트를 실행합니다. 가중치가 10인 항목이 가중치 1인 항목보다 약 10배 더 자주 나타난다면 구현이 올바르게 된 것입니다.
  • 단일 패스 스트리밍: 알고리즘이 사전에 전체 후보 수를 알 필요가 없으므로, 행을 하나씩 반환하는 저희의 SQLite 커서 방식과 자연스럽게 맞습니다.

요약

가중치 기반 레저보어 샘플링을 사용하면 비디오 추천 서비스는 수만 개의 후보를 단 한 번만 훑으면서도 홈 페이지를 신선하게 유지하고, 관련성 점수를 존중하며, 메모리 사용량을 가볍게 유지할 수 있습니다. 키 계산을 로그 공간으로 옮기고 최소 힙을 사용함으로써, 이 방식은 정밀함과 성능을 모두 잡을 수 있습니다.