В ZFS появилась поддержка исключения дубликатов

> для каждого блока данных в ZFS вычисляется контрольная сумма по алгоритму SHA256. Если данная контрольная сумма уже присутствует в хэше, то запись такого же блока данных, который уже есть в хранилище, не производится, а создаётся ссылка на уже имеющийся блок данных

АААаааа!!!! Оно съело их мозг, и теперь сожрет мозг и нам!!!! Они судят об идентичности данных по контрольной сумме! Если сумма букв вашей фамилии совпадает с суммой букв в другой фамилии, то вас застрелят а другой будет жить сразу по двум паспортам!

google venti+fosil

в plan9 это уже реализовано и есть множество высказываний по поводу потенциальных коллизий.

То есть это не шутка и не опечатка? Оно ДЕЙСТВИТЕЛЬНО так работает?!

да http://en.wikipedia.org/wiki/Venti только пацтол не падай.

Тебе пояснить разницу между контрольной суммой и хешем (хэш-кодом/дайджестом/криптографической контрольной суммой) или сам погуглишь?

Любой хеш имеет коллизии. Вот перемешаются кусочки mp3 файлов, будете знать.

А как же потенциальные коллизии?

Это как в LessFS?

> Статистика, собранная за два с половиной года на десяти серверах Google, показала, что количество ошибок в RAM гораздо выше, чем предполагалось ранее. В среднем на каждый модуль DIMM приходится 3751 ошибка в год. Если в микросхеме не реализована технология ECC, то эти ошибки так и остаются неисправленными.

http://m.habrahabr.ru/post/71748/

Вероятность коллизии много-много порядков меньше вероятности порчи данных, загруженных в память. Говорить о коллизиях (если их не искать специально) просто смешно.

Справедливости ради отмечу, в git работа с ревизиями во многом основана на хешах. И коллизии там тоже могут привести к печальным последствиям. Вроде уже в Talks или Development обсуждали.

Sun запускает новый амбициозный распределённый проект dedup по поиску коллизий в SHA256. :)

Они собираются взломать собственную ФС! NO WAY!

реквестирую матиматик-кунов с алгоритмами вычисления максимального размера блока хэш от которого не имеет коллизий

блок должен быть размером не больше размера хэша :)

спасибо КО

Предлагаю изобрести алгоритм позволяющий однозначно отображать любое количество данный в однобитный хеш... Человечество будет нам благодарно...

Нифиговый у вас будет архиватор :D

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

То есть нам нужны всего лишь биты с плавающей запятой.

> То есть нам нужны всего лишь биты с плавающей запятой.

Для этого нужно всего лишь перевести бит в жидкое агрегатное состояние, и бросить в него битонерастворимую запятую...

у военных такие есть, но разве ж они поделятся

Предположим размер блока 4К, размер ФС 4Т, имеем ~ Г*Г=10^18 возможных случаев коллизии, если размер ША256 -- действительно 256 бит, то вероятность коллизии будет ~ 10^(18-77)=1/10^59, теперь допустим 100М таких юзеров обновляют полностью содержимое своих дисков за допустим месяц (стирают все старые торренты и закачивают новые), то коллизия имеет вероятность 1/10^51 в месяц.

при размере ФС 4000ТБ получим 1/10^45 в месяц

> Наиболее заметный эффект технология исключения дубликатов проявляется при организации резервного копирования

Ну еще бы! Автолинкование на уровне блоков - имеено то, о чём мечтают при создании бэкапов. 10 милисек - и тетрабтайтный бэкап готов!

>В среднем на каждый модуль DIMM приходится 3751 ошибка в год.

У наркоманов приход? Больше десяти ошибок на модуль _ежедневно_ ?! Ну вы понели.

sdio ***** (04.11.2009 8:52:57) >Сжатие и дедупликация вещи ортогональные.

В общем, да.

Однако.

Дедупликация и так учитывает уникальные блоки данных и не увеличивает количество дубликатов, а наоборот — меньшает их (как бы логично из названия механизма). Улучшается скорость ввода-вывода, так как при операциях с одинаковыми файлами из носителя в память загружается только один блок данных (например, лицензионное соглашение в куче текстовых файлов будет одно, и часть блоков данных, содержащих его, одинаковы). Алгоритмы компрессии не задействуются — меньше расход ресурсов CPU.

Блоки данных нельзя сжать по отдельности, поэтому в ФС сжимаются файлы, состоящие из этих блоков. Алгоритм сжатия слишком интеллектуальный, чтобы не учитывать уникальность блоков, а жать весь файл наиболее оптимальным образом. Например, два текстовых файла, отличающихся несколькими байтами, будут ужаты и иметь абсолютно все отличающиеся блоки данных. ВСЕ блоки данных — что в случае дедупликации быть не могло в принципе. Для систем контроля версий сжатие на лету будет накладно как по объёму занимаемого места, так и по времени доступа. Так что для /usr/src дедупликация — самое то, если нужен быстрый доступ к исходникам и их модификация.

