Discussion :

[Bruno]

HC-tree, un dorsal expérimental de base de données haute-concurrence pour SQLite,
il vise à développer un nouveau module de base de données qui améliore SQLite

Le moteur de base de données SQLite est parfois utilisé comme noyau d'un système de base de données client/serveur. Bien qu'il fonctionne de manière fiable dans de tels cas, le module de base de données qu'il utilise pour stocker les structures B-arbre dans son fichier de base de données n'a pas été conçu dans ce cas et peut être amélioré de plusieurs manières. Le projet HC-tree est une tentative de développement d'un nouveau module de base de données qui améliore SQLite

En informatique, un arbre B aussi appelé B-tree est une structure de données en arbre équilibré. Les arbres B sont principalement mis en œuvre dans les mécanismes de gestion de bases de données et de systèmes de fichiers. Ils stockent les données sous une forme triée et permettent une exécution des opérations d'insertion et de suppression en temps toujours logarithmique.

Le principe est de permettre aux nœuds parents de posséder plus de deux nœuds enfants : c'est une généralisation de l’arbre binaire de recherche. Ce principe minimise la taille de l'arbre et réduit le nombre d'opérations d'équilibrage. De plus un arbre B grandit à partir de la racine, contrairement à un arbre binaire de recherche qui croît à partir des feuilles.

SQLite est un moteur de base de données relationnelle léger accessible par le langage SQL. Contrairement aux serveurs de bases de données traditionnels, comme MySQL ou PostgreSQL, sa particularité est de ne pas reproduire le schéma habituel client-serveur, mais d'être directement intégrée aux programmes. L'intégralité de la base de données (déclarations, tables, index et données) est en effet stockée dans un fichier indépendant de la plateforme.

Voici, ci-dessous, les améliorations qu’apporte HC-tree :

Amélioration de la concurrence : le SQLite standard est limité à un seul script simultané. L'utilisation de l'extension begin-concurrent change cela de façon à ce que plusieurs scripts puissent fonctionner simultanément en utilisant le verrouillage optimisé au niveau de la page. Cela améliore quelque peu la concurrence, mais le verrouillage au niveau de la page peut détecter des conflits entre des transactions logiquement indépendantes, et les opérations COMMIT doivent toujours être sérialisées.

Hctree utilise un verrouillage optimisé au niveau des lignes et est conçu pour supporter des dizaines de scripts simultanés fonctionnant à pleine vitesse. Les résultats des tests obtenus à partir du prototype montrent que cela est possible. Tous les tests ont été effectués sur un processeur AMD 5950X à 16 cœurs avec 32G de mémoire et utilisant tmpfs comme système de fichiers. Les fonctions avancées de gestion de la fréquence du CPU du BIOS comme "Core Boost", "AMD Cool & Quiet" et Simultaneous Multi-Threading sont toutes désactivées.

Support de la réplication : SQLite standard supporte l'extension sessions, qui permet au contenu d'une transaction validée d'être sérialisé pour être transmis et appliqué à une seconde base de données.

L'extension de session fournit un mécanisme permettant d'enregistrer les modifications apportées à certaines ou à toutes les rowid des tables d'une base de données SQLite, et de regrouper ces modifications dans un fichier changeset ou patchset qui peut être utilisé ultérieurement pour appliquer le même ensemble de modifications à une autre base de données ayant le même schéma et des données compatibles de départ. Un changeset peut également être inversé et utilisé pour "annuler" une session.

Hc-tree intègre cette extension dans le backend de la base de données, et ajoute la prise en charge de l'application de telles transactions aux bases de données subordonnées dans des configurations leader-follower. Dans ce cas, les transactions reçues d'une base de données leader peuvent être appliquées plus rapidement et avec une plus grande simultanéité que celle avec laquelle elles ont été initialement appliquées à la base de données leader, car aucune validation de transaction n'est requise.

