LINUX.ORG.RU

Контрольная сумма файла

 , ,


0

2

Пишу небольшую утилитку для бекапов файлов. В утилитке будет функционал вроде «если файл изменился - забекапить снова». В общем, определять, что файл изменился, нужно по контрольной сумме.

Вопрос: какой алгоритм использовать? MD5, SHA256? Какой из них надёжнее? Есть ли альтернативный алгоритм, возможно с меньше вероятностью получения одинаковых хэшей для разных файлов, но работающий быстрее? MD5 и SHA256 уже очень сильно нагружают машину, для утилиты бекапа слишком, её в идеале должно быть незаметно... Вопрос «Тот это файл или уже другой» буду определять не только по хэшу, а по хэш+путь+имя+время изменения, так что алгоритм можно бы и полегче, но не знаю какой. Углублять в криптографию неохота :)

★★★★★

можно другой вопрос?

на какой хрен тебе хеши? нельзя получать ивенты от ведра/фс?

Stil ★★★★★ ()

http://ru.wikipedia.org/wiki/Кольцевой_хэш

Применяется в алгоритме поиска подстроки Рабина — Карпа, а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32).

anonymous ()

Пользуюсь md5 в таких случаях.

MD5 и SHA256 уже очень сильно нагружают машину, для утилиты бекапа слишком, её в идеале должно быть незаметно...

А как ты хотел, надо же файл целиком прочитать, это самое затратное действие и есть (для больших файлов).

unfo ★★★★★ ()

Сколько там символов в хэше, раздели пополам. Единственность для хэша обеспечивается такой длиной данных. Например двухсимвольный хэш соответствует одному байту данных, можно подобрать несколько двухсимвольных комбинаций данных с одним и тем же хэшем.

anonymous ()
Ответ на: комментарий от Stil

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

Alve ★★★★★ ()
Ответ на: комментарий от anonymous

«Хорошая» хеш-функция отличается более-менее равномерным распределением вычисленных значений. Очевидно, что Adler-32 не удоволетворяет этому требованию для коротких данных (максимальное значение A для 128-байтного сообщения равняется 32640, которое ниже чем 65521 — число по которому берется операция модуля). Из-за этого недостатка разработчики протокола SCTP предпочли этому алгоритму CRC32, так как в сетевом протоколе необходимо хеширование коротких последовательностей байт. Точно как и для CRC32, для Adler-32 можно легко сконструировать коллизию, то есть для данного хеша найти другие исходные данные, имеющие то же значение функции.

Как-то уж слишком печально, хотя ТСа, вероятно, устроит.

unfo ★★★★★ ()
Ответ на: комментарий от Alve

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

В большинстве редакторов кнопка «Сохранить» неактивна же, пока изменения не будут внесены. Хотя можно добавить пробел, стереть его и сохранить.

З.Ы. Если большинство файлов текстовые, может стоит приспособить для этого дела какой-нибудь Mercurial, например?

unfo ★★★★★ ()
Ответ на: комментарий от unfo

З.Ы. Если большинство файлов текстовые, может стоит приспособить для этого дела какой-нибудь Mercurial, например?

Нет, большинство файлов будут бинарные и всяких форматов, неэффективно обрабатываемых всякими гитами и меркуриалами.

Alve ★★★★★ ()

Пишу небольшую утилитку для бекапов файлов.

Для начала: почему не использовать готовый rsync, tar -u или даже cp -u?

В общем, определять, что файл изменился, нужно по контрольной сумме.

Зачем по контрольной сумме? Можно же тупо сравнить файлы. И, кстати, быстрее, если только они не на одном физическом диске. Но если они на одном диске, то «бакап» будет уже не бакапом, т.к. если диск накроется, то накроется и сам файл и его бакап.

Вопрос: какой алгоритм использовать? MD5, SHA256?

Формально надёжнее тот, что длиннее. Т.е. из стандатных это sha512. Затем sha386, sha256, sha224, sha1 и md5.

большинство файлов будут бинарные и всяких форматов, неэффективно обрабатываемых всякими гитами и меркуриалами.

Вообще-то всякие гиты и меркуриалы вполне себе работают с бинарными файлами.

Итого: не морочь себе голову, используй то, что проще. Если так хочется именно контрольную сумму — бери её. Если под рукой есть готовая либа с sha512 — бери её. Если под рукой нет sha512, но есть md5 — бери её. Если можно ничего не писать, а просто заюзать готовый rsync/tar/cp — юзай их. :)

