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

Я хочу отсортировать списки от 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 байт?

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


performance sorting parallel-processing algorithm low-latency
person Ole Tange    schedule 16.04.2020    source источник
comment
Для такого сценария сортировка ведром творит чудеса в качестве первого этапа.   -  person Mooing Duck    schedule 17.04.2020
comment
Кроме того, это похоже на проблему, которую я изучал какое-то время, и пришел к интересному выводу: поскольку диск настолько медленнее процессора, вашей целью должно быть создание алгоритма, IO связан. Процессор фактически свободен. Скорее всего, оптимальное решение можно реализовать на одном ядре ЦП. (Опять же, мой жесткий диск не работает со скоростью 1 ГБ/с :O)   -  person Mooing Duck    schedule 17.04.2020
comment
en.wikipedia.org/wiki/External_sorting   -  person user3386109    schedule 17.04.2020
comment
По крайней мере, на март 2018 года скорость самого быстрого потребительского диска составляла 480 МБ/с. Сверхбыстрые SSD — 235 МБ/с. tomshardware.com/news/seagate-exos- hdd-hamr-mach.2,36719.html   -  person Mooing Duck    schedule 17.04.2020
comment
billion длинный или короткий?   -  person greybeard    schedule 17.04.2020
comment
@MooingDuck Массив RAID-0 может легко увеличить скорость до 1 ГБ / с.   -  person btilly    schedule 17.04.2020
comment
@greybeard Будет ли ваше решение отличаться от длинного или короткого? Я думаю, что лучшее решение будет охватывать оба.   -  person Ole Tange    schedule 17.04.2020
comment
@user3386109 user3386109 Внешняя сортировка будет частью этого, но сегодня диски настолько быстры (вспомните NVMe в RAID0), что могут легко перегрузить одно ядро. Но перегрузить 128 ядер они не могут. Так что это алгоритм, который подходит для той области, которую я ищу. Кроме того, NVMe работает лучше, если несколько обращений стоят в очереди параллельно, и с помощью параллельного алгоритма это также можно использовать.   -  person Ole Tange    schedule 17.04.2020
comment
@MooingDuck 235 МБ/с кажется довольно медленным для твердотельных накопителей... ты действительно это имел в виду?   -  person Kelly Bundy    schedule 17.04.2020
comment
@HeapOverflow: я дважды проверил свой источник, по-видимому, он был для жестких дисков. Виноват.   -  person Mooing Duck    schedule 17.04.2020
comment
@OleTange Да, мое решение отличается, если есть данные для удвоенной емкости ОЗУ, 30 раз или многократно раз. То же самое для вторичного хранилища с последовательным доступом (лента — LTO и IBM TS все еще существуют, собственная емкость находится в диапазоне низких ТБ по состоянию на 2020 г.), движущихся дисков с неоднородным блочным доступом и NV SS с единым блочным доступом.   -  person greybeard    schedule 17.04.2020
comment
Я думаю, что ваше возражение против этого последнего шага слияния необоснованно. По моему опыту, последний шаг слияния привязан к выходным данным, даже если задействовано сравнение строк. Должно быть достаточно легко проверить. Загрузите миллиард строк: половину в один массив и половину в другой. Отсортируйте два массива. Затем объедините их на диск. Посмотрите, не привязаны ли вы к процессору или вводу-выводу во время слияния.   -  person Jim Mischel    schedule 17.04.2020
comment
@JimMischel Я тестировал. Это действительно узкое место, если диски быстрые или вы можете уместить большую часть в памяти. Должно быть легко убедить себя, что это правда. Просто предположим, что сравнения смехотворно дороги для процессора. Тогда вы действительно хотите использовать все процессоры, за которые заплатили.   -  person Ole Tange    schedule 17.04.2020
comment
@MooingDuck Можете ли вы уточнить входные данные сортировки ведра, разработанные дьяволом (т. Е. Все ваши догадки неверны, и дьявол попытается спроектировать входные данные, чтобы все они попадали в одно и то же ведро)?   -  person Ole Tange    schedule 17.04.2020
comment
@OleTange Там, где важна максимальная производительность, пересмотренный закон Амдала. Не могли бы вы опубликовать lcspu + hwloc / lstopo ( как в stackoverflow.com/a/50221801 ) для указанной тестируемой системы? Знание реальности как есть помогает разработать наиболее эффективную стратегию, не так ли? ( ... и в самом деле БОЛЬШОЕ СПАСИБО ЗА gnu PARALLEL --jobs 1 echo {} ::: крутой, крутой, крутой, мощный инструмент, сэр )   -  person user3666197    schedule 17.04.2020
comment
Системы, которые я использую сегодня: gitlab.com/snippets/1967455, но я бы предпочел решение, которое также работают на серверах разного размера, поэтому я даю характеристики оборудования в вопросе как диапазон довольно обычных серверов.   -  person Ole Tange    schedule 17.04.2020
comment
@OleTange: Вы правы в том, что в патологических случаях сортировка ведра разваливается. Вам определенно нужна сортировка слиянием, как предлагает Джим в качестве запасного варианта. Особенно, когда сравнения очень дороги, в среднем сортировка ведра будет намного быстрее для непатологических случаев, экономя вам log(numBuckets) сравнений для каждого элемента.   -  person Mooing Duck    schedule 17.04.2020
comment
@OleTange Спасибо за детали lscpu / lstopo (возможно, вы уже знаете, что при публикации комментария без подписанного текста @-‹user› сайт StackOverflow будет не уведомлять предполагаемого пользователя, чтобы он/она никогда не узнал, что вы ответили на вопросы в комментарии). Имея это оборудование, какова ваша реальная целевая базовая производительность, чтобы получить результат примерно из этих элементов 1E11 примерно в 1E3 [B] каждый отсортированный? Не имея цели, любой путь подходит и может привести вас к ней.   -  person user3666197    schedule 18.04.2020
comment
@user3666197 user3666197 Если вы сосредоточитесь на моих скудных результатах, мы не добьемся достаточного прогресса. Цель должна быть следующей: как заставить все процессоры выполнять O(n/k *log n) сравнений, если мы не ограничены дисковым вводом-выводом, как оптимизировать дисковый ввод-вывод, когда мы ограничены дисковым вводом-выводом. (что обычно достигается за счет выполнения некоторого, но меньшего количества параллельных дисковых операций ввода-вывода), и можем ли мы сделать это, не считывая все данные перед запуском. Мои скудные результаты приведены на gitlab.com/ole.tange/tangetools/- /tree/master/parsort Что меня действительно удивило, так это то, что, похоже, не существует общеизвестной передовой практики.   -  person Ole Tange    schedule 18.04.2020

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

person btilly    schedule 16.04.2020
comment
Как вы объединяете куски, чтобы получить один отсортированный вывод? Разве они не проходят через одно ядро, которое должно выполнять сравнение для каждого элемента? Или у вас есть параллельный алгоритм для последнего шага? - person Ole Tange; 17.04.2020
comment
Предположим, что нам не хватает 1 байта для использования нескольких серверов и 1 байта для использования распределенной файловой системы. Итак, мы говорим о максимуме, который вы могли бы сделать на одном сервере. - person Ole Tange; 17.04.2020
comment
@OleTange Фрагменты выглядят как AG, HM, ... и выбираются динамически после того, как вы выполнили достаточное слияние, чтобы у вас было достаточно длинных файлов, чтобы начать разбивать на фрагменты. Они не обязательно должны быть точно такого же размера. А поскольку диапазоны не пересекаются, их можно распараллелить естественным образом. - person btilly; 17.04.2020
comment
@OleTange Это требует изменения мышления. Но как только мышление изменилось, это легко. - person btilly; 17.04.2020
comment
@btilly: я думаю, что этот ответ правильный, но его очень сложно понять. - person Mooing Duck; 17.04.2020
comment
@MooingDuck Было бы полезно сказать, что специально созданное программное обеспечение для выполнения тяжелой работы, о которой я говорил, описано в static.googleusercontent.com/media/research.google.com/en//? - person btilly; 17.04.2020
comment
@btilly Есть хороший вопрос о том, как лучше всего сортировать данные в больших кластерах, и ваша ссылка на статью Google MapReduce будет иметь смысл для ответа на этот вопрос. Однако здесь возникает вопрос: как быстрее всего отсортировать самый большой объем данных, который вы бы отсортировали на одном сервере? - person Ole Tange; 18.04.2020
comment
@OleTange Распараллеливание — это распараллеливание. Стратегия, которую я описал, позволит вам полностью использовать все процессоры. - person btilly; 18.04.2020

arrow_upward
1
arrow_downward

При традиционном слиянии с использованием отсортированных подфайлов окончательное слияние равно 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), которые он сделал бы, если бы вы использовали одно ядро ​​ЦП для слияния.

person Jim Mischel    schedule 17.04.2020
comment
у которого есть проблема, заключающаяся в том, что на последнем этапе слияния необходимо выполнить n сравнений на одном ядре при слиянии последних двух [подфайлов] - person Mooing Duck; 17.04.2020
comment
Это также записывает NlogN байтов на диск. Очень неэффективно. - person Mooing Duck; 17.04.2020
comment
@MooingDuck Да, окончательное слияние должно выполнять n сравнений. Что намного меньше, чем n log k. В любом случае, это, вероятно, будет привязано к выходу. И нет, он не записывает n log n байт на диск. Сеть слияния работает в памяти. Первый уровень процессоров — поток из файлов и слияние в память. Следующие уровни читают буферы памяти, заполненные предыдущим уровнем. Все это делается с помощью очередей производителей/потребителей. - person Jim Mischel; 17.04.2020
comment
Извините, я не прочитал ответ полностью и неправильно понял сеть слияния. - person Mooing Duck; 17.04.2020
comment
@JimMischel Ваше решение - это простая сортировка слиянием, которую я отвергаю именно потому, что одно ядро ​​​​должно выполнять n сравнений. Если диск быстрый или большая часть данных помещается в ОЗУ, то это является узким местом, особенно если сравнения требуют больших ресурсов ЦП, как это предлагается в вопросе (я тестировал). Можем ли мы найти решение, в котором одно ядро ​​не должно выполнять n сравнений? Что-то, где каждый из k процессоров должен выполнять O (n / k * log n) сравнений? - person Ole Tange; 17.04.2020