Lorsqu'une transaction doit être validée dans un système de concurrence optimisé, elle doit d'abord être validée. La validation d'une transaction consiste à vérifier que, considérée de concert avec toutes les autres transactions passées et actuelles, la transaction aurait pu être validée dans un système qui sérialise toutes les transactions sans changer le résultat en termes d'état final de la base de données ou de résultats de requête renvoyés à un client. En pratique, il existe deux façons de valider une transaction Hc-tree :

1. Si aucun autre client n'a engagé une transaction dans la base de données depuis l'ouverture, la transaction doit être valide ;
2. Si aucun autre client n'a modifié une entrée ou une plage de B-tree à laquelle la transaction en cours d'exécution a accédé par une plage de requête, alors la transaction est valide.

Par exemple, si l'on considère la base de données suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b TEXT, c TEXT);
    CREATE INDEX i1 ON t1(b);
    INSERT INTO t1 VALUES(1, 'a', 'A');
    INSERT INTO t1 VALUES(2, 'b', 'B');
    INSERT INTO t1 VALUES(3, 'x', 'X');
    INSERT INTO t1 VALUES(4, 'c', 'C');
    INSERT INTO t1 VALUES(5, 'd', 'D');

Et la transaction suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
    BEGIN CONCURRENT;
      SELECT * FROM t1 WHERE (b BETWEEN 'a' AND 'c') AND c!='B';
      INSERT INTO t1 VALUES(6, 'e');
    COMMIT;

Ensuite, pendant l'exécution de la transaction, Hc-tree enregistre que les éléments suivants ont été accédés :

• la plage de clés comprise entre 'a' et 'c', inclusivement, dans l'index B-tree ;
• les clés 1, 2, 4 et 6 de la table B-tree.

Si, lors de la tentative de validation, le client Hc-tree constate que le contenu de la plage de l'index B-tree ou l'une des clés de la table B-tree a été modifié depuis l'ouverture, la validation échoue et la transaction n'est pas validée.

Notons qu'un autre client qui modifie le tuple (2, 'b', 'B') fait échouer la validation, même si la requête SELECT exclut cette ligne. Cela s'explique par le fait que la validation est basée sur les entrées et les plages d'entrées lues à partir de la couche B-tree, et non sur le sous-ensemble de celles réellement utilisées par le moteur de la base de données. S'il n'y avait pas d'index dans le schéma de la base de données, la requête SELECT de l'exemple serait mise en œuvre en utilisant un balayage complet de la table B-tree. Dans ce cas, toute modification d'une ligne de la table B-tree entraînerait l'échec de la validation de la transaction.

Suppression des limitations de taille des bases de données : le SQLite standard utilise des numéros de page de 32 bits. En utilisant la taille de page par défaut de 4KiB, cela conduit à une taille maximale de base de données de 2⁴⁴ octets, ou 16TiB. Hc-tree utilise des numéros de page de 48 bits, permettant des bases de données de 2⁶⁰ octets, ou 1EiB. En gros, un million de TiB.

Ce projet contient un fork du projet SQLite qui a été modifié pour inclure un prototype du dorsal de la base de données Hc-tree. Il peut être construit et utilisé de la même manière que le code de la bibliothèque SQLite. Le prototype est suffisamment avancé pour être utilisé à titre expérimental et pour effectuer des tests de performance multi-threads, mais il est incomplet.

Source : Hc-tree team

Et vous ?

Quel est votre avis sur le sujet ?

Voir aussi :

SQLite 3.40 est disponible, le moteur de base de données léger apporte le support officiel de Wasm, une API de récupération qui pourrait récupérer une partie du contenu d'un fichier de BD corrompu

SQLite n'est pas assez ouvert et a besoin d'être modernisé, se plaint son fondateur, « SQLite est explicitement et sans équivoque "Open Source, pas Open Contribution" »

Il y'aurait plus de mille milliards de bases de données SQLite en utilisation active, faisant du SGBD le composant logiciel le plus largement déployé et utilisé