Live data from Hacker News

Reservoir Sampling

samwho.dev

31–40 of 107 posts

Re: Reservoir Sampling

#31
post #3

Hello! 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 :)

This is really beautiful design, and excellent teaching. Thank you!

Re: Reservoir Sampling

#32
post #16
post #3

Hello! 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 :)

Does your blog have an RSS feed?

Looks like it - https://samwho.dev/rss.xml

Re: Reservoir Sampling

#33
post #3

Hello! 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 :)

Does this method compose with itself? E.g. if I implement reservoir sampling in my service and then the log collector service implements reservoir sampling, is the result the same as if only the log collector implemented it?

Yes

Re: Reservoir Sampling

#34
post #3

Hello! 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 e…

Good question. I'm not sure how suitable this would be to then do statistical analysis on what remains. You'd likely want to try and aggregate at source, so you're considering all data and then only sending up aggregates to save on space/bandwidth (if you were at the sort of scale that would require that).

The use-case I chose in the post was more focusing on protecting some centralised service while making sure when you do throw things away, you're not doing it in a way that creates blind-spots (e.g. you pick a rate limit of N per minute and your traffic is inherently bursty around the top of the minute and you never see logs for anything in the tail end of the minute.)

A fun recent use-case you might have seen was in https://onemillionchessboards.com. Nolen uses reservoir sampling to maintain a list of boards with recent activity. I believe he is in the process of doing a technical write-up that'll go into more detail.

Re: Reservoir Sampling

#35
post #24
post #3

Hello! 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!

Recovering WoW addict. :)

Re: Reservoir Sampling

#36

This is a great post that also illustrates the tradeoffs inherent in telemetry collection (traces, logs, metrics) for analysis. It's a capital-H Hard space to operate in that a lot of developers either don't know about, or take for granted.

Something I've considered writing about in the past is how sampling affects the shape of lines on graphs. Render the same underlying data with different sampling strategies and show how the resulting graph can look extremely different depending on the strategy used. I think it's an underappreciated thing a lot of people don't think about when looking at their observability tools.

Re: Reservoir Sampling

#37
post #25
post #11

Earlier quoted context omitted.

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.

Something no one seems to have realised yet is that the hero simulation at the top of the page is using reservoir sampling to colour 3 of the shapes black.

Re: Reservoir Sampling

#38
post #22

Earlier quoted context omitted.

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?

My gut instinct is no. I certainly don't think I'd be able to derive this algorithm from first principles in a 60 minute whiteboarding interview, and I worked at Google for 4 years.

Re: Reservoir Sampling

#40

Great 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…

The article addressed this. In fact, you don't typically want to throw away all of the low priority logs ... you just want to limit them to a budget. And you want to limit the total number of log lines collected to a super budget.

Reservoir sampling can handle all of that.

Post reply on HN