This makes me wonder if there isn’t some intentional weighting going on, e.g. certain favored pages get space in front of them cleared out so they’re more likely to pop up.
If you do something naive like "ORDER BY RAND() LIMIT 1" performance is worse than abysmal. Similarly, doing a "LIMIT 0 OFFSET RAND() * row_count" is comparably abysmal. While if you do something performant like "WHERE id >= RAND() * max_id ORDER BY id LIMIT 1", you encounter the same problem where the id gaps in deleted articles make certain articles more likely to be chosen.
There are only two "correct" solutions. The first is to pick id's at random and then retry when an id isn't a valid article, but the worry here is with how sparse the id's might be, and the fact it might have to occasionally retry 20 times -- unpredictable performance characteristics like that aren't ideal. While the second is to maintain a separate column/table that includes all valid articles in a sequential integer sequence, and then pick a random integer guaranteed to be valid. But the problem with performance is now that every time you delete an article, you have to recalculate and rewrite, on average, half the entire column of integers.
So for something that's really just a toy feature, the way Wikipedia implements it is kind of "good enough". And downsides could be mitigated by recalculating each article's random number every so often, e.g. as a daily or weekly or slowly-but-constantly-crawling batch job, or every time a page gets edited.
You could also dramatically improve it (but without making it quite perfect) by using the process as it exists, but rather than picking the article with the closest random number, select the ~50 immediately lower and higher than it, and then pick randomly from those ~100. It's a complete and total hack, but in practice it'll still be extremely performant.
Add a column to the article database for "random_index". This gives each article a unique integer index within a consecutive range of 1 to N. To pick a random article, just pick a random number in that range using your favorite random number generator and then look up the row with that random_index value.
The tricky part, obviously, is maintaining the invariant that random index values are (1) randomly assigned and (2) contiguous. To maintain those, I believe it's enough to:
1. Whenever a new article is created, give it random_index N+1. Then choose a random number in the range (1, N+1). Swap the random_index of the new article and the article whose random_index is the number you just rolled. This is the Fisher-Yates step that gives you property (1).
2. Whenever an article is deleted or otherwise removed from the set of articles that can be randomly selected, look up the article with random_index N. Set that article's random_index to the random_index of the article about to be deleted. This gives you property (2).
Yes, this should definitely considered to be the correct, definitive, performant solution then. Thank you!
I think you'll need a full table lock in the case of a race condition trying to do a remove and add at the same time, but that's probably not usually going to be an issue?
> I think you'll need a full table lock in case you're ever trying to do a remove and add at the same time
Yeah, I think you need some sort of locking to ensure N can't be concurrently modified but I'm not a DB person, so I don't know how to go about that.
Also I liked your book.
I believe that for the operation of randomly sampling a single row, only the consecutiveness invariant is needed. The random permutation invariant is unnecessary, because the choice from the range (1, N+1) is random anyway.
However, I can imagine the random permutation invariant being useful for other operations (although I can't immediately think of one).
EDIT: the random permutation invariant could maybe be useful for a list that can be displayed to the user. I can imagine some cases where it is nice to have an order that doesn't change a lot while you don't want it to depend on any property in particular (like the order in which the rows were added).
Is this really a big deal? Surely for a SQL database, looking up the existence of a few IDs, just about the simplest possible set operation, is an operation measured in a fraction of a millisecond. Wikipedia is not that sparse, and a lookup of a few IDs in a call would easily bound it to a worst case of <10 calls and still just a millisecond or two.
My comment covered your suggestion already -- that's why I wrote "you encounter the same problem where the id gaps in deleted articles make certain articles more likely to be chosen".
And you've still got to decide how you're going to pick random ID's from an array of tens of millions of elements that are constantly having elements deleted from the middle. Once you've figured out how to do that efficiently, you might as well skip all the trouble and just use that algorithm on the database itself.
How so? you have array of only valid IDs [1,2,3]
I agree that rerolling is probably a fine strategy, but it's not obvious that everyone would be willing to just trust probability like that. In fact, if you set up your own wiki with 99 bad pages and 1 good page, hitting the random article button won't work most of the time.
You could of course pick a random number from 1 to M, where M is the number of valid articles. But that runs into the same problem of how do you map the 1-to-M number back to an actual article id?
This method may be biased, but it's constant performance.
(I still prefer just keeping all valid articles in memory and choosing a random one of those. There are only 7M as of October, so including the deleted pages, there's probably ~70M, which is on the same order as HN's total item count. Heck, even creating one file per valid article on disk and doing a random search with "find . -type f | shuf -n 1" probably wouldn't be terrible if you cache the result every few seconds, though that'd also be biased in its own way.)
I'd have 1) a remote cache for deleted articles 2) the application servers adding to the remote cache whenever they roll a deleted article. The remote cache can be data-center local and backed by durable storage, with a long TTL. It's possible to not roll un-deleted articles until the cache TTL, but that's ok. Data-center locality ensures some level of fault tolerance and low latency. Durable storage means restarts don't have as much of a cold-cache problem. The ID range maximum water-mark can be updated asynchronously. It's ok if new articles don't show up for a short while.
I suppose current implementation makes sense since the weights would be roughly equal as the number of articles increases, and any individual user is unlikely to care about fairness as long as they get some random article.