Partitionnement aléatoire (“shuffle sharding”) : isolation massive et magique des erreurs

Un jeu de cartes standard comprend 52 cartes à jouer différentes et 2 jokers. Si nous mélangeons soigneusement un jeu de cartes et que nous distribuons une main de quatre cartes, il y a plus de 300 000 mains différentes possibles. Une autre façon de dire la même chose est que si nous remettons les cartes, que nous les mélangeons et que nous distribuons à nouveau, les chances sont inférieures à 1 sur 300 000 que nous distribuions à nouveau la même main. C’est donc très peu probable.

Il est également peu probable, avec moins d’un quart de chance, qu’une seule des cartes corresponde entre les deux mains. Et pour compléter le tableau, il y a moins d’1 chance sur 40 que deux cartes soient identiques, et bien moins d’1 chance sur 1000 que trois cartes soient identiques.

La librairie Route 53 Infima peut être utilisée pour isoler les erreurs liées à une requête, tels que les problèmes spécifiques à un utilisateur ou à un client. Le partionnement aléatoire de Route 53 Infima utilise ce schéma de diminution rapide de la probabilité d’un nombre croissant de correspondances, un schéma qui est à la base de nombreux jeux de cartes, loteries et même bingos, et le combine à la mise à l’échelle horizontale traditionnelle pour produire une sorte d’isolation des erreurs qui peut sembler presque magique.

Mise à l’échelle horizontale traditionnelle

Tous les services, à l’exception des plus petits, s’exécutent généralement sur plusieurs instances (à quelques exceptions près). L’utilisation de plusieurs instances permet d’avoir une redondance active : lorsqu’une instance rencontre un problème, les autres peuvent prendre le relais. Généralement, le trafic et les demandes sont répartis entre toutes les instances saines.
Bien que ce modèle soit idéal pour équilibrer le trafic et pour gérer les défaillances occasionnelles au niveau de l’instance, il est terrible si les requêtes elles-mêmes ont quelque chose de dangereux : chaque instance sera affectée. Si le service dessert de nombreux clients, par exemple, un client accaparé par d’importantes requêtes pourrait submerger tous les autres. La limitation des demandes par client peut être utile, mais même les mécanismes de limitation peuvent eux-mêmes être débordés.
Pire encore, la limitation n’aidera pas s’il s’agit d’une sorte de « requête empoisonnée ». Si une requête particulière déclenche un bug qui provoque le basculement du système, l’appelant peut déclencher un échec en cascade en essayant à plusieurs reprises la même requête, instance après instance, jusqu’à ce que toutes les requêtes échouent.

Partage et cloisonnement

L’une des améliorations que nous pouvons apporter à la mise à l’échelle horizontale traditionnelle consiste à utiliser le partitionnement (“sharding“). Le partionnement est une technique traditionnellement utilisée avec les systèmes de stockage et d’indexation de données. Au lieu de répartir le trafic provenant de tous les clients sur chaque instance, nous pouvons diviser les instances en partitions. Par exemple, si nous avons huit instances pour notre service, nous pouvons créer quatre partitions de deux instances chacune (deux instances pour assurer la redondance au sein de chaque partition).

Ensuite, nous devons décider de quelle manière procéder au partitionnement. L’une des méthodes la plus courante consiste à utiliser l’identifiant du client pour attribuer des partitions spécifiques, mais d’autres choix de partitionnement sont possibles, par exemple par type d’opération ou par identifiant de ressource. Vous pouvez même choisir d’effectuer un partitionnement multidimensionnel et demander à des paires client-ressource de sélectionner une partition ou un type d’opération client-ressource-client.
Ce qui convient le mieux à un service donné dépend de ses caractéristiques intrinsèques et de sa combinaison particulière de risques, mais il est généralement possible de trouver une combinaison d’identifiant ou de type d’opération qui fera toute la différence s’il est possible de l’isoler.
Avec ce type de partitionnement en place, si un problème est causé par les requêtes, nous obtenons le même type d’effet de cloisonnement que nous avons vu auparavant ; le problème peut être limité à une seule partition. Ainsi, dans notre exemple ci-dessus, avec quatre partitions, environ un quart des clients (ou toute autre dimension choisie) peuvent être affectés par un problème déclenché par un client. C’est bien mieux que si tous les clients étaient concernés.
Si les clients (ou les objets) reçoivent des noms DNS spécifiques à utiliser (tout comme les clients reçoivent des noms DNS uniques pour de nombreux services AWS), le DNS peut être utilisé pour séparer clairement les partitions par client.

Partitionnement aléatoire (de l’anglais “Shuffle Sharding”)

Grâce au partitionnement, nous sommes en mesure de réduire l’impact sur les clients en proportion directe du nombre d’instances dont nous disposons. Même si nous avions 100 shards, 1 % des clients subiraient tout de même un impact en cas de problème. Une solution judicieuse consiste à créer des systèmes de surveillance capables de détecter ces problèmes et, une fois détectés, de repartitionner les requêtes vers leur propre partition entièrement isolée. Il s’agit néanmoins d’une mesure réactive qui ne peut généralement qu’atténuer l’impact, plutôt que de l’éviter en premier lieu.
Avec le partitionnement aléatoire, nous pouvons faire mieux. L’idée de base du partitionnement aléatoire est de générer des partitions comme on distribue des mains à partir d’un jeu de cartes. Prenons l’exemple des huit instances. Auparavant, nous l’avions divisé en quatre fragments de deux instances. Avec le partitionnement aléatoire, les partitions contiennent deux instances aléatoires et, tout comme nos mains de cartes, elles peuvent se chevaucher dans une certaine mesure.

