Lag y acciones causales en la red (was: Re: [IRC-DEV] CHaN sets mode: +o nick_que_no_esta_en_el_canal)

[Jesus Cea Avion]

> *** NiCk1 ha sido expulsado por [j]ack (kick)
> *** CHaN sets mode: +o NiCk1
> *** NiCk1 ( user at ip.virtual ) entra

Voy a intentar aclarar la situación un poco. Partamos de lo siguiente:

a) La red de IRC es un "spanning tree".

b) Por lo tanto, entre dos nodos de IRC, en un momento dado, existe una
y solo una ruta posible para sus comandos.

c) y, todo comando ejecutado como respuesta a otro es recibido por TODA
la red en la secuencia correcta: Primero el iniciador, y luego la
respuesta.

Las características "a" y "b" se derivan de forma trivial de la
topología "a" (spanning tree), que es la estructura usada por todas las
redes de IRC "normales".

El punto C podría indicar que la red es causal, pero solo lo es en
sentido estricto. Es decir, la red es causal solo cuando se analizan los
comandos de dos servidores, pero no cuando se analiza toda la red.
Lamport (google rules :), hace ya unos años, ya definió el problema de
la causalidad parcial que, entre otras cosas, hace que sea imposible
clasificar en el orden exacto mensajes semicausales recibidos por parte
de varios nodos de la red. Entre otras cosas porque ese orden puede ser
distinto para cada nodo en cuestion.

Supongamos un ejemplo simple:

A -- B -- C -- D

Sean A, B, C y D nodos. Supongamos que el enlace B--C tiene mucho lag.
En un momento determinado, entra un usuario en el nodo B, y un usuario
del nodo A le da op. Más o menos a la vez, entra un usuario en C, y un
usuario en D le da op. Esas órdenes se propagan también por el enlace
B--C. Cuanto más lag tenga ese enlace, más aparente será el problema,
aunque en realidad éste existe SIEMPRE.

El nodo A y B ven la siguiente secuencia de eventos:

a. Entra usuario en B
b. Un usuario de A le da op
c. Entra un usuario en C
d. Un usuario de D le da op.

En cambio la gente que esté conectada por los nodos C y D ven:

a. Entra usuario en C
b. Un usuario de D le da op
c. Entra un usuario en B
d. Un usuario de A le da op.

Dependiendo del retardo en dar op y del lag relativo, casi todas las
combinaciones son posibles. Por ejemplo, el nodo B podría ver:

a. Entra usuario en B
b. Entra usuario en C
c. Un usuario de D le da op al usuario en C
d. Un usuario en A da op a B.

¿Qué representación es correcta?. Las respuesta es... TODAS.

Lo importante es que ver y entender que las relaciones son semicausales.
Es decir, siempre se verá primero la causa y luego el efecto, nunca al
revés. Es decir, siempre se verá entra al usuario en el canal ANTES de
darle OP. Pedro las relaciones causales entre causas independientes no
están determinadas, y cada nodo de la red puede ver una cosa distinta.

Por ejemplo, supongamos el usuario que entra por B. Cuando elcomando de
entrada llega al nodo A, un usuario de ese nodo le puede dar op. A todos
los efectos, un usuario de ese nodo "ve" que el op se lo ha dado un
compañero de A.

No obstante cuando llega la entrada del usuario a D, todavía no ha
llegado el OP, y un usuario local de D puede decidir darle op también.
Los usuarios de D piensan que el op lo han dado ellos.

Mientras tanto, el op de A viaja hacia la derecha y el op de D viaja
hacia la izquierda. Dependiendo de en qué orden llegue cada comando a
cada nodo (que depende de la topología y el LAG), cada nodo intermedio
(incluyendo el propio B) verá que el op lo da alguien distinto.

Esto no suele ocasionar problemas normalmente, y es un "problema" con el
que estamos acostumbrados a lidiar. Pero existen situaciones que lo
hacen evidente y nos hacen ver "cosas raras".

Una de esas situaciones es cuando un server está en DESYNC. Es decir, un
usuario con @ (desde su perspectiva) intenta dar op a otro usuario, y un
server de la otra punta de la red insiste en quitarlo. Eso es porque
para ese nodo remoto, el usuario es cuestión NO tiene el op. ¿Cómo se
soluciona?. Pues quitando los ops del canal y volviéndolos a dar. De esa
forma toda la red tendrá la misma visión de la misma. Este problema
suele ocurrir cuando arranca un nodo desde cero, se "enlaza" a la red y
está despistado sobre qué modelo de red es la que vale, la suya (recién
creada) o la de "la red". Es un problema poco habitual pero que se ve
sin demasiado esfuerzo, de vez en cuando. Sobre todo cuando se realizan
actualizaciones de servers, por los reinicios de demonios y el
consiguiente descontrol sobre quien tiene la red correcta y quien entra
"de guays".

