Voldemort, le gardien de vos recommandations quotidiennes (1/3)

Hadoop permet d’optimiser le temps d’exécution de traitements distribués quand ils sont limités par la bande passante vers les données. Mais, pour cette même raison, son système de fichiers (HDFS) n’est pas conçu pour les accès aléatoires. Si vous recalculez les recommandations pour vos utilisateurs chaque nuit, comment exposer alors à chaque utilisateur les données le concernant? BigData in, BigData out. Dans ce contexte, LinkedIn utilise Voldemort. Cette base de données clef/valeur propose en effet de construire son index en utilisant Hadoop. Nous allons voir ensemble la justification et la mise en place.

BigData out

Quel que soit le domaine de votre métier, il existe des traitements de batchs volumineux. Les résultats peuvent être les n prochains films à recommander à un utilisateur ou encore les statistiques d’un des nombreux scénarios économiques que vous devez évaluer. Fondamentalement, ces deux cas bien distincts se ressemblent cependant. La sortie est une liste potentiellement gigantesque de clefs/valeurs. Vous souhaitez accéder au document associé à une clef. Vous connaissez par avance la clef. Et vous souhaitez disposer de la donnée rapidement. Mais, toutes les mises à jour se font au même moment, une fois par jour. Bref, un scénario courant mais caractérisé par des contraintes très particulières, telle qu’un import massif des résultats en un point unique de la journée.

Hadoop MapReduce est une plateforme, parmi d’autres, permettant de distribuer un traitement. Elle se distingue cependant par son design conçu pour diminuer l’impact de la bande passante, trop limitée, vers les disques durs. Ceci se fait principalement grâce à deux décisions : lire les données séquentiellement et localement. Mais cela a un prix. Contrairement à un système de fichiers classique, HDFS fonctionne avec peu de fichiers (des millions contre des milliards) de grandes tailles (bloc par défaut à 64Mo contre 4Ko). HDFS est conçu pour lire rapidement de larges volumes de données et non pas pour fournir rapidement une donnée précise.

Si vous avez utilisé Hadoop pour le calcul, vos clefs/valeurs sont désormais sur votre cluster. A priori, non pas sous la forme de grands fichiers texte, mais plutôt stockées dans des conteneurs. Historiquement, cela pourraient être des SequenceFiles, plus récemment sans doute des fichiers avro. Si vous souhaitez récupérer le document pour une clef donnée, il faut dans le pire des cas parcourir tous les fichiers dans leur ensemble puisqu’ils n’ont a priori pas d’ordre explicite. C’est loin d’être idéal à la fois pour la latence mais aussi pour le volume de données à lire. Pour éviter un ‘full-scan’, comme dans le monde relationnel, il faut construire un index. Mais comment?

Des solutions insuffisantes

On pourrait rester sur HDFS. Le SequenceFile possède en effet un cousin, le MapFile, qui est trié et possède un index qui sera chargé en mémoire. Et le monde avro possède quelque chose de similaire avec le SortedKeyValueFile. MapReduce peut alors être utilisé pour créer ces fichiers en parallèle et de telle façon que, pour une clef donnée, on sait par avance quel index consulter. Cela va grandement réduire la latence, puisque l’on peut désormais cibler le document, mais cela ne fournit toujours pas suffisamment de garantie. Utilisant un système de fichiers distribué, la partie du fichier à consulter n’est vraisemblablement pas sur la machine ayant demandé l’ouverture du fichier. Cela implique un transfert du trafic de requêtage sur le cluster pour au final interroger des nœuds occupés à faire tourner à ce moment précis des batchs dont le goulot d’étranglement est justement la lecture des données sur le disque. Une solution à écarter, donc.

On pourrait sortir du HDFS. Cela implique de copier l’ensemble des données sur un autre système, que celui-ci soit capable de mettre à jour de façon incrémentale un index distribué et il faudra bien faire attention à ne pas causer un déni de service. Clairement, ces systèmes existent mais sont au final bien compliqués par rapport à ce contexte alors que l’on a vu que l’utilisation du HDFS résolvait une grosse partie du problème. Comme vous avez pu le prévoir, Voldemort va permettre de tirer le meilleur de ces deux mondes.

Voldemort en lecture-seule

Voldemort est une base de données distribuée clef/valeur, parmi d’autres. Elle possède cependant une particularité : une implémentation de son stockage est ‘lecture-seule’. LinkedIn utilise ce système depuis plus de 3 ans en production pour diverses recommandations que vous voyez sans doute tous les jours : les contacts, les jobs et les compétences.

Historiquement, il s’agit d’un clone d’Amazon Dynamo initié par LinkedIn. Voldemort en tire notamment son partitionnement logique des données. Le nombre de partitions n’étant pas lié au nombre de serveurs, la perte d’un nœud ou l’ajout d’un nœud supplémentaire ne nécessite pas une redistribution des clefs. La donnée étant partitionnée, le sharding (pour la distribution de la charge) et la réplication (pour la tolérance aux pannes) sont également gérées. Le 19 mars dernier, la version 1.3 fut publiée. Une des grandes avancées est le support d’avro pour stocker les clefs et les valeurs. En fournissant au préalable le schéma, il est ainsi possible d’avoir un stockage compact, standardisé et interprétable dans de nombreux langages.

Le facteur différenciant est cependant le stockage ‘lecture-seule’. Les fichiers (données et index) partitionnés de la base sont construits sur Hadoop de façon distribuée puis récupérés par les nœuds de Voldemort pour des raisons de performance. L’index sera chargé en mémoire et le cache de l’OS sollicité pour optimiser l’accès aux données souvent demandées.  Ce système permet d’effectuer une mise à jour, ou un retour en arrière, de plusieurs teraoctets conceptuellement en ne changeant qu’un seul lien symbolique. Bien sûr cela a également un coût caché. Ce système est bien conçu pour une mise à jour massive en remplaçant l’ensemble des fichiers utilisés par la base de données. Cette implémentation du stockage ne permet pas de changer une seule clef/valeur indépendamment du reste. C’est bien pour cela que le stockage est nommé ‘lecture-seule’.

C’est une solution extrême répondant au cas d’utilisation décrit précédemment et non pas une solution générique. Il faut donc aussi rester pragmatique. Tout le monde n’est pas LinkedIn et chaque contexte apporte potentiellement sa propre solution puisque les compromis n’ont pas à être les mêmes. Cela dit, l’utilisation de Voldemort en lecture-seule reste une approche intéressante par le choix de ses contraintes mais aussi par la simplicité de son installation et de son exploitation. Les données d’origine étant sur HDFS, elles sont déjà répliquées. Les données sur le nœud ne sont qu’une copie et ne nécessitent pas de stratégie de backup spécifique.

A la suite de cet article, je vous propose de voir la mise en place complète, pas-à-pas. Dans un premier temps, l’installation de Voldemort en lecture seule. Puis finalement, la génération des fichiers (données et index) depuis Hadoop ainsi que leur import. A vous de voir ensuite, si cette solution reste un point de comparaison théorique ou bien une solution que vous ne pouvez plus lâcher.