▲

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

 (samwho.dev)
1P by GN⁺ 2일전 | ★ favorite | 댓글 1개
  • 저장소 샘플링은 데이터의 크기를 모를 때 공정하게 무작위 샘플을 뽑는 독특하고 효율적인 기법임
  • 전통적 방법을 사용하면 지원되지 않는 상황들을 효율적으로 해결할 수 있다는 점에서 실시간 로그 수집 등 다양한 분야에 활용됨
  • 핵심 아이디어는 새로운 요소가 등장할 때마다 1/n 확률로 저장 공간을 갱신하여, 모든 요소에 동일한 선택 기회를 제공함
  • 여러 개의 샘플을 고를 경우 확률을 k/n로 확장하고, 해당 확률에 따라 무작위적으로 기존 샘플을 대체함
  • 이 알고리듬은 적은 메모리 사용으로도 공정한 샘플링을 보장하며, 실시간 처리의 효율성과 신뢰성을 높여 줌

저장소 샘플링의 개념 및 필요성

  • 저장소 샘플링은 전체 크기를 모르는 데이터 집합에서 공정하게 샘플을 추출하는 효율적인 기법임
  • 일반적인 경우, 데이터의 크기를 알 때는 무작위 인덱스를 뽑는 방식이 효과적이지만, 크기를 모를 경우에는 이러한 방법이 불가능함
  • 선형적으로 도착하는 대량 데이터(예: 로그 스트림)에서 메모리 사용을 제한해야 하며, 동시에 각 데이터가 동일한 확률로 선택될 필요성이 존재함

크기를 아는 경우의 샘플링

  • 제한된 크기의 집합(예: 10장의 카드)에서는 모든 항목을 섞고 앞에서 원하는 만큼 선택하는 셔플 방식이 공정성 보장에 적합함
  • 컴퓨터의 배열 구조를 활용하면, 직접적으로 무작위 인덱스를 선택해 빠르게 샘플을 추출할 수 있음
  • 그러나 실제로 수백만 개의 데이터나 크기를 모르는 스트림에서는 이러한 방식이 비효율적임

크기를 모르는 경우의 샘플링 : 문제점 및 필요성

  • 1개씩 데이터를 순차적으로 받아보면서 오직 1개만 저장할 수 있고, 이미 지난 데이터를 되돌릴 수 없는 상황이 현실에서 자주 발생함
  • 로그 수집 시스템 등에서는 갑작스러운 트래픽 급증이 발생할 수 있으며, 이로 인해 서버 과부하를 방지하기 위해 일부만 샘플링해서 보내야 하는 상황이 존재함
  • 임의로 첫 몇 개만 선택하는 방식은 모든 항목에 동일한 기회를 주지 않기 때문에 공정성 부족 문제를 야기함

저장소 샘플링 알고리듬의 원리

  • 각 데이터가 들어올 때마자 현재까지 받아본 개수 n을 계산하고, 새 데이터가 1/n 확률로 선택되도록 함
  • 최초 데이터는 무조건 선택되고, 이후 각 새로운 데이터는 점점 낮은 확률로 기존 데이터를 대체함으로써 동일 선택 확률을 유지함
  • 마지막까지 저장된 데이터가 전체 중 어느 것이 되어도 확률이 균등해짐
  • 동전 던지기가 아니라 1/n의 확률을 사용하는 방식으로 모든 데이터에 공정한 기회 보장이 실현됨

수학적 직관 (카드 예시 활용 설명)

  • 1번째 데이터: 무조건 선택됨 (확률 1/1 임)
  • 2번째 데이터: 1/2 확률로 선택, 기존 데이터는 50% 확률만 남음
  • 3번째 데이터: 새 데이터는 1/3로 선택, 기존 데이터는 그 확률의 보완값만큼 생존 확률이 누적됨
  • 일반화하면, n번째 데이터까지 포함할 때 항상 1/n의 확률을 모든 데이터가 가짐

