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

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

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

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

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

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

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

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

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

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

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

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