Разреженные файлы. Естественно, такие вещи имеют много одинаковых блоков сами по себе и ужимаются очень хорошо. Так что дедупликация здесь работает как простое RLE-«сжатие» данных, а сжатие на лету алгоритмом GZIP может ещё больше уменьшить занимаемое файлом место.

Обычные бинарные файлы, файлы архивов и мультимедиа файлы — здесь оптимизируются только заголовки (и то не все). Дедупликация и сжатие вообще не помогут НИКАК.

Интересная фича.

Ну, для read-only оно может и забавно, но вот запись в файл может испоганить страшно.

>блок должен быть размером не больше размера хэша :)

Вообще-то нет. man сжатие_данных

когда в ФС нового поколения ждать модуля для приготовления кофе?

В NetApp это работает уже года два. и никаких коллизий не наблюдали. падение производительности - 5-7%. бонус - в зависимости от характера данных.

для SATA эта штука врядли кому пригодится. а вот для SAS/SSD - экономия налицо.

p.s. предрекаю срач в стиле "вот шлюха, не достанься же ты никому" опять страниц на 5 минимально.

интересно насколько затормозится скорость записи ? http://www.cryptopp.com/benchmarks.html

Мутная на мой взгляд фича. Я не спорю, может и имеется где то такая острая необходимость дедупликации, но на мой взгляд больно уж много накладных расходов на нее надо. SHA256 надо посчитать (это все таки не так быстро), потом их надо хранить где то для всех блоков. Предположим мы записываем новый блок, наши действия - посчитать SHA256, поискать в базе этих SHA, а нет ли там такого же, если есть то повезло, а если нет записать блок, добавить в базу новый SHA256. При чтении, если в файле присутствует такой блок значит файл 99.99% фрагментированный, что то же не добавляет скорости. А преимущества дедупликации какие то сомнительные. Может я чего то не понимаю?

Фича то интересная. ZFS не останавливается в развитии, это радует.

А никто не подумал, что при нахождении блоков с одинаковым хешем, фс сравнит также и содержимое блоков? Таким образом, на коллизии пох.

+тормоза впрочем...

>А преимущества дедупликации какие то сомнительные. Может я чего то не понимаю?

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

Еще бы они написали исследовательскую утилиту, которая выводила бы количество блоков в системе, из них с одинаковой суммой SHA256 столько то. Было бы очень наглядно, хотя наверное и долго бы выполнялась эта утилитка.

SHA256 надо посчитать (это все таки не так быстро), потом их надо хранить где то для всех блоков

Как известно, для каждого блока данных в ZFS вычисляется контрольная сумма по алгоритму SHA256

Т.е. оно и так вычисляется и хранится, вне зависимости от того, включена ли дедупликация.

А преимущества дедупликации какие то сомнительные

Первое, что приходит в голову - хранение больших объемов данных разных пользователей, среди которых с огромной вероятностью есть схожие. Таки пользователи далеко не всегда блещут оригинальностью в том, что выкачивают.

Или просто файлохранилище, которому некритична скорость, но место понапрасну лучше бы не тратить.

> У наркоманов приход? Больше десяти ошибок на модуль _ежедневно_ ?! Ну вы понели.

For example, we observe DRAM error rates that are orders of magnitude higher than previously reported, with 25,000 to 70,000 errors per billion device hours per Mbit

Значит, на 1Гбайт будет 1 ошибка за время от 2 до 5 часов.

А по ссылке и вовсе указывают, что в определенных случаях это поднимет производительность:

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

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

>зато если общий для всех файлов сектор умрет физически

каким образом? еще раз - для сохо с SATA дедупликация не нужна. дешевле еще винт докупить. да и данные такие врядли встретятся.

Data de-duplication in ZFS and elliptics network (POHMELFS)

лет 20 назад было бы актуально. сейчас при обьеме жд в терабайты оно нафиг не надо. нашли бы лучше более полезное применение ресурсам цпу :)

> при обнаружении коллизий, фс сравнит так же и содержимое
Где это написано?
А файловая система вкусная, жаль в линуксе нету (фьюз не в линуксе, а в юзерспейсе)

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

>> Первое, что приходит в голову - хранение больших объемов данных разных пользователей, среди которых с огромной вероятностью есть схожие. Таки пользователи далеко не всегда блещут оригинальностью в том, что выкачивают.

Для реализации этой фичи не требуется писать ФС.

> Тебе пояснить разницу между контрольной суммой и хешем (хэш-кодом/дайджестом/криптографической контрольной суммой) или сам погуглишь?

Никакой кроме вероятности/частоты колизий.

И тут все вспоминают старые добрые расчёты маркетоидов ШТЕУДа на тему частоты возникновения ошибки в первых пнях....

>>блок должен быть размером не больше размера хэша :)

>Вообще-то нет. man сжатие_данных

Вообще то да. Сожми архивированныйф файл тем же архиватором еще раз.

> А никто не подумал, что при нахождении блоков с одинаковым хешем, фс сравнит также и содержимое блоков? Таким образом, на коллизии пох.

Я, Я подумал! Вообще это более чем логично, почему то по другому и не представлял.