Хранение бэкапов — это всегда очень большие объемы данных и долгий срок хранения. Разрабатывая нашу систему хранения данных (СХД) для резервных копий TATLIN.BACKUP, мы столкнулись с недопустимо быстрым ростом метаданных для восстановления данных, причём метаданные часто дублировались. При среднем сжатии данных в 6 раз и доступной ёмкости для данных в 690 ТБ, объём метаданных достигал 13 ТБ, что занимало всю выделенную ёмкость под них.

Я расскажу:
* как мы решали эту проблему с использованием структуры Дерева Меркла и сократили объём метаданных на 83% при средней дедупликации в 6x раз;
* как это позволило нам ускорить поиск дубликатов в 10 раз;
* о применении content-defined chunking-алгоритма для построения дерева для того, чтобы эти решения работали;
* о подобных (но не наших) решениях для систем контейнеризации и распределённых key-value-хранилищ.

Наш подход сильно экономит дисковое пространство, а значит, и финальную стоимость хранения. И его также могут использовать системы хранения и БД для ускорения операций поиска, pull/push-операций данных или быстрой синхронизации реплик в распределённых БД.