Une base de données purement fonctionnelle

Le modèle relationnel est né à une époque où l'espace était rare, et fut donc conçu pour minimiser le niveau de redondance des données: il était plus économique de stocker une indirection vers une chaine de caractères que de stocker cette chaine deux fois. Aujourd'hui, cette contrainte d'espace ne tient plus. On achète un Teraoctet pour 100 dollars, la RAM est abondante, et les disques flash aux performances élevées vont bientôt rejoindre le prix des disques durs rotatifs.

Deux limitations fondamentales du stockage ont donc disparu: le coût de la redondance et le coût de la non-localité pour le traitement de structures de données complexes. Il est maintenant possible de concevoir de nouvelles bases de données plus riches et plus sûres.

Update in place is a poison apple. - Jim Gray, Turing Award 1998

Le choix d'une base de données mutables n'est plus optimal. Les bases de données purement fonctionnelles n'existent pas encore, mais je pense que les utilisateurs de bases de données auraient déjà intérêt à envisager le stockage read-only et le versioning manuel.

Que veut-on dire par "base de données mutables"? Il s'agit d'une BDD dans laquelle chaque donnée peut être modifiée à tout moment, et dans laquelle on ne garde pas l'historique de ses modifications. Les modifications sont faites "sur place", de manière destructive.

Que veut-on dire par "base de données purement fonctionnelle"? Il s'agirait d'une BDD dans laquelle chaque structure de donnée serait purement fonctionnelle, c'est-à-dire immuable par défaut et ne ferait référence qu'à des données immuables. Pour prendre une analogie programmatique, cette BDD serait une interface vers des snapshots versionnés. Une sorte de Git!

Vers une implémentation plus adaptée

Les données d'une BDD méritent un traitement différencié en fonction de leurs patterns d'usage. Pourquoi par exemple, chez un grand opérateur téléphonique, devrait-on utiliser le même objet "table" pour référencer les monnaies, gérer la liste des clients et la liste des appels? Examinons leurs particularités. A partir de ces trois exemples simplifiés nous allons inférer plusieurs mécanismes fondamentaux d'une base de données purement fonctionnelle.

La liste de référence des monnaies est peu volumineuse. Elle est mise à jour quelques fois par an, tout au plus. La liste des clients de l'opérateur est moyennement volumineuse. Elle est mise à jour quotidiennement, avec quelques ajouts, suppressions et modifications aléatoires. La liste des appels est très volumineuse. Elle est mise à jour quotidiennement, mais seulement en insertion.

Nous avons donc au moins trois cas d'usage très différents. Or dans une BDD classique, ces trois données sont stockées de la même manière, c'est-à-dire sous la forme de listes mutables et indexées. Beaucoup d'effort a été investi pour améliorer les performances de ces tables avec le matériel donné, mais les solutions proposées sont encore très génériques.

Revenons à nos trois données. Il est possible de les implémenter autrement, en faisant appel à trois types d'objets:

• Des listes immuables (de type homogène, et implémentées par exemple par des hashtables sur la clef primaire)
• Des deltas sur ces listes
• Quelques métadonnées peu volumineuses qui serviront à articuler l'ensemble.

La table des monnaies est l'exemple typique d'une liste simple et immuable. La liste d'aujourd'hui s'appelle la 'v1'. Si demain une union monétaire est créée en Amérique du sud, nous créerons une copie modifiée qui s'appellera la 'v2'. Pour des raisons de performance, la v1 et la v2 devront être copiées intégralement sur tous les noeuds de la base de données. La performance en update de cette implémentation est médiocre, mais toutes les lectures pourront être faites sans aucun mécanisme de synchronisation.

La table des clients est un peu plus volatile. Tous les jours quelques clients arrivent ou s'en vont, et quelques clients existants peuvent modifier leur adresse postale. Nous pouvons stocker la liste des clients comme une liste immuable 'v1', accompagnée par une séquence chronologique de deltas. D'ici à quelques mois, l'accumulation des deltas commencera à affecter la vitesse de lecture: il faudra alors matérialiser la liste, la nommer 'v287' et archiver la v1. Dans le cas d'une machine seule, nous retrouvons presque exactement la manière dont Git stocke son historique. Dans le cas d'un cluster, il est bien sûr préférable de partitionner/sharder cette liste sur tous les nœuds. Selon quelle politique va-t-on vouloir archiver une version, la compresser ou la supprimer? Et selon quelles modalités? Chaque utilisateur doit prendre cette décision en fonction de ses besoins métier. Il est agréable, en tout cas, de remarquer que le Data Lifecycle Management est offert sur un plateau par les BDD fonctionnelles.

