Decrypt » Sharding et optimisation des accès aux données

Sharding et optimisation des accès aux données

Le sharding ou partitionnement de données entre dans le cadre plus global de la scalabilité. Il s’agit tout simplement du découpage des données d’une base afin d’avoir à requêter sur moins d’occurrences et donc d’avoir un résultat plus rapide donc de meilleures performances. Le sharding est une solution à part entière, mais qui ne convient pas dans tous les cas. Nous verrons également quelles sont les solutions alternatives pour une amélioration des temps de réponse au niveau d’une base de données.

Pourquoi est-il si méchant ?
Oui ? Pourquoi vouloir à tout prix découper cette pauvre donnée dans tous les sens ? Quel est le déclencheur de cet acte barbare ?

Cela se produit simplement quand les temps de réponse des opérations sur une table fortement peuplée deviennent trop importants. Nous prendrons comme exemple une table « utilisateurs » comportant plusieurs millions de lignes. Depuis de nombreux SELECT en concurrence, qui unitairement ne présentent pas de performances dégradées malgré le nombre d’enregistrements, mais qui, sur de nombreuses requêtes, accumulent les latences, jusqu’aux INSERT demandant de reconstruire des INDEX monstrueux, où quelques insertions en trop sature la base, il y a de nombreuses raisons évidentes de vouloir découper son pool de données afin de pouvoir les manipuler plus légèrement.

Pour résumer, le besoin peut provenir de la masse de données elle-même ou bien du nombre/type de requêtes sur cette masse.

Il existe à ce niveau 2 techniques de sharding : le découpage en tranches et en lamelles…

Découpage en tranches… ou horizontal
Le sharding horizontal consiste à répartir les données (lignes) d’une table cible entre plusieurs selon un critère basé sur une information liée à la donnée, par exemple un modulo sur l’identifiant qui permet de répartir les données sur X tables. Le tout est de savoir, au niveau de l’application cliente, sur quelle table aller chercher l’information. La clé et le plan de répartition sont , en effet, des éléments déterminants. La clé étant l’élément (ou les éléments) de la donnée à répartir sur lequel (ou lesquels) va porter le plan.

Plusieurs plans de répartition sont possibles sur une clé donnée :

• Le modulo comme cité précédemment, ou autre fonction mathématique adaptée, est une option possible. Cependant, un changement du nombre de shard implique une redistribution complète. C’est cependant pratique si on doit définir la répartition sur un identifiant que l’on ne maitrise pas (récupéré d’un autre système ou fournisseur par exemple).

• Dans la même idée, on peut répartir selon un algorithme de hash à définir soigneusement sur des valeurs non modifiables pour un objet donné à répartir et de telle manière que le calcul du hash soit rapide, le nombre de collisions entre 2 résultats minimum et la dispersion bonne. De même que précédemment, un changement du nombre de shard peut impliquer une redistribution complète. Cependant, des algorithmes appelés « consistants » existent. En utilisant des algorithmes de hash consistants, seulement K/n clés doivent être redistribuées en moyenne, où K est le nombre total de clés et n le nombre de shards.

• Un « range », c’est-à-dire un intervalle, est aussi une solution. Pratique pour étendre le nombre de shard, il faut cependant maitriser l’identifiant retenu, un incrément par exemple, afin d’avoir une diffusion correcte.

D’autres méthodes peuvent êtres envisagées. Celles que j’ai citées sont les plus communes et les plus utilisées car elles répondent en général au besoin. La diffusion de la méthode retenue sur le critère choisi est dans tout les cas à vérifier pour une répartition efficace des données, c’est-à-dire qu’une répartition efficace aboutit à l’obtention de shards de tailles équivalentes. Le critère choisi pour répartir est généralement un identifiant, en effet, toute modification de la valeur déterminant la répartition, dans le cas d’un range ou bien intégrée dans le calcul d’un hash ou d’une fonction mathématique, ferait que l’objet ne serait plus accessible car pas enregistré dans le shard lui correspondant ou alors il faudrait le redispatcher…

Cette répartition peut se faire sur X tables dans une même base ou serveur ou bien sur 1 table dans Y bases ou serveurs (ou les 2 ;ob). Tout dépend du point d’engorgement. Est-ce purement le temps de réponse dû au volume de la table ? Ou bien atteint-on la limite physique du serveur qui peine à répondre à toutes ces requêtes ?

