Format reftable de Git : guide pour les débutants

Jusqu'à récemment, Git ne pouvait stocker des références qu'au format « fichiers ». Avec la version 2.45.0 de Git, Git peut désormais stocker des références au format « reftable ». Ce nouveau format binaire est un peu plus complexe, mais c'est précisément cette complexité qui lui permet de corriger plusieurs lacunes du format « fichiers ». Les objectifs du format « reftable » sont les suivants :

• Rendre la recherche d'une référence unique et l'itération à travers des plages de références aussi efficaces et rapides que possible.
• Prendre en charge des lectures cohérentes des références afin que Git ne lise jamais un état intermédiaire lorsqu'une mise à jour de plusieurs références n'a été appliquée que partiellement.
• Prendre en charge des écritures atomiques de sorte que la mise à jour de plusieurs références peut être effectuée comme une opération tout ou rien.
• Stocker efficacement des références et des journaux de référence (« reflog »).

Dans cet article, nous allons examiner le format « reftable » pour comprendre son fonctionnement.

Stockage des références dans Git

Avant d'entrer dans les détails, récapitulons rapidement la façon dont Git stockait les références jusqu'à présent. Si le sujet vous est familier, vous pouvez passer cette section.

Un dépôt Git contient deux structures de données importantes :

• Les objets, qui contiennent les données réelles de votre dépôt. Ils incluent les validations (« commits »), la structure d'arborescence des répertoires (« tree ») et les blobs qui contiennent votre code source. Les objets sont organisés de manière à ce qu'ils pointent les uns vers les autres, formant ainsi un graphe des objets. En outre, chaque objet est associé à un identifiant unique, appelé ID d'objet.

• Les références, telles que les branches et les étiquettes (« tags »). Ces pointeurs sur des objets du graphe vous permettent de donner des noms à des objets qui sont plus faciles à mémoriser et de suivre les différentes étapes et directions de votre historique de développement. Par exemple, un dépôt peut contenir une branche main : il s'agit d'une référence nommée refs/heads/main qui pointe vers une validation spécifique.

Les références sont stockées dans la base de données des références. Jusqu'à la version 2.45.0 de Git, le format « fichiers » constituait le seul format de base de données disponible. Ce format stocke chaque référence en tant que fichier normal contenant l'un des éléments suivants :

• Une référence standard qui contient l'ID d'objet de la validation vers laquelle elle pointe.
• Une référence symbolique qui contient le nom d'une autre référence, de la même manière qu'un lien symbolique pointe vers un autre fichier.

Ces références sont régulièrement empaquetées dans un seul fichier packed-refs afin de faciliter les recherches.

Les exemples suivants illustrent le fonctionnement du format « fichiers » :

$ git init .
$ git commit --allow-empty --message "Initial commit"
[main (root-commit) 6917c17] Initial commit

# HEAD is a symbolic reference pointing to refs/heads/main.
$ cat .git/HEAD
ref: refs/heads/main

# refs/heads/main is a regular reference pointing to a commit.
$ cat .git/refs/heads/main
6917c178cfc3c50215a82cf959204e9934af24c8

# git-pack-refs(1) packs these references into the packed-refs file.
$ git pack-refs --all
$ cat .git/packed-refs
# pack-refs with: peeled fully-peeled sorted
6917c178cfc3c50215a82cf959204e9934af24c8 refs/heads/main

Vue d'ensemble de la structure « reftable »

Si vous avez installé la version 2.45.0 de Git ou une version plus récente, vous pouvez créer un dépôt au format « reftable » en utilisant l'option --ref-format=reftable :

$ git init --ref-format=reftable .
Initialized empty Git repository in /tmp/repo/.git/
$ git rev-parse --show-ref-format
reftable

# Irrelevant files have been removed for ease of understanding.
$ tree .git
.git
├── config
├── HEAD
├── index
├── objects
├── refs
│   └── heads
└── reftable
	├── 0x000000000001-0x000000000002-40a482a9.ref
	└── tables.list

4 directories, 6 files

Regardez la configuration du dépôt. Remarquez tout d'abord sa clé de configuration extension.refstorage :

$ cat .git/config
[core]
    repositoryformatversion = 1
    filemode = true
    bare = false
    logallrefupdates = true
