Accueil / Algorithmes

Algorithmes

Chunking, hachage hierarchique et indexation pour la deduplication

Vue d'ensemble des algorithmes

La deduplication efficace repose sur trois piliers algorithmiques : le decoupage des donnees (chunking), le calcul d'empreintes (hashing), et l'indexation pour la recherche rapide.

Pipeline algorithmique
flowchart LR subgraph Input["Donnees"] FILE["Fichier"] end subgraph Chunking["1. Chunking"] FIXED["Fixed
Blocs uniformes"] CDC["CDC
Content-Defined"] end subgraph Hashing["2. Hashing"] XXH["XXH3-128
Rapide"] SHA["SHA-256
Crypto"] HIER["Hash 256-bit
Hierarchique"] end subgraph Indexing["3. Indexation"] BLOOM["Bloom Filter
Pre-check"] BTREE["B+Tree
Lookup exact"] end subgraph Output["Resultat"] NEW["Nouveau"] DUP["Doublon"] end FILE --> FIXED FILE --> CDC FIXED --> HIER CDC --> HIER XXH --> HIER SHA --> HIER HIER --> BLOOM BLOOM --> BTREE BTREE --> NEW BTREE --> DUP style Chunking fill:#1e40af,stroke:#3b82f6 style Hashing fill:#065f46,stroke:#10b981 style Indexing fill:#7c2d12,stroke:#f59e0b

1. Algorithmes de Chunking

Le chunking decoupe les fichiers en blocs avant le calcul des empreintes. DRAGON propose deux modes adaptes a differents cas d'usage.

Fixed-Size Chunking

Principe

Decoupage en blocs de taille fixe (ex: 16 KB). Simple et rapide, mais sensible aux insertions/suppressions qui decalent tous les blocs suivants.

Fixed Chunking - Probleme du decalage
flowchart TB subgraph Original["Fichier Original"] O1["Bloc A
16 KB"] O2["Bloc B
16 KB"] O3["Bloc C
16 KB"] O4["Bloc D
16 KB"] end subgraph Modified["Fichier Modifie (+1 byte au debut)"] M1["Bloc A'
decale"] M2["Bloc B'
decale"] M3["Bloc C'
decale"] M4["Bloc D'
decale"] end O1 -.->|"different"| M1 O2 -.->|"different"| M2 O3 -.->|"different"| M3 O4 -.->|"different"| M4 style Original fill:#14532d,stroke:#22c55e style Modified fill:#7f1d1d,stroke:#ef4444

Algorithme Fixed Chunking

  1. Definir taille_chunk (ex: 16384 bytes)
  2. position = 0
  3. Tant que position < taille_fichier :
    • taille = min(taille_chunk, taille_fichier - position)
    • Creer chunk(position, taille)
    • position = position + taille_chunk

Avantages

  • Tres rapide (O(n) lecture simple)
  • Previsible (nombre de chunks connu)
  • Parallelisable facilement
  • Faible overhead CPU

Inconvenients

  • Sensible aux insertions/deletions
  • Taux dedup sous-optimal
  • Mauvais pour fichiers edites

Content-Defined Chunking (FastCDC)

Principe

Les frontieres de chunks sont determinees par le contenu lui-meme, en utilisant une fonction de hachage glissante (rolling hash). Les insertions/suppressions n'affectent que les chunks locaux.

CDC - Resilience aux modifications
flowchart TB subgraph Original["Fichier Original"] O1["Chunk A
12 KB"] O2["Chunk B
18 KB"] O3["Chunk C
14 KB"] O4["Chunk D
20 KB"] end subgraph Modified["Fichier Modifie (+1 byte dans B)"] M1["Chunk A
12 KB"] M2["Chunk B'
19 KB"] M3["Chunk C
14 KB"] M4["Chunk D
20 KB"] end O1 -->|"identique"| M1 O2 -.->|"different"| M2 O3 -->|"identique"| M3 O4 -->|"identique"| M4 style O1 fill:#14532d,stroke:#22c55e style M1 fill:#14532d,stroke:#22c55e style O3 fill:#14532d,stroke:#22c55e style M3 fill:#14532d,stroke:#22c55e style O4 fill:#14532d,stroke:#22c55e style M4 fill:#14532d,stroke:#22c55e style O2 fill:#7f1d1d,stroke:#ef4444 style M2 fill:#7f1d1d,stroke:#ef4444

Algorithme FastCDC

  1. Initialisation :
    • min_size = 4 KB, max_size = 64 KB, avg_size = 16 KB
    • mask_s = calculer_masque(avg_size * 2) -- pour normalisation
    • mask_l = calculer_masque(avg_size / 2)
  2. Pour chaque position dans le fichier :
    • Si position < min_size : continuer
    • Calculer fp = gear_hash(byte) avec table de lookup
    • Si position < avg_size : utiliser mask_s (plus strict)
    • Sinon : utiliser mask_l (plus permissif)
    • Si (fp & mask) == 0 OU position >= max_size :
      • Frontiere trouvee, creer chunk

Gear Hash (Rolling Hash)

Principe du Gear Hash
flowchart LR subgraph Window["Fenetre glissante"] B1["byte[i]"] B2["byte[i+1]"] B3["byte[i+2]"] BN["..."] end subgraph Gear["Gear Hash"] TABLE["Table[256]
valeurs aleatoires"] SHIFT["fp = (fp << 1) + Table[byte]"] end subgraph Check["Verification"] MASK["fp & MASK == 0 ?"] YES["Frontiere !"] NO["Continuer"] end Window --> Gear Gear --> Check MASK --> YES MASK --> NO
Parametre CDC Valeur defaut Impact
min_size 4 KB Chunks minimum (evite fragmentation)
avg_size 16 KB Taille moyenne cible
max_size 64 KB Chunks maximum (garantit progression)
normalization_level 2 Niveaux de masque (1, 2 ou 3)

Comparaison Fixed vs CDC

Taux de deduplication selon le mode
xychart-beta title "Taux de deduplication (%)" x-axis ["Backup VM", "Repos Git", "Documents", "Logs", "Media"] y-axis "%" 0 --> 100 bar [85, 62, 45, 78, 12] bar [92, 71, 58, 82, 15]
Critere Fixed Chunking FastCDC
Vitesse Tres rapide Rapide (10-20% plus lent)
Taux deduplication Bon Excellent (+10-15%)
Resilience edits Faible Excellente
Cas d'usage ideal Images VM, ISO Backups, documents

2. Hachage Hierarchique

Pour garantir zero collision tout en maintenant des performances elevees, DRAGON utilise un schema de hachage hierarchique a deux niveaux.

Schema Hash 256-bit (2x128-bit)
flowchart TB subgraph Input["Chunk Data"] DATA["16 KB de donnees"] end subgraph Level1["Niveau 1 : Hash Rapide"] XXH["XXH3-128
~30 GB/s"] H1["Hash primaire
128 bits"] end subgraph Level2["Niveau 2 : Hash Crypto"] SHA["SHA-256
tronque"] H2["Hash secondaire
128 bits"] end subgraph Combined["Hash Combine"] HIER["Hash256
= H1 || H2
256 bits"] end DATA --> XXH DATA --> SHA XXH --> H1 SHA --> H2 H1 --> HIER H2 --> HIER

Pourquoi deux hash ?

XXH3-128 : Extremement rapide, ideal pour le lookup initial. Probabilite de collision : 1 / 2^128 (negligeable mais non nulle sur des billions de chunks).

SHA-256 : Cryptographiquement sur. En combinant les deux, la probabilite de double collision tombe a 1 / 2^256, soit essentiellement zero.

Algorithme de verification de doublon

  1. Calculer hash_primaire = XXH3-128(chunk)
  2. Consulter Bloom Filter avec hash_primaire :
    • Si absent : chunk nouveau (certain), ajouter a l'index
    • Si present : potentiel doublon, verifier
  3. Rechercher hash_primaire dans B+Tree :
    • Si non trouve : faux positif Bloom, chunk nouveau
    • Si trouve : verifier hash_secondaire
  4. Comparer hash_secondaire :
    • Si identique : doublon confirme (probabilite erreur ~0)
    • Si different : collision primaire, chunk nouveau
Algorithme Taille Debit GPU Usage
XXH3-128 128 bits ~180 GB/s Lookup primaire rapide
SHA-256 256 bits (tronque 128) ~18 GB/s Verification secondaire
Hash256 combine 256 bits ~15 GB/s Identification unique finale

3. Indexation

L'indexation permet de retrouver rapidement si un hash existe deja. DRAGON combine un Bloom Filter pour le pre-filtrage et un B+Tree pour la recherche exacte.

Bloom Filter Hierarchique

Structure du Bloom Filter
flowchart TB subgraph Query["Requete"] HASH["Hash a verifier"] end subgraph Bloom["Bloom Filter (GPU)"] subgraph Functions["k=4 fonctions hash"] F1["h1(hash) mod m"] F2["h2(hash) mod m"] F3["h3(hash) mod m"] F4["h4(hash) mod m"] end subgraph BitArray["Tableau de bits (256 MB)"] B1["bit[pos1]"] B2["bit[pos2]"] B3["bit[pos3]"] B4["bit[pos4]"] end end subgraph Result["Resultat"] ALL1["Tous = 1
Peut-etre present"] ANY0["Au moins un = 0
Certainement absent"] end HASH --> Functions F1 --> B1 F2 --> B2 F3 --> B3 F4 --> B4 BitArray --> ALL1 BitArray --> ANY0

Parametres Bloom

  • Taille : 256 MB (2 milliards bits)
  • k = 4 fonctions de hachage
  • Taux faux positifs : ~1%
  • Capacite : ~100 millions chunks

Hierarchie (niveaux)

  • Niveau 0 : Hot (recent, en RAM GPU)
  • Niveau 1 : Warm (RAM CPU)
  • Niveau 2 : Cold (SSD/HDD)
  • Promotion/demotion automatique

B+Tree GPU Index

Structure B+Tree optimisee GPU
flowchart TB subgraph Root["Noeud Racine"] R["Keys: [K1, K2, K3]
Children: [P0, P1, P2, P3]"] end subgraph Internal["Noeuds Internes"] I1["Keys: [...]
Children: [...]"] I2["Keys: [...]
Children: [...]"] I3["Keys: [...]
Children: [...]"] end subgraph Leaves["Feuilles (donnees)"] L1["Hash256 -> BlockRef"] L2["Hash256 -> BlockRef"] L3["Hash256 -> BlockRef"] L4["Hash256 -> BlockRef"] NEXT["next ->"] end R --> I1 R --> I2 R --> I3 I1 --> L1 I1 --> L2 I2 --> L3 I3 --> L4 L1 --> NEXT NEXT --> L2

Algorithme de recherche B+Tree

  1. Descente : Depuis la racine, comparer la cle avec les separateurs
    • Recherche binaire dans le noeud (O(log b))
    • Suivre le pointeur vers l'enfant
  2. Feuille : Recherche binaire dans les cles
    • Si trouve : retourner BlockRef
    • Si non trouve : cle absente
  3. Complexite : O(log_b N) avec b = branching factor (~128)
Parametre B+Tree Valeur Impact
Branching factor 128 Profondeur ~4 pour 1 milliard cles
Taille noeud 4 KB Aligne sur page GPU
Cache L1 GPU Top 3 niveaux Acces quasi-instantane
Bulk loading Oui Construction rapide depuis tries

Pipeline de deduplication complet

Flux complet avec probabilites
flowchart TB START["Chunk a analyser"] --> BLOOM BLOOM{"Bloom Filter
present ?"} BLOOM -->|"Non (99%)"| NEW1["Chunk NOUVEAU
Ajouter a index"] BLOOM -->|"Oui (1%)"| BTREE BTREE{"B+Tree
hash primaire ?"} BTREE -->|"Non trouve"| FP["Faux positif Bloom
Chunk NOUVEAU"] BTREE -->|"Trouve"| CHECK CHECK{"Hash secondaire
identique ?"} CHECK -->|"Non"| COLLISION["Collision primaire
(~0%, chunk nouveau)"] CHECK -->|"Oui"| DUP["Chunk DOUBLON
Stocker reference"] NEW1 --> UPDATE["Mettre a jour
Bloom + B+Tree"] FP --> UPDATE COLLISION --> UPDATE style NEW1 fill:#14532d,stroke:#22c55e style FP fill:#14532d,stroke:#22c55e style COLLISION fill:#14532d,stroke:#22c55e style DUP fill:#1e40af,stroke:#3b82f6

Analyse de complexite

Pour N chunks totaux dont D sont des doublons :

  • Bloom lookup : O(k) = O(1) constant
  • B+Tree lookup : O(log N) - seulement si Bloom positif
  • Cas moyen : ~99% des nouveaux chunks s'arretent au Bloom
  • Memoire : Bloom 256 MB + B+Tree ~32 bytes/chunk

Pour aller plus loin

Acceleration GPU >

Comment ces algorithmes sont parallelises sur GPU.

Mode distribue >

Scalabilite avec index distribue.

Architecture >

Integration dans le systeme global.