Sharding : verso

2.1 Comment fragmenter et ralentir N fois ?

Vous pouvez fragmenter et ralentir exactement N fois comme ceci :

• Envoyez les requêtes docs00...docs15 de manière séquentielle , et non en parallèle.
• Dans les requêtes simples, faites une sélection non par clé , WHERE quelquechose=234.

Dans ce cas, la partie sérialisée (serial) ne prend pas 1% et non 5%, mais environ 20% dans les bases de données modernes. Vous pouvez également obtenir 50 % de la partie sérialisée si vous accédez à la base de données à l'aide d'un protocole binaire extrêmement efficace ou si vous la liez en tant que bibliothèque dynamique dans un script Python.

Le reste du temps de traitement d'une requête simple sera occupé par des opérations non parallélisables d'analyse syntaxique de la requête, de préparation du plan, etc. Autrement dit, ne pas lire le dossier ralentit.

Si nous divisons les données en 16 tables et les exécutons de manière séquentielle, comme il est d'usage dans le langage de programmation PHP, par exemple, (ce n'est pas très bon pour lancer des processus asynchrones), alors nous obtiendrons un ralentissement de 16 fois. Et, peut-être, plus encore, car des allers-retours réseau seront également ajoutés.

Du coup, le choix du langage de programmation est important lors du sharding.

N'oubliez pas le choix du langage de programmation, car si vous envoyez des requêtes à la base de données (ou au serveur de recherche) de manière séquentielle, alors d'où vient l'accélération ? Au contraire, il y aura un ralentissement.

2.2 À propos du semi-automatique

Par endroits, la sophistication des technologies de l'information inspire l'horreur chtonienne. Par exemple, MySQL prêt à l'emploi n'avait pas la mise en œuvre du sharding sur certaines versions à coup sûr, cependant, les tailles des bases de données utilisées au combat atteignent des valeurs indécentes.

L'humanité souffrante face aux DBA individuels est tourmentée depuis des années et écrit plusieurs mauvaises solutions de partitionnement basées sur rien. Après cela, une solution de partitionnement plus ou moins décente est écrite appelée ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Ceci est un exemple bien connu de cette tache très.

ProxySQL dans son ensemble est, bien sûr, une solution d'entreprise à part entière pour l'open source, pour le routage et plus encore. Mais l'une des tâches à résoudre est le sharding pour une base de données, qui en elle-même ne peut pas se sharder de manière humaine. Vous voyez, il n'y a pas de commutateur "shards = 16", vous devez soit réécrire chaque requête dans l'application, et il y en a beaucoup par endroits, soit mettre une couche intermédiaire entre l'application et la base de données qui ressemble : "Hmm ... SÉLECTIONNER * À PARTIR de documents ? Oui, il doit être divisé en 16 petits SELECT * FROM server1.document1, SELECT * FROM server2.document2 - à ce serveur avec un tel login / mot de passe, à celui-ci avec un autre. Si l'on n'a pas répondu, alors ... ", etc. Exactement cela peut être fait par des taches intermédiaires. Ils sont légèrement inférieurs à ceux de toutes les bases de données. Pour PostgreSQL, pour autant que je sache,

La configuration de chaque correctif spécifique est un sujet géant distinct qui ne rentrera pas dans un seul rapport, nous ne discuterons donc que des concepts de base. Parlons un peu de la théorie du buzz.

2.3 Automatisation parfaite absolue ?

Toute la théorie du high dans le cas du sharding dans cette lettre F() , le principe de base est toujours à peu près le même : shard_id = F(object).

Sharding - de quoi s'agit-il? Nous avons 2 milliards d'enregistrements (soit 64). Nous voulons les diviser en plusieurs morceaux. Une question inattendue se pose - comment? Par quel principe dois-je éparpiller mes 2 milliards d'enregistrements (soit 64) sur 16 serveurs à ma disposition ?

Le mathématicien latent en nous devrait suggérer qu'au final il y a toujours une fonction magique qui, pour chaque document (objet, ligne, etc.), déterminera dans quel morceau le mettre.

