WALSH — новый подход к хранению dedup-индекса

Write-Aggregating Log-Structured Hashing: новая модель хранения данных

Недавно группа ученых представили WALSH — Write-Aggregating Log-Structured Hashing (источник: https://dl.acm.org/doi/10.1145/3715010), индекс для гибридной DRAM + постоянной памяти (PM), который одновременно:

Сокращает write-amplification записи

Вместо множественных мелких обращений WALSH собирает их в мини-журнал в DRAM и единым блоком сбрасывает в PM. Это резко снижает аппаратное write-amplification, критичное для Storage-Class Memory подобных модулей .

Хранит минимум метаданных в ОЗУ

«Голова» каждой цепочки остаётся в DRAM, а «хвосты» ведутся прямо в журналах PM;в  итоге  -87 % DRAM по сравнению с лучшими гибридными хеш-таблицами.

Обеспечивает параллелизм

Четырёхфазный протокол отделяет поиск, запись, компакцию и очистку; потоки работают без глобальных блокировок и при этом сохраняют crash-consistency.

Восстанавливается за секунды

Для базы на ≈1 млрд ключей контекст журнала перечитывается за «несколько секунд», тогда как аналоги требовали минут. Производительность вставок до 2,4× выше других современных подходов.

Почему для BAUM это важно?

Мы в BAUM MDS постоянно исследуем подобные архитектуры. 

Хранить огромные хеш-таблицы — будь то карты дедупликации или карты размещения блоков — очень сложная инженерная задача:

• Обновление таблиц происходит мелкими вставками 24/7;
• Карты размещения должны переживать сбой и подниматься в секунды, иначе падает весь storage-кластер;
• Объем метаданных может быстро разрастаться, сталкивая нас с Memory-wall 

WALSH демонстрирует, как лог-структурная идея LSM может жить внутри простой хеш-структуры и тем самым убивать сразу три боли: износ SLC модулей, нехватку оперативки и длительное recovery.

Мы будем анализировать, какие элементы решения можно перенести в наши модули MDS.

Автор: Андрей Гантимуров