Разбор: одинаковые файлы на диске

Если ты умеешь строить проверку ступенями от дешёвого признака к точному и знаешь, зачем каноническая форма, листай до «Теперь сам».

Как думаешь, с чего начать

На файловом сервере полмиллиона файлов, место кончается. Нужно найти копии. Первая мысль - сравнить каждый файл с каждым. Сколько это пар? И какое свойство файла можно проверить, вообще не открывая его?

Ответь себе до чтения. Пар - около 1,25 · 10¹¹: даже по микросекунде на пару это полтора дня, а сравнение пары - это чтение двух файлов с диска, и счёт идёт на годы. А не открывая файла, можно узнать его размер: файлы разного размера заведомо разные, и большинство пар отсеивается без чтения единого байта.

На что это похоже

Поиск свидетеля в толпе. Не опрашивают каждого - сначала «кто был здесь в два часа?», это отсекает почти всех. Оставшихся спрашивают «что видели?» - это короткий разговор. И только с теми, чьи ответы совпали, говорят подробно. Каждая ступень дороже предыдущей, но к ней доходит всё меньше людей.

Механизм: от просьбы к модели

Пройдём вопросы из главы о чтении задачи.

Вход - пути к файлам; размеры известны без чтения - их хранит файловая система в записи о файле, вместе с именем и датой изменения (это метаданные). Их показывает ls -l - «длинный» формат списка: в строке -rw-r--r-- 1 user user 4365 окт 27 23:42 a.conf размер - число 4365 перед датой. Содержимое же узнаётся только чтением, и чтение дорогое (диск, сеть). Вид ответа - все группы копий: это «все», но ответ не длиннее списка файлов - каждый файл попадает не больше чем в одну группу. Программа ниже печатает число пар-копий, чтобы сравнить два способа, число групп и первые три из них; весь список gruppy - списки номеров файлов - и отдают заказчику. Что значит «одинаковые» - побайтно равные; если заказчик имел в виду «равные по смыслу», это другая задача (второй разбор). Размер - 5 · 10⁵ файлов: n² пар не проходит ни при каком бюджете.

Модель. Это группировка по ключу: файлы с равным ключом - кандидаты в копии. Идеального ключа («содержимое целиком») нет - его дорого получить и сравнить. Поэтому ключей несколько, от дешёвого к точному, и каждый следующий применяется только внутри групп предыдущего:

Так устроены утилиты поиска копий: fdupes, например, по своему описанию сравнивает размеры и MD5-подписи, а затем проверяет файлы побайтно.

Правило

Когда точная проверка дорогая, строй её ступенями: дешёвый признак отсеивает большинство, точная проверка работает только внутри групп с равным признаком. Совпадение хеша - кандидат, а не доказательство: последняя ступень - всегда точное сравнение.

Разбор: копии ступенями

Модель сервера: 80 файлов одного формата - у всех общий заголовок, четыре размера, примерно каждый четвёртый файл - копия одного из прежних. Считаем сравнения пар и прочитанные байты.

import random

random.seed(11)
bukvy = "abcdefgh"

def sluchajnyj(dlina):
    s = ""
    for i in range(dlina):
        s = s + bukvy[random.randint(0, 7)]
    return s

# 80 файлов одного формата: общий заголовок, четыре размера,
# примерно каждый четвёртый - копия какого-то из прежних
zagolovok = "HDR:v2|cfg|"
fajly = []
for i in range(80):
    if i > 0 and random.random() < 0.25:
        fajly.append(fajly[random.randint(0, i - 1)])
    else:
        dlina = random.choice([30, 40, 50, 60])
        fajly.append(zagolovok + sluchajnyj(dlina))

schet = {"пар": 0, "байт": 0}

def ravny(a, b):
    # побайтно, пока не нашли различие
    schet["пар"] = schet["пар"] + 1
    if len(a) != len(b):
        return False
    for i in range(len(a)):
        schet["байт"] = schet["байт"] + 2     # символ - байт: латиница
        if a[i] != b[i]:
            return False
    return True

