Dans cet article, nous détaillons la façon dont le moteur de stockage organise les données sur disque et les différents types de colonnes que l'on trouve dans C*. Si vous avez raté le premier article d'introduction au modèle de données dans C*, c'est par ici.

Le type composite

Si le modèle de données de C* devait s'arrêter à la simple abstraction des Map imbriquées, on n'irait pas bien loin. En effet, les requêtes avec un tel modèle sont plutôt limitées. Heureusement pour nous, le type composite a été introduit et avec lui de nouvelles possibilités pour requêter les données.

Définition

L'idée du type composite est qu'au lieu d'avoir un seul type pour les #partition ou #col, on en définit plusieurs... Concrètement , il s'agit de stocker dans une clé (de partition ou de colonne) plusieurs composantes de type différent. Ainsi on aura :

type(#partition) = type1:type2:...:typentype(#col) = type1:type2:...:typen

Pour les composites de colonnes, les données seront triées dans l'ordre successif de leurs composantes. Si on a une composite de colonne de type DateType:UTF8Type:LongType par exemple, les #cols seront triées par date, puis par tri lexicographique et enfin par ordre naturel des entiers.

En théorie on peut mettre autant de composantes différentes que l'on veut, en pratique on s'arrêtera à 2 - 3 composantes pour les composites.

L'abstraction en structure de données correspondante est :

  Map<#partition,
    SortedMap<composante1,
      SortedMap<composante2,
        ...
          SortedMap<compostanteN,valeur>...>

Exemple

Sans plus tarder, voyons en pratique comment fonctionnent les composites.

Supposons qu'on veuille stocker l'hygrométrie (température et humidité entre-autres) pour différentes villes en France et à différents moments. Naturellement, on choisira le nom de la ville comme #partition et la date comme #col. Sans les composites, on devrait logiquement stocker la température et l'humidité dans la cellule.

Ci-dessous le script de création de la table avec l'API Thrift :

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

Et les données :

(Cliquez pour agrandir l'image)

On se rend bien compte qu'il faut arriver à stocker nos métriques de température et d'humidité dans une seule cellule pour chaque date. On peut soit tout stocker sous forme de String et faire le découpage à la main, soit stocker sous forme sérialisée en JSON ou bytes. Quoiqu'il en soit, cela n'est pas très pratique au final.

En ligne de commande, avec le client cassandra-cli, on verrait ceci :

[default@test] list hygrometrie_json;
Using default limit of 100
Using default cell limit of 100
-------------------
RowKey: Paris
=> (name=20140625, value={"temperature": 26.8, "humidite":0.72}, timestamp=1405866112852000)
=> (name=20140626, value={"temperature": 27.0, "humidite":0.70}, timestamp=1405866112856000)
=> (name=20140627, value={"temperature": 27.7, "humidite":0.65}, timestamp=1405866112857000)
-------------------
RowKey: Lyon
=> (name=20140625, value={"temperature": 29.0, "humidite":0.82}, timestamp=1405866112859000)
=> (name=20140626, value={"temperature": 30.0, "humidite":0.87}, timestamp=1405866112860000)
=> (name=20140627, value={"temperature": 29.4, "humidite":0.78}, timestamp=1405866112862000)

Avec les composites, le problème sera résolu de manière plus élégante :

    create column family hygrometrie_composite 
      with key_validation_class = UTF8Type 
      and comparator = CompositeType(LongType,UTF8Type)
      and default_validation_class = UTF8Type

Ici la #col a deux composantes, la première de type LongType pour coder la date au format YYYYMMdd et la deuxième de type UTF8Type pour coder le type de mesure (température ou humidité).

Les données seront stockées de la manière suivante :

(Cliquez pour agrandir l'image)

Avec le client cassandra-cli :

[default@test] list hygrometrie;
Using default limit of 100
Using default cell limit of 100
-------------------
RowKey: Paris
=> (name=20140625:humidite, value=0.72, timestamp=1405866368678000)
=> (name=20140625:temperature, value=26.8, timestamp=1405866368675000)
=> (name=20140626:humidite, value=0.7, timestamp=1405866368690000)
=> (name=20140626:temperature, value=27.0, timestamp=1405866368685000)
=> (name=20140627:humidite, value=0.65, timestamp=1405866368695000)
=> (name=20140627:temperature, value=27.7, timestamp=1405866368693000)
-------------------
RowKey: Lyon
=> (name=20140625:humidite, value=0.82, timestamp=1405866368701000)
=> (name=20140625:temperature, value=29.0, timestamp=1405866368699000)
=> (name=20140626:humidite, value=0.87, timestamp=1405866368705000)
=> (name=20140626:temperature, value=30.0, timestamp=1405866368703000)
=> (name=20140627:humidite, value=0.78, timestamp=1405866368707000)
=> (name=20140627:temperature, value=29.4, timestamp=1405866368706000)

L'utilisation des composites dans ce cas a permis de séparer, pour une date donnée, la température et l'humidité dans deux colonnes physiques distinctes.

On réserve une colonne physique pour chaque type de mesure, ici température et humidité. On notera également que la valeur de la date est dupliquée, une fois pour chaque type mesure :

=> (name=20140625:humidite, value=0.72, timestamp=1405866368678000)
=> (name=20140625:temperature, value=26.8, timestamp=1405866368675000)

Si l'on introduisait des types de mesure supplémentaires, temperature ressentie et humidite relative par exemple, on aurait eu en base :

=> (name=20140625:humidite, value=0.72, timestamp=1405866368678000)
=> (name=20140625:humidite_relative, value=0.60, timestamp=1405866368678000)
=> (name=20140625:temperature, value=26.8, timestamp=1405866368675000)
=> (name=20140625:temperature_ressentie, value=25.0, timestamp=1405866368675000)

Cette fois ci, la date est dupliquée 4 fois.

On voit bien que les composites permettent une plus grande facilité pour modéliser les données. Par contre, le prix à payer est une plus grande consommation en espace disque.

Abstraction et Requêtes

Pour l'exemple de la table d'hygrométrie ci-dessus, l'abstraction en structure de données correspondante est :

  Map<ville,
    SortedMap<date,
      SortedMap<type_de_mesure,valeur>>>

Avec une telle structure de données, les types de requêtes différentes que l'on peut faire sont :

1. Pour une ville, donner toutes les mesures quelle que soit la date (requête coûteuse sans clause limit car on remonte toutes les colonnes sur la partition correspondante à une ville)
2. Pour une ville et une date, donner la valeur de la température
3. Pour une ville et une date, donner la valeur de l'humidité
4. Pour une ville et une date entre 2 bornes, donner les mesures d'hygrométrie

Et c'est tout ! Le lecteur attentif se demandera s'il est possible, pour une ville et un type de mesure donné, de lister les valeurs à toutes les dates. Ce n'est simplement pas possible.

Pourquoi ?

Parce qu'en regardant la structure de données présentée plus tôt, pour accéder à la valeur d'hygrométrie, il faut d'abord donner la ville, puis la date, puis le type de mesure, précisément dans cet ordre là.

Pour pouvoir faire la requête demandée, il faudrait inverser le type de mesure et la date et créer une table comme suit :

    create column family hygrometrie_composite 
      with key_validation_class = UTF8Type 
      and comparator = CompositeType(UTF8Type,LongType)
      and default_validation_class = UTF8Type

Le timestamp des colonnes

Présentation

Chaque colonne physique dans C*, outre la #col et la cellule, contient une méta-donnée appelée timestamp. Cette valeur de timestamp s'exprime en micro seconde et est générée automatiquement côté serveur lorsqu'une nouvelle colonne physique est créée.

Cette méta donnée timestamp apparaît très clairement quand on utilise le client cassandra-cli :

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

 -------------------
 RowKey: 10
 => (name=age, value=32, timestamp=1405867440163000)
 => (name=nom, value=MARTIN, timestamp=1405867440163000)
 => (name=prenom, value=Jean, timestamp=1405867440163000)
 -------------------
 RowKey: 11
 => (name=age, value=26, timestamp=1405867440164000)
 => (name=nom, value=DUCROS, timestamp=1405867440164000)
 => (name=prenom, value=Elise, timestamp=1405867440164000)

Avec le client cqlsh, le timestamp n'apparaît pas spontanément, il faut utiliser la fonction préféfinie WRITETIME() pour avoir l'information :

cqlsh:test> select user_id,nom,prenom,age,WRITETIME(nom),WRITETIME(prenom),WRITETIME(age) from users;

 user_id | nom   | prenom | age | writetime(nom)   | writetime(prenom) | writetime(age)
---------+-------+--------+-----+------------------+-------------------+------------------
      10 |  Jean | MARTIN |  32 | 1405867440163000 |  1405867440163000 | 1405867440163000
      11 | Elise | DUCROS |  26 | 1405867440164000 |  1405867440164000 | 1405867440164000

Remarquons que pour chaque personne, les colonnes ont le même timestamp. En effet, lors de l'insertion des données INSERT INTO users(user_id,nom,prenom,age) VALUES(...) le coordinateur qui reçoit la requête génère le même timestamp à toutes les colonnes. Pour avoir des timestamps différents, il faudrait avoir inséré les colonnes une à une avec des requêtes distinctes.

Rôle du timestamp

Ce timestamp sert à C* pour distinguer 2 colonnes ayant la même #col et partant de là, à faire la résolution de conflit lors de la lecture.

C* est un moteur de stockage basé sur principe du Log Structured Merge Tree, les données écrites sur disques sont immuables, elles ne sont jamais modifiées. Supposons qu'on insère un utilisateur avec un âge initial à 30 à t₁ ans et qu'on modifie cet âge plus tard :

• à t₂ : 31 ans
• à t₃ : 29 ans

En base, puisque les données sont immuables, C* se contentera de rajouter des colonnes physiques avec une valeur de timestamp différente à chaque fois. Voilà à quoi ressemblerait les données stockées physiquement sur disque :

Une modification/mise à jour dans C* se traduit toujours par la création d'une colonne physique, avec un timestamp supérieur aux timestamps précédents mis sur cette colonne.

Lors de la lecture, C* rassemblera toutes les colonnes et pour une même #col (ici "age") s'il y a plusieurs instances physiques de colonnes, il gardera celle dont le timestamp sera le plus élevé. Dans l'exemple, on aura age = 29.

La règle de résolution dans C* est du last-write-win.

La résolution à la micro seconde est nécessaire car sous forte charge en mode distribué, on peut avoir plusieurs clients qui écrivent des valeurs différentes, pour une #col donnée, au sein d'une même milli seconde.

Grâce à cette méthode de résolution de conflit, chaque noeud de C* peut recevoir les requêtes d'insertion/update dans le désordre, même plusieurs fois de manière dupliquée. A la fin d'un temps fini, lorsque les modifications ont été correctement propagées, les données restent cohérentes à la lecture.

Par conséquent, une telle méthode de résolution basée sur le timestamp nécessite une synchronisation constante du temps entre les différents noeuds du cluster.

Note: il est possible pour le client de forcer la valeur du timestamp à une valeur particulière. C'est néanmoins déconseillé de le faire car cela interfère évidemment avec le mécanisme de résolution de conflit, à moins de savoir exactement ce que l'on fait.

Les types de colonnes

Ci-dessus nous avons vu l'anatomie d'une colonne "normale" dans C*, mais il existe d'autres types de colonnes réservées à des usages spécifiques.

Les colonnes d'expiration

Avec C* il est possible de définir une durée de vie appelée TimeToLive (TTL) sur une colonne physique donnée. Ce TTL s'exprime en seconde.

Exemple avec le client cqlsh :

cqlsh:test> INSERT INTO users(user_id,nom,prenom) VALUES(10,'Jean','MARTIN');
cqlsh:test> UPDATE users USING TTL 1000 SET age = 32 WHERE user_id=10;

Ci-dessus nous avons créé l'utilisateur "Jean MARTIN" et nous avons défini l'âge à 32 ans avec une durée de vie de 1000 secondes.

Si l'on requête les données sur "Jean MARTIN" immédiatement après l'insertion :

cqlsh:test> SELECT * FROM users WHERE user_id=10;

user_id | age | nom  | prenom
--------+-----+------+--------
     10 |  32 | Jean | MARTIN

Après 1000 secondes, on aurait :

cqlsh:test> SELECT * FROM users WHERE user_id=10;

user_id | age   | nom  | prenom
--------+-------+------+--------
     10 |  null | Jean | MARTIN

La donnée sur l'âge a expiré. Comment fait C* pour expirer automatiquement cette colonne ?

Avec l'utilitaire sstable2json fourni dans le répertoire $CASSANDRA_HOME/bin, on peut demander à C* de convertir un fichier de données binaires au format JSON :

% sstable2json /tmp/cassandra/data/test/users/test-users-jb-2-Data.db 
[
  {"key": "000000000000000a",
   "columns": [
      ["","",1405871120597000], 
      ["age","32",1405871489294000,"e",1000,1405872489], 
      ["nom","Jean",1405871120597000], 
      ["prenom","MARTIN",1405871120597000]
   ]
  }
]

Nous voyons bien que les colonnes "nom" et "prénom" ont le même timestamp 1405871120597000 puisqu'elles ont été insérées au même moment. La colonne "age" a un timestamp légèrement supérieur 1405871489294000 mais également 3 propriétés de plus :

1. "e" : indique que cette colonne est une colonne d'expiration
2. 1000 : indique le TTL qui a été défini sur cette colonne
3. 1405872489 : indique le timestamp, en seconde après lequel cette colonne cesserait d'exister

Le lecteur attentif aurait remarqué que 1405872489 = 1405871489 294000 / 10⁶ (micro sec -> sec) + 1000. Le calcul est bon.

Egalement, la colonne ["","",1405871120597000] est une colonne marqueur dont on verra l'utilité dans le prochain article.

Les colonnes tombstone

On a vu précédemment qu'avec C*, les données, une fois écrites sur disque, sont immuables. Une modification de valeur revient à écrire une nouvelle colonne avec un timestamp supérieur. Qu'en est il de la suppression des données ?

En suivant la même logique, il n'y a pas de suppression physique. A la place, C* écrira une nouvelle colonne physique dite tombstone qui signifie que la colonne en question est supprimée/n'existe pas.

Un exemple illustrera mieux le fonctionnement :

cqlsh:test> INSERT INTO users(user_id,nom,prenom,age) VALUES(10,'Jean','MARTIN',32);
cqlsh:test> DELETE age from users WHERE user_id=10;

Avec sstables2json, on voit ceci :

[
  {"key": "000000000000000a",
   "columns": [
      ["","",1405871483973000], 
      ["age","53cbe581",1405871489294000,"d"], 
      ["nom","Jean",1405871483973000], 
      ["prenom","MARTIN",1405871483973000]
   ]
  }
]

Cette fois ci, on a :

1. "d" comme marqueur d'effacement (deleted)
2. 1405871489294000 comme timestamp du moment où la suppression a été effectuée
3. 53cbe581 comme valeur, assez étrange. On s'attendait à 32. En réalité, c'est le temps local serveur quand la suppression a eu lieu, exprimé en seconde et sérialisé en bytes, qui a été mis à la place de l'âge

Le lecteur averti se demanderait pourquoi stocker le temps local de suppression alors qu'on aurait pu utiliser le timestamp qui a été justement généré lors de la suppression de cette colonne...

En réalité, comme mentionné ci-dessus, il est toujours possible pour un client de forcer la valeur du timestamp, y compris pour une colonne tombstone. Pour cette raison, le serveur ne se fie pas à ce timestamp lorsqu'il fait le ménage parmi les colonnes tombstone mais plutôt au temps local de suppression qu'il a positionné lui-même.

Les colonnes compteur

Le dernier type de colonne spéciale est le type compteur distribué. C'est un type assez particulier dans C*. Avec un compteur, on ne peut faire que les opérations suivantes :

• lire la valeur actuelle du compteur
• incrémenter de n
• décrémenter de n
• supprimer le compteur

On ne peut pas insérer une valeur initiale pour un compteur. Ceci est lié à la façon dont C* implémente les compteurs distribués. Pour résumer, chaque cellule d'un compteur peut se découper en 3 parties :

1. shard id : identifie de manière unique le noeud à l'origine de la modification du compteur
2. temps logique du shard : valeur croissante qui s'incrémente à chaque fois que le compteur est modifié
3. valeur du shard : valeur du compteur

Lorsqu'on lit le mot shard, on se demande si la valeur du compteur est distribuée à chaque replica. Et c'est exactement le cas.

Supposons un compteur répliqué sur 3 noeuds A, B et C et la séquence suivante de mise à jour :

a) incrémente +2 sur A b) incrémente +1 sur A
c) décrémente -1 sur C
d) incrémente +3 sur B

