Indeed I've always thought this was a very cool algorithm.

I once had to extend it for a distributed setting (think mapreduce) where you can cheaply iterate all records but not sequentially. Instead you have multiple reservoirs, and you can't resample those uniformly since each saw a different number of records.

The unbiased way to aggregate 2 reservoirs is to draw a random number from a hypergeometric distribution. You aggregate a larger number by combining 2 at a time.

Fun story, an interviewer at Google once asked me to derive reservoir sampling a long time ago, which I completely wiffed.