Nous continuons à considérer des exemples d'utilisation de la réplication de chaîne. Les définitions et architectures de base ont été données dans la première partie , je vous recommande de vous familiariser avec celle-ci avant de lire la deuxième partie.

Dans cet article, nous étudierons les systèmes suivants:

• Hibari est un référentiel distribué tolérant aux pannes écrit en erlang.
• HyperDex - stockage de valeurs-clés distribué avec prise en charge de la recherche rapide par attributs secondaires et de la recherche par plage.
• ChainReaction - Causalité + cohérence et géo-réplication.
• Construire un système distribué sans utiliser de processus de surveillance / reconfiguration externes supplémentaires.

5. Hibari

Hibari est un référentiel KV tolérant aux pannes distribué écrit en erlang. Utilise la réplication de chaîne (approche de base), c'est-à-dire atteint une cohérence stricte. Lors des tests, Hibari affiche des performances élevées - plusieurs milliers de mises à jour par seconde sont réalisées sur des serveurs à deux unités (requêtes de 1 Ko)

5.1 Architecture

Un hachage cohérent est utilisé pour placer des données. La base de stockage est constituée de blocs physiques et logiques. La brique physique est un serveur avec Linux, peut-être une instance EC2 et, en général, la machine virtuelle dans son ensemble. Une brique logique est une instance de stockage avec laquelle les principaux processus du cluster fonctionnent, et chaque bloc est un nœud d' une chaîne. Dans l'exemple ci-dessous, le cluster est configuré avec 2 blocs logiques sur chaque bloc physique et avec une longueur de chaîne de 2. Notez que les nœuds de la chaîne sont «étalés» sur les blocs physiques pour augmenter la fiabilité.

Le processus maître (voir la définition dans la première partie) s'appelle le serveur Admin .

Les données sont stockées dans des «tables», qui sont simplement divisées en espaces de noms, chaque table est stockée dans au moins une chaîne et chaque chaîne stocke les données dans une seule table.

Le client Hibari reçoit des mises à jour du serveur d'administration avec une liste de toutes les têtes et queues de toutes les chaînes (et toutes les tables). Ainsi, les clients savent immédiatement à quel nœud logique envoyer la demande.

5.2 Hachage

Hibari utilise une paire $$$\ {T, K \}$ pour déterminer le nom de la chaîne qui stocke la clé $$$K$ dans le tableau $$$T$ : clé $$$K$ mappé à l'intervalle $$$[0,1, 1,0)$ (en utilisant MD5), qui est divisé en sections dont une chaîne est responsable. Les sections peuvent être de différentes largeurs, en fonction du "poids" de la chaîne, par exemple:



Ainsi, si certains blocs physiques sont très puissants, les chaînes situées sur celui-ci peuvent recevoir des sections plus larges (alors plus de clés tomberont dessus).

6. HyperDex

L'objectif de ce projet était de créer un référentiel de valeurs-clés distribué qui, contrairement à d'autres solutions populaires (BigTable, Cassandra, Dynamo), prendra en charge une recherche rapide d'attributs secondaires et pourra rapidement effectuer une recherche par plage. Par exemple, dans les systèmes précédemment considérés, pour rechercher toutes les valeurs dans une certaine plage, vous devez passer par tous les serveurs, ce qui, évidemment, est inacceptable. HyperDex résout ce problème en utilisant le hachage hyperspace .

6.1 Architecture

L'idée du hachage hyperespace est de construire $$$n$ -espace dimensionnel où chaque attribut correspond à un axe de coordonnées. Par exemple, pour les objets (prénom, nom, numéro de téléphone), l'espace peut ressembler à ceci:



L'hyperplan gris passe à travers toutes les clés, où nom = Smith, jaune - à travers toutes les clés, où prénom = John. L'intersection de ces avions constitue une réponse à la requête de recherche des numéros de téléphone des personnes portant le nom John et le nom Smith. Donc, la demande de $$$k$ retourne les attributs $$$(n-k)$ -sous-espace dimensionnel.

L'espace de recherche est divisé en $$$n$ -régions disjointes dimensionnelles, et chaque région est affectée à un seul serveur. Un objet avec les coordonnées d'une région est stocké sur le serveur de cette région. Ainsi, un hachage est construit entre les objets et les serveurs.

Une requête de recherche (par plage) déterminera les régions incluses dans l'hyperplan résultant et, ainsi, réduira au minimum le nombre de serveurs interrogés.

Il y a un problème avec cette approche - le nombre de serveurs requis croît de façon exponentielle à partir du nombre d'attributs, c'est-à-dire si attributs $$$k$ alors tu as besoin $$$O (2 ^ k)$ serveurs. Pour résoudre ce problème, HyperDex applique une partition d'hyperespace en sous-espaces (avec une dimension inférieure) avec, respectivement, un sous-ensemble d'attributs:

