Опубликована (http://crypto.junod.info/2012/12/13/hash-dos-and-btrfs/) техника DoS-атаки на файловую систему Btrfs, манипулирующая коллизиями хэшей имён файлов. При создании примерно 500 файлов со случайными именами, их удаление происходит почти мгновенно. Но если выбрать имена файлов, вызывающих коллизии при их хэшировании, при удалении система начинает тратить чрезмерные ресурсы. Например, создав 500 файлов с именами, которые сводятся к 55 хэш-значениям crc32c, их удаление заняло настолько много времени, что в ходе эксперимента пришлось принудительно завершить процесс после того как его выполнение заняло 220 минут.
URL: http://crypto.junod.info/2012/12/13/hash-dos-and-btrfs/
Новость: https://www.opennet.ru/opennews/art.shtml?num=35593
Готова к продакшену, да? Поздравлямс сусю.
https://www.opennet.ru/opennews/art.shtml?num=35561
>При этом, в примечании к релизу SUSE Linux файловая система XFS рекомендуется для создания хранилища данных, а Btrfs для корневой ФСв таком варианте?
вполне.
> XFS рекомендуется для создания хранилища
> Btrfs для корневой ФСВы точно читать умеете? Хранилище, это там где положили и хранят. Корень, это там, где постоянно что-то меняется.
Если корень это там, где что-то постоянно меняется, то расскажи как нам милок, что есть /var?
> Если корень это там, где что-то постоянно меняется, то расскажи как нам
> милок, что есть /var?Так тенденция же идет к тому, что не будет ни каких тебе /var /usr и пр., будет только /. И линуксовые же админы с пеной у рта всем доказывают что все в / - это хорошо.
это называется — объяснение прописных истин.
корень (/) — это такое место, где хранятся файлы и каталоги, доступные по записи только привилегированным пользователям (как правило root), а также где содержаться точки монтирования других фс.
к последним относятся и tmpfs(shm/…) с точками монтирования в /run, /var/tmp, /tmp и тдэто понятно? не?
root НЕ доступен для записи кем попало (включая сабж) и не расшаривается как ресурс различными сервисами.
усвойте это.
чтобы понятнее уж совсем — рут это такой ц:\\видавс, который доступен для записи только админам.
$ testparm[SHARA]
path = /
read only = No
force directory mode = 1777
use sendfile = Yes
write cache size = 8192
case sensitive = Yes
strict locking = Yes
# cat /etc/exports/ master(rw) trusty(rw,no_root_squash)
А некоторые еще и через костры прыгают, в прорубь зимой ныряют, делают татуировки, пирсинг и в уши вставляют туннели.
>[оверквотинг удален]
> write cache size =
> 8192
> case sensitive = Yes
> strict locking = Yes
>
А, может, самба зачрутована. Не убедил. :)))))))))))
> А, может, самба зачрутована.Или запихана в LXC. В KVM-виртуалке.
>> А, может, самба зачрутована.
> Или запихана в LXC. В KVM-виртуалке.... на бездисковом сервере.
>это называется — объяснение прописных истин.
>корень (/) — это такое место, где хранятся файлы и каталоги, доступные по записи только привилегированным пользователям (как правило root), а также где содержаться точки монтирования других фс.http://lists.busybox.net/pipermail/busybox/2010-December/074...
http://www.osnews.com/story/25556/Understanding_the_bin_sbin.../
Прописная истина в том, что вся движуха с монтированием произошла от одной единственной причины - было мало места. Всё. Больше ничего. Вообще ничего. Никакой политики и религиозных взглядов на высшее предназначение отдельно монтируемых каталогов, никакой принудиловки. Твой юникс - твои правила.
А трындёж, что бтрфс лажает на одном типе задач, но, мол, на том типе нагрузок, характерном для корня и с вынесенными всем и вся на другие устройства каталогами, дак это и нестрашно совсем, остаётся просто трындёжом
Вы с дубу рухнули, где таких админов откопали.
А систему то как апдейтить?
У вас систему злоумышленник апдейтит?
вот нелегко нам злоумышленникам( все время палки в колеса подлые админы вставляют(
в цитаты!
/var это tmpfs, очевидно же
Прядочная женщина любит порядок: сегод7я один, завтра другой. Потаскуха - потоскует и идет спать.
> Готова к продакшену, да? Поздравлямс сусю.Выпустят патч и ФС приблизиться к идеалу еще на шажок.
zfs ещ в 2011 от такого страдала и ни чё так, 7 лет в продакшене. :D
http://www.securiteam.com/securitynews/5KP300U6UK.html
Только так и не видно его, продакшна этого, вот в чём соль.
> Только так и не видно его, продакшна этого, вот в чём соль.Лиц пубертатного возраста к продакшену не допускают.
>> Только так и не видно его, продакшна этого, вот в чём соль.
> Лиц пубертатного возраста к продакшену не допускают.Видимо да, в этом и причина...
> Лиц пубертатного возраста к продакшену не допускают.По тебе заметно :)
> Лиц пубертатного возраста к продакшену не допускают.Если так, то у ZFS нет шансов в продакшене.
у вас странный продакшен :-) Только не надо отмазываться рассказывая про университеты..
> у вас странный продакшен :-) Только не надо отмазываться рассказывая про университеты..Не, ну что вы, как можно! Продакшн - это изен, у которого пул из 3 дисков 18Мб/сек выжимает.
> Готова к продакшену, да? Поздравлямс сусю.Оракл сперва поздравь.
>> Готова к продакшену, да? Поздравлямс сусю.
> Оракл сперва поздравь.zfs не crc32 использует. А вполне себе SHA-256, чтоб ты знал. Где-где тама коллизии, гришь?
> zfs не crc32 использует. А вполне себе SHA-256, чтоб ты знал. Где-где
> тама коллизии, гришь?SHA256, говоришь? Как там с загрузкой CPU при создании 100500 файлов в каталоге?
> SHA256, говоришь? Как там с загрузкой CPU при создании 100500 файлов в каталоге?По-моему эти ламерюги элементарно перепутали хэши которые внутренняя функция хэш-таблицы с хэшами которые в роли чексуммы выступают. Бывает же такое ламерсто, а?! И смех и грех :). С одной стороны это не тред а просто перепись ламеров опеннета, эпически палящихся на непонимании того что есть хэш-таблица и как это работает. С другой - печально что на планете столько тупиц несущих с умным видом абсолютную чепуху.
> По-моему эти ламерюги элементарно перепутали хэши которые внутренняя функция хэш-таблицы
> с хэшами которые в роли чексуммы выступают. Бывает же такое ламерсто,
> а?! И смех и грех :). С одной стороны это не
> тред а просто перепись ламеров опеннета, эпически палящихся на непонимании того
> что есть хэш-таблица и как это работает. С другой - печально
> что на планете столько тупиц несущих с умным видом абсолютную чепуху.Он пониже спалился, угу.
checksum=on | off | fletcher2,| fletcher4 | sha256
>> По-моему эти ламерюги элементарно перепутали хэши которые внутренняя функция хэш-таблицы
>> с хэшами которые в роли чексуммы выступают. Бывает же такое ламерсто,
>> а?! И смех и грех :). С одной стороны это не
>> тред а просто перепись ламеров опеннета, эпически палящихся на непонимании того
>> что есть хэш-таблица и как это работает. С другой - печально
>> что на планете столько тупиц несущих с умным видом абсолютную чепуху.
> Он пониже спалился, угу.
> checksum=on | off | fletcher2,| fletcher4 | sha256Уймись уже. Контрольная сумма — частный случай хэширования.
> Уймись уже. Контрольная сумма — частный случай хэширования.Спич был за хэш-таблицы. А ты почему-то вспомнил чексуммирование области данных. Которое хэш-таблицам довольно перпендикулярно. FAIL :P.
>>> Готова к продакшену, да? Поздравлямс сусю.
>> Оракл сперва поздравь.
>zfs не crc32 использует. А вполне себе SHA-256, чтоб ты знал. Где-где тама коллизии, гришь?У тебя zfs межушного ганглия. Не офтопь, тут не про этот чудопепелац новость. Ей пользуются полтора землекопа в продакшне, да и досит она себя сама без посторонней помощи.
http://www.oracle.com/us/corporate/press/1555025
March 13, 2012
The Btrfs file system is now production-ready with this release. Standard in Oracle Linux, Btrfs supports data stores of up to 16 exabyte, is optimized for solid state disks, is easy to administer, and includes built-in data integrity.
>[оверквотинг удален]
>>zfs не crc32 использует. А вполне себе SHA-256, чтоб ты знал. Где-где тама коллизии, гришь?
> У тебя zfs межушного ганглия. Не офтопь, тут не про этот чудопепелац
> новость. Ей пользуются полтора землекопа в продакшне, да и досит она
> себя сама без посторонней помощи.
> http://www.oracle.com/us/corporate/press/1555025
> March 13, 2012
> The Btrfs file system is now production-ready with this release. Standard in
> Oracle Linux, Btrfs supports data stores of up to 16 exabyte,
> is optimized for solid state disks, is easy to administer, and
> includes built-in data integrity.Btrfs не сертифицирована для продакшена баз данных.
http://www.spinics.net/lists/linux-btrfs/msg19006.html
> Btrfs не сертифицирована для продакшена баз данных.А где был сертифицирован ZFS в бсд? Ну или даже в лине? Ах, нигде? Ну я так и подумал.
Хотя ты конечно в твоем праве покупать у оракля соляру на их конских условиях для их БД, если тебе сертификация так свербит. Иные сертифицированные конфиги тебе имхо не понравятся, т.к. там нет ZFS но есть Linux :)
>>> Готова к продакшену, да? Поздравлямс сусю.
>> Оракл сперва поздравь.
> zfs не crc32 использует. А вполне себе SHA-256, чтоб ты знал.Только в особых случаях — http://www.freebsd.org/cgi/man.cgi?query=zfs&apropos=0&sekti...
checksum=on | off | fletcher2,| fletcher4 | sha256
Controls the checksum used to verify data integrity. The default
value is on, which automatically selects an appropriate algorithm
(currently, fletcher4, but this may change in future releases). The
value off disables integrity checking on user data. Disabling
checksums is NOT a recommended practice.Changing this property affects only newly-written data.
Вы что, настолько дятлы что не отличаете хэши используемые как внутренняя функция хэш-таблиц от хэшей использыемых для проверки чексум? Пиндец. Откуда такие ламаки берутся? Не знают чем одно от другого отличается, зато поумничать уже вылезли.Ну-ка раскалывайтесь, бастарды, сколько из вас представляет как сделана хэш-таблица? И сколько из вас видело SHA-256 в виде функции для хэш-таблиц. Ну? :)
> Вы что, настолько дятлы что не отличаете хэши используемые как внутренняя функция
> хэш-таблиц от хэшей использыемых для проверки чексум? Пиндец. Откуда такие ламаки
> берутся? Не знают чем одно от другого отличается, зато поумничать уже
> вылезли.
> Ну-ка раскалывайтесь, бастарды, сколько из вас представляет как сделана хэш-таблица? И
> сколько из вас видело SHA-256 в виде функции для хэш-таблиц. Ну?
> :)В теории хэш-таблица легко может строиться и деревом на основе SHA-256, почему нет?
На практике сие могут сделать только идиоты.
Еще раз перечитал пост изена выше - ни хрена это не хеш-таблица, это чексуммирование данных.
> В теории хэш-таблица легко может строиться и деревом на основе SHA-256, почему нет?Потому что на практике от такой диверсии хэш-таблица изрядно тормознет. Всерьез криптостойкие алгоритмы делаются так чтобы коллизии вообще нельзя было подобрать с разумными затратами даже в единичном случае - там раундов преобразований дофига и скорость принесена в ущерб максимальной стойкости. Но пойнт хэш-таблицы только в том что она работает быстро и это мало зависит от числа элементов. Юзеж тяжелой хэш-функции убивает наповал практически смысл в хэш-таблице.
> На практике сие могут сделать только идиоты.
По-моему, идиоты тут все-таки те кто не отличил функцию хеширования в таблицах от функции чексуммирования данных. Вот это я понимаю, ололо на совесть :)
> Еще раз перечитал пост изена выше - ни хрена это не хеш-таблица, это чексуммирование данных.
Ну да, эти додики облажались :). Былинный отказ :)
>> В теории хэш-таблица легко может строиться и деревом на основе SHA-256, почему нет?На самом деле я просто использовал хэш-дерево на основе результата MD4 для хранения энного набора данных в бытности для быстрого поиска длинных подстрок. Обычной таблицы на коротких хешах не хватало (элементов также было прилично), и коллизий тоже нужно было минимум - поскольку при нахождении элемента требовалось сравнение всей подстроки. Поэтому строилось дерево из результатов шустрого криптохеша.
// и только позже до меня дошло, что проще сделать дерево на базе символов самой подстроки xD :) теперь оно реализовано именно так
> На самом деле я просто использовал хэш-дерево на основе результата MD4 для
> хранения энного набора данных в бытности для быстрого поиска длинных подстрок.Вариант, конечно, но кстати MD4 уже и не считается криптостойким - для него коллизии AFAIK научились генерить. Так что как криптоалгоритм он свое уже давно отлетал.
> Поэтому строилось дерево из результатов шустрого криптохеша.
> // и только позже до меня дошло, что проще сделать дерево на
> базе символов самой подстроки xD :) теперь оно реализовано именно такНа третий день Зоркий Глаз заметил что у сарая нет стены :)
> Вы что, настолько дятлы что не отличаете хэши используемые как внутренняя функция
> хэш-таблиц от хэшей использыемых для проверки чексум?
> Пиндец. Откуда такие ламаки берутся? Не знают чем одно от другого отличается, зато поумничать уже вылезли.Чексуммирование — частный случай применения хэширования! Хэш на основе CRC32 в ZFS не используется, но используется похожий на него алгоритм "fletcher".
> Ну-ка раскалывайтесь, бастарды, сколько из вас представляет как сделана хэш-таблица?
В общем случае это массив вида "хэш-список значений (ссылки на объект)". Структура данных может быть отсортирована по значению хэша — для быстрого поиска соответствий.
На входе функция получает точное имя объекта, в теле функции производится преобразование имени объекта в хэш, хэш ищется на совпадение в массиве, возвращается сопряжённое с хэшем значение (ссылка на объект). Так как разные имена объектов могут иметь одинаковый хэш (коллизии), то в таблице одному хэшу могут соответствовать несколько значений (несколько ссылок на объекты). В этом случае требуется уточнение, какой именно объект (ссылка) запрашивается, исходя из контекста запроса (текущий каталог, пространство имён и т.д.) — в последнем случае поиск нужного объекта усложняется и приводит к увеличению времени возврата результата. В идеале использования список значений (ссылок) объекта должен состоять из одного элемента, тогда коллизий не возникает и время выполнения функции стремится к O(1).> И сколько из вас видело SHA-256 в виде функции для хэш-таблиц. Ну? :)
В FreeBSD /etc/login.conf устанавливает функцию SHA-512 для пользовательских паролей:
default:\
:passwd_format=sha512:\Если интересно, можно глянуть на хэши таких паролей в vipw.
> Чексуммирование — частный случай применения хэширования! Хэш на основе CRC32 в ZFS
> не используется, но используется похожий на него алгоритм "fletcher".Только к хэш-таблицам все это ну вообще совсем не относится. Ни флетчер, ни sha из чексуммирования данных. Вот тут то вы и зафэйлили, бакланы.
> данных может быть отсортирована по значению хэша — для быстрого поиска соответствий.
В совсем простом случае короткий хэш может быть вообще влобешник индексом массива. Такие реализации бывают. И вполне имеют право на жизнь. В более сложных - что-то типа того что ты озвучил.
> в теле функции производится преобразование имени объекта
Пардон, в хэш-таблице есть ключи и значения. Ключи не обязательно имена или их хэши. А значения не обязательно объекты.
> в хэш, хэш ищется на совпадение в массиве,
Прикол в том что обычно не "ищется" а "быстро лукапается по вычисленному смещению". За счет чего и наступает профит.
> возвращается сопряжённое с хэшем значение (ссылка на объект).
Жабист такой жабист, мыслит какими-то тупыми ява-категориями, понимая как это работает едва ли наполовину. Вот что с людьми переросточные рантаймы делают - мозг атрофируют :).
> В FreeBSD /etc/login.conf устанавливает функцию SHA-512 для пользовательских паролей:
Утверждается что /etc/login.conf - это хэш-таблица? А с фига ли?
> Если интересно, можно глянуть на хэши таких паролей в vipw.
И что это даст? :)
>> Чексуммирование — частный случай применения хэширования! Хэш на основе CRC32 в ZFS
>> не используется, но используется похожий на него алгоритм "fletcher".
> Только к хэш-таблицам все это ну вообще совсем не относится. Ни флетчер,
> ни sha из чексуммирования данных. Вот тут то вы и зафэйлили,
> бакланы.А что, кто-то утверждал что CRC32, fletcher, SHA-256 в ZFS используется в хэш-таблицах? Повнимательнее надо быть.
> Пардон, в хэш-таблице есть ключи и значения. Ключи не обязательно имена или
> их хэши. А значения не обязательно объекты.Это несущественно.
>> в хэш, хэш ищется на совпадение в массиве,
> Прикол в том что обычно не "ищется" а "быстро лукапается по вычисленному
> смещению". За счет чего и наступает профит.Ну да. Сортировка (либо индексация) ключей и есть механизм, ускоряющий поиск (lookup), в противном случае придётся перебирать все элементы ключей-хэшей в таблице, чтобы найти пару ключ-значение, соответствующие искомому.
>> возвращается сопряжённое с хэшем значение (ссылка на объект).
>> В FreeBSD /etc/login.conf устанавливает функцию SHA-512 для пользовательских паролей:
> Утверждается что /etc/login.conf - это хэш-таблица?Буквы не понимаешь? /etc/login.conf задаёт алгоритм хэширования паролей для логинов в системе.
> А с фига ли?
Не фантазируй.
>> Если интересно, можно глянуть на хэши таких паролей в vipw.
> И что это даст? :)Увидишь, что представляют собой хэши относительно простых паролей. Может быть представишь, как по ним восстановить исходные пароли или найти какие-то коллизионные наборы символов вместо паролей.
> А что, кто-то утверждал что CRC32, fletcher, SHA-256 в ZFS используется в
> хэш-таблицах? Повнимательнее надо быть.Ну вот и будьте. Какой смысл с апломбом вспоминать sha-256 чексуммировние данных, когда спич о хэш-таблицах? Чтобы публично зафэйлить по максимуму? Ну ок, засчитано :)
>> их хэши. А значения не обязательно объекты.
> Это несущественно.Лучше знать общий случай чем частный имхо.
> Ну да. Сортировка (либо индексация) ключей и есть механизм, ускоряющий поиск (lookup),
> в противном случае придётся перебирать все элементы ключей-хэшей в таблице, чтобы
> найти пару ключ-значение, соответствующие искомому....и оно превратится в обычный линейный список/массив. Фикус в том что хэш-таблица свалится в подобный режим если ее коллизиями преднамеренно глушить.
> Буквы не понимаешь? /etc/login.conf задаёт алгоритм хэширования паролей для логинов в системе.
Буквы я понимаю. Вот только я не понимаю каким боком все это относится к данной новости.
>> А с фига ли?
> Не фантазируй.Ну так и скажи что это оффтопик. Заодно еще можешь нажать кнопочку "сообщить модератору" на своем сообщении для пущей оригинальности. Оффтопик - это к ним.
>>> Если интересно, можно глянуть на хэши таких паролей в vipw.
>> И что это даст? :)
> Увидишь, что представляют собой хэши относительно простых паролей.Ты меня решил хешированию поучить? Ололо.
>[оверквотинг удален]
> Controls the checksum used to verify data
> integrity. The default
> value is on, which automatically selects
> an appropriate algorithm
> (currently, fletcher4, but this may change in future
> releases). The
> value off disables integrity
> checking on user data. Disabling
> checksums is NOT a recommended practice.
> Changing this property affects only newly-written data.Дополню справедливости ради:
///---
Блоки пула дисковой памяти ZFS образуют дерево Меркле, в котором каждый блок проверяет всех своих "детей". Было доказано, что дерево Меркле обеспечивает криптографически стойкую аутентификацию как для каждого компонента дерева, так и для всего дерева целиком. ZFS использует 256-битную контрольную сумму (алгоритм SHA-256) для каждого блока (метаданных) и проддерживает алгоритмы вычисления контрольных сумм для пользовательских данных начиная с простого и быстрого алгоритма fletcher2 (используемого по умолчанию) до медленного, но безопасного SHA-256. При использовании для пользовательских данных криптографически стойкого хеша, такого как SHA-256, контрольная сумма убер-блока является постоянно обновляющимся крипто-хэшем для всех данных в пуле.
---///
> Поздравлямс сусю.Разработчики суси уже надоели. Всё время совершают какие-то ошибки. То ли дело разработчики убунты - никогда их не совершают! Ещё ни разу не было новости о том, что разработчики ядра из Canonical объявили свою разработку готовой к использованию, а через неделю появляется новость о критичном баге в нём!
Толсто!
>разработчики ядра из CanonicalТаких не существует в природе!
>>разработчики ядра из Canonical
>Таких не существует в природе!https://www.opennet.ru/opennews/art.shtml?num=35240
commit 2000afe4fb86c374650371f41eb287746790d9ff
Author: Herton Ronaldo Krzesinski <herton.krzesinski@canonical.com>
Date: Mon Aug 27 20:56:52 2012 -0300floppy: do put_disk on current dr if blk_init_queue fails
commit 238ab78469c6ab7845b43d5061cd3c92331b2452 upstream.>Толсто!
а с этим согласен.
http://www.kernel.org/pub/linux/kernel/v3.0/ChangeLog-3.6.6
>floppy: do put_disk on current dr if blk_init_queue failsПризнаю, таки существуют:))
Кому же, как не им проблемы с флопорём устранять :))
ребят то что не готово к продакшену досить даже не пытаются...
> ребят то что не готово к продакшену досить даже не пытаются...А в коментах в бложике упоминается что в OpenBSD (!!) с использованием похожей тактики успешно задосилась файловая система используемая по умолчанию. Там граждане развлекаются с попытками подгадить кэшу имен, чтоли. Ща мы узнаем много нового :)
ОО.. и где местные аналитики которые кричали все хорошо?
Ооо, btrfs-у выпала честь от более-менее оригинально мыслящего перца потыкать в него палочкой и обнаружить неординарные возможности.Заметьте, все остальные просто не попали под его внимание. Это не значит что там всенепременно нет проблем. Это значит что их пока никто палочкой не тыкал.
атаки на хэши давно известны, их часто используют (вспоминаем, например, недавние атаки на питоны и некоторые веб сервера). Так что сам факт хэширования по crc32 кричит всякой школоте и просто скучающим людям - поимей меня!> Заметьте, все остальные просто не попали под его внимание. Это не значит что там всенепременно нет проблем.
в остальных фс обычно используют менее тривиальное хэширование и деревья, саксес подобного DoSа будет ниже или вообще невозможен.
> давно известны,...
> недавние атакиВзаимоисключающие параграфы детектед :)
> crc32 кричитОн, конечно, кричит, но в хеш-таблице ФС это не сильно очевидно. Это надо развитую фантазию иметь :)
> в остальных фс обычно используют менее тривиальное хэширование
В случае хэш-таблиц никто в общем случае за сложностью генерации коллизионных хэшей не гоняется. Просто потому что как-то так традиционно считается что там криптостойкость не требуется. Вообще, для хэш-таблиц коллизия является штатным сценарием и обрабатывается. Оказалось что в некоторых случаях это может преподнести сюрприз, если некто постарается этот сценарий злонамеренно провоцировать :)
> и деревья,
Радуют меня такие индивиды - мешают в кучу все подряд. Указанное поведение - проблема именно хэш-таблиц. При чем тут деревья вообще? Это иные структуры с иными свойствами. Потенциально деревья кстати не лучше хэш-таблиц. Для дерева O(log(N)) а для таблиц O(1). Вот только как оказалось, можно спровоцировать ситуацию когда O(1) скорее станет похоже на O(N) :)
> Радуют меня такие индивиды - мешают в кучу все подряд. Указанное поведение
> - проблема именно хэш-таблиц. При чем тут деревья вообще? Это иные
> структуры с иными свойствами. Потенциально деревья кстати не лучше хэш-таблиц. Для
> дерева O(log(N)) а для таблиц O(1). Вот только как оказалось, можно
> спровоцировать ситуацию когда O(1) скорее станет похоже на O(N) :)для хэш таблиц никогда не бывает O(1), именно из-за колизий. Не позорьтесь.
И вопрос был не о O(N), там явно что-то другое сыграло :-)
> для хэш таблиц никогда не бывает O(1), именно из-за колизий. Не позорьтесь.Вообще-то нормальным сценарием эксплуатации хэш-таблицы является случай когда коллизий нет или мало. Поэтому при нормальном юзеже получается именно O(1), за что их и любят, собственно. Если коллизий слишком много, значит дуболом который юзал хэш-таблицу выбрал слишком которкий хэш для используемого размера таблицы. Какгбэ это в общем случае считается FAIL-ом в использовании данной технологии :)
> И вопрос был не о O(N), там явно что-то другое сыграло :-)В конкретно этом случае возмжно алгоритм вообще локапнулся где-то. Ибо 220 минут - как-то шибко уж дофига.
Эксперт 294 уровня как всегда газифицировал лужу, побыв для части сведений кэпом, а в остальной облажавшись. Эти вещи на втором курсе дают, есличо. И распределение (равномерность) значений хэш-функции учат смотреть, так что "похожесть на O(N)" для не забивавших не "как оказалось", а давно известное понятие. И что такое контрольные суммы, и что CRC предназначена для поиска и исправления ошибок в канале связи (а не для хеширования), тоже учат.И да, деревья тоже дают. Ты мог бы уже включить моск и подумать, почему проектировщики файловых систем обычно выбирают деревья, а не хэши.
> И что такое контрольные суммы, и что CRC предназначена для
> поиска и исправления ошибок в канале связи (а не для хеширования), тоже учат.Много апломба и мало по делу. На втором курсе обычно учат тому что нужна "какая-нибудь" хэш-функция. Про криптостойкость и прочая - ни звука. И почти все существующие реализации рассматривают коллизии как некую норму жизни. Ориентируясь на скорость в среднем, а не worst case (о чем обычно честно предупреждают). CRC32, очевидно, является хэш-функцией, сжимая все множество входных значений до 32 битов (или сколько там у кого). Ниоткуда не следует что ее нельзя юзать как функцию хэш-таблицы.
> И да, деревья тоже дают. Ты мог бы уже включить моск и
> подумать, почему проектировщики файловых систем обычно выбирают деревья, а не хэши.Деревьев в сабже хоть отбавляй. Хотя если вы хотели показать что не смотрели на дизайн сабжа - у вас это получилось.
> Ориентируясь на скорость в среднем, а не worst case (о чем
> обычно честно предупреждают). CRC32, очевидно, является хэш-функцией, сжимая все множество
> входных значений до 32 битов (или сколько там у кого).ага, а костыли — это такие ноги, только альтернативные и экономичные. но марафоны на костылях почему-то не бегают.
вообще-то в *нормальном* учебном заведении когда говорят про хэш-таблицы, рассказывают и про uniform distribution, и про avalanche, и — в том числе — почему люди, использующие crc32 в качестве хэш-функции для хэш-таблиц — форменные идиоты.
> Ниоткуда не следует что ее нельзя юзать как функцию хэш-таблицы.
следует, причём напрямую: из изучения её свойств.
не надо больше про хэши в этом контексте, ок? а то позоришься не хуже изи.
Никто не говорил, что все идеально. Уверен, подобную "фишку" можно было бы со всеми существующими ФС сотворить, и не одна не была бы идеальной.
> со всеми существующими ФС сотворить,Насчет всех - это смотреть надо. Зависит от юзаемых алгоритмов.
Потенциально же такая проблема с теми или иными последствиями может быть вообще везде где есть хэш-таблицы. Где-то это не проблема. А где-то может позволить кому-то что-то основателььно тормознуть.
> со всеми существующими ФС сотворить,Для OpenBSD что-то похожее нашли. Там же в бложике в коментах немало интересного встречается.
> ОО.. и где местные аналитики которые кричали все хорошо?Это вы еще просто не видели перцев с IXBT которые совершенно случайно нашли видеофайл который можно нарезать на CD, но потом тотально не получается его оттуда прочитать. Хотя носитель при этом абсолютно исправен.
Оказывается, после трансформации алгоритмами коррекции ошибок данные файла превратились в нечто, совпадающее с служебной сущностью (IIRC, синхрометкой). Ну а приводы налетев на такое западло совершенно не понимали как это читать дальше и отдавали ошибку чтения :)
>> ОО.. и где местные аналитики которые кричали все хорошо?
> Это вы еще просто не видели перцев с IXBT которые совершенно случайно
> нашли видеофайл который можно нарезать на CD, но потом тотально не
> получается его оттуда прочитать. Хотя носитель при этом абсолютно исправен.
> Оказывается, после трансформации алгоритмами коррекции ошибок данные файла превратились
> в нечто, совпадающее с служебной сущностью (IIRC, синхрометкой). Ну а приводы
> налетев на такое западло совершенно не понимали как это читать дальше
> и отдавали ошибку чтения :)а ссыли нет? интересно было бы самому нарезать...
> а ссыли нет? интересно было бы самому нарезать...Вот ссыль на описалово. Вместе с объяснением феномена - http://www.ixbt.com/optical/magia-chisel.shtml
местные аналитики забывают что подобная атака была и на питон и на пхп и на много еще чего находящегося в продакшене.
Это можно сделать не только на Btrfs, в том плане что поедание ресурсов возможно не только в данной ФС и не только в ФС
> Это можно сделать не только на Btrfs, в том плане что поедание
> ресурсов возможно не только в данной ФС и не только в ФСЭто можно сделать много где и это не самый ожидаемый вектор атаки для программистов.
В общем то это довольно фундаментальная проблема использующая слабое место хэш-таблиц: при коллизиях хэш-таблица может быть медленной. Если коллизий много - дело дрянь. Атака состоит в потугах сделать так чтобы коллизий стало много. Для криптостойких функций это невозможно, но они слишком медленны для скоростных применений (лукап в структуре ключ-значение в памяти). А вот упрощенные хэши дают достаточно маневра для попыток их проабузить. CRC32 в этом плане очень плох, т.к. алгоритмы подгона CRC32 под ответ ни для кого не секрет.
На качественных файловых системах, xfs(btree вместо hash), reiserfs(на этапе проектировки предусмотрена устойчивость к коллизиям) такого сделать не получится.
> предусмотрена устойчивость к коллизиям)А нельзя ли пруф на то что они специально дизайнились с учетом этого фактора? А то проблема просто есть у целого класса алгоритмов - хэш функций. И задумались о аккуратном подгоне входных данных для их торможения относительно недавно. Явно позже чем указанные ФС проектировались. Что вызывает некие нехорошие подозрения на ваш счет.
какая-то у вас каша в голове.. скорость вычисления хэша - вещь константная. И то что колизии бывают - нормальный разработчик как бы в курсе.. (достаточно подумать 255 байт ужимают до 32 - тут уж не бывает без вариантов). Другой вопрос что при реализации кто-то заложился что таких колизий не много - но это уже проблемы реализации :-) Которую тут хвалили..
> И то что колизии бывают - нормальный разработчик как бы в курсе..Просто намеренный гасеж коллизиями вообще-то не является штатным видом эксплуатации ФС. И есть большие сомнения что остальные существующие ФС кто-то хоть как-то изучал под таким углом вообще. Хотя если хочется поисходить на г-но - это круто, конечно, но тогда для справедливости придется полить им и кучу иного софта где эту проблему выловили и зачинили.
> (достаточно подумать 255 байт ужимают до 32
Вообще-то CRC32 - это 4 байта. Или 32 бита. Критиканить других с такими познаниями о криптографии - ну да, это круто.
> кто-то заложился что таких колизий не много
Это совершенно стандартное допущение для реализации хэш-таблиц. Ибо в абсолютно вырожденном случае хэш-таблица вырождается например в линейный список ("ничего кроме коллизий нет"). Нормально? :)
>> И то что колизии бывают - нормальный разработчик как бы в курсе..
> Просто намеренный гасеж коллизиями вообще-то не является штатным видом эксплуатации ФС.
> И есть большие сомнения что остальные существующие ФС кто-то хоть как-то
> изучал под таким углом вообще. Хотя если хочется поисходить на г-но
> - это круто, конечно, но тогда для справедливости придется полить им
> и кучу иного софта где эту проблему выловили и зачинили.
>> (достаточно подумать 255 байт ужимают до 32
> Вообще-то CRC32 - это 4 байта. Или 32 бита. Критиканить других с
> такими познаниями о криптографии - ну да, это круто.crc32 не является криптохэшем :-) видимо что бы это узнать нужны дикие познания?
а что брякнул до 32 - это было просто пояснение без привязки к конкретному алгоритму - так будет лучше?
>> кто-то заложился что таких колизий не много
> Это совершенно стандартное допущение для реализации хэш-таблиц. Ибо в абсолютно вырожденном
> случае хэш-таблица вырождается например в линейный список ("ничего кроме коллизий нет").
> Нормально? :)формулировка нормальная - только с тем как используются хэш при построении файловых систем - вы не знакомы. Знакомы только с хэшированными списками - но есть и другие варианты - с другими болячками.
В случае ext3/4 - к примеру есть дерево хэшей в узлах которого расположены ссылки на имена имеющие одинаковых хэш. В этом случае поиск имени сначала ведется по частичному или полному хэшу от имени - дальше производится модификации блоков которые хранят информацию о именах с одинаковым результатом хэш функции. Вот тут то и приплыли - если колизий будет слишком много - затраты на модификацию этих блоков - могут быть очень и очень большими. (split, merge blocks - и создание дополнительных листьев в дерево). Сдается мне что в случае btrfs идет атака как раз на этот кусок - а улучшением хэш функции (как и увеличением размера хэша) - можно только усложнить подбор имен дающих колизию.
Нормально ? :-)
> crc32 не является криптохэшем :-) видимо что бы это узнать нужны дикие познания?Внезапно, хэш-таблицы сами по себе вообще не требуют в общем случае использования именно криптостойких функций. И для них совергшенно нормально если будет некий процент коллизий. Покуда он небольшой - это мало замедляет работу таблицы. Это считается штатным развитием событий и как правило явно обрабатывается, так что столкнувшиеся записи тем не менее сохраняются и доступны. А вот то что специально нагенеренные оптом коллизии в хэш-таблице можно абузануть для сильного торможения работы чего-либо с злонамеренной целью - намного менее очевидный факт. Требующий не программерского мышления а хакерского. Не "как закрепить рельсу на полотне", а "как сделать так чтобы рельсу не унес первый встречный козел, голыми руками, за минуту". Редкий программер мыслит именно в таком контексте. Где-то это и так прокатывает. А где-то случаются различные приколы.
> к конкретному алгоритму - так будет лучше?
Отмазался, типа? :)
> формулировка нормальная - только с тем как используются хэш при построении файловых
> систем - вы не знакомы.Нифига себе апломба. А откуда такой масштабный вывод следует? Из вашего немеряного апломба? Других предпосылок не вижу.
> Знакомы только с хэшированными списками - но есть и другие варианты - с другими болячками.
Кто вам сказал что я знаком только с хэш-таблицами? Вы сами придумали?
> будет слишком много - затраты на модификацию этих блоков - могут
> быть очень и очень большими. (split, merge blocks - и созданиеНу спасиб, Капитан. Что бы я без вас делал? А еще можно b-деревья юзать, например. Нет хэш-функции - нет проблем с ней. Зато других проблем есть.
> (как и увеличением размера хэша) - можно только усложнить подбор имен дающих колизию.
Ну так если подобрать коллизию не получится - стало быть и проблема отсутствует. Что мне там не нравится - так это 220 минут взвиса. Похоже на то что алгоритм совсем где-то взвис. Т.е. там видимо еще и просто баг где-то порылся.
reiserfs использует хеш функцию r5, для которой не известен алгоритм создания коллизий.
И уж точно (даже если коллизия возникнет) это ограничится проблемой производительности, а не будет отказ в создании файла.
> И уж точно (даже если коллизия возникнет)В общем то коллизии находят даже для криптостойких функций иногда, а для хэш-таблиц нет требования криптостойкости в общем случае. Хотя как оказалось, такая поблажка может икаться совершенно неожиданным образом.
> а не будет отказ в создании файла.
Так в btrfs нет отказов при создания файла. Правда есть какое-то непотребное время удаления.
>Так в btrfs нет отказов при создания файла.По ссылке не ходил статью не читал? brtfs выдал ошибку на шестьдесят втором файле с коллизией.
> По ссылке не ходил статью не читал?Не только читал, но и в курсе как хэш таблицы делают.
Понимаете ли, для хэш-таблиц сроду не использовали криптографически стойкие функции. Потому что они медленные. Коллизии для хэш-таблиц - нормальное явление. Это как правило не просто допустимо, но и явно обрабатывается. Так что путем того или иного костылинга таблица в результате помнит обе конфликтующие записи и может достать и ту и другую. В общем случае это не создает никаких проблем. Главное чтобы процент коллизий был небольшой. Большой процент коллизий говорит о том что разрядность хэша мала относительно числа элементов и таблица работает неэффективно (приходится смотреть по нескольку записей с одним и тем же хэшом чтобы понять какая из них нужна). Но это не является чем-то совершенно недопустимым.
Но как оказалось, при должной изобретательности можно глушить коллизиями прицельно. Спровоцировав очень много коллизий. В этом случае хэш-таблица завалится в дуpной режим, когда она вместо быстрого лукапа по индексу начинает разгрeбать немеряную цепочку коллизий. Большинство алгоритмов хэш-таблиц вообще никогда не дизайнилось с прицелом на учет такой подставы. И на практике такие атаки появились лишь сравнительно недавно.
> Не только читал, но и в курсе как хэш таблицы делают.Почитай ещё раз. То что ты знаешь, не значит что авторы btrfs знают. По факту, в директории btrfs не возможно создать больше 61 файла с одним хешем.
>> По ссылке не ходил статью не читал?
> Не только читал, но и в курсе как хэш таблицы делают.
> Но как оказалось, при должной изобретательности можно глушить коллизиями прицельно. Спровоцировав
> очень много коллизий. В этом случае хэш-таблица завалится в дуpной режим,
> когда она вместо быстрого лукапа по индексу начинает разгрeбать немеряную цепочку
> коллизий.остальной бред скипнут. В случае применения в FS - там все немного не так как вы представляете.
Собственно очень часто появляется вопрос - который уже тут задавали.
"как дописать в середину файла - не переписывая каждый раз его хвост"Создаем большой каталог (hint вспоминаем почему гугл сделал патч на max dir size в ext4) - после чего выбираем новые имена файлов так что бы модификация была где-то в начале - и смотрим на это развлечение..
А учитывая что в btrfs - был заявлен b-tree+ - эта дура может затребовать еще и постоянную балансировку при удалении / создании элемента.. Ну и приплыли...ps. знакомство с хэшами это хорошо - это бонус. Знакомство с предметной областью - все же более привествуется...
> Собственно очень часто появляется вопрос - который уже тут задавали.
> "как дописать в середину файла - не переписывая каждый раз его хвост"Во первых, простите, а что есть "дописать" в середину файла? Технически я понимаю что CoW это мог бы и это изобразить как 2 пальца об асфальт, но в posix вообще нет вызовов позволяющих ДОписать. Только ПЕРЕЗАПИСАТЬ. Поверх того что было (cow опять же сделает выносок, но это второй вопрос).
Во вторых - не особо понятно как дозапись в файл коррелирует с коллизиями вызваными именами файлов.
> Создаем большой каталог (hint вспоминаем почему гугл сделал патч на max dir
> size в ext4) - после чего выбираем новые имена файлов так
> что бы модификация была где-то в начале - и смотрим на это развлечение..Я что-то не понял: а где тут про дозапись в середину файла? :)
А как генерить имена файлов чтобы там коллизии были - я и сам догадаюсь, спасибо. Тем более что у гражданина который это нашел даже скрипт для иллюстрации есть.> ps. знакомство с хэшами это хорошо - это бонус. Знакомство с предметной
> областью - все же более привествуется...С хэшами и деревьями я позгнакомился фиг знает когда. И вообще, наезды смотрятся не сильно уместно, особенно с учетом того что вы сами временами какой-то бред с удовольствтем задвигаете.
Мисье - вы уверены что к директориям примимо слово posix?
Если уверены - то мне очень сложно вам будет объяснить что там не так.
> Мисье - вы уверены что к директориям примимо слово posix?Пардон, вы сами про ФАЙЛЫ завели речь:
> "как дописать в середину файла - не переписывая каждый раз его хвост"
> Если уверены - то мне очень сложно вам будет объяснить что там не так.На самом деле я просто не понял ваш маневр - сначала задвинули про файлы и потом перешли на директории, тихонько спустив тему дозаписи в середину файла на тормозах. Получился какой-то бред, имхо.
у ext4 тоже специально предусмотрена обработка колизий в dx tree..
> у ext4 тоже специально предусмотрена обработка колизий в dx tree..Проблема не в том что обработки нет. А в том что если коллизий будет много, алгоритм очень существенно провалится по скорости относительно "среднего по больнице" поведения. Что позволяет вредителю воткнуть весьма конкретный лом в чей-то вентилятор если коллизии можно более-менее просто посчитать и организовать их появление в системе. А вот дальще система займется их обработкой. В хучшем случае хэш-таблица может деграднуть до чего-то типа линейного списка, со всеми вытекающмим, как то не O(1) а O(N), что уже совсем иной коленкор.
>> у ext4 тоже специально предусмотрена обработка колизий в dx tree..
> Проблема не в том что обработки нет. А в том что если
> коллизий будет много, алгоритм очень существенно провалится по скорости относительно "среднего
> по больнице" поведения.see up. все не так просто.
> see up. все не так просто.Да, оказывается не все так просто. В коментах к бложику продолжается изучение где еще можно так поприкалываться. Под внимание попала дефолтная ФС OpenBSD, которую как я понял успешно заDOSили :)
Не понятно чего так носятся с этой btrfs, преимуществ никаких, сколько тестов уже было опубликовано, сколько раз сам ставил на корень и убеждался. В ЧЕМ, ПРИ КАКИХ УСЛОВИЯХ проявляется ее мифическая производительность???
Её преимущества не в производительности.
> преимуществ никаких,Возятся с ней потому что вот в этом вы не правы.
Во первых, покажите хоть какую-то еще ФС в лине которая сможет делая полное журналирование писать со скоростью близкой к скорости носителя. Журналинг только метаданных не предлагать.
Во вторых, покажите ФС которые бы менее горбато и более шустро оперировали в лине со снапшотами. Кой-как конечно и на других ФС закостылить можно. Но - именно кой-как.
В третьих, там не самый плохой менеджмент томов и ФС весьма гибка в размещении метаданных. Не то чтобы это нельзя сделать иначе, но делание этого в ФС дает некие плюсы. ФС лучше остальных знает что и где лежит. Поэтому если нам надо вынуть диск из пула, фс может адресно удвинуть с именно этого диска все ценное в другие места. После чего его можно изъять. В менее продуманных топологиях это или невозможно совсем или долго и сложно.
Показываю для упоротых: http://zfsonlinux.org/
> Показываю для упоротых: http://zfsonlinux.org/Она не работает.
>> Показываю для упоротых: http://zfsonlinux.org/
> Она не работает.Правда что ли? Вот тут запустили: http://www.linux.org.ru/gallery/screenshots/8556285
Видимо, Gentoo — это какой-то инопланетянский Linux, не то что человечная Ubuntu. :))
> Правда что ли? Вот тут запустили: http://www.linux.org.ru/gallery/screenshots/8556285Запорожец с горы Арарат.
Хорошо пошёл.
Ubuntu переводится как "я не могу настроить Debian"
> Ubuntu переводится как "я не могу настроить Debian"Казалось бы, при чем тут вообще Лужков^W убунту. Впрочем, черный пиар - это тоже пиар.
> Она не работает.Не, ну почему. Как-то работает. Вопрос только в том КАК.
1) Это не в майнлайне. И потому отсутствует по дефолту в дистрах и их инсталляционных медиях. Что намекает на веселые проблемы в случае аварии и загрузки для восстановления с какого-то побочного носителя.
2) И вообще, если некто хотел булочек с изюмом, довольно странно дать ему булочку и пакет изюма, намекая что он должен заковырять его туда сам.
3) Технически у ZFS своих дебилизмов - есть. Странный кэш. Странные дисковые структуры. Ну и работает оно странно. Btrfs надизайнили в том числе и с учетом известных проблем zfs. Пусть любители ZFS изобразят конверсию ext4 -> btrfs путем оформления ext4 как этакого снапшота :). Хочу увидеть такую магию с их стороны.
4) С такой лицензией это никто не будет сильно допиливать. Потому что 1) нереально и стало быть в лине оно пролетает. Чужеродный для системы элемент.
> Пусть любители ZFS изобразят конверсию ext4 -> btrfs путем оформления ext4 как этакого снапшота :). Хочу увидеть такую магию с их стороны.Зачем это им нужно?! Магия поддержки любых ФС в ZVOL со всеми плюшками ZFS, как то: отключаемый чексумминг, дедупликатинг, компрессинг, снапшотинг — реализована, что ещё нужно-то? Может вам ещё соломки подстелить под Ext4 и Btrfs, чтобы не было так больно падать, а? Так пожалуйста. :)) Фактически, ZFS представляет собой комбинацию MD+LVM для классических файловых систем плюс расширенные возможности для собственных файловых датасетов.
> С такой лицензией это никто не будет сильно допиливать. Потому что 1) нереально и стало быть в лине оно пролетает. Чужеродный для системы элемент.
С какой лицензией и что не будет сильно допиливать? Напомню: ZFS давно уже в продакшене (во FreeBSD с 2008 года) и получает новые возможности, а Btrfs только сейчас SUSE объявила готовой, причём в ней нет ни фига, кроме зеркалирования.
> С какой лицензией и что не будет сильно допиливать? Напомню: ZFS давно
> уже в продакшене (во FreeBSD с 2008 года) и получает новыеИзя, в 2008 она была experimental.
Плюшки пилятся в illumos + zfsonlinux.Кстати, на linux поверх zfs пускают lustre.
> Зачем это им нужно?! Магия поддержки любых ФС в ZVOL со всемиЗатем. Чтобы эту "магию" попробовать, надо либо с чистого листа начинать, либо переносить готовое. Долго, нудно, опасно. С BTRFS проще - завернул имеющуюся ext4 в BTRFS, начал юзать. Что-то в производительности или чём еще не устроило - откатился к моменту завертывания.
> Напомню: ZFS давно уже в продакшене (во FreeBSD с 2008 года)С 2009 года — http://svnweb.freebsd.org/base?view=revision&revision=197221
FreeBSD в продакшене))) Изя как всегда отжигает)))
> FreeBSD в продакшене))) Изя как всегда отжигает)))У него жгучий продакшн с трехдисковым пулом выдающим 18Мб/сек. А у меня ноутбучный винч, один, без всяких пулов меньше 45 на больших файлах в принципе не загибается :)
>> FreeBSD в продакшене))) Изя как всегда отжигает)))
> А у меня ноутбучный винч, один, без всяких пулов меньше 45 на больших файлах в принципе не загибается :)Твой винт поддерживает хотя бы дедупликацию блоков ФС, не говоря уж о сквозной целостности данных и метаданных? Что нет? Тогда включи хотя бы журналирование _данных_и_метаданных_ в своей Ext4 (или какая у тебя там высокопроизводительная ФС?) и _СРАВНИ_ПОХОЖИЕ_РЕШЕНИЯ_, а не выставляй себя идиотом.
> Твой винт поддерживает хотя бы дедупликацию блоков ФСМммм... трудновато найти мазохиста, готового платить за дедуп 4+ кратным падением производительности.
> не говоря уж о сквозной целостности данных и метаданных?
Ты не поверишь - твоя система также не имеет никакой "сквозной целостности". Сбой памяти/контроллера памяти/CPU угробит твою FS еще до расчета CRC, и вся твоя целостность пойдёт лесом.
> Тогда включи хотя бы журналирование _данных_и_метаданных_ в своей Ext4
Лично мне нужно только журналирование метаданных. Включать журнал данных имеет смысл только там, где действительно нужна целостность рабочего набора. В общем же случае рабочий набор при сбоях перестраивается из долгосрочного.
>> Твой винт поддерживает хотя бы дедупликацию блоков ФС
> Мммм... трудновато найти мазохиста, готового платить за дедуп 4+ кратным падением производительности.А чего же тогда лезет в охотный ряд и сравнивает в принципе известные факты: "дедупликация тормозит", "обеспечение журналирования и данных и метаданных тормозит". Капитан Очевидность для тех кто в курсе, а для тех, кто не в курсе, герой-срывающий-покровы-с-гадкой-и-тормозной-технологии?
>> не говоря уж о сквозной целостности данных и метаданных?
> Ты не поверишь - твоя система также не имеет никакой "сквозной целостности".
> Сбой памяти/контроллера памяти/CPU угробит твою FS еще до расчета CRC, и
> вся твоя целостность пойдёт лесом.При сбое любого компонента на пути данных ZFS пул немедленно завершает свою работу. Это сделано намеренно, чтобы не разрушить пул окончательно.
>> Тогда включи хотя бы журналирование _данных_и_метаданных_ в своей Ext4
> Лично мне нужно только журналирование метаданных. Включать журнал данных имеет смысл только
> там, где действительно нужна целостность рабочего набора. В общем же случае
> рабочий набор при сбоях перестраивается из долгосрочного.Ну а в ZFS свойство checksum для данных можно перевести в состояние "off" и избавиться от проверки данных на лету. Что случится в этом случае с быстродействием? Быстродействие вырастет незначительно, так как эта вещь хорошо оптимизирована.
А что с механизмом журналирования данных в Ext3/4? Тут производительность I/O гуляет в весьма широких пределах в зависимости от того, включен он или выключен, так как эта ФС не проектировалась как CoW-only. Но если вы хотите сравнивать сравнимые вещи, то, пожалуйста, задействуйте этот механизм в своей любимой ФС и тогда сравнивайте с ZFS. А то можно сравнить сжатие потока нулей из /dev/zero с потоком MP4 и внезапно удивиться, что нули-то жмутся сильнее и быстрее!
> При сбое любого компонента на пути данных ZFS пул немедленно завершает свою
> работу. Это сделано намеренно, чтобы не разрушить пул окончательно.Блджад. Вот сразу видно жабиста. "Zero knowledge of underlying operations". Не узнает твой "пул" до момента расчёта CRC вообще о том, что данные "не те". Они ему придут уже искаженными. А то и еще хуже - посчитает гнилую CRC из нормальных данных, и благополучно запишет на диск.
А при чтении сильно удивится :) когда увидит порушенную "по CRC" цепочку вроде бы нормально записавшихся данных. Причем начнет "откатываться"/"восстанавливаться", что еще хуже, чем если бы просто прочитал "как есть".
> Ну а в ZFS свойство checksum для данных можно перевести в состояние
> "off" и избавиться от проверки данных на лету. Что случится в
> этом случае с быстродействием? Быстродействие вырастет незначительно, так как эта вещь
> хорошо оптимизирована.Спасибо, кэп.
> Блджад. Вот сразу видно жабиста. "Zero knowledge of underlying operations". Не узнает
> твой "пул" до момента расчёта CRC вообще о том, что данные "не те". Они ему придут
> уже искаженными. А то и еще хуже - посчитает гнилую CRC из нормальных данных,
> и благополучно запишет на диск.Ну что поделать. Не понимают жабисты как работают компьютеры. Это позволяет им красиво зафэйлить, картинно сев в лужу на элементарщине. Бывает.
> А при чтении сильно удивится :) когда увидит порушенную "по CRC" цепочку
> вроде бы нормально записавшихся данных. Причем начнет "откатываться"/"восстанавливаться",
> что еще хуже, чем если бы просто прочитал "как есть".Да вон на лисяре гражданин выкусил - элементарнейший бэдсектор, а солнце пришлось закатывать вручную. Потому что fsck нету и не планируется. Так что если механика драйвера ФС сбойнет - вообще все, финиш. Хэксэдитором колупай это монстрило. Особенно прикольно на многодисковом пуле с каким-нибудь сжатием и райдом будет :). Сани вообще любят маркетинговый буллшит :)
> Да вон на лисяре гражданин выкусил - элементарнейший бэдсектор, а солнце пришлось
> закатывать вручную. Потому что fsck нету и не планируется.Не поэтому. scrub бессилен на FAULTED-пуле. Но недавно появилась волшебная команда "zpool import -F" — дарю, пользуйся на здоровье и больше не неси чепухи про fsck.
> Зачем это им нужно?! Магия поддержки любых ФС в ZVOL со всеми плюшками ZFS,Просто прикольная иллюстрация гибкости в размещении метаданных. Оно даже иную ФС может оформить как свой снпашот. Практическая польза? Ну, если не понравилось, можно откатиться на этот снапшот. Получится старая ФС в виде "как было". Весьма забавно.
> как то: отключаемый чексумминг, дедупликатинг, компрессинг, снапшотинг — реализована,
Дык в btrfs тоже все это есть. Ну может кроме дедупликатинга разве что. А еще там нормальные экстенты, буфера используются по человечески, а не как у саней, лицензия нормальная так что это в майнлайне будет, etc.
> Фактически, ZFS представляет собой комбинацию MD+LVM
И файловой системы. Только в лине все это как собаке пятая нога в таком исполнении. Нафиг надо btrfs я еще понимаю. Нафиг надо zfs в таком виде как оно есть - не особо. Это бсдшники жрут что попало, т.к. все-равно больше нечего, ресурсов нет, блаблабла. Но у линуксоидов такая проблема не стоит и им не обязательно жрать первый попавшийся кактус, игноря все колючки.
> возможности, а Btrfs только сейчас SUSE объявила готовой, причём в ней нет ни фига,
> кроме зеркалирования.Чего в ней нет то? Разве что чего-то RAID5-образного да дедупа? Остальное вроде на месте уже.
>> Показываю для упоротых: http://zfsonlinux.org/
> Она не работает.машинка из TOP10 (что-то в первой пятерке - секвоя) говорит что работает.. можно посмотреть в презентациях LUG2012, LAD2012. Кому верить?
> машинка из TOP10 (что-то в первой пятерке - секвоя) говорит что работает..
> можно посмотреть в презентациях LUG2012, LAD2012. Кому верить?Да и пусть себе работает. А топ10 - это потому что "1 из 500" звучит гораздо менее понтово, да? :)
>> машинка из TOP10 (что-то в первой пятерке - секвоя) говорит что работает..
>> можно посмотреть в презентациях LUG2012, LAD2012. Кому верить?
> Да и пусть себе работает. А топ10 - это потому что "1
> из 500" звучит гораздо менее понтово, да? :)Вы мне покажете еще 10-15P стораджей под btrfs? а top10 намекает что размер дискового массива - там не из маленьких..
> Вы мне покажете еще 10-15P стораджей под btrfs? а top10 намекает что
> размер дискового массива - там не из маленьких..Один какой-то мегауникальный пепелац в лаборатории - это круто и замечательно. Только вот при чем тут продакшн?
А дополнительно для упоротых там подарят мне 32 гб озу если я скачаю сорца zfsonlinux?
Тебе ехать или шашечки? За что-то нужно чем-то платить.
да все твои уже итак знают.
ты лучше нормальным покажи кто поддержкой этой каки в ынтырпрайзе (аля сюзе) займётся?
компания упоротых айзенов?
> да все твои уже итак знают.
> ты лучше нормальным покажи кто поддержкой этой каки в ынтырпрайзе (аля сюзе)
> займётся?
> компания упоротых айзенов?LLNL.gov, Intel.com .... мало ?
> LLNL.gov, Intel.com .... мало ?Один, два, много! Хм... где-то я это слышал. А, дикари так считали, во!
> Показываю для упоротых: http://zfsonlinux.org/Спасиб, сами это кушайте.
>если нам надо вынуть диск из
> пула, фс может адресно удвинуть с именно этого диска все ценное
> в другие места. После чего его можно изъять. В менее продуманных
> топологиях это или невозможно совсем или долго и сложно.pvmove разве не тоже самое делает?
>>если нам надо вынуть диск из
>> пула, фс может адресно удвинуть с именно этого диска все ценное
>> в другие места. После чего его можно изъять. В менее продуманных
>> топологиях это или невозможно совсем или долго и сложно.
> pvmove разве не тоже самое делает?Создание снапшота в lvm2 просаживает производительность тома, который снапшотили, в 2(!) раза. Если на этом томе виртуальная машина с dns-сервисом - это, конечно, не проблема. А если там база данных? А в btrfs эта проблема решена.
>Создание снапшота в lvm2 просаживает производительность тома, который снапшотили, в 2(!) раза.эта… как его… использование zfs вообще в принципе просаживает и производительность, и ресурсоёмкость. btrfs тоже пока не особо производительностью радует.
так что это ещё тот пример.
> А если там база данных?и в самый пик нагрузки именно снэпшоты и делаются?
и ещё, как дба, не стоит полагаться на снэпшоты с субд — файлы в этот момент могут быть не в консистентном состоянии и кэши в памяти могут быть не скинуты
> эта… как его… использование zfs вообще в принципе просаживает и производительность,
> и ресурсоёмкость. btrfs тоже пока не особо производительностью радует.Тем не менее, скорость записи на оную от самого по себе факта наличия снапшота там падать не обязана. В отличие от LVM, где роялит сам факт того что снапшот есть. Ну в общем сколько ни прикручивай проволокой к жигуленку крылья, а летун из него хреновый. Самолет должен быть просто надизайнен под свою задачу. А не быть креативной переработкой автомобилей, с аргументом что дизайн дескать есть и обкатан уже.
> и в самый пик нагрузки именно снэпшоты и делаются?
Проблема не в пике нагрузки. А в том насколько после этого скорость всех операций вообще угробится. В LVM снапшотирование реализовано довольно невкусно. Конечно на безрыбье и рак - рыба, но тут то намного более вкусная сущность светит. Вы в вашем праве долбаться с снапшотами ext4 через LVM если оно вам зачем-то надо.
>Тем не менее, скорость записи на оную от самого по себе факта наличия снапшота там падать не обязана.Тем не менее скорость записи на оную падает всегда и ресурсы жрутся тоже всегда, а не только в редкие моменты снэпшотов и бэкапов, которые более-менее адекватные админы делают в наименее нагруженное время.
а если учесть упомянутую тобой бд, то сожранные фс ресурсы (а именно память) гораздо эффективнее отдать под кэш этой субд, при этом скорость работы с оной увеличится опять же всегда, при чём так, что процесс создания снепшотов будет даже и не заметен.
>> и в самый пик нагрузки именно снэпшоты и делаются?
>Проблема не в пике нагрузки.тогда не понятен плач ярославны по поводу скорости (снэпшот тормозит пока он есть, zfs тормозит всегда)
>А в том насколько после этого скорость всех операций вообще угробится.а нафига снепшоты вообще делают?
а то как в анекдоте:
- доктор, если я вот так вот подтяжки перекручиваю, то вот тут жмёт.
- ну не перекручивайте так подтяжки.
сделал снепшот, сделал бэкап (инкрементальный), убрал снэпшот.
>Вы в вашем праве долбаться с снапшотами ext4 через LVM если оно вам зачем-то надо.Вы тоже в праве тормозить всегда, а не только в моменты снепшотов.
> Тем не менее скорость записи на оную падает всегда и ресурсы жрутсяПростите, падает - это если на ext4 полный журнал врубить. А тут аналог полного журнала вообще "почти нахаляву".
> тоже всегда, а не только в редкие моменты снэпшотов и бэкапов,
Именно запись в нормальном крейсерском режиме там достаточно быстрая. Вот фрагментация потенциально сильнее, да. И нагрузки CoW-based удобнее иные чем классическим ФС. Это не баг и не фича. Просто свойство дизайна такое.
> а если учесть упомянутую тобой бд, то сожранные фс ресурсы (а именно память)
А именно памяти btrfs особо и не жрет, как ни странно. И кэш юзает системный, так что если кто захочет памяти в ущерб кэшу - это можно. В отличие от ZFS, где все это эфемерно и негарантированно.
> процесс создания снепшотов будет даже и не заметен.
Именно БД на CoW класть может быть вообше не лучшей идеей. Поэтому там есть возможность выключить оную механику. Теперь банановый^W даже для отдельных файлов вообще.
> тогда не понятен плач ярославны по поводу скорости (снэпшот тормозит пока он
> есть, zfs тормозит всегда)Да фиг с ним с ZFS, он реально тормоз. Но btrfs явно будет резвее. Часть тупняков zfs там таки устранили.
>>А в том насколько после этого скорость всех операций вообще угробится.
> а нафига снепшоты вообще делают?А снапшоты делают чтобы откатиться к ним если результат не понравился и что-то факапнулось, например.
>>Вы в вашем праве долбаться с снапшотами ext4 через LVM если оно вам зачем-то надо.
> Вы тоже в праве тормозить всегда, а не только в моменты снепшотов.Ну вот я и предпочитаю btrfs как разумный баланс между торможением и снапшотами.
Почитайте про устройство снапшотов в LVM, а потом говорите про уменьшение производительности в 2 раза.
> Почитайте про устройство снапшотов в LVM, а потом говорите про уменьшение производительности
> в 2 раза.Спасибо, я почитал. И остаюсь при своем мнении: крылья и аэродинамика задуманные сразу в дизайне - лучше чем если это получено проволокой и напильником. Так что btrfs лично мне явно пригодится и не раз.
починили
Хм, на собственном опыте при единственном снэпшоте особой просадки производительности (тем более в 2 раза) не заметил. Сильно заметно просадку после 3-4 снапшота. Тестилось достаточно дубово - копированием кучи rpm-ов, общая дельта изменений ~60% от первоначального. Ось RHEL-6. Для себя сделал вывод, использовать не более двух снапшотов с последующим архивированием и удалением.
>>>если нам надо вынуть диск из
>>> пула, фс может адресно удвинуть с именно этого диска все ценное
>>> в другие места. После чего его можно изъять. В менее продуманных
>>> топологиях это или невозможно совсем или долго и сложно.
>> pvmove разве не тоже самое делает?
> Создание снапшота в lvm2 просаживает производительность тома, который снапшотили, в 2(!)
> раза. Если на этом томе виртуальная машина с dns-сервисом - это,
> конечно, не проблема. А если там база данных? А в btrfs
> эта проблема решена.pvmove это не снапшот, это вынуть диск из пула, я же специально цитировал на что отвечаю :)
> Не понятно чего так носятся с этой btrfs, преимуществ никаких, сколько тестов
> уже было опубликовано, сколько раз сам ставил на корень и убеждался.
> В ЧЕМ, ПРИ КАКИХ УСЛОВИЯХ проявляется ее мифическая производительность???Помимо производительности, есть соображения удобства администрирования и количества поддерживаемых возможностей.
Зачем нужны возмжности, если давно уже есть LVM+ext4?
> Зачем нужны возмжности, если давно уже есть LVM+ext4?Вот вы и юзайте там снапшоты если хотите.
У бтрфс есть еще одно узкое место помимо производительности - пожирание места на диске за счет метаданных. на 10 гб данных требуется 1 гб метаданных, если правильно помню - 10% места коту под хвост в самом лучшем случае ;)
> У бтрфс есть еще одно узкое место помимо производительности - пожирание места
> на диске за счет метаданных. на 10 гб данных требуется 1
> гб метаданных, если правильно помню - 10% места коту под хвост
> в самом лучшем случае ;)Слегка ошибся. На 5ТБ данных 10ГБ метаданных. А вообще это зависит.
> на диске за счет метаданных. на 10 гб данных требуется 1 гб метаданных,Хотите прикол? Создавайте директории и в них файлы 0-го размера до упора. Однажды вы обнаружите что хотя на диске всего 0 байтов (т.к. все файлы нулевого размера), место тем не менее почему-то кончилось. Да-да, на 0 байтов полезных данных можно спровоцировать 100500Гб метаданных, сожравших вообще все место. Кстати, от типа файловой системы это вообще не зависит особо :)
> У бтрфс есть еще одно узкое место помимо производительности - пожирание места
> на диске за счет метаданных. на 10 гб данных требуется 1
> гб метаданных, если правильно помню - 10% места коту под хвост
> в самом лучшем случае ;)Внезапно, эта величина сильно зависит от среднего размера файлов. Потому что информация о том, что файл есть, и как он называется - это и есть метаданные.
crc32? ну они дали(((
> crc32? ну они дали(((Для hash table это в принципе вполне себе функция. Просто оказалось что в конкретно этом случае можно хитро изогнуться. Но этот изгибон требует хакерского мышления а не програмерского. Так умеют не все.
>> crc32? ну они дали(((
> Для hash table это в принципе вполне себе функция. Просто оказалось что
> в конкретно этом случае можно хитро изогнуться. Но этот изгибон требует
> хакерского мышления а не програмерского. Так умеют не все.Покажи-ка еще хотя бы парочку известных применений, где CRC32 использовался бы именно в качестве _хэша_ для таблиц. То, что формально математически его можно отнести к хэшам, не означает, что таким идиотизмом надо заниматься на практике.
> Покажи-ка еще хотя бы парочку известных применений, где CRC32 использовался бы именно
> в качестве _хэша_ для таблиц.Насчет CRC32 - увы, я не коллекционировал специально для вас подборку всех реализаций с ранжированием по функции хеширования. Однако недавние дыры в пыхе, питоне и чем там еще - прозрачно намекают что простые и предсказуемые функции в хэш-таблицах - вполне обычное явление.
> Для hash table это в принципе вполне себе функция.вот такие кулхацкеры и суют её в хэши, ага. сейчас я тебе скажу два словосочетания: «avalanche test» и «uniform distribution test». да, это надо вбивать в гугель вместе с буквами «crc32».
я надеюсь, ты не пишешь ничего сложнее приветмиров. или хотя бы не показываешь публике. потому что с таким уровнем компетенции… в других областях она у тебя не лучше, инфа 146%
хэш. crc32. на всякий случай отложил идею пощупать btrfs на 50 лет.
> хэш. crc32. на всякий случай отложил идею пощупать btrfs на 50 лет.Лучше на 100. А то вдруг каким-то чудом доживешь еще? Как же тогда твой статус некрофила?