[X-Istence]

Why not just use UUID 4:

http://en.wikipedia.org/wiki/Universally_unique_identifier#V...

This will have an better distribution for when they are used as keys as well.

[e12e]

As far as I can tell, neither MySQL, nor MariaDB has a function for generating type 4 UUIDs. It's of course possible to generate the UUIDs on the client side, but then it's not really an alternative to auto-incrementing surrogate keys.