Linux: сортировка текстового файла объемом 500 ГБ с 10 ^ 10 записями

У меня есть текстовый файл объемом 500 ГБ, содержащий около 10 миллиардов строк, которые нужно сортировать в алфавитном порядке. Каков наилучший алгоритм? Могут ли быть улучшены мои настройки и настройки?

В настоящее время я использую команду sortutils sort:

LANG=C
sort -k2,2 --field-separator=',' --buffer-size=(80% RAM) --temporary-directory=/volatile BigFile

Я запускаю это в AWS EC2 на 120 ГБ оперативной памяти и 16-ядерную виртуальную машину. Это занимает большую часть дня.

/volatile - массив массивов 10ТБ RAID0.

Трюк "LANG = C" обеспечивает ускорение скорости x2 (благодаря 1)

По умолчанию "сортировка" использует 50% доступной ОЗУ. Повышение до 80-90% дает некоторое улучшение.

Я понимаю, что gnu 'sort' - это вариант алгоритма сортировки слияния с O (n log n), который является самым быстрым: см. 2 и 3. Переместился бы в QuickSort help (я доволен нестабильной сортировкой)?

Одна вещь, которую я заметил, это то, что используются только 8 ядер. Это связано с установкой default_max_threads в 8 в linux coreutils sort.c(см. 4). Помогло бы перекомпилировать sort.c с 16?

Спасибо!

ПОСЛЕДУЮЩИЙ:

@dariusz

Я использовал Криса и ваши предложения ниже.

Поскольку данные уже были сгенерированы партиями: я отсортировал каждый блок отдельно (на нескольких отдельных машинах), а затем использовал функцию sort -merge. Работает как шарм и намного быстрее: O (log N/K) против O (log N).

Я также переосмыслил проект с нуля: некоторые данные пост-обработки теперь выполняются во время генерации данных, так что некоторые ненужные данные (шум) могут быть отброшены до начала сортировки.

Все вместе, уменьшение размера данных и сортировка/слияние привели к значительному сокращению вычислительных ресурсов, необходимых для достижения моей цели.

Спасибо за все ваши полезные комментарии.

Ответ 1

Преимущества quicksort over mergesort не являются дополнительными издержками памяти. Преимущество mergesort - гарантированное время O (n log n), где, поскольку quicksort может быть намного хуже в случае плохой выборки опорных точек. Если у вас нет причин беспокоиться об использовании памяти, не изменяйте. Если вы это сделаете, просто убедитесь, что вы выбрали реализацию быстрой сортировки, которая делает сплошную выборочную выборку.

Я не думаю, что это поможет эффектно перекомпилировать sort.c. Это может быть в масштабе микро-оптимизации. Но ваше узкое место здесь будет иметь скорость памяти/диска, а не количество доступных процессоров. Моя интуиция будет состоять в том, что 8 потоков будут максимизировать пропускную способность ввода-вывода, и вы не увидите улучшения производительности, но это, безусловно, будет зависеть от вашей конкретной настройки.

Кроме того, вы можете добиться значительного увеличения производительности, воспользовавшись распределением ваших данных. Например, равномерно распределенные данные могут быть отсортированы очень быстро одним проходом сортировки в байтах, а затем с помощью mergesort сортировать ведра. Это также имеет дополнительное преимущество, заключающееся в уменьшении суммарной накладной памяти для mergesort. Если сложность памяти mergesort равна O (N), и вы можете разделить свои данные на K-ведрах, ваши новые служебные данные памяти O (N/K).

Ответ 2

Просто идея:

Я предполагаю, что содержимое файла генерируется довольно долгое время. Напишите приложение (script?), Которое периодически перемещает файл, созданный по-прежнему, в другое место, добавляет его содержимое в другой файл, выполняет сортировку в этом другом файле и повторяется до тех пор, пока не будут собраны все данные.

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

Ответ 3

Думаю, вам нужно выполнить этот сорт в 2 этапа:

Разделить на триподобные ковши, вставить в память.
Итерировать ведра в соответствии с порядком алфавита, извлекать каждый, сортировать и добавлять к выходному файлу.

Это пример.

Предположим, что у вас есть ограничение на 2 строки, а ваш входной файл:

входной_файл: 0000 0001 0002 0003 5 53 52 7000

на 1-й итерации вы читаете свой входной файл "супер-ведро с пустым префиксом" и разделяете по 1-й букве.

Было бы 3 выходных файла:

0: 000 001 002 003

5: (Пусто) 3 2

7: 000

Как вы видите, ведро с именем/префиксом 7 содержит только одну запись 000, которая равна "7000", разделенная на 7 - имя файла и 000 - хвост строки. так как это всего лишь одна запись, вам больше не нужно разделить этот файл. Но файлы "0" и "5" содержат 4 и 3 записи, что больше, чем предел 2. Итак, нужно разделить их снова. После раскола:

00: 01 02 03

5: (Пусто)

52: (Пусто)

53: (Пусто)

7: 000

Как видите, файлы с префиксом "5" и "7" уже расщеплены. поэтому нужно просто разделить файл "00".

Как вы видите, после расщепления у вас будет набор относительных небольших файлов. Затем выполните 2-й этап:

Отсортировать имена файлов и обрабатывать имена файлов в соответствии с отсортированным порядком. сортировать каждый файл и добавлять resut для вывода, добавляя имя файла в строку вывода.