La table des appels téléphoniques est différente. Chaque jour elle reçoit des milliers de nouvelles lignes, lesquelles sont parfaitement indépendantes des lignes antérieures. Cette liste est segmentable par journée, et chacun des segments quotidiens est une liste immuable. Nous devrions en plus partitionner chaque segment de manière à coller à la liste des clients: l'ID du client devient alors la clef de partitionnement des appels téléphoniques.

En résumé, à travers ces mécanismes de mise à jour, on accepte de consommer un peu plus d'espace disque, et de réduire la localité des données (car une nouvelle version ne sera probablement pas écrite à côté de l'ancienne). Tout cela pour garder une information plus riche. Remarquez bien que ces trois idées de versioning s'appliquent aussi bien à l'implémentation d'une nouvelle base de données qu'à une implémentation manuelle, basée sur les outils d'aujourd'hui.

Conséquences

Voilà pour les bases. Observons maintenant les conséquences positives de ces nouveaux choix d'implémentation.

Il devient possible par exemple:

• d'attribuer un identifiant unique à une version complète de la BDD, donc d'exécuter des requêtes de lecture sur une version du passé
• d'effectuer un rollback à tout moment, en reprenant une ancienne version. Pas besoin d'attendre des heures pour recharger!
• de paralléliser le requêtage à l'infini (car les listes immuables et les deltas sont triviaux à copier)
• de hasher cryptographiquement le contenu (à la Git), pour un usage légal ou contractuel
• de connaitre la séquence des processus qui ont fait évoluer la base ou une ligne en particulier
• de diminuer le coût du backup et du Plan de Reprise d'Activité. Réaliser trois copies vers des disques sur étagère coûte peu (car les deltas sont copiables via des écritures non-aléatoires, donc rapides, et sans consommer de CPU)
• de cacher le résultat de toute sorte de traitements, à la manière de vues matérialisées (filtrage, agrégation..)
• de stocker dans la même BDD des objets classiques relationnels, et des objets plus variés (key-value store..)

En l'absence d' "état global", nous offrons aux processus d'alimentation et d'interrogation de la BDD tous les bénéfices de la programmation purement fonctionnelle. Ces processus deviennent référentiellement transparents (donc sans effet de bord), d'où une meilleure lisibilité pour les équipes de développement et de maintenance, et une diminution du risque d'erreur. De plus, nous avons la garantie que l'ordre d'exécution des processus n'a plus aucune importance. La qualité de transparence référentielle nous aide aussi à implémenter proprement le pattern Command-Query Separation (CQS), qui conseille de séparer les processus de requêtage des processus d'écriture. Les nombreux "lecteurs" opèrent sur des données immuables, éventuellement disséminées dans un cluster, alors que le processus "modificateur" agit sur les données de référence pour leurs ajouter des deltas.

Quelles sont les contreparties? Il devient plus couteux de réaliser de nombreuses modifications aléatoires sur une grande table. Une BDD purement fonctionnelle ne serait donc pas adaptée à la table d'inventaire d'Amazon, même si l'usage de disques SSD permettrait d'annuler une grande partie de la dégradation de performance.

Remarquez encore une fois qu'une grande partie de ces bénéfices/contreparties s'applique telle quelle dans le cas d'un versioning manuel.

Conclusion

Le choix historique d'implémenter les BDD à l'aide de données mutables n'est plus optimal. Le besoin de protéger les mises à jour dans un environnement concurrent nuit à la scalabilité, et l'absence d'historique et de points de retour rend toute manipulation périlleuse. Une base de données purement fonctionnelle serait intrinsèquement plus sûre, et offrirait une meilleure scalabilité pour de nombreuses applications. En outre, ses besoins seraient tout à fait compatibles avec les bénéfices des disques flash. Mon pari est qu'une telle base de données va réellement exister dans les années à venir. Le monde académique en parle depuis les années 80; voir notamment la thèse de Phil Trinder qui avait déjà identifié les conséquences de la transparence référentielle dans les bases de données, puis ouvert la voie vers le requêtage monadique (LINQ) avec ses collègues de l'université de Glasgow. Il ne lui manquait que du matériel plus performant. Aujourd'hui, la startup RethinkDB et la base in-memory HANA utilisent déjà une partie de cette technologie et atteignent de belles performances. En attendant l'arrivée et la maturation de ces nouveaux outils, il est déjà possible d'enrichir manuellement nos BDD pour bénéficier, en partie, de leurs avantages.

Bibliographie

http://www-03.ibm.com/ibm/history/exhibits/storage/storage_3330.html (Histoire du disque dur IBM 3330) http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-TN-1997-018.pdf (Génèse du SQL) www.cs.ox.ac.uk/files/3404/PRG82.pdf: Phil Trinder "A functional database" http://www.quora.com/What-would-be-the-main-advantages-of-a-(purely-)-functional-database http://nathanmarz.com/blog/how-to-beat-the-cap-theorem.html http://research.microsoft.com/~gray/papers/theTransactionConcept.pdf (Implémentations d'une transaction)