- Reservoir Sampling é uma técnica única e eficiente para selecionar uma amostra aleatória de forma justa quando o tamanho dos dados é desconhecido
- É usada em diversas áreas, como coleta de logs em tempo real, por resolver com eficiência situações que métodos tradicionais não conseguem atender
- A ideia central é atualizar o espaço de armazenamento com probabilidade de 1/n sempre que um novo elemento aparece, dando a todos os elementos a mesma chance de serem escolhidos
- Ao selecionar várias amostras, a probabilidade é ampliada para k/n, e uma amostra existente é substituída aleatoriamente de acordo com essa probabilidade
- O algoritmo garante amostragem justa com baixo uso de memória e aumenta a eficiência e a confiabilidade do processamento em tempo real
Conceito e necessidade de Reservoir Sampling
- Reservoir Sampling é uma técnica eficiente para extrair amostras de forma justa de um conjunto de dados cujo tamanho total é desconhecido
- Em casos comuns, quando o tamanho dos dados é conhecido, escolher um índice aleatório é eficaz, mas isso se torna impossível quando o tamanho é desconhecido
- Em grandes volumes de dados que chegam de forma linear, como um fluxo de logs, é necessário limitar o uso de memória e, ao mesmo tempo, garantir que cada item tenha a mesma probabilidade de ser selecionado
Amostragem quando o tamanho é conhecido
- Em um conjunto de tamanho limitado, como 10 cartas, o método de embaralhar todos os itens e escolher a quantidade desejada no início é adequado para garantir justiça
- Aproveitando a estrutura de array do computador, é possível selecionar índices aleatórios diretamente e extrair amostras rapidamente
- Porém, em fluxos com milhões de dados ou tamanho desconhecido, essa abordagem é ineficiente
Amostragem quando o tamanho é desconhecido: problemas e necessidade
- Na prática, é comum haver situações em que os dados chegam um a um, só é possível armazenar 1 item, e não dá para voltar aos dados já passados
- Em sistemas de coleta de logs, por exemplo, pode ocorrer um aumento repentino de tráfego, exigindo o envio de apenas uma parte dos dados para evitar sobrecarga do servidor
- Escolher arbitrariamente apenas os primeiros itens não dá a todos a mesma oportunidade, causando falta de justiça
Princípio do algoritmo de Reservoir Sampling
- Sempre que um dado entra, calcula-se n, o número total de itens recebidos até então, e o novo dado passa a ter probabilidade 1/n de ser escolhido
- O primeiro dado é sempre selecionado e, depois disso, cada novo dado substitui o anterior com probabilidade cada vez menor, mantendo a mesma probabilidade de seleção
- No final, qualquer item do conjunto terá a mesma chance de ser o dado armazenado
- Em vez de lançar uma moeda, usa-se a probabilidade 1/n para garantir a todos os dados uma chance justa
Intuição matemática (explicação com exemplo de cartas)
- 1º dado: é sempre selecionado (probabilidade 1/1)
- 2º dado: é selecionado com probabilidade 1/2, e o dado anterior permanece apenas com 50% de chance
- 3º dado: o novo dado é selecionado com 1/3, enquanto os anteriores acumulam sua probabilidade de sobrevivência pelo valor complementar
- Generalizando, ao incluir o n-ésimo dado, todos os dados sempre ficam com probabilidade 1/n
Expansão para seleção de várias amostras (k-out-of-n)
- Para selecionar k amostras, cada novo dado é escolhido com probabilidade k/n e, quando isso ocorre, substitui aleatoriamente um dos itens atualmente armazenados
- Esse método também faz com que todos os itens armazenados permaneçam na amostra com a mesma probabilidade
- Usando apenas memória constante (proporcional a k), é possível extrair várias amostras de forma justa mesmo em grandes fluxos de dados
Uso de Reservoir Sampling em serviços de coleta de logs
- Entre os logs recebidos a cada segundo, seleciona-se no máximo k itens (por exemplo, 5) com Reservoir Sampling, e apenas essas amostras são enviadas ao servidor
- Quando há pouco dado, todos os logs são enviados sem perdas; mesmo em picos de tráfego, não se envia mais que k, o que ajuda a garantir a estabilidade do serviço
- Enviar amostras em intervalos regulares introduz um pequeno atraso em tempo real, mas no geral contribui para estabilidade e eficiência de custos
Aplicações adicionais e materiais de referência
- Se alguns dados, como logs de erro, forem mais importantes, pode-se usar a variação Weighted Reservoir Sampling, que aplica pesos
- Conceitos mais avançados podem ser encontrados em materiais externos, como a Wikipédia, mas o princípio básico continua sendo a manutenção da justiça
Conclusão
- Reservoir Sampling é um algoritmo elegante e prático para fazer amostragem justa e eficiente em memória em fluxos de dados de tamanho desconhecido
- Em processamento de dados em tempo real, ele tem grande valor de aplicação por oferecer rapidez, consistência e baixo uso de recursos
1 comentários
Comentários no Hacker News
Quando eu era criança e morava no interior, um amigo do meu pai tinha como trabalho medir todo ano a população de ptarmigan (lagópodes) nas montanhas
O método era seguir uma rota definida e, em intervalos regulares, assustar os pássaros para fazê-los voar e então contá-los
Ele enviava esses números ao escritório responsável, e o escritório estimava a população total com base neles
Em certo ano, esse amigo estava no exterior, então explicou o método em detalhes a outro amigo e pediu que o substituísse
Mas, quando chegou o dia real da pesquisa, esse amigo simplesmente esqueceu e, por achar trabalhoso, mandou números inventados que pareciam plausíveis
No ano seguinte, a manchete de capa do jornal local foi “Aumento recorde da população de ptarmigan”
Isso virou notícia porque esses números eram usados para definir as permissões de caça. O amigo não tinha pensado nisso
Uma vez, trabalhando no sistema de reservas de uma grande estação de esqui, precisei concluir o relatório estatístico oficial enviado ao governo, com dados como diárias de hóspedes
Sem tempo e virando a noite, os dados estatísticos daquele ano ficaram bem diferentes dos valores reais
Olá! o/
Sou o autor deste texto. Perguntas e feedback são bem-vindos
O código de todos os posts está disponível sob licença MIT em https://github.com/samwho/visualisations. Usem à vontade
Acho que este é um post excelente
Em outra direção de otimização do reservoir sampling, em vez de sortear um número aleatório para verificar a cada item se ele substitui outro, dá para sortear saltos a partir de uma distribuição geométrica
Isso é interessante em algo como tape drive, onde dá para pular vários itens a baixo custo (você não sabe o comprimento da fita de antemão, mas pode deixar a maior parte do sistema em modo de suspensão enquanto pula)
Para selecionar k amostras entre n itens, você precisa de aproximadamente O(k * log(n/k)) operações de amostragem e salto
Outro conceito de que gosto é atribuir uma prioridade aleatória a cada carta conforme ela chega e manter as k maiores
Um problema relacionado aqui é como selecionar apenas os top k itens de um stream de comprimento desconhecido em tempo O(n) e espaço O(k).
Você coloca tudo em um buffer não ordenado de tamanho 2*k e, quando ele enche, usa quickselect aleatorizado ou median-of-medians para manter só os top k
Processando isso n vezes, você obtém tempo O(n)
Outra técnica relacionada interessante é rendezvous hashing
E, sobre o alias method, este texto ajuda: https://www.keithschwarz.com/darts-dice-coins/
Fiquei curioso se esse método pode ser usado de forma aninhada
Por exemplo, se eu fizer reservoir sampling no meu serviço e o serviço coletor de logs também fizer reservoir sampling, isso fica equivalente a usar apenas o coletor de logs uma vez?
Gostei especialmente da animação e da explicação
Principalmente das várias interações no gráfico, como embaralhar 100 vezes
No começo, falando de escolher 3 cartas entre 10 ou 436.234, e de repente mudar para o exemplo de ver apenas 1 carta por vez e escolher 1, isso me confundiu um pouco
Na parte “Agora vamos jogar uma curva nisso!”, acho que ficaria mais fácil de entender se houvesse uma divisão de seção ali.
Agora estamos assumindo que você só pode segurar 1 carta e nem sabe o tamanho do baralho
Gostei especialmente do design do site
As interações, o personagem cachorro, as fontes, as cores e o layout geral, tudo ficou muito bom
O blog inteiro parece um baú de tesouros
Fiquei feliz por tê-lo descoberto
Gostei dos gráficos
Mas não tenho certeza de que esse método seja estatisticamente totalmente válido. Todos os logs dentro de um período acabam com a mesma probabilidade de serem escolhidos, mas será que logs gerados em “períodos lentos” não ficam super-representados nas estatísticas gerais?
Por exemplo, se eu quiser descobrir qual endpoint consumiu mais CPU no sistema inteiro para otimizá-lo, não pode acontecer de logs de endpoints cujo tráfego explode temporariamente ficarem sub-representados e, com isso, eu não conseguir avaliar corretamente quais endpoints realmente são mais usados?
Ou, em coisas como planejamento de capacidade por serviço, também parece que serviços com tráfego em rajadas ficariam sub-representados
Para que tipo de uso o reservoir sampling é mais adequado e que tipos de análise estatística são possíveis com esse método?
Ótimo texto, matemática ou estatística deveriam ser ensinadas assim para serem divertidas de aprender
Me passou uma sensação parecida com https://distill.pub/
A frase “Sometimes the hand of fate must be forced” me marcou
Gostei especialmente da interatividade
Acho o design do site e a forma de ensinar realmente lindos. Obrigado
Fiquei curioso se o blog tem feed RSS
É um post muito claro e muito bem ilustrado
Como extensão mais avançada, também existem algoritmos que calculam quantos itens pular de cada vez, em vez de usar o método básico
Para uma explicação detalhada, vale ver https://richardstartin.github.io/posts/reservoir-sampling
Ótimo texto e ótima explicação
Para coleta real de logs, eu recomendaria primeiro tentar vários métodos e deixar a fairness como último recurso
Por exemplo, priorizar logs e descartar primeiro os de prioridade baixa (mais verbosos)
Em logs que semanticamente representam uma única atividade, reduzir os logs repetitivos do meio e manter apenas início, fim e mudanças importantes de estado
Se você agregar logs semelhantes/duplicados e armazená-los em forma de resumo, reduz o volume total e ainda facilita perceber tendências
Tenho pesquisado bastante sobre observability recentemente, e o método citado é uma forma híbrida de head/tail sampling.
Dá para consultar a explicação relacionada em https://docs.honeycomb.io/manage-data-volume/sample/
O texto também aborda esse ponto
Na verdade, em vez de simplesmente descartar todos os logs de baixa prioridade, o importante é aplicar o conceito de “orçamento” para limitá-los
O número total de logs também pode ser limitado por um orçamento superior separado
Reservoir sampling também lida bem com esse tipo de restrição
Ótimo texto e ótima explicação
No artigo do Vitter, é explicado o “Algorithm R”, que é uma forma de reservoir sampling.
Pode consultar https://www.cs.umd.edu/~samir/498/vitter.pdf
Um artigo anterior do Vitter, https://dl.acm.org/doi/10.1145/358105.893, cita o volume 2 do TAOCP do Knuth, mas o próprio Knuth também não dá uma fonte clara
Está muito bem organizado e, se você tiver curiosidade sobre weighted reservoir sampling, há uma explicação em https://gregable.com/2007/10/reservoir-sampling.html
Também existe um método fácil de aplicar em ambiente distribuído com map-reduce e um método muito simples de manter o Top N associando um valor aleatório a cada item
O método básico de sortear a prioridade de cada item com POW(RANDOM(), 1.0 / weight) e então selecionar o Top N perde estabilidade numérica quando o peso (
weight) é muito grande ou muito pequenoAlém disso, a amostra resultante pode não refletir suficientemente a distribuição da população original. Isso é especialmente forte quando o peso total está concentrado em poucos itens
Ainda assim, na maioria das situações, é uma aproximação boa o bastante
Mais detalhes em https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html
Lendo este texto, lembrei do método usado pelos Aliados na Segunda Guerra para estimar a produção de tanques alemães por meio dos números de série
Na época, o pessoal em campo estimava um número cerca de 5 vezes maior que a produção real, mas o método pelos números de série teve precisão superior a 90%
Excelente post, e as visualizações são realmente impressionantes
Em produção, usamos uma variação parecida para estimar em tempo real valores de percentil variáveis em streams muito grandes
Os valores de percentile às vezes mudam, mas normalmente permanecem por um número muito grande de repetições. Os dados de base são quasi-stationary
Com backup em splay tree, dá para estimar em tempo amortizado O(1), embora com uma faixa de erro maior por uso de RAM do que outros métodos
Também é possível ajustar a probabilidade de substituição para reduzir a “half-life” dos dados, ou seja, enviesar a estimativa em direção aos dados mais recentes
Do ponto de vista de ciência de dados, a própria quantidade de dados contém informação importante, então acho que a taxa de amostragem deve ser registrada junto
Por exemplo, se a taxa de amostragem for 10%, registrar 10 em cada amostra permite reconstruir e estimar corretamente contagens totais, somas, médias etc.
Este post mostra bem os trade-offs da coleta de telemetry (traces, logs, metrics)
Essa área de análise de dados tem uma barreira de entrada alta e é algo que muitos desenvolvedores deixam passar batido
Mesmo quando os dados parecem iguais, o gráfico observado pode mudar completamente dependendo de como a amostragem foi feita, e muita gente deixa isso passar batido