Deriva la formula exacta que mide el error de reparto en consistent hashing

Un autor ha publicado en su web una derivacion completa de las formulas que describen como se reparte el trabajo entre servidores en un sistema de hashing consistente. La pieza es parte paper, parte demo interactiva y parte entrada de blog, y termina con una expresion cerrada para el error de reparto en lugar de la cota asintotica que suele aparecer en los apuntes. Es el articulo companero del post que el mismo autor escribio para Cloudflare sobre como usaron estas cuentas para recuperar mas de 100 TB de RAM en el edge.

El resultado

Con N servidores y k hashes por servidor, el error de reparto queda como la raiz de (N-1) dividida entre (kN+1). El autor senala que cuando N es grande la expresion se parece mucho a la raiz de 1/k, que es la cota que se ve habitualmente en la literatura, con una diferencia de alrededor del 1% a partir de unos 50 servidores.

Esa cercania es justamente el problema que queria resolver. La cota asintotica dice como escala el error, pero no cuanto vale en un cluster concreto ni que pasa si cada servidor lleva un numero distinto de hashes. Con la formula cerrada esas preguntas tienen respuesta.

Como llega hasta ahi

El desarrollo no necesita calculo avanzado. El autor remapea el espacio de hashes, que en produccion son enteros de 32 o 64 bits, a numeros reales entre 0 y 1, lo que hace manejable el algebra a cambio de convertir el resultado en una aproximacion.

A partir de ahi trata el anillo como una circunferencia: como no hay puntos privilegiados en la salida de la funcion hash, puede fijar el cero en el hash del propio servidor y olvidarse de la parte circular. El tamano del tramo asignado depende entonces solo del minimo del resto de hashes. De ahi pasa a la funcion de distribucion acumulada y, derivando, a la funcion de densidad de probabilidad, que es lo que permite calcular media y desviacion tipica.

El texto incluye demos en WebAssembly para ver como varia el tamano del tramo asignado entre ejecuciones, ademas de algun chiste suelto entre formulas. El propio autor admite que estadistica fue la unica asignatura que suspendio en la universidad.

Que cambia para quien despliega esto

El hashing consistente esta en casi cualquier sistema que reparta carga entre nodos y asuma que estos entran y salen: caches distribuidas, brokers, almacenes con particionado. El numero de hashes por servidor es una decision de configuracion con coste, y hasta ahora se tomaba a ojo o siguiendo la cota asintotica. Tener la expresion exacta permite dimensionar esa k con criterio y, como en el caso de Cloudflare, detectar cuando se esta pagando memoria de mas por un reparto mas fino del necesario.

Queda por ver si el desarrollo se traslada a herramientas que calculen el error directamente a partir de la topologia de un anillo real, porque el articulo se queda en la parte analitica y en las demos.