Задача:

Клиент-сервер

На сервере хранится некоторый (довольно большой) набор файлов.

Клиент тоже хранит некоторый набор файлов (ни как не связанный с файлами сервера).

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

Замечания:
1.Файлы могут быть размером от нескольких байт, до десятков гигабайт.
2.Данное действие может выполняться довольно часто.
3.Неизвестно какие файлы будут чаще обрабатываться маленькие, средние или громадные, хотя скорей всего небольшие файлы будут использоваться чаще.
4.К одному серверу могут подключаться несколько разных клиентов, а так же клиент может подключаться к нескольким серверам.
5.На одной машине может быть установлен как сервер, так и клиент, работающие с одними и теме же файлами.
6.Вероятность ошибки должна быть довольно низкой. Например: одна на миллион файлов, а лучше ещё меньше.

Есть идеи как это реализовать?

У меня некоторые идеи есть, но сначала хотелось бы услышать другие мнения.

Здравствуйте, KinK, Вы писали:

Еще одна программа синхронизации домовых файлопомоек с индивидуальными компами? Что-то подобное здесь уже обсуждалось — с файлом хранится хеш типа (размер, CRC. набор выбранных байт)

Здравствуйте, KinK, Вы писали:

KK>Задача:

KK>Клиент-сервер

KK>На сервере хранится некоторый (довольно большой) набор файлов.

KK>Клиент тоже хранит некоторый набор файлов (ни как не связанный с файлами сервера).

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

KK>Замечания:
KK>1.Файлы могут быть размером от нескольких байт, до десятков гигабайт.
KK>2.Данное действие может выполняться довольно часто.
KK>3.Неизвестно какие файлы будут чаще обрабатываться маленькие, средние или громадные, хотя скорей всего небольшие файлы будут использоваться чаще.
KK>4.К одному серверу могут подключаться несколько разных клиентов, а так же клиент может подключаться к нескольким серверам.
KK>5.На одной машине может быть установлен как сервер, так и клиент, работающие с одними и теме же файлами.
KK>6.Вероятность ошибки должна быть довольно низкой. Например: одна на миллион файлов, а лучше ещё меньше.

KK>Есть идеи как это реализовать?

KK>У меня некоторые идеи есть, но сначала хотелось бы услышать другие мнения.

одна на миллион? используешь хешфункцию, которая дает одинаковый хеш только в одно миллионном случае, так понимаю 20 битовый хеш хватит
используй какой нибудь самый длинный вариант хеш функций, sha-256, например, за глаза хватит, еще размер проверяй, ошибка одна на 2^256, хотя вот этот момент могу соврать, не специалист в криптографии

Здравствуйте, jhfrek, Вы писали:

J>Еще одна программа синхронизации домовых файлопомоек с индивидуальными компами?

Ага. Берешь хотя бы DC++ и изучаешь.

KK>У меня некоторые идеи есть, но сначала хотелось бы услышать другие мнения.
Вот собственно идеи реализации, которые были момент написания того поста:
1. Храним у клиента и сервера, для каждого файла, ID (идентификатор) рассчитанный по определённому алгоритму.
2. При запросе клиент отправляет серверу ID, сервер ищет его у себя и возвращает ответ.
3. ID-ы можно хранить в отсортированном виде, что бы ускорить поиск.
4. Ну и самое сложное, придумать алгоритм расчета ID.

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

Вторая мысль сделать размер ID динамичным, зависящим от размера файла. То есть ID = { filelen, hash (длины равной некоторой HashSize(filelen)) }.

Третья мысль для небольших файлов вместо хэш-кода можно попробовать использовать код, из которого однозначно можно декодировать содержимое файла. Это не должно существенно увеличить ID, так как вероятность коллизии для небольших файлов выше. Зато при заливке файла на сервер, не будет необходимости повторно заливать данные, сервер раскодирует файл по ID-у.