여러 개의 샘플 선택 확장 (k-out-of-n)

  • k개의 샘플을 뽑으려면 새로운 데이터가 k/n 확률로 선택되며, 선택 시 현재 저장된 항목 중 랜덤하게 하나를 대체함
  • 이 방식 역시 저장되는 모든 항목이 동일 확률로 샘플로 남게 됨
  • 일정한 메모리(k만큼)만 사용하면서 큰 데이터 스트림에서도 공정하게 여러 샘플을 추출 가능함

로그 수집 서비스에서의 저장소 샘플링 활용

  • 매 초마다 유입되는 로그 중 최대 k개(예: 5개)만 저장소 샘플링 기법으로 고르고, 해당 샘플만 서버로 전송함
  • 데이터가 적을 때는 모든 로그가 전송돼 손실이 없으며, 트래픽 폭증 시에도 k를 초과하여 전송하지 않아 서비스 안정성 보장이 가능함
  • 일정 주기로 샘플을 보냄으로써 실시간성에서 약간의 딜레이가 있지만, 전체적으로 안정성과 비용 효율성 확보에 도움을 줌

추가 응용 및 참고 자료

  • 일부 데이터(예: 에러 로그)가 더 중요하다면 가중치가 적용된 저장소 샘플링(Weighted Reservoir Sampling) 변형을 사용할 수 있음
  • 심화 개념은 위키피디아 등 외부 자료에 실려 있지만, 기본 원리는 공정성 유지임

결론

  • 저장소 샘플링은 크기를 모르는 데이터 스트림에서 메모리 효율적이고 공정하게 샘플링할 수 있는 매우 우아하고 실용적인 알고리듬임
  • 실시간 데이터 처리에서 신속성, 일관성, 낮은 자원 사용이라는 장점으로 인해 많은 분야에서 활용 가치가 높음
