Алгоритмы для оптимизации с быстрым дисковым хранилищем (SSD)?

Question

Учитывая, что твердотельные диски (SSD) снижаются в цене и скоро станут более распространенными в качестве системных дисков, а также учитывая, что их скорости доступа значительно выше, чем у вращающихся магнитных носителей, какие стандартные алгоритмы выиграют в производительности от использования SSD для локального хранения? Например, высокая скорость произвольного чтения SSD делает нечто вроде хэш-таблицы на основе диска жизнеспособностью для больших хеш-таблиц; Легко доступно 4 ГБ дискового пространства, что делает возможным хеширование всего диапазона 32-разрядного целого числа (больше для поиска, чем для заполнения, хотя это все равно займет много времени); хотя этот размер хеш-таблицы будет запрещен для работы с вращающимися носителями из-за скорости доступа, он не должен быть проблемой для SSD.

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

Answer 1

Ваш пример хеш-таблиц действительно является ключевой структурой базы данных, которая принесет пользу. Вместо того, чтобы загружать весь 4 ГБ или более файл в память для проверки значений, SSD может быть проверен напрямую. SSD по-прежнему медленнее, чем RAM, на порядок, но вполне разумно иметь хэш-таблицу на 50 ГБ на диске, но не в RAM, если вы не платите большие деньги за большое железо.

Пример - базы данных шахматных позиций. У меня более 50 ГБ хешированных позиций. Существует сложный код, чтобы попытаться сгруппировать связанные позиции рядом друг с другом в хэше, поэтому я могу постраничать по 10 МБ таблицы за раз и надеюсь повторно использовать некоторые из них для нескольких похожих запросов позиций. Есть тонна кода и сложности, чтобы сделать это эффективным.

Замененный на SSD, я смог отбросить всю сложность кластеризации и просто использовать действительно тупые рандомизированные хэши. Я также получил увеличение производительности, поскольку я получаю только те данные, которые мне нужны, с диска, а не большие 10-мегабайтные куски. Задержка действительно больше, но чистое ускорение является значительным ... и суперчистый код (20 строк, а не 800+), возможно, даже лучше.

Answer 2

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

Несмотря на то, что твердотельные накопители значительно перемещают иглу, они все еще намного медленнее, чем операции процессора и физической памяти. Например, для вашей хеш-таблицы объемом 4 ГБ вы можете получить более 250 МБ / с от SSD для доступа к случайным сегментам хеш-таблиц. Для ротационного привода вам посчастливится разбить однозначную цифру МБ / с. Если вы можете хранить эту 4-гигабайтную хеш-таблицу в памяти, вы можете получить к ней доступ порядка порядка гигабайт в секунду - намного быстрее, чем даже очень быстрый SSD.

В указанной статье перечислено несколько изменений, которые MS сделала для Windows 7 при работе на SSD, что может дать вам представление о том, какие изменения вы могли бы рассмотреть. Во-первых, SuperFetch для предварительной выборки данных с диска отключен - он разработан, чтобы обойти медленное время произвольного доступа к диску, которое облегчается SSD. Дефрагментация отключена, поскольку разброс файлов по всему диску не влияет на производительность SSD.

Answer 3

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

Хотя я мог видеть, что некоторые системы баз данных выигрывают от этого. MySQL, например, с использованием механизма хранения MyISAM (где записи данных в основном являются прославленными CSV). Тем не менее, я думаю, что очень хорошие хеш-таблицы будут лучшим выбором для хороших примеров.

Answer 4

SSD намного быстрее для случайного чтения, немного для последовательного чтения и, соответственно, медленнее для записи (случайной или нет).

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

Answer 5

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