Sur la perte de données dans les grands clusters

Il existe trois routines de réplication couramment utilisées : La base de données garantit que chaque donnée est copiée sur trois disques indépendants sur trois ordinateurs différents. La raison en est simple : les disques ne tombent en panne qu'à un certain moment. Si un disque tombe en panne, vous avez le temps de le remplacer et vous pouvez toujours prendre l'une de vos deux autres copies pour restaurer les données et les écrire sur le nouveau disque. . La probabilité que le deuxième disque meure avant que vous ne le restauriez est si faible que la probabilité que vos deux disques meurent en même temps est aussi mince qu'un astéroïde frappant la Terre.

Nous avons également spécialement calculé que la possibilité de panne d'un disque est de près de 0,1 % (peut-être grossièrement), la possibilité de panne de deux disques est de près de 10 puissance 6 et la possibilité de panne de trois disques en même temps. environ 10 à la puissance -9, ce qui équivaut à une partie sur un milliard. Ce calcul montre que la panne d'un disque est indépendante de la panne des autres disques - ce n'est pas très précis, par exemple, si vos disques sont tous produits à partir de la même ligne de production, alors ils peuvent tous être mauvais - Mais c'est suffisant pour notre idée.

Jusqu'à présent, cela semble raisonnable, mais malheureusement, ce n'est pas le cas pour de nombreux systèmes de stockage de données. Dans ce blog, je vais vous montrer pourquoi.

Perdre des données est trop facile

Si votre cluster de bases de données ne contient que trois machines, la possibilité que toutes les machines tombent en panne en même temps est trop faible (à l'exclusion des erreurs associées, comme la destruction d'un centre de données). Cependant, une fois que vous utilisez un cluster plus grand, le problème change en conséquence. Plus vous utilisez de nœuds et de disques dans le cluster, plus vous risquez de perdre des données.

Ceci est basé sur des calculs. Vous pensez peut-être « Vraiment ? J'ai copié les données sur trois disques. Comment la probabilité de panne peut-elle augmenter à mesure que le cluster augmente ? Qu'en est-il de la capacité du cluster ? » Mais j'ai calculé les possibilités et je les ai montrées. vous pourquoi avec l'icône suivante :

Évidemment, il ne s'agit pas de la possibilité d'une panne d'un nœud - c'est de la possibilité de perdre définitivement les trois copies des données, donc restaurer les données à partir d'une sauvegarde n'est qu'une approche conservatrice. Plus votre cluster est grand, plus vous risquez de perdre des données. C’est quelque chose auquel vous ne pensez peut-être pas lorsque vous envisagez de payer pour répliquer vos données.

L'axe Y du graphique est un peu arbitraire et repose sur beaucoup d'imagination, mais la direction des lignes est incroyable. Sur la base des hypothèses précédentes, la probabilité qu'un nœud tombe en panne à un moment donné est de 0,1 %. Cependant, la figure montre que dans un cluster de 8 000 nœuds, la probabilité de perdre définitivement trois copies d'une donnée est d'environ 0,2 %. Oui, c'est vrai, le risque de perdre les trois copies est deux fois plus élevé que le risque de perdre les données d'un nœud. Alors à quoi servent ces copies ?

À en juger intuitivement à partir de cette image : dans un cluster de 8 000 nœuds, il est courant que certains nœuds tombent en panne à certains moments. Cela n'est peut-être pas un problème : une certaine probabilité de chaos et de remplacement de nœuds peut être déduite, et cela est en partie dû à la maintenance de routine. Cependant, si vous n'avez pas de chance et que le nœud de destination des données du nœud que vous avez copié est en panne, vos données ne seront jamais récupérées. La perte de données représente une part relativement petite de l'ensemble de données global du cluster, mais lorsque vous perdez trois réplicas, vous pensez peut-être « Je ne veux vraiment pas perdre ces données » plutôt que « Je ne m'y attendais pas ». perdre accidentellement certaines données, même si elles ne sont pas très volumineuses "Peut-être que cette partie des données manquantes est une partie importante des données.

La possibilité que les trois répliques soient des nœuds défectueux dépend de l'algorithme de réplication utilisé par le système. Le diagramme ci-dessus repose simplement sur la division des données en un certain nombre de partitions (ou fragments), de sorte que chaque partition stocke trois nœuds sélectionnés aléatoirement (ou fonction de hachage pseudo-aléatoire). Il s'agit d'un cas particulier de hachage cohérent, utilisé dans Cassandra et Riak (pour autant que je sache). Je ne sais pas comment les autres systèmes distribuent le travail de réplication, donc je le regarde de la part de quelqu'un qui connaît les composants internes d'un système multi-stockage.

