Generador de Números Aleatorios de MySQL

MySQL y MariaDB tienen una función RAND que se supone que devuelve números aleatorios. Sin embargo, los números que devuelve no son particularmente aleatorios.

Cómo funciona

MySQL y MariaDB tienen una función RAND que devuelve un número «aleatorio». De la documentación de MariaDB:

Devuelve un valor de punto flotante de doble precisión aleatorio v en el rango 0 <= v < 1.0.

El generador de números pseudoaleatorios (PRNG) mantiene dos variables de estado y las modifica cada vez que se llama de la siguiente manera:

seed1 = (seed1 * 3 + seed2) % 0x3FFFFFFF
seed2 = (seed1 + seed2 + 33) % 0x3FFFFFFF
return seed1 / 0x3FFFFFFF

Puedes encontrar el código fuente de MySQL y MariaDB.

Semilla

Los valores iniciales de seed1 y seed2 se derivan de la hora actual. Una instancia PRNG global se siembra primero con la hora en segundos:

my_rnd_init(&sql_rand,(ulong) server_start_time,(ulong) server_start_time/2);

Luego, un PRNG específico del hilo se siembra desde el PRNG global, más algo:

tmp= (ulong) (my_rnd(&sql_rand) * 0xffffffff);
my_rnd_init(&rand, tmp + (ulong)((size_t) &rand), tmp + (ulong) ::global_query_id);

::global_query_id es un contador de consultas, que siempre es 1 cuando se inicia el servidor.

