5 ms·

I’m shocked at the method for picking a random page. It’s guaranteed to produce permanent biases in the randomization and lots of path dependence in how individ

by jprete 3y ago

I’m shocked at the method for picking a random page. It’s guaranteed to produce permanent biases in the randomization and lots of path dependence in how individual articles’ chances change over time. Picking a random int from 1 to N is not rocket science. 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.

stefan_ 3y ago
If they went to this much trouble it's presumably because selecting a random row is an actually slow operation for their database (and this is a pure gimmick feature so the weighting not being equal is irrelevant). MariaDB suggests that "ORDER BY RAND() LIMIT 1" involves a full table scan..
- WesolyKubeczek 3y ago
  Worse yet, they have had to struggle with MySQL’s idiosyncrasies since at least 3.22. There will be a lot of leftovers from those grim times that used to be “real clever hacks” back in the day.
sillysaurusx 3y ago
How would you do it given that you can't know ahead of time which articles have been deleted? If you pick a random int from 1 to N, there's a probability that you'd get a bad result. If the proportion of bad pages is greater than good pages (a not-unlikely hypothesis given spam) then repeatedly picking a random int from 1 to N will take a few rerolls. 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.)
- deleted 3y ago
  [deleted]
pradn 3y ago
If I had a database with articles (deleted or not), each with an ID, and knowing the ID range at each app server - and I want to roll a random non-deleted article: 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.
omoikane 3y ago
I also thought that the different weights might have been intentional since it reminds me of arithmetic coding[1]. Turns out it was just an accident. 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. [1] https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
crazygringo 3y ago
It is shocking, but what's more shocking is that doing it correctly is kind of rocket science. MySQL simply isn't built for picking a truly random row performantly (I'm not sure if any of the common relational databases are?). 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.
- jonesnc 3y ago
  Why does the randomization have to happen in the database query? Assuming there aren't any large gaps in the distribution of IDs, and if you know the max_id, couldn't you pick a random number between min_id and max_id and get the record whose ID matches that random number?
  - crazygringo 3y ago
    Precisely because of the gaps. Tons of Wikipedia article ID's aren't valid for random selection because they've been deleted, because they're a disambiguation page, because they're a redirect, or they're a talk page or user page or whatever else. 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".

by jprete 3y ago

stefan_ 3y ago

If they went to this much trouble it's presumably because selecting a random row is an actually slow operation for their database (and this is a pure gimmick feature so the weighting not being equal is irrelevant). MariaDB suggests that "ORDER BY RAND() LIMIT 1" involves a full table scan..

WesolyKubeczek 3y ago
Worse yet, they have had to struggle with MySQL’s idiosyncrasies since at least 3.22. There will be a lot of leftovers from those grim times that used to be “real clever hacks” back in the day.

sillysaurusx 3y ago

How would you do it given that you can't know ahead of time which articles have been deleted? If you pick a random int from 1 to N, there's a probability that you'd get a bad result. If the proportion of bad pages is greater than good pages (a not-unlikely hypothesis given spam) then repeatedly picking a random int from 1 to N will take a few rerolls. 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.)

deleted 3y ago
[deleted]

pradn 3y ago

If I had a database with articles (deleted or not), each with an ID, and knowing the ID range at each app server - and I want to roll a random non-deleted article: 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.

omoikane 3y ago

I also thought that the different weights might have been intentional since it reminds me of arithmetic coding[1]. Turns out it was just an accident. 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. [1] https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding

crazygringo 3y ago

It is shocking, but what's more shocking is that doing it correctly is kind of rocket science. MySQL simply isn't built for picking a truly random row performantly (I'm not sure if any of the common relational databases are?). 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.

jonesnc 3y ago
Why does the randomization have to happen in the database query? Assuming there aren't any large gaps in the distribution of IDs, and if you know the max_id, couldn't you pick a random number between min_id and max_id and get the record whose ID matches that random number?
- crazygringo 3y ago
  Precisely because of the gaps. Tons of Wikipedia article ID's aren't valid for random selection because they've been deleted, because they're a disambiguation page, because they're a redirect, or they're a talk page or user page or whatever else. 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".