Horloges de Lamport et vectorielles en Go : ordonner des événements sans horloge partagée

En 1978, Leslie Lamport a fait remarquer que « avant » n'a presque rien à voir avec le temps. L'événement a est avant l'événement b seulement si a a pu influencer b : ils sont sur la même machine, ou une chaîne de messages les relie. Si aucun des deux ne peut atteindre l'autre, demander lequel est venu en premier n'a pas de réponse.

Cela ressemble à un détail philosophique, jusqu'à ce que votre résolution de conflit en dépende. Les horloges murales ne tranchent pas : les serveurs dérivent, les corrections NTP les font sauter, et un écart de 3 ms entre deux réplicas est largement dans la marge d'erreur de la plupart des installations. Même une horloge logique peut tromper. L'horloge de Lamport classique donne des horodatages différents à neuf paires d'événements sans lien sur dix (mesuré plus bas), comme si l'un était clairement venu avant.

Cet article construit les maths qui corrigent cela, un ordre qui admet des paires incomparables, et deux algorithmes qui l'implémentent, les horloges de Lamport et les horloges vectorielles, en Go. C'est le deuxième d'une série sur les maths au cœur des systèmes distribués, après le consistent hashing.

Les maths : « avant » est un ordre partiel

Partons de ce qu'on veut vraiment savoir. Pour deux événements a et b, on veut répondre : a a-t-il pu influencer b ? Leslie Lamport a défini cela en 1978 comme la relation happened-before (« s'est produit avant »), notée a → b, avec trois règles :

1. Si a et b sont sur le même processus et que a vient en premier, alors a → b.
2. Si a envoie un message et que b reçoit ce même message, alors a → b.
3. Si a → b et b → c, alors a → c (transitivité).

Rien ici ne mentionne une horloge. On suit seulement la cause et l'effet : la suite d'étapes d'un processus, et les messages entre processus.

Cette relation est un ordre partiel, et le mot partiel compte. Un ordre total comme 1 < 2 < 3 compare deux éléments quelconques. Un ordre partiel admet des paires simplement non comparables. Pensez à un arbre généalogique : un grand-parent vient avant ses petits-enfants dans la lignée, mais deux cousins ne sont ni ancêtre ni descendant l'un de l'autre. Formellement, happened-before est :

• irréflexive : aucun événement ne se produit avant lui-même,
• transitive : si a → b et b → c alors a → c,
• antisymétrique : a → b et b → a ne peuvent jamais être vrais ensemble.

Deux événements sans a → b ni b → a sont dits concurrents, notés a ∥ b. Concurrent ne veut pas dire « au même instant ». Cela veut dire que ni l'un ni l'autre n'a pu connaître l'autre. Détecter ce cas est tout l'enjeu : ce sont exactement les événements dont le système doit décider l'ordre exprès, ou signaler comme conflit.

Le vrai objectif est donc d'attacher une étiquette à chaque événement pour que comparer les étiquettes retrouve →. Les horloges de Lamport font la moitié du travail, les horloges vectorielles le font entièrement.

Horloges de Lamport : un compteur par processus

L'idée est un seul entier par processus. Règles :

• Avant tout événement local ou envoi, incrémentez votre compteur.
• Joignez le compteur à chaque message envoyé.
• À la réception, mettez votre compteur à max(le vôtre, celui du message) + 1.

type Lamport struct{ t uint64 }

// Tick : événement local ou envoi.
func (c *Lamport) Tick() uint64 { c.t++; return c.t }

// Recv : max avec l'horodatage du message, puis tick.
func (c *Lamport) Recv(m uint64) uint64 {
    if m > c.t {
        c.t = m
    }
    c.t++
    return c.t
}

Ce que ça garantit

Notons L(a) l'horodatage de l'événement a. La garantie, appelée condition d'horloge, est :

a → b   implique   L(a) < L(b)

La preuve est courte et suit les trois règles. Sur un même processus le compteur ne fait qu'augmenter (règle 1). Une réception met le compteur au-dessus de l'horodatage de l'envoi (règle 2). Et < sur les entiers est transitif (règle 3). Donc si a peut influencer b, a a toujours le plus petit numéro.

