Le partitionnement

Le point de contention des applications est bien souvent la base de données qui lorsqu'elles sont transactionnelles, distribuées, ne permettent pas facilement le passage à l'échelle. Que l'on fasse du lock optimiste, pessimiste ou transaction à deux phases, on couple toujours les données entre elles, ce qui empêche la sérialisation. En plus, pour la sécurité de fonctionnement, il faut que les données soient répliquées, se qui complique encore un peu plus les choses. Dans les architectures modernes, la validation du modèle se fait désormais dans les objets, au niveau de l'applicatif. Cela permet de soulager la base et de ne se concentrer que sur les requêtes. des mouvements comme le DDD ont remis au gout du jour les objets avec du code métier plutôt que des POJOs.

Lorsque l'on veux scaler une base de données,une première solution peut être le partitionnement :

  • Vertical : une base pour les livres, une base pour les CDs, etc
  • Horizontal : une base pour les livre de A-M et une pour les livres de N-Z, ...

C'est donc une segmentation intelligente qui permet une montée en charge. mais cette architecture montre tout de même des limites, c'est là que le NoSQL entre en jeu

Le théorème de CAP

La quasi totalité des sites à fort trafic n'utilisent pas de base de données relationnelles avec des propriétés ACID mais plutôt des bases de données dites NoSQL basées sur le théorème de CAP d’Eric Brewer, qui est plus adaptés aux données massivement partagés.

En voici les 3 principes :

  • Consistance (consistency /C) : Tous les clients voient la même vue même lorsqu’il y a des mises-à-jour, en fait il s'agit du 'Atomic' des propriétés ACID.
  • Haute disponibilité (availability /A) : L’ensemble des clients peuvent trouver des données répliquées, même lorsqu’une avarie survient
  • Tolérant à la partition (partition-tolerance /P) : Le système est tolérant au partitionnement.

En revanche, seul deux des trois principes peuvent être respectés en même temps, souvent ce sont les deux derniers principes qui sont choisis (c'est le cas d 'Amazon par exemple) car le besoin en disponibilité et en partitionnement est souvent plus important que la consistance.

Les utilisateurs n'ont pas forcément tous la même vue à un moment donné, mais est-ce vraiment une nécessité ? Dans certains cas oui mais souvent non. Si vous faites une recherche sur Google et que vous n'avez pas exactement la même réponse qu'un autre utilisateur cela parait moins important que de ne pas avoir de résultats de recherche du tout (pas de haute disponibilité) !

Souvent, si la consistance est importante pour certaines données, il est d'usage de les isoler dans des bases relationnelles et de placer les autres données dans des bases dite NoSQL.

Certaines données nous paraissent logiques d'être consistantes mais cela est souvent du à notre inertie d'esprit. Prenons le cas d'une valeur indiquant le stock d'un article. Si deux serveurs ont des valeurs non consistantes, il peut arriver qu'un serveur considère qu'il en reste un alors qu'un autre qui a était mis à jour, sait qu'il n'en reste plus. Lorsque vous faites un achat et si par malchance vous acheter un livre qui n'est plus en stock, le site marchand à deux possibilités : vous rembourser ou réapprovisionner le stock (je ne sais pas vous, mais cela m'est déjà arrivé de recevoir un mail en disant que le produit était épuisé,après l'avoir commandé)

Dans cet exemple, vous pouvez avoir des désagrément mais je pense qu'entre

  • acheter sur un site très lent (disons quelques dizaine de secondes de latence par page) mais où le stock est en tant réel entre les milliers de serveurs pour tous les produits du site
  • une éventualité de stock non cohérente mais une haute disponibilité,

les sites ont fait leur choix ! Amazon a d'ailleurs constaté qu'un dixième de seconde de latence leur fait diminuer les ventes de 1%, et Google a remarqué qu'une demi seconde de latence fait chuter le trafic d'un cinquième.

Le fait d'accepter des données inconsistantes est connu sous le nom de BASE (Basically Available, Soft-state, Eventually consistent) qui est en fait, l'opposé des propriétés ACID. Le fait d'accepter que deux des trois principes du théorème de CAP peuvent être satisfait en même temps a fait le succès des plus gros sites de la planète, alors si cela a marché pour eux, je ne vois pas pourquoi cela ne marcherai pas pour d'autres.

Les 4 types de bases NoSQL

il existe 4 catégories de base NoSQL.

  • Orientées colonnes, comme HBase, Hypertable ou Cassandra, elles sont basées sur le concept de BigTable de Google
  • Basées sur la théorie des graphes (Euler) implémenter par Neo4J.
  • Orientées clé-valeur (Voldemort, Dynomite, Riak).
  • Orientées document, comme CouchDB.

Voyons maintenant leurs spécificités plus en détail :

Bases de données orientés colonnes :

Alors que les colonnes sont statiques pour une base relationnelle, elles sont dynamiques pour une base de données orientée colonnes, il est alors possible d'ajouter des colonnes dynamiquement et il n'y a pas de coût de stockage pour les valeurs Null.

Pour des raisons de performances les colonnes sont triées sur le disques, minimisant les accès aléatoires. De plus pour Cassandra, les écritures sont séquentielles pour éviter les latences de disques durs, les données sont tout d'abord écrites en mémoire, puis, persistées sur le disque lors d'un commitlog ou lorsque la mémoire est pleine.