En choisissant deux instances parmi huit, vous pouvez obtenir 56 partitions aléatoires potentielles, bien plus que les quatre partitions simples que nous avions auparavant.
À première vue, il peut sembler que ces partitions aléatoires sont moins adaptées à l’isolation des pannes; dans l’exemple ci-dessus, deux partitions aléatoires partagent l’instance 5, de sorte qu’un problème affectant cette instance peut avoir un impact sur les deux shards. La clé pour résoudre ce problème est de rendre le client tolérant aux pannes. En utilisant une logique de nouvelle tentative simple dans le client qui l’amène à essayer tous les points de terminaison d’une partition aléatoire, jusqu’à ce que l’un d’entre eux réussisse, nous obtenons un effet de cloisonnement spectaculaire.
Lorsque le client essaie chaque instance de la partition, le client à l’origine du problème avec la partition aléatoire 1 peut avoir un impact à la fois sur l’instance 3 et sur l’instance 5 et donc être affecté, mais les clients utilisant la partition aléatoire 2 ne devraient subir qu’un impact négligeable (voire aucun) si les nouvelles tentatives du client ont été soigneusement testées et mises en œuvre pour gérer correctement ce type de dégradation partielle. L’impact réel est donc limité à 1/56e de l’ensemble des partitions aléatoires.
L’impact 1/56 représente une nette amélioration par rapport au 1/4, mais nous pouvons encore faire mieux. Auparavant, avec le partitionnement simple, nous devions placer deux instances dans chaque partition pour obtenir une certaine redondance. Avec le partionnement aléatoire, comme avec la mise à l’échelle horizontale N+1 traditionnelle, nous disposons d’un plus grand nombre d’instances. Nous pouvons partager vers autant d’instances que nous le souhaitons. Avec 3 tentatives (une valeur de nouvelle tentative courante), nous pouvons utiliser quatre instances au total par partition aléatoire.
Avec quatre instances par partition aléatoire, nous pouvons réduire l’impact à 1/1680 de notre clientèle totale et nous avons rendu le problème des « voisins bruyants » (de l’anglais « noisy neighbours ») beaucoup plus facile à gérer.

Infima et Partitionnement Aléatoire

La bibliothèque Route 53 Infima inclut deux types de partionnement aléatoire. Le premier type est le partionnement aléatoire simple sans état (“simple stateless shuffle sharding”). Le partionnement aléatoire sans état utilise le hachage, un peu comme le fait un filtre “bloom”, pour transformer un client, un objet ou d’autres identifiants en modèle de partionnement aléatoire. Cette technique entraîne une certaine probabilité de chevauchement entre les clients, tout comme lorsque nous distribuons des mains à partir d’un jeu de cartes. Mais comme il est sans état, ce type de partionnement aléatoire peut être facilement utilisé, même directement pour appeler des clients.
Le deuxième type de partionnement aléatoire inclus est le partitionnement aléatoire avec état (“Stateful Searching Shuffle Sharding”). Ces partitions sont générées par assignation aléatoire, encore une fois comme les mains d’un jeu de cartes, mais un support intégré permet de comparer chaque partition nouvellement générée à chaque fragment précédemment attribué afin de garantir qu’il n’y a pas de chevauchement. Par exemple, nous pouvons choisir de donner à chaque partition aléatoire 4 points de terminaison (de l’anglais “endpoints”) sur 20, tout en exigeant que deux partitions aléatoires ne partagent jamais plus de deux points de terminaison particuliers.
Les deux types de partitionnement aléatoire dans Infima tiennent compte du compartimentage. Par exemple, nous pouvons nous assurer que les partitions aléatoires utilisent également toutes les zones de disponibilité. Nos instances peuvent donc se trouver dans 2 zones de disponibilité, 4 dans chacune d’elles. Infima peut s’assurer de choisir deux points de terminaison dans chaque zone, plutôt que deux au hasard (qui peut choisir les deux dans la même zone de disponibilité).

Enfin, Infima facilite également l’utilisation de partitions aléatoires avec RubberTree, afin que les points de terminaison puissent être facilement exprimés dans le DNS à l’aide de Route 53. Par exemple, chaque client peut se voir attribuer son propre nom DNS, qui correspond à une partition aléatoire gérée par un RubberTree.

Post-scriptum

Les deux principes généraux sont qu’il peut souvent être préférable d’utiliser de nombreux éléments plus petits, car cela permet de réduire le coût des zones tampon de capacité et de minimiser l’impact de tout conflit, et qu’il peut être avantageux de permettre aux partitions de se chevaucher partiellement au sein de leurs membres, en échange d’une augmentation exponentielle du nombre de partitions que le système peut prendre en charge.
Ces principes font du partitionnement aléatoire une technique polyvalente. Vous pouvez également choisir d’utiliser le partitionnement aléatoire avec de nombreux types de ressources, y compris des structures de données purement en mémoire telles que des files d’attente, des limiteurs de débit, des verrous et d’autres ressources contestées.
Il se trouve qu’Amazon Route 53, CloudFront et d’autres services AWS utilisent le compartimentage, le partitionnement aléatoire par client, etc. pour isoler les pannes.

Mise à jour de l’auteur : une version antérieure de cet article utilisait un chiffre incorrect pour le nombre de mains de 4 cartes dans un jeu de 52 cartes (j’en ai écrit 7 millions, sur la base des permutations, au lieu de 300 000 sur la base des combinaisons)

Article original publié par Colm MacCarthaigh, Vice-Président et Distinguished Engineer chez AWS. Version française éditée par Patrick Mével, Architecte de Solutions Sénior chez AWS.