anonymous ()

Я советую по времени изменения

anonymous ()
Ответ на: комментарий от anonymous

Например, 10 серий «Звездных врат» по 900 метров каждая. Будем хеш считать?

anonymous ()
Ответ на: комментарий от anonymous

Можно исхитриться, ввести стратегии сравнения для типов файлов.
Например всё кино/музыку сравнивать по размеру, дате, имени и содержащейся внутри информации, такой как название, битрейт, кодек, разрешение и т.п. (уж явно быстрее чем считывать кучу серий по 900 метров, или кучу кино по много гиг). Ну и для контроля можно читать в нескольких разных местах небольшими блоками (а то можно нарваться на недокачанный файл допустим).

invy ★★★★★ ()

SHA1 и взять реализацию Торвальдса )

quest ★★★★ ()

еще можно использовать Git )))

quest ★★★★ ()

определять, что файл изменился, нужно по контрольной сумме

А по mtime не вариант, что ли? И make для резервирования использовать.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Alve

открыл посмотрел и нажал сохранить

И какой ненормальный редактор переписывает неизмененный файл?

Eddy_Em ☆☆☆☆☆ ()

Ты уверен, что машину грузит вычисление хеша а не считывание файла?

Legioner ★★★★★ ()
Ответ на: комментарий от Eddy_Em

Ну это я для примера, я точно не уверен, как себя ведут редакторы.

Alve ★★★★★ ()
Ответ на: комментарий от Eddy_Em

И какой ненормальный редактор переписывает неизмененный файл?

Очень многие, если не все. Для компиляции порой нужно просто обновить дату изменения файла.

Pavval ★★★★★ ()

а можно вопрос? чем rdiff-backup не устроил?

beastie ★★★★★ ()
Ответ на: комментарий от beastie

Потому что нужен свой алгоритм. Ну или скажем так, я хочу свой алгоритм бекапа :)

Alve ★★★★★ ()
Ответ на: комментарий от Pavval

Для компиляции порой нужно просто обновить дату изменения файла.

А не быстрей ли будет набрать touch file?

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Alve

1. Сравниваем даты
2. Если находим файл с обновленной датой, сравниваем размеры
3. Если размер не изменился, считаем контрольную сумму
4. Если суммы/размеры отличаются →

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Alve

ну, если только NIH или лабораторная. ☺

а так, если хочешь что бы было быстро, то

сверяешь ctime и размер, если сходится — то файл не менялся, идёш дальше; иначе если md5 разный, то бэкап, если одинатовый, то побайтовое сравнение, если сходится — то файл не менялся, идёш дальше; иначе бэкап.

как-то так, быстро и сердито. md5 забэкапеных файлов лучше хранить предрасчинанными.

PS: при таком подходе может уже и CRC32 хватить.

beastie ★★★★★ ()
Ответ на: комментарий от Eddy_Em

5. побайтовое сравнение, что бы исключить коллизии

beastie ★★★★★ ()
Ответ на: комментарий от Eddy_Em

… но железно ☺

к тому же коллизий будет и так не много и в больших файлах, даже если оно дойдёт до этого, всё равно врядли что-то меняться будет.

или k.o. критерий — побайтовое сравнение только если файл меньше, скажим, килобайта, если больше, то доверяем md5.

beastie ★★★★★ ()
Последнее исправление: beastie (всего исправлений: 2)
Ответ на: комментарий от Eddy_Em

А не быстрей ли будет набрать touch file?

А подумать? Нет, я подскажу: для сохранения файла нужно нажать Ctrl+S. Для «touch file» нужно открыть консоль или переключиться на нее, зайти в нужный каталог и там набрать touch <file>. И что быстрее?

Pavval ★★★★★ ()
Ответ на: комментарий от Pavval

Это если файл уже открыт. Кроме того, make-то все равно в консоли набираешь…

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Кроме того, make-то все равно в консоли набираешь…

Я что, дурак? Я F7 в IDE нажимаю.

Pavval ★★★★★ ()
Ответ на: комментарий от Pavval

Я что, дурак?

Это риторический вопрос.

anonymous ()

CRC32. Надежность 1 - 2^-32, считается быстро.

gadfly ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.