Avec un jeu de données de 1 To sur le disque avec environ 1 Ko par enregistrement de données, comment puis-je trouver des doublons avec 512 Mo de RAM et un espace disque infini?

Question

Il y a 1 To de données sur un disque avec environ 1 Ko par enregistrement de données. Comment trouver des doublons avec 512 Mo de RAM et un espace disque infini?

Answer 1

Les solutions proposées jusqu'à présent semblent trop compliquées. Un filtre de Bloom, tout en étant la structure de données du jour pour la dernière plusieurs années, n'est pas recommandé de les appliquer dans une situation comme celle-ci: parce que les données ne peuvent être associés avec le haché de contenu, vous devez non seulement de maintenir la Floraison de filtre, mais vous devez toujours enregistrer chacun (seulement 6 bits!) la valeur de hachage et d'enregistrer sur le disque, de le détruire au profit de la prolifération de filtre et d'avoir un aberrante haut taux de collision.

D'autre part, de fusion et le tri de l'ensemble du téraoctet n'est pas seulement O(n log n) des comparaisons, mais O(n log n) du trafic sur le disque, puisque la majorité des fichiers intermédiaires devraient être fusionnées à partir du disque, plutôt que de la mémoire. Toute solution réelle doit essayer de réduire le trafic sur le disque autant que possible, puisque c'est notre principal goulot d'étranglement.

Ma solution est simple, faire une hypothèse: que le téraoctet de données est enregistré dans ce qui est effectivement un fichier.

Itérer sur les registres de l'téraoctets de fichiers et de hachage. Un hachage cryptographique est inutile, coûteux et trop grand ici; au lieu de cela, utilisez quelque chose comme la version 64 bits de murmurhash. Il peut hachage de plus de 2 Go/sec (bien plus rapide que nous allons probablement besoin, compte tenu de la vitesse de stockage de ces jours) et a d'excellentes (mais pas cryptographique sécurisé) collision de la résistance. Avec une version 64 bits de hachage, nous nous attendons à ce que nos premières collisions à 2^32, il est donc probable que notre-environ un milliard d'enregistrements n'aura pas de collisions.

Écrire les hachages et leur enregistrement associé décalages vers un autre fichier. Depuis le registre contient des données binaires arbitraires, nous ne pouvons pas compter sur Unix en quelque sorte(1) pour faire le tri, parce que certains des hachages et les décalages peuvent contenir ce genre(1) s'interpréter comme des retours à la ligne. Nous allons tout simplement écrire les enregistrements comme à largeur fixe (probablement 16 octets: 8 octets pour les murmur2 64 bits de hachage, et 8 octets pour le décalage dans le téraoctet de fichier) de dossiers. Le fichier qui en résulte devrait être d'environ 16 GO, compte tenu de notre nombre d'enregistrements.

Nous pouvons faire le tri de ce fichier en lecture le nombre d'enregistrements qui seront en toute sécurité tenir en mémoire et de les trier, les bouffées de chaleur le tri des morceaux sur le disque. Nous pouvons adapter à plusieurs enregistrements dans la mémoire avec une heapsort (il utilise O(1) de l'espace) qu'avec une quicksort (qui utilise O(log n) de la mémoire de la pile d'appel), mais dans la plupart des implémentations, quicksort victoires en vertu de sa localité de mémoire et inférieure de l'instruction de comptage. Ces fichiers intermédiaires (il devrait être de 35 à 40 d'entre eux) seront écrites sur le disque.

La dernière étape consiste à fusionner ces fichiers (à la mémoire; il n'y a pas besoin de stocker un résultat sur le disque pour cela), la collecte de toutes les collisions de hachage et de rechercher les enregistrements associés dans le téraoctet de fichier, en comparant les enregistrements pour la duplication et l'émission les dossiers (ou les décalages) quelle que soit la façon dont le problème précise.

Aussi loin que je peux dire, cette tâche frappe le disque de manière significative moins que toute autre solution, et c'est très conceptuel simple: hash les dossiers, rechercher les doublons dans les tables de hachage, et vérifier dans les enregistrements réels.

Pour le disque I/O, il serait lire la téraoctet de données de fichier, écrire 16 GO de disque, lire que de 16 GO de disque et l'écrire triés, puis de le lire et de retourner les doublons. Comme une optimisation, le processus de hachage les enregistrements peuvent s'accumuler dans la mémoire avant de les débusquer sur le disque, de les trier avant de le faire: qui coupe les 16 GO de fichier intermédiaire, et permet au processus de se déplacer à partir de hachage directement de la fusion et de reporting des doublons.

Answer 2

Utiliser un filtre de Bloom: un tableau de simultanée des hachages. Selon Wikipedia, le nombre optimal de hachages est - ln(2) * 2^32 / 2^30 ≈ 2.77 ≈ 3. (Hmm, en branchant 4 donne moins de faux positifs, mais 3 est encore mieux pour cette application.) Cela signifie que vous avez un tableau de 512 mo ou 4 gigabits, et le traitement de chaque dossier ensembles de trois nouveaux bits dans cette vaste mer. Si tous les trois bits étaient déjà ensemble, c'est une possibilité de correspondance. Enregistrer les trois hachage des valeurs dans un fichier. Sinon, de les enregistrer dans un autre fichier. Remarque l'enregistrement de l'index le long à chaque match.

(Si 5% de taux d'erreur est tolérable, omettre le gros fichier et utiliser le fichier de petite taille, comme votre résultats.)

Lorsque vous avez terminé, vous devriez avoir un fichier d'environ 49 millions de positif correspond à un fichier de 975M négatifs qui peut encore correspondre positifs. Lire l'ancien en vector<pair<vector<uint32_t>,vector<uint32_t> > > (index dans le dernier vector, l'ancien peut être un array) et de tri. Mettre l'index dans un autre vector<uint32_t>; ils sont déjà triés. Lire le fichier de grande taille, mais au lieu de définir les bits d'une table, de trouver les valeurs de hachage dans l' vector. (Par exemple, equal_range.) Utilisez la liste de positif-fichier des indices pour suivre l'index de l'enregistrement courant dans le négatif fichier. Si aucune correspondance trouvée, l'ignorer. Sinon, ajouter l'enregistrement de l'indice match->second.push_back(current_negative_record_index).

Enfin, parcourir la carte et les vecteurs des indices. Toute seau avec plus d'une entrée est "presque" certains pour contenir un ensemble de doublons, mais vous avez fait tout ce chemin, afin de les regarder et de les comparer complètement pour être sûr.

Total synchrone disk I/O: (un seul passage = 1 TiB) + (96 hachage bits par enregistrement = 12 GiB) + (32 indice de bits par positif = ~200 Mo).

Montage Final (sérieusement): À la réflexion, à la prolifération de Filtre aspect pourrait ne pas être vraiment aider ici. La quantité de données de hachage est plus un facteur limitant que le nombre de faux positifs. Avec seulement une fonction de hachage, le montant total de hachage de données serait de 4 GiB et les indices de l'124 millions attendus faux positifs serait ~500 MiB. Qui devrait globalement optimiser cette stratégie.

Clarification (got un downvote): il y a une distinction entre un faux positif de la Floraison filtre et d'un hash collision. Un hash collision ne peuvent pas être résolus que par un retour aux enregistrements d'origine et de les comparer, ce qui est coûteux. Une Floraison de faux positifs peuvent être résolus par un retour à l'origine des valeurs de hachage et en les comparant, qui est ce que la seconde étape de cet algorithme. Donc, à la réflexion, celui-filtre de hachage décrit dans le "finale" modifier indûment cause de disque cherche. Deux de hachage Bloom filtre à augmenter le nombre de faux positifs se terminant en un seul seau de l' match carte, et porterait le nombre de faux positifs en arrière vers le bas pour les dizaines de millions de personnes.

Answer 3

C'est beaucoup de dossiers ;-) dans l'ordre de 1 000 000 000 d'. 'd mieux être intelligent à ce sujet...

La nature des dossiers est indéterminée: ne nous venons de découvrir, un à la fois par les lire dans l'ordre, ou est-il une sorte d'indice, ou peut-être sont-ils stockés en tant que fichiers dans différents répertoires? Aussi non précisé dans la question, la disponibilité d'un sgbd que l'on peut utiliser pour l'indice de structure de données (plutôt que d'avoir à les trier avec notre propre code). Aussi un [même approximative] une idée du nombre de doublons permettrait d'aider à orienter les choix vers un processus efficace.

Si aucun index n'existe, on peut/doit créer une; ce qui pourrait être fait dans les premiers à passer à travers les données. La même passe serait utilisé pour produire une empreinte (hash) de toutes sortes pour chaque enregistrement (ou, éventuellement, pour des raisons d'efficacité, pour la première quelques centaines d'octets de l'enregistrement).

L'idée générale est de produire rapidement un indice qui peut être utilisé pour identifier les possibles doublons, et de finaliser la liste de réel en double, éventuellement par le biais d'un traitement parallèle.

L'info utile dans l'index serait:

• la longueur de l'enregistrement
• premiers octets du texte
• code de hachage (voir plus bas)
• aussi l'offset dans le fichier ou que ce soit pointeur vers les données, mais bien sûr, à la différence de ces 3 éléments, cela ne peut pas être utilisé pour identifier les correspondances possibles.

Le choix de la valeur de hachage est critique: doit favoriser un algorithme rapide au détriment de celui qui est parfaitement distribués; le nombre d'octets haché pour chaque enregistrement est également un compromis, peut-être 100 à 200 octets (c'est à dire environ 10 à 20% de la moyenne de la taille d'enregistrement) est une bonne valeur, en fonction du taux escompté de doublons, et selon le moment où l'enregistrement de cette offre (comparaison avec le hachage de l'ensemble de l'enregistrement). (voir modification ci-dessous)

Une fois un tel indice est disponible, nous pouvons [relativement rapidement et sans effort] obtenir un nombre de doublons possibles; sur la base de ce résultat, une deuxième phase visant à améliorer la qualité de l'index, si elle n'est pas jugée suffisamment sélectif, qui peut être fait (en laissant les dossiers qui sont facilement qualifier d'unique). Cette seconde étape peut calculer une autre de hachage, sur l'ensemble de l'enregistrement (à l'exclusion des les x premiers octets de la première de hachage), ou encore sur un autre sous-ensemble de l'enregistrement. Notez que grâce à l'index, cette seconde étape peut être multi-thread, si possible.

La deuxième ou la dernière passe de tri nécessite les enregistrements au sein d'un groupe de correspondances possibles (même longueur, même code de hachage(s), de même le premier x octets). Ceci peut être réalisé comme décrit par Pax Diablo, l'avantage de cet indice est qu'une telle opération peut, encore, être multi-thread et implique beaucoup plus petits sets (beaucoup d'entre eux). Ajouté: Ici encore, Nick Johnson fait un grand point que la deuxième phase pourrait être inutile devrions-nous utiliser un long code de hachage (il suggère de 128 octets de long SHA1). En supposant qu'il n'y a pas de gain de partiellement le hachage de l'records, c'est un très plausible solution depuis que l'indice peut résider sur le disque et encore plus rapidement triés et stockés que si nous étions de tri/stockage de l'ensemble des dossiers.

---

Edit: Nick Johnson a fait de l'excellent point que le temps de latence de cherche dans le disque de stockage peut être telle qu'une simple lecture séquentielle pour être plus rapide et que le goulot d'étranglement étant Disk I/O bound, un rapide fonction de hachage exécuté simultanément peut effectivement être plus rapide que la lecture séquentielle, et donc de ne pas ajouter à l'ensemble du processus. C'est probable (en particulier si une lecture séquentielle si effectivement nécessaire pour la détection de chaque enregistrement de début/de fin, etc.), et c'est pourquoi je "tranchant mon pari" par écrit "en fonction du gain de temps cette offre...". Cela dit, le réel de la structure des dossiers sur le disque est l'un des paramètres ouverts de la question (par exemple, si nous sommes juste en train de lire des fichiers individuels dans des répertoires, et donc d'imposer une non lecture séquentielle) et aussi un Téraoctet de la taille de stockage est probablement pris en charge par une fantaisie de RAID où chercher latence tout en restant une préoccupation est généralement beaucoup améliorée.
Je maintiens ma suggestion de deux passes approche peut être plus efficace qu'un système dans lequel chaque enregistrement est complètement haché, mais je souhaite que j'avais insisté sur la possibilité et les avantages de la un seul passage de l'approche. Comme avec beaucoup de questions d'entrevue, plusieurs caractéristiques de la situation à portée de main étaient non spécifié; l'idée n'est pas tant de voir le demandeur d'alimentation, le droit absolu répondre (même si certaines réponses peuvent être tout à fait mauvais!) mais au lieu d'avoir un aperçu de son processus de pensée et la capacité à identifier les options et les points de décision.

Answer 4

Recherchez une fonction de hachage appropriée et hachez chaque enregistrement en stockant la liste des hachages avec des index dans un fichier. Maintenant, triez le fichier de hachage par hachage. Enfin, vérifiez tous les enregistrements de hachages correspondants pour les doublons réels.

Bien sûr, cela dépend du nombre de doublons que vous espérez trouver et de ce que vous allez faire avec les informations par la suite.

Answer 5

Charger les données dans la mémoire 512M à un moment, puis trier ce morceau et de les écrire sur le disque (comme son propre fichier). Une fois l'ensemble de 1T a été fait de cette façon, de fusion-trier les fichiers individuels dans un grand honkin' fichier, puis lire que les gros (tri) fichier séquentiellement, l'écrire dans le fichier final, tout en supprimant les doublons.

1T, 512M, à un moment, sera d'environ 2,1 millions de fichiers (en supposant que le binaire définitions des unités SI, plutôt que de virgule). 512M de 1K enregistrements ne permettent 524,288 enregistrements dans la mémoire à la fois, de sorte que vous aurez probablement à faire de la fusion de tri en deux étapes. En d'autres termes, de fusion-trier les 2,1 millions de fichiers en quatre groupes pour créer des quatre plus gros fichiers, puis fusionnez-trier les quatre dans le grand fichier trié. Alors que c'est celui que vous traitez de manière séquentielle afin de supprimer les doublons.

Une fusion de tri est tout simplement la fusion de plusieurs déjà-trier les fichiers en sélectionnant simplement le premier restant de l'enregistrement de chaque fichier et de choisir la "plus faible". Par exemple, les deux fichiers a et b:

a   b
7   6
3   5
1   4
    2
 \_/
  1 (a)
  2 (b)
  3 (a)
  4 (b)
  5 (b)
  6 (b)
  7 (a)