Bonjour à tous,
La version 1 de mon programme de sauvegarde Woodstock Backup utlise Btrfs et Rsync pour effectuer une sauvegarde. Je
l'utilise depuis quelques mois pour sauvegarder mes differentes machines (7 machines).
Voici un premier compte-rendu de l'utilisation de la première version de cet outil dont je suis l'auteur:
- Lors de mon utilisation la sauvegarde fonctionne très bien, et cela c'est cool :). Je suis aux alentours de 200 snapshots.
- J'ai eu un problème d'espace disque. Lors du déplacement de plusieurs énormes fichiers sur un serveur. La taille de
l'espace de stockage à augmenté énormément.
En effet rsync ne permet pas de détecter les déplacements de fichiers et btrfs ne permet pas de dédupliquer à la volée
les données.
Les fichiers ont donc été considérés comme étant nouveau.
- L'espace disque étant tombé à zéro, j'ai voulu supprimer la dernière snapshot pour tester un déplacement de fichiers
dans btrfs (à la main).
La suppression de la snapshot a commencé à prendre énormément de temps, puis la machine est devenue inaccessible.
En me connectant en direct sur la machine (KVM), j'ai découvert que la suppression du dernier volume Btrfs remplissait
la mémore. Les 8Go octets de mémoire ont été remplis. Et le noyaux linux a utilisé OOM Killer pour détruire tous les
processus.
Bref la machine n'était plus dans un état lui permettant de faire les sauvegardes.
On parle déjà de problème avec btrfs et la suppression de snapshot (https://www.spinics.net/lists/linux-btrfs/msg52088.html).
On trouve aussi pas mal d'article si les problèmes de btrfs quand il n'y a plus d'espace.
Cela me fait penser que btrfs ne me permettrait pas de gérer mes sauvegardes sur le long terme (tant sur le nombre de snapshots
que cela allait créér que sur la déduplication).
Cela m'amène à la conclusion suivante, il faut que je repense la gestion du pool et de la déduplication. C'est d'ailleurs
ce que font beaucoup de logiciel de sauvegarde (UrBackup proposer Btrfs et une version interne ; BackupPC gère son pool interne,
Borg gère son pool interne ...)
Je vais donc repenser la manière dont je gère la déduplication dans l'application de sauvegarde. Si je réécris la manière
dont est géré le stockage, je ne pourrais plus me baser sur rsync pour la sauvegarde. Il faudra donc que je développe mon
propre outil pour générer la sauvegarde.
Par contre cela à l'avantage de ne plus être dépendant d'un système de fichier.
Le pool
Diviser pour réigner
Nous allons donc commencer par construire ce qui doit être le pool des données. Permettant de faire la déduplication.
Afin de faire de la déduplication, nous allons découper les fichiers en plusieurs morceaux. Cela permettra de faire des
sauvegardes de gros fichiers dont seule une partie change:
- Comme les images de machine virtuelle par exemple
- Comme les fichiers de logs par exemple
Quelle est la bonne taille pour un morceau de fichier. Si on découpe le fichier de taille trop petite alors le découpage ne
sert à rien. J'ai donc pris un échantillon de tous les fichiers que j'ai sur mes différentes machines pour déterminer la taille
de cet échantillon.
find . -type f -print0 | \\
xargs -0 ls -l | \\
awk '{ n=int(log($5)/log(2)); if (n<10) { n=10; } size[n]++ } END { for (i in size) printf("%d %d\\n", 2^i, size[i]) }' | \\
sort -n | \\
awk 'function human(x) { x[1]/=1024; if (x[1]>=1024) { x[2]++; human(x) } } { a[1]=$1; a[2]=0; human(a); printf("%3d%s: %6d\\n", a[1],substr("kMGTEPYZ",a[2]+1,1),$2) }'
Voici le resultat de ce test d'échantillon.
| File size |
Number |
Repartition |
|---|
| 1k |
29126558 |
37,36 % |
| 2k |
8649088 |
48,45 % |
| 4k |
7915884 |
58,60 % |
| 8k |
6394302 |
66,81 % |
| 16k |
4839627 |
73,01 % |
| 32k |
3606949 |
77,64 % |
| 64k |
3477900 |
82,10 % |
| 128k |
5158625 |
88,72 % |
| 256k |
3601985 |
93,34 % |
| 512k |
971108 |
94,58 % |
| 1M |
875574 |
95,71 % |
| 2M |
1698194 |
97,88 % |
| 4M |
1046430 |
99,23 % |
| 8M |
309027 |
99,62 % |
| 16M |
105271 |
99,76 % |
| 32M |
65211 |
99,84 % |
| 64M |
50832 |
99,91 % |
| 128M |
33947 |
99,95 % |
| 256M |
21338 |
99,98 % |
| 512M |
8066 |
99,99 % |
| > 1G |
10068 |
100,00 % |
La conclusion que l'on peut tirer de cela est que si on prend un chunk de 4Mo, alors 99% des fichiers ne seront pas découpés. Dans
le lot rentrerons la plupart des fichiers textes, des photos, ... . Tous des fichiers qui s'ils ne sont pas des copies, sont normalement
unique.
Dans une première version, je pense que cette taille ne sera pas paramétrable, mais il faudra la rendre dynamiquement paramétrable dans le
futur (si le type des fichiers d'autres personnes a pour conséquence une répartition différente).
La table de hashage
Ces différents morceaux de fichiers (chunk) doivent ensuite pouvoir être identifiés facilement sans pour autant relire le contenu du fichier à
chaque fois.
L'idée est d'utiliser une table de hashage où avec une clé on peut retrouver le contenu d'un morceau de fichier.
Il faut pouvoir, à partir de la clé:
- savoir si le morceau de fichier existe,
- lire le contenu du morceau de fichier,
- écrire le contenu du morceau de fichier.
Quelle clé peut-on utiliser ?
Après quelque recherches je vais partir sur un SHA-256. Quels sont les avantages et les inconvénients d'une telle clé ?
L'avantage est qu'il est possible, quand on connait le hash de faire le lien direct avec le morceau de fichier associé. La clé est
facile à générer et le lien entre la clé et le chunk est facile à connaître.
Le plus gros inconvénient est le risque de collision. Le but d'une fonction de hash est de calculer un nombre "court" qui permet
de representer un texte beaucoup plus long. Ce type de fonction de hashage est généralement utilisé pour:
- quand elle est coupler à une clé public/privé, signer un document,
- verifier l'intégrité d'un document (en cas d'erreur transfert réseau),
- envoyer séparement permet de vérifier que le fichier n'a pas été corrompu.
Ce qui est le propre d'une fonction de hash est sa non réversibilité. En effet s'il était possible de retrouver facilement à partir d'un
hash le texte contenu associé, les algo de compression n'utiliseraient que ca ;).
Mais la plus grosse conséquence de tout cela est que deux textes (de contenus et de longueurs différentes) peuvent arriver au même hash.
Pour un logiciel de sauvegarde, cela pose alors un gros problème. Si parcequ'il possède le même hash qu'un autre fichier, on ne sauvegarde
pas un document, la restauration ne sera pas faite à l'identique et cela engendrera de la perte de fichier.
Je me suis donc renseigné sur ce qui se faisait ailleurs.
Borg
Je trouve borg intéressant dans son fonctionnement, ses performances, ainsi que son stockage interne. Ce qui est dommage, c'est que dans
mon cas, je n'ai pas une vue centralisée des machines dont j'organise la sauvegarde.
Dans la partie Internals on retrouve la structure interne du pool de Borg.
Borg utilise HashIndex, qui si j'ai bien compris
calcule un hash sur un contenu dont la taille peut varier. Des utilisateurs se sont déjà posés la question du risque de collision.
La réponse faite par l'équipe de Borg a été de rejeter la demande. L'explication qui est faite est que la probabilité qu'une telle
collision arrive est faible sur un hash de 256. Très faible.
UrBackup
Même chose pour UrBackup. Dans le manuel d'administration, partie 6.3,
on retrouve l'information suivante:
UrBackup uses SHA512 to hash the files before file deduplication. In comparison ZFS uses SHA256 for block deduplication.
The choice of SHA512 is safer. The Wikipedia page for “Birthday attack” has a probability table for SHA512. According to
it one needs 1.6 _ 1068 different files (of same size) to reach a probability of 10-18 of a collision. It also states
that 10-18 is the best case uncorrectable bit error rate of a typical hard disk. To have 1.6 _ 1068 different files of
1KB you need 1.4551915 * 1056 EB of hard disk space. So it is ridiculously more likely that the hard disk returns bad
data or the data gets corrupted in RAM, rather than UrBackup linking the wrong files to each other.
Bref, on y explique sur la probabilité de collision pour un SHA512 est plus faible que celle utilisé pour la déduplication
dans ZFS. On y explique également qu'elle est ridicule par rapport au risque de panne d'un disque dur.
BackupPC
BackupPC utilise un MD5 pour gérer son les clés de son pool. En cas de collision (ce qui est beaucoup plus probable avec un MD5 qu'avec
un SHA-256) une extension est ajoutée à la fin du fichier.
Cela necessite alors de ré-envoyer le fichier sur le réseau pour comparer, mais permet de s'assurer qu'en cas de collision on ait une
solution de repli.
Un MD5 fait 4 octets contrairement à un SHA-256 qui en fait 32.
Du coup, est-ce qu'avec un md5, j'ai beaucoup de collision sur mon instance BackupPC ? Pour un pool qui contient 3 464 397 fichiers, j'ai
0 collision.
> find . -type f | wc -l
3464397
> find . -type f | awk 'length($0) > 40' | wc -l
0
Ce qui est plutôt rassurant sur le risque de collision sur un SHA-256
Woodstock Backup
Pour mon propre logiciel, je vais partir sur un SHA-256. Je vais partir du principe qu'il n'y a pas de collision (et je ferais un test
pour vérifier cela).
Dans une version future il pourrait être intéressant d'ajouter une extension au fichier dans le cas où il y a une collision, et laisser
la possibilité à l'utilisateur de demander à retransférer le fichier pour être sûr qu'il n'y a pas de collision.
Structure du pool
Maintenant que l'on connaît la taille des différents morceau de fichier ainsi que la clé qui nous servira à les classer. Nous allons
maintenant voir comment les organiser dans notre système de fichier.
Derrière le stockage j'ai les idées suivantes:
- Si on stocke tout les chunks (morceau de fichier) dans un seul dossier, nous pourrions au plus avoir
1.3 x 10^154 fichiers. Mais
cela dépendra plus du nombre de fichier (chunk) que du nombre du nombre de possibilités.
- Un système de fichier est en lui-même déjà une table de correspondance où la clé est le nom du fichier.
- Il y a une limite sur le nombre de fichiers par dossier:
- FAT32: 65 536 (donc non utilisable)
- NTFS: à priori pas de limit.
- EXT2: ~1.3 x 10^20 (mais problème de perf au delà de 10 000) - (donc je déconseille son utilisation).
- EXT4: pas de limit de nombre de fichier par dossier
- J'aimerai à terme (un jour peut-être) pouvoir proposer l'utilisation d'un stockage objet (exemple S3, minio, ...) afin de pouvoir
utiliser ce stockage depuis plusieurs serveurs. Il n'y a pas de limite du nombre de fichier dans un bucket S3.
- Sur une structure à deux niveaux (et 255 possibilité par niveau), on peut espérer que les 3,5 millions de fichiers seront répartis
ce qui ferait un peu plus d'une 50 de fichier par dossier. (le nombre de fichier par dossier dépend du nombre de fichier et de leurs
taille).
Voici la structure que j'imagine utiliser pour le stockage des chunks.
pool
├── aa
│ ├── aa
│ │ ├── aa
│ │ │ ├── REFCNT
│ │ │ │ ├── sha256 cnt
│ │ │ │ ├── sha256 cnt
│ │ │ │ └── sha256 cnt
│ │ │ ├── LOCK
│ │ │ │ └── host backupNumber
│ │ │ └── aaaaaacdefghih-sha256.zlib
Pour les 3 premiers niveaux, nous allons avoir une structure de dossier qui est constituée des 3 premiers octets du SHA-256. Ce qui permet
de réduire le nombre de fichiers par dossier, mais aussi de limiter le nombre de LOCK lors de la création du pool.
Ensuite dans chaque dossier, nous aurons un fichier de LOCK qui sera créé lors de l'ajout d'un nouveau morceau de fichier. Il sera également
utilisé lors de la lecture.
Un fichier REFCNT sera utilisé pour compter le nombre de référence. Cela permettra de supprimer les morceaux quand ces derniers ne seront
plus utilisés.
Enfin les morceaux de fichiers sont stockés dans des fichiers dont le nom contient le hash. Ces fichiers peuvent être compressés pour réduire
l'espace utilisé.
Structure des fichiers de sauvegardes
Une fois les morceaux de fichiers déposés dans le pool, il nous faut un fichier permettant de référencer l'ensemble des fichiers qui composent
la sauvegarde.
Il y aura un fichier par sauvegarde.
Ces fichiers de sauvegarde seront stockés dans les dossiers des différents serveurs sauvegardés. Ce fichier contient l'ensemble des fichiers
d'une sauvegarde et pour chaque fichier, le hash de l'enssemble des morceaux de fichiers.
Ce fichier doit avoir un format lisible facilement et rapidement par un programme. Ce fichier sera dans un format binaire (pour que le fichier
soit lisible rapidement et qu'il ne prenne pas trop de place).
Afin de simplifier la mise en place de ce fichier, nous allons utiliser protocol-buffers. Ce
dernier permet d'avoir un format de fichier compatible quel que soit le language de l'application. Voici un premier jet de format de fichier qui
sera utilisé pour stocker chaque fichier d'une sauvegarde.
message FileManifest {
message FileManifestStat {
int32 ownerId = 1;
int32 groupId = 2;
int64 size = 3;
int64 lastRead = 4;
int64 lastModified = 5;
int64 created = 6;
int32 mode = 7;
}
message FileManifestAcl {
string user = 1;
string group = 2;
int32 mask = 3;
int32 other = 4;
}
bytes path = 1;
FileManifestStat stats = 2;
map<string, bytes> xattr = 5;
repeated FileManifestAcl acl = 6;
repeated bytes chunks = 3;
bytes sha256 = 4;
}
Le fichier sera constitué d'une liste de FileManifest. Ce fichier est de la forme :
int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest
int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest int32 FileManifest
(vous avez compris le principe)
où chaque int32 est la taille de chaque FileManifest.
Lors de la sauvegarde, le serveur repartira de la sauvegarde précédente et écrira toute modification dans un journal. Le journal
indiquera, les fichiers ajoutés, supprimés, et modifiés. Une fois la sauvegarde terminée, le journal sera fusionné dans le fichier de
sauvegarde (et le comptage de référence sera mis à jour).
Conclusion
Maintenant que j'ai une idée de la forme du nouveau de format de stockage, il ne me reste plus qu'à développer le pool de stockage.
Si vous avez des retours à me faire sur le format de stockage alors n'hésitez pas à me contacter. Vous pouvez le faire par exemple sur
https://github.com/phoenix741/woodstock-backup.
Original post of Ulrich Van Den Hekke.Votez pour ce billet sur Planet Libre.