def hesh(f):
    # читает файл целиком один раз; полиномиальный хеш (раздел 7):
    # множитель 131 и простой модуль 10⁹ + 7 - обычный выбор
    h = 0
    for ch in f:
        schet["байт"] = schet["байт"] + 1
        h = (h * 131 + ord(ch)) % 1000000007
    return h

# наивно: каждая пара файлов сравнивается
par = 0
for i in range(len(fajly)):
    for j in range(i + 1, len(fajly)):
        if ravny(fajly[i], fajly[j]):
            par = par + 1
print("каждый с каждым: копий", par, "| сравнено пар", schet["пар"],
      "| прочитано байт", schet["байт"])

# ступенями: размер (бесплатно) -> хеш -> побайтно при равных хешах
schet["пар"] = 0
schet["байт"] = 0
po_razmeru = {}
for i in range(len(fajly)):
    r = len(fajly[i])
    if r not in po_razmeru:
        po_razmeru[r] = []
    po_razmeru[r].append(i)
par = 0
gruppy = []         # ответ заказчику: номера файлов каждой группы копий
for r, gruppa in sorted(po_razmeru.items()):
    if len(gruppa) < 2:
        continue
    po_heshu = {}
    for i in gruppa:
        h = hesh(fajly[i])
        if h not in po_heshu:
            po_heshu[h] = []
        po_heshu[h].append(i)
    for h, g in po_heshu.items():
        # равный хеш - ещё не равенство: каждый файл сравниваем
        # с представителем каждой уже найденной подгруппы копий
        podgruppy = []
        for i in g:
            najden = False
            for pg in podgruppy:
                if not najden and ravny(fajly[pg[0]], fajly[i]):
                    par = par + len(pg)       # i - копия всех в pg
                    pg.append(i)
                    najden = True
            if not najden:
                podgruppy.append([i])
        for pg in podgruppy:
            if len(pg) > 1:
                gruppy.append(pg)
print("ступенями:       копий", par, "| сравнено пар", schet["пар"],
      "| прочитано байт", schet["байт"])
print("групп копий:", len(gruppy), "| первые три:", sorted(gruppy)[:3])
razmery = []
for g in gruppy:
    razmery.append(len(g))
print("размеры групп:", sorted(razmery))

каждый с каждым: копий 21 | сравнено пар 3160 | прочитано байт 21086
ступенями:       копий 21 | сравнено пар 17 | прочитано байт 6664
групп копий: 13 | первые три: [[0, 1, 2], [3, 73], [4, 56]]
размеры групп: [2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3]

Ответ один, работа разная. Пары сходятся с группами: девять пар дают двойки и по три - четыре тройки, 9 + 12 = 21. «Каждый с каждым» сравнил все 80 · 79 / 2 = 3160 пар; ранний выход по первому различию спас его от полного чтения, но общий заголовок заставил каждую пару файлов одного размера читать хотя бы его. Ступени сделали 17 побайтных сравнений: каждый файл с совпавшим хешем сравнивался с представителем своей подгруппы, а не со всеми её членами. Читали так: каждый файл из групп с равным размером - один раз под хеш, плюс оба файла каждого из 17 сравнений ещё раз. Представитель большой группы перечитывается на каждой своей копии, но копий мало, и это слагаемое растёт с числом копий, а не с n². Прикинем 5 · 10⁵ файлов по мегабайту. Пар 1,25 · 10¹¹; если на пару уходит хотя бы миллисекунда (открыть два файла и прочитать начало), это около четырёх лет. Один проход под хеш при чтении 200 МБ/с - 5 · 10⁵ МБ / 200 ≈ 2500 с, меньше часа, плюс сравнения копий. Годы против часа - а точные числа для своего сервера получаются подстановкой своих размеров и скорости диска.

Заметь, как устроена последняя ступень: файл сравнивается с представителем подгруппы, а не со всеми её членами. Равенство транзитивно: равный представителю равен и всем остальным. А если хеш совпал у разных файлов, они просто окажутся в разных подгруппах. Коллизия стоит лишних сравнений - каждый следующий файл с этим хешем сверяется с представителем каждой чужой подгруппы, - но не ошибки. При хорошем хеше коллизии редки. При слабом хеше или подобранных злоумышленником файлах подгрупп с одним хешем много, и сравнения снова растут квадратично - поэтому хеш берут хороший (раздел 7).