En approfondissant les mathématiques, cette fonction dépend toujours non seulement de l'objet lui-même (la ligne elle-même), mais également de paramètres externes tels que le nombre total de fragments. Une fonction qui pour chaque objet doit dire où le mettre, ne peut pas retourner une valeur de plus qu'il y a de serveurs dans le système. Et les fonctions sont légèrement différentes :

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...). 

Mais nous n'irons pas plus loin dans ces fouillis de fonctions individuelles, nous parlerons simplement de ce que sont les fonctions magiques F ().

2.4 Que sont F() ?

Ils peuvent proposer de nombreux mécanismes de mise en œuvre différents et très différents. Résumé de l'échantillon :

• F = rand() % nums_shards
• F = somehash(object.id) % num_shards
• F = objet.date % num_shards
• F = object.user_id % num_shards
• ...
• F = shard_table [ somehash() |… object.date |… ]

Un fait intéressant - vous pouvez naturellement disperser toutes les données au hasard - nous lançons le prochain enregistrement sur un serveur arbitraire, sur un noyau arbitraire, dans une table arbitraire. Il n'y aura pas beaucoup de bonheur là-dedans, mais ça marchera.

Il existe des méthodes légèrement plus intelligentes pour fragmenter par une fonction de hachage reproductible ou même cohérente, ou fragmenter par un attribut. Passons en revue chaque méthode.

F = rand()

La dispersion n'est pas une méthode très correcte. Un problème : nous avons dispersé nos 2 milliards d'enregistrements sur un millier de serveurs au hasard, et nous ne savons pas où se trouve l'enregistrement. Nous devons retirer user_1, mais nous ne savons pas où il se trouve. Nous allons sur un millier de serveurs et trions tout - d'une manière ou d'une autre, c'est inefficace.

F = un hachage()

Dispersons les utilisateurs de manière adulte : calculons la fonction de hachage reproductible à partir de user_id, prenons le reste de la division par le nombre de serveurs et contactons immédiatement le serveur souhaité.

Pourquoi fait-on ça? Et puis, que nous avons une charge élevée et que rien d'autre ne rentre dans un seul serveur. Si cela convenait, la vie serait si simple.

Génial, la situation s'est déjà améliorée, afin d'obtenir un enregistrement, nous nous rendons à l'avance sur un serveur connu. Mais si nous avons une plage de clés, alors dans toute cette plage, nous devons parcourir toutes les valeurs des clés et, à la limite, aller soit à autant de fragments que nous avons de clés dans la plage, soit même à chaque serveur. La situation s'est améliorée, bien sûr, mais pas pour toutes les demandes. Certaines requêtes ont été affectées.

Partitionnement naturel (F = object.date % num_shards)

Parfois, c'est-à-dire souvent, 95 % du trafic et 95 % de la charge sont des requêtes qui ont une sorte de partitionnement naturel. Par exemple, 95 % des requêtes conditionnellement d'analyse sociale n'affectent que les données des derniers 1 jour, 3 jours, 7 jours, et les 5 % restants se réfèrent aux dernières années. Mais 95% des requêtes sont ainsi naturellement shardées par date, l'intérêt des utilisateurs du système se portant sur les derniers jours.

Dans ce cas, vous pouvez diviser les données par date, par exemple, par un jour, et suivre la réponse à la demande d'un rapport pour un jour ou un objet de ce jour à ce fragment et c'est parti.

La vie s'améliore - nous connaissons maintenant non seulement l'emplacement d'un objet particulier, mais nous connaissons également sa portée. Si on nous demande non pas une plage de dates, mais une plage d'autres colonnes, alors, bien sûr, nous devrons parcourir tous les fragments. Mais selon les règles du jeu, nous n'avons que 5% de telles demandes.

Il semble que nous ayons trouvé une solution idéale à tout, mais il y a deux problèmes :

• Cette solution est adaptée à un cas précis, lorsque 95% des demandes ne concernent que la dernière semaine.
• Étant donné que 95 % des demandes touchent la semaine dernière, elles tomberont toutes sur un seul fragment qui sert cette dernière semaine. Ce fragment va fondre, tandis que tous les autres seront inactifs pendant ce temps. En même temps, vous ne pouvez pas les jeter, les données d'archives doivent également être stockées.

