Dans les systèmes distribués, il existe un certain nombre de problèmes fondamentaux: des transactions distribuées efficaces, un traitement des données exact, une synchronisation précise des horloges physiques. Pour résoudre ce dernier problème , différents types d' horloges logiques ont été inventés .
Néanmoins, les horloges vectorielles ont des propriétés désagréables: elles introduisent une dépendance conditionnelle entre des événements là où elle n'existe pas et la perdent là où elle se trouve réellement.
Cependant, vous pouvez trouver quelque chose de plus fiable - Kronos. Dans l'article, nous examinerons l'algorithme de comptabilité de relation de cause à effet et son application pour créer le référentiel de valeurs-clés avec des transactions distribuées.
Les problèmes
Comme déjà mentionné, il y a un certain nombre de problèmes avec l'horloge logique:
Des dépendances inexistantes surviennent parce qu'une horloge logique introduit un ordre complet sur les événements - c'est-à-dire que l'un des deux événements peut être considéré comme conditionnel plus tôt et conditionnellement plus tard. Le contrat est conditionnel, car il est impossible de déterminer avec précision la relation entre les événements dans le temps, notamment en raison de la théorie spéciale de la relativité.
D'un autre côté, une horloge logique ne considère que l'interconnexion via des messages au sein du système. Si deux événements sont connectés, mais en dehors du système, par exemple via l'utilisateur (ajout de marchandises au panier dans une partie du système -> paiement de la commande), l'horloge logique peut manquer une telle relation.
Les horloges logiques ne sont pas accessibles de l'extérieur, et il est également difficile d'interconnecter plusieurs composants indépendants (système de fichiers distribué, services de traitement des demandes, analyse).
Solution
Un article de Kronos de 2014 : La conception et la mise en œuvre d'un service de commande d'événements propose une solution - un service autonome qui prendra en compte les relations de cause à effet dans les événements.
L'abstraction principale à l'intérieur de Kronos est un événement dans lequel un ordre partiel est introduit. La relation de causalité est transitive - c'est-à-dire si, par exemple, nous savons que la création d'un fichier précède sa modification et que la modification précède la suppression, nous pouvons conclure logiquement que la création s'est produite avant la suppression.
L'API minimale peut être définie par l'ensemble de méthodes suivant:
| La méthode | Résultat | Commentaire |
|---|
create_event() | e | Crée un nouvel événement à Kronos |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | Pour chaque paire de la demande, elle renvoie la direction de la relation de cause à effet ou la simultanéité des événements |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | Pour chaque paire de la demande, définit le sens de la causalité |
acquire_ref(e) | OK | Augmente le compteur de référence pour cet événement. |
release_ref(e) | OK | Diminue le nombre de références pour cet événement. |
Implémentation
Il est logique que le système soit basé sur un graphe orienté des événements, avec une recherche efficace en largeur pour vérifier la relation des événements, un mécanisme de stabilité en cas d'échec et un ramasse-miettes.
Comme le montre l'API, la demande assign_order accepte assign_order un type de relation causale: must ou prefer . must correspond à des invariants stricts - par exemple, _->_ , prefer peut ne pas être appliqué s'il entre en conflit avec des relations must . Un exemple d'utilisation de prefer est que les requêtes qui sont venues plus tôt sont mieux encapsulées plus tôt, mais cela n'affecte pas l'exactitude.
BFS efficace
Dans notre cas, le graphique peut être volumineux, mais les événements pour lesquels des demandes de vérification seront exécutées seront généralement proches. Par conséquent, vous devez exécuter BFS plus rapidement pour de tels cas.
Dans l'implémentation standard, l'endroit le plus long est l'initialisation du tableau de sommets visités, ce qui prend toujours un temps égal au nombre de sommets dans le graphe. Au lieu de cela, vous pouvez utiliser une table de hachage ou appliquer d'autres astuces.
Collecte des ordures
Comme vous pouvez le voir dans le tableau, il existe deux autres méthodes: acquire_ref et release_ref .
A l'intérieur de Kronos, un compteur de référence est stocké pour chaque événement. Alors que certains services traitent l'événement ou se réservent la possibilité d'ajouter de nouveaux événements qui se produisent après l' événement en cours, il stocke le lien. Lorsque ce besoin disparaît, le service appelle release_ref .
Kronos supprimera l'événement lorsque toutes les conditions seront remplies:
- Le nombre de liens atteint zéro
- Tous les événements qui précèdent sont déjà supprimés du graphique.
Cette approche ne limite pas les requêtes possibles, mais économise de la mémoire dans Kronos.
Les applications
Envisagez l'utilisation du système en utilisant l'exemple du stockage de valeur-clé avec des transactions distribuées.
Supposons qu'il y ait plusieurs serveurs, chaque serveur est responsable d'une plage de clés.
Chaque transaction correspond à un événement à Kronos. Pour chaque clé, le serveur doit enregistrer le numéro de la dernière transaction à laquelle cette clé a participé. Le client crée un événement et envoie son numéro à tous les serveurs dont les clés sont affectées par cette transaction. Le serveur tente de créer une dépendance dans Kronos entre le numéro de transaction actuel et l'événement précédent qui a été enregistré pour cette clé. Si vous ne pouvez pas créer la dépendance, la transaction est reconnue comme infructueuse (notez que jusqu'à présent, il n'y a pas encore d'interaction avec les données).
Si toutes les opérations d'ajout de dépendance se sont déroulées avec succès, cela signifie que la transaction aura lieu et pourra être effectuée. Les serveurs en sont informés par le client et commencent à exécuter des parties de la transaction.
Notez que ces transactions seront ACID :
- Atomicité : la transaction ne sera pas planifiée dans Kronos, ou sera planifiée pour être exécutée sur tous les nœuds.
- Cohérence : automatiquement dans les référentiels KV.
- Isolement : si deux transactions se croisent en fonction des données, alors elles seront connectées par une relation causale dans Kronos, ce qui signifie que l'une sera exécutée avant l'autre.
- Durabilité : Kronos étant résistant aux chutes et supposant que chaque réplique du coffre-fort est également stable, la seule chose à prouver est la persistance des données des transactions en attente. En effet, si la transaction est marquée par le client comme réussie, mais que l'enregistrement n'est pas encore terminé sur le serveur, ce fait est facile à établir, car le serveur garde également une trace des parties terminées des transactions.
Performances
La mise en œuvre d'un tel stockage KV peut en effet être efficace. L'article d'origine cite des données selon lesquelles l'implémentation décrite du stockage KV est 4 fois plus rapide que la transaction basée sur les verrous.
De plus, par rapport à MongoDB, le système au-dessus de Kronos n'a que 6% de retard, malgré le fait que MongoDB n'utilise pas de transactions distribuées.
Analyse
Cependant, le fonctionnement de Kronos présente plusieurs inconvénients.
- Premièrement, il y a la surcharge d'accès à Kronos - chaque demande nécessitera au moins un appel.
- Kronos sera également un point de défaillance unique - les auteurs de l'article n'offrent pas de moyens de partitionner le graphique des événements.
- Ce serait bien d'ajouter un certain nombre de méthodes au système. Par exemple, dans l'exemple avec KV-stockage, il serait bien d'avoir un rappel qui informerait le serveur de l'état de la transaction - il a été ajouté avec succès au graphique avec toutes les dépendances nécessaires - ou, inversement, la transaction n'a pas pu être terminée.
Néanmoins, le système décrit permet un contrôle flexible d'une relation causale entre les événements, garantissant une conformité prévisible avec les invariants nécessaires.
Conclusion
À ce sujet, nous, à GoTo School, enseignons aux étudiants et aux écoliers en direction des systèmes distribués.
Et il y a les algorithmes et les applications , la programmation appliquée, la bioinformatique et l' analyse des données
Venez à notre école d'automne du 27 octobre au 4 novembre ou à l'école d'hiver début janvier.
Et si vous n'êtes plus étudiant ou écolier, venez enseigner .