6.2 Réplication

Pour garantir une cohérence stricte, les auteurs ont développé une approche spéciale basée sur la réplication de chaîne - chaînage dépendant de la valeur , où chaque nœud suivant est déterminé en hachant l'attribut correspondant. Par exemple, la clé $$$("John", "Smith")$ il sera d'abord haché dans l'espace clé (nous obtenons la chaîne de tête, également appelée point leader ), puis le hachage de$$ $ inline $ "John" $ inline $ à la coordonnée sur l'axe correspondant et ainsi de suite. (Voir l'image ci-dessous pour un exemple de mise à jour. $$$u_1$ )

Toutes les mises à jour passent par un point leader, qui commande les demandes (linéarisation).



Si la mise à jour entraîne un changement dans la région, la première version est d'abord écrite immédiatement après l'ancienne (voir mise à jour $$$u_2$ ), et après avoir reçu l'ACK de la queue, le lien vers l'ancienne version du serveur précédent sera modifié. Aux demandes simultanées (par ex. $$$u_2$ et $$$u_3$ ) n'a pas violé le leader du point de cohérence qui ajoute le versionnement et d'autres métadonnées au serveur, s'il est reçu $$$u_3$ avant $$$u_2$ pourrait déterminer que la commande est rompue et que vous devez attendre $$$u_2$ .

7. ChainReaction

Un modèle de convergence causale + est utilisé, qui ajoute la condition d'une convergence sans conflit à la convergence causale (causale). Pour réaliser la convergence causale, des métadonnées sont ajoutées à chaque demande, ce qui indique les versions de toutes les clés dépendantes. ChainReaction vous permet de faire de la géoréplication dans plusieurs centres de données et est un développement ultérieur de l'idée de CRAQ.

7.1 Architecture

L'architecture de FAWN est utilisée avec des modifications mineures - chaque contrôleur de domaine se compose de serveurs de données - backends (stockage de données, réplication, forme un anneau DHT) et des proxys clients - frontaux (envoi d'une demande à un nœud spécifique). Chaque clé est répliquée sur R nœuds consécutifs, formant une chaîne. Les demandes de lecture sont traitées par tail et écrites par head.

7.2 Un centre de données

Nous notons une propriété importante découlant de la réplication de chaîne - si le nœud $$$k$ cohérent avec certaines opérations client, puis tous les nœuds précédents - aussi. Donc, si l'opération $$$Op$ a été vue pour la dernière fois par nous sur le site $$$j$ , alors toutes les causes dépendantes (de $$$Op$ ) les opérations de lecture ne peuvent être effectuées que sur les nœuds de la tête vers $$$j$ . Dès que $$$Op$ sera exécuté sur la queue - il n'y aura aucune restriction de lecture. Indique les opérations d'écriture effectuées par tail dans le DC $$$d$ comme DC-Write-Stable (d) .

Chaque client stocke une liste (métadonnées) de toutes les clés demandées par le client au format (clé, version, chainIndex), où chainIndex est la position du nœud dans la chaîne qui a répondu à la dernière demande de clé. Les métadonnées sont stockées uniquement pour les clés dont le client ne sait pas si elles sont stables en écriture DC (d) ou non .

7.2.1 Opération d'écriture

Notez qu'une fois que l'opération est devenue DC-Write-Stable (d), aucune demande de lecture ne peut lire les versions précédentes.

Pour chaque demande d'écriture, une liste de toutes les clés sur lesquelles des opérations de lecture ont été effectuées avant l'ajout de la dernière opération d'écriture. Dès que le proxy client reçoit la demande, il effectue des lectures de blocage sur la queue de toutes les clés des métadonnées (nous attendons la confirmation de la disponibilité de la même version ou d'une version plus récente, en d'autres termes, nous remplissons la condition de cohérence causale). Dès réception des confirmations, la demande d'écriture est envoyée au responsable de la chaîne correspondante.



