[IRC-DEV] Comentarios: Procesado O(n^2) en la gestión de baneos durante un BURST

[Jesus Cea Avion]

Esto lo hemos vivido hoy en nuestras carnes, con un canal que tenía más
de 6.000 "bans". A Gaia le costaba casi 10 minutos hacer el "netjoin".

Cuando dos trozos de la red se unen, se intercambian los "bans" de cada
canal, entre otras muchas cosas. El hecho es que el procesado actual de
"bans" durante el BURST es de complejidad cuadrática respecto al número
de "bans" presentes en el canal.

Esto es así porque cuando llega un "ban" a un canal, se compara con
todos los que ya hay en dicho canal, y detectar así duplicados o
conversiones de "bans" a otros más generales. Eso supone que si llegan
10 banes, el número de comparaciones son:

0+1+2+3+4+5+6+7+8+9 = 45 (El cuarto "ban" que llega, debe compararse con
los tres anteriores, etc).

En cambio si tenemos 15 baneos, las cuentas son:

0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19 = 190

Asintóticamente, el tiempo de procesado es proporcional aproximadamente
al cuadrado del número de "bans" en el canal. Es decir, si procesar 60
"bans" nos lleva un segundo, por ejemplo, procesar 6.000 nos llevaría
10.000 segundos, o 2 horas, 46 minutos y 40 segundos.

Obviamente esto es un problema, que ha quedado muy patente hoy a medio
día con el canal que tenía 6.000 baneos. No voy a dar detalles del canal
en cuestión ni cómo se ha producido este caso. Es confidencial :-). Pero
sí interesa qué hacer al respecto.

Baste decir que a mediodía un "netjoin" suponía que el nodo que
conectaba validase 36.451.299 "bans" (si, 36 millones). En un UltraSparc
I antiguo, he calculado que cada comparación consumía en torno a 1900
ciclos de reloj de CPU, lo que es una barbaridad para una comparación,
pero no lo es tanto si consideramos que las comparaciones que se están
haciendo incluyen soportes de máscaras "*" y "?", la arroba, etc.

Es decir, se hacen un número cuadrático de comparaciones, y cada
comparación es lenta en sí misma. Receta para el desastre.

Imaginemos ahora el siguiente caso: La red unida y un canal con 75
"bans". Ahora un server se va en "split". Cada lado del split evoluciona
a su aire y, tras un rato, un lado de la red tiene 78 baneos y el otro
80. De esos, 75 son los viejos, que son comunes a ambos lados.

Cuando se une la red, un extremo envía 78 baneos al otro lado, y el otro
lado nos manda 80 hacia nosotros. De esos baneos, la mayoría, 75, son
comunes e iguales en ambos extremos, por lo que hacer una comparación "a
lo burro" con máscaras y todo es absolutamente innecesario. Basta con
una comparación directa "strcmp()" antes de machacarnos las máscaras en
sí, con comodines y todo lo demás.

Esto reduciría bastante el consumo de CPU cuando un servidor se va y
vuelve más tarde, ya que muchos de los "bans" se podrán comparar de
forma rápida, aunque su complejidad siga siendo cuadrática.

Queda el caso de un nodo al que le llegan decenas, cientos o miles de
"bans" nuevos en el burst. Es el caso, por ejemplo, de un nodo que se
actualiza, arranca desde cero, y se intenta conectar a la red. ¿Qué
hacer en este caso?.

No hay soluciones sencillas. Una que se me ha ocurrido es que cuando
llegan "bans" a través de un BURST, *SOLO* se comparen con "bans" que
tenga el servidor y que no hayan llegado a través de ESE "burst". ¿por
qué?. Porque se supone que los "bans" que nos llegan por un "burst" ya
han sido filtrados y consolidados convenientemente por el otro extremo.

Es decir, si un nodo acaba de arrancar y se conecta a su HUB, no
necesita comprobar los "bans" que le manda el HUB porque a) el nodo que
arranca no tiene ninguno y b) los "bans" que llegan ya han sido
comprobados por el HUB.

Este esquema tiene muchas complicaciones, no obstante. La más evidente
es cómo separar los "bans" que nos llegan por el burst de los que ya
tenemos, sobre todo considerando que en un canal con muchos "bans",
éstos pueden verse repartidos en varias líneas de BURST, y que entre
esas lineas un usuario local puede inyectar un "ban" nuevo. El otro
problema, que afecta a los HUBS, es que pueden haber varios BURST en
curso, para diferentes servidores, en un momento dado.

Una posibilidad sería tener una variable global "burst". Dicha variable
se incrementa cada vez que se inicia un burst NUEVO por un enlace. A
dicho enlace, que tendrá una variable extra, se le añade un campo nuevo,
que indique si está en BURST o no, y si está en BURST, qué "número de
burst" le toca.

Cada BAN tiene un número de BURST. Este número se asigna así: los "bans"
activados en un BURST, heredan su número de BURST. En otro caso, el
número de BURST del "ban" es CERO.

A la hora de comparar un "ban" con los que ya hay:

a) Si el número de BURST de ese "ban" es cero, se compara con todos.

b) Si el número de BURST de ese "ban" *NO* es cero, se compara con todos
los "bans" que *NO* compartan el mismo número de BURST.

Este sistema soluciona los dos problemas señalados: que se nos cuele el
procesamiento de comandos ajenos al burst en medio del burst, y que haya
varios burst en curso en un momento dado.

Si el contador global de BURST tiene 32 bits, nos proporciona cuatro mil
millones de burst posibles antes de ver "cosas raras". Si se hiciera un
burst por segundo, estaríamos hablando de 136 años, así que no lo veo
problemático.

¿Ideas?. ¿Sugerencias?.

Por favor, pensad *MUY* bien las cosas antes de sugerir nada. No me
hagais perder el tiempo. No me mandeis ninguna idea que no hayais
pensado con calma y detenimiento durante al menos una horita :-)

-- 
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
jcea at argo.es http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
                                      _/_/    _/_/          _/_/_/_/_/
PGP Key Available at KeyServ   _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz