Dans cet article, nous examinerons l'architecture d'un stockage KV simple et efficace utilisant la réplication de chaîne, qui est activement étudiée et utilisée avec succès dans divers systèmes.

Il s'agit de la première moitié d'un article de réplication de chaîne. La deuxième partie est ici . Il y aura d'abord un peu de théorie, puis quelques exemples d'utilisation avec diverses modifications.

1. L'objectif est l'énoncé du problème et la comparaison avec le protocole principal / de sauvegarde.
2. La réplication de chaîne est une approche de base.
3. Réplication de chaîne - demandes distribuées.
4. FAWN: un tableau rapide de nœuds Wimpy.

1. Introduction

1.1 Objet

Supposons que nous voulons concevoir un magasin de valeurs-clés simple. Le référentiel aura une interface très minimale:

1. écriture (clé, objet): sauvegarde / mise à jour de la valeur par clé clé.
2. lecture (clé): retourne la valeur stockée par clé clé.

Nous savons également que la taille des données est relativement petite (tout tient sur un seul serveur, il n'y a pas besoin de partitionnement), mais il peut y avoir beaucoup de demandes d'écriture / lecture.

Notre objectif est de résister à un grand nombre de demandes ( haut débit, HT ), d'avoir une haute disponibilité ( HA ) et une forte cohérence ( SC ).

Dans de nombreux systèmes, SC est sacrifié pour HA + HT, car remplir les trois propriétés est une tâche non triviale. Amazon Dynamo a été un énorme bond en avant et a engendré un certain nombre de bases de données de style Dynamo, telles que Cassandra, Riak, Voldemort, etc.

1.2 Primaire / sauvegarde

L'une des approches les plus courantes et les plus simples pour créer un tel système de stockage consiste à utiliser la réplication principale / de sauvegarde.
Nous avons 1 serveur principal, plusieurs serveurs de sauvegarde, les opérations d'écriture / lecture passent uniquement par le serveur principal.


Ici, l'image montre l'un des protocoles d'interaction possibles (le principal attend un accusé de réception de toutes les sauvegardes avant d'envoyer un accusé de réception au client), il existe d'autres options (non mutuellement exclusives), par exemple:

• Le primaire organise strictement les demandes d'écriture.
• Le primaire envoie un accusé de réception dès que l'une des sauvegardes répond par un accusé de réception.
• Quorum bâclé et transfert suggéré.
• Etc.

Un processus distinct est également nécessaire qui surveille l'état du cluster (distribue la configuration aux participants) et, lorsque le serveur hôte tombe en panne, fait (initie) l'élection d'un nouveau, et détermine également ce qu'il faut faire en cas de division du cerveau. Encore une fois, selon les exigences, une partie de cette logique peut être exécutée dans le cadre de l'algorithme de réplication, une partie en tant qu'application tierce (par exemple, un gardien pour stocker la configuration), etc.

Évidemment, tôt ou tard, les performances de la réplication primaire / de sauvegarde seront limitées par deux goulots d'étranglement:

• Performances du serveur principal.
• Nombre de serveurs de sauvegarde.

Plus les exigences de fiabilité / cohérence sont présentées à un cluster, plus ce moment sera rapide.

Existe-t-il d'autres moyens d'atteindre notre objectif?

1.3 Réplication de chaîne

En général, la réplication de chaîne consiste en une séquence (chaîne) de serveurs, avec des rôles spéciaux HEAD (le serveur avec lequel le client communique) et TAIL (fin de chaîne, garantie SC). Une chaîne a au moins les propriétés suivantes:

1. Résiste à la chute sur n - 1 serveurs.
2. La vitesse d'écriture n'est pas significativement différente de la vitesse de SC Primary / Backup.
3. La reconfiguration du cluster en cas de crash HEAD se produit beaucoup plus rapidement que Primary, les autres serveurs sont comparativement ou plus rapidement que dans Primary / Backup.

Un petit point important: une connexion FIFO fiable entre les serveurs est requise .

Examinons plus en détail les différentes méthodes de construction de la réplication de chaîne.

2. L'approche de base

2.1 Algorithme opérationnel