Une fois la nouvelle valeur stockée sur $$$k$ nœuds de la chaîne, une notification est envoyée au client (avec l'index du dernier nœud). Le client met à jour le chainIndex et supprime les métadonnées des clés envoyées, comme il est devenu connu d'eux qu'ils sont DC-Write-Stable (d). En parallèle, l'enregistrement se poursuit - propagation paresseuse . Ainsi, la priorité est donnée à l'écriture des opérations sur le premier $$$k$ nœuds. Dès que tail stocke la nouvelle version de la clé, une notification est envoyée au client et transmise à tous les nœuds de la chaîne afin qu'ils marquent la clé comme stable.

7.2.2 Opération de lecture

Le proxy client envoie une demande de lecture à $$$index: = rand (1, chainIndex)$ nœud dans le circuit, tout en répartissant la charge. En réponse, le nœud envoie la valeur et la version de cette valeur. La réponse est envoyée au client, tandis que:

• Si la version est stable, le nouveau chainIndex est égal à la taille de la chaîne.
• Si la version est plus récente, le nouveau chainIndex = index.
• Sinon, chainIndex ne change pas.

7.2.3 Basculement de nœud

Elle est presque complètement identique à l'approche de base, avec quelques différences dans le fait que dans certains cas, le chainIndex sur le client devient invalide - cela est facilement déterminé lors de l'exécution des demandes (il n'y a pas de clé avec cette version) et la demande est redirigée vers la tête de la chaîne pour rechercher le nœud avec la version souhaitée.

7.3 Plusieurs ( $$$N$ ) centres de données (géo-réplication)

Nous prenons comme base les algorithmes d'une architecture à serveur unique et les adaptons au minimum. Pour commencer, dans les métadonnées, au lieu des seules valeurs de version et chainIndex, nous avons besoin de vecteurs versionnés de N dimensions.

Nous définissons Global-Write-Stable d'une manière similaire avec DC-Write-Stable (d) - l'opération d'écriture est considérée comme Global-Write-Stable si elle a été effectuée sur des queues dans tous les DC.

Un nouveau composant apparaît dans chaque DC - remote_proxy , sa tâche est de recevoir / envoyer des mises à jour à partir d'autres DC.

7.3.1 Exécution d'une opération d'écriture (sur le serveur $$$i$ )

Le début est similaire à une architecture à serveur unique - nous effectuons des lectures de blocage, écrivons sur le premier $$$k$ noeuds d'une chaîne. À ce stade, le proxy client envoie au client un nouveau vecteur chainIndex, où les zéros sont partout, sauf pour la position $$$i$ - il y a un sens $$$k$ . Ensuite - comme d'habitude. Une opération supplémentaire à la toute fin - la mise à jour est envoyée à remote_proxy, qui accumule plusieurs requêtes, puis envoie tout.

Deux problèmes se posent ici:

• Comment garantir les dépendances entre différentes mises à jour provenant de différents DC?
  
  Chaque remote_proxy stocke un vecteur de version local $$$rvp$ les dimensions $$$N$ , qui stocke le nombre de mises à jour envoyées et reçues et l'envoie dans chaque mise à jour. Ainsi, lors de la réception d'une mise à jour d'un autre contrôleur de domaine, remote_proxy vérifie les compteurs, et si le compteur local est inférieur, l'opération est bloquée jusqu'à ce que la mise à jour correspondante soit reçue.
• Comment fournir des dépendances pour cette opération dans d'autres DC?
  
  Ceci est réalisé en utilisant un filtre Bloom. Lors de l'exécution des opérations d'écriture / lecture à partir du proxy client, en plus des métadonnées, un filtre de bloom est également envoyé pour chaque clé (appelés filtres de réponse). Ces filtres sont stockés dans la liste AccessedObjects , et lors de la demande d'opérations d'écriture / lecture, les métadonnées envoient également des filtres OU envoyés des clés (appelés filtre de dépendance). De même, après l'opération d'écriture, les filtres correspondants sont supprimés. Lors de l'envoi d'une opération d'écriture à un autre contrôleur de domaine, un filtre de dépendance et un filtre de réponse pour cette demande sont également envoyés.
  
  En outre, le contrôleur de domaine distant, après avoir reçu toutes ces informations, vérifie que si les bits définis du filtre de réponse coïncident avec les bits définis de plusieurs filtres de requête, ces opérations sont potentiellement dépendantes de manière occasionnelle. Potentiellement - parce qu'un filtre de floraison.

7.3.2 Opération de lecture

De manière similaire à une architecture à serveur unique, ajustée pour l'utilisation du vecteur chainIndex au lieu d'un scalaire et la possibilité de l'absence d'une clé dans le contrôleur de domaine (car les mises à jour sont asynchrones) - attendez ou redirigez la demande vers un autre contrôleur de domaine.

7.3.3 Résolution des conflits

Grâce aux métadonnées, les opérations liées à la causalité sont toujours effectuées dans le bon ordre (parfois vous devez bloquer le processus pour cela). Mais les changements de concurrence dans différents pays en développement peuvent conduire à des conflits. Pour résoudre de telles situations, Last Write Wins est utilisé, pour lequel une paire est présente dans chaque opération de mise à jour $$$(horloge, s)$ où $$$c$ - heures sur proxy, et $$$s$ - id de DC.

7.3.4 Gestion des défaillances de nœuds

Similaire à l'architecture à serveur unique.

8. Tirer parti du sharding dans la conception de protocoles de réplication évolutifs

L'objectif de l'étude est de construire un système distribué avec des fragments et avec réplication sans utiliser de processus maître externe pour reconfigurer / surveiller le cluster.

Dans les principales approches actuelles, les auteurs constatent les inconvénients suivants:

Réplication:

• Principal / Sauvegarde - conduit à une divergence dans l'état si le principal a été identifié par erreur comme ayant échoué.
• Intersection de quorum - peut entraîner une divergence d'état lors de la reconfiguration du cluster.

Cohérence stricte:

• Les protocoles s'appuient sur des algorithmes de vote majoritaire (par exemple, Paxos) si nécessaire $$ faire des nœuds $$$N$ nœuds.

Détection des défaillances de nœuds:

• P / B et CR impliquent la présence d'une détection idéale des nœuds défaillants avec un modèle fail-stop, ce qui est inaccessible en pratique et vous devez choisir un intervalle de balayage approprié.
• ZooKeeper est soumis aux mêmes problèmes - avec un grand nombre de clients, un temps considérable (> 1 seconde) leur est nécessaire pour mettre à jour la configuration.

L'approche proposée par les auteurs, appelée réplication élastique , est dépourvue de ces défauts et présente les caractéristiques suivantes:

• Cohérence stricte.
• Pour résister à la chute $$$N$ les nœuds doivent avoir $$$N + 1$ noeud.
• Reconfiguration sans perte de cohérence.
• Il n'y a pas besoin de protocoles de consensus basés sur un vote majoritaire.

Plaque de résumé:

8.1 Organisation des répliques

Chaque fragment définit une séquence de configurations $$$\ mathcal {C} = C_1 :: C_2 :: C_3 \ dots$ par exemple, la nouvelle configuration ne contient pas de réplique déchue $$$\ mathcal {C} = \ mathcal {C}: :( Répliques \ setminus R_j)$

Chaque élément de la séquence de configuration comprend:

• répliques - un ensemble de répliques.
• orderer - id d'une réplique avec un rôle spécial (voir ci-dessous).

Chaque fragment est représenté par un ensemble de répliques (par construction - $$$N$ ), c'est-à-dire nous ne divisons pas les rôles de «fragment» et de «réplique».

Chaque réplique stocke les données suivantes:

• conf - id de la configuration à laquelle cette réplique appartient.
• orderer - quelle réplique est l'ordonnanceur de cette configuration.
• mode - mode réplique, l'un des trois: $$$EN ATTENTE$ (toutes les répliques de $$$C_1$ ), $$$ACTIVE$ (toutes les répliques de $$$C_1$ ), $$$IMMUTABLE$ .
• historique - séquence d'opérations sur les données de réplique réelles $$$op_1 :: op_2 :: \ dots$ (ou juste une condition).
• stable - la longueur maximale du préfixe d'historique fixé par cette réplique. De toute évidence, $$$0 <= stable <= longueur (historique)$ .

Le principal objectif d'un réplicateur est d'envoyer des demandes au reste des répliques et de conserver le plus grand préfixe d'historique:

8.2 Organisation des fragments

Les éclats sont combinés en anneaux appelés bandes élastiques . Chaque éclat appartient à un seul anneau. Le précurseur de chaque éclat $$$X$ joue un rôle spécial - il est séquenceur pour lui. Le travail du séquenceur est de donner à son successeur une nouvelle configuration en cas de panne de réplique.


Deux conditions sont requises:

• Chaque bande élastique possède au moins un éclat et une réplique fonctionnelle.
• Chaque bande élastique a au moins un éclat, dans lequel toutes les répliques fonctionnent.

La deuxième condition semble trop stricte, mais elle équivaut à la condition «traditionnelle» que le processus maître ne tombe jamais.

8.3 Utilisation de la réplication de chaîne

Comme vous l'avez peut-être deviné, les répliques sont organisées en chaîne (approche de base) - le commandeur sera à la tête, avec de légères différences:

• En cas d'échec dans CR, le nœud est jeté hors de la chaîne (et remplacé par un nouveau), dans ER - une nouvelle chaîne est créée.
• Les demandes de lecture dans CR sont traitées par queue, dans ER, elles passent par toute la chaîne de la même manière que les demandes d'écriture.

8.5 Reconfiguration en cas de panne

• Les répliques sont surveillées par les répliques de votre fragment et les répliques d'un fragment de séquenceur.
• Dès qu'une défaillance est détectée, les répliques envoient une commande à ce sujet.
• Sequencer envoie une nouvelle configuration (sans réplique défaillante).
• Une nouvelle réplique est créée qui synchronise son état avec la bande élastique.
• Après cela, le séquenceur envoie la nouvelle configuration avec la réplique ajoutée.

Les références

• Hibari
• hyperdex.orgerdex.org
• HyperDex: un magasin de valeurs-clés distribué et consultable
• Réaction en chaîne
• Tirer parti du sharding dans la conception de protocoles de réplication évolutifs