Le traitement de très grands graphes a toujours été et reste un challenge. Pourtant, les avancées récentes des technologies Big Data rendent cette tâche plus aisée. Tapad, startup basée à NYC, se concentre sur la mise à disposition de contenu cross-device, et fait du traitement de graphes le coeur de son business modèle. Les technologies Big Data leur permettent de prendre en charge des terabytes de données.
Les réseaux sociaux comme Facebook ou Twitter manipulent des données qui s'accordent naturellement avec une représentation sous forme de graphe. Mais les graphes peuvent être aussi utilisés pour représenter des données pour lesquelles le rapprochement est moins évident, comme dans le cas du graphe de devices de Tapad. Le co-fondateur et CTO de Tapad, Dag Liodden, décrit pourquoi l'utilisation d'une représentation des devices sous forme de graphes est adaptée à leur cas :
Tapad adopte une approche orientée graphe pour la modélisation des relations entre devices. Les identifiants anonymes (comme les identifiants de cookies) sont représentés sous forme de noeuds dans notre graphe des Devices. Nous maintenons en plus sur ceux-ci des informations marketing. Les arêtes entre les noeuds sont associées à un score ou un poids en utilisant une combinaison de données déterministes et de modèles statistiques probabilistes ainsi que des techniques de machine learning. Le concept de "device" est défini par un noeud (un device) de départ, par exemple le cookie ID d'un browser, et les collections de noeuds accessibles depuis ce point de départ en fonction d'un ensemble personnalisable de contraintes sur les arêtes (par exemple les cookies ID d'une tablette et d'une TV connectée). Disposer d'une vraie structure de graphe, et pas simplement des informations aggrégées sur un noeud unique, nous donne la flexibilité pour équilibrer exactitude et scaling dynamique, tout en ouvrant aussi la possibilité d'ajouter de nouveaux modèles d'inférence.
Il faut utiliser le bon outil pour faire un bon travail ; ceci est valable pour le Graph Processing. Comme le mentionne Dag Liodden, il n'est pas nécessaire d'avoir recours aux technologies Big Data pour les graphes qui peuvent être pris en charge par les moyens plus traditionnels :
Pour moi, "Big Data" correspond à la limite où il devient impossible d'utiliser un petit ensemble d'outils génériques, prêts à l'emploi, pour stocker et analyser ses données. À ce moment, vous aurez plutôt à accommoder différentes technologies pour répondre à des cas d'utilisation spécifiques. Cette limite ne cesse de changer année après année, tandis que les solutions logicielles et matérielles évoluent et gagnent en maturité, tout comme croissent les volumes de données à traiter et le niveau de sophistication des analyses à réaliser.
Pour Facebook, cette limite est de l'ordre du petabyte, comme détaillé lors de leur présentation à la conférence ACM SIGMOD 2013 à NYC. Pour Tapad et leurs graphes, le volume de données est plus restreint mais reste impossible à traiter avec les méthodes traditionnelles :
Le graphe US a actuellement à peu près 1.1 milliard de noeuds, qui correspondent aux téléphones mobiles, tablettes, laptops, consoles de jeux et télévisions. Certains de ces noeuds sont éphémères, par exemple pour le cas d'un navigateur internet avec des cookies non-persistants, et donc auront peu de données et pas d'arêtes. Les noeuds non-éphémères ont chacun à peu près 5 arêtes et 500 éléments d'information associés, tels que les segments comportementaux. Le graphe de données "live" pèse plusieurs TB et nous effectuons dessus des opérations de lecture / écriture plusieurs centaines de fois par seconde sur plusieurs data centers. Les mises à jour sur le graphe sont répliquées géographiquement et chaque data center est actuellement au service de serveurs équipés de 20 TB de stockage Flash SSD et 2 TB de RAM.
Nous avons assisté au cours des dernières années une forte hausse du nombre de technologies utilisées pour traiter les graphes de taille importante. L'année 2013 en particulier a vu apparaître plusieurs nouveautés dans cet écosystème. Il y a deux classes de systèmes à considérer :
- Les bases graphes pour les tâches OLTP pour les accès rapides, à faible latence, à de petites portions de données du graphe
- Les moteurs de traitement de graphes pour les tâches OLAP permettant de traiter en batch de grosses portions d'un graphe
La liste des bases graphes est déjà très longue, mais plusieurs projets ont émergé et se sont différenciés récemment. Neo4j est une des plus anciennes et des plus matures des bases graphes mais souffre encore de problèmes de scalabilité, étant donné qu'elle ne supporte pas encore le sharding. Une autre base, Titan, bien qu'encore jeune, a beaucoup gagné en popularité en 2013. Étant une base de données agnostique au backend, elle peut s'appuyer sur les architectures scalables de HBase ou de Cassandra et utilise des représentations internes optimisées des arêtes et des noeuds pour permettre de prendre en charge des milliards de noeuds, comme le rapporte ce billet de blog de 2013.
Mais il n'est pas obligatoire d'utiliser des bases spécifiquement graphe. Les solutions NoSQL scalables et plus génériques peuvent apporter une bonne solution au problème. Apache Accumulo, une technologie basée sur BigTable de Google et rendue open-source en 2011, est un exemple de base générique qui peut prendre en charge de façon efficace le stockage des graphes à grande échelle. Ses enregistrements sont flexibles et permettent de stocker des graphes avec des noeuds typés et des poids. D'après ce rapport technique publié en 2013, cette technologie est actuellement utilisée par la NSA. Cassandra et Aerospike sont d'autres exemples de bases qui, avec un modèle de données adapté, peuvent modéliser de façon efficace un graphe avec des noeuds, des arêtes et des poids. Facebook a aussi construit sa propre solution basée sur MySQL et Memcached avec un système appelé Tao, utilisé pour exposer le graphe social aux utilisateurs. D'après Dag, Tapad adopte la même philosophie pour la conception de son graphe de devices :
Le graphe "live" vit dans une base de données clef-valeur pour permettre des parcours et mises à jour rapides. Nous réalisons régulièrement des snapshots du graphe dans HDFS, où celui-ci peut être récupéré pour des traitements graphes plus avancés et pour y ajouter des informations venant d'autres flux de données. Les résultats sont ensuite réinjectés dans le graphe "live". Il y a des avantages à utiliser une base de données spécifiquement graphe mais notre installation actuelle, avec d'une part des parcours courts et extrêmement rapides du store clef-valeur, et d'autre part des parcours et analyses lents mais très flexibles sur Hadoop, nous convient bien, du moins pour l'instant.
Même avec un graphe stocké dans une base de données, les opérations à réaliser à grande échelle seront certainement limitées à des "lookups" et des petits parcours. Pour des analyses complexes sur des portions plus importantes d'un graphe, il est nécessaire de recourir à des frameworks de traitements par batch distribués. Pour de meilleures performances, le framework GraphLab utilise un modèle Message Passing Interface (MPI) et des données dans HDFS, pour le scaling et l'exécution d'algorithmes complexes. Les frameworks plus récents comme Apache Giraph et Apache Hama s'appuient sur le paradigme Bulk Synchronous Parallel (BSP), popularisé par le projet Pregel de Google. Les récentes additions à l'écosystème sont le projet GraphX, qui s'exécute au dessus de Spark et qui a été dévoilé en 2013, ainsi que Faunus, qui utilise Hadoop pour l'exécution de jobs MapReduce qui traitent des graphes dans une base Titan. Tapad utilise ces nouvelles technologies afin de traiter leur graphe de données offline. D'après Dag :
Actuellement, notre framework principal pour le traitement des graphes est Apache Giraph, mais nous expérimentons aussi avec Spark GraphX et Graphlab. Tous ces frameworks sont relativement jeunes, la courbe d'apprentissage est plutôt raide et chaque solution a ses avantages, ses inconvénients, ses précautions à prendre. Par exemple, Giraph et GraphX sont pratiques car ils s'intègrent bien à notre infrastructure Hadoop, mais Graphlab est très attrayant de par ses performances.
Quelques projets essaient de fournir un framework unifié pour répondre à la fois à des requêtes OLTP et à des requêtes OLAP. Dendrite, de Lab41, est un exemple de projet qui met à profit GraphLab au dessus de Titan pour le stockage et le traitement, et AngularJS pour la visualisation. C'est un projet assez jeune, révélé début 2014, donc la réaction de la communauté est encore limitée. Mais le fait qu'il essaie de couvrir tous les cas d'utilisation devrait aider à son adoption.