Les clients envoient des demandes d'écriture au nœud principal et les demandes de lecture sont envoyées au nœud arrière. La réponse vient toujours de la queue. Head, ayant reçu une demande de changement, calcule le changement d'état nécessaire, l'applique et l'envoie au nœud suivant. Dès que la queue le traite, une réponse ACK est renvoyée dans la chaîne. Évidemment, si une demande de lecture renvoie une valeur de x, elle est stockée sur tous les nœuds.

2.2 Protocole de réplication

Nous numérotons les serveurs de la tête à la queue, puis sur chaque nœud $$$i$ nous stockerons en outre:

• $$$Pending_i$ - une liste des requêtes reçues par le nœud qui n'ont pas encore été traitées par tail.
• $$$Sent_i$ - une liste des requêtes envoyées par le serveur à son successeur qui n'ont pas encore été traitées par tail.
• $$$History_i (clé)$ - l'historique des modifications de la valeur clé (vous pouvez stocker à la fois l'historique et uniquement la valeur totale). Notez que:

  $$

  $$History_j (clé) \ subseteq History_i (clé), \ forall j> i$$
  
  
• Et aussi:

  $$

  $$Sent_i \ subseteq Pending_i \\ History_i (clé) = History_ {i + 1} (clé) \ cup Sent_i$$
  
  

2.3 Basculement du serveur

Comme mentionné dans l'introduction, nous avons besoin d'une sorte de processus maître qui:

• Identifie un serveur défaillant.
• Avertit son prédécesseur et son successeur des modifications du circuit.
• Si le serveur est en queue ou en tête, il informe les clients de leur changement.

Nous pensons que le processus maître est stable et ne se bloque jamais. Le choix d'un tel processus dépasse le cadre de cet article.

La deuxième hypothèse très importante est que nous supposons que les serveurs sont à échec:

• En cas de défaillance (interne), le serveur cesse de fonctionner et ne donne pas de résultat incorrect.
• La défaillance du serveur est toujours déterminée par le processus maître.

Voyons comment un nouveau serveur est ajouté:
Théoriquement, un nouveau serveur peut être ajouté à n'importe quel endroit de la chaîne, l'ajout à la queue semble le moins difficile - il vous suffit de copier le statut de la queue actuelle sur le nouveau serveur, d'informer l'assistant de la modification de la chaîne et d'informer l'ancienne queue que les demandes doivent maintenant être envoyées plus loin.

Enfin, envisagez trois scénarios de défaillance possibles:

2.3.1 Chute de tête
Retirez simplement le serveur de la chaîne et affectez la nouvelle tête suivante. Seule la perte de ces demandes de $$$Pending_ {head}$ qui n'ont pas été envoyés plus loin - $$$Pending_ {head} \ setminus Sent_ {head}$

2.3.2 Queue d'automne
Nous supprimons le serveur de la chaîne et affectons le précédent à la nouvelle queue, avant cela $$$Sent_ {tail - 1}$ effacées (toutes ces opérations sont marquées comme queue traitée), respectivement $$$Pending_ {tail - 1}$ diminue.

2.3.3 Noeud intermédiaire tombant $$$k$
L'assistant informe les nœuds $$$k-1$ et $$$k + 1$ sur la réorganisation dans une chaîne.
Perte possible $$$Sent_ {k-1}$ si le nœud $$$k$ Je n'ai pas réussi à les envoyer plus loin à mon successeur, donc, après avoir supprimé le nœud $$$k$ de la chaîne, la première chose est envoyée à nouveau $$$Sent_ {k - 1}$ et seulement après ce nœud $$$k - 1$ continue de traiter les nouvelles demandes.

2.4 Comparaison avec le protocole de sauvegarde / principal

• Dans la réplication de chaîne, un seul serveur (queue) est impliqué dans l'exécution des demandes de lecture, et il donne une réponse immédiatement, tandis qu'en P / B primaire, il peut attendre la confirmation de la fin des demandes d'écriture.
• Dans les deux approches, la demande d'écriture est exécutée sur tous les serveurs, P / B le fait plus rapidement en raison de l'exécution parallèle.

Délais de réplication de la chaîne d'échec:

