C'est arrivé il y a quelques jours . Les gars du groupe JUG.ru ont invité des conférenciers de rêve (Leslie Lamport ! Cliff Click ! Martin Kleppmann !) et ont consacré deux jours aux systèmes distribués et à l'informatique. Kontur était l'un des trois partenaires de la conférence. Nous avons parlé sur le stand, parlé de notre stockage distribué, joué au bingo et résolu des énigmes.
Ceci est un article avec une analyse des tâches au stand Kontur de l'auteur de leur texte. Qui était sur l'hydre - c'est votre raison de vous souvenir de l'expérience agréable, qui ne l'était pas - une chance d'étirer votre cerveau grand O-notation.
Il y avait même des participants qui ont démantelé le tableau à feuilles mobiles en diapositives pour noter leur décision. Je ne plaisante pas - ils ont remis cette pile de papier pour vérification :
Il y avait trois tâches au total :
- à propos de la sélection des répliques par pondération pour l'équilibrage de charge
- sur le tri des résultats de requête par rapport à une base de données en mémoire
- sur le transfert d'état dans un système distribué avec une topologie en anneau
Tâche 1. ClusterClient
Il était nécessaire de proposer un algorithme pour la sélection efficace de K parmi N répliques pondérées d'un système distribué :
Votre équipe est chargée de développer une bibliothèque cliente pour un cluster massivement distribué de N nœuds. La bibliothèque garderait une trace de diverses métadonnées associées aux nœuds (par exemple, leurs latences, les taux de réponse 4xx/5xx, etc.) et leur attribuerait des poids à virgule flottante W1..WN. Afin de prendre en charge la stratégie d'exécution simultanée, la bibliothèque doit être capable de choisir K nœuds sur N au hasard - une chance d'être sélectionnée doit être proportionnelle au poids d'un nœud.
Proposer un algorithme pour sélectionner efficacement les nœuds. Estimez sa complexité de calcul en utilisant la notation grand O.
Pourquoi tout est en anglais ?
Parce que sous cette forme les participants à la conférence se sont battus avec eux et parce que l'anglais était la langue officielle d'Hydra. Les tâches ressemblaient à ceci :
Prenez du papier et un crayon, réfléchissez, ne vous précipitez pas pour ouvrir les spoilers tout de suite 🙂
Analyse de la solution (vidéo)
A partir de 5h53, seulement 4 minutes :
Et voici comment les gars avec le tableau à feuilles mobiles ont présenté leur solution :
Analyse de la solution (texte)
La solution suivante se trouve en surface : additionnez les poids de toutes les répliques, générez un nombre aléatoire de 0 à la somme de tous les poids, puis choisissez une i-réplique telle que la somme des poids des répliques de 0 à (i-1)ème est inférieur à un nombre aléatoire, et la somme des poids de réplique de 0 à i-ème - plus que lui. Ainsi, il sera possible de sélectionner une réplique, et pour sélectionner la suivante, vous devrez répéter toute la procédure sans tenir compte de la réplique sélectionnée. Avec un tel algorithme, la complexité de choisir une réplique est O(N), la complexité de choisir K répliques est O(N K) ~ O(N2).
La complexité quadratique est mauvaise, mais elle peut être améliorée. Pour ce faire, nous allons construire pour des sommes de poids. Un arbre de profondeur lg N sera obtenu, dans les feuilles duquel il y aura des poids de réplique, et dans les nœuds restants - des sommes partielles, jusqu'à la somme de tous les poids à la racine de l'arbre. Ensuite, nous générons un nombre aléatoire de 0 à la somme de tous les poids, trouvons la ième réplique, la supprimons de l'arbre et répétons la procédure pour trouver les répliques restantes. Avec cet algorithme, la complexité de construction d'un arbre est O(N), la complexité de trouver la i-ième réplique et de la supprimer de l'arbre est O(lg N), la complexité de choisir K répliques est O(N + K lg N) ~ O(N lg N) .
La complexité logarithmique linéaire est plus agréable que la complexité quadratique, en particulier pour les grands K.
C'est cet algorithme Bibliothèques ClusterClient du projet "". (Là, l'arbre est construit en O(N lg N), mais cela n'affecte pas la complexité finale de l'algorithme.)
Tâche 2. Zèbre
Il fallait proposer un algorithme de tri efficace des documents en mémoire par un champ arbitraire non indexé :
Votre équipe est chargée de développer une base de données de documents en mémoire partagée. Une charge de travail courante consisterait à sélectionner les N premiers documents triés par un champ numérique arbitraire (non indexé) à partir d'une collection de taille M (généralement N < 100 << M). Une charge de travail légèrement moins courante consisterait à sélectionner top N après avoir ignoré les documents top S (S ~ N).
Proposer un algorithme pour exécuter efficacement de telles requêtes. Estimez sa complexité de calcul en utilisant la notation grand O dans le cas moyen et les pires scénarios.
Analyse de la solution (vidéo)
A partir de 34h50, seulement 6 minutes :
Analyse de la solution (texte)
Solution de surface : trier tous les documents (par exemple avec ), puis prenez les documents N+S. Dans ce cas, la complexité du tri est en moyenne O(M lg M), au pire O(M2).
Il est évident que trier tous les documents M et n'en prendre qu'une petite partie est inefficace. Afin de ne pas trier tous les documents, un algorithme convient , qui sélectionnera N + S des documents souhaités (ils peuvent être triés par n'importe quel algorithme). Dans ce cas, la complexité diminuera à O(M) en moyenne, tandis que le pire des cas restera le même.
Cependant, vous pouvez le faire encore plus efficacement - utilisez l'algorithme . Dans ce cas, les premiers documents N+S sont ajoutés au tas min ou max (selon le sens du tri), puis chaque document suivant est comparé à la racine de l'arbre, qui contient le document minimum ou maximum actuel, et est ajouté à l'arborescence si nécessaire. . Dans ce cas, la complexité dans le pire des cas, lorsque vous devez constamment reconstruire l'arbre, est O(M lg M), la complexité en moyenne est O(M), comme avec quickselect.
Cependant, le streaming de tas s'avère plus efficace du fait qu'en pratique la plupart des documents peuvent être supprimés sans reconstruire le tas après une seule comparaison avec son élément racine. Un tel tri est implémenté dans la base de données de documents en mémoire Zebra développée et utilisée dans Kontur.
Tâche 3. Échanges d'état
Il fallait proposer l'algorithme le plus efficace pour changer d'état :
Votre équipe est chargée de développer un mécanisme sophistiqué d'échange d'états pour un cluster distribué de N nœuds. L'état du i-ème nœud doit être transféré au (i+1)-ème nœud, l'état du N-ème nœud doit être transféré au premier nœud. La seule opération prise en charge est l'échange d'état lorsque deux nœuds échangent leurs états de manière atomique. On sait qu'un échange d'état prend M millisecondes. Chaque nœud est capable de participer à un seul échange d'état à tout moment.
Combien de temps faut-il pour transférer les états de tous les nœuds d'un cluster ?
Analyse de la solution (texte)
Solution de surface : échangez les états du premier et du deuxième élément, puis du premier et du troisième, puis du premier et du quatrième, et ainsi de suite. Après chaque échange, l'état d'un élément sera dans la position souhaitée. Vous devez faire O(N) permutations et passer O(N M) temps.
Le temps linéaire est long, vous pouvez donc échanger les états des éléments par paires : le premier avec le second, le troisième avec le quatrième, et ainsi de suite. Après chaque échange d'état, un élément sur deux sera dans la bonne position. Vous devez faire des permutations O(lg N) et passer du temps O(M lg N).
Cependant, il est possible de rendre le changement encore plus efficace - non pas en linéaire, mais en temps constant. Pour ce faire, à la première étape, vous devez échanger l'état du premier élément avec le dernier, le second avec l'avant-dernier, et ainsi de suite. L'état du dernier élément sera dans la bonne position. Et maintenant, nous devons échanger l'état du deuxième élément avec le dernier, le troisième avec l'avant-dernier, et ainsi de suite. Après cette ronde d'échanges, les états de tous les éléments seront dans la bonne position. Il y aura O(2M) ~ O(1) permutations au total.
Une telle solution ne surprendra nullement un mathématicien qui se rappelle encore qu'une rotation est une composition de deux symétries axiales. Soit dit en passant, il est trivialement généralisé pour un décalage non pas de un, mais de K < N positions. (Écrivez dans les commentaires comment exactement.)
Vous avez aimé les puzzles ? Connaissez-vous d'autres solutions ? Partagez dans les commentaires.
Et voici quelques liens utiles à la fin :
- en savoir plus sur en contour
- voir les enregistrements internes sur les systèmes distribués
- regarder la série de conférences vidéo»
- abonnez-vous à notre
Source: habr.com