Un Plakar pour ranger ses archives

Plakar est un outil de sauvegarde multi-plateforme et open source. Basé sur les technologies et les usages contemporains : il utilise la déduplication, la compression et met la priorité sur le chiffrage et la signature (intégrité de l’archive et authenticité).

Le code de Plakar, en golang, est découpé entre plusieurs bibliothèques que l’on peut utiliser de manière granulaire. Plakar est l’application qui va tirer toutes ses bibliothèques pour proposer une UI élégante.

Kloset

Kloset (qui m’évoque la martyre de Thénardier) s’occupe des archives, c’est cette partie que je souhaite disséquer.

Théorie

Découper en tranches

Le document est découpé en tranches (chunks en VO), avec l’espoir d’avoir des tranches en commun avec d’autres fichiers.

Si le format de fichier ne secoue pas tout chaque fois qu’il enregistre, il est fort probable d’avoir des duplicas. C’est le pari de git qui travaille à partir de patch. Cette approche fonctionne très bien avec des fichiers plats (tant qu’il n’y a pas de guerre vaine de formatage).

Limiter les transferts

Même avec une connexion moderne, il est toujours appréciable de limiter la bande passante utilisée lors d’un transfert de données. À l’ère du NVMe, la sauvegarde sur un disque à plateau (plus pérenne à long terme) va vous paraitre mollassonne.

L’outil de référence (et historique) de synchronisation incrémentale est rsync, enfin, librsync. L’explication de l’algorithme (simple et élégant) est décrit dans l’article originel The rsync algorithm de 1996.

Il est agréablement lisible.

Le fichier cible est découpé en blocs de taille fixe (des chunks), dont on calcule deux hashs. Le premier hash, dit “faible”, peu couteux à calculer, aide à trouver des similarités, le second, dit “fort”, garanti que deux chunks sont identiques.

La cible fournit cette liste à la source.

Cette approche est élégante, mais le fichier cible doit être non chiffré pour pouvoir appliquer les modifications sur la cible. Techniquement, il est possible d’avoir le fichier cible chiffré tant qu’il fournit la liste de ses hashs, par contre, ils seront stockés en l’état sur la cible. Le moment où l’on souhaitera effacer les anciennes versions pour faire de la place va être compliqué.

Le temps de calcul va dépendre (de manière non linéaire) de la taille du fichier, bon courage pour les vidéos et les images disques.

Déduplication par le chunk

Les chunks peuvent être utilisés de manières différentes.

En décrivant les fichiers avec des listes des chunks, sans “fenêtre roulante”, la création de patch minimaliste n’est plus possible. Par contre, en travaillant sur un volume conséquent de fichiers (en To), il y aura statistiquement de doublons, des chunks communs à plusieurs fichiers : le Graal du dédoublonnage.

La déduplication est fort pratique pour la sauvegarde, mais elle est aussi déployée pour le stockage distant, qualifié de “synchronisation”, comme le propose Dropbox, Google Drive et tant d’autre. Seafile est un équivalent open source, même s’il a un coup de mou depuis 2016.

Historiquement, les morceaux découpés avaient une taille fixe, plus simple, moins couteux en CPU, mais limitant les chances d’avoir des doublons.

Le Content-Defined Chunking décrits dans ce papier (“Découpage basé sur le contenu” dans la langue de Pivot) propose d’utiliser des morceaux de tailles variables (dans une fourchette imposée) pour augmenter le taux de duplicas.

Hugginface est enthousiaste sur le dédoublonnage permettant un gain en place et bande passante pour ses modèles monstrueux.

Optimiser le débit

Le meilleur moyen d’optimiser le débit d’un transfert et de ne pas transférer. Pour ça, il faut maximiser la chance que le chunk soit déjà sur place, un duplica. Les petits chunks ont plus de chance d’avoir des duplicas, mais trop de chunks sont plus lourds à indexer : les chunks sont regroupés dans un fichier de taille raisonnable, il faut donc maintenir un index pour savoir dans quel fichier se trouve un chunk.

Hugginface explique ses optimisations pour partager ses données. Il possède, à l’époque de la rédaction de leur billet, 45Po de données découpées en chunks de 64ko, soit 690 milliards de chunks. Pour un fichier de 200Go, taille normale chez eux, il faut 3.125 millions de chunks.

Pour téléverser un fichier, il faut le découper en chunks, et pour chacun vérifier qu’il n’est pas déjà sur le serveur via un filtre de Bloom : on prend le hash du chunk, modulo 1000, et hop, on connait le nom de l’index à télécharger qui peut contenir le nom du chunk. Les chunks sont regroupés en bloc de 64Mo, et envoyés dans un ordre quelconque.

L’archivage se fait sur un disque dur, les SSD/NVMe restent hors de prix pour les gros volumes. Le HDD, lui continue sa course à la densité, même si le débit ne suit pas.