• Tête: l'exécution des demandes de lecture n'est pas interrompue, les demandes d'écriture sont retardées de 2 messages - du maître à tous les serveurs sur la nouvelle tête et du maître à tous les clients sur la nouvelle tête.
• Serveur intermédiaire: les requêtes de lecture ne sont pas interrompues. L'enregistrement des demandes peut être retardé à l'exécution $$$Sent_i$ Il n'y a aucune perte de mise à jour.
• Queue: retard des demandes de lecture et d'écriture pour deux messages - notification $$$queue - 1$ sur la nouvelle queue et alerter les clients sur la nouvelle queue.

Retards d'échec P / B:

• Primaire: délai de 5 messages pour sélectionner un nouvel état primaire et synchroniser.
• Sauvegarde: il n'y a pas de délais de lecture s'il n'y a pas de demandes d'écriture. Lorsqu'une demande d'enregistrement apparaît, un délai de 1 message est possible.

Comme vous pouvez le voir, la pire défaillance de queue pour la réplication de chaîne est plus rapide que la pire pour P / B (primaire).

Les auteurs de cette approche ont effectué des tests de charge, qui ont montré des performances comparables avec le protocole P / B.

3. Requêtes distribuées (réplication en chaîne avec requêtes réparties - CRAQ)

L'approche de base a une faiblesse évidente - queue, qui gère toutes les demandes de lecture. Cela peut entraîner deux problèmes:

• La queue devient un point chaud, c'est-à-dire un serveur qui gère bien plus de demandes que tout autre nœud.
• Lorsque vous placez une chaîne dans plusieurs centres de données, la queue peut être très éloignée, ce qui ralentit les demandes d'écriture.

L'idée de CRAQ est assez simple - laissez les requêtes de lecture arriver à tous les serveurs sauf tail, et pour assurer la cohérence, nous stockons le vecteur des versions d'objet pour les requêtes d'écriture, et en cas d'ambiguïté, les nœuds feront une requête de tail pour obtenir la dernière version fixe.

3.1 CRAQ

