Dedup_offline (4)

1. Оффлайн дедупликация в связке с RAID

Подготовил: Горбунов Константин

2. Повторим, что мы знаем про дедупликацию

• Дедупликация (от лат. deduplicatio — устранение дубликатов) —
специализированный метод сжатия массива данных,
использующий в качестве алгоритма сжатия исключение
дублирующих копий повторяющихся данных.

3. Повторим, что мы знаем про дедупликацию

В результате нашего предыдущего исследования были выбраны
два наиболее перспективных алгоритма: HV и BF. В их контексте мы
и будем рассматривать вопрос дедупликации в связке RAID.

4. Повторим, как работают HV и BF

Идея HV: кластеризуем блоки по простой хэш функции с
коллизиями, в получившихся кластерах внутри проводим
дедупликацию
Идея BF: кластеризуем суперблоками(суперблок – некоторое
кол-во подряд идущих блоков) по метрике близости их фильтров
блума(в нашем случае – по расстоянию Хэмминга), в получившихся
кластерах внутри проводим дедупликацию

5. Аналогии HV и BF

По сути оба алгоритма просто добавляют кластеризацию в
глобальную дедупликацию: вопрос только в том, что и как мы
кластеризуем. Приведем простые аналогии к данным алгоритмам
на примере задачи сортировки деталек Lego.

6. Аналогия HV

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

7. Аналогия HV

При этом, мы заранее можем
предположить количество
групп, зная кол-во значений
определенного признака. Так
же от выбора признака
разбиение будет зависеть
равномерность распределения
блоков по кластерам: где-то
более равномерно, а где-то с
выделенными популярными и
непопулярными кластерами

8. Аналогия BF

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

9. Аналогия BF

В нашем случае все немного
сложней – нет списка наборов и
деталей в них. Поэтому мы,
постепенно “разбирая коробку”,
сами формируем “журналы”
наборов, по которым сортируем
следующие детали в коробке.
Условием на формирование
нового набора является
достаточная степень отличия от
всех предыдущих.

10. Повторим различия HV и BF

HV
• Кластеризует поблочно, по
сути своей – бакетизация
• Больше обращений к диску,
т.к. каждый блок кладется в
соответствующий кластер
• Нет потерь коэффициента
дедупликации, по
сравнению с глобальным
алгоритмом
BF
• Кластеризует суперблоками
из подряд идущих 4k блоков
• Меньше обращений к диску,
т.к. кластер определяется
для целого суперблока
• Есть потери коэффициента
дедупликации, т.к.
кластеризация более грубая

11. Какие проблемы возникают у дедупликации на уровне RAID

• Онлайн дедупликация работает с RAID без всяких проблем: все
благодаря тому, что дедупликация происходит еще до записи на
диск(по сути, RAID и дедупликация никак не взаимодействуют)
• Основная проблема возникает при офлайн дедупликации: в
результате нее в страйпах RAID-а появляются “дырки”, которые
впоследствии очень дорого использовать (а это и есть
сэкономленное нами место)

12. Откуда появляются дырки при офлайн дедупликации

• Проблема возникает из-за
несовпадения размеров блока
страйпа(фрагмент страйпа,
хранящийся на одном диске – в
нашем примере блок A1) и
блока дедупликации
Стандартные размеры:
• Блок страйпа – 64k
• Блок дедупликации – 4k или 8k

13. Откуда появляются дырки при офлайн дедупликации

• На рисунке представлены блоки страйпов
на одном из дисков
Зеленые – дублированные
Красные – уникальные
• Зеленые блоки в результате дедупликации
оставят “дырки”, которые как раз и будут
сэкономленным пространоством на диске

14. Какие проблемы возникают из-за дырок

Полученное место в результате такой
дедупликации крайне тяжело использовать:
• В лучшем случае мы пишем блоком страйпа, и
соответственно, нам требуется считать его
целиком, чтобы сохранить недедуалицированные
значения
• Возникает вопрос, что писать в эти блоки, т.к. если
записывать в них последние данные, то будет
сильная фрагментация
• Если “сдвигать” все данные назад, чтобы
заполнить дырки, потребуется много перезаписи