(ulong)((size_t) &rand es la dirección actual de la estructura PRNG específica del hilo en la memoria. Es diferente para cada hilo.

El PRNG se siembra cuando se crea un nuevo hilo, pero no cuando se establece una nueva conexión.

Problemas

30 bits

Las operaciones se realizan módulo 0x3FFFFFFF, o 2³⁰ – 1. Entonces, los números aleatorios contienen como máximo 30 bits de entropía, o poco más de mil millones de resultados posibles. Si intentas crear números aleatorios más grandes que ese, algunos números nunca serán elegidos. Por ejemplo, la siguiente consulta siempre devuelve un número par:

SELECT RAND() * 0x7FFFFFFE;

Módulo 33

Hay tres operaciones realizadas en el generador de números aleatorios:

• suma de 33,
• multiplicación por 3,
• módulo 0x3FFFFFFF.

0x3FFFFFFF es divisible limpiamente por 33. Si el generador de números aleatorios se siembra con valores que son divisibles por 33, permanecen así. Ninguna de las operaciones anteriores va a cambiar un número divisible por 33 a uno que no lo sea.

Esto también se cumple si las semillas son divisibles por 11. Ninguna de las operaciones anteriores va a cambiar la semilla a algo que no sea divisible por 11.

Si las semillas no son divisibles por 33 o 11, el generador de números aleatorios aún se atasca en un grupo donde solo genera ciertos números módulo 33.

Esto afecta solo a los bits menos significativos, por lo que al hacer RAND() * 10 esto no será notable. Sin embargo, reduce significativamente la cantidad de bits utilizables en el PRNG. Con una semilla divisible por 33, la siguiente consulta devuelve solo números pares:

SELECT RAND() * 65075262;

Semillas

El PRNG global se siembra con la hora actual y la hora actual dividida por dos. Estos valores no son particularmente aleatorios y también están relacionados entre sí. Arriba dijimos que el PRNG se comporta mal si ambas semillas son divisibles por 11. Si ambas semillas fueran independientes, esto sucedería una vez cada 11 × 11 o 121 veces. Sin embargo, dado que seed2 es la mitad de seed1, esto ahora sucede cada 22 veces.

El PRNG específico del hilo tampoco está sembrado muy bien. Primero, se crea una variable común a ambas semillas:

tmp= (ulong) (my_rnd(&sql_rand) * 0xffffffff);

Sin embargo, my_rnd aquí devuelve un número aleatorio de 30 bits entre 0 y 1. Multiplicar esto por 0xffffffff intenta crear un número aleatorio de 32 bits a partir de un número aleatorio de 30 bits. Como resultado, los bits inferiores no son particularmente aleatorios.

Luego, inicializa el PRNG específico del hilo:

my_rnd_init(&rand, tmp + (ulong)((size_t) &rand), tmp + (ulong) ::global_query_id);

Agrega una dirección de memoria a la primera semilla. Dado que las estructuras están alineadas en memoria, esto siempre es un múltiplo de 8, pero eso no es realmente un problema después de que el PRNG lo reduce a módulo 0x3FFFFFFF. Si el sistema tiene aleatorización del diseño del espacio de direcciones (ASLR), el kernel coloca el proceso en un lugar aleatorio en el espacio de direcciones de memoria. La dirección &rand también será bastante aleatoria, causando una buena semilla para el PRNG.

Se supone que ASLR mantiene las direcciones de memoria en secreto, para que sea más difícil explotar desbordamientos de búfer. Usar una dirección como semilla para el PRNG expone un poco de información del espacio de direcciones al usuario. Esto podría comprometer ASLR: un atacante puede leer las semillas del PRNG y determinar dónde está el proceso en la memoria. El PRNG expone solo un poco de información de la dirección, pero este patrón de usar direcciones de memoria conlleva un riesgo de seguridad.

Aunque el proceso está en un lugar aleatorio en la memoria, los datos de los hilos están todos en el mismo proceso. Entonces, las semillas de los diferentes PRNG específicos del hilo difieren entre sí en una cantidad específica no aleatoria.

Semillas bajas

Si ambas semillas son bajas, los valores no se envuelven. Si los valores están muy por debajo del módulo (0x3FFFFFFF), las operaciones de ×3 y +33 son solo eso, y la salida simplemente se hace lentamente más grande con cada paso.

MariaDB> set session rand_seed1 = 123, rand_seed2 = 456;
MariaDB> select * from numbers order by rand();
+------+
| num  |
+------+
|    1 |
|    2 |
|    3 |
|    4 |
|    5 |
|    6 |
|    7 |
|    8 |
|    9 |
|   10 |
+------+
10 rows in set (0.001 sec)

Hay más semillas que exhiben un comportamiento tan estable, como 0x3FFFFFFF / 3.

Repeticiones

El PRNG de MySQL también es propenso a repetirse con una probabilidad relativamente alta después de un cierto número de iteraciones.

Si creamos dos listas de n números aleatorios, ¿cuáles son las posibilidades de que la entrada superior de ambas listas sea la misma? En otras palabras, ¿el PRNG se repite después de n llamadas? Para un PRNG de 30 bits, esperaríamos que esta probabilidad sea 2⁻³⁰, independientemente de n. Para el PRNG de MySQL, esta probabilidad es mayor de lo esperado para algunos n:

• n = 960, probabilidad de 1/449829, 2⁻¹⁹
• n = 22800, probabilidad de 1/92349, 2⁻¹⁶
• n = 91200, probabilidad de 1/2979, 2⁻¹²

Período bajo

El PRNG vuelve al mismo estado después de como máximo 83265600 iteraciones, después de lo cual repite la misma secuencia. Esto es un poco más de 2²⁶. Para un PRNG que mantiene 60 bits de estado, esperaríamos que esto esté más cerca de 2⁶⁰.

Distribución

Una forma sencilla de elegir una fila aleatoria de una tabla relativamente pequeña es la siguiente:

SELECT * FROM table ORDER BY RAND() LIMIT 1

Esto devuelve la fila para la cual RAND() devuelve el valor más bajo. Para algunos tamaños de tabla, esto funciona bastante mal. Si la tabla tiene 2400 filas, algunos elementos tienen 40 veces más probabilidades de ser elegidos que otros elementos.

Simulé la consulta anterior un millón de veces y tracé los resultados en un gráfico. La línea naranja muestra la distribución para una muestra realmente aleatoria. La línea azul muestra cuántas veces se seleccionan los elementos con consultas simuladas ORDER BY RAND() en una tabla de 2400 filas.

El eje x muestra la cantidad de veces que se elige una fila determinada, y el eje y muestra cuántas filas se eligen tantas veces. Por ejemplo, en el primer pico azul de la izquierda, vemos que hay 2 filas que se eligen 28 veces. Para la serie naranja, realmente aleatoria, vemos una distribución normal alrededor de 420, como se esperaba. Para la serie azul, MySQL RAND, vemos un comportamiento realmente no aleatorio. Algunas filas se eligieron 460 veces, algunas filas se eligieron 490 veces, pero ni una sola fila se eligió 475 veces.

Además, la distribución es mucho más amplia de lo esperado. Algunas filas se eligieron solo 28 veces, lo cual es muy poco probable con una distribución aleatoria.

La posición de estos picos cambia cuando se vuelve a sembrar el PRNG. Por lo tanto, resembrar regularmente el PRNG puede dar una mejor distribución de las filas elegidas.

Punto fijo

Existen semillas para las que el PRNG se atasca en un bucle y siempre genera el mismo número «aleatorio». Por ejemplo:

seed1 = 1073741790 = -33 (mod 0x3FFFFFFF)
seed2 = 66

En una ronda de PRNG, hace:

seed1 = seed1 × 3 + seed2, so seed1 = -33 × 3 + 66 = -33
seed2 = seed1 + seed2 + 33, so seed2 = -33 + 66 + 33 = 66

Ambas semillas permanecen iguales, por lo que el PRNG siempre genera el mismo número.