On en vient à la limitation de ce modèle pour lequel les requêtes ensemblistes posent problème. Je m’explique : on répartit les utilisateurs dans 2 tables en fonction du sexe : homme / femme. Je souhaite récupérer via une requête unitaire le Monsieur dont l’identifiant est X. Pas de problème je « SELECT * FROM UTILISATEUR_HOMME WHERE id=X ». Maintenant je souhaite récupérer toutes les personnes possédant un numéro de portable… Il va falloir faire la requête sur les 2 tables et corréler les résultats au niveau applicatif… dans des requêtes plus compliquées, notamment incluant des jointures, ce n’est pas forcément bénéfique. La parallélisation des requêtes, sur un sharding, au niveau applicatif est possible (quand le modèle de données le permet bien sûr), mais doit rester, à mon avis, mineur afin de ne pas perdre le bénéfice du sharding sur le temps de réponse pour une base donnée, en multipliant le nombre d’accès/connexions sur X sources et en traitant les résultats obtenus au niveau applicatif.

La répartition peut également engendrer des problèmes d’intégrité au niveau des données : la gestion des commit et des rollback est effective sur une connexion/transaction sur une base donnée. Comment gérer une transaction fonctionnelle qui s’étendrait sur plusieurs shard ? Commiter/rollbacker unitairement et prendre le risque d’une problématique d’intégrité ? Commiter/rollbacker chacune des connexions à la fin de la transaction fonctionnelle et conserver les connexions sur les X shards durant la transaction fonctionnelle et donc diminuer les capacités de connexions des X bases ?

Le problème de l’intégrité se pose également au niveau des backup/sauvegardes journalières, qui devront par conséquent s’effectuer lors d’une période de mise en maintenance (pas forcément longue) du site, nocturne par exemple. Il en va de même pour la restauration qui devra être effectuée, en cas de problème sur l’un des shards, sur l’ensemble des shards pour des problèmes d’intégrité.

On arrive enfin à la notion de « Single Point of Failure » dont le nombre augmentera avec le nombre de shards que vous mettrez en place sur des serveurs/machines différentes… A moins que vous ne fassiez de la réplication sur chacun des shards… Mais souvenez-vous qu’une solution efficace est bien souvent simple (ou tout du moins minimaliste) ! Alors…

Il n’y a pas de contre indication au sharding, il doit simplement être mesuré et prendre en compte les aspects précités afin d’être sûr que votre cas fonctionnel, et plus généralement votre besoin métier, accepte bien ce principe ou tout du moins en retire suffisamment de bénéfices pour valoir le jeu et être mis en place.

Découpage en lamelles… ou vertical
Le sharding vertical se base sur une notion de temporalité. Plus simple à comprendre et à mettre en place, il dépend surtout de la typologie de votre site : un site marchand où 90% des visites du jour sont effectuées par des utilisateurs dont la connexion précédente à moins de 7 jours ou bien une administration dont 80% des dossiers consultés du jour l’ont déjà été dans les 2 dernières semaines. Ce n’est pas nécessaire de s’embêter à sharder si il n’y a pas de problématique de volumétrie, cependant, si le nombre d’informations trop important dans la table provoque des lenteurs sur la récupération/mise à jour/ajout d’informations et que la majeure partie des informations n’est que rarement utilisée… Bingo ! Il est intéressant de pouvoir donner à 90% (dans le premier cas) de vos visiteurs une expérience nettement meilleure tandis que les 10% restants auront une expérience quasi similaire, voire un peu dégradée dans le pire des cas.

L’étape la plus sensible sera de déterminer et d’ajuster au mieux la « coupure » de façon à satisfaire le plus grand nombre avec des performances optimales. C’est le moment d’analyser vos données et vos statistiques de fréquentation ! ;ob

Le mécanisme est très simple : quelque soit l’utilisateur, vous cherchez l’information dans la première table réduite contenant les données les plus accédées en un temps record, si elle y est tant mieux, sinon on requête dans la seconde table, celle des « archives ». il ne reste plus qu’à lancer un batch la nuit qui redispatche les éléments qui ont expiré de la table « courante » vers la table « archive » et de ramener les éléments archivés consultés ce jour vers la table courante.

Cette technique n’est absolument pas faite pour parer au problème du nombre d’accès/connexions à la base comme peut l’être le sharding horizontal, puisque le but est justement de satisfaire le plus rapidement possible la majeure partie des connexions à la dite base. Le but est purement de limiter la volumétrie d’une source de données pour en accélérer les traitements/requêtes dessus.