Четвертая мысль:
ID =””;
Если filelen = 0 то AddByte2ID(0) // ID = 0; размер ID = 1 байт
Иначе Если filelen < 255 то AddByte2ID(filelen), AddFile2ID(file) // размер ID = filelen + 1
Иначе Если filelen < (256*256-2+255) то AddByte2ID(255), AddInt2ID(filelen-255), AddHash2Id(file,HashSize(filesize))
Иначе Если filelen <(256*256*256*256-2+ (256*256-2+255) ) то AddByte2ID(255), AddByte2ID(255), AddByte2ID(255), AddLong2ID(filelen-(256*256-2+255)), AddHash2Id(file,HashSize(filesize))
Ну и так далее…Осталось только придумать HashSize().

Пятая мысль: Заменить AddFile2ID(file) на AddPackedFile2ID, хотя есть ли смысл паковать файлы до 255 байт?

Шестая мысль: ID = { filelen, hash (длины равной некоторой f(filelen)) } заменить (для файлов больших 254 байта) на ID = { filelen, filetype(file), hash (длины равной некоторой HashSize(filelen)) }, где filetype(file) — некоторый внутренний тип файла. Как варианты использовать вместо filetype — расширения файла, либо для основного набора файлов использовать нулевой тип, а не нулевыми типами обозначать файлы, для которых особенно критично уменьшить шанс ошибки.

Вопросы:
1. Кто что об этом думает?
2. Какие есть советы, предложения?
3. Какую взять HashSize()?
4. Какой использовать Хэш-алгоритм?

J>Еще одна программа синхронизации домовых файлопомоек с индивидуальными компами?
Не, задумка более глобальная, хотя и есть много общего, и это только маленькая её часть, жалко только, что скорей всего сил и терпения на осуществление этого проекта не хватит, но хоть мозги потренирую, развлекусь

J>Что-то подобное здесь уже обсуждалось
По каким словам легче найти? А то я с дуру ввёл в поиск слово хэш и подсел кучу интерсного читать Но оно все немного не по теме, как то самое найти?

J> — с файлом хранится хеш типа (размер, CRC. набор выбранных байт)
Тоже вариант! Только для небольших файлов подругому сделать, как я в нижнем посье написал.

Только интересно, что лучше/хуже и самое главное чем: md5 или crc+выбраные байты.

И какие стоит байты указывать? Наверное для более длинных файлов, больше байт и байты не определённые, а с номерами вычисляемыми определённым образом из размера и CRC.

Хотя наверное crc+bytes не стоит использовать, так как такой хэш, скорей всего, не будет криптографически стойким. (Про защиту от умышленой колизии, я забыл в условии написать )

W>Ага. Берешь хотя бы DC++ и изучаешь.
Ну, копаться в чужом коде не сильно бы хотелось. Лучше бы сначала в теории, алгоритмы и методы рассмотреть.

Хотя как это в DC++ реализовано жутко интересно!

Здравствуйте, KinK, Вы писали:
KK>У меня некоторые идеи есть, но сначала хотелось бы услышать другие мнения.
Идея очень простая. Пусть сервер умеет отдавать файлы по частям.
Шаг1: забираем первые N байт файла с сервера, и смотрим у себя, есть ли начинающиеся с них файлы
Если нет, то выходим с отрицательным результатом.
Если есть, то
Шаг 2: забираем с сервера следующие N байт этого файла и ищем среди файлов, найденных на шаге 1, байты.
Если байты на сервере кончились, и у нас есть ровно один файл, то мы получили полное соответствие.

Все остальное — лишь вариации этого банального алгоритма. Важно понимать, что 100% гарантию можно получить только полностью передав весь файл для сравнения.
Поэтому все улучшения могут быть связаны только с переупорядочиванием байтов так, чтобы раньше детектировать расхождения. Сравнение с начала — не самый эффективный способ, т.к. файлы имеют свойство содержать одинаковые хидеры. Хеш — достаточно неплохой способ, т.к. он гарантированно отличается для сильно похожих файлов. Хороший хеш имеет настолько низкую вероятность коллизии, что можно рискнуть и не проверять файл целиком. К тому же можно существенно улучшить результаты, если дополнительно хранить, к примеру, md5 посчитанный только для четных байт + md5 для нечетных байт. Вероятность случайного совпадения всех трех хешей настолько низка, что на нее можно с уверенностью забить, если от этого не зависит жизнь людей.