Calculez la probabilité de perdre des données

Laissez-moi vous montrer comment j'ai calculé le graphique ci-dessus en utilisant un modèle probabiliste d'une base de données répliquée.

Supposons que la probabilité qu'un nœud indépendant perde des données est p=P (perte de nœud). Je vais ignorer le temps dans ce modèle et examiner brièvement la probabilité d'échec pendant certaines périodes. Par exemple, nous pouvons supposer que p=0,001 est la probabilité qu'un nœud tombe en panne un certain jour. Il est raisonnable de passer une journée à remplacer le nœud et à transférer les données perdues vers le nouveau nœud. Pour faire simple, je ne veux pas faire de distinction entre une panne de nœud et une panne de disque, je ne parlerai que de panne permanente.

Soit n le nombre de nœuds dans le cluster. f est le nombre de nœuds défaillants (en supposant que les pannes sont relativement indépendantes) et est distribué de manière binomiale :

L'expression est la probabilité d'échec de f nœuds. L'expression est la probabilité de garantir que n-f nœuds n'échouent pas. C'est le nombre de f nœuds extraits de n de différentes manières. Prononcé « n choisissez f », il est défini comme :

. . . . . .

Le processus de dérivation spécifique ne sera pas décrit en détail ici. Sur la base de la formule ci-dessus, nous pouvons déduire la probabilité de perdre une ou plusieurs partitions dans un cluster avec n nœuds et un facteur de réplication de (nombre de nœuds de sauvegarde répliqués). Si le nombre de nœuds défaillants f est inférieur au facteur de réplication, nous pouvons être sûrs qu'aucune donnée n'a été perdue. Cependant, il faut additionner toutes les possibilités lorsque f est compris entre r et n :

C'est un peu verbeux, mais je pense que c'est exact. Si vous laissez r=3, p=0,001, k=256n, n est compris entre 3 et 10 000, alors vous pouvez obtenir l'image ci-dessus. J'ai écrit quelques programmes Ruby pour implémenter ce calcul.

Nous utilisons la liaison syndicale pour obtenir une estimation plus simple :

Bien que la défaillance d'une partition ne soit pas complètement indépendante des autres partitions, cette conjecture s'applique toujours. Cela semble plus proche des résultats expérimentaux : en chemin, la probabilité de perte de données ressemble davantage à une ligne droite, proportionnelle au nombre de nœuds. La conjecture montre que la probabilité est positivement liée au nombre, et nous supposons que chaque nœud a 256 partitions fixes.

En pratique. . .

Comment cela fonctionnera dans la pratique, je ne suis pas sûr. Mais je pense qu’il s’agit d’un phénomène intéressant et sensible sur le plan informatique. J'ai entendu parler de situations dans lesquelles des entreprises disposant de grands clusters de bases de données ont subi de réelles pertes de données. Mais ce n’est pas très courant dans les articles et les rapports. Si vous étudiez actuellement ce sujet, vous pouvez me le dire.

Les résultats calculés montrent que si vous souhaitez réduire le risque de perte de données, vous devez réduire le nombre de partitions et augmenter le facteur de réplication. Utiliser davantage de sauvegardes coûte plus cher, ce qui est donc déjà coûteux si l'on considère de grands clusters. Cependant, le nombre de partitions indique un processus d'équilibrage de charge significatif. Cassandra avait à l'origine une partition par nœud, mais plus tard, elle est devenue 256 partitions par nœud pour faire face à une meilleure répartition de la charge et à un équilibrage secondaire efficace.

Vous devez trouver des clusters raisonnablement grands avant que ceux-ci puissent vraiment fonctionner, mais des clusters de milliers de niveaux sont utilisés par de nombreuses grandes entreprises. Je suis donc intéressé à entendre des personnes ayant une expérience pratique dans ce domaine. Si la probabilité de perte permanente de données pour 10 000 nœuds est contrôlée à 0,25 % chaque jour, cela signifie que 60 % des données seront perdues en un an.

En tant que concepteur de systèmes de données distribués, que pensez-vous après avoir lu cet article ? Si ce que je dis est juste, il faudrait réfléchir davantage à la conception de schémas de réplication. J’espère que cet article pourra accroître votre conscience de la réalité. Parce que 3 nœuds de réplication ne sont vraiment pas si sûrs.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!