NoSQL Europe : Bases de données clé-valeur et Riak

Vision simplifiée à l’extrême, la base de données clé-valeur se comporte, du point de vue de son application cliente, comme une grosse table de hachage persistante. Ce type de base de données trouve sa légitimité dans le constat que les applications présentent de nombreux accès à la base de données qui ne sont que de simples lectures ou écritures à partir d’un identifiant.

Partant de la même idée, Amazon a créé sa base de données distribuée Dynamo dont les idées ont été reprises par de nombreux projets. Ce type de système distribué, robuste, et répliqué est toutefois bien loin du concept de table de hachage de base, c’est pourquoi Bryan Fink s’est attaché à présenter le cheminement logique qui a permis de passer de l’un à l’autre.

Bryan Fink a enfin introduit Riak – projet sur lequel il travaille chez Basho – en tant qu’implémentation de base de données clé-valeur.

Architecture d’une base de données clé-valeur

D’une table de hachage à une BDD clé-valeur distribuée

Observons le cheminement qui permet de passer d’une table de hachage persistante à une base de données clé-valeur moderne.

Table de hachage persistante : les informations sont ici stockées sur un nœud unique. Ce mode de stockage est donc efficace tant que le volume de données stockées et la charge de requêtes n’excèdent pas les capacités de la machine. En outre aucune tolérance aux pannes n’est ici admise puisque les données ne sont pas redondées.

Table partitionnée : pour palier à la problématique de montée en charge et en volume, une solution simple est de partitionner la table, divisant ainsi le volume et la charge entre toute les instances. Cette approche simple n’est pas idéale car elle peut entrainer une répartition inégale des données entre les instances. Ainsi sur la figure suivante où l’on considère le cas du partitionnement d’un ensemble de clés de type String, l’une des partitions pourrait avoir une taille bien plus importante que les autres :

Consistent hashing : une meilleure répartition des clés peut être assurée par l’utilisation d’un consistent hashing. Ce mécanisme se base sur un hash de la clé pour sélectionner l’instance qui se chargera du stockage. Si la fonction de hachage utilisée est uniforme, les données seront équitablement réparties.

Si cette solution permet de résoudre la problématique de montée en charge et en volume, aucune tolérance aux pannes n’est en revanche assurée ici.

Réplication : la réplication est la solution classique pour assurer la tolérance aux pannes d’un système. Il s’agit donc ici de répliquer chacune des instances de partition du modèle précédent.
Une réplication naïve de chaque instance entrainerait un besoin conséquent en machines puisque chaque nouvelle partition nécessiterait l’ajout de N machines (où N est le nombre de replicas). Pour cette raison, chaque machine se voit attribuer plusieurs partitions ce qui permet de mutualiser la capacité de réplication.

Relâchement de la consistance

Dans l’architecture précédente, si l’on souhaite offrir un comportement parfaitement consistant, tel que chaque lecture voit toujours la dernière version de la donnée écrite, il est nécessaire d’attendre une réponse de chaque replica lors des opérations put et get. Cette contrainte entraîne un comportement suboptimal. Pour cette raison, on définit un quorum pour les opérations de lecture et écriture, celui-ci indique le nombre de réponses à attendre dans chacun des cas. Ce quorum détermine alors le niveau de consistance souhaité.

Un tel système est alors paramétré par 3 variables fondamentales :

• N : le nombre de replicas pour chaque partition de données
• R : le quorum en lecture, soit le nombre de réponses à attendre lors d’une requête en lecture
• W : le quorum en écriture, c’est-à-dire le nombre de confirmations d’écriture à attendre lors d’une requête d’écriture

Une fois la consistance relâchée, des conflits de versions peuvent apparaître à la suite de deux écritures qui sont intervenues sans synchronisation mutuelle. Ce type de problématique est bien connu des développeurs avec les outils de versionning de code source tels que Subversion. Ceci est ici résolu par des vector clocks qui tracent l’historique des versions et délèguent à l’application cliente la tâche de résoudre le conflit d’une manière adaptée au métier (fusion des deux versions, conservation uniquement de la plus récente, …).

Le modèle Dynamo d’Amazon est basé sur ce principe de table de hachage distribuée, répliquée et partiellement consistante. Il l’étend en y ajoutant, entre autres, la redistribution automatique des clés lors de l’ajout ou de la suppression d’une instance et la gestion des défaillances. Dynamo constitue, avec BigTable, un modèle de référence dont beaucoup de bases de données NoSQL s’inspirent. Nous reviendrons donc sur ces modèles dans un article ultérieur.

Riak

Riak en quelques mots

Riak est une base de données clé-valeur qui s’inspire du modèle Dynamo tel que décrit précédemment. En ce sens il est distribué et offre un niveau de consistance paramétrable. Le projet est écrit en Erlang et est très actif car soutenu par une entreprise dédiée : Basho.

Riak organise des ensembles logiques de clés / valeurs sous forme de buckets. Il offre une interface REST et de nombreuses librairies clientes sont disponibles pour y faciliter l’accès depuis les langages les plus courants.

En outre, il est possible d’écrire des batch de type MapReduce en Javascript ou en Erlang. Enfin une fonctionnalité propre à Riak est la possibilité d’établir des liens entre les données (Links) qui permettent par la suite au client de parcourir ce graphe de liens.

Premiers pas avec Riak

Le téléchargement, l’installation et le démarrage d’une instance Riak sont triviaux. Pour le développeur Java, les premiers pas avec Riak se feront par l’intermédiaire de la librairie cliente dédiée. Celle-ci peut être intégrée par Maven via le repository central :

    com.basho.riak
    riak-client
    0.9.1

Le code Java permettant d’interagir avec Riak est alors trivial :

// Connexion à l'instance Riak
RiakClient riak = new RiakClient("http://localhost:8098/riak");

// Ecriture
RiakObject o = new RiakObject("bucket", "key", "value");
riak.store(o);

// Lecture
FetchResponse r = riak.fetch("bucket", "key");
if (r.hasObject()) {
   o = r.getObject();
   System.out.println(
      "bucket: " + o.getBucket() 
      + ", key: " + o.getKey() 
      + ", value: " + o.getValue());
}

Le coefficient de réplication N et les paramètres de consistance R et W peuvent être manipulés ainsi :

// Définition d'un coefficient de réplication de 3 pour le bucket
RiakBucketInfo bucketInfo = new RiakBucketInfo();
bucketInfo.setNVal(3);
riak.setBucketSchema("bucket", bucketInfo);

// Ecriture avec W=2
riak.store(o, RequestMeta.writeParams(2));

// Lecture avec R=1
client.fetch("bucket", "key", RequestMeta.readParams(1));

Conclusion

L’intérêt d’une base de données clé-valeur comme Riak ne se situe donc pas simplement dans sa capacité de stockage avec accès direct par clé. Il s’agit aussi d’une puissante solution de stockage permettant de répartir les données et la charge entre plusieurs instances tout en assurant une réplication pour augmenter la disponibilité.

Intuitivement, le relâchement de la contrainte de persistance est synonyme de stockage peu fiable. Pour certains types de données il n’en est rien. En effet s’il est possible de définir une règle de gestion des conflits qui soit satisfaisante d’un point de vue métier, il en résultera un stockage hautement disponible et robuste. Le fait que Dynamo soit utilisé chaque jour en production chez Amazon pour la persistance du panier d’achat permet de s’en convaincre.