Cloudflare a dévoilé des détails techniques concernant son service de consensus distribué expérimental Meerkat, conçu pour gérer le plan de contrôle interne à l'échelle mondiale. Le service s'appuie sur un algorithme de consensus moderne appelé QuePaxa, publié par les chercheurs Tennage & Băsescu en 2023. Ce choix représente une rupture avec les habitudes dans le domaine des systèmes distribués, la plupart des infrastructures actuelles reposant sur des algorithmes bien établis tels que Raft, Paxos ou Viewstamped Replication.
Les défis des algorithmes de consensus traditionnels dans les réseaux mondiaux
Les algorithmes de consensus traditionnels souffrent d'une forte baisse de performance ou d'une interruption totale du service lorsqu'ils fonctionnent sur des réseaux étendus (WAN) caractérisés par une latence fluctuante et des coupures de communication potentielles. Ces protocoles dépendent fondamentalement d'un processus leader (Leader Process) qui garantit l'ordre des opérations et fournit des réponses dans un délai prévu. Lorsque le leader subit une augmentation de la latence ou une perte de connexion réseau, les opérations de consensus s'arrêtent complètement jusqu'à la détection de la panne et l'élection d'un nouveau leader.
Les principaux défauts des systèmes traditionnels se manifestent en deux points critiques :
- Interférence destructive (Destructive Interference) : Dans le protocole Paxos, la soumission de propositions simultanées par plusieurs nœuds entraîne l'annulation mutuelle des propositions et plonge le système dans une spirale de tentatives infructueuses qui bloquent sa progression. Bien que le protocole Raft résolve ce problème en désignant un unique leader, l'interférence destructive réapparaît lors des élections de leader en cas de perturbation réseau temporaire.
- Détecteurs de pannes impuissants (Fault Detectors) : Dans les réseaux non synchrones comme Internet, il est difficile de distinguer un ralentissement du réseau d'une panne complète d'un nœud. Les estimations erronées des détecteurs de pannes déclenchent des processus d'élection de leader inutiles, plongeant le système dans un état de défaillance similaire à une défaillance métastable (Metastable Failure) et arrêtant les écritures pendant plusieurs heures.
Comment QuePaxa corrige-t-elle les points de défaillance sans leader obligatoire ?
L'algorithme QuePaxa surmonte ces obstacles grâce à trois choix de conception fondamentaux : faire du leader une option facultative, se passer entièrement des détecteurs de pannes et privilégier la coopération plutôt que la compétition entre les proposants (Proposers). L'algorithme repose sur une répartition des rôles entre les candidats (Proposers) et les enregistreurs (Recorders).
L'algorithme attribue des priorités aléatoires aux propositions. Lorsqu'un proposant reçoit une proposition d'une priorité supérieure à celle d'un autre enregistreur, il adopte immédiatement la nouvelle proposition et commence à la diffuser, ce qui amène tous les nœuds à coopérer pour atteindre la plus haute priorité annoncée au lieu de se bloquer mutuellement. En présence d'un leader, la plus haute priorité possible lui est accordée, ce qui lui permet de finaliser le consensus en un seul aller-retour (Single Round-Trip) tant que le réseau est stable.
Mécanisme de fonctionnement technique : Les quatre étapes pour parvenir au consensus
QuePaxa exécute les cycles de consensus à travers quatre étapes successives par lesquelles le système passe pour valider les journaux :
- Étape 0 (Soumission et adoption) : Les proposants génèrent des priorités aléatoires pour leurs propositions. Si le leader fonctionne correctement et que ses messages parviennent d'abord à la majorité des enregistreurs, le consensus est immédiatement finalisé via le « chemin rapide » (Fast Path).
- Étape 1 (Diffusion) : Les proposants diffusent les propositions adoptées à la majorité des enregistreurs pour empêcher tout retour en arrière ultérieur sur les propositions dotées de priorités supérieures, en s'appuyant sur l'intersection des majorités (Majority Intersection).
- Étape 2 (Vérification et finalisation) : Les proposants interrogent les enregistreurs pour connaître la plus haute priorité observée lors de l'étape précédente ; si elle correspond à leur proposition adoptée, celle-ci est officiellement validée.
- Étape 3 (Transmission au cycle suivant) : En l'absence de finalisation, les nœuds adoptent la meilleure proposition disponible en prévision du cycle suivant, ce qui augmente fortement la probabilité d'un consensus cumulatif.
Pourquoi cette transition technique est-elle importante ?
L'adoption de QuePaxa constitue une étape pratique qui modifie la manière de concevoir les systèmes distribués intercontinentaux ; elle prouve que les systèmes n'ont pas besoin de sacrifier la disponibilité (Availability) ou de subir un arrêt total lors de perturbations sur Internet. Les résultats de l'exploitation de Meerkat dans l'environnement de production de Cloudflare ont montré que plus de 95 % des décisions sont finalisées via le chemin rapide du leader. En cas de défaillance du réseau ou de chute du leader, le système ne s'arrête pas : son taux de productivité diminue d'un tiers au maximum tout en continuant à traiter les requêtes.
L'algorithme permet également des techniques de couverture (Hedging), où les clients peuvent envoyer des propositions à l'ensemble des réplicas tout en définissant localement un court délai d'attente sans dépendre de la latence du réseau, éliminant ainsi les périodes d'arrêt provoquées par les longs délais d'élection de Raft qui atteignent plusieurs secondes. Cloudflare travaille actuellement sur la vérification formelle rigoureuse (Formal Verification) du code de l'algorithme écrit en langage Rust afin de garantir la sécurité des données lors des scénarios de récupération après incident (Crash Recovery).