Bête comme chou

Préambule

Cet article reprend (et traduit) en grande partie la page concernant le data model sur lequel est basé Cassandra. J’y ai ajouté d’autres informations (toujours relative au data model) glanées deci-delà et ai tenté de les agréger de la façon la plus cohérente possible pour arriver à cerner ce système. Bien entendu, ce post expose également une réflexion personnelle, et ma perception de Cassandra. N’hésitez donc pas à commenter ou corriger.

Le modèle de donnée de Cassandra est plus ou moins dérivé de celui de BigTable de Google. Les développement de Cassandra ont commencés au sein de Facebook, puis ont été transmis à la communauté Open Source. Cette base de donnée non relationnelle est orientée vers le stockage de données de sites Web de grande ampleur (tels que les réseaux sociaux)

Introduction

Cassandra peut être pensé comme une structure a 4 ou 5 dimensions dont les noms sont les tables, les familles de colonnes, les clés, les super colonnes et les colonnes. Au croisement de ces dimensions on trouve le couple (valeur, timestamp).

Les SGBD classiques sont orientés lignes. Cela signifie que toutes les colonnes d’une ligne sont stockées à la suite les unes des autres, de manière regroupée. Une base de données orientée colonne, quant à elle, stocke les données en privilégiant le regroupement des données des colonnes entières. Une base de donnée orienté ligne stocke les données d’une manière favorisant principalement les lignes (c’est à dire que toutes les colonnes d’une même ligne sont stockées ensemble). Les stockage d’une base de données orientée colonne quant a lui favorisera les colonnes.

Les familles de colonnes permettent une approche hybride. Elles permettent de diviser les lignes (correspondant aux clés) en nombre statique de groupe (les familles de colonnes). Dans Cassandra, chaque famille de colonne dans une table est stockée dans un fichier séparé, et le fichier est trié par ligne (par clé). Cette clé est une chaîne de caractères de longueur quelconque identifiant uniquement chaque ligne.

Les colonnes ayant un lien entre elle et devant être accédées dans les mêmes occasions, doivent idéalement être incluses dans une même famille afin d’en optimiser l’accès.

Les structures de données

La table :

Il faut penser les tables comme des espaces de travail, des domaines. Il s’agit du plus haut niveau d’organisation de Cassandra. Généralement on leur donne le nom d’application. Quoique j’ai pu lire à droite et à gauche, il est possible de créer plusieurs table dans le cluster. Ces tables doivent être déclarées dans le fichier de configuration storage-conf.xml avant le démarrage du cluster.

La famille de colonne :

L’unité suivante d’organisation des données au sein de Cassandra est la Famille de colonne (Column Family). Une table est composée d’une ou plusieurs Familles de colonnes. Le nombre, le nom, le type (simple ou super) ainsi que les autres paramètres des Familles de colonnes sont fixés à l’avance, lors du démarrage du cluster. Il n’y pas de limitation quant au nombre de Familles de colonnes mais ce nombre doit rester relativement restreint.

Dans Cassandra les données dans une  table sont stockées dans un fichier séparé pour chaque colonne family. Au sein de cette famille, les données sont stockées en ligne (correspondant aux clés). Les colonnes ayant des liens entre elles, c’est-à-dire celle auxquelles on accède en même temps, doivent être regroupée au sein de column families. Par ailleurs il peut être intéressant de positionner les données fréquemment au sein d’une famille de colonne et les données les moins fréquemment accédée au sein d’une autre. Par exemple on peut nommer les colonne families : Posts, User ou UserAudit. On est assez proche dans ce cas de la notion de table, au sens SGBDR classique.

La clé

Il s’agit de l’identifiant unique de la ligne de donnée, de l’enregistrement. C’est son nom. On peut requêter sur des ranges de  clés.

Cassandra supporte une option de partitionnement avec un ajout de code minime. En standard, Cassandra fournit le hash-based RandomPartitioner et le  OrderPreservingPartitioner. Le premier permet une répartition de charge relativement efficace sans autre développement. Le second quant a lui permet d’exécuter des requêtes par range (range queries) sur les clés qui sont stockées. Les systèmes supportant uniquement des partitions hash-based ne permettent pas ce genre de requêtes de manière efficace.

Les colonnes :

Une famille de colonnes comportent des colonnes qui peuvent être de deux types : Simple ou Super. Dans ces deux cas, les colonnes au sein des familles peuvent être créées dynamiquement, et leur nombre n’est pas limité.

Les familles de colonnes simples : Les colonnes sont des structures qui sont identifiées par un nom, une valeur et un timestamp défini par l’utilisateur. Le nombre et le nom des colonnes peut être très important, et peut varier d’une clé (key)  à l’autre. Par exemple la clé k1 peut avoir 1024 colonnes/super-colonnes alors que la clé k2 n’en aura que 64.

Les colonnes peuvent être triées par leur nom, ou le timestamp..

Dans le cadre des colonnes simple il est possible d’utiliser des jokers (wildcards) “*” pour effectuer des recherches du type :

• Table:CF:(key name, *)

Cela ramènera l’ensemble des tuples  (nom de colonne, valeur, timestamp) correspondant

Les familles de colonnes de type super sont des structures qui ont un nom et un nombre infini de colonnes associées. Le nombre de super columns associées à une Famille de Colonne peut être très important. Elles ont les mêmes caractéristiques que les colonnes. L’ordre de tri peut encore être explicitement donné dans un fichier de configuration, pour chacune des familles de colonnes. Les super colonnes peuvent être vues comme des Familles de colonnes au sein d’une famille de colonnes.

Notation : CFx : Famille de colonne, Cx : colonne, [,] liste, ( x,y ) tuple .

De meme concernant les super colonnes, on peut faire des recherches générique des types suivant :

• Table:CF:(key name, super column name, *)
• Table:CF:(key name, *, *)

“:” est un mot réservé et ne peut donc pas composer le nom d’une famille de colonne ou celui s’une supercolonne ou d’une colonne. (La version 0.4 devrait lever cette restriction)

Les points forts

Plusieurs raisons peuvent amener a préférer Cassandra pour alimenter une application web.

Flexibilité du schéma : Cassandra, comme un Document Store, permet de ne pas figer les strucutres qui seront utilisées. On peut en ajouter ou en retirer au fur et à mesure. Par ailleurs les champs peuvent varier d’un enregistrement à l’autre. Attention il faut néanmoins, au moment du démarrage du cluster fixer les nom des tables et des Familles de colonnes qui seront utilisées.  C’est au niveau des colonnes que cette souplesse arrive.

Scalabilité réelle : Cassandra permet de scaler réellement facilement. On peut ajouter une machine à la volée sans avoir a redémarrer aucun process, ni changer les requêtes ou avoir a redispatcher les données.

Connaissance de l’infrastructure : Il est possible de configurer le cluster pour que les données soient réparties dans des racks différents ou des datacenters différents, ce qui permet de gérer de manière fine les problématiques de répartition de charge sur différents sites ou de PRA

Range queries: Certes par rapport aux bases de données relationnelles classiques, ce n’est absolument pas un avantage, tant cette fonctionnalité est standard. Cependant face aux distributed key value store il es réellement intéressant d’utiliser Cassandra, dont le modèle d’implémentation permet de faire des range queries.

Distributed writes: Les écritures n’échouent jamais, il n’y a jamais de single point of failure.

Limitations

La principale limitation concernant les tailles des colonnes et des super-colonnes est que toutes les données pour une valeur de clé, doivent tenir sur le disque d’une seule machine. Parce que la valeur des clés seules détermine les noeuds responsable de la réplication des données, la quantité de données associées à une clé a cette limitation. Cette limitation est inhérente au modèle de distribution.

A ce jour Cassandra a également une autre limitation : au pire des cas, les données pour une valeur de la pair (clé, famille de colonne) seront entièrement dé sérialisées en mémoire  lors d’une requête de lecture  (mais jamais pour une  écriture). Cet inconvénient sera levé dans une version future.

Example:

Dans ce paragraphe nous ne verrons que l’exemple proposé sur le wiki de Cassandra. Néanmoins, je reviendrai sur un exemple plus détaillé dans un autre post.

On peut penser au nom de chaque super colonne comme un mot clé, et les colonnes associées comme contentant des docids, avec des informations de classement (rankinfo) et d’autre attributs. Si les clés représentent les userids, on obtient un index par utilisateur.
C’est ainsi qu’est fait l’index par utilisateur dans la recherche au sein de la BAL (inbox) sur facebook. De plus, puisqu’on a la possibilité de stocker les données sur le disque par timestamp, il est très simple pour ce type de système de répondre à des requêtes du type “donne moi les 10 messages les plus récents”.

Conclusion

Références :

http://wiki.apache.org/cassandra/DataModel
http://code.google.com/p/the-cassandra-project/wiki/DataModel
http://wiki.apache.org/cassandra/ClientExamples
http://blog.evanweaver.com/articles/2009/07/06/up-and-running-with-cassandra/
Pour obtenir des explications sous forme graphique, merci de vous reporter aux slides PowerPoint de présentation présentés lors du SIGMOD 2008.

Ces articles peuvent vous interesser

• Cloud Camp : Paris le 11 Juin 2009 (1)