Tokyo Tyrant / Tokyo Cabinet, un key-value store à la Japonaise

Les bases de données non relationnelles sont mises en avant depuis quelques temps avec un panel important de systèmes de stockage de la forme clé/valeur (key/value store). Cette approche permet d’avoir des structures optimisées pour certains types de fonctionnel et facilement distribuables. Tokyo Cabinet est un de ces outils. C’est un outil de stockage clé/valeur open source sponsorisé et utilisé par Mixi (Facebook japonais). Il a été développé par Mikio Hirabayashi que vous pouvez retrouver ainsi que l’exhaustivité des produits qu’il met à disposition sur Mikio Hirabayashi’s homepage. Tokyo Cabinet est couplé à un autre produit : Tokyo Tyrant. Tokyo Tyrant est en fait l’interface réseau qui permet, entre autre, d’accéder à partir d’un serveur distant à Tokyo Cabinet. Il ne se limite cependant pas à cela et permet un certain nombre de fonctionnalités très intéressantes. Le point fort de ce couple est la rapidité de traitement des requêtes, ainsi que les possibilités de mise en oeuvre.

Pour servir de support à cet article, je vous propose de regarder cette vidéo très intéressante de Ilya Grigorik, fondateur et CTO de AideRSS, que vous pourrez retrouver sur son blog igvita.com (un blog très intéressant que je vous conseille de lire).

La VIDEO.

Cette vidéo de 30 min, dans un anglais tout à fait abordable, est très intéressante, notamment sur les extensions de fonctionnalités rendues possibles par le langage de scripting Lua, intégrable au niveau de Tokyo Tyrant afin de permettre la mise en place de « user-defined fonctions » au niveau du serveur, centralisant les traitements et les rendant pseudo-atomiques. Je reviendrai dessus par la suite.

Les APIs
Comme je vous le précisais, Tokyo Tyrant/Tokyo Cabinet est un couple gérant respectivement les requêtes à partir de serveurs distants (interface réseau) et les accès au système de stockage. 6 APIs sont disponibles afin de stocker les données :

  1. On memory Hash,
  2. On memory B+tree,
  3. File Hash,
  4. File B+tree,
  5. Fixed-length Array,
  6. Table.

Chacune d’entre elles a ses propres spécificités et répond à des besoins particuliers en termes de performances et de fonctionnalités.

Je ne paraphraserai pas la vidéo de Ilya Grigorik qui explique déjà un certain nombre de choses, mais apporterai quelques précisions.

Sur la notion de complexité des mécanismes de stockage Hash et B+tree (On memory ou File), les fonctions O(1) et O(log N) représentent la complexité d’accès à la donnée en fonction du nombre d’occurences stockées dans le système. On comprend bien que le comportement O(1) correspond bien à celui d’une hashtable, puisque le temps d’accès à la donnée ne dépend pas du nombre d’occurrences. En effet, la donnée est accédée directement à partir du hash de sa clé. Eventuellement, cette complexité peut varier si des collisions sur le hash apparaissent (2 clés différentes peuvent donner le même hash, à ce hash correspond alors une liste chainée de valeurs possibles). Il n’y a pas non plus d’index et donc de reconstruction d’index sur les insertions : donc gain de rapidité par rapport à une base de données classique. Pour plus de détail sur le fonctionnement des hashtables suivez ce lien. Voici également 2 schémas issus de « Wikipedia, the free encyclopedia » expliquant la notion de hash et de collision :

Hashtable

Hashtable

Hashtable - Collisions

Hashtable - Collisions

La notion permettant d’évaluer la probabilité de collision est ce que l’on appelle la dispersion… Mais cela est un autre sujet ! ;ob

On comprend que le B+tree est donc un peu moins performant car sensible dans une certaine mesure (O(log N)) au nombre d’enregistrements. B+tree trouve son utilité dans le fait que le stockage est moins volumineux sur disque (ou en mémoire). Dans le cas du B+tree, les clés ne sont pas nécessairement uniques et il y a une notion de tri.

Pour le détail sur ces APIs, vous pouvez consulter la spécification.

Les performances
Il est à noter que les performances atteintes par Tokyo Cabinet seront probablement limitées du fait de l’utilisation de Tokyo Tyrant, puisque dans la majorité des cas vous aurez probablement à accéder au système de stockage à partir d’un serveur distant. Partez donc sur les performances affichées par Tokyo Tyrant qui, soit dit en passant, sont déjà considérables. Lors d’un bench que j’ai effectué sur le produit, je me suis aperçu que le load average de mon serveur hébergeant Tokyo Tyrant et Tokyo Cabinet était anormalement élevé… Pas à cause du CPU, mais à cause du disque qui ne répondait pas assez vite aux I/O débités par la Tokyo Team… Pensez à bien choisir votre système de fichier dans ce cas (type – EXT3, XFS, … -, journalisé ou non, options de montage, …) et n’hésitez pas à mettre du RAID0, par exemple, pour optimiser les performances en lecture/écriture ou bien à répartir les écritures des différents fichiers physiques (données, ulogs, …) sur différents disques.

Est-il nécessaire de préciser que ce qui vous prendra du temps sur l’accès à une donnée via le réseau c’est… Le réseau ! Hé oui ! Donc dans tous les cas préférez l’utilisation au niveau client (API) de « mget » (multi get), par exemple, en positionnant en paramètre le tableau de clés que vous souhaitez récupérer, plutôt que d’effectuer N fois un « get » à partir du client, donc N accès réseau. « mget » se résoudra, lui, au niveau serveur (Tokyo Tyrant).

Les protocoles
Il est à noter que les protocoles HTTP et Memcached (et donc leurs APIs) sont directement utilisables afin d’accéder à Tokyo Tyrant, pas besoin de modifier le code de l’application pour passer d’un stockage on-memory sur Memcached à un stockage on-file sur Tokyo Tyrant/Tokyo Cabinet, par exemple. A noter que l’intégralité des fonctionnalités de Tokyo Tyrant ne seront donc pas forcément disponibles via le protocole Memcached ou HTTP, comme la concaténation, … Vous pouvez également utiliser le protocole natif binaire pour communiquer avec Tokyo Tyrant, ou bien avec Tokyo Cabinet si vous fonctionnez en « localhost ».

Le requêtage ensembliste
En utilisant l’API Table, vous remarquerez qu’à chaque clé correspond un ensemble d’attributs, pas forcément le même nombre pour chaque clé (ces attributs peuvent être ajoutés à la volée et pas forcément valorisés pour les clés « antérieures »… Ni « postérieures » d’ailleurs). Il n’y a donc pas de schéma figé et chaque attribut peut faire l’objet d’une clause de requête ensembliste de type « WHERE ». Vous pourrez donc récupérer une liste de valeurs correspondant à des conditions sur un attribut et n’avez pas besoin de nommer explicitement la clé ou un pattern de clé afin de récupérer votre objet ou votre liste d’objets (cela n’est possible qu’avec l’API Table). Ce fonctionnement est similaire à celui que l’on peut retrouver sur SimpleDB, par exemple. A noter qu’il est aussi possible de positionner un index sur un attribut (Cf. vidéo de Ilya Grigorik).

