Est-ce que quelqu'un trie vraiment des téraoctets de données?

Question

J'ai récemment parlé à quelqu'un qui travaille pour Amazon et il m'a demandé: Comment procéder pour trier des téraoctets de données en utilisant un langage de programmation? Je suis un gars C++ et bien sûr, nous avons parlé de tri par fusion et l'une des techniques possibles est de diviser les données en plus petite taille et de trier chacune d'entre elles et de les fusionner finalement.

Mais en réalité, des sociétés comme Amazon ou eBay trient téraoctets de données? Je sais, ils stockent des tonnes d'informations, mais les trient-ils? En résumé, ma question est la suivante: pourquoi ne les tiendraient-ils pas triés au départ, au lieu de trier des téraoctets de données?

Answer 1

Oui, certaines entreprises trient certainement au moins autant de données chaque jour.

Google a un framework appelé MapReduce qui répartit le travail - comme un tri de fusion - sur différentes boîtes, et gère les défaillances matérielles et réseau en douceur.

Hadoop est un projet Apache similaire à celui que vous pouvez utiliser pour vous permettre de diviser un algorithme de tri sur un cluster d'ordinateurs.

Answer 2

Mais en réalité, est-ce que les entreprises aiment Amazon/Ebay, trier des téraoctets de données? Je sais, ils stockent des tonnes d'informations mais les triant ???

Oui. La dernière fois que j'ai vérifié Google traitéesover 20 petabytes des données quotidienne.

Pourquoi ne seraient-ils les garder à Sorted premier lieu au lieu de trier téraoctets de données, est ma question en quelques mots .

EDIT: relet fait un très bon point; il suffit de garder des index et de les trier. Vous pouvez récupérer facilement et efficacement les données de tri de cette manière. Vous n'avez pas à trier tout le jeu de données.

Answer 3

Chaque index de base de données est une représentation triée de certaines parties de vos données. Si vous l'indexez, vous triez les clés, même si vous ne réorganisez pas nécessairement l'intégralité du jeu de données.

Answer 4

Les jeux de données scientifiques peuvent facilement fonctionner en téraoctets. Vous pouvez les trier et les stocker d'une certaine manière (disons par date) lorsque vous rassemblez les données. Cependant, à un certain moment, quelqu'un voudra que les données soient triées par une autre méthode, par ex. par la latitude si vous utilisez des données sur la Terre.

Answer 5

Considérer les données de journal des serveurs, Amazon doit avoir une énorme quantité de données. Les données du journal sont généralement stockées telles qu'elles sont reçues, c'est-à-dire triées en fonction du temps. Ainsi, si vous voulez trier par produit, vous devrez trier l'ensemble des données.

Un autre problème est que plusieurs fois les données doivent être triées en fonction des besoins de traitement, ce qui peut ne pas être connu à l'avance. Par exemple: Bien qu'il ne s'agisse pas d'un téraoctet, j'ai récemment trié environ 24 Go de données de réseau suiveur Twitter en utilisant le tri par fusion. L'implémentation que j'ai utilisée était celle du Prof Dan Lemire.

http://www.daniel-lemire.com/blog/archives/2010/04/06/external-memory-sorting-in-java-the-first-release/

Les données ont été classées d'après les userids et chaque ligne contenait userid suivie userid de la personne qui le suit. Cependant, dans mon cas, je voulais des données sur qui suit qui. J'ai donc dû trier à nouveau par second ID utilisateur dans chaque ligne. Cependant, pour le tri de 1 To, j'utiliserais map-reduce avec Hadoop. Le tri est l'étape par défaut après la fonction de carte. Ainsi, je choisirais la fonction de carte pour être identité et NONE pour réduire la fonction et configurer les tâches de streaming.

Hadoop utilise HDFS qui stocke les données dans des blocs énormes de 64 Mo (cette valeur peut être modifiée). Par défaut, il exécute une carte unique par bloc. Une fois la fonction map exécutée, la sortie de map est triée, je suppose par un algorithme similaire au tri par fusion.

Voici le lien vers le mappeur d'identité: http://hadoop.apache.org/common/docs/r0.16.4/api/org/apache/hadoop/mapred/lib/IdentityMapper.html

Si vous voulez trier un élément dans ces données puis je faire de cet élément une clé dans XXX et la ligne en tant que valeur en sortie de la carte .

Answer 6

Oui. Certaines entreprises le font. Ou peut-être même des individus. Vous pouvez prendre les commerçants à haute fréquence à titre d'exemple. Certains d'entre eux sont bien connus, disent Goldman Sachs. Ils utilisent des algorithmes très sophistiqués contre le marché, en tenant compte des données des ticks des dernières années, à savoir tous les changements dans l'offre de prix, les prix réels (AKA comme impressions), etc. Pour les instruments très volatils tels que les actions , contrats à terme et options, il y a des gigaoctets de données tous les jours et ils doivent faire des recherches scientifiques sur des données pour des milliers d'instruments au cours des deux dernières années. Sans parler des nouvelles qu'ils corrèlent avec le marché, les conditions météorologiques et même la phase de la lune. Donc, oui, il y a des gars qui trient des téraoctets de données. Peut-être pas tous les jours, mais quand même, ils le font.

Answer 7

Les grandes entreprises trient régulièrement les tera et pétaoctets de données. J'ai travaillé pour plus d'une entreprise. Comme l'a dit Dean J, les entreprises s'appuient sur des cadres conçus pour gérer de telles tâches de manière efficace et cohérente. Ainsi, les utilisateurs des données n'ont pas besoin d'implémenter leur propre tri. Mais les personnes qui ont construit le cadre ont dû comprendre comment faire certaines choses (pas seulement le tri, mais l'extraction des clés, l'enrichissement, etc.) à grande échelle. Malgré tout cela, il pourrait y avoir des situations où vous devrez mettre en place votre propre tri. Par exemple, j'ai récemment travaillé sur un projet de données impliquant le traitement de fichiers journaux avec des événements provenant d'applications mobiles. Pour les stratégies de sécurité/confidentialité, certains champs des fichiers journaux devaient être chiffrés avant que les données puissent être déplacées pour un traitement ultérieur. Cela signifiait que pour chaque ligne, un algorithme de chiffrement personnalisé était appliqué. Cependant, étant donné que le rapport Chiffrement sur événements était élevé (la même valeur de champ apparaît 100 fois dans le fichier), il était plus efficace de trier le fichier, de chiffrer la valeur, de mettre en cache le résultat pour chaque valeur répétée.