저장소 샘플링: 크기를 모르는 데이터에서 공정한 무작위 추출 방법

 (samwho.dev)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 저장소 샘플링은 전체 크기를 모르는 데이터 스트림에서도 정해진 개수만 메모리에 두고 모든 항목에 같은 선택 기회를 주는 추출 기법임
  • 크기를 아는 배열은 섞기나 무작위 인덱스 선택으로 충분하지만, 한 번 지나간 항목으로 돌아갈 수 없는 스트림에서는 다른 접근이 필요함
  • 단일 항목 선택에서는 n번째 항목을 1/n 확률로 채택해 새 항목의 선택 가능성과 기존 항목의 생존 가능성을 균형 있게 맞춤
  • 여러 항목을 뽑을 때는 보관 개수 k에 맞춰 새 항목을 k/n 확률로 채택하고, 필요하면 현재 보관 중인 항목 하나를 무작위로 교체함
  • 로그 수집에 적용하면 초당 최대 5개 같은 처리 상한을 넘기지 않으면서, 조용한 구간의 로그 손실과 메모리 사용량을 함께 줄일 수 있음

크기를 아는 집합에서의 샘플링

  • 10장의 카드에서 3장을 무작위로 뽑는다면, 전체를 섞고 앞의 3장을 고르는 방식만으로 각 카드에 같은 선택 확률을 줄 수 있음
  • 카드가 100만 장으로 늘어나면 직접 섞기 어렵지만, 배열처럼 인덱스로 접근 가능한 구조에서는 무작위 인덱스 3개를 고르면 같은 목적을 달성함
  • 메모리상의 배열은 특정 인덱스 접근이 쉽지만, 카드 더미에서 436,234번째 카드를 세는 식의 작업은 현실적으로 오래 걸림

크기를 모르는 스트림에서 생기는 제약

  • 한 번에 카드 1장만 보고, 동시에 1장만 들고 있을 수 있으며, 지나간 카드로 돌아갈 수 없다면 전체 개수를 모른 채 최종 1장을 골라야 함
  • 로그 수집 서비스도 비슷한 형태의 문제를 만남
    • 다른 서비스에서 로그 메시지를 받아 한곳에 저장함
    • 나쁜 릴리스나 트래픽 급증으로 로그가 몰리면 수집 서비스가 압도될 수 있음
  • 예시의 로그 수집 서비스는 초당 5개 로그를 처리할 수 있는 임계값을 가짐
  • 로그의 10%만 보내는 방식은 급증 구간에서는 임계값을 넘지 않게 해주지만, 조용한 구간에서도 필요 없이 90% 로그를 버림
  • 원하는 동작은 조용한 구간에서는 모든 로그를 보내고, 급증 구간에서는 초당 최대 5개까지만 보내는 방식임
  • 매초 처음 본 5개 로그만 보내면 뒤에 도착한 로그가 선택될 기회를 잃기 때문에 공정하지 않음

단일 항목 저장소 샘플링

  • 저장소 샘플링은 전체 개수를 모르는 상태에서도 지금까지 본 항목들 중 공정한 샘플을 유지함
  • 모든 메시지를 메모리에 저장한 뒤 나중에 고를 수도 있지만, 스파이크 규모를 모르면 필요한 메모리 양도 예측하기 어려움
  • 이 방식은 요청한 샘플 수보다 더 많은 메모리를 쓰지 않으면서 같은 문제를 해결함
  • 단일 카드를 고르는 규칙은 간단함
    • 첫 번째 카드는 항상 보관함
    • n번째 새 카드는 1/n 확률로 보관함
    • 새 카드를 보관하기로 하면 기존 보관 카드는 버림
  • 매 카드마다 50% 확률로 교체하면 뒤쪽 카드가 유리해져 공정하지 않음
    • 첫 번째 카드는 10번째 카드 이후에도 남으려면 여러 번의 교체 기회를 모두 살아남아야 함
    • 마지막 카드는 한 번만 선택되면 손에 남을 수 있음
  • 1/n 규칙은 새 카드의 선택 확률뿐 아니라 기존 카드의 생존 확률까지 맞춤
    • 첫 번째 카드는 1/1, 즉 100% 확률로 보관됨
    • 두 번째 카드에서는 새 카드가 1/2 확률로 선택되고, 첫 번째 카드도 1/2 확률로 남음
    • 세 번째 카드에서는 새 카드가 1/3 확률로 선택되고, 기존 보관 카드도 50% × 2/3으로 1/3 확률이 됨
  • 일반적으로 n번째 단계에서 기존 카드가 남을 확률은 1/(n-1) * (1-(1/n))이고, 새 카드가 선택될 확률은 1/n으로 같아짐

