Vector Clocks

Comment savoir si deux mises à jour distribuées sont en conflit ou si l'une cause l'autre, sans dépendre d'horloges murales synchronisées.

Problème

Dans un système distribué multi-master, deux nœuds peuvent recevoir des mises à jour différentes sur la même donnée pendant qu'une partition réseau les empêche de communiquer. À la résolution, le système doit décider : ces écritures sont-elles concurrentes (conflit à résoudre) ou bien l'une est-elle la conséquence causale de l'autre (la plus récente gagne) ? Une horloge murale n'aide pas — les clocks divergent (NTP a une précision de ~10ms en LAN, pire en WAN), et un événement causalement postérieur peut avoir un timestamp antérieur. Il faut une structure qui capture l'ordre causal (happens-before, noté →), pas l'ordre temporel.

Forces

• Taille mémoire : un vector clock contient une entrée par nœud, donc N entiers ; explose avec le nombre de réplicas.
• Garbage collection : retirer les entrées de nœuds disparus est un problème en soi.
• Détection de conflit, pas résolution : VC dit « il y a conflit » mais pas « voici la valeur correcte » — il faut une fonction métier.
• Pas d'ordre total : on obtient un ordre partiel ; deux événements concurrents sont incomparables.
• Coût comparatif : les hybrid logical clocks (HLC, Kulkarni 2014) offrent un compromis entre VC et horloge physique.

Solution

Chaque nœud i maintient un vecteur VC[i] = [c1, c2, ..., cN]. Sur événement local, on incrémente VC[i][i]. Sur envoi de message, on attache VC[i]. Sur réception, on calcule VC[i][k] = max(VC[i][k], VC[reçu][k]) pour tout k, puis on incrémente VC[i][i]. Pour comparer deux vector clocks VC(a) et VC(b) : si VC(a)[k] ≤ VC(b)[k] pour tout k et au moins une inégalité stricte, alors a → b (a happens-before b). Si ni a → b ni b → a, alors a et b sont concurrents — conflit à résoudre. Dynamo (Amazon) stocke plusieurs versions concurrentes et laisse l'application les fusionner (« last-write-wins » ou logique métier).

Structure

Three nodes: A, B, C
Initial: VC_A = [0,0,0]   VC_B = [0,0,0]   VC_C = [0,0,0]

A writes "x=1"     → VC_A = [1,0,0]
A sends to B       → message carries VC = [1,0,0]
B receives, writes → VC_B = max([0,0,0], [1,0,0]) + own++ = [1,1,0]

Meanwhile, C writes "x=2" independently
                   → VC_C = [0,0,1]
C sends to B       → message carries VC = [0,0,1]

B compares its current VC_B = [1,1,0] with incoming [0,0,1]:
  Is [1,1,0] ≤ [0,0,1]? NO (1 > 0)
  Is [0,0,1] ≤ [1,1,0]? NO (1 > 0)
  → CONCURRENT! Conflict between "x=1 via A" and "x=2 via C"
  → Application must resolve (e.g., merge shopping cart, max value, ...)

Implémentation EDI

Vector clocks ne servent pas dans le hub EDI canonique (où l'ordre est garanti par la queue centrale Kafka), mais ils sont indispensables dans deux contextes : (1) hub EDI multi-région actif-actif sur un store CRDT (Riak KV, par exemple) où les écritures locales se synchronisent en arrière-plan — chaque écriture porte son VC, et la résolution de conflits est métier (la dernière INVOIC reçue gagne, ou bien on garde les deux pour audit) ; (2) edge computing pour mandats e-invoicing — un partenaire émet une facture depuis le edge et le hub central concurremment ; VC permet de détecter et tracer ces collisions. Amazon Dynamo (papier 2007) est l'exemple canonique : il utilise vector clocks pour les paniers shopping où les conflits doivent être fusionnés, pas perdus. Pour l'EDI, ce type de logique apparaît typiquement dans la dédup sémantique de notes de crédit qui croisent l'INVOIC originale en cours de traitement.

Anti-patterns

• Stocker un VC par enregistrement avec des milliers de nœuds — la taille explose ; utiliser pruning ou dotted version vectors.
• Compter sur VC pour résoudre les conflits automatiquement — VC détecte, l'application résout.
• Ignorer le garbage collection — les anciens nœuds laissent des entrées éternelles dans tous les vecteurs.
• Mélanger VC et timestamps mur — annule l'intérêt du VC qui était précisément d'éviter la dépendance à l'horloge.
• Supposer un ordre total — VC fournit un ordre partiel ; deux événements concurrents sont incomparables par construction.

Patterns liés

• Idempotence — combinée à VC pour détecter doublons réels vs concurrents.
• Event Sourcing — un event store distribué multi-région utilise typiquement VC.
• Aggregator (EIP 268) — la corrélation multi-message peut s'appuyer sur VC.
• Consistent Hashing — combiné à VC dans Dynamo.

Sources

• Lamport L. — Time, Clocks, and the Ordering of Events in a Distributed System, CACM 1978. Le papier fondateur sur les horloges logiques. lamport.azurewebsites.net
• Mattern F. — Virtual Time and Global States of Distributed Systems, 1989. Formalisation des vector clocks. vs.inf.ethz.ch
• Fidge C. — Timestamps in Message-Passing Systems That Preserve the Partial Ordering, 1988.
• DeCandia G. et al. — Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. Application industrielle de référence. allthingsdistributed.com
• Kleppmann M. — Designing Data-Intensive Applications, O'Reilly 2017, chap. 5 (« Replication »).