Horloges logiques : horodatages de Lamport, horloges vectorielles et horloges hybrides

Ce que c'est

L'article de Lamport de 1978 (répertorié sur sa page de publications, cité) définit la relation « s'est produit avant » : l'événement a précède b si les deux se produisent dans ce même processus dans cet ordre, si a est l'envoi d'un message et b sa réception, ou par transitivité. Une horloge de Lamport est un compteur par processus : on l'incrémente à chaque événement local, on l'attache à chaque message, et à la réception on fixe le compteur au maximum entre la valeur locale et la valeur reçue, plus un. Si a s'est produit avant b, alors horloge(a) < horloge(b) ; la réciproque n'est pas vraie, si bien que des horodatages égaux ou proches ne disent rien de la causalité. Départager les égalités par un identifiant de processus donne un ordre total.

Une horloge vectorielle, telle que décrite dans l'article Dynamo (cité), est une liste de paires (nœud, compteur) attachée à chaque version d'un objet. Comparer deux vecteurs indique si une version descend de l'autre ou si elles se situent sur des branches parallèles ; c'est ainsi que Dynamo détecte les écritures conflictuelles à réconcilier lors de la lecture.

Les horloges logiques hybrides combinent les deux idées. La documentation de CockroachDB (citée) décrit une HLC comme une composante physique proche de l'heure murale locale, additionnée d'une composante logique qui distingue les événements partageant la même valeur physique ; le temps HLC est ainsi toujours supérieur ou égal à l'heure murale, tout en ordonnant les événements liés par une relation de causalité.

Pourquoi c'est important

Le principe « le dernier à écrire l'emporte, selon l'horodatage » élimine silencieusement des mises à jour lorsque le décalage entre horloges dépasse l'intervalle entre deux écritures. Les données répliquées, les clients capables de fonctionner hors ligne et les déploiements multirégions rencontrent tous ce problème.

Comment l'appliquer

• Doter chaque enregistrement modifiable d'un compteur de version qui augmente à chaque écriture, et l'utiliser pour la concurrence optimiste (UPDATE ... WHERE version = $seen) ; il s'agit d'une horloge de Lamport par enregistrement.
• Dans les flux d'événements, ordonner par numéro de séquence au sein d'une partition, et non par horodatage du producteur.
• Lorsque plusieurs répliques acceptent des écritures, conserver un vecteur de version par enregistrement ou utiliser un type de donnée doté d'une fusion définie (un CRDT), et signaler les conflits plutôt que de désigner un vainqueur selon l'heure murale.
• Utiliser les horodatages de l'heure murale pour l'affichage et la conservation, et noter dans la conception la source de l'horloge (synchronisée par NTP ou non).

Pièges

Les horloges vectorielles croissent avec le nombre de rédacteurs et nécessitent des règles d'élagage. Les horloges de Lamport ordonnent mais ne peuvent pas détecter la concurrence. Une horloge monotone sur une machine ne dit rien de l'horloge d'une autre machine.