Cela ne veut pas dire qu'il s'agit d'un mauvais schéma de partitionnement - nous avons coupé les données chaudes, néanmoins, quelque chose doit être fait avec la partition la plus chaude.

Le problème est résolu par des bouffonneries, des sauts et des cataplasmes, c'est-à-dire une augmentation du nombre de répliques pour la journée en cours de gravure, puis une diminution progressive du nombre de répliques lorsque cette journée devient passée et entre dans les archives. Il n'y a pas de solution idéale appelée "il suffit de répartir les données sur le cluster avec une fonction de hachage magique dans le mauvais sens".

2.5 Prix à payer

Formellement, nous savons maintenant que nous savons "tout". Certes, nous ne connaissons pas un mal de tête géant et deux petits maux de tête.

1. Douleur simple : mal enduite

Ceci est un exemple tiré d'un manuel, qui ne se produit presque jamais au combat, mais soudainement.

• Par exemple avec une date, seulement sans date !
• Distribution inégale (perceptible) non intentionnelle .

Ils ont choisi le mécanisme de partitionnement, et/ou les données ont changé, et, bien sûr, le PM n'a pas transmis les exigences (nous n'avons pas d'erreurs dans le code, le PM ne signale toujours pas les exigences), et la distribution devenu monstrueusement inégal. Autrement dit, ils ont raté le critère.

Pour attraper, vous devez regarder la taille des fragments. Nous verrons certainement le problème au moment où l'un de nos fragments surchauffe ou devient 100 fois plus gros que les autres. Vous pouvez le réparer simplement en remplaçant la clé ou la fonction de partage.

C'est un problème simple, pour être honnête, je ne pense pas qu'au moins une personne sur cent rencontrera cela dans la vie, mais du coup cela aidera au moins quelqu'un.

2. Douleur « invincible » : agrégation, jointure

Comment faire des sélections qui joignent un milliard d'enregistrements d'une table à un milliard d'enregistrements d'une autre table ?

• Comment calculer "rapidement"... OÙ randcol ENTRE aaa ET bbb ?
• Comment faire "intelligemment"... users_32shards JOIN posts_1024 shards ?

Réponse courte : pas question, souffrez !

Si vous avez distribué un milliard d'enregistrements à un millier de serveurs dans la première table pour qu'ils fonctionnent plus rapidement, et que vous ayez fait de même dans la deuxième table, alors naturellement mille à mille serveurs devraient se parler par paires. Un million de connexions ne fonctionneront pas bien. Si nous faisons des requêtes à la base de données (recherche, stockage, magasin de documents ou système de fichiers distribué) qui ne correspondent pas bien au sharding, ces requêtes ralentiront énormément.

Un point important est que certaines requêtes seront toujours étalées sans succès et ralentiront . Il est important d'essayer de minimiser leur pourcentage. Par conséquent, il n'est pas nécessaire de faire des jointures gigantesques avec un milliard par un milliard d'enregistrements. S'il est possible de répliquer une petite table, par rapport à laquelle vous vous joignez à une table partagée géante, sur tous les nœuds, vous devez le faire. Si les jointures sont en fait locales d'une manière ou d'une autre, par exemple, il est possible de placer l'utilisateur et ses publications côte à côte, de les fragmenter de la même manière et de faire toutes les jointures au sein de la même machine - vous devez faire exactement cela .

Il s'agit d'un cours séparé de conférences pendant trois jours, passons donc à la dernière douleur infernale et aux différents algorithmes pour y faire face.

2.6. Douleur complexe/longue : refendissement

Préparez-vous : si vous avez partagé vos données pour la première fois de votre vie, vous les partagerez en moyenne cinq fois de plus.

Quel que soit le nombre de clusters que vous configurez, vous devez toujours repartitionner.

Si vous êtes très intelligent et chanceux, alors overshard au moins une fois. Mais une fois que vous êtes sûr, car au moment où vous pensez que 10 unités suffisent à l'utilisateur, quelqu'un à ce moment-là écrit une demande pour 30 et prévoit d'avoir une demande pour 100 unités de ressources inconnues. Les éclats ne suffisent jamais. Avec le premier schéma de partitionnement, dans tous les cas, vous manquerez - vous devrez toujours soit augmenter le nombre de serveurs à ajouter, soit faire autre chose - en général, reconditionner les données d'une manière ou d'une autre.

