Qualcuno veramente ordina terabyte di dati?

Question

Recentemente ho parlato con qualcuno che lavora per Amazon e mi ha chiesto: come farei per smistare i terabyte di dati usando un linguaggio di programmazione?

Sono un ragazzo C++ e, naturalmente, abbiamo parlato di merge sort e una delle possibili tecniche è quella di dividere i dati in dimensioni più piccole e ordinare ciascuno di essi e unirli infine.

Ma in realtà, aziende come Amazon o eBay ordinano terabyte di dati? Lo so, memorizzano un'infinità di informazioni, ma le ordinano?

In poche parole, la mia domanda è: perché non dovrebbero tenerli ordinati in primo luogo, invece di ordinare terabyte di dati?

Answer 1

Sì, alcune aziende certamente ordinano almeno tanti dati ogni giorno.

Google ha un framework chiamato MapReduce che suddivide il lavoro - come un tipo di unione - su diverse caselle e gestisce gli errori hardware e di rete in modo fluido.

Hadoop è un progetto Apache simile che puoi giocare con te stesso, per abilitare la suddivisione di un algoritmo di ordinamento su un cluster di computer.

Answer 2

Ma in realtà, le aziende come Amazon/Ebay, ordinano terabyte di dati? I so, memorizzano tonnellate di informazioni ma ordinandole ???

Sì. L'ultima volta che ho controllato Google elaboratoover 20 petabytes di dati al giorno.

perché non dovrebbero tenerli ordinato al primo luogo, invece di smistamento terabyte di dati, è la mia domanda in un poche parole.

MODIFICA: relet rappresenta un ottimo punto; devi solo mantenere gli indici e ordinarli. È possibile recuperare in modo facile ed efficiente i dati di ordinamento in questo modo. Non è necessario ordinare l'intero set di dati.

Answer 3

Ogni indice di database è una rappresentazione ordinata di una parte dei dati. Se lo indicizzate, ordinate le chiavi, anche se non necessariamente riordinate l'intero set di dati.

Answer 4

I set di dati scientifici possono facilmente essere inclusi in terabyte. Puoi ordinarli e memorizzarli in un modo (diciamo per data) quando raccogli i dati. Tuttavia, a un certo punto qualcuno vorrà che i dati siano ordinati con un altro metodo, ad es. dalla latitudine se stai usando i dati sulla Terra.

Answer 5

Considerare i dati di registro dai server, Amazon deve disporre di un'enorme quantità di dati. I dati del registro vengono generalmente memorizzati così come vengono ricevuti, cioè ordinati in base al tempo. Pertanto, se lo si desidera ordinare per prodotto, è necessario ordinare l'intero set di dati.

Un altro problema è che molte volte i dati devono essere ordinati in base ai requisiti di elaborazione, che potrebbero non essere noti in anticipo.

Ad esempio: Sebbene non sia un terabyte, di recente ho ordinato circa 24 GB di dati di rete follower su Twitter utilizzando l'ordinamento di tipo merge. L'implementazione che ho usato è stata del Prof. Dan Lemire.

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

I dati sono stati ordinati in base a ID utente e ogni linea conteneva userid seguito da userid di persona che lo segue. Tuttavia nel mio caso volevo dati su chi segue chi. Così ho dovuto riordinarlo di nuovo dal secondo userid in ogni riga.

Tuttavia per l'ordinamento di 1 TB, utilizzare la riduzione della mappa utilizzando Hadoop. Ordinamento è il passo predefinito dopo la funzione mappa. Quindi sceglierei la funzione mappa come identità e NESSUNO per ridurre la funzione e impostare i lavori di streaming.

Hadoop utilizza HDFS che memorizza i dati in enormi blocchi di 64 MB (questo valore può essere modificato). Di default esegue una singola mappa per blocco. Dopo che la funzione mappa è stata eseguita, l'output della mappa viene ordinato, credo per un algoritmo simile all'unione sort.

Ecco il link per il mapping identità: http://hadoop.apache.org/common/docs/r0.16.4/api/org/apache/hadoop/mapred/lib/IdentityMapper.html

Se si desidera ordinare qualche elemento in quei dati poi mi avrebbe fatto che elemento chiave nel XXX e la linea come valore di uscita della mappa .

Answer 6

Sì. Alcune aziende lo fanno. O forse anche individui. Puoi prendere commercianti ad alta frequenza come esempio. Alcuni di loro sono ben noti, dice Goldman Sachs. Eseguono algoritmi molto sofisticati contro il mercato, tenendo conto dei dati relativi ai tick negli ultimi due anni, ovvero ogni variazione nell'offerta di prezzo, i prezzi degli scambi reali (scambiano AKA come stampe), ecc. Per strumenti altamente volatili, come gli stock , i futures e le opzioni, ci sono gigabyte di dati ogni giorno e devono fare ricerche scientifiche sui dati per migliaia di strumenti negli ultimi due anni. Per non parlare delle notizie relative al mercato, alle condizioni meteorologiche e persino alla fase lunare. Quindi, sì, ci sono ragazzi che ordinano terabyte di dati. Forse non tutti i giorni, ma ancora, lo fanno.

Answer 7

Le grandi società ordinano regolarmente tera e petabyte di dati. Ho lavorato per più di una società. Come ha affermato Dean J, le aziende si affidano a framework costruiti per gestire tali compiti in modo efficiente e coerente. Pertanto, gli utenti dei dati non devono implementare il proprio ordinamento. Ma le persone che hanno costruito il framework hanno dovuto capire come fare certe cose (non solo l'ordinamento, ma l'estrazione delle chiavi, l'arricchimento, ecc.) Su larga scala. Nonostante tutto, potrebbero esserci situazioni in cui sarà necessario implementare il proprio ordinamento. Ad esempio, di recente ho lavorato a progetti di dati che comportavano l'elaborazione di file di registro con eventi provenienti da app mobili. Per le politiche di sicurezza/privacy, alcuni campi nei file di registro dovevano essere crittografati prima che i dati potessero essere spostati per un'ulteriore elaborazione. Ciò significava che per ogni riga veniva applicato un algoritmo di crittografia personalizzato. Tuttavia, poiché il rapporto tra Encrypted e gli eventi era elevato (lo stesso valore di campo appare centinaia di volte nel file), era più efficiente ordinare il file per primo, crittografarlo, memorizzare il risultato per ogni valore ripetuto.