En dispersant les chunks sur un disque dur, les performances en lecture ne sont pas optimales, les lectures séquentielles sont bien plus performantes.

Les écritures sont regroupées en plus gros blocs, plus simple à optimiser pour le système de fichier.

Les fabricants de disques durs font de gros efforts pour conjuguer densité et débit.

Le cache distant (celui du disque, ou d’un SSD en renfort), et local (les duplicas) amélioreront grandement les performances en téléchargement. La restauration complète d’une sauvegarde, sans cache local, avec peu de chance que les chunks soient dans le cache distant, est le cas le plus défavorable.

Tout ça n’est que théorie, il faut des tests de charge pour valider/invalider ces hypothèses.

Le bus interne (SATA/SAS), le processeur, la bande passante de l’hébergeur, et fort probablement la bande passante de l’utilisateur peuvent être des goulots d’étranglement.

Hugginface, est dans un cas bien plus favorable, ses modèles en best-seller profitent pleinement d’un cache en SSD/NVMe.

Entropie d’un binaire

L’entropie mesure le côté aléatoire d’un binaire, l’absence de motifs répétés (comme des séries de 1 ou de 0). Les binaires pleins de trous ont même un nom, les sparse files et les systèmes de fichiers savent bien les gérer. Une faible entropie va perturber le processus de découpage basé sur le contenu qui créera des chunks rares, qui n’auront que peu de duplicas. Les images disques de machine virtuelle sont un bon exemple de sparse file en représentant l’espace disponible de longues suites de 0.

L’article The Impact of Low-Entropy on Chunking Techniques for Data Deduplication explique ça avec précision.

Traiter les données depuis la cible

Traditionnellement, les chunks ne sont pas chiffrés, ce qui permet d’agir depuis la cible.

Redécouper les chunks pour chaque client, en fonction de la qualité de leur connexion (latence et pertes de paquets) permettra une utilisation fluide sur un réseau de qualité médiocre (ce qui arrive régulièrement sur les réseaux de téléphonie mobile).

Indexer le contenu permettra aux utilisateurs de chercher dans leur fatras de documents en ligne. Dropbox vous propose de chercher vos images (OCR et description par une IA) mais aussi de bannir le contenu protégé par le droit d’auteur (initialement à base de hachages sur liste noire) et finalement de faire la chasse aux pédonazis.

Chiffrage

“Oui, mais moi, je n’ai rien à cacher”, comme l’affirme le projet ECHELON. Depuis la révélation de ce projet, le chiffrage s’est généralisé sur Internet. Il n’y a aucune raison de ne pas chiffrer son stockage en ligne (dans le Nuage ?).

Cryptomator se positionne comme intermédiaire local entre vous et un stockage distant. C’est gentil de leur part, mais l’un des objectifs du chiffrage est de transformer vos données en ce qui semble être un amas d’octets complétement aléatoire. Cette bouillie d’octets est le pire cas pour le chunking et le dédoublonnage.

Le chiffrage doit se faire après le découpage des chunks, à la source et la cible ne doit avoir aucun moyen de lire le contenu.

Implémentation de Kloset

Comme le laisse supposer les précédentes explications théoriques, Kloset va chunker, vérifier, authentifier, dédoublonner, compresser et chiffrer.

Son objectif est la sobriété (stockage et bande passante), la résilience et la sécurité.

Ces explications, bien que denses, se contentent de vulgariser les choix techniques de Kloset, pour avoir une connaissance exhaustive, il faut lire le code.

Chungking Express

Le jeu de mot avec le film était trop tentant, même si c’est loin d’être le meilleur de ce réalisateur.

Kloset utilise du CDC (des chunk de taille variables) et comme il n’y a aucun hash à rouler, un seul, fort, est utilisé. Un chunk, et bien d’autres objets sont désignés par leur hachage.

Clef maîtresse

Toute la sécurité de Kloset part du mot de passe de l’utilisateur (qui est validé par diverses contraintes de sécurité lors de sa création).

À la création du dépôt, un bloc de 32 octets aléatoire est créé, il sera le sel.

Le mot de passe et le sel vont générer une master key (de 32 octets) avec une fonction de dérivation de clef.

Ce hachage est volontairement compliqué et lent (même pour un GPU) pour ralentir les attaques en force brute. Argon2 a été choisi (gagnant du concours de hash de 2015 quand même).

MAC

Il n’est pas tout à fait vrai de dire que Kloset utilise des hash pour vérifier l’intégrité de ses contenus. Pour être précis, il faut parler de HMAC, sur-ensemble d’un hash, qui permet de vérifier en plus l’authenticité avec un secret. N’importe qui peut modifier le document et fournir un hash valide, mais seul les personnes connaissant le secret peuvent signer et authentifier. Le terme MAC est utilisé dans le code pour désigner les HMAC.

La clef maitresse est utilisée comme secret pour les différents HMAC.

Pour de meilleures performances le hachage n’est pas forcément confié au standard SHA-256, mais utilise par défaut BLAKE3, très rapide et facilement parallélisable (SIMD et multi-threads).

Ce MAC sert de clef pour désigner les différents objets du projet.

Chunk et PackFile

Kloset considère que tout est un blob binaire, référencé par un Chunk. Les blobs et leur Chunk sont entassés dans un Packfile qui, lui, sera enregistré sur un disque dur, un S3, quelque part.

Un PackFile se compose de trois parties. D’abord une écriture en flot (sans tout charger en mémoire) d’une suite de blobs. Ensuite viennent les métadonnées (de taille fixe) pour chacun des blobs, consolidées en RAM (28o de méta par bloc, c’est plus que raisonnable). Le PackFile se termine par un footer, de taille fixe (28o aussi) qui contient, entre autre, l’offset de l’index.

Les Packfile ont une taille maximale. Si l’on a besoin de plus de place, il suffit d’en créer un nouveau.

En théorie un Packfile peut contenir n’importe quels binaires typés (jusqu’à 2^32 types différents). Kloset s’en contente d’une vingtaine.

Comme tous les différents objets sont désignés par des hash, les Chunk vont se retrouver ventilés dans de multiples Packfiles.

Il est techniquement possible d’itérer dans tous vos Packfile pour trouver un MAC (une clef) précis, mais un confortable index permet de connaitre, rapidement, pour chaque objet son Packfile, son offset, sa taille et son type.

Entry

Kloset sauvegarde des fichiers, pas uniquement des données binaires abstraites.

Le fichier est modélisé par un Entry (participant ?), sérialisable, qui va contenir toutes les méta-informations spécifiques à l’OS (UNIX, Windows), et les fichiers spéciaux (dossiers, liens symboliques, liens durs) en plus des méta-données liées à l’archivage.

Une Entry contient moult méta-données, et une référence à son Object listant des références Chunk (qui eux font référence au contenu binaire).

MessagePack est utilisé pour la sérialisation. C’est un format similaire à JSON (auto-descriptif), mais rapide et compact.

Repository

Le “dépôt” est le point de départ pour sauvegarder ses données. Différents paramètres permettent de l’adapter à ses besoins, et il maintient un index pour manipuler efficacement ses archives.

Un dépôt peut utiliser un disque local, distant, un serveur de stockage (façon S3) ou un serveur distant (sftp et même ftp).

Un dépôt peut se synchroniser avec un autre dépôt.

Snapshot

Les fichiers sont archivés par lots, dans des Snapshot.

Un Importer va effectuer un scan, un parcours (walk en VO) de l’arborescence de fichiers filtrés par des règles.

Kloset décrit l’interface Importer qui n’a qu’une implémentation de test. Plakar, lui, fournit des implémentations concrètes.

L’Importer fournit un flot de ScanRecord représentant les fichiers à sauvegarder.

PackageManager

Un Repository possède un PackageManager (qui parallélise ses taches) que l’on va nourrir de Blob (type, MAC, contenu) pour créer des PackFile, le Repository se chargeant de les compresser et chiffrer (si la configuration le réclame).

Pour l’instant, aucune excentricité dans les choix des outils de compression : le vénérable GZIP (bonne compression, mais débit mou) ou LZ4 (débit fantastique au détriment de la compression).

Le chiffrage propose des configurations normées d’AES-256.

Store et index

Les PackFile sont enregistrés dans un Store, une interface avec juste une implémentation de test dans Kloset, mais des implémentations concrètes dans Plakar.

Il n’y a pas d’index pour retrouver ses petits, mais un cache, que l’on peut reconstruire. Plus précisément, c’est une interface StateCache qui a pour une fois des implémentations dans Kloset basés sur PebbleCache. Pebble est un clone de RocksDB en Golang.

Sécurité

La sécurité, c’est comme les interfaces utilisateurs, il ne faut jamais laisser un développeur s’en approcher.

Lire la page Wikipédia pour comprendre les concepts est un bon début. Ne pas tripoter les curseurs, surtout sans savoir ce qu’ils font est simplement du bon sens. Faire valider/auditer par un spécialiste la partie liée à la sécurité est sage (ça éloigne le mauvais œil et les zero days).

Les salles secrètes du donjon

Après une rapide visite du donjon de Kloset, on peut apercevoir des indices sur des fonctionnalités futures.

Des notions de “classification” et de “Score” apparaissent.

Il est aussi possible que j’aie raté des éléments dans ma lecture du code.

Ma lettre au père Noël

Trousseaux

Laisser trainer sa clef avec le risque de la perdre et de transformer ses archives en brique est inutilement stressant.

• [ ] Intégration à Vault ou un équivalent, pour gérer le “grand secret”
• [ ] Intégration à différents trousseaux (gnome keyring, keepass, freedesktop keyring, apple keyring…)

Résilience

Les disques durs qui meurent, ou plus fourbe, les octets pourris (bit rot en VO), ça arrive, c’est même pour ça que l’on fait des sauvegardes (même si le cas d’usage classique et de pouvoir revenir sur une action hasardeuse).

• [ ] Correction d’erreurs de Reed-Solomon pour palier ou compléter la flemme de la réplication
• [ ] Gestion de la parité en XOR sur 3 disques pour contourner Minio ou le RAID

UX

La sauvegarde doit être systématique, machinale, la moindre friction ressentie par l’utilisateur va espacer les backups. L’assurance de pouvoir restaurer sereinement est tout autant indispensable.

• [ ] Sauvegarde qui se déclenche (ou demande gentiment) dès que l’on branche un disque USB dédié (et si la machine est branché à son chargeur)
• [ ] Décompression à la volée des archives, comme les dumps SQL ou les fichiers OpenDocument, pour avoir de jolis chunk (et de recompresser dans le PackFile)
• [ ] Sauvegarder un snapshot, si le système de fichier en est capable (ZFS, Btrfs, bcachefs, APFS…)
• [ ] Connexion aux sauvegardes intégrées d’applications, comme le archive_command de Postgresql

Plus vite, plus haut, plus fort

• [ ] Gestion des disques SMR avec des PackFile qui remplissent efficacement les tracks.
• [ ] Échange des PackFile en QUIC, tant pis pour les paquets perdus, on les redemandera plus tard. Ça revient presque à du chunk de chunk.

Indexation et recherche

Là, on s’éloigne du backup pour se rapprocher de l’archivage.

• [ ] Création de vignette pour les images, et la possibilité d’afficher, comme pour le teste, le delta (avec un PixelMatch moins laid) pour choisir la version à restaurer
• [ ] Embeding avec le Fast Tokenizer d’Hugginface pour de la recherche par mot (enfin, par token) ou même de la similarité.
• [ ] Indexation des images (création de mots clefs) avec YOLO ou d’autres modèles (avec une licence compatible).

SAAS

Chacun ses chunk

Backblaze a un prix d’archive au kilo (enfin, au téra) fort difficile à concurrencer, même s’ils fournissent la recette pour construire leurs serveurs.

L’offre de Backblaze est, à la louche, le prix d’un dédié (OVH, SCW, Hetzner), avec une redondance de stockage de deux. Il faut compter en plus les salaires et leur marge.

Mutualiser les chunk de différents utilisateurs

Juste pour l’exercice d’une offre SAAS qui partage des chunk entre utilisateurs (chunk qui reste rangés dans des Packfile), pour dédoublonner encore plus fort. Pour ça, il faut que chaque chunk ait une clef de chiffrage différente, et un hash (pas un hmac) pour les désigner.

Il faut un archiviste-notaire qui certifie une clef TLS pour chaque utilisateur.

Un utilisateur souhaite envoyer un chunk avec une taille et un hash, le serveur dit “OK, je pense l’avoir déjà, voici un sel aléatoire, calcul moi le hmac du chunk“, si la preuve est correcte, pas besoin d’envoyer le fichier. Le notaire va ajouter l’utilisateur à la liste des propriétaires du chunk.

La partie chiffrage est la plus casse-gueule.

Pour déchiffrer un chunk que l’on n’a pas créé, il faut demander au notaire la liste des propriétaires, et contacter l’un d’eux en point à point, en s’authentifiant en mTLS. Le propriétaire s’assure auprès du notaire que la demande est légitime, puis il fournira la clef (qu’il a chiffrée en local avec sa clef maitresse).

Pour ça, il faut qu’une des personnes soit connecté et réponde à un moment ou à un autre (comme l’utopique IPFS).

Sinon, le serveur conserve et fournit les clefs, ce qui est contraire au concept même de Kloset.

Je vois là une belle usine à gaz instable, et je n’ai même pas prononcé le mot DHT.

Un concept de crypto qui m’échappe peut, peut-être, résoudre ce micmac.

La limite du raisonnable

Oui, une partie des souhaits ne sont pas raisonnables.

Essayer de contourner des services existants est risqué.

Optimiser quelque qui chose qui fonctionne déjà correctement, ou pour des conditions extrêmes n’est jamais une bonne idée.

Par contre, d’autres gadgets, comme la synchronisation QUIC peut être développé (pour le sport) à côté sans rien secouer. Si le gain est décevant, poubelle, et retour aux approches sages.

Old

Le billet de blog officiel décrivant Kloset existe, mais promis, je suis parti des sources et des publications universitaires pour écrire ma version.