Ce que ça ne garantit pas

La flèche ne va que dans un sens. L(a) < L(b) n'implique pas a → b. Une exécution concrète à trois processus le montre :

L(e6) = 1 est plus petit que L(e3) = 3, donc les nombres suggèrent que e6 est venu avant. Mais C n'avait rien reçu de A ni de B quand e6 s'est produit : les deux sont concurrents. Les horloges de Lamport fabriquent un ordre qui n'existe pas.

Ce n'est pas un cas tordu. Sur 10 000 exécutions aléatoires de 4 processus (environ 6,7 millions de paires d'événements), 59,9 % des paires étaient concurrentes, et Lamport a donné des horodatages différents à 90,0 % de ces paires concurrentes, qui paraissent donc ordonnées. La condition d'horloge elle-même a tenu à chaque fois, comme la preuve le dit.

Où c'est quand même utile

Si vous avez seulement besoin d'un ordre qui respecte la causalité, Lamport suffit, pour le prix d'un entier par message. Pour en faire un ordre total, départagez les égalités avec l'id du processus : triez par (L, processID). Chaque nœud dérive alors la même séquence des mêmes événements, ce qui fonde les logs répliqués simples et l'exclusion mutuelle distribuée. Ce que vous ne pouvez pas faire, c'est demander « ces deux événements étaient-ils concurrents ? ».

Horloges vectorielles : un compteur par processus, gardé par tous

Pour détecter la concurrence il faut garder plus d'information. Au lieu d'un entier, chaque processus garde un vecteur : un compteur pour chaque processus. L'entrée V[B] veut dire « combien d'événements de B je connais ».

Règles :

• Sur un événement local ou un envoi, incrémentez votre propre entrée.
• Joignez le vecteur entier à chaque message.
• À la réception, prenez le maximum composante par composante de votre vecteur et de celui du message, puis incrémentez votre propre entrée.

type VClock map[string]uint64

func (v VClock) Tick(id string) { v[id]++ }

func (v VClock) Recv(id string, m VClock) {
    for k, x := range m {
        if x > v[k] {
            v[k] = x
        }
    }
    v[id]++
}

Les maths : comparer des vecteurs

On ordonne deux vecteurs composante par composante. V ≤ W veut dire que chaque entrée de V est au plus égale à l'entrée correspondante de W. V < W veut dire V ≤ W et qu'ils ne sont pas égaux.

C'est encore un ordre partiel, et c'est exactement pourquoi ça marche. Deux vecteurs peuvent être incomparables : [A:3, B:0] et [A:1, B:2] ont chacun une entrée plus grande que l'autre, donc aucun n'est ≤ à l'autre. Le théorème :

a → b    si et seulement si    V(a) < V(b)
a ∥ b    si et seulement si    V(a) et V(b) sont incomparables

Notez le si et seulement si. Contrairement à Lamport, les horloges vectorielles préservent l'ordre dans les deux sens. L'intuition : V(a)[i] compte les événements du processus i qui sont dans le passé causal de a. Si a est dans le passé de b, tout ce qui est dans le passé de a est aussi dans celui de b, donc chaque entrée de V(b) est au moins aussi grande, et b lui-même en ajoute une. Si a n'est pas dans le passé de b, b n'a pas vu au moins un événement que a a vu, et une entrée de V(b) est plus petite. La comparaison tient alors en quelques lignes :

func Compare(a, b VClock) Order {
    aLE, bLE := true, true // a <= b ?   b <= a ?
    for k, x := range a {
        if x > b[k] {
            aLE = false
        }
    }
    for k, x := range b {
        if x > a[k] {
            bLE = false
        }
    }
    switch {
    case aLE && bLE:
        return Equal
    case aLE:
        return Before
    case bLE:
        return After
    }
    return Concurrent
}

Sur la même exécution que ci-dessus, les deux méthodes diffèrent exactement sur la paire qui compte :

Comparer e3 et e6 donne concurrent (aucun vecteur n'est ≤ à l'autre), alors que Lamport disait que e6 était venu avant. Comparer e3 et e7 donne avant, ce qui est correct : e3 → e4 → e5 → e7 par les messages.

