Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Garbage collection inter-clients gc Décidé

Mark-and-sweep par tenant, auto-réparant, sans jamais un verrou exclusif — le magasin reste ouvert pendant l'inventaire. Le bloom filter revient côté sortie, où ses erreurs tombent du côté sûr, et rien n'est détruit sans quarantaine.

Le problème en une phrase : on ne peut supprimer un chunk que si plus personne ne le référence — or tout le monde le partage, et des backups tournent pendant qu’on compte. Les voisins y ont tous laissé des plumes : restic a historiquement exigé un verrou exclusif pour le prune (le dépôt ferme, les backups attendent), borg maintient des caches de comptage qui se désynchronisent, kopia s’appuie sur des marges horloge sensibles au clock skew. Mais Cairn arrive au combat armé : les racines sont recensées, les sessions épinglent déjà tout backup en cours, l’index a son champ époque, les segments métadonnées sont séparés sur SSD, et la dédup est scopée au tenant.

Décision 1 — Mark-and-sweep, pas de comptage de références

En clair — l'inventaire tournant, pas les tickets de caisse Le comptage de références, c'est additionner les tickets au fil de l'eau : chaque upload incrémente, chaque prune décrémente. Une seule erreur de caisse — un crash entre deux écritures, un bug — et le total est faux pour toujours : c'est la plaie des caches borg. L'inventaire tournant, lui, ne fait jamais confiance aux totaux d'hier : il recompte depuis les registres officiels (les racines) à chaque passage. Un bug du GC ? Le cycle suivant le corrige tout seul. Auto-réparant par construction — et zéro coût sur le chemin chaud : l'ingest n'entretient aucun compteur.

Décision 2 — Par tenant : l’avantage structurel

Chaque chunk appartient à exactement un tenant (dédup scopée) → le GC tourne tenant par tenant : travail borné, parallélisable, ordonnancé en tournée (chaque tenant tous les N jours, ou déclenché par le volume pruné). Jamais de « stop the world » global. restic, borg et kopia sont des outils mono-dépôt — ils ne peuvent pas faire ça ; c’est l’architecture multi-tenant qui l’offre.

Décision 3 — Le protocole anti-course : l’horizon d’époque

La règle d'or — dans un seul sens Faussement vivant un cycle de plus = acceptable. Faussement mort = jamais. Toutes les courses se résolvent par cette asymétrie : un backup qui référence un vieux chunk pendant le GC ? Impossible — le « présent » de l'API d'existence l'a épinglé (le ticket de consigne, conçu pour exactement ça). Un snapshot qui committe pendant le marquage ? Ses chunks — fraîchement uploadés ou épinglés — portent tous une époque récente. La règle qui unifie : le sweep ne condamne que les chunks hors de l'ensemble vivant ET dont l'époque < horizon, où l'horizon = le début de la plus ancienne session active. Tout ce qui a bougé récemment est intouchable par principe.

Décision 4 — Le bloom filter, côté sortie

En clair — le même portier, à l'autre porte L'ensemble vivant d'un gros tenant = 50 M d'adresses × 32 o = 1,6 Go. Solution : un bloom filter — et savoure le retournement. À l'entrée (API d'existence), on a interdit au portier à mémoire floue de dire « présent » : son faux positif y causait une perte de données. À la sortie (le GC), son erreur change de sens : un faux positif marque un chunk mort comme vivant → il reste un cycle de plus — parfaitement sûr, et le cycle suivant (bloom re-semé, faux positifs ailleurs) le ramasse. Et un bloom n'a jamais de faux négatif → un chunk vivant ne sera jamais jugé mort. Le même outil, exactement inversé : ses erreurs tombent du côté sûr. L'ensemble vivant tient en ~60 Mo de RAM.

Le marquage parcourt le DAG depuis les racines — métadonnées SSD uniquement (la séparation des segments paie ici), sous-arbres partagés visités une fois — et remplit le bloom. Le sweep itère l’index du tenant et condamne ce qui n’y est pas (et dont l’époque < horizon).

Décision 5 — Quarantaine, puis compaction gloutonne

  • La benne fermée à clé. Le sweep ne détruit rien : il marque « condamné à l'époque E ». La destruction physique n'arrive qu'à la compaction, après confirmation par un cycle suivant + délai de grâce (72 h) — fenêtre d'undelete, protection contre le bug du GC lui-même et l'erreur d'opérateur. Grâce en époques logiques, pas en horloge murale (la faiblesse de kopia).
  • On ne réorganise que les caisses aux trois-quarts vides. Chaque segment a son taux de vivants ; la compaction prend les pires d'abord (le plus d'octets récupérés par octet réécrit — le glouton de la littérature log-structured), recopie les survivants dans un segment neuf, bascule l'index, supprime l'ancien. Seuil ~50 % ajustable ; les segments froids attendent d'être très morts. Ça referme le point laissé ouvert par la section D.

Décision 6 — Jamais de verrou exclusif, jamais

En clair — le magasin reste ouvert pendant l'inventaire Chez les concurrents, le dépôt ferme pendant le prune (restic : verrou exclusif, les backups attendent des heures). Chez nous : les bracelets de session protègent les clients en rayon, l'horizon d'époque protège l'inventaire des mouvements en cours — prune, mark, sweep et compaction tournent pendant les backups et les restaurations, avec throttling I/O pour ne pas affamer la production. C'est l'anti-restic — et un argument commercial de plus.

Le cycle complet

Le cycle du GC — par tenant, en tâche de fond, sans verrou

SESSIONS ACTIVES — épinglages · HORIZON D'ÉPOQUE : ce qui a bougé récemment est intouchable PRUNE la rétention retire des refs de snapshots (jamais le client) MARK racines → DAG → bloom ~60 Mo métadonnées SSD seules SWEEP condamne si hors bloom ET époque < horizon ne détruit rien COMPACT segments < 50 % vivants les pires d'abord après grâce (72 h) quarantaine cycle suivant — recompte depuis les racines : auto-réparant PAR TENANT · EN TOURNÉE · SANS VERROU EXCLUSIF backups et restaurations continuent pendant tout le cycle

Quatre étapes par tenant, en tâche de fond. Le sweep condamne, ne détruit pas — la destruction n'arrive qu'à la compaction, un cycle et une grâce plus tard. Et tout recommence depuis les racines : le GC ne fait jamais confiance à sa mémoire.

Les chiffres qui rassurent : tenant de 100 To (50 M chunks) → marquage = lecture streaming de dizaines de Go de métadonnées SSD (~minutes), sweep = scan de ~2,5 Go d’index (~minutes), bloom 60 Mo en RAM. Le GC d’un gros tenant est une affaire de minutes par cycle, en tâche de fond.