Voici le premier article d'une longue série sur la modélisation de données dans Apache Cassandra avec CQL3.

Qu'est ce que Cassandra ?

Avant d'entrer dans le vif du sujet, une petite présentation de la base de données Apache Cassandra s'impose pour ceux qui ne la connaissent pas.

Historique

Apache Cassandra est une base de données de la famille NoSQL très en vogue. Elle se classe parmi les bases orientées colonnes tout comme HBase, Apache Accumulo, Big Table. Cette base a été développée à l'origine par des ingénieurs de Facebook pour leurs besoins en interne avant d'être mise à la disposition du grand public en open-source.

Pour la petite histoire, dans le code source de Cassandra, on retrouve encore des classes préfixées avec FB (comme Facebook) qui rappelle cette origine.

Origine du nom

Une petite anecdote veut que le nom de Cassandra ait été choisi par rapport à Oracle. D'après la mythologie grecque, Cassandra est un oracle maudit qui prédisait du malheur mais dont personne ne voulait croire les prédictions, jusqu'au jour où ... C'était un clin d'oeil très explicite à la base de données Oracle, faite à l'époque par les ingénieurs de Facebook.

Cluster

Quand on parle de Cassandra, on parle souvent de cluster. Un cluster est un regroupement de plusieurs noeuds (serveur physique) qui communiquent entre eux pour la gestion de données.

Ci-dessus un exemple d'un cluster Cassandra à 5 noeuds. Les noeuds communiquent entre eux par un protocole peer-to-peer qu'on appelle le Gossip (bavardage).

Théorème CAP

Dans le monde des bases de données NoSQL, on entend souvent parler du Théorème CAP. Ce théorème établit 3 paramètres sur lesquels on peut jouer pour configurer une base de données distribuée :

1. La cohérence ( C pour Consistency)
2. La disponibilité ( A pour Availability)
3. La tolérance aux pannes et aux coupures réseaux ( P pour Partition-tolerance)

Le théorème postule que pour toute base de données distribuée, on ne peut choisir que 2 de ces 3 paramètres, jamais les 3 en même temps. En théorie, on peut donc choisir les couples suivants :

a. Cohérence et disponibilité ( CA ) donc non résistante aux pannes ( P )
b. Cohérence et tolérance aux pannes ( CP ) donc non disponible à 100% ( A )
c. Disponibilité et tolérance aux pannes ( AP ) donc non cohérente à 100% ( C )

Ceci est la théorie. En pratique, on se rend compte que le paramètre P est plus ou moins imposé. En effet, les coupures réseaux cela arrive, c'est inévitable, même si on s'appelle Google... Du coup, le choix se résume en fin de compte à CP ou AP. Cassandra fait clairement le choix de AP pour une tolérance aux pannes et une disponibilité absolue. En contrepartie, Cassandra sacrifie la cohérence absolue (au sens ACID du terme) contre une cohérence finale, c'est à dire une cohérence forte obtenue après une convergence des données (garantie par un ensemble de mécanisme d'anti-entropie).

Architecture

L'architecture Cassandra (qu'on va appeler désormais en C* pour plus de concision) s'inspire énormément du papier de recherche Big Table de Google , ainsi que de l'architecture Dynamo d'Amazon. Le moteur de stockage de C* dérive directement de Big Table alors que sa couche de distribution de données s'inspire de l'architecture de Dynamo.

Sur le schéma ci-dessus, on distingue la présence de 3 couches métiers :

• API, responsable de recevoir les requêtes venant des clients sous format Thrift (protocole RPC) ou dans le nouveau format binaire CQL3
• Dynamo, responsable de la distribution des données entre différents noeuds et du protocole peer-to-peer
• Base de données, responsable de la persistance des données sur disques

Désormais et jusqu'à la fin de cette série d'articles, on s'intéressera uniquement à la couche base de données, les autres couches techniques feront l'objet d'articles ultérieurs.

Modèle physique de données

Keyspace et tables

