Il y a quelques jours, il y a eu une conférence Hydra . Les gars du groupe JUG.ru ont invité les conférenciers de rêve (Leslie Lampport! Cliff Click! Martin Kleppmann!) Et ont consacré deux jours aux systèmes distribués et à l'informatique. Contour était l'un des trois partenaires de la conférence. Nous avons parlé sur le stand, parlé de nos installations de stockage distribuées, joué au bingo, résolu des problèmes.
Il s'agit d'un article avec une analyse des tâches sur le stand Contour de l'auteur de leur texte. Qui était sur Hydra est votre raison de vous rappeler des impressions agréables, qui ne l'étaient pas - une chance d'étirer votre cerveau sur une grande note O.
Il y avait même des participants qui ont démonté le tableau-papier en diapositives pour enregistrer leur décision. Je ne plaisante pas - ils ont remis pour vérifier ce paquet de papier:
Il y avait trois tâches au total:
- sur le choix des répliques pour les poids pour l'équilibrage de charge
- sur le tri des résultats d'une requête dans 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 a fallu 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 des diverses métadonnées associées aux nœuds (par exemple, leurs latences, taux de réponse 4xx / 5xx, etc.) et leur attribuerait des poids à virgule flottante W 1 ..W N. Afin de prendre en charge la stratégie d'exécution simultanée, la bibliothèque devrait être en mesure de choisir K de N nœuds au hasard - une chance d'être sélectionnée devrait être proportionnelle au poids d'un nœud.
Proposer un algorithme pour sélectionner efficacement les nœuds. Estimer sa complexité de calcul à l'aide de la grande notation 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, pensez, ne vous précipitez pas pour ouvrir immédiatement les spoilers :)
Débriefing (vidéo)À partir de 5 h 53, seulement 4 minutes:
Et voici comment ces gars avec un tableau à feuilles mobiles ont présenté leur décision:
Analyse de la décision (texte)En surface, il existe une telle solution: additionner les poids de toutes les répliques, générer un nombre aléatoire de 0 à la somme de tous les poids, puis choisir une réplique i de telle sorte que la somme des poids de réplique de 0 à la (i-1) e soit inférieure au nombre aléatoire et la somme des poids de réplique de 0 au i-ème - plus que ça. Il s'avérera de choisir une réplique et pour sélectionner la suivante, vous devez répéter la procédure entière sans considérer la réplique sélectionnée. Avec un tel algorithme, la complexité du choix d'une réplique est O (N), la complexité du choix de K répliques est O (N · K) ~ O (N 2 ).
La complexité quadratique est mauvaise, mais elle peut être améliorée. Pour ce faire, construisez un arbre de segments pour les sommes de poids. Cela produira un arbre avec une profondeur de log N, dans les feuilles desquelles 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, supprimons-la de l'arborescence et répétons la procédure pour rechercher les répliques restantes. Avec un tel algorithme, la complexité de la construction d'un arbre est O (N), la complexité de trouver la ième réplique et de la supprimer de l'arbre est O (log N), la complexité de choisir K répliques est O (N + K log N) ~ O (N log N) .
La complexité logarithmique linéaire est plus agréable que la complexité quadratique, en particulier pour les grands K.
Cet algorithme est implémenté dans le code de la bibliothèque ClusterClient du projet Vostok .
Tâche 2. Zebra
Il a fallu 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 fragmentée. Une charge de travail courante serait de 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 les N premiers après avoir ignoré les S principaux documents (S ~ N).
Proposer un algorithme pour exécuter efficacement ces requêtes. Estimer sa complexité de calcul en utilisant la notation O grand dans le cas moyen et les pires scénarios.
Débriefing (vidéo)Départ à 34h50, seulement 6 minutes:
Analyse de la décision (texte)La solution est apparente: trier tous les documents (par exemple, en utilisant le tri rapide ), puis prendre des documents N + S. Dans ce cas, la complexité du tri est en moyenne O (M lg M), au pire - O (M 2 ).
De toute évidence, le tri de tous les documents M afin de n'en prendre qu'une petite partie est inefficace. Afin de ne pas trier tous les documents, l'algorithme de sélection rapide convient , qui sélectionnera N + S des documents nécessaires (ils peuvent être triés par n'importe quel algorithme). Dans ce cas, la complexité diminue en moyenne à O (M) et le pire des cas reste le même.
Cependant, vous pouvez le faire encore plus efficacement - utilisez l'algorithme de streaming de tas binaire . 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'arborescence, qui contient le document minimum ou maximum pour le moment, et est ajouté à l'arborescence si nécessaire . Dans ce cas, la complexité dans le pire des cas est lorsque vous devez constamment reconstruire l'arbre - O (M lg (N + S)), la complexité moyenne est O (M), comme avec quickselect.
Cependant, la diffusion en continu de tas est plus efficace car, dans la 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 en mémoire des documents Zebra développée et utilisée dans le Circuit.
Tâche 3. Swaps d'état
Il a fallu proposer l'algorithme le plus efficace pour le changement d'état:
Votre équipe est chargée de développer un mécanisme d'échange d'état sophistiqué 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 atomiquement. Il est connu qu'un échange d'état prend M millisecondes. Chaque nœud est capable de participer à un échange d'état unique à tout moment.
Combien de temps faut-il pour transférer les états de tous les nœuds d'un cluster?
Analyse de la décision (texte)Une solution en 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, etc. Après chaque échange, l'état d'un élément sera à la position souhaitée. Vous devez faire des permutations O (N) et passer du temps O (N · M).
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, etc. Après chaque échange, l'état de chaque deuxième élément sera dans la position souhaitée. Nous devrons faire des permutations O (log N) et passer du temps O (M log N N).
Cependant, vous pouvez rendre le changement encore plus efficace - non pas en linéaire, mais en temps constant. Pour ce faire, dans la première étape, vous devez échanger l'état du premier élément avec le dernier, le second avec l'avant-dernier, etc. L'état du dernier élément sera à la position souhaitée. Et maintenant, vous devez échanger l'état du deuxième élément avec le dernier, le troisième avec l'avant-dernier, etc. Après ce cycle d'échanges, les états de tous les éléments seront dans la bonne position. Au total, des permutations O (2M) ~ O (1) seront effectuées.
Une telle solution ne surprendra pas un mathématicien qui se souvient encore que la rotation est une composition de deux symétries axiales. Soit dit en passant, il est trivialement généralisé de se déplacer non pas d'un, mais de K <N positions. (Écrivez exactement comment dans les commentaires.)
Aimez-vous les puzzles? Connaissez-vous d'autres solutions? Partagez dans les commentaires.
Et voici quelques liens utiles à la fin: