Come faccio per la deduplicazione dei dati su scala?

Hashing?

Essential.

using divide and conquer type algorithms to exploit parallelism?

Se necessario.

Considera questo.

Hai già milioni di righe nel DB. Ogni riga deve avere un singolo campo PK surrogato che sia (idealmente) un numero. Ogni riga contiene anche i campi chiave utilizzati per il rilevamento dei duplicati.

1. Calcola un hash dei vari campi chiave di confronto. Carica hash e PK in una hashmap (o treemap) in memoria. Questo è 2 milioni di pochi megabyte di memoria. Quasi niente su un processore ragionevolmente moderno. La parte più lenta sta calcolando l'hash di milioni di righe.

2. Ogni riga in entrata viene controllata rispetto all'hashmap. Se è nella mappa, i tasti di confronto indicano un duplicato. Se non è nella mappa, va bene.

Questo dovrebbe coprire la maggior parte delle basi. Le probabilità di una collisione "falsa positiva" sono davvero ridotte. E (per eventuali duplicati) devi semplicemente ripetere il controllo per confermare che le loro chiavi sono effettivamente un duplicato.

Se i campi chiave di confronto sono chiavi corrette, non possono essere aggiornati. È possibile denormalizzare l'intera mappa hash chiave PK al di fuori del database ed evitare di ricostruirla.

Se i campi delle chiavi di confronto sono attributi (e possono essere aggiornati), è necessario gestire denormalizzazione dei valori hash con garbo. Una modifica a una chiave di confronto modifica i valori hash. Calcolalo al momento dell'aggiornamento e salva un ricordo di questo cambiamento in modo che l'hash di confronto possa essere ottimizzato senza essere ricostruito da zero.

Penso che l'hashing sia la strada da percorrere. Ricerca rapida & inserzioni veloci. Lo proverei già direttamente. I record di 100 milioni non mi sembrano così tanti ... ma ovviamente ci vorranno molte ore.

Se necessario, un modo per dividere il carico di lavoro è dividere i dati in pacchetti di hash. Ad esempio, il numero di PC i legge tutti i record con hash_value % N == i e quindi inserisce / rifiuta tutti i record aggiuntivi che hanno anche hash_value % N == i . Una volta che hai finito, unisci i set di dati N e ottieni il risultato.

Modifica:

Un modo per renderlo leggermente più efficiente consiste nell'utilizzare 2 hash. Un hash facile e veloce, su un singolo campo, ad esempio, utilizzato per un filtro rapido hash % N == i . E un normale hash per l'effettivo inserimento / ricerca nel database stesso.

Potresti voler esaminare una funzione di cancellatura hash . Con uno, è possibile calcolare l'hash di una determinata finestra di byte, quindi "rollarlo" di un byte in avanti per trovare l'hash della successiva finestra di byte:

Hello world
[    ]
 [    ]
  [    ]
   [    ]
    [    ]
     [    ]

Se il tuo compito è creare un archivio oggetti che funzioni con blob binari, puoi fare qualcosa di simile:

• Conserva una tabella hash di blocchi di dimensioni fisse (in questo esempio, blocchi di 64 byte e hash a 32 bit).

• Quando viene inserito un nuovo blob, cancellarlo ogni 64 byte e memorizzare ciascun blocco nella tabella hash. "Comprimi" il blob codificandolo come una matrice di hash e stringhe. Tieni presente la possibilità di collisioni di hash.

  ------------------------------
  [1fedccba][deadbeef][13579ace]
  

• Quando viene inserito un blob successivo, esegui il rollover per trovare i blocchi che abbiamo già:

  ---------------------------
  [a7ed8842]
   [cb438564]
    [e5fe0527]
     [c2ff4713]
      [1fedccba] *** Chunk matches one we already have.
                [793bd55d]
                 [45a39f7e]
                  [dace4e10]
                   [ee6fcc7b]
  

Questa tecnica può essere utilizzata per deduplicare blocchi di dati anche in presenza di inserimenti e cancellazioni, o variazioni di allineamento dovute alla serializzazione.

Per deduplicare valori esattamente uguali, (piuttosto che quasi uguali), puoi semplicemente usare un dizionario codificato da un hash crittografico . Esempio, utilizzando i tipi di PostgreSQL:

CREATE TABLE dictionary (
    sha256 BYTEA PRIMARY KEY,
    value  BYTEA
);

Il vantaggio di ciò è che rende l'operazione di ricerca molto più veloce. Piuttosto che confrontare intere stringhe (che potrebbero potenzialmente essere molto grandi), stai semplicemente confrontando i valori a 256 bit (32 byte).

Questo presuppone che non incontrerai mai due stringhe diverse con lo stesso hash SHA-256 . Sebbene tali coppie di stringhe esistano in teoria a causa del principio pidgenhole, un hash SHA-256 è solo a 256 bit, mentre una stringa di byte può essere (e in genere lo sarà) molto più a lungo - nessuno ha trovato tale coppia.

Se i tuoi valori non sono stringhe di byte, dovrai trovare un modo per serializzarli .

Prova a utilizzare MapReduce .

modifica : Ecco una voce wiki sulla mappa ridurre. Ecco come vorrei andare utilizzando la mappa ridurre su questa attività:

La funzione Mappatura mapperebbe l'elemento a se stesso (ad esempio, restituisce una coppia). La funzione Riduci, per una coppia di elementi duplicati, eliminerebbe uno degli elementi.