Самая быстрая сортировка, если данные не помещаются в физическую память RAM?

Question

Я хочу отсортировать списки от 1 до 100 миллиардов элементов в системах с 8-128 ядрами, оперативной памятью на 10% элементов и дисками со скоростью 100-1000 МБ / с.

Я протестировал простую сортировку слиянием, где каждое слияние выполняется параллельно процессором:

sorted_part_a:__
                \__[CPU.1]__
sorted_part_b:__/           \
                             \__[CPU.5]__
sorted_part_c:__             /           \
                \__[CPU.2]__/             \
sorted_part_d:__/                          \
                                            \__[CPU.7]
sorted_part_e:__                            /
                \__[CPU.3]__               /
sorted_part_f:__/           \             /
                             \__[CPU.6]__/
sorted_part_g:__             /
                \__[CPU.4]__/
sorted_part_h:__/

Но есть проблема, связанная с тем, что последний шаг слияния [CPU.7] имеет делать n сравнений на одном ядре при объединении двух последних входных данных, и сравнение может быть дорогим (подумайте о строках, которые должны соответствовать настройкам локали). В моем тесте [CPU.7] было узкое место.

Затем я посмотрел на красно-черные деревья. У них есть несколько преимуществ:

• , когда дерево построено, тогда получение отсортированного списка будет O(n) без сравнений. Это позволяет избежать узкого места, которое я видел в своем тесте сортировки слиянием.
• вы можете строить деревья параллельно и объединять их параллельно , используя несколько ядер.
• вам не нужно все данные, прежде чем вы сможете начать строить деревья (поэтому, если вы читаете с медленного устройства, вы можете сортировать, пока вы читаете, таким образом, не тратя время настенных часов).

Сохранение дерева на диск также кажется довольно просто (просто экспортируйте отсортированный список и высоту дерева), но получение только части дерева с диска кажется более сложным.

Я прочитал Какой алгоритм параллельной сортировки имеет лучшее среднее значение производительность дела? , но, похоже, он игнорирует общий случай с данными среднего размера: эти данные помещаются на диск сервера, но не помещаются в ОЗУ.

Учитывая аппаратное обеспечение (8-128 ядер, ОЗУ для 10% элементов и с дисками, обеспечивающими потоковую передачу 100-1000 МБ / с, 1000 iops), что является самым быстрым способом сортировки списков от 10 ^ 9 до 100 * 10 ^ 9 элементов из 10-100 байт каждый?

С точки зрения непрофессионала:
Какой проверенный и верный способ быстрой сортировки наибольшего объема данных, который вы бы отсортировали на одном сервере?

Answer 1

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

Но Вы можете распараллелить это слияние. Скажем, у вас есть 8 вложенных файлов. Вы можете построить сеть слияния следующим образом:

    f1    f2    f3    f4    f5    f6    f7    f8
      \  /        \  /        \  /        \  /
       p1          p2          p3          p4
         \__    __/              \__    __/
            \  /                    \  /
             p5                      p6
                \_______    _______/
                        \  /
                         p7

Идея состоит в том, что каждое ядро ​​процессора с p1 по p4 начинает объединять два файла. Каждый из процессоров p5 и p6 объединяет выходные данные двух процессоров первого уровня, а p7 объединяет результаты от них. p7 заканчивает тем, что делает n сравнений, а не O (n log k) сравнений, которые он сделал бы, если бы вы использовали одно ядро ​​ЦП для слияния.

Answer 2

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

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

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