Лес Меркла, или Как мы уменьшили объём метаданных на 83% | Сергей Ли

Подписывайтесь на наш канал здесь и в телеграм https://t.me/meetups_evrone, чтобы быть в курсе будущих митапов и не пропускать полезные доклады! Как уменьшить объём метаданных на 83% и ускорить поиск дубликатов в 10 раз? В этом докладе разработчики TATLIN.BACKUP рассказывают, как с помощью дерева Меркла и алгоритма content-defined chunking удалось эффективно оптимизировать хранение резервных копий. Вы узнаете о практическом применении структур данных в реальных СХД, решениях для дедупликации и снижении стоимости хранения. Доп. материалы и презентация: https://clck.ru/3EiZ4z 00:00 - Введение 00:25 - Что такое TATLIN.BACKUP 01:15 - Запись в СХД для резервных копий 02:10 - Как восстановить файл? 03:00 - Линейный рост метаданных 04:00 - Затраты на хранение списков хешей 05:30 - Какую структуру данных мы хотим? 06:29 - Построение Дерева Меркла 07:40 - Свойство: structural sharing 08:47 - Построение Леса Меркла на записи 10:30 - Приходит fsync 11:04 - Сохранение Леса Меркла на fsync 12:29 - Хранение метаданных 12:53 - Лес Меркла vs Список хешей 13:52 - Выводы 15:03 - Корневой узел дерева содержит хеш от всего набора данных 16:02 - Синхронизация с помощью Дерева Меркла 17:43 - Ускорение поиска дубликатов 19:26 - Суммарное время работы функции проверки на дубликаты 19:49 - Как строить дерево Меркла 23:31 - Content-defined chunking алгоритм 24:32 - Адаптирование алгоритма для разбиения хешей на группы 25:22 - Фиксированное vs Contend-defined 26:03 - Минусы Content-defined chunking 27:14 - Заключение