Dans un cluster Cassandra, on trouve des tables et des keyspaces. Un keyspace peut-être vu comme une base. En effet, dans un modèle multi-tenant on sépare les données de chaque partie dans des keyspaces.

A l'intérieur de chaque keyspace, on trouve des tables. Une table dans C* a la même signification qu'une table dans le monde SQL, avec des lignes et des colonnes.

La terminologie de table est apparue avec CQL3. L'ancien terme pour désigner une table est column family. Dans la suite de l'article, nous utiliserons indistinctement chacun de ces termes.

Partitions, Colonnes et Cellules

Dans une table, les données sont stockées sous forme de lignes et de colonnes comme suit :

Note : désormais, on utilisera le symbole # pour désigner une clé. Par exemple, clé de partition s'écrira #partition, clé de colonne #col.

Les données sont disposées sur des lignes (qu'on appelle partitions), et au sein de chaque partition on trouve une série de colonnes avec #col/cellule qu'on peut assimiler à une série de clé/valeur.

On peut remarquer qu'une partition peut contenir de 1 à N colonnes, la limite physique de N étant de 2 milliards (2.10⁹), ce qui nous laisse beaucoup de marge. Une différence avec une base de données SQL classique est qu'ici, C* ne réserve pas d'espace en avance pour chaque colonne. La création de colonne se fera lorsqu'on insérera de nouvelles données, dynamiquement.

A noter qu'il est possible d'insérer une colonne juste avec #col et sans cellule (c'est ce qu'on appelle les colonnes value-less).

Pour résumer, une table peut être visualisée conceptuellement comme un ensemble de :

    <Clé de partition, <Clé de colonne,cellule>>
 

A noter que les colonnes sont triées par leur clé de colonne. Nous verrons par la suite que cette fonctionnalité est cruciale pour la modélisation de données dans Cassandra.

Distribution de Données

Concept

Dans un cluster, les partitions dans une table sont réparties entre plusieurs noeuds. Il y a 2 façons de répartir les données :

1) De manière ordonnée, chaque noeud prend en charge une plage de clé de partition triée par ordre croissant.

Exemple : si la clé de partition est le nom de famille, les noms commençant entre A et E se répartissent sur le noeud₁, entre F et J sur le noeud₂ etc...

2) De manière aléatoire, chaque noeud prend en charge une plage de la clé de partition distribuée uniformément (on verra comment ci-dessous).

Une répartition ordonnée a l'avantage de conserver l'ordre. Par contre, on se retrouvera avec des noeuds non équilibrés. En effet, il est fort à parier qu'il y aura beaucoup plus de noms de famille commençant par F-J que V-Z, du coup certains noeuds contiendront plus de données que d'autres.

Le choix du type de partitionnement se fait au niveau du keyspace. Pour un partitionnement ordonné, il faut utiliser le BytesOrderedPartitioner et RandomPartitioner pour un partitionnement aléatoire. Depuis C* version 2, on conseille l'utilisation du Murmur3Partitioner, plus performant que le RandomPartitioner basé sur un simple hash MD5.

Dans tous les cas, il est vivement conseillé d'utiliser un partitionnement aléatoire pour éviter les hot-spots dans le cluster et une meilleure répartition de la charge. Les cas où l'utilisation du partitionnement ordonné est appropriée sont très rares.

Quel que soit le type de partitionnement choisi, une partition (ligne physique) se trouve toujours entièrement sur un seul noeud. Il n'est pas possible de trouver le début d'une partition sur un noeud_A et la fin sur un autre noeud_B.

Les tokens