[extensions]
    refstorage = reftable

Cette configuration indique à Git que le dépôt a été initialisé avec le format « reftable » et que Git doit utiliser le backend « reftable » pour y accéder.

Curieusement, le dépôt contient encore des fichiers qui semblent utilisés par le backend « fichiers » :

• HEAD est une référence symbolique dans Git qui indique généralement la branche sur laquelle vous travaillez actuellement. Bien que le format « reftable » n'utilise pas HEAD, la présence de cette référence est nécessaire pour qu'un répertoire soit reconnu comme un dépôt Git par les clients Git. Par conséquent, lorsque vous utilisez le format « reftable », HEAD est juste une entité fictive et temporaire dont le contenu est ref: refs/heads/.invalid.

• refs/head est un fichier dont le contenu est : this repository uses the reftable format. Les clients Git qui ne connaissent pas le format « reftable » s'attendent généralement à ce que le chemin d'accès soit un répertoire. Par conséquent, la création de ce chemin d'accès en tant que fichier entraîne intentionnellement l'échec des anciens clients Git s'ils tentent d'accéder au dépôt par le biais du backend « fichiers ».

Les références réelles sont stockées dans le répertoire reftable/ :

$ tree .git/reftable
.git/reftable/
├── 0x000000000001-0x000000000001-794bd722.ref
└── tables.list

$ cat .git/reftable/tables.list
0x000000000001-0x000000000001-794bd722.ref

Il y a ici deux fichiers :

• 0x000000000001-0x000000000001-794bd722.ref est une table contenant des références et des données de reflog dans un format binaire.

• tables.list est, comme son nom l'indique, une liste de tables. Dans l'état actuel du dépôt, le fichier contient une seule ligne, qui est le nom de la table. Ce fichier suit l'ensemble actuel des tables actives dans la base de données « reftable ». Il est mis à jour chaque fois que de nouvelles tables sont ajoutées au dépôt.

La mise à jour d'une référence crée une nouvelle table :

$ git commit --allow-empty --message "Initial commit"
[main (root-commit) 1472a58] Initial commit

$ tree .git/reftable
.git/reftable/
├── 0x000000000001-0x000000000002-eb87d12b.ref
└── tables.list

$ cat .git/reftable/tables.list
0x000000000001-0x000000000002-eb87d12b.ref

Comme vous pouvez le constater, la table précédente a été remplacée par une nouvelle. En outre, le fichier tables.list a été mis à jour pour contenir la nouvelle table.

Structure d'une table

Comme mentionné précédemment, les données réelles de la base de données des références sont contenues dans des tables. Pour faire simple, une table se divise en plusieurs sections :

• L'en-tête contient des métadonnées sur la table. En plus d'autres informations, il inclut la version du format, la taille des blocs de données et la fonction de hachage utilisée par le dépôt (par exemple, SHA1 ou SHA256).
• La section « ref » contient vos références. Ces enregistrements ont une clé identique au nom de la référence et pointent soit vers un ID d'objet pour les références standards, soit vers une autre référence pour les références symboliques.
• La section « obj » contient la correspondance inverse entre les ID d'objet et les références qui pointent vers eux. Celle-ci permet à Git de rechercher efficacement les références qui pointent vers un ID d'objet spécifique.
• La section « log » contient vos éléments reflog. Ces enregistrements ont une clé identique au nom de la référence, plus un index qui représente le numéro de l'élément du journal. Ils contiennent en outre les anciens et nouveaux ID d'objet, ainsi que le message pour cet élément reflog.
• Le « footer » contient des offsets pour les différentes sections.

Chaque type de section est structuré de manière similaire. Les sections contiennent un ensemble d'enregistrements qui sont classés en fonction de la clé de chaque enregistrement. Par exemple, lorsque vous avez ces deux enregistrements de références : refs/heads/aaaaa et refs/heads/bbb, vous avez deux enregistrements de références dont les noms de référence sont les clés respectives, et refs/heads/aaaaa vient avant refs/heads/bbb.

Chaque section est par ailleurs divisée en blocs d'une longueur fixe. La longueur d'un bloc est encodée dans l'en-tête et remplit deux fonctions :

