Кто-то действительно сортирует терабайты данных?

Question

Я недавно поговорил с кем-то, кто работает в Amazon, и он спросил меня: как бы я занялся сортировкой терабайтов данных с использованием языка программирования?

Я парень C ++ и, конечно, мы говорилио сортировке слиянием, и одним из возможных методов является разделение данных на меньшие по размеру, сортировка каждого из них и окончательное слияние.

Но на самом деле, такие компании, как Amazon или eBay, сортируют терабайты данных?Я знаю, они хранят тонны информации, но сортируют ли они их?

В двух словах, мой вопрос таков: почему бы им не хранить их в первую очередь вместо сортировки терабайтов данных?

Answer 1

Но на самом деле, нравится ли компаниям Amazon / Ebay, сортировать терабайты данных? я знаете, они хранят тонны информации, но сортировка их ???

Да. В прошлый раз я проверял Google обработал более 20 петабайт данных ежедневно .

Почему бы им не хранить их в первое место вместо сортировки терабайт данных, мой вопрос в скорлупа.

РЕДАКТИРОВАТЬ: Релет делает очень хорошую точку; вам нужно только сохранить индексы и отсортировать их. Вы можете легко и эффективно получать данные сортировки таким образом. Вам не нужно сортировать весь набор данных.

Answer 2

Рассмотрим данные журналов с серверов, Amazon должен иметь огромное количество данных. Данные журнала обычно хранятся по мере их поступления, то есть сортируются по времени. Таким образом, если вы хотите отсортировать данные по продукту, вам нужно отсортировать весь набор данных.

Другая проблема заключается в том, что во многих случаях данные должны быть отсортированы в соответствии с требованиями обработки, которые могут быть неизвестны заранее.

Например: хотя и не терабайт, я недавно отсортировал около 24 ГБ данных сети Twitter-последователя, используя сортировку слиянием. Реализация, которую я использовал, была проф. Dan Lemire.

http://www.daniel -lemire.com / блог / Архивы / 2010/04/06 / внешнего памяти сортировочный-в-Java--первый-релиз /

Данные были отсортированы в соответствии с идентификаторами пользователей, и каждая строка содержала идентификатор пользователя, за которым следует идентификатор пользователя, который следует за ним. Однако в моем случае мне нужны были данные о том, кто за кем следует. Поэтому мне пришлось снова отсортировать его по второму идентификатору пользователя в каждой строке.

Однако для сортировки 1 ТБ я бы использовал map-Reduction, используя Hadoop . Сортировка - это шаг по умолчанию после функции карты. Таким образом, я бы выбрал функцию карты в качестве идентификатора, а НЕТ - в качестве функции сокращения и настройки потоковых заданий.

Hadoop использует HDFS , которая хранит данные в огромных блоках по 64 МБ (это значение можно изменить). По умолчанию он запускает одну карту на блок. После запуска функции map вывод из карты сортируется, я думаю, по алгоритму, подобному сортировке слиянием.

Вот ссылка на личность: http://hadoop.apache.org/common/docs/r0.16.4/api/org/apache/hadoop/mapred/lib/IdentityMapper.html

Если вы хотите отсортировать по какому-либо элементу в этих данных, я бы сделал этот элемент ключом в XXX, а строку в качестве значения в качестве вывода карты.

Answer 3

Да, некоторые компании, конечно, сортируют как минимум столько данных каждый день.

У Google есть фреймворк под названием MapReduce , который разбивает работу - как сортировка слиянием - на разные блоки и плавно обрабатывает аппаратные и сетевые сбои.

Hadoop - это аналогичный проект Apache, в который вы можете поиграть самостоятельно, чтобы разрешить разделение алгоритма сортировки по кластеру компьютеров.

Answer 4

Да. Некоторые компании делают. Или, может быть, даже отдельные лица. Вы можете взять высокочастотных трейдеров в качестве примера. Некоторые из них хорошо известны, говорят Goldman Sachs. Они используют очень сложные алгоритмы против рынка, принимая во внимание данные тиков за последние пару лет, то есть каждое изменение в ценовом предложении, реальных ценах сделок (торгует АКА в виде отпечатков) и т. Д. Для инструментов с высокой волатильностью, таких как акции Фьючерсы и опционы, есть гигабайты данных каждый день, и им приходится проводить научные исследования данных для тысяч приборов за последние пару лет. Не говоря уже о новостях, которые связаны с рынком, погодными условиями и даже фазой луны. Так что, да, есть ребята, которые сортируют терабайты данных. Может быть, не каждый день, но тем не менее, они делают.

Answer 5

Каждый индекс базы данных представляет собой отсортированное представление некоторой части ваших данных. Если вы индексируете его, вы сортируете ключи - даже если вы не обязательно переупорядочиваете весь набор данных.

Answer 6

Научные наборы данных могут легко столкнуться с терабайтами. Вы можете сортировать их и хранить их одним способом (скажем, по дате), когда вы собираете данные. Однако в какой-то момент кто-то захочет отсортировать данные другим способом, например, по широте, если вы используете данные о Земле.

Answer 7

Крупные компании регулярно сортируют тера и петабайты данных.Я работал в нескольких компаниях.Как сказал Дин Дж, компании полагаются на фреймворки, созданные для эффективного и последовательного решения таких задач.Таким образом, пользователям данных не нужно реализовывать собственную сортировку.Но люди, которые создали структуру, должны были понять, как делать определенные вещи (не только сортировку, но извлечение ключей, обогащение и т. Д.) В массовом масштабе.Несмотря на все это, могут возникнуть ситуации, когда вам потребуется реализовать собственную сортировку.Например, я недавно работал над проектом данных, который включал обработку файлов журнала с событиями, поступающими из мобильных приложений.Для политик безопасности / конфиденциальности определенные поля в файлах журналов должны быть зашифрованы, прежде чем данные могут быть перемещены для дальнейшей обработки.Это означало, что для каждой строки применялся собственный алгоритм шифрования.Однако, поскольку отношение Encrypted к событиям было высоким (одно и то же значение поля появляется в файле 100 раз), было бы более эффективно сначала отсортировать файл, зашифровать значение, кэшировать результат для каждого повторного значения.