L'un des moyens simples pour bien répartir les données sur tout le cluster est d'utiliser une fonction de hachage dispersif et uniforme. En pratique, à chaque opération de modification ou de lecture de données, le client fournit une clé de partition (#partition) à C*. Cette clé passe d'abord par une fonction de hachage et le résultat est ce qu'on appelle un token. En choisissant bien la fonction de hachage, on peut faire en sorte qu'à 2 valeurs de #partition assez proche, les tokens produits soient très différents afin de mieux les disperser :

hash(#partition1) = token1
hash(#partition2) = token2
 
 token1 !!= token2

Si l'on prend le hash MD5, la valeur du token se situe dans l'intervalle [0 .. 2¹²⁷-1]. On répartit uniformément cette plage de valeur de token entre les différents noeuds du cluster. Ainsi, pour un cluster de 5 noeuds, on aura par exemple :

• le noeud₁ est responsable de la plage ]0 .. (2¹²⁷-1)/5]
• le noeud₂ est responsable de la plage ](2¹²⁷-1)/5 .. (2¹²⁷-1)*2/5]
• le noeud₃ est responsable de la plage ](2¹²⁷-1)*2/5 .. (2¹²⁷-1)*3/5]
• le noeud₄ est responsable de la plage ](2¹²⁷-1)*3/5 .. (2¹²⁷-1)*4/5]
• le noeud₅ est responsable de la plage ](2¹²⁷-1)*4/5 .. (2¹²⁷-1)]

Comme on peut le voir ci-dessus, l'ensemble des partitions (lignes) d'une table est éparpillé sur plusieurs noeuds grâce à la distribution du token. La fonction de hachage étant dispersif, on garantit une distribution uniforme des données et de la charge sur tous les noeuds du cluster.

Le seul inconvénient de cette façon de faire est qu'il n'est plus possible de demander une plage de valeur de #partition. Demander des noms de famille entre A et B par exemple, reviendrait à scanner tous les noeuds du cluster, un coût prohibitif sur un cluster de plusieurs centaines de noeuds.

Le noeud coordinateur

Dans C*, il n'y a pas de notion de maître/esclave. Une architecture sans maître/esclave garantit l'absence de point unique de défaillance (SPOF). Par contre, pendant la durée d'une requête (lecture ou écriture), le client fournit toujours une #partition. Le noeud qui reçoit la requête ne l'exécute pas nécessairement en local car le hash de cette #partition ne tombe pas forcément dans la plage de hash dont il est responsable.

Il va rediriger cette requête vers un autre noeud du cluster responsable de ces données. Dans ce cas là, il jouera le rôle de noeud coordinateur pour la requête actuelle.

Soulignons que le noeud coordinateur ne joue en aucun cas un rôle de maître, il est juste responsable de la redirection de la requête. N'importe quel noeud dans le cluster peut à tout moment jouer le rôle de coordinateur, il y a une symétrie totale.

Structure d'une table

Maintenant, nous allons voir comment une table est représentée dans le moteur de stockage (storage engine) de C*.

Il faut savoir d'abord que les tables sont très fortement typées. Par type, on entend le type de :