Nous formalisons l'architecture CRAQ:
Chaque nœud, à l'exception de tail, traite les requêtes de lecture et renvoie une réponse, et head renvoie une réponse à partir des requêtes d'écriture (comparer avec l'approche de base).


Sur chaque nœud non-queue, plusieurs versions du même objet peuvent être stockées et les versions forment une séquence strictement monotone croissante. Pour chaque version, un attribut supplémentaire est ajouté «propre» ou «sale». Au départ, toutes les versions sont propres.

Dès que le nœud reçoit une demande d'écriture, il ajoute la version reçue à la liste des versions, puis:

• Si le nœud est queue, il marque la version comme propre, à ce moment la version est considérée comme fixe et envoie une confirmation en aval de la chaîne.
• Sinon, il marque la version comme sale et envoie la demande plus loin dans la chaîne.

Dès que le nœud reçoit la confirmation du successeur, il marque la version comme propre et supprime toutes les versions précédentes.

Dès que le nœud reçoit une demande de lecture:

• Si la dernière version de l'objet connue du nœud est propre, elle la renvoie.
• Sinon, il fait une demande de queue pour obtenir la dernière version fixe de l'objet, qu'il retourne au client. (Par construction, une telle version sera toujours sur le nœud).

Pour les applications avec une prédominance de demandes de lecture, les performances du CRAQ croissent linéairement avec la croissance des nœuds , dans le cas d'une prédominance des demandes d'écriture, les performances ne seront pas pires que l'approche de base.

CRAQ peut être situé à la fois dans un ou plusieurs centres de données. Cela permet aux clients de sélectionner les nœuds les plus proches pour augmenter la vitesse des demandes de lecture.

3.2 Cohérence dans le CRAQ

CRAQ fournit une forte cohérence, sauf dans un cas: lorsque le nœud reçoit la dernière version validée de tail, tail peut valider la nouvelle version avant que le nœud ne réponde au client. Dans cette situation, le CRAQ assure une lecture monotone (les demandes de lecture séquentielle ne seront plus du passé, mais peuvent renvoyer d'anciennes données) sur l'ensemble de la chaîne .

Une faible cohérence est également possible:

• Cohérence éventuelle: le nœud ne demandera pas la dernière version validée à tail. Cela perturbera la lecture monotone sur toute la chaîne, mais gardera la lecture monotone sur le même nœud . De plus, il peut résister à la tolérance de partitionnement du réseau .
• Cohérence éventuelle bornée: renvoyer une version sale uniquement jusqu'à un certain point. Par exemple, la différence entre les versions sales et propres ne doit pas dépasser N révisions. Ou un délai.

3.3 Basculement du serveur

Similaire à l'approche de base.

3.4 Facultatif

CRAQ a une fonctionnalité intéressante - vous pouvez utiliser la multidiffusion pendant l'opération d'enregistrement. Supposons que la tête envoie la modification avec une multidiffusion et envoie vers le bas de la chaîne uniquement un identifiant pour cet événement. Si la mise à jour elle-même n'est pas arrivée au nœud, elle peut attendre et la recevoir du nœud suivant lorsque Tail envoie un message de confirmation du changement. De même, la queue peut envoyer une confirmation de fixation avec la multidiffusion.

4. FAWN: une matrice rapide de nœuds Wimpy

Une étude très intéressante, pas directement liée au sujet de cet article, mais sert d'exemple de l'utilisation de la réplication de chaîne.

Les stockages de valeurs-clés hautes performances (Dynamo, memcached, Voldemort) ont des caractéristiques communes - ils nécessitent des E / S, un minimum de calcul, un accès indépendant parallèle à des clés aléatoires en grandes quantités et de petites valeurs de clés jusqu'à 1 Ko.

Les serveurs avec disques durs ne conviennent pas à ces clusters en raison de la longue opération de recherche (temps d'accès aléatoire), et les serveurs avec un grand nombre de DRAM consomment une quantité étonnamment grande d'énergie - 2 Go de DRAM équivalent à 1 To de disque dur.

La construction d'un cluster efficace (bande passante) avec une consommation électrique minimale est l'objectif de l'étude originale. 50% des coûts du serveur sur trois ans sont des coûts d'électricité, et les modes d'économie d'énergie modernes ne sont pas aussi efficaces qu'ils sont annoncés - dans les tests à 20% de charge, la consommation du processeur est restée à 50%, et les autres composants du serveur n'ont pas du tout de modes d'économie d'énergie ( La DRAM, par exemple, fonctionne déjà au minimum). Il est important de noter que dans de tels clusters, l'écart entre le processeur et les E / S s'élargit - un processeur puissant est obligé d'attendre la fin des opérations d'E / S.

4.1 Architecture

Le cluster FAWN est construit sur d'anciens serveurs pour 250 $ (prix 2009), avec un processeur 500 MHz intégré, 512 Mo de RAM, SSD 32 Go. Si vous êtes familier avec l'architecture Amazon Dynamo ou le hachage cohérent, alors vous serez familier avec l'architecture FAWN:

1. Chaque serveur physique contient plusieurs nœuds virtuels, chacun a son propre VID.
2. Les VID forment un anneau, chaque VID est responsable de la plage «derrière lui» (par exemple, A1 est responsable des clés de la plage R1).
3. Pour augmenter la fiabilité, les données sont répliquées dans R des nœuds suivants dans le sens horaire. (par exemple, avec R = 2, la clé sur A1 est répliquée sur B1 et C1), nous obtenons donc une réplication de chaîne (approche de base).
4. Les demandes de lecture vont à la chaîne de queue, c'est-à-dire La lecture de la clé de A1 ira à C1.
5. Les demandes d'écriture vont à la chaîne principale et vont jusqu'à la fin.

La mappe de serveur est stockée sur un cluster de serveurs frontaux, chacun étant responsable de sa liste VID spécifique, et peut rediriger la demande vers un autre serveur frontal.

4.2 Résultats des tests

Dans les tests de charge, le FAWN atteint un QPS (requêtes par seconde) de 90% du QPS sur un lecteur flash à lecture aléatoire.

Le tableau suivant compare le coût total de possession (TCO) de diverses configurations, où la base de Traditional est un serveur de 1 000 $ avec une consommation de 200 W (prix de 2009):

Ainsi, si:

• Big data, quelques requêtes: FAWN + 2 To 7200 RPM
• Une petite quantité de données, beaucoup de demandes: FAWN + 2GB DRAM
• Valeurs moyennes: FAWN + 32GB SSD

Les références

• Réplication de chaîne pour prendre en charge un débit et une disponibilité élevés
• Stockage d'objets sur CRAQ: réplication de chaîne à haut débit pour les charges de travail en lecture seule
• FAWN: Un tableau rapide de nœuds Wimpy