여러 항목을 뽑는 확장

  • 단일 항목 선택은 여러 항목 선택으로 확장할 수 있음
  • k개의 항목을 선택하려면 규칙 두 가지가 달라짐
    • 새 항목은 1/n이 아니라 k/n 확률로 선택됨
    • 교체가 필요하면 현재 보관 중인 k개 항목 중 하나를 무작위로 골라 새 항목으로 바꿈
  • 기존 항목의 선택 확률은 k/(n-1)로 표현되고, 새 항목으로 교체되지 않을 확률을 곱해 공정성이 유지됨
  • 보관 중인 모든 항목이 같은 확률로 교체 대상이 되므로, 매 단계에서 각 항목이 계속 남을 가능성도 같게 유지됨
  • 구현은 크기 k의 배열을 두는 방식으로 정리됨
    • 새 항목마다 0부터 n 사이의 무작위 수를 생성함
    • 무작위 수가 k보다 작으면 해당 인덱스의 항목을 새 항목으로 교체함
    • 그렇지 않으면 새 항목을 버림

로그 수집 서비스에 적용하기

  • 로그 수집 예시에서는 k=5로 설정해 한 번에 최대 5개 로그 메시지만 보관함
  • 매초 선택된 로그를 로그 수집 서비스로 보내고, 이후 크기 5 배열을 비운 뒤 다시 시작함
  • 이 방식은 실시간 로그 스트림 대신 일정 간격으로 로그 묶음을 보내는 덩어리진 패턴을 만듦
  • 대신 전송된 로그 수는 임계값을 넘지 않고, 조용한 구간에서는 전체 로그와 전송 로그가 거의 같이 움직임
  • 조용한 구간에서는 로그를 잃지 않고, 급증 구간에서는 초당 임계값보다 많은 로그를 보내지 않으며, 저장 공간도 k=5개 로그를 넘지 않음

