?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

ZFS dedup: Trust or verify? - morfizm


Mar. 7th, 2015 02:25 pm ZFS dedup: Trust or verify?

"If you accept the mathematical claim that a secure hash like SHA256 has only a 2\^-256 probability of producing the same output given two different inputs, then it is reasonable to assume that when two blocks have the same checksum, they are in fact the same block. You can trust the hash. An enormous amount of the world's commerce operates on this assumption, including your daily credit card transactions. However, if this makes you uneasy, that's OK: ZFS provies a 'verify' option that performs a full comparison of every incoming block with any alleged duplicate to ensure that they really are the same, and ZFS resolves the conflict if not. To enable this variant of dedup, just specify 'verify' instead of 'on':..." (from https://blogs.oracle.com/bonwick/entry/zfs_dedup)

Yes, quite uneasy. Using "verify", of course :)
Reliance on hash for exact matching was one of my big concerns with WHS (Windows Home Server). I am really glad that ZFS is paranoiac-friendly.

Tags: ,

46 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:_m_e_
Date:March 8th, 2015 02:10 am (UTC)
(Link)
and probability of SHA256 hash collision vs. probability of undetected bitflip in your ECC memory?
From:morfizm
Date:March 8th, 2015 07:47 am (UTC)
(Link)
You aren't picking the right probabilities to compare. You need to compare chance of data corruption when you trust block hashes for dedup to chance of data corruption in case of undetected ECC memory error. This is totally different issue, because (a) chance of bugs in implementation is much higher for #1, and (b) people can find and use known collisions that may end up screwing up my file system. Unless there's a proof that data blocks are additionally randomized using my encryption key or something. Here, again, we go back to the chance of bugs thing, since we have to rely that FreeNAS/ZFS implementation is trustworthy. It's much easier for me to trust that ECC memory works as designed.
From:_m_e_
Date:March 8th, 2015 09:18 am (UTC)
(Link)
There are two types of problems with collisions
1) Someone finds a few pairs of collisions - somewhat possible. But what's harm here? One of two untrusted files will be "merged" into another one. No trusted file is harmed in process.
2) Someone finds a way to create collision for any file. Dangerous but very unlikely.
From:morfizm
Date:March 8th, 2015 07:48 am (UTC)
(Link)
Also, the contents of the disk is not random. Certain patterns are much more unlikely than others. Will you provide a proof that chance of collision is still very low, if you have to omit randomness assumption and study the real thing? :)
From:kot_begemot
Date:March 8th, 2015 04:08 am (UTC)
(Link)
dedup в ZFS сделан настолько отвратительно, что практически уже неважно, включать совершенно ненужную проверку, или нет - производительность по-любому совершенно убита.
From:morfizm
Date:March 8th, 2015 07:42 am (UTC)
(Link)
Меня performance дедупа мало волнует. Волнует space efficiency для конкретного юс-кейса: image-бэкапы клиентских компьютеров: full and incremental. Во-первых, они сжимаются где-то в полтора-два раза, во-вторых, второй full backup очень мало отличается от предыдущих, в-третьих, одни и те же системные файлы есть на разных компьютерах. Оно должно всё дедупаться. WHS это делал (!), учитывая всё вышеперечисленное. Как настроить ZFS, чтобы он тоже так делал? Я попробовал и чё-то слабовато, очень незначительные savings.

Есть подозрение, что 128K block size убивает возможность дедупа файлов из бэкапов разных компьютеров, т.к. кластеры там по 4K и одинаковые блоки misaligned. С другой стороны, если поставить 4K recordsize, то дедуп 1TB затребует 80GB RAM'а (320 байт на блок?), которого у меня нет. Я могу в лучшем случае опустить recordsize до 64K (размышляю вслух...)

Вы можете что-то посоветовать?

From:kot_begemot
Date:March 8th, 2015 12:12 pm (UTC)
(Link)
С ZFS - нет. Хорошего дедупа в открытом доступе нет ни у кого.
Есть отдельные компании, у которых есть очень дорогие enterprise class решения. На сегодня, пожалуй, лучшее решение на рынке incremental backup dedup - это Actifio. Как это ни смешно звучит, внутри они используют ZFS, но дедуп у них свой.
Если всё-таки заморачиваться с ZFS в качестве дедупнутого бэкапа, я бы делал отдельный небольшой пул и как можно меньший размер блока - сколько память позволяет.
Насчёт WHS - по непроверенным сведениям, там совершенно другой принцип дедупа. Пару лет назад на FAST была статья от Microsoft Research, где они анализировали статистики, и из неё следовало, что скорее всего у Microsoft dedup сделан не на блоковом, а на файловом уровне. Т.е. они банально чексамят файлы, а не блоки.


