This reminds me that I need to spend more time thinking about the algorithm the allies used to count German tanks by serial number. The people in the field estimated about 5x as many tanks as were actually produced but the serial number trick was over 90% accurate.
Reservoir Sampling
21–30 of 107 posts
Re: Reservoir Sampling
#22Earlier quoted context omitted.
I didn't know about the algorithm until after I got hired there. It's actually really useful in a number of contexts, but my favorite was using it to find optimal split points for sharding lexicographically sorted string keys for mapping. Often you will have a sorted table, but the underlying distribution of keys isn't known, so uniform sharding will often cause imbalances where some mappers end up doing far more wor…
Interesting idea, hadn’t that about that way to apply it. I knew it from before my interview from a turbo pascal program I had seen that sampled dat tape backups of patient records from a hospital system. These samples were used for studies. That was a textbook example of it’s utility.
I guess the question in my mind is: would you expect a smart person who did not previously know this problem (or really much random sampling at all) to come up with the algorithm on the fly in an interview? And if the person had seen it before and memorized the answer, does that provide any signal of their ability to code?
Re: Reservoir Sampling
#23Earlier quoted context omitted.
Love your website’s design, I find all of interactivity, the dog character as an “audience”, and even the font/color/layout wonderful. Loved the article too!
Thank you so much! The dogs on the playing cards were commissioned just for this post. They’re all made by the wonderful https://www.andycarolan.com/ . The colour palette is the Wong palette that I learned about from https://davidmathlogic.com/colorblind/ . Oh, and you can pet the dogs. :)
It would've been easy to just use green for the held card and red for the discard pile.
Thank you for using a colour-blind friendly palette; as someone with deuteranopia :)
Re: Reservoir Sampling
#24Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)
I loved the "Sometimes the hand of fate must be forced" comment!
Re: Reservoir Sampling
#25Earlier quoted context omitted.
Love your website’s design, I find all of interactivity, the dog character as an “audience”, and even the font/color/layout wonderful. Loved the article too!
Thank you so much! The dogs on the playing cards were commissioned just for this post. They’re all made by the wonderful https://www.andycarolan.com/ . The colour palette is the Wong palette that I learned about from https://davidmathlogic.com/colorblind/ . Oh, and you can pet the dogs. :)
Just noticed the physics simulator at the top is interactive. Then I was stacking squares on top of each other to see how tall I could make it, and started throwing things at it angry birds style. Fun stuff.
Re: Reservoir Sampling
#26This reminds me that I need to spend more time thinking about the algorithm the allies used to count German tanks by serial number. The people in the field estimated about 5x as many tanks as were actually produced but the serial number trick was over 90% accurate.
https://en.wikipedia.org/wiki/German_tank_problem
It seems like it could have some utility in places where hyperloglog isn’t quite right. YouTube recommendations pointed me at a Numberphile video on this a couple weeks ago:
Re: Reservoir Sampling
#27Hello! o/ I’m the author of this post. Happy to answer any questions, and love to get feedback. The code for all of my posts can be found at https://github.com/samwho/visualisations and is MIT licensed, so you’re welcome to use it :)
I loved the graphics!
However, I'm not sure I understand the statistical soundness of this approach. I get that every log during a given period has the same chance to be included, but doesn't that mean that logs that happen during "slow periods" are disproportionately overrepresented in overall metrics?
For example, if I want to optimize my code, and I need to know which endpoints are using the most time across the entire fleet to optimize my total costs (CPU-seconds or whatever), this would be an inappropriate method to use, since endpoints that get bursty traffic would be disproportionally underrepresented compared to endpoints that get steady constant traffic. So I'd end up wasting my time working on endpoints that don't actually get a lot of traffic.
Or if I'm trying to plan capacity for different services, and I want to know how many nodes to be running for each service, services that get bursty traffic would be underrepresented as well, correct?
What are the use-cases that reservoir sampling are good for? What kind of statistical analysis can you do on the data that's returned by it?
Re: Reservoir Sampling
#28Great article and explanation.
On a practical level though, this would be the last thing I would use for log collection. I understand that when there is a spike, something has to be dropped. What should this something be?
I don't see the point of being "fair" about what is dropped.
I would use fairness as a last resort, after trying other things:
Drop lower priority logs: If your log messages have levels (debug, info, warning, error), prioritize higher-severity events, discarding the verbose/debug ones first.
Contextual grouping: Treat a sequence of logs as parts of an activity. For a successful activity, maybe record only the start and end events (or key state changes) and leave out repetitive in-between logs.
Aggregation and summarization: Instead of storing every log line during a spike, aggregate similar or redundant messages into a summarized entry. This not only reduces volume but also highlights trends.
Re: Reservoir Sampling
#29Great article and explanation. On a practical level though, this would be the last thing I would use for log collection. I understand that when there is a spike, something has to be dropped. What should this something be? I don't see the point of being "fair" about what is dropped. I would use fairness as a last resort, after trying other things: Drop lower priority logs: If your log messages have levels (debug, info…
I’ve been down the observability rabbit hole recently, and what you’re describing is probably a mix of head and tail sampling: https://docs.honeycomb.io/manage-data-volume/sample/
Re: Reservoir Sampling
#30Great article and explanation. On a practical level though, this would be the last thing I would use for log collection. I understand that when there is a spike, something has to be dropped. What should this something be? I don't see the point of being "fair" about what is dropped. I would use fairness as a last resort, after trying other things: Drop lower priority logs: If your log messages have levels (debug, info…
I’ve been down the observability rabbit hole recently, and what you’re describing is probably a mix of head and tail sampling: https://docs.honeycomb.io/manage-data-volume/sample/
honeycomb seems quite mature, thanks.