• En se basant sur le début de la section ainsi que la taille des blocs de données, le processus qui lit les tables sait implicitement où chacun des blocs commence. Git peut ainsi facilement effectuer une recherche au milieu d'une section sans lire les blocs précédents, ce qui permet d'effectuer des recherches par dichotomie sur des blocs pour accélérer la recherche d'enregistrements.
• Elle permet au processus qui lit les tables de savoir combien de données lire sur le disque à la fois. Par conséquent, la taille des blocs de données est par défaut définie à 4 KiB, ce qui correspond à la taille de secteur la plus courante pour les disques durs. La taille maximale des blocs de données est de 16 Mo.

Intéressons-nous à une section « ref » : elle ressemble à peu près au graphique suivant. Notez comment ses enregistrements sont ordonnés lexicographiquement à l'intérieur des blocs, mais aussi entre différents blocs.

Maintenant que vous disposez de ces informations, vous pouvez localiser un enregistrement en suivant les étapes suivantes :

1. Effectuez une recherche par dichotomie sur les blocs en regardant les clés de leurs premiers enregistrements respectifs, ce qui permet d'identifier le bloc qui doit contenir l'enregistrement.

2. Effectuez une recherche linéaire sur les enregistrements de ce bloc.

Ces deux étapes sont encore quelque peu inefficaces. S'il y a beaucoup de blocs, vous devrez peut-être effectuer une lecture logarithmique d'un bon nombre d'entre eux au cours de la recherche par dichotomie pour trouver celui que vous recherchez. Et lorsque les blocs contiennent de nombreux enregistrements, une recherche linéaire doit potentiellement tous les lire.

Le format « reftable » intègre des mécanismes supplémentaires pour résoudre ces problèmes de performance. Nous les mentionnerons dans les prochaines sections.

Compression de préfixe

Comme vous l'avez peut-être remarqué, toutes les clés d'enregistrement partagent le même préfixe refs/. C'est une norme établie dans Git :

• Toutes les branches commencent par refs/heads/.
• Toutes les étiquettes (« tags ») commencent par refs/tags/.

Par conséquent, il est très probable que les enregistrements suivants partagent une partie importante du préfixe de leur clé. C'est une bonne occasion d'économiser de l'espace de stockage précieux. Comme nous savons que la plupart des clés partagent un préfixe commun, il est logique d'utiliser ce dernier à des fins d'optimisation.

Celle-ci passe par la compression de préfixe. Chaque enregistrement encode une longueur de préfixe qui indique au processus qui lit les tables le nombre d'octets à réutiliser à partir de la clé de l'enregistrement précédent. Si vous avez deux enregistrements, refs/heads/a et refs/heads/b, ce dernier peut être encodé en spécifiant une longueur de préfixe de 11, puis en stockant uniquement le suffixe b. Le processus qui lit les tables prendra alors les 11 premiers octets de refs/heads/a, c'est-à-dire refs/heads/, et y ajoutera le suffixe b.

« Restart points »

Comme expliqué précédemment et d'après vos connaissances actuelles du format « reftable », une recherche linéaire constitue la meilleure façon de chercher une référence dans un bloc, car la longueur des enregistrements n'est pas fixe. Il est donc impossible de savoir où les enregistrements devraient commencer sans parcourir l'intégralité du bloc depuis le début. En outre, même si les enregistrements étaient de longueur fixe, il ne serait pas possible de rechercher au milieu d'un bloc, car la compression de préfixe nous oblige également à lire les enregistrements précédents.

Une recherche linéaire serait assez inefficace, dans la mesure où les blocs peuvent contenir des centaines, voire des milliers d'enregistrements. Pour résoudre ce problème, le format « reftable » encode des « restart points » dans chaque bloc. Les « restart points » sont des enregistrements non compressés où la compression de préfixe est réinitialisée. Par conséquent, les enregistrements des « restart points » contiennent toujours leur clé complète. Il devient donc possible de rechercher et de lire directement l'enregistrement, sans avoir à lire les enregistrements précédents. Ces « restart points » sont répertoriés dans le footer de chaque bloc.