15. Как бороться с дырками от дедупликации

Есть два пути борьбы с дырками:
• Превентивный – организовать алгоритм так, чтобы дырок не
было
• Постфактум – придумать эффективный алгоритм перезаписи для
избавления от дырок
К сожалению, второй вариант найти так и не удалось – все
упиралось в сложность восстановления последовательной
структуры и в большой разброс “дырок” по хранилищу

16. Превентивная борьба с дырками от дедупликации

Идея метода – поделить данные на
“чистые” и “грязные”.
Чистые – уже прошедшие
дедупликацию
данные(соответственно в чистом
регионе все блоки уникальные)
Грязные – только записанные на диск
данные

17. Превентивная борьба с дырками от дедупликации

Как данные переходят из грязных в
чистые:
В момент простоя системы
включается офлайн дедупликация –
берется блок из грязных данных и
ищется совпадение с чистыми.
Если совпадение не найдено, блок
записывается в чистые данные, в
противном случае - дедуплицируется

18. Превентивная борьба с дырками от дедупликации - оптимизация

Дополнительная оптимизация –
внедрение небольшой части онлайн
дедупликации при помощи простого
хэша с малым числом значений.
Если значение хэша новое – данные
100% новые – пишем сразу в чистые;
Если значение уже было – ничего
конкретного сказать не можем.
Идея очень похожа на фильтр Блума

19. Пример

Изначально, когда
вся дедупликация
выполнена, все
наши данные
находятся в U
регионе.
ND регион же в
свою очередь пуст –
все блоки из него
либо переписаны в
U регион, либо же
дедуплицированны

20. Пример

В ходе работы, мы
копим поступающие
нам данные, а затем,
накопив страйп,
записываем его в
грязные данные (ND
регион). Пока идет
достаточно большая
нагрузка на запись,
дедупликация не
запускается и ждет
“окна” в нагрузке.

21. Пример

Когда нагрузка
приостанавливается,
начинает работать
дедупликация – она
берет блок из ND
региона и ищет его
копию в U регионе.
Если копия
обнаружена – блок
дедуплицируется,
если же нет – то он
добавляется в буфер
на запись в U регион.

22. Пример

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

23. Пример

Алгоритм
дедупликации
продолжается до тех
пор, пока снова не
появится нагрузка
на запись, или весь
ND регион не
окажется пуст.

24. Про добавление онлайн дедупликации

• Онлайн дедупликацию можно легко добавить при помощи какого
либо вероятностного критерия на данные(есть ли они у нас в
хранилище). Если мы точно знаем, что данные новые – сразу
записываем их в буфер U региона. Для этого, например, хорошо
подойдет фильтр Блума.

25. Про добавление онлайн дедупликации

Теперь в ходе работы мы
так же копим данные, но
только теперь не в одном
буфере, а в двух: U буфер
и ND буфер. После
заполнения буфера, он по
прежнему записывается в
соответствующий регион.
В какой буфер конкретно
мы записываем блок
определяем при помощи
вероятностного критерия.

26. Про добавление онлайн дедупликации

• Также можно подойти к вопросу с другой стороны, и искать не
100% уникальные данные, а наиболее встречающиеся дубликаты,
дедуплицируя их “на лету”. Тем самым, еще больше сократив
количество данных в ND регионе. В этом нам поможет любая из
техник кэширования.

27. Что улучшает данный подход

• Блоки в чистых данных сохраняют последовательный порядок (не
учитывая дедуплицированные блоки)
• Запись, чтение, обработка данных – все ведется в масштабе
страйпа (всего лишь нужен буфер для накопления 4k блоков до
страйпа)
• Данные явно разделены на дедуплицированные и
неопределенные
• Добавление нескольких видов онлайн дедупликации ускоряет
алгоритм, позволяя равномернее нагрузить схд и уменьшить
кол-во работы в оффлайн фазе

28. Как данный подход работает с BF и HV

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