▲
GN⁺ 2일전  [-]
Hacker News 의견

  • 어릴 때 시골에서 살던 시절 아버지 친구 분이 매년 직업적으로 산 속의 ptarmigan(뇌조) 개체 수를 측정해야 했음
    지정된 코스를 따라 일정 시간마다 새를 놀래켜 날리면서 숫자를 세는 방식이었음
    그 수치를 담당 사무실에 제출하면 사무실은 전체 개체 수를 추정했음
    어떤 해엔 친구 분이 해외에 계셔서 다른 친구에게 방법을 자세히 설명하고 대신 맡겼음
    그런데 실제 조사 날짜가 됐을 때 그 친구가 그냥 까먹어버렸고, 번거로워서 적당히 그럴듯한 수치를 대충 제출함
    그 다음 해 지역 신문 1면에 “ptarmigan 개체 수 기록적 증가”라는 제목이 실렸음
    이런 급격한 변화가 뉴스거리가 된 이유는, 그 수치가 사냥 허가를 정하는 기준으로 쓰였기 때문임. 친구는 그걸 생각 못한 것임

    • 통계 수치는 믿으면 안 된다는 이야기임
      전에 큰 스키 리조트 예약 시스템 작업을 하다가 공식 통계 보고서(게스트 숙박일 등을 나타내는 정부 제출용)를 끝내야 했음
      시간이 부족해서 밤새 일하는 상황에서, 그 해 통계 자료는 실제 값과 많이 달랐음

  • 안녕하세요! o/
    이 글 작성자임. 질문이나 피드백 환영임
    모든 포스트의 코드는 https://github.com/samwho/visualisations에서 MIT 라이선스로 제공중임. 편하게 사용 가능함

    • 아주 좋은 포스트라고 생각함
      Reservoir sampling을 최적화하는 다른 방향으로, 각 아이템마다 교체 여부를 확인하려고 무작위수를 뽑기보다는, Geometric 분포에서 건너뛰기를 뽑는 방법이 있음
      Tape drive 같이 싸게 여러 개를 건너뛸 수 있을 때 흥미로움 (테이프 길이를 미리 모르지만, 건너뛰는 동안 시스템 대부분을 슬립 상태로 둘 수 있음)
      n개 중 샘플 k개 뽑으려면 대략 O(k * log(n/k))번 샘플링과 스킵만 필요함
      또 내가 선호하는 개념은, 각 카드 도착 시 랜덤한 우선순위를 부여해 상위 k개를 유지하는 방식임
      여기서 연관된 문제로, 길이를 모르는 스트림에서 상위 k개 아이템만 O(n) 시간, O(k) 공간으로 고르는 방법이 있음.
      2*k 사이즈 미정렬 버퍼에 다 집어넣고, 찼을 땐 랜덤화된 퀵셀렉트나 미디안-오브-미디언스를 사용해 상위 k개만 남김
      이 과정을 n번 처리하면 O(n) 시간 필요함
      또 관련 기술로 rendezvous hashing도 흥미로움
      그리고 alias method는 https://www.keithschwarz.com/darts-dice-coins/ 글 참조하면 도움됨

    • 이 방법을 중첩해서 쓸 수 있는지 궁금함
      예시로, 내 서비스에서 reservoir sampling을 하고, 로그 수집기 서비스에서도 reservoir sampling한다면, 로그 수집기 한 번만 사용하는 것과 같아지는지 질문임

    • 애니메이션과 설명이 특히 마음에 들었음
      특히 그래프에서 100번 섞기 등 다양한 상호작용이 인상적임
      처음에는 10장 또는 436,234장에서 3장을 뽑는 내용에서, 갑자기 1장씩만 보고 1장 뽑기 예시로 넘어가서 약간 혼란스러웠음
      “이제 곡선을 던져볼게요!” 부분에서 섹션 구분이 하나 들어가면 더 이해하기 좋을 것 같음.
      이제는 1장만 들고 있다고 가정하고, 덱 크기도 모르는 상황임

    • 사이트 디자인을 특히 좋아함
      상호작용, 강아지 캐릭터, 폰트나 색감, 전체 레이아웃 모두 좋았음

    • 블로그 전체가 보물 창고 같은 느낌임
      발견해서 기쁨을 느낌

    • 그래픽이 마음에 들었음
      다만 이 방법이 통계적으로 완전히 타당한지 확신이 없음. 한 기간 내 모든 로그가 같은 확률로 뽑히긴 한데, ‘느린 기간’에 발생한 로그가 전체 통계에서 과대표집되진 않는지 걱정임
      예를 들어 전체 시스템에서 어떤 엔드포인트가 CPU를 가장 많이 사용했는지 알아내 최적화하려면, Traffic이 일시적으로 폭증하는 엔드포인트의 로그가 과소대표되어 실제로 많이 쓰인 엔드포인트를 제대로 평가하지 못하게 되는 것 아닌지 질문임
      혹은 서비스별 용량 계획 등에서도, 버스트 트래픽 있는 서비스가 과소대표될 것 같음
      Reservoir sampling이 잘 맞는 용도는 무엇인지, 이 방법으로 가능한 통계 분석의 종류가 뭔지 궁금함

    • 아주 좋은 글임, 수학이나 통계는 이런 식으로 가르쳐야 재밌게 배울 수 있을 것임
      https://distill.pub/와 비슷한 느낌을 받았음

    • “Sometimes the hand of fate must be forced”라는 문구가 인상 깊었음

    • 상호작용 방식이 특히 마음에 듦

    • 사이트 디자인과 교수법이 정말 아름답다고 생각함. 고마운 마음임

    • 블로그에 RSS 피드가 있는지 궁금함

  • 아주 명확하고 삽화도 잘 된 포스트임
    더 고급 확장 내용으로, 기본 방법 대신 몇 개씩 건너뛰는 양을 계산하는 알고리즘도 있음
    자세한 설명은 https://richardstartin.github.io/posts/reservoir-sampling 참고할만함

  • 좋은 글과 설명임
    실제 로그 수집엔 다양한 방법을 먼저 시도한 뒤 마지막 수단으로 공정성(fairness)을 사용하는 방향을 추천함
    예를 들어 로그 우선순위를 두고 priority가 낮은(verbosity 높은) 로그 먼저 버림
    의미상 하나의 활동을 이루는 로그들은 중간 반복 로그를 줄이고, 시작·종료·주요 상태 변화만 저장
    유사/중복 로그를 집계하여 요약해 저장하면 전체 용량도 줄이고 트렌드 파악에도 유리함

    • 최근 관측성(observability) 관련해서 많이 알아보고 있는데, 언급된 방법은 head/tail sampling 혼합 방식임.
      https://docs.honeycomb.io/manage-data-volume/sample/에서 관련 설명 참고 가능함

    • 글에서도 이 부분을 다룸
      사실 모든 low priority 로그를 버리기보다는 ‘예산’ 개념을 적용해 제한하는 게 중요함
      전체 로그 수 자체도 별도의 상위 예산으로 제한할 수 있음
      Reservoir sampling은 이런 제약도 잘 처리할 수 있음

  • 좋은 글과 설명임
    Vitter의 논문에서 “Algorithm R”이 설명되고 있는데, reservoir sampling 방식임.
    https://www.cs.umd.edu/~samir/498/vitter.pdf 참고할 수 있음

    • 그런데 그 논문도 "Algorithm R (which is a reservoir algorithm due to Alan Waterman)"라고만 하고 출처를 생략함
      Vitter의 이전 논문 https://dl.acm.org/doi/10.1145/358105.893는 Knuth TAOCP 2권을 인용하는데, Knuth도 명확한 출처 없음

  • 매우 잘 정리되어 있고, weighted reservoir sampling이 궁금하면 https://gregable.com/2007/10/reservoir-sampling.html에서 설명함
    분산 환경에 map-reduce로 쉽게 적용되는 방법도 있고, 아주 간단한 방법으로 각 아이템에 랜덤 값을 짝지어서 Top N을 유지하는 방법도 있음

    • weighted 버전에 대한 두 가지 참고 사항임
      각 아이템마다 POW(RANDOM(), 1.0 / weight)로 우선순위를 뽑아 Top N을 고르는 기본 방법은, 가중치(weight)가 크거나 작을 때 수치 안정을 잃는 문제가 있음
      또 결과 표본이 원래 전체 모집단의 분포를 충분히 반영하지 못할 수도 있음. 특히 전체 weight가 소수 아이템에 몰릴 때 그 경향이 심해짐
      그래도 대부분의 상황에선 충분히 괜찮은 근사임
      자세한 내용은 https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html에서 설명함

  • 이 글을 읽으니 연합군이 2차 대전 때 독일 전차 생산량을 일련번호로 추정했던 방법이 떠오름
    당시 현장 인원들은 실제 생산량보다 약 5배 많다고 추정했으나, 일련번호 방법은 정확도가 90%를 넘었음

  • 훌륭한 게시물이고, 시각화도 정말 뛰어남
    실 서비스에선 비슷한 변형 방식을 사용해, 변화하는 Percentile 값을 매우 큰 스트림에서 실시간 추정함
    percetile 값이 가끔 바뀌지만 보통는 매우 많은 반복 동안 유지됨. 기반 자료가 quasi-stationary임
    splay tree로 백업하면, 다른 방법보다 RAM 사용량 대비 오차 범위는 넓지만 Amortized O(1) 시간으로 추정 가능함
    교체 확률을 조정해 데이터의 ‘half-life’를 줄 수도 있고, 즉 최근 데이터 중심으로 추정값을 편향시키는 것도 가능함

  • 데이터 과학 입장에서는 데이터 양 자체가 중요한 정보를 담으므로, 표집 비율을 반드시 같이 기록해야 한다고 생각함
    예를 들면 표집률이 10%라면 샘플별로 10을 기록해, 전체 카운트, 합, 평균 등을 정확히 복구 및 추정할 수 있음

  • 이 포스트는 telemetry(트레이스, 로그, 메트릭스) 수집이 가진 트레이드오프를 잘 보여주고 있음
    이런 데이터 분석 분야는 진입 장벽이 높고 많은 개발자가 간과하는 영역임

    • 이전부터 생각해온 주제인데, 표집 전략에 따라 그래프의 ‘선 모양’ 자체가 얼마나 많이 달라지는지 보여주는 글을 써보고 싶었음
      같아 보이는 데이터라도 어떤 방법으로 표집했는지에 따라 관찰되는 그래프가 완전히 바뀔 수 있고, 많은 사람들이 이 점을 간과함
답변달기