가중치가 필요한 경우

  • 일부 로그는 다른 로그보다 더 가치가 있을 수 있음
  • 예를 들어 오류 로그는 모두 보관하고 싶을 수 있음
  • 이런 경우에는 가중치 기반 저장소 샘플링 변형을 사용할 수 있음
  • 저장소 샘플링은 처음에는 불가능해 보이는 스트림 샘플링 문제를 적은 메모리로 풀 수 있게 해주는 알고리듬임

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 어릴 때 시골에 살았는데, 아버지 친구가 직업상 매년 산에서 바위뇌조 개체 수를 세어야 했다고 들었음
    정해진 경로를 걸으며 일정 간격마다 새를 놀라게 해 날아오르게 한 뒤 숫자를 세고, 그 합계를 관청에 제출하면 전체 개체 수 추정에 쓰였다고 함
    어느 해에는 조사 시기에 해외에 나가야 해서 친구에게 방법을 자세히 알려주고 대신 부탁했는데, 그 친구가 당일에 잊어버렸고 번거롭기도 해서 대충 그럴듯한 숫자를 제출했음
    다음 해 지역 신문 1면에 바위뇌조 개체 수 기록적 증가라는 제목이 났는데, 그 추정치가 사냥 허가량을 정하는 데 쓰인다는 점을 그 친구가 생각하지 못했던 것임
    https://en.wikipedia.org/wiki/Rock_ptarmigan

    • 통계는 믿으면 안 됨
      예전에 꽤 큰 스키 리조트들의 예약 시스템을 만들었는데, 일정이 늦어져 밤샘 작업을 하던 중 마지막으로 끝내야 했던 것 중 하나가 정부가 발표하는 숙박객 수 같은 공식 통계 보고서였음
      그해 통계는 현실과 거의 관련이 없었다고만 해두겠음

  • 이 글의 작성자임. 질문이 있으면 답할 수 있고, 피드백도 환영함
    모든 글의 코드는 https://github.com/samwho/visualisations에 있으며 MIT 라이선스라 자유롭게 써도 됨

    • 좋은 글임
      저수지 샘플링을 더 흥미롭게 확장하면, 각 항목마다 난수를 뽑아 교체 여부와 대상을 정하는 대신 기하분포에서 값을 뽑아 다음 교체 전까지 안전하게 건너뛸 항목 수를 정할 수 있음
      테이프 드라이브를 빨리 감을 수 있지만 전체 길이는 모른다거나, 건너뛰는 동안 시스템 대부분을 절전 상태로 둘 수 있는 경우처럼 많은 항목을 싸게 건너뛸 수 있으면 특히 유용함
      n개 중 k개를 뽑을 때 이 방식은 대략 O(k * log (n/k))번 샘플링과 건너뛰기를 함
      개념적으로는 각 카드가 도착할 때 고정된 무작위 우선순위를 부여하고 우선순위 상위 k개만 유지하는 저수지 샘플링 버전을 더 선호함
      여기서 이어지는 문제는 길이를 모르는 스트림에서 상위 k개를 O(n) 시간과 O(k) 공간으로 고르는 것임. 단순하게 최소 힙을 유지하면 O(k) 공간은 되지만 O(n log k) 시간이 듦
      대신 최대 2k 용량의 순서 없는 버퍼를 두고 항목을 추가하다가 가득 차면 무작위 quickselect나 median-of-medians로 O(k)에 상위 k개만 남기면 됨. 전체 n개에 대해 k개마다 O(2k) 일을 하므로 O(n) 실행 시간이 나옴
      관련 주제로 rendezvous hashing도 있음: https://en.wikipedia.org/wiki/Rendezvous_hashing
      곁가지로, 이산 확률분포에서 샘플링하는 별칭 방법에 대한 좋은 글도 있음: https://www.keithschwarz.com/darts-dice-coins/
    • 이 방법은 자기 자신과 합성해도 되나? 예를 들어 내 서비스에서 저수지 샘플링을 하고, 로그 수집 서비스도 저수지 샘플링을 하면, 결과가 로그 수집 서비스만 했을 때와 같아지는지 궁금함
    • 애니메이션과 설명이 정말 좋았고, 특히 그래프 형태에서 앞으로 끌어보거나 shuffle 100 times를 클릭할 수 있는 부분이 마음에 들었음
      다만 처음에는 10장 또는 436,234장의 덱에서 카드 3장을 무작위로 고르는 이야기였다가 갑자기 카드 1장만 고르는 이야기로 바뀌어서 잠깐 헷갈렸음
      “이제부터는 카드 3장이 아니라 1장만 들고 있고, 덱 크기도 모른다는 단순화된 가정으로 전환한다”는 식의 섹션 제목이 “Now let me throw you a curveball...” 앞에 있으면 더 명확할 듯함
    • 사이트 디자인이 아주 좋음. 상호작용 요소, “관객” 역할의 강아지 캐릭터, 글꼴·색상·레이아웃까지 전부 마음에 들었고 글도 좋았음
    • 그래픽이 정말 좋았음
      다만 이 접근의 통계적 타당성을 잘 이해했는지는 모르겠음. 특정 기간의 모든 로그가 포함될 확률이 같다는 건 알겠지만, 그러면 “느린 시간대”에 발생한 로그가 전체 지표에서 과대대표되는 것 아닌가?
      예를 들어 전체 플릿의 총 비용(CPU-초 등)을 줄이기 위해 어떤 엔드포인트가 시간을 가장 많이 쓰는지 알고 싶다면, 버스트성 트래픽을 받는 엔드포인트가 꾸준한 트래픽을 받는 엔드포인트보다 과소대표될 수 있어 이 방법은 부적절해 보임
      그러면 실제로 트래픽이 많지 않은 엔드포인트를 최적화하느라 시간을 낭비할 수 있음
      서비스별 용량 계획에서도 버스트성 트래픽을 받는 서비스가 과소대표되는 게 맞는지 궁금함
      저수지 샘플링은 어떤 사용 사례에 적합하고, 반환된 데이터로 어떤 통계 분석을 할 수 있는지 알고 싶음

  • 글과 설명이 훌륭함
    실무적인 관점에서는 그래도 로그 수집에 이 방식을 가장 마지막으로 쓸 것 같음. 급증이 생기면 뭔가는 버려야 한다는 점은 이해하지만, 무엇을 버려야 하느냐가 핵심임
    무엇을 버릴지 “공정하게” 정하는 데 큰 의미가 있어 보이진 않음
    낮은 우선순위 로그부터 버리는 편이 낫고, debug/info/warning/error 같은 로그 수준이 있다면 심각도가 높은 이벤트를 우선하고 장황한 debug 로그를 먼저 버릴 수 있음
    또 로그 시퀀스를 하나의 활동 일부로 묶어, 성공한 활동은 시작과 종료 또는 핵심 상태 변화만 기록하고 반복적인 중간 로그는 빼는 방식도 가능함
    급증 시 모든 로그 줄을 저장하기보다 비슷하거나 중복된 메시지를 집계·요약하면 양도 줄고 추세도 더 잘 드러남

    • 최근 관측 가능성 쪽을 깊게 보고 있는데, 설명한 방식은 아마 헤드 샘플링과 테일 샘플링의 조합에 가까움: https://docs.honeycomb.io/manage-data-volume/sample/
    • 글에서 이 부분을 다룸. 실제로는 낮은 우선순위 로그를 전부 버리고 싶은 게 아니라 예산 안으로 제한하고 싶은 것임
      그리고 수집되는 전체 로그 줄 수도 더 큰 예산으로 제한하고 싶음. 저수지 샘플링은 이런 것을 모두 처리할 수 있음
    • 가능하면 일부 항목을 버리거나 합치는 게 맞지만, 그렇게 하고 남은 중요한 항목도 여전히 너무 많아서 무작위로 줄여야 할 수 있음. 시스템이 막히는 것보다는 뭐든 낫기 때문임
      공정한 저수지 샘플링도 통제된 방식으로 불공정하게 만들 수 있음. 예를 들어 내용이 특히 흥미로운 항목은 유지 확률을 높일 수 있음
      최후의 수단으로는 덜 원칙적인 편향 무작위 선택이나 무작위조차 아닌 선택 알고리즘과 경쟁하는 기법임

  • 정말 잘 쓰이고 잘 시각화된 글임
    고급 확장으로는 레코드마다 시행을 하는 대신 건너뛸 레코드 수를 계산하는 알고리즘들이 있음. 이에 대한 좋은 글은 여기 있음: https://richardstartin.github.io/posts/reservoir-sampling

  • 가중 저수지 샘플링 변형은 ReSTIR(실시간 광선 추적을 위한 시공간 저수지 재샘플링)에서 쓰임. 이는 내장된 시공간 노이즈 제거를 가진 확률적 빛 전달 추정기임
    빛 전달 추정기는 장면을 통과하는 빛의 양을 계산하려고 함(https://en.wikipedia.org/wiki/Radiance). 이를 위해 에너지 보존을 유지하면서 빛이 갈 수 있는 모든 경로의 radiance를 적분해야 함(https://en.wikipedia.org/wiki/Rendering_equation)
    아주 단순한 경우를 제외하면 렌더링 방정식의 이 적분은 다루기 쉬운 닫힌형 해가 없어서 확률적으로 풀어야 함
    기본 아이디어는 몬테카를로 방법(https://en.wikipedia.org/wiki/Monte_Carlo_method)으로, 가능한 경로를 무작위로 많이 샘플링해 평균을 내는 것임
    이후 수십 년 동안 중요도 샘플링(IS), 다중 중요도 샘플링(MIS), 샘플 중요도 재샘플링(SIR), 재샘플링 중요도 샘플링(RIS), 가중 저수지 샘플링(WRS), 그리고 RIS와 WRS를 결합한 ReSTIR 같은 더 정교한 전략이 발전했음
    자세한 글은 여기 있음: https://agraphicsguynotes.com/posts/understanding_the_math_b...

  • 이걸 보니 연합군이 일련번호로 독일 전차 수를 추정했던 알고리즘을 더 생각해봐야겠다는 생각이 듦
    현장 추정은 실제 생산량의 약 5배였지만, 일련번호 기법은 90% 넘게 정확했음

  • 좋은 글이고 설명도 훌륭함. 이건 Vitter가 아마 처음 설명했을 Algorithm R을 다룬 것으로 보임: https://www.cs.umd.edu/~samir/498/vitter.pdf

    • 그 논문에는 “Algorithm R은 Alan Waterman의 저수지 알고리즘”이라고 되어 있지만 인용은 없음
      Vitter의 이전 논문 https://dl.acm.org/doi/10.1145/358105.893은 Knuth의 TAOCP 2권을 인용하고, Knuth에는 다시 인용이 없음

  • 데이터 과학 관점에서는 데이터 양 자체도 매우 중요한 정보를 담으므로, 각 데이터 포인트가 몇 개를 대표하는지도 로그에 남기는 게 좋음
    예를 들어 샘플링 비율이 10%라면 10을 담는 필드를 두면, count·sum·average 같은 대부분의 통계를 다시 구성하고 추정할 수 있음

  • 구성도 좋고 설명도 잘 되어 있음. 가중치 버전이 궁금하다면 여기서 조금 설명해둔 적이 있음: https://gregable.com/2007/10/reservoir-sampling.html
    MapReduce로 쉽게 만들 수 있는 분산 버전도 있음
    아주 단순한 알고리즘으로는 스트림의 각 항목마다 무작위 쌍을 만들고, 그 무작위 값 기준 상위 N개를 유지하는 방법도 가능함

    • 가중치 버전에 대해 두 가지가 있음
      첫째, POW(RANDOM(), 1.0 / weight)로 순위를 매긴 뒤 상위 N개를 고르는 직관적인 구현은 가중치가 매우 크거나 작을 때 수치 안정성 문제가 있음
      둘째, 결과 샘플은 기대값 기준으로도 원 모집단과 같은 분포를 갖지 않음. 전체 가중치가 소수의 모집단 원소에 집중될수록 특히 그렇지만, 많은 경우에는 쓸 만한 근사임
      이 문제들은 여기서 더 다뤘음: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....

  • 훌륭한 글이고 접근하기 쉬우며 시각화도 뛰어남
    $WORK에서는 이와 비슷한 변형을 써서, 실행 중인 스트림에서 어떤 백분위수를 추정하는 관련 문제를 풀고 있음
    선택하려는 백분위수는 가끔 바뀌지만 대체로 1조 번 이상의 반복 동안 고정되어 있고, 기본 데이터는 준정상적이라는 제약이 있음
    이 과정을 스플레이 트리로 받치면 상각 O(1) 백분위수 추정이 가능함. 같은 RAM 사용량에서 다른 여러 기법보다 오차 범위는 크지만 매우 빠름
    교체 확률을 조절해 시간이나 개수 기준의 “데이터 반감기”를 두고 최근 이벤트 쪽으로 추정을 편향시킬 수도 있는데, 어떤 문제에는 이 편이 더 적합함

답변달기