Разбор: одинаковые по смыслу и слабый хеш

Теперь заказчик уточняет: «одинаковые» конфиги - это те, что различаются только порядком строк и пробелами в конце. Побайтное сравнение такие не найдёт. Задача сводится к предыдущей канонической формой - преобразованием, после которого равные по смыслу объекты становятся равными побайтно: убрать хвостовые пробелы, отсортировать строки. Ступени тогда работают на канонических формах: размер и хеш считают от них, а не от исходных файлов, - иначе конфиг 2 с лишним пробелом отсеется уже на размере. И рядом - урок про хеш: что будет, если ключом взять слишком слабую функцию.

konfigi = [
    ["port=80", "host=a", "log=on"],
    ["host=a", "log=on", "port=80"],
    ["log=on ", "port=80", "host=a"],
    ["port=80", "host=b", "log=on"],
    ["port=8", "host=a", "log=on0"],
]

def kanon(stroki):
    # каноническая форма: без пробелов в конце, строки по порядку.
    # rstrip(" ") снимает только пробелы - табуляция по условию значима
    chistye = []
    for s in stroki:
        chistye.append(s.rstrip(" "))
    return "\n".join(sorted(chistye))

def slabyj_hesh(stroki):
    # сумма кодов символов: порядок и границы строк не видны
    h = 0
    for s in stroki:
        for ch in s.rstrip(" "):
            h = h + ord(ch)
    return h

def gruppy(klyuch_f):
    po = {}
    for i in range(len(konfigi)):
        k = klyuch_f(konfigi[i])
        if k not in po:
            po[k] = []
        po[k].append(i)
    out = []
    for k, g in po.items():
        if len(g) > 1:
            out.append(g)
    return sorted(out)

def kak_est(stroki):
    return "\n".join(stroki)

print("точное совпадение:  ", gruppy(kak_est))
print("каноническая форма: ", gruppy(kanon))
print("слабый хеш:         ", gruppy(slabyj_hesh))

точное совпадение:   []
каноническая форма:  [[0, 1, 2]]
слабый хеш:          [[0, 1, 2, 4]]

Каноническая форма нашла группу 0, 1, 2 - три записи одного конфига. Слабый хеш - сумма кодов символов - склеил с ними и конфиг 4, где port=8 и log=on0: те же символы, иначе разложенные по строкам. Это граница правила про ступени: хеш - фильтр, и если он слабый, через него проходят разные файлы. Поэтому последняя ступень - сравнение канонических форм целиком, а хорошая хеш-функция (раздел 7) просто делает так, чтобы до этой ступени доходило мало лишнего.

Что ломается без этого

Сравнение каждого с каждым. Работает на тестовой папке из ста файлов и не заканчивается на сервере.

Удаление по совпадению хеша. Хеш совпал - файл удалён; при слабом хеше это разные файлы, и данные пропали. Удаляют только после побайтной проверки.

Не тот смысл «одинаковых». Побайтный поиск отчитался «копий нет», а заказчик видел десятки одинаковых конфигов с разным порядком строк.

Зачем это в работе

Тот же приём живёт везде, где проверка дорогая: дедупликация в резервном копировании (сначала размер и хеш блока), поиск дублей клиентов в базе (сначала нормализованный телефон, потом сравнение имён), проверка «изменился ли файл» в системах сборки (сначала время изменения и размер, потом хеш). Каноническая форма - тоже повсюду: нижний регистр для домена e-mail, сортированные ключи JSON перед сравнением, нормализованные пути.

Теперь сам

1. На диске 10⁶ файлов, все одного размера. Что изменится в схеме ступеней?
2. Ключ «дешёвая ступень» - первые 4 КБ файла. В каком наборе файлов она почти ничего не отсеет?
3. Придумай каноническую форму для «одинаковых» e-mail: Ivan.Petrov@Mail.RU и ivan.petrov@mail.ru.