Edited at 2015-03-08 12:22 pm (UTC)
From:morfizm
Date:March 8th, 2015 08:06 am (UTC)
(Link)
Max cluster size for NTFS = 64K. Может, переделать клиентские компы на 64K-кластеры и поставить 64K record size в ZFS?
From:kot_begemot
Date:March 8th, 2015 12:18 pm (UTC)
(Link)
Это может помочь, при условии, что бэкапный софт бэкапит именно целые partitions. Что, вообще говоря, довольно редко встречается - обычно бэкапный софт делает некий аналог ленты (т.е. tar файла), обходя дерево файловой системы по какому-то алгоритму.
Это также не решит проблему одинаковых файлов на разных хостах, т.к. почти с гарантией NTFS их разложит по-разному на разных железках.
Разве что речь идёт об очень большом количестве маленьких (64К и меньше) файлов.
Про то что при увеличении размера блока резко испортится утилизация диска на NTFS мы, понятное дело, не говорим вовсе. Хотя, в таком раскладе random read performance должна несколько подрасти.


Edited at 2015-03-08 12:19 pm (UTC)
From:ermouth
Date:March 8th, 2015 11:24 am (UTC)
(Link)
Тут, конечно, хитрый маркетинг, больше похожий на несколько враньё.

Блоков в реальной жизни не бывает всего два, стало быть оценка в 2-256 мягко говоря занижена на десятки порядков. Парадокс дней рождений же.

Edited at 2015-03-08 11:25 am (UTC)
From:morfizm
Date:March 8th, 2015 12:02 pm (UTC)
(Link)
Я запустил считалку, чтобы посчитать точно какова вероятность коллизий для 10M файлов (весьма reasonable оценка всего количества файлов, которое домашний пользователь может "потрогать" за много лет, если, конечно, temporary internet files не считать... кстати, а их хорошо бы считать, т.к. они представляют из себя vulnerability если восстанавливать их из бэкапа, а в них порча из-за коллизий; но для простоты посчитаем пока без них).

Запощу ответ минут через 15.

Edited at 2015-03-08 12:02 pm (UTC)
From:morfizm
Date:March 8th, 2015 01:32 pm (UTC)
(Link)
Для 10 млн файлов вероятность коллизии 2-210. Про -256 наврали, но 210 это тоже немало. Вероятность, что коллизия возникнет хотя бы у одного человека из 10 млрд будет на 10 десятичных порядков меньше, соотв., на 33 двоичных, т.е. 2-177 (или 10-54). Всё равно дохренища.

Мне кажется, настоящий catch:
1) в assumption'е случайного распределения хэшей (пойди докажи случайность),
2) в assumption'е того, что хэш нельзя сломать (уже сейчас есть методы нахождения коллизий, работающие на порядки быстрее, чем разрядность, см. http://en.wikipedia.org/wiki/SHA-2, and they keep coming!), скажем, в RSA у меня куда больше уверенности, чем в SHA-256.
3) в assumption'е, что оно корректно реализовано в данной системе (куда легче поверить, что побайтовая проверка корректно реализована).
From:morfizm
Date:March 8th, 2015 01:35 pm (UTC)
(Link)
Насчёт birthday attack - он позволяет за ~2^128 шагов сгенерировать коллизию. Это несколько другое, чем оценка коллизий уже существующих в природе, но, несомненно, злоумышленников учитывать надо, так что оно ставит upperbound. Там в википедии вроде и получше атаки есть.
From:andreyvo
Date:March 9th, 2015 01:11 am (UTC)
(Link)
Just because you're paranoid doesn't mean they aren't after you
From:morfizm
Date:March 9th, 2015 01:19 am (UTC)
(Link)
Yep. My favorite moment was either RED film (or maybe RED 2?) where one of the old guys was seemingly too paranoid, suspecting random people of being dangerous and watching them. Then all of these people turned out to be actually malicious =)