La otra fuente interesante de situaciones curiosas, como las que
ejemplifican el remitente del mensaje original, son las "race
condition".

Supongamos el caso anterior. Un usuario entra por B. Al vez su entrada,
un usuario de A le da op. Cuando la entrada llega a D, un usuario de D
lo kickea, ANTES de haber llegado el op que le dió el usuario de A.
Desde esta perspectiva, el usuario de A ve la entrada, el op y el kick,
mientras que el usuario de D ve la entrada y el kick. El op *NO* debería
verlo, ya que cuando llega, desde su perspectiva, B ya no está en el
canal.

Esto puede parecer incongruente, pero es consistente con la causalidad
parcial, ya que todo el desencadenante es la entrada del usuario B, y
todos van a ver las respuestas como consecuencia de dicha acción
(efectos causales), independientemente unos de otros.

Pero la cosa no acaba aquí. Supongamos, desde la perspectiva de B

a. El usuario de B conecta
b. El usuario de A le da op
c. El usuario de B kickea a un usuario en D.

Pero desde la perspectiva de D, lo que ocurre es:

a. El usuario de B conecta
b. El usuario de D lo kickea
c. Llega el op de A para B (que ya no está en el canal, según nuestra
visión)
d. El usuario D ES KICKEADO por un "fantasma" llamado B, que ya no está
en el canal y que, cuando estaba, ni siquiera llegó a tener OP (desde
nuestra perspectiva).

Si alguien ve esto, que puede ocurrir perfectamente (y cuando hay lag
ocurre y provoca informes de "bugs" y similares :-) pensará en eso de
que "las meigas no existen, pero haberlas hailas"). Pero todo tiene una
explicación clara y evidente si se conoce el funcionamiento del sistema.

El nodo D debe honrar el KICK, aunque el usuario ni siquiera esté en el
canal, porque no hacerlo provocaría un DESYNC. Los nodos A y B verían al
usuario D fuera del canal, mientras que D se considera dentro. Los
usuarios de C verían una cosa o la otra, dependiendo de qué mensajes les
haya llegado primero.

En el caso concreto del ejemplo que puso el remitente original, lo que
el ve es:

a. El usuario entra en el canal.

b. Lo kickeo.

c. Llega un OP para ese usuario, que ya no está, proveniente de CHAN.

Ese OP llega en respuesta al JOIN del usuario, y CHAN lo envía *ANTES*
de ver el KICK.De hecho, en situaciones de lag, podría ser prefectamente
posible que haya nodos (topológicamente entre CHAN y el nodo donde está
el que hace el KICK) que vean como el usuario entra, recibe OP desde
CHAN e, inmediatamente después, es pateado fuera.

Ahora imaginaros los problemas, de cara a la red, de que ese usuario,
justo antes de ser pateado y justo despues de recibir OP, pasa el op a
otro usuario. En esa parte de la red se veria el op de chan, el op del
usuario a otro y el KICK. En la parte del kick, no obstante, se verá la
entrada del usuario, su KICK, la llegada del OP de CHAN (que ya no hace
nada, porque el usuario no está en el canal). Pero... ¿y el op que hace
ese usuario a otro?. ¿Llega?. ¿Se procesa?.

Tendría que mirar los fuentes, pero me inclino a pensar que ese segundo
op se ignorará. Acabamos de generar un desync, ya que la mitad de la red
ve que ese segundo usuario tiene op, y la otra mitad no.

No pasa nada hasta que el usuario en cuestión intenta hacer algo con el
op. Su mitad de la red lo acepta, pero la otra mitad o lo ignora o lo
"rebota". Acabamos de generar un DESYNC.

Cuanto más lag haya en la red, más fácil es que se produzcan este tipo
de situaciones.

¿Soluciones?. Complicadas. Lamport solucionó el problema dándonos un
algoritmo mundialmente famoso para tener causalidad TOTAL en toda una
red, de forma que todos los eventos tengan un orden calculable y
determinado, idéntico para TODA la red. El algoritmo es muy sencillo, y
lo podeis encontrar en cualquier búsqueda de Google, por ejemplo.

Pero en nuestro caso ese algoritmo tiene un problema: requiere que todos
los nodos tengan un lag muy pequeño (sino, el nodo con más lag propaga
su lag a toda la red, aunque sea un nodo pequeñito y sin usuarios),
tiene un consumo de tráfico algo mayor, y cuando se tienen entradas y
salidas de nodos ("netjoins", "splits") las cosas empiezan a "flipar"
durante el periodo de transición.

Un esquema tipo LAMPORT solucionaría todos estos problemas, pero su
coste (lag, el lag de la red es igual al del nodo con más lag, lo que
incluye nodos a punto de caerse por "ping timeout", que pueden ser
varios minutos y complejidad de implementación) no parece justificable
en virtud de que los DESYNC existen, pero si la red tiene poco lag y
pocos "splits", se puede vivir bien con ellos.

-- 
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