De plus, dans le cas de requêtes ensemblistes portant sur les 2 « zones », le problème est similaire à celui du découpage horizontal.

Un petit cube, 2 petits cubes, …
Et les 2 en même temps ? Oui c’est possible ! Mais il faut satisfaire aux pré-requis des 2 cas et en accepter les bénéfices et inconvénients.

Alternatives
Les alternatives proviennent du fait que le sharding répond à un besoin : celui d’améliorer les temps de réponse sur les accès aux sources de données. Mais d’autres solutions existent…

L’essentiel tuning de base
Avant de se lancer dans du sharding et autres solutions plus complexes… Avez-vous paramétré convenablement votre base en fonction de l’utilisation que vous en faites ? Vous seriez surpris des différences que l’on peut obtenir… C’est LA première étape avant d’aller plus loin et d’envisager le sharding ou une autre solution. Une base convenablement tunée vous suffira peut-être.

Ensuite intéressez-vous au type de stockage. Il influe sur les performances en fonction des opérations effectuées. J’ai étudié le problème sur MySQL et constaté les différences flagrantes, en pratique, entre InnoDB et MyISAM. Pour les tables essentiellement accédées en lecture, MyISAM est fait pour. En revanche, pour celles accédées en écriture, InnoDB, avec son système de row locking, vous donnera bien meilleure satisfaction.

C’est LE conseil que je peux vous donner à cette étape : maitrisez d’abord votre outil de base (sans jeu de mots) avant de vouloir ajouter une couche de complexité, parfois nécessaire… Mais pas tout le temps.

Le classique Master-Slave
Le classique Master-Slave, encore appelé réplication, vous permettra d’optimiser des problèmes de temps de réponse dus au nombre de connexions/requêtes sur une table à forte volumétrie, où l’écriture peut prendre du temps du fait de la reconstruction d’index sur les INSERT par exemple et ce faisant influant sur les temps de réponse des lectures (SELECT) et vice-versa , en séparant la lecture de l’écriture : typiquement l’écriture s’effectuera sur le master et la lecture sur le slave (ou les slaves).

L’éventuel partitionnement MySQL
Depuis la version 5.1, MySQL propose un partitionnement (ou sharding) géré nativement. Ne l’ayant pas testé par moi-même, je ne pourrais vous donner de retour sur le sujet. Le partitionnement proposé par l’outil est horizontal. Il est à noter que la notion de partitionnement vertical est différente de celle que je vous est présentée dans la sémantique MySQL : il s’agit de pouvoir stocker sur différentes partitions les colonnes d’une même table, par exemple les colonnes de type standard d’une table donnée sur une partition et la colonne de type BLOB sur une autre. Dans tous les cas, le partitionnement vertical n’est pas assuré dans la version 5.1 de MySQL. Même si cela peut paraître attrayant, je pense qu’il est moins limitant de sharder soi-même et qu’il est rassurant de conserver la main sur la répartition des données que l’on souhaite et de pouvoir intervenir en toute connaissance de cause, sans se soucier, par exemple, de la version de la base et donc de la version de la fonctionnalité de partitionnement associée qui sous-tend la répartition des données, lors d’une montée de version… Je ne pense pas non plus qu’il soit possible d’effectuer un partitionnement « multi serveurs » afin de répartir le nombre de connexions entre diverses machines… Mais bon j’ai pas testé alors…

Le « hors sujet » MySQL Proxy
Compatible avec les versions 5.0.x de MySQL, cet outil est en version alpha et donc ne convient pas à un environnement de production. Mais le « hors sujet » ne provient pas de là mais du fait que cet outil traite de load balancing sur plusieurs backend (probablement des réplicats d’un master servant à une optimisation en lecture sur X slaves), de failover, et d’« injection SQL » permettant au niveau du proxy d’ajouter des clauses d’analyse aux requêtes ou bien de filtrer les résultats, … C’est l’équivalent d’un proxy web qui répartit la charge, gère le statut des backends et modifie les requêtes. Alors pourquoi est-ce que je parle de ça ? Hors sujet : 0/20 ! C’est uniquement parce que j’en ai entendu parler plusieurs fois de la part de clients et qu’il y avait une confusion sur son utilité. Le Proxy MySQL NE permet PAS de faire de la répartition de données.

