На вопрос уже дан ответ, но я дам более подробный ответ с фактами, которые будут понятны всем. Я постараюсь рассказать о существующих решениях и даже о том, как их распространять, с объяснениями того, почему все вышло так, как они.
У вас есть 7 ГБ текстовый файл. Ваш диск позволяет нам передавать данные со скоростью 20 МБ / с, давайте будем пессимистичны. Это может передать все это за 350 секунд. Это меньше 6 минут.
Если предположить, что средняя строка составляет 70 символов, у нас есть 100 миллионов строк. Если наш диск вращается со скоростью 6000 об / мин, среднее вращение занимает 0,01 секунды, поэтому захват случайного фрагмента данных с диска может занять от 0 до 0,01 секунды, а в среднем - 0,005 секунды. Это называется нашим временем поиска. Если вы точно знаете, где находится каждая запись, и будете искать каждую строку, это займет у вас 0,005 с * 100 000 000 = 500 000 с, что близко к 6 дням.
Уроки
- При работе с данными на диске вы действительно хотите избежать поиска. Вы хотите передавать данные.
- Если возможно, вы не хотите, чтобы ваши данные были на диске.
Теперь стандартный способ решения этой проблемы - сортировка данных. Стандартная сортировка слиянием работает, беря блок, сортируя его, беря другой блок, сортируя его, а затем объединяя их вместе, чтобы получить больший блок. Операция слияния передает данные и записывает поток, который является именно тем шаблоном доступа, который нравится дискам. Теперь в теории с 100 миллионами строк вам потребуется 27 проходов с сортировкой слиянием. Но на самом деле большинство из этих проходов легко вписываются в память. Кроме того, умная реализация - какой, кажется, nsort - может сжать промежуточные файлы данных, чтобы сохранить больше проходов в памяти. Этот набор данных должен быть хорошо структурированным и сжимаемым, в котором все промежуточные файлы данных должны умещаться в оперативной памяти. Поэтому вы полностью избегаете дисков, за исключением чтения и записи данных.
Это решение, которое вы выбрали.
ОК, это говорит нам, как решить эту проблему. Что еще можно сказать?
Совсем немного. Давайте проанализируем, что случилось с предложениями базы данных. Стандартная база данных имеет таблицу и несколько индексов. Индекс - это просто структурированный набор данных, который сообщает вам, где находятся ваши данные в вашей таблице. Таким образом, вы идете по индексу (возможно, выполняете множественный поиск, хотя на практике все, кроме последнего, как правило, находятся в ОЗУ), который затем сообщает вам, где находятся ваши данные в таблице, и вам нужно будет снова искать их, чтобы получить данные. Таким образом, захват части данных из большой таблицы потенциально означает поиск 2 дисков. Кроме того, запись части данных в таблицу означает запись данных в таблицу и обновление индекса. Что означает писать в нескольких местах. Это означает, что больше дисков ищет.
Как я объяснил в начале, поиск диска плох. Вы не хотите делать это. Это катастрофа.
Но, спросите вы, разве люди из баз данных не знают этого? Ну, конечно, они делают. Они разрабатывают базы данных, чтобы делать то, что просят пользователи, и они не контролируют пользователей. Но они также заставляют их поступать правильно, когда они могут понять, что это такое. Если вы работаете с приличной базой данных (например, Oracle или PostgreSQL, но не MySQL), база данных будет иметь неплохую идею, когда будет хуже использовать индекс, чем слиянием, и выберет поступать правильно. Но он может сделать это только в том случае, если у него есть весь контекст, поэтому так важно перенести работу в базу данных, а не кодировать простой цикл.
Кроме того, база данных хороша тем, что не нужно писать везде, пока это не нужно. В частности, база данных записывает что-то, называемое журналом WAL (запись в журнал доступа - да, я знаю, что второй журнал избыточен) и обновляет данные в памяти. Когда он добирается до него, он записывает изменения в память на диск. Это объединяет записи и заставляет их искать меньше. Однако есть предел тому, сколько можно выпить. Таким образом, поддержание индексов является по своей сути дорогостоящей операцией. Вот почему стандартный совет для больших объемов данных в базах данных - отбросить все индексы, загрузить таблицу, а затем воссоздать индексы.
Но все это говорит о том, что базы данных имеют пределы. Если вы знаете правильный способ решения проблемы внутри базы данных, то я гарантирую, что использование этого решения без дополнительной нагрузки на базу данных всегда будет быстрее. Хитрость в том, что очень немногие разработчики обладают необходимыми знаниями, чтобы найти правильное решение. И даже для тех, кто это делает, гораздо проще заставить базу данных понять, как сделать это достаточно хорошо, чем написать идеальное решение с нуля.
И последний бит. Что если у нас есть кластер машин? Стандартное решение для этого случая (популяризируемое Google, которое использует это внутренне) называется MapReduce. Он основан на наблюдении, что сортировка слиянием, которая хороша для диска, также действительно хороша для распределения работы по нескольким машинам. Таким образом, мы очень, очень хотим подтолкнуть работу к роду.
Уловка, которая используется для этого, состоит в том, чтобы выполнить работу в 3 основных этапа:
- Возьмите большой объем данных и создайте поток фактов ключ / значение.
- Сортировка фактов, разбиение их на ключ / значения и отправка для дальнейшей обработки.
- Имейте редуктор, который принимает набор ключей / значений и что-то с ними делает.
При необходимости редуктор может отправлять данные в другой MapReduce, и вы можете связывать любой набор этих операций.
С точки зрения пользователя, хорошая вещь в этой парадигме состоит в том, что все, что вам нужно сделать, это написать простой преобразователь (берет часть данных, например, строку, и генерирует 0 или более пар ключ / значение). ) и редуктор (принимает набор ключей / значений, что-то с ним делает) и кровавые подробности могут быть перенесены в вашу среду MapReduce. Вам не нужно осознавать тот факт, что он использует своего рода под капотом. И он может даже позаботиться о таких вещах, как то, что делать, если одна из ваших рабочих машин умирает в середине вашей работы. Если вам интересно поиграть с этим, http://hadoop.apache.org/mapreduce/ - это широко доступный фреймворк, который будет работать со многими другими языками. (Да, он написан на Java, но не важно, на каком языке написаны маппер и редуктор.)
В вашем случае ваш картограф может начать с фрагмента данных в форме (filename, block_start), открыть этот файл, начать с этого блока и выдать для каждой строки пару ключ / значение в форме domain: (filename, registrar). Затем редуктор получит для одного домена 1 или 2 файла, из которых он получен, с полной информацией. Это тогда только испускает факты интереса. Добавляет, что это в новом, но не в старом. Снижения в том, что это в старом, а не в новом. Изменения в регистраторе состоят в том, что он есть в обоих, но регистратор изменился.
Предполагая, что ваш файл легко доступен в сжатом виде (так что его можно легко скопировать на несколько клиентов), это может позволить вам обработать ваш набор данных гораздо быстрее, чем любая отдельная машина.