InnoDB appears to contain two different implementations of a random number generator: page_cur_lcg_prng() and ut_rnd_gen_next_ulint(). Both suffer from a scalability issue (and race condition) due to sharing the internal state between multiple threads.

We should investigate whether replacing the linear congruential generator with a Galois linear-feedback shift register would improve the performance, and we should attempt to use thread-local storage for the seed values.

Last but not least, the function page_cur_open_on_rnd_user_rec() is using a linear search for positioning the cursor, instead of invoking page_rec_get_nth().

Side note: It appears that pick_next() causes crashes in ./mtr --suite=innodb_gis if the sequence of random numbers is replaced with a constant.