Les BDD orientées colonnes sont prévues pour stocker des millions de colonnes, ce qui en fait des bases adaptées au stockage one-to-many. L'inconvénient est bien sur la mise à jour. Alors que pour une base de donnée relationnelle, une mise à jour du tuples disposant d'une clé étrangère peux suffire, une BDD orientée colonnes peut nécessiter une mise à jour de toutes les valeurs d'une colonne pour tous les enregistrements.

Il existe également des super colonnes qui sont des conteneurs de colonnes.

Les requête sont assez minimalistes, par exemple :

  • Toutes les colonnes ayant comme clé 256
  • Les colonnes dont le nom est compris entre 'bbb' et 'bbc' et dont la clé est 8652
  • La colonne 'abc' pour les lignes allant de 500 à 1000.

Cassandra (initialement utilisé par Facebook pour les messages non instantanés) et HBase sont des solutions de BDD orientées colonnes. Cassandra permettait à Facebook d'accéder aux messages échangés entre utilisateurs et aux messages comportant certains mots.

Ces bases sont destinées à des usages où l'on doit stocker des données par utilisateur et des données uniques. Ne chercher pas à faire du relationnel avec cette base, la mailing liste est pleine de ce genre de questions mais ce n'est tout simplement pas fait pour !

Bases de données orientées graphes.

Les bases de données orientés graphes n'ont pas pour but premier de résoudre des problèmes de performances mais plutôt de palier à des problèmes impossibles à résoudre avec des BDD relationnelles.

Le cas d'utilisation typique est bien sur les réseaux sociaux où l'aspect graphe prend tout son sens, mais aussi où des relations complexes entre les acteurs ont besoin d'être décrits (pièces d'une machine, arbre généalogique). Les bases de données orientés graphes ne représenteront probablement pas la majeure partie des BDD NoSQL.

Neo4J semble être actuellement la solution la plus mature.


Base de données clé-valeur

Dynamo, développé par Amazon, semble la plus connue des BDD clé-valeur. En simplifiant à l'extrême, les bases de données clé-valeur sont de grosses tables de hashage, leur légitimité se trouve dans le fait que les entités sont, dans une grande partie des cas, rapatriées à partir d'un identifiant. Toutefois le fonctionnement de ces bases est loin d'être aussi simple : les tables sont partitionnées. La partition est choisie en fonction d'un hash de la clé, qui donnera l'instance qui se chargera du stockage. Tout réside donc dans l'algorithme de la fonction de hashage qui doit garantir une répartition la plus égale possible entre les partitions.

Les données, à la différence d'une table de hashage, sont redondées. Afin de ne pas être sur un modèle 1 partition = 1 partition répliquée = 1 machine, chaque machines se voit attribuer une ou plusieurs partitions offrant ainsi de meilleurs performances et une tolérance aux pannes accrue.

Une des particularité de ces bases est que l'on peux choisir le niveau de consistance. ce niveau est défini par un quorum correspondant aux nombres de réponses de la part des partitions pour lequel on considère les données consistante. Si l'on veux que les données soit 100 % consistantes (toutes lectures sur n'importe quelles partitions donneront le même résultat), on définit alors le quorum au maximum. Le quorum peux être différent en lecture et en écriture, par contre des conflits de versions peuvent apparaitre, c'est alors à l'application cliente de résoudre les conflits (quelle version garder? un peu comme quand vous résolvez les conflits avec SVN).


Bases de données orientées documents

Elles sont une évolution des bases de données clé-valeur, où à une clé, est associé un document dont la structure est libre. il faut cependant que la base soit consciente de ce qu'elle stocke afin de permettre des fonctionnalités sur les documents. Je trouve que ces bases ressemblent beaucoup, au niveau stockage, à des utilisations comme SOLR / Lucene, ou a Xylème de l'INRIA (j'ai fais mon mémoire d'ingénieur sur ce projet).

De part son modèle, ces BDD se pré destine au stockage d'informations one-to-one et one-to-many et au stockage d'informations de session, de données de fichiers, pages web, etc

Un mot sur la sérialisation des données

Lorsque les données sont dispersées, et que l'on doit faire des traitement dessus, il faux souvent les véhiculer. Les grands comptes optent souvent pour des solutions évitant les sérialisation à outrance, les données ne sont pas véhiculées sur le réseau, seul l'endroit où elle se trouvent l'est. La donnée doit être accédée le plus tardivement possible ce qui permet d'économiser du réseaux, de la mémoire et du CPU. De plus les traitements doivent être insensibles à l'ordre d'arrivée des messages : la synchronisation tue les systèmes distribués !

conclusion

Pour le moment, le NoSQL est un mouvement grandissant, bien qu'il soit utilisé par les grand comptes qui sont à l'origine du mouvement. il n'y a pas de solutions qui se démarque vraiment du lot, il n'y a que des solutions adaptés aux besoins. On remarquera aussi qu'il manque vraiment des standards, comme JDBC et SQL le sont pour les SGBDR, mais cela s'explique sans doute par la jeunesse du mouvement et l'hétérogénéité des type de bases.