нужна высокая производительность / bin / sort; какие-либо предложения?

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

Nsort - это программа сортировки / слияния, которая может быстро сортировать большие объемы данных, используя большое количество процессоров и дисков параллельно. Nsort - единственная коммерческая программа сортировки, обладающая уникальной эффективностью процессора и демонстрирующая:

• Сортировка 1 терабайт (33 минуты)
• Скорость чтения и записи файлов 1 гигабайт / с

Nsort имеет долгую историю сортировки массивных производственных наборов данных, таких как:

• Веб-журналы для веб-сайтов с высокой посещаемостью
• Журналы телефона
• Данные государственного агентства

Грм. Думаю, здесь вы столкнетесь с несколькими проблемами. Прежде всего, ваши входные данные будут иметь большое влияние на производительность сортировки (разные алгоритмы работают лучше или хуже в зависимости от распределения входных данных). Однако большая проблема заключается в том, что 60 ГБ - это много данных.

Кроме того, сортировка не так проста, как сжатие, потому что нет гарантий близости. Другими словами, с помощью сжатия / распаковки вы можете разбить ввод на дискретные части и работать с ними по отдельности и независимо. После обработки каждого фрагмента они просто объединяются вместе. С сортировкой у вас есть несколько шагов, потому что вы не можете просто объединить результаты (если вы не выполните некоторую предварительную обработку), вам нужно объединить результаты (потому что запись в начале 60 ГБ может оказаться рядом с записью в конце 60гб, после сортировки).

В основном я могу придумать здесь несколько общих решений:

• Предварительно разбейте данные на разделы таким образом, чтобы они были удобны для сортировки и рекомбинации. Например, если вы выполняете простую сортировку по алфавиту, вы можете хранить данные в 26 сегментах, по одному на каждую букву алфавита. Затем вы можете отсортировать каждое ведро по отдельности и в конце объединить их заново. Специфика того, как вы предварительно разбиваете данные, будет зависеть от самих данных, вашего текущего метода хранения и т. Д. Некоторые настройки могут работать лучше, чем другие.
• Напишите свой собственный интерфейс сортировки, который делает в основном то, о чем я писал выше, но на лету. Другими словами, у вас был бы сценарий, который считывает ввод и, основываясь на какой-нибудь очень быстрой операции (например, считывая первую букву или что-то еще, что работает с вашими данными), затем распределяет этот фрагмент данных в соответствующий сегмент сортировки. Каждая сортировка работает независимо до тех пор, пока все данные не будут обработаны, а затем вы снова объедините их вместе. На самом деле это очень похоже на частный случай использования MapReduce для сортировки.
• Используйте решение сортировки на основе MapReduce. Существует проект с открытым исходным кодом под названием Hadoop, который предоставляет множество подпроектов, один из которых является реализацией MapReduce с открытым исходным кодом. Однако я никогда им не пользовался, просто читал об этом. Понятия не имею, применимо ли это к вашей конкретной проблеме.
• Можете ли вы проиндексировать данные, а затем просто отсортировать их? Являются ли все 60 ГБ частью ключа сортировки? Или есть меньшая часть, по которой вы сортируете, а затем набор дополнительных данных для каждой части? Если это последнее, возможно, лучше всего подойдет индексация и сортировка какого-то ключевого значения, а затем поиск дополнительных данных по мере необходимости.
• Возможно, вы могли бы полностью предварительно отсортировать свои данные и поддерживать их в отсортированном состоянии. Каждый раз, когда вы добавляете или обновляете данные, вы должны исправлять их с отсортированной точки зрения. Это решение будет во многом зависеть как от того, как вы храните свои данные, так и от того, будет ли приемлемым влияние на производительность обновлений сортировки.
• И, наконец, вы могли бы заняться всем этим. Выгрузите данные в СУБД (мне сам нравится PostgresSQL) и позвольте базе данных обрабатывать вашу сортировку за вас.

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

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

GNU sort имеет -m, который, вероятно, может вам помочь. Предположим, у вас есть 200 файлов .gz, которые вы хотите отсортировать и объединить. Затем вы можете использовать GNU Parallel для:

seq 1 200 | parallel mkfifo /tmp/{}
ls *.gz | nice parallel -j200 'zcat {} | sort >/tmp/$PARALLEL_SEQ' &
seq 1 200 | parallel -X sort -m /tmp/{} >/tmp/sorted

Если проблема связана с вводом-выводом, а память не является проблемой, используйте -S для первого sort чтобы все осталось в памяти. Также вы можете использовать lzop каждый раз, когда вы пишете на диск (--compress-program = lzop): диски часто являются ограничивающим фактором, поэтому lzopping на лету может дать вам дополнительную скорость. Или вы можете создать RAM-диск и установить -T для этого каталога.

Perl?

Изменить: Ну, эта статья о настройке Perl sort perf. Насколько я могу понять из этого, это в основном руководство по передовой практике, в котором сравнивается, как плохой код сортировки может сделать вашу программу очень медленной, и, наоборот, как сделать ее быстрее.

Небрежное программирование, неаккуратное исполнение.