Ci-dessous une représentation schématique de la valeur du compteur à chaque opération :

Chaque shard est répliqué intégralement sur les 3 noeuds, de sorte qu'à la lecture, il suffit de lire un seul noeud et de faire la somme des valeurs dans les 3 shards pour avoir la valeur actuelle du compteur.

Il existe quelques limitations sur l'utilisation des compteurs :

1. Une table qui contient des compteurs ne peut contenir aucun autre type de données. En effet, le type compteur est un type à part. Pour créer une table compteur sous cassandra-cli

        create column family compteur 
          with key_validation_class = LongType 
          and comparator = UTF8Type 
          and default_validation_class = CounterType
   

   On voit bien que le type de la cellule pour la table "compteur" est CounterType, dès lors on ne peut plus stocker aucun autre type dans les celulles (Long, int, String ...).

2. On ne peut pas effacer un compteur puis le réutiliser immédiatement après. Si l'on crée la séquence incrémente, suppression, incrémente, dans un environnement distribué, l'ordre de suppression peut arriver après le dernier incrément, auquel cas on a un comportement non déterministe. Ceci est une limitation technique inhérente à la façon dont C* implémente les compteurs distribués. Il est cependant possible de supprimer définitivement un compteur si on ne le ré-utilise pas immédiatement après.

Conclusion

Avec cet article, nous avons vu les détails d'implémentation du moteur de stockage de C* ainsi que les différents types de colonnes. A partir du prochain article, nous parlerons exclusivement du nouveau language CQL3.

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 ...).