Lua
Lua… Lua !!! Un langage de scripting léger et efficace et comme le dit Ilya Grigorik : « C’est un mélange de Ruby et de Javascript… Enfin… Les mauvaises choses des 2 ! ;ob ». Cela explique probablement sa popularité : facile à utiliser, simple, efficace, … que demander de plus ? Il permet, par comparaison avec MySQL, de mettre en place des « user-defined fonctions », à la différence qu’il s’agit d’un langage interprété qui ne provoquera pas le plantage du serveur Tokyo Tyrant sur une erreur ;ob. Il permet de mettre en place des opérations complexes comme par exemple :

  • Renvoyer les données avec un format particulier (JSON, …).
  • Implémenter des fonctionnalités pseudo-atomiques au niveau serveur (c’est à dire atomique vu par le client = un seul appel réseau) afin de reproduire des fonctionnements tels que ceux du composant Set de Redis, un autre système de stockage clé/valeur montant l’intégralité de son dataset en mémoire (il faut tenir compte de ce point quand on choisit Redis au regard du volume de données que l’on doit stocker, mais rien n’empêche de distribuer le dataset sur plusieurs Redis) et assurant la persistance des données en écrivant de manière asynchrone sur le disque (soit suivant un délai, soit suivant un nombre de modifications effectuées sur ledit dataset). Concernant les types de données natifs sous Redis, vous pourrez notamment trouver les « List » qui sont des séquences d’éléments ordonnées et les « Set » (évoqués dans la vidéo) correspondant à une collection non-ordonnée sur laquelle on peut appliquer des opérations de type intersection, union, différence, … avec d’autres « Set ». Pour terminer cette digression permettant de comprendre l’exemple donné au cours de la vidéo, vous pouver consulter la Page de référence des commandes Redis, ainsi que l’Introduction aux types de données Redis. Un exemple/tutoriel très intéressant est également disponible et présente la mise en place d’un clone de Twitter nommé Retwis : A case study: Design and implementation of a simple Twitter clone using only the Redis key-value store as database and PHP.
  • Implémenter une notion de TTL (Time To Live) comme dans Memcached. Cet exemple est basé sur l’utilisation de la Table API, puisqu’il faut un attribut supplémentaire ( « l’expiration time » ) qu’il est commode d’indexer pour des questions de performances (la possibilité d’introduire des index est noter pour cette API).

A noter que ces implémentations, et notamment celle du Set, ne sont probablement pas aussi rapides qu’une fonctionnalité native, mais il est très pratique de pouvoir embarquer de la logique au niveau du serveur.
A noter également la possibilité de démarrer le serveur Tokyo Tyrant en demandant un appel périodique (pc = periodic call) à ces « user-defined fonctions » en background. Pratique pour des opérations de purge, …

MapReduce inside !
On note l’introduction du paradigm MapReduce à l’intérieur de Tokyo Tyrant, en natif, avec la possibilité de développer ses fonctions de Map et de Reduce en Lua.

Réplication
Il est également possible de mettre en place de la réplication master-slave simplement entre 2 serveurs : quel beau couple qu’un master « on-memory » permettant d’optimiser les accès et un slave « on-file » assurant la persistance des données.

Voici les commandes permettant de mettre 2 serveurs en master-slave :

ttserver -port 1978 -ulog ulog-1 -sid 1 casket-1.tch
ttserver -port 1979 -ulog ulog-2 -sid 2 -mhost localhost -mport 1978 -rts 2.rts casket-2.tch

Simple non ?

Conclusion
Tokyo Tyrant / Tokyo Cabinet est un outil de stockage clé/valeur très intéressant, d’une part par ses performances et d’autre part par les possibilités d’évolutions qu’il offre en termes de fonctionnalités et de logique embarquée.

Cependant au delà de l’outil lui-même, il faut se poser la question en amont du modèle que l’on souhaite adopter vis à vis du fonctionnel de son application. Il est évident que si votre application peut s’adapter à un modèle clé/valeur, il est indispensable d’envisager cette possibilité, et c’est une des premières étapes à envisager au niveau de la conception. Je cite un de mes articles concernant le Sharding et optimisation des accès aux données :

Le sharding est une des solutions possible pour l’amélioration des temps de réponse sur ladite source d’éléments. Mais avant d’envisager cette solution, il est intéressant d’envisager d’autres possibilités dans cet ordre :

• le concept du modèle non relationnel, hébergé ou non, en général, puisque de ce choix découlera un autre modèle de fonctionnement,

Le modèle clé/valeur est en effet un boost en termes de performances, si évidemment celui-ci correspond à votre fonctionnel. Cette question est à soulever rapidement et permettra de ne pas partir sur un modèle relationnel trop coûteux et sous exploité par certains types d’application.

Frédéric FAURE

Répondre

 

 

 

Vous pouvez utiliser ces balises HTML

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>