Vérifier l'affirmation

Je ne voulais pas me fier à la seule preuve. J'ai généré 10 000 exécutions aléatoires (4 processus, 40 pas, envois et réceptions aléatoires), calculé la vraie relation happened-before par fermeture transitive, et comparé. Résultat sur les 6,7 millions de paires : le verdict de l'horloge vectorielle a coïncidé avec la vraie relation à chaque fois, paires concurrentes comprises.

L'usage : détecter un conflit d'écriture

C'est le cas d'usage qui a rendu les horloges vectorielles célèbres : Dynamo d'Amazon, et les bases de sa lignée comme Riak. Deux réplicas acceptent des écritures sur le même panier à partir de la même version :

base := VClock{"A": 1}
wa := base.Copy(); wa.Tick("A")   // le réplica A écrit : [A:2]
wb := base.Copy(); wb.Tick("B")   // le réplica B écrit : [A:1 B:1]
Compare(wa, wb)                   // Concurrent

Aucune version n'est ≤ à l'autre, donc le système sait qu'il détient deux siblings, pas une version récente et une ancienne. Une règle « le plus récent gagne » sur l'horloge murale en aurait supprimé une sans prévenir personne. Ici la base peut remettre les deux à l'application pour fusion (par exemple l'union des articles du panier). Le client écrit ensuite la fusion avec une horloge qui domine les deux :

merged := wa.Copy(); merged.Recv("A", wb)  // [A:3 B:1]
Compare(wa, merged)  // Before
Compare(wb, merged)  // Before

La version fusionnée est strictement supérieure aux deux siblings, donc le conflit est résolu et les deux anciennes versions peuvent être écartées. Gardez cette image en tête. L'opération « prendre le maximum composante par composante » est une jointure (join), le plus petit vecteur au-dessus des deux entrées. Elle est associative, commutative et idempotente, et le prochain article de la série, sur les CRDT, repose exactement sur cette propriété.

Coûts et alternatives

• La taille croît avec le nombre de processus. Un vecteur a une entrée par écrivain, donc chaque message et chaque valeur stockée porte O(n) de données en plus. Les systèmes avec beaucoup de clients éphémères ont besoin d'élagage ou de variantes plus fines comme les dotted version vectors.
• Les écritures concurrentes demandent toujours une décision. Détecter un conflit n'est pas le résoudre. Les systèmes à la Dynamo remettent les siblings à l'application, d'autres choisissent une règle comme last-writer-wins et acceptent de perdre des données.
• Les horloges logiques hybrides (HLC) combinent un horodatage physique et un compteur à la Lamport. Elles gardent une taille constante et restent proches du temps réel, ce qui explique leur usage dans des systèmes comme CockroachDB. Comme les horloges de Lamport, elles préservent la causalité mais ne détectent pas la concurrence.
• Les horloges physiques peuvent suffire si on y met le prix. Spanner de Google borne l'incertitude d'horloge avec du matériel dédié et attend qu'elle passe. C'est une réponse d'ingénierie là où cet article donnait une réponse mathématique.

À retenir

• Les horloges murales ne peuvent pas ordonner des événements entre machines. Ce qu'il faut, c'est la relation happened-before, un ordre partiel construit à partir de la séquence locale et des messages.
• Dans un ordre partiel, certaines paires sont incomparables. Ce sont les événements concurrents, et c'est là que vivent les conflits.
• Les horloges de Lamport gardent un compteur : a → b implique L(a) < L(b), mais pas l'inverse. Dans mon test, elles ont fait paraître ordonnées 90 % des paires concurrentes. Utilisez-les quand n'importe quel ordre cohérent suffit.
• Les horloges vectorielles gardent un compteur par processus et se comparent composante par composante : a → b si et seulement si V(a) < V(b). Elles détectent exactement la concurrence, pour un coût O(n) par message.
• Le maximum composante par composante utilisé pour fusionner les horloges est une jointure, la même opération qui fait tourner les CRDT.

Prochain article de la série : les CRDT, et comment la jointure permet aux réplicas de fusionner sans conflit.