C'est bien si nous avons de belles puissances de deux : il y avait 16 fragments de serveur, maintenant c'est 32. C'est plus amusant si c'était 17, c'est 23 - deux nombres vasimalement premiers. Comment font les bases de données, peut-être qu'elles ont une sorte de magie à l'intérieur ?

La bonne réponse est : non, il n'y a pas de magie à l'intérieur, ils ont l'enfer à l'intérieur.

Ensuite, nous examinerons ce qui peut être fait «à la main», peut-être comprendrons-nous «comme une machine automatique».

Sur le front #1. Tout déplacer

Pour tous les objets, nous considérons NewF(object), shift to a new shard.

La probabilité de correspondance NewF()=OldF() est faible.

Couvrons presque tout.

Oh.

J'espère qu'il n'y a pas d'enfer pour transférer les 2 milliards d'enregistrements d'anciens fragments vers de nouveaux. L'approche naïve est compréhensible : il y avait 17 machines, 6 machines ont été ajoutées au cluster, 2 milliards d'enregistrements ont été triés, ils sont passés de 17 machines à 23 machines. Une fois tous les 10 ans, vous pouvez probablement même le faire. Mais dans l'ensemble, c'est un mauvais coup.

Sur le front #2. Déplacer la moitié

La prochaine amélioration naïve - abandonnons un schéma aussi stupide - interdira à 17 voitures de repartitionner en 23, et nous repartirons toujours 16 voitures en 32 voitures ! Ensuite, selon la théorie, nous devrons déplacer exactement la moitié des données, et en pratique, nous pouvons également le faire.

Pour tous les objets, nous considérons NewF(object), shift to a new shard.

C'était strictement 2^N, maintenant c'est strictement 2^(N+1) fragments.

La probabilité de faire correspondre NewF()=OldF() est de 0,5.

Transférons environ 50% des données.

Optimal, mais ne fonctionne que pour les puissances de deux.

En principe, tout va bien, sauf la liaison à la puissance deux en termes de nombre de voitures. Cette approche naïve, curieusement, peut fonctionner.

Veuillez noter que la division supplémentaire du cluster par puissances de deux dans ce cas est également optimale. Dans tous les cas, en ajoutant 16 machines à un cluster de 16, nous sommes obligés de décaler la moitié des données - exactement la moitié et décaler.

D'accord, mais l'humanité n'a-t-elle vraiment rien inventé d'autre - la question vient d'un esprit curieux.

Plus amusant #3. Hachage cohérent

Bien sûr, une image avec un cercle sur le hachage cohérent est requise ici.

Si vous recherchez "hachage cohérent" sur Google, un cercle apparaîtra certainement, tous les résultats sont peuplés de cercles.

Idée : dessinons les identifiants de partition (hachages) sur un cercle et marquons les identifiants de serveur hachés en haut. Lorsque vous devez ajouter un serveur, nous plaçons un nouveau point sur le cercle, et ce qui s'est avéré être proche de lui (et seulement ce qui s'est avéré être proche), nous le déplaçons.

Lors de l'ajout d'un shard : on regarde pas tout, mais seulement 2 "voisins", on décale en moyenne de 1/n.

Lors de la suppression d'un shard : on ne regarde que le shard en cours de suppression, on le décale uniquement. Genre d'optimal.

Très efficace en termes de minimisation du trafic lors de l'ajout d'un fragment, et absolument dégoûtant en termes d'équilibrage normal des données. Car lorsque nous hachons tous ces objets que nous distribuons à un grand nombre de machines, nous le faisons de manière relativement inégale : les points autour du cercle sont inégalement espacés, et la charge de chaque nœud particulier peut être très différente du reste.

Ce problème est résolu par la dernière ligne du nœud virtuel. Chaque nœud, chaque serveur sur le cercle est indiqué par plus d'un point. En ajoutant un serveur, un shard, etc., nous ajoutons quelques points. Chaque fois que nous supprimons quelque chose, nous supprimons en conséquence quelques points et décalons une petite partie des données.

