Дедупликация файлов: хеш содержимого как ключ

Прямой ответ

Дедупликация по содержимому использует хеш файла как его идентификатор. Если два файла дают одинаковый хеш, это один и тот же набор байтов, и хранить его достаточно один раз. Подход называется content-addressable storage: адрес объекта вычисляется из данных, а не назначается извне.

Практическая схема:

import hashlib

def sha256_of(path: str, chunk: int = 1024 * 1024) -> str:
    h = hashlib.sha256()
    with open(path, "rb") as f:
        while block := f.read(chunk):
            h.update(block)
    return h.hexdigest()

Хеш вычисляется потоково, поэтому размер файла не влияет на потребление памяти. Полученное значение используется как ключ объекта:

blobs/9f/9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08

Разбиение пути по первым символам хеша предотвращает создание каталога с миллионами записей, что замедляет файловые системы.

Что это даёт на практике:

«Мгновенная загрузка» строится так: клиент вычисляет хеш локально, отправляет его серверу, и при совпадении с существующим объектом передача данных не выполняется. Это экономит трафик и время, но требует осторожности — см. ниже.

Git использует ту же модель: объекты хранятся по SHA-1 (в новых версиях поддерживается SHA-256), а дерево каталогов описывается через хеши содержимого — см. Git Internals. Проверка наборов объектов строится на дереве Меркла, о котором есть отдельная статья — дерево Меркла.

Практика: корректная реализация

1. Используйте SHA-256, а не MD5. MD5 быстрее, но для него существуют практические коллизии: два разных файла с одинаковым хешем можно построить намеренно. В системе, где хеш служит ключом, это означает подмену содержимого. SHA-256 определён в FIPS 180-4.

2. Не доверяйте хешу от клиента без проверки. Если сервер принимает файл по заявленному хешу и не пересчитывает его, злоумышленник может сослаться на чужой объект и получить к нему доступ. Правило: сервер всегда вычисляет хеш сам, а значение клиента использует только как подсказку.

3. Учитывайте конфиденциальность при мгновенной загрузке. Ответ «такой файл уже есть» раскрывает факт наличия содержимого у другого пользователя. Для приватных данных мгновенную загрузку не применяют либо проверяют право доступа к найденному объекту.

4. Ведите подсчёт ссылок. Объект хранится один, а ссылаются на него многие записи. Удаление одной записи не должно удалять данные, пока на них есть другие ссылки.

CREATE TABLE blobs (
    sha256      CHAR(64) PRIMARY KEY,
    size_bytes  BIGINT NOT NULL,
    ref_count   INTEGER NOT NULL DEFAULT 0
);

5. Удаляйте по порогу, а не сразу. Запись, у которой ref_count стал нулевым, удаляется фоновой задачей с задержкой, чтобы отменить случайное удаление.

6. Храните размер вместе с хешем. Совпадение хеша при разном размере невозможно, но поле размера упрощает диагностику и проверку квот.

7. Сравнивайте хеши безопасно. Если значение используется как секрет (например, в токене), сравнение должно выполняться за постоянное время — hmac.compare_digest.

Рекомендации:

1. Вычисляйте хеш при приёме, а не по расписанию. Отложенный подсчёт означает, что дубликаты уже заняли место.
2. Используйте дедупликацию и для артефактов сборки. Идентичные слои образов и пакеты не нужно хранить дважды; о версионировании артефактов — в статье про артефакты сборки.
3. Делайте дедупликацию идемпотентной. Повторный приём того же файла не должен создавать новую запись — принцип описан в статье про идемпотентность.
4. Не дедуплицируйте шифрованные данные до шифрования. После шифрования одинаковые файлы дают разные байты, и дедупликация перестаёт работать.
5. Измеряйте эффект. На наборах с уникальными файлами дедупликация даёт только накладные расходы на подсчёт хеша.

Практический сценарий: хранилище выросло втрое из-за повторяющихся вложений

Контекст: сервис приёма документов хранил вложения пользователей. За квартал объём вырос втрое, при этом число уникальных документов увеличилось незначительно.

1. Диагностика. Выборочная проверка показала, что один и тот же PDF встречался в системе десятки раз: пользователи загружали типовые формы и шаблоны.
2. Оценка эффекта. Подсчёт SHA-256 по выборке из 10 000 объектов показал, что уникальны 34 % содержимого.
3. Действия. (а) Ввели таблицу blobs с хешем как первичным ключом и счётчиком ссылок; (б) приём файла начали с вычисления хеша на сервере и проверки существования; (в) при совпадении создавали только запись-ссылку, без копирования данных; (г) добавили фоновую задачу удаления объектов с нулевым счётчиком старше 30 дней; (д) отказались от мгновенной загрузки по заявленному клиентом хешу из-за риска раскрытия наличия документа.
4. Миграция. Существующие объекты обработали пакетно: вычислили хеши, сгруппировали дубликаты, оставили по одной копии и обновили ссылки.
5. Результат. Объём сократился на 62 %; повторная загрузка типового документа перестала занимать место, а проверка целостности стала возможной по сохранённому хешу.

Вывод: дедупликация по содержимому даёт наибольший эффект там, где файлы повторяются, — шаблоны, формы, артефакты сборки. Обязательные условия: сервер вычисляет хеш сам, ведётся подсчёт ссылок, удаление отложено.

FAQ

Возможна ли коллизия SHA-256 на практике? Случайная коллизия требует порядка 2^128 попыток, что недостижимо. Практические атаки известны для MD5 и SHA-1, поэтому их не используют там, где хеш служит идентификатором.

Чем дедупликация по файлам отличается от блочной? Файловая ищет одинаковые файлы целиком, блочная — одинаковые фрагменты внутри разных файлов. Блочная эффективнее на больших похожих файлах, но сложнее в реализации и обслуживании.

Что делать, если нужно изменить содержимое дедуплицированного файла? Создавать новый объект с новым хешем. Изменение существующего нарушит все ссылки на него — это основное свойство content-addressable хранилища.

Подходит ли дедупликация для баз данных? На уровне приложения — да, для вложений и артефактов. Дедупликация внутри СУБД зависит от возможностей конкретной системы и обычно применяется на уровне хранилища.

Источники: NIST FIPS 180-4, Git Internals, Python hashlib — ссылки в шапке.