Кто-то действительно сортирует терабайты данных?
Недавно я поговорил с кем-то, кто работает на Amazon, и он спросил меня: как бы я отсортировал терабайты данных с использованием языка программирования?
Я - парень C ++ и, конечно, мы говорили о сортировке слиянием, и один из возможных методов - разделить данные на меньшие по размеру, отсортировать каждый из них и объединить их окончательно.
Но на самом деле, делайте такие компании, как Amazon или eBay сортируют терабайты данных? Я знаю, что они хранят тонны информации, но сортируют ли они их?
В двух словах, мой вопрос: почему они не будут хранить их в первую очередь, вместо того, чтобы сортировать терабайты данных?
6 ответов
Да, некоторые компании определенно сортируют по крайней мере такой объем данных каждый день.
У Google есть структура под названием MapReduce , которая разделяет работу - как сортировка слиянием - на разные блоки и плавно обрабатывает сбои оборудования и сети.
Hadoop - это аналогичный проект Apache, в который вы можете играть сами, чтобы включить разделение алгоритма сортировки по кластеру компьютеров.
Да. Некоторые компании это делают. Или, может быть, даже отдельные лица. В качестве примера можно взять высокочастотных трейдеров. Некоторые из них хорошо известны, говорит Goldman Sachs. Они запускают очень сложные алгоритмы работы с рынком, принимая во внимание тиковые данные за последние пару лет, то есть каждое изменение ценового предложения, реальных цен сделок (торгуются как отпечатки) и т. Д. Для инструментов с высокой волатильностью, таких как акции. , фьючерсы и опционы, ежедневно поступают гигабайты данных, и им приходится проводить научные исследования данных для тысяч инструментов за последние пару лет. Не говоря уже о новостях о том, что они коррелируют с рынком, погодными условиями и даже фазой луны. Так что да, есть ребята, которые сортируют терабайты данных. Может быть, не каждый день, но тем не менее, они делают.
Рассмотрим данные журнала с серверов, Amazon должен иметь огромный объем данных. Данные журнала обычно хранятся по мере поступления, то есть сортируются по времени. Таким образом, если вы хотите отсортировать данные по продуктам, вам нужно будет отсортировать весь набор данных.
Другая проблема заключается в том, что во многих случаях данные необходимо сортировать в соответствии с требованиями обработки, которые могут быть неизвестны заранее.
Например: я недавно отсортировал около 24 ГБ данных сети подписчиков Twitter, используя сортировку слиянием. Реализация, которую я использовал, принадлежит профессору Дэну Лемайру.
Данные были отсортированы в соответствии с ИД пользователя, и каждая строка содержит ИД пользователя, за которым следует ИД пользователя, который следует за ним.Однако в моем случае мне нужны были данные о том, кто за кем следует. Таким образом, мне пришлось снова отсортировать его по второму идентификатору пользователя в каждой строке.
Однако для сортировки 1 ТБ я бы использовал map-reduce, используя Hadoop . Сортировка - это шаг по умолчанию после функции карты. Таким образом, я бы выбрал функцию карты для идентификации и NONE в качестве функции сокращения и настройки потоковых заданий.
Hadoop использует HDFS , который хранит данные в огромных блоках по 64 МБ (это значение можно изменить). По умолчанию он запускает одну карту для каждого блока. После запуска функции карты вывод карты сортируется, я думаю, по алгоритму, аналогичному сортировке слиянием.
Вот ссылка на средство сопоставления личности: http://hadoop.apache.org/common/docs/r0.16.4/api/org/apache/hadoop/mapred/lib/IdentityMapper.html
Если вы хотите отсортировать по какому-либо элементу в этих данных тогда я бы сделал этот элемент ключом в XXX, а строку - значением как выводом карты.
Наборы научных данных легко могут занимать терабайты. Вы можете отсортировать их и сохранить одним способом (например, по дате) при сборе данных. Однако в какой-то момент кто-то захочет, чтобы данные были отсортированы другим методом, например по широте, если вы используете данные о Земле.
Но на самом деле компаниям нравится Amazon / Ebay, сортировать терабайты данных? я знаете, они хранят тонны информации, но сортируя их ???
Да. В прошлый раз, когда я проверял, Google обрабатывал более 20 петабайт данных ежедневно .
Почему бы им не отсортировать их по первое место вместо сортировки терабайты данных, мой вопрос в в двух словах.
РЕДАКТИРОВАТЬ: relet делает очень хорошее замечание; вам нужно только сохранить индексы и отсортировать их. Таким образом вы можете легко и эффективно извлекать отсортированные данные. Вам не нужно сортировать весь набор данных.
Каждый индекс базы данных - это отсортированное представление некоторой части ваших данных. Если вы индексируете его, вы сортируете ключи - даже если вы не обязательно упорядочиваете весь набор данных.