Re: [Bitobi-arch] [posts] unicité des norl oges et ordre des posts

[Olivier Lourdais]

Estian wrote:

> Olivier Lourdais wrote:
>
> | >
> | >
> | >> toujours pas convaincu que ce soit nécessaire. Amusant, oui, mais pas
> | >> nécessaire. Tu dis que les norloges uniques sont indispensables, 
> je ne
> | >> suis pas d'accord : on ne les a pas aujourd'hui, ça ne nous 
> empêche pas
> | >> de mouler.
> | >>
> | mouais, on n'a pas des horloges uniques, mais on n'en est pas loin non
> | plus : comme il y a une seule machine pour poster, c'est elle qui fixe
> | le numéro mineur de l'horloge (càd le "3" de "42:42:42-3"), même s'il
> | n'apparait pas dans le backend, il est implicite (le numéro d'ordre dans
> | la liste pour les posts datés de la même horloge) et fixe (si il y a
> | parfois des inversions avec wmc², ça vient juste d'un problème de
> | slip/chaussette apparemment). Maintenant c'est vrai qu'on n'utilise pas
>
> ah non , pas du tout efface, les 'numéros de mineures' sont gérés *au
> niveau du coin²*, le backend lui n'en sait rien du tout..

Je le répète : le numéro mineur est _implicite_ c'est-à-dire qu'il peut 
être calculé de façon déterministe depuis les autres infos présentes 
dans le backend (l'horloge + soit l'id soit la position dans la liste 
des posts).

Le point important, c'est que c'est déterministe, c'est dû au fait que 
tout le monde poste sur la même machine, et que donc quand le post est 
rajouté dans la base/le backend/ce_qu'on_veut, on est sûr que _tous_ les 
posts précédents ont déjà été pris en compte.

Maintenant, on perd la propriété de numéro mineur implicite 
déterministe. Même si le tri sur le post/le md5 kipu/l'ip/... permet de 
définir un ordre (arbitraire) qui sera identique sur tout les noeuds (et 
donc qui permet de définir un numéro mineur implicite), cet ordre n'est 
pas stable (un nouveau post peut arriver, s'insérer dans la liste et 
modifier la position des posts déjà présents) : un post peut changer de 
numéro mineur implicite au cours du temps !

> |
> | >
> | > Comme tu le dis, il faut qu'on soit compatible avec les coincoins
> | > existants.
> | >
> | La technique que j'avais proposée assurait justement la compatibilité
> | avec les coincoins existant :)
>
> voui, mais bon, c'est pas la seule permettant de rester compatible, 
> non plus

(J'avais compris qu'on reprochait à ma technique de ne pas garantir la 
compatibilité.)


Bon je reviens un peu sur ma technique.
Pour garantir le fonctionnement des numéros mineurs, on a besoin de deux 
propriétés :
- [1] qu'ils se basent sur un ordre universel (ie identique sur tous les 
backends une fois que tous les posts concernés ont été reçus et traités)
- [2] qu'ils se basent sur un ordre stable (ie qui n'évolue pas dans le 
temps pour un backend donné)

Vous êtes bien d'accord avec moi ?

Actuellement, avec un serveur unique, les 2 propriétés sont vérifiées 
(pour la [1] c'est tautologique, pour la [2] vu que les posts sont pris 
en compte dans l'ordre dans lequel ils sont postés c'est bon). Vous êtes 
toujours d'accord ?
Un algo basé sur les horloges de Lamport garantit aussi les 2 
propriétés, mais il a été établi que ça n'était pas utilisable ici.

Un algo basé sur un tri arbitraire garantit [1] mais pas [2] (cf supra). 
Toujours d'acc ?

Donc ma technique consistait à s'occuper d'abord du point [2], c'est à 
dire que pour une horloge donnée les posts sont insérés dans le backend 
selon leur ordre d'arrivée sur le noeud.
Illustration. Initialement, on a ça dans le backend :
42:42:42 (-1) : plop
42:42:42 (-2) : pika
42:42:43 (-1) : coincoin
42:42:44 (-1) : tchoutchou
Puis arrivent ces posts :
42:42:42 greuuuuu
42:42:43 bonjour
Une fois ces posts traités, le backend contiendra :
42:42:42 (-1) : plop
42:42:42 (-2) : pika
42:42:42 (-3) : greuuuuu
42:42:43 (-1) : coincoin
42:42:43 (-2) : bonjour
42:42:44 (-1) : tchoutchou
Donc ici, l'ordre des numéros mineurs est stable, un post ne change 
jamais de numéro mineur (je l'ai mis entre parenthèses car il est 
implicite).

Bon, comme tous les noeuds ne reçoivent pas les posts dans le même 
ordre, la propriété [1] n'est pas vérifiée.
C'est là qu'intervient ma gruickerie :)
On associe une horloge longue (du style 
01/01/03-12:36:address@hidden) à chaque post, elle lui servira en 
interne d'identifiant unique. Elle est attribuée par le noeud qui a 
servi a poster le message et accompagne le post durant sa diffusion sur 
le résal. Par contre elle n'est pas utilisée par les coincoins, vu 
qu'ils se servent des horloges et id "oldschool".
Donc, sur un noeud donné, correspond à chaque post une horloge longue ET 
une horloge coincoin (que le noeud est capable de calculer).
Quand quelqu'un poste un message via le noeud, on parse le corps du 
message pour retrouver les horloges coincoin et pour chacune de ces 
horloges on ajoute au post une association [horloge coincoin -> horloge 
longue]. Quand un autre noeud traitera ce post, il regardera quelle 
horloge coincoin il associé pour cette horloge longue et fera le 
remplacement kivabien dans le corps du message.

Illustration (on est sur le même noeud que tout à l'heure). Quelqu'un 
poste :
"42:42:42-3 prout 42:42:43-2 salut"
on associe alors au post, par exemple :
[42:42:42-3 -> 01/01/03-42:42:address@hidden [42:42:43-2 -> 
01/01/03-42:42:address@hidden
Sur un autre noeud, on a par exemple :
42:42:42 (-1) : pika
42:42:42 (-2) : greuuuuu
42:42:42 (-3) : plop
42:42:43 (-1) : bonjour
42:42:43 (-2) : coincoin
42:42:44 (-1) : tchoutchou
et à la réception du post les horloges sont remplacées pour obtenir 
"42:42:42-2 prout 42:42:43-1 salut"

Les horloges longues permettent de définir un ordre universel, les 
horloges coincoin respectent un ordre stable. Le seul truc c'est que ce 
ne sont pas les mêmes ordres et qu'il faut gruicker pour passer de l'un 
à l'autre.
Cette technique est gruick, mais au moins elle respecte les DEUX propriétés.