L’indispensable cache mémoire
Je prendrai l’exemple de Memcached qui est un cache de données réseau pour objets génériques. Memcached est le cache que j’utilise et qui a fait ses preuves. Maintenant, libre à vous d’utiliser d’autres outils ou bien même de réaliser vous-même votre système de cache mémoire adapté à votre utilisation, pour peu que vous en ayez l’envie et le temps. Dans tout les cas, votre cache mémoire vous permettra de limiter le nombre d’accès au système de stockage plus lent qu’est la base de données, en conservant un certain nombre de résultats dans une « hashtable géante ». En diminuant le nombre de requêtes sur vos tables volumineuses, cela suffira peut-être à obtenir des temps de réponse convenables et à ne pas saturer votre serveur en connexions, vous permettant ainsi de ne pas avoir à sharder.

Le surprenant modèle non relationnel hébergé et SimpleDB
Et oui ! Remis au goût du jour par Google avec BigTable et Amazon avec SimpleDB, le modèle non relationnel prouve toute son efficacité et sa scalabilité. Si vous n’avez effectivement pas besoin des jointures et autres relations, c’est peut-être votre solution. Et pourquoi pas utiliser l’API Amazon pour SimpleDB et profiter de l’infrastructure et des services Amazon ?

Les prometteuses innovations distribuées et Cassandra
A rapprocher de SimpleDB car développé sur un modèle similaire à Dynamo, la technologie qui sous-tend simpleDB. Cassandra est un système de stockage de données, structuré mais non relationnel, basé sur un réseau P2P (« peer to peer » ou « pair à pair » en Français ;ob). Il s’agit d’un système distribué sous forme de nodes, fortement scalable, et dont la particularité est qu’il est actuellement accessible au format Open Source. Développé par Facebook et actuellement en production chez eux, Cassandra est en version Beta et accessible dans le projet « Apache incubator » (Cf. liste de liens de la rubrique « Outils » de Decrypt : « Cassandra »). Vous pouvez également consulter cette note http://www.facebook.com/note.php?note_id=24413138919 pour de plus amples informations. Il est surtout intéressant que l’explosion des applications et réseaux sociaux ait un impact sur la mise à disposition d’outils de stockage et de gestion de données fortement scalables. Cette tendance (augmentation de la volumétrie des données) va s’étendre à d’autres domaines du fait de la croissance des sources de données informatisées et de l’évolution des services. Les architectures distribuées se propagent jusqu’à la source… de données, dernier goulet d’étranglement des architectures scalables. Je pense cependant que le sujet de la scalabilité du système de stockage de données restera encore le point le plus ardu à mettre en place, pour un bout de temps, dans toute architecture.

Conclusion
On constate que le sharding répond à un besoin bien particulier. Il concerne dans tous les cas une ou des tables contenant un volume important de données. Les lenteurs au niveau des temps de réponse peuvent être induites par le volume de données lui-même ou bien/et par le nombre d’utilisateurs s’y connectant de ce fait (dans le cas d’un site grand public). Le sharding est une des solutions possible pour l’amélioration des temps de réponse sur ladite source d’éléments. Mais avant d’envisager cette solution, il est intéressant d’envisager d’autres possibilités dans cet ordre :

• le concept du modèle non relationnel, hébergé ou non, en général, puisque de ce choix découlera un autre modèle de fonctionnement,

• le tuning de la base de données pour optimiser le socle de votre problématique,

• le cache mémoire, simple de mise en place et terriblement efficace pour limiter les connexions inutiles sur votre source de données et livrer les informations en un temps record,

• la réplication master-slave, classique mais efficace, dans la même optique de limitation du nombre de requêtes sur une base donnée,

• les fonctionnalités de partitionnement livrées en natif avec le produit, potentiellement utiles, potentiellement limitées…

• finalement le sharding (ou partitionnement) fait main ou plutôt les sharding, vertical et horizontal, pour limiter la volumétrie de la ou des tables, et par là même limiter le nombre de requêtes sur ladite ou lesdites tables dans le cas du sharding horizontal.

Il est tout à fait possible de composer en utilisant le cache mémoire avec la réplication, ou bien le cache mémoire avec un ou les 2 sharding… Le tout est de cibler son problème, le point d’engorgement et donc son besoin, pour utiliser la ou les techniques adéquates. Si une seule suffit, tant mieux.

Le sharding de données fait donc partie intégrante d’un problème plus global et est une solution tout à fait viable, demandant tout de même « un peu » de réflexion et de temps de mise en place et impactant dans la conception et la maintenance de l’infrastructure. Il est donc à utiliser à bon escient, mais se révèle fort utile et très efficace.

Frédéric FAURE