Grâce à ces informations, vous pouvez maintenant éviter d'effectuer une recherche linéaire sur le bloc. Effectuez plutôt une recherche par dichotomie sur les « restart points » en cherchant le premier « restart point » dont la clé est lexicographiquement supérieure à la clé recherchée. Il s'ensuit que l'enregistrement que vous recherchez doit être situé dans la section s'étendant entre le « restart point » précédent et celui identifié.

La procédure initiale pour rechercher un enregistrement (recherche par dichotomie du bloc, recherche linéaire de l'enregistrement) est donc la suivante :

1. Effectuez une recherche par dichotomie sur les blocs, pour identifier celui qui doit contenir l'enregistrement.

2. Effectuez une recherche par dichotomie sur les « restart points », en identifiant la sous-section du bloc qui doit contenir l'enregistrement.

3. Effectuez une recherche linéaire sur les enregistrements de cette sous-section.

Index

Bien que la recherche d'enregistrements à l'intérieur d'un bloc soit désormais raisonnablement efficace, ce n'est pas le cas pour l'identification du bloc spécifique. Une recherche par dichotomie peut être relativement performante sur quelques blocs, mais les dépôts contenant des millions de références peuvent comporter des centaines, voire des milliers de blocs. En l'absence d'une structure de données supplémentaire visant à minimiser les accès au disque, chaque recherche de bloc pourrait entraîner en moyenne un nombre important d'accès au disque.

Pour éviter cette situation, chaque section peut être suivie d'une section d'indexation qui fournit un moyen efficace de rechercher un bloc. Chaque enregistrement d'index contient les informations suivantes :

• L'emplacement du bloc qu'il indexe.
• La clé du dernier enregistrement du bloc qu'il indexe.

Pour trois blocs ou moins, une recherche par dichotomie nécessite toujours, au plus, deux lectures de disque pour trouver le bloc cible souhaité. Le nombre de lectures est le même pour un index : une pour lire l'index et une pour lire le bloc souhaité. Par conséquent, les index ne sont écrits que lorsqu'ils évitent de fait plusieurs lectures, ce qui est le cas lorsque quatre blocs ou plus sont indexés.

La question se pose alors de savoir ce qu'il se passe lorsque l'index lui-même devient si grand qu'il s'étend sur plusieurs blocs. Vous l'avez peut-être deviné : nous écrivons un nouvel index qui indexe l'index. Ces index à plusieurs niveaux ne deviennent vraiment nécessaires que lorsque vos dépôts contiennent des centaines de milliers de références.

À l'aide de ces index, vous pouvez désormais accélérer la recherche d'enregistrements :

1. Déterminez s'il existe un index en consultant le footer de la table.
   • Si c'est le cas, effectuez une recherche par dichotomie dans l'index pour trouver le bloc souhaité. Ce bloc peut pointer vers un bloc d'index, auquel cas il vous faut répéter l'opération jusqu'à atteindre un enregistrement du type souhaité.
   • Dans le cas contraire, effectuez une recherche par dichotomie dans les blocs comme auparavant.
2. Effectuez une recherche par dichotomie sur les « restart points » pour identifier la sous-section du bloc qui doit contenir l'enregistrement.
3. Effectuez une recherche linéaire sur les enregistrements de cette sous-section.

Tables multiples

Jusqu'à présent, nous n'avons discuté que de la façon de lire une table unique. Comme l'indique le nom tables.list, votre base de données « reftable » peut contenir une liste de tables.

Chaque fois que vous mettez à jour une référence dans votre dépôt, une nouvelle table est créée et ajoutée à tables.list. Vous obtiendrez donc plusieurs tables, comme suit :

$ tree .git/reftable/
.git/reftable/
├── 0x000000000001-0x000000000007-8dcd8a77.ref
├── 0x000000000008-0x000000000008-30e0f6f6.ref
└── tables.list

$ cat .git/reftable/tables.list
0x000000000001-0x000000000007-8dcd8a77.ref
0x000000000008-0x000000000008-30e0f6f6.ref

La lecture de l'état réel d'un dépôt nous oblige à fusionner ces multiples tables en une seule table virtuelle.

Vous vous demandez peut-être comment le format « reftable » connaît la valeur la plus récente d'une référence donnée, si une table est créée pour chaque mise à jour de référence et que la même référence est mise à jour plusieurs fois. Intuitivement, on pourrait supposer que la valeur serait celle de la table la plus récente contenant la référence.

En réalité, chaque enregistrement a un index de mise à jour qui encode la « priorisation » d'un enregistrement. Par exemple, s'il existe deux enregistrements pour le même nom de référence, celui qui a l'index de mise à jour le plus élevé remplace celui qui a l'index de mise à jour le plus bas.

Ces index de mise à jour sont visibles dans la structure de fichiers ci-dessus. Les longues chaînes hexagonales (par exemple 0x000000000001) sont les index de mise à jour. L'index de mise à jour minimum contenu dans la table se trouve dans la partie gauche de son nom de fichier et l'index de mise à jour maximum dans la partie droite.

Le merge des tables se fait ensuite via une file d'attente de priorisation qui est triée par clé d’enregistrement ainsi que son index de mise à jour. Imaginez que vous voulez parcourir tous les enregistrements de références. Vous devez suivre les étapes suivantes :

1. Pour chaque table, ajoutez son premier enregistrement à la file d'attente de priorisation.

2. Récupérez et retirez de la file d'attente l'enregistrement en tête de la file. Comme la file d'attente est triée par index de mise à jour, cet enregistrement doit être la version la plus récente. Ajoutez l'enregistrement suivant de la table de cet enregistrement à la file d'attente de priorisation.

3. Retirez tous les enregistrements de la file d'attente qui ont la même clé que l’enregistrement récupéré. Ces enregistrements sont dépassés et ne seront pas utilisés. Pour chaque table pour laquelle vous supprimez des enregistrements, ajoutez l'enregistrement suivant à la file d'attente de priorisation.

Vous pouvez maintenant répéter les étapes ci-dessus pour lire les enregistrements pour d'autres clés.

Les tables peuvent contenir des enregistrements spéciaux « tombstone » qui marquent un enregistrement supprimé. Vous pouvez ainsi supprimer des enregistrements sans avoir à réécrire toutes les tables afin qu'elles ne contiennent plus ces enregistrements.

Compactage automatique

La file d'attente de priorisation a beau être un concept simple, elle ne parviendrait pas à fusionner efficacement des centaines de tables, ni même des dizaines. S'il est vrai que chaque mise à jour de vos références ajoute une nouvelle table à votre fichier tables.list, ce n'est pas tout.

Le compactage automatique entre ici en scène : lorsqu'une nouvelle table a été ajoutée à la liste des tables, le backend « reftable » vérifie si certaines des tables doivent être fusionnées. Ce processus utilise une méthode simple : nous vérifions que les tailles de fichiers de la liste des tables forment une séquence géométrique. Chaque table n doit être au moins deux fois plus grande que la table suivante la plus récente n + 1. Si cette séquence géométrique n'est pas respectée, le backend compacte les tables afin de restaurer la séquence géométrique.

Ce processus aboutit à des structures de ce type :

$ du --apparent-size .git/reftable/*
429    .git/reftable/0x000000000001-0x00000000bd7c-d9819000.ref
101    .git/reftable/0x00000000bd7d-0x00000000c5ac-c34b88a4.ref
32    .git/reftable/0x00000000c5ad-0x00000000cc6c-60391f53.ref
8    .git/reftable/0x00000000cc6d-0x00000000cdc1-61c30db1.ref
3    .git/reftable/0x00000000cdc2-0x00000000ce67-d9b55a96.ref
1    .git/reftable/0x00000000ce68-0x00000000ce6b-44721696.ref
1    .git/reftable/tables.list

Notez que la propriété size(n) > size(n+1) * 2 est respectée pour chaque table.

L'une des conséquences du compactage automatique est la maintenance automatique du backend « reftable ». Il n'est plus nécessaire d'exécuter git pack-refs dans un dépôt.

Vous souhaitez en savoir plus ?

À présent, le fonctionnement du nouveau format « reftable » ne devrait plus avoir de secret pour vous. Si vous souhaitez approfondir vos connaissances, vous pouvez consulter la documentation technique fournie par le projet Git.

Lisez notre récapitulatif sur Git 2.45.0, Git 2.46.0 et Git 2.47.0 pour découvrir les autres points forts de cette version.