Je parle de cet espace avec des cercles, car, par exemple, un tel schéma se trouve à l'intérieur de Cassandra. Autrement dit, lorsqu'elle a commencé à courir après les enregistrements entre les nœuds, sachez que le cercle vous regarde et n'approuve probablement pas.

Cependant, par rapport aux premières méthodes, la vie s'est améliorée - lors de l'ajout / de la suppression d'un fragment, nous ne parcourons déjà pas tous les enregistrements, mais seulement une partie, et ne décalons qu'une partie.

Attention, la question est : peut-on encore l'améliorer ? Et aussi améliorer l'uniformité du chargement des fragments ? Ils disent que c'est possible !

Plus amusant #4. Rendez-vous/HRW

La prochaine idée simple (le matériel est pédagogique, donc rien de compliqué) : shard_id = arg max hash(object_id, shard_id).

Pourquoi cela s'appelle le hachage Rendezvous, je ne sais pas, mais je sais pourquoi cela s'appelle le poids aléatoire le plus élevé. Il est très facile de le visualiser comme ceci :

Nous avons, par exemple, 16 fragments. Pour chaque objet (chaîne) qui doit être placé quelque part, nous calculons 16 hachages en fonction de l'objet à partir du numéro de fragment. Celui qui a la valeur de hachage la plus élevée gagne.

C'est ce qu'on appelle le hachage HRW, alias hachage Rendezvous. Muet comme un bâton, le schéma de calcul du nombre d'éclats, d'une part, est plus facile à regarder que les cercles et donne une charge uniforme, d'autre part.

Le seul point négatif est que l'ajout d'un nouveau fragment a empiré pour nous. Il y a un risque que lors de l'ajout d'un nouveau shard, nous ayons encore des hachages qui vont changer et il faudra peut-être tout revoir. La technologie d'élimination des éclats n'a pas beaucoup changé.

Un autre problème est qu'il est lourd en termes de calcul avec un grand nombre de fragments.

Plus amusant #5. Plus de techniques

Fait intéressant, la recherche ne s'arrête pas et Google publie chaque année de nouvelles technologies spatiales :

• Saut de hachage - Google '2014.
• Multi-sonde—Google '2015.
• Maglev-Google '2016.

Si le sujet vous intéresse, vous pouvez lire de nombreux mémoires. Je présente ces données afin de bien faire comprendre que le problème n'a pas été résolu, il n'y a pas de super-solution qui puisse être implémentée dans toutes les bases de données. Jusqu'à présent, les gens défendaient des thèses.

conclusion

Il existe une technique de base importante appelée sharding du nom de Gallius Julius Caesar : « Diviser pour régner, régner et diviser ! ». Si les données ne rentrent pas dans un seul serveur, il est nécessaire de les diviser en 20 serveurs.

Après avoir appris tout cela, on devrait avoir l'impression qu'il vaut mieux ne pas se séparer. Si vous décidez qu'il vaudrait mieux ne pas partager, c'est le bon sentiment. Si vous pouvez ajouter de la mémoire au serveur pour 100 $ et ne rien fragmenter, alors vous devriez le faire. Lors du partitionnement, un système distribué complexe apparaîtra avec le transfert de données dans les deux sens, empilant les données dans personne ne sait où. Si cela peut être évité, il faut l'éviter.

C'est mieux de ne pas le faire à la main, c'est mieux que la "base" (search, DFS, ...) puisse se sharder. Dans tous les cas, tôt ou tard, un highload arrivera et d'une manière ou d'une autre, les données devront être divisées. Ce n'est pas un fait que même si la base peut le faire elle-même, vous ne rencontrerez aucun problème. N'oubliez pas le fondamentalisme algorithmique - vous devez comprendre comment tout fonctionne à l'intérieur.

Lorsque vous configurez le sharding pour la première fois, choisissez soigneusement F(), pensez aux requêtes, au réseau, etc. Mais préparez-vous, vous devrez probablement choisir 2 fois et au moins une fois vous devrez tout refaire.