1. la clé de partition (#partition)
2. la clé de colonne (#col)
3. la celulle

Lors de la création d'une table (column family), on doit définir ces 3 types qui ne peuvent plus être modifiés par la suite.

Les types

De base, C* supporte les types suivants :

• bytes
• boolean
• composite
• counter
• date (bientôt déprécié)
• decimal
• double
• float
• inetAddress
• int32 (entier de taille fixe)
• integer (entier de taille variable)
• long
• uuid
• timestamp
• timeuuid (uuid de type 1)

Ci-dessous, le script de création d'une table user avec l'API Thrift :

    create column family user 
      with key_validation_class = LongType 
      and comparator = UTF8Type 
      and default_validation_class = UTF8Type

• key_validation_class correspond au type de la #partition
• comparator correspond au type de la #col
• default_validation_class correspond au type de la cellule

Ici, la #partition est l'userId représenté par un Long (LongType). Les clés de colonnes sont codées en String ( UTF8Type ) et correspondent au nom de chaque propriété d'une personne. Le type de la cellule est du String ( UTF8Type ) pour stocker les données sous forme textuelle.

Voici un contenu possible de la table user en utilisant le client cassandra-cli avec l'API Thrift :

[default@test] list user;
Using default limit of 100
Using default cell limit of 100

 -------------------
 RowKey: 10
 => (name=age, value=32, timestamp=1403441029826000)
 => (name=nom, value=MARTIN, timestamp=1403441024052000)
 => (name=prenom, value=Jean, timestamp=1403441027825000)
 -------------------
 RowKey: 11
 => (name=age, value=26, timestamp=1403441047501000)
 => (name=nom, value=DUCROS, timestamp=1403441034463000)
 => (name=prenom, value=Elise, timestamp=1403441039578000)

RowKey correspond à #partition.

Dans l'exemple, la table contient 2 personnes :

• Jean MARTIN 32 ans, userId = 10
• Elise DUCROS 26 ans, userId = 11

Pour chaque personne, on retrouve 3 colonnes avec les propriétés name, value et timestamp. name représente la clé de colonne (#col), value représente la cellule. Quant au timestamp, c'est une propriété de la colonne, assignée automatiquement au moment de l'insertion de la donnée par C*. Nous verrons plus tard à quoi cette valeur de timestamp peut bien servir.

On remarque que les colonnes sont triées alphabétiquement par leur clé. Ceci est dû au fait que C* trie naturellement les #col dans l'ordre naturel du type, qui est ici du String.

L'exemple ci-dessus illustre la manière dont C* stocke physiquement les données sur disque : de manière séquentielle et triées par type de #col

Ce stockage a un grand avantage, il permet un accès séquentiel aux données sur disque lors de la lecture, ce qui améliore grandement les performances. On peut même affirmer sans trop de risque que ce modèle de données a été conçu exprès pour une lecture rapide sur les disques durs rotatifs classiques.

On pourrait croire naïvement que l'arrivée des SSD bon marché rend ce modèle de stockage séquentiel moins pertinent, que nenni ! La présentation de Rick Branson sur le support des SSDs dans C* prouve le contraire, ainsi que cet article de highscalability.com qui montre que les opérations en séquentiel ont encore de beaux jours devant elles.

Abstraction

D'une manière générale, une table dans C* peut être assimilée à une structure de données.

  Map<#partition,SortedMap<#col,cellule>>

On retrouve le tri des #col avec la SortedMap (Map triée). La Map externe n'est pas triée si on utilise un partitionnement aléatoire qui disperse les #partition sur tous les noeuds.

Si on avait choisi un partitionnement ordonné, la structure d'une table serait assimilable à :

  SortedMap<#partition,SortedMap<#col,cellule>>

Les requêtes

Étant donné la façon dont les données sont stockées sur disque, il y a différentes façons d'insérer et de récupérer les données. Dans ce chapitre, nous allons passer en revue ces techniques et étudier leurs avantages/inconvénients.

L'API Thrift

Historiquement, avant l'arrivée de CQL3, la seule façon d'interagir avec C* passait par l'API Thrift. Bien que très puissante et versatile, cette API reste très bas niveau et demande pas mal d'effort au développeur pour communiquer avec la base. Néanmoins, cette API donne un bon aperçu de la façon dont le moteur de stockage de C* gère les données et est, à ce titre, un bon outil pédagogique pour expliquer et illustrer le modèle de données.

Ci-dessous, un résumé succint de quelques méthodes importantes de l'API Thrift (liste non-exhaustive) :

• get(#partition,#col) : récupère une cellule identifiée par #partition et #col

Exemple: table user

Un get(10,"age") donnerait 32, un get(11,"nom") donnerait DUCROS.

• getSlice(#partition, #col_start, #col_end, reverse, limit) : pour une #partition donnée, récupère toutes les colonnes situées entre #col_start et #col_end, dans l'ordre décroissant ou pas (reverse), et limité aux limit colonnes trouvées. On appelle cette requête également Slice Query car il s'agit de demander une tranche de colonnes pour une partition donnée.

Exemple : table superhéros Comics

Un getSlice(#partition = "héros",#col_start = "catwoman", #col_end = "green latern", reverse = false, limit = 100) donnerait les colonnes :

["catwoman/{...}", "flash/{...}", "green latern/{...}"]

Un getSlice(#partition = "vilains",#col_start = "sinestro", #col_end = "darkseid", reverse = true, limit = 2) donnerait les colonnes :

["sinestro/{...}", "lex luthor/{...}"]

Il est possible d'omettre les bornes de sélection #col_start et #col_end. Dans ce cas là, C* prend toutes les colonnes.

Un getSlice(#partition = "neutre",#col_start = null, #col_end = "jimmy olsen", reverse = false, limit = 100) donnerait les colonnes :

["alfred/{...}", "james gordon/{...}", "jimmy olsen/{...}"]

La même requête avec une valeur de limit = 2 donnerait: ["alfred/{...}", "james gordon/{...}"]. On voit que dans ce cas, la borne de fin #col_end = "jimmy olsen" n'est même pas atteinte, C* s'arrête de lire des données dès que la limite spécifiée est atteinte.

En règle générale, C* essaie de prendre les critères de recherche les plus restrictifs et les applique.

Comme on peut avoir jusqu'à 2.10⁹ colonnes sur une partition physique, il est de bon ton de donner une limite à notre requête. Cette bonne pratique a été poussée au niveau API et oblige les clients à toujours fournir une limite pour éviter de charger trop de données et saturer le serveur.

• multiGetSlice(list #partition,#col_start,#col_end,reverse,limit) : similaire à getSlice sauf que la requête est exécutée pour une liste de #partition. C* attend d'avoir les données pour chaque #partition avant de renvoyer la réponse au client.

L'avantage du multiGetSlice est une plus grande simplicité du côté client, il n'y a qu'une seule requête à envoyer, le travail de rassemblage des résultats est pris en charge par C*. L'inconvénient est que le temps de réponse de la requête globale est lié au temps de réponse de la requête unitaire la plus lente.

• insert(#partition,#col,cellulle) : insérer la cellule donnée à la partition dont la clé est #partition et à la colonne dont la clé est #col
• remove(#partition,#col) : effacer toute la colonne identifiée par #partition et #col

On peut remarquer que toutes les requêtes mentionnées ci-dessus demandent toujours une #partition. En effet, comme C* utilise #partition pour calculer le token et répartir la donnée dans le cluster, sans #partition C* ne saurait pas où se trouve la partition et serait obligé de scanner tous les noeuds du cluster, pour un coût prohibitif. C'est pourquoi les API Thrift ci-dessus demandent systématiquement une #partition.

Les #col sont par contre facultatives dans certains cas, notamment pour les Slice Query et MultiGet Slice Query car le paramètre limit est là pour jouer les garde-fous.

Abstraction

Si l'on reprend l'abstraction avec la structure de données mentionnée précédemment :

  Map<#partition,SortedMap<#col,cellule>>

On peut résumer les méthodes de l'API Thrift comme :

a. Accès direct à une cellule (get, insert, remove)

b. Accès à une plage de colonnes (getSlice)

c. Accès à une plage de colonnes pour un ensemble de partitions (multiGetSlice)

On constate que les méthodes d'accès aux données respectent bien la structure de données de la double Map imbriquée présentée plus tôt.

Conclusion

Avec ce premier long article d'introduction, nous avons vu comment Cassandra stocke physiquement les données sur disque et par quel moyen il y accède. Nous avons vu également l'API Thrift qui est très bas niveau mais illustre bien le modèle de données.

Dans le prochain article, nous regarderons en détails le stockage physique des données sur disques, notamment le type composite, le timestamp, les colonnes d'expiration et les colonnes tombstones.

Au sujet de l'Auteur

DuyHai DOAN est Développeur Java depuis toujours, il s'est passionné pour le domaine du Big Data et plus particulièrement pour Cassandra depuis plusieurs années. Il fait régulièrement des présentations pour vulgariser l'utilisation de Cassandra au plus grand nombre. La journée, il participe au projet Libon, le Viber/WhatsApp du groupe Orange en utilisant Cassandra comme solution NoSQL. Le soir, il code sur Achilles, un object mapper pour rendre le développement sur Cassandra encore plus aisé et productif (approche TDD, génération du schéma, request tracing ...).

Suivez DuyHai sur Twitter à @doanduyhai.