blob: dccbdce36309c485c297698cedcd19b6fe1c2bf3 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
|
# DNA Backup
[![build][build-img]][build-url]
_Deduplicated versioned backups for DNA._
## Details (FR)
Le système part du principe qu'on a une copie des données stockées en ADN
sur un support de stockage classique : le _repo_.
```
+----------------------------------+
| +---------+ +---------+ | +-----------+
| | | | | | | |
| | Source |--------->| Repo |----------->| DNA-Drive |
| | | COMMIT | | | SYMTHESE | |
| +---------+ +---------+ | +-----------+
| |
| Ordinateur |
+----------------------------------+
```
La structure du _repo_ est la suivante :
```
repo/
├── 00000/
│ ├── chunks/
│ │ ├── 000000000000000
│ │ ├── 000000000000001
│ │ ├── 000000000000002
│ │ └── 000000000000003
│ ├── files
│ ├── hashes
│ └── recipe
└── 00001/
├── chunks/
│ ├── 000000000000000
│ └── 000000000000001
├── files
├── hashes
└── recipe
```
Pour un repo d'une taille totale de 401 Mio:
```
/tmp/test-1/00000/recipe 5076011 (1.20%)
/tmp/test-1/00000/files 24664 (0.06%)
/tmp/test-1/00000/hashes 3923672 (0.93%)
/tmp/test-1/00000/chunks 412263137 (97.8%)
/tmp/test-1/00000 421287604 ( 100%)
```
- On considère que le _repo_ est toujours présent lors d'une écriture (_commit_).
- Le _repo_ peut être reconstruit à partir des données présentes dans le
_DNA-Drive_.
- Les _hashes_ ne sont pas écrits en ADN car ils peuvent être reconstruits à
partir des données des _chunks_.
- L'ensemble des données écrites en ADN sont compressées, pour le moment via
_ZLib_.
- Les metadonnées sont stockées de manière incrémentale, chaque version stocke
donc ses metadonnées sous la forme de delta par rapport à la version
précédente.
On imagine le _DNA-Drive_ comme un segment de _pools_ :
```
+---+---+---+---+---+---------+---+---+---+
| 0 | 1 | 2 | 3 | 4 |--> <--| 61| 62| 63|
+---+---+---+---+---+---------+---+---+---+
|versions| chunks | | metadata |
(recipe+files)
```
### Commit algorithm
1. Chargement des métadonnées du _repo_ afin de reconstruire en mémoire l'état
de la dernière version :
- Reconstruction de la _recipe_ à partir des deltas de chaque version.
- Reconstruction du listing des fichiers à partir des deltas de chaque
version (fichier _files_).
- Reconstruction en mémoire des _maps_ de _fingerprints_ et de _sketches_
à partir des fichiers _hashes_ de chaque version.
2. Listing des fichiers de la _source_.
3. Concatenation de l'ensemble des fichiers de la source en un disque virtuel
continu.
4. Lecture du _stream_ de ce disque virtuel et découpage en _chunk_ (de 8kio
actuellement).
5. Pour chaque _chunk_ du _stream_:
1. Calculer sa _fingerprint_ (hash classique), si elle est présente dans la
_map_ : le stocker de manière dédupliquée (sous la forme d'identifiant
faisant référence au _chunk_ trouvé dans la map).
2. Si elle n'était pas présente, calculer son _sketch_ (hash de ressemblance),
si il est présent dans la _map_, le stocker sous la forme de delta (calcul
de sa différence par rapport au _chunk_ trouvé dans la map).
3. Si il n'était pas présent, le stocker sous la forme de nouveau bloc (ajout
de sa _fingerprint_ et de son _sketch_ dans les _maps_ et stockage du
contenu complet dans un nouveau _chunk_).
6. Calcul des différences entre la nouvele version et la précédente pour les
métadonnées (_files_ et _recipe_) et stockage des deltas ainsi obtenus.
### Restore algorithm
1. Chargement des métadonnées du _repo_ afin de reconstruire en mémoire l'état
de la dernière version :
- Reconstruction de la _recipe_ à partir des deltas de chaque version.
- Reconstruction du listing des fichiers à partir des deltas de chaque
version.
2. À partir de la _recipe_, reconstruire le disque virtuel (sous la forme d'un
_stream_).
3. Découper ce _stream_ en fonction du listing des fichiers (_files_) et
réécrire les données dans les fichiers correspondants dans le repertoire
_destination_.
### Restorer sans le _repo_
#### Reconstruction complète du _repo_
Il est possible de reconstruire le _repo_ en entier en lisant la totalité du
_DNA-Drive_.
#### Restauration de la dernière version
Il est possible de ne restaurer que ka dernière version en lisant dans un
premier temps le _pool_ de versions et les quelques _pools_ de métadonnées
(environ 2% de la totalité des données écrites), puis en lisant tous les _pools_
contenant des _chunks_ référencés par la _recipe_ de cette version.
#### Restauration d'un seul fichier
Il pourrait être possible (pas pour le moment) de ne restaurer qu'un seul fichier
d'une version en ayant moins de données à lire que pour restaurer la version
complète.
Pour cela, il faudrait en plus stocker en ADN un mapping _chunk_ décompressé ->
_pool_ contenant ce _chunk_ et ainsi n'avoir à lire que les _pools_ contenant
des _chunks_ de ce fichier.
## Build instructions
_Classical go_
### Requirements
- Go >= 1.16
### Instructions
```bash
# Build
go build
# Test
go test ./...
# Run
go run . <source-dir> <repository>
```
[build-img]: https://github.com/n-peugnet/dna-backup/actions/workflows/build.yml/badge.svg
[build-url]: https://github.com/n-peugnet/dna-backup/actions/workflows/build.yml
|
