Мысли вслух. Предостережение от наступления на грабли.

Работает в разы быстрее, чем просто рекурсивное удаление каталога. Она сначала рекурсивно удаляет все файлы (сохраняя всю структуру каталогов - остается пустой скелет, каталоги есть, файлов в них нет), и только потом уже рекурсивно удаляет сами каталоги.

это говорит лишь о тупизне твоей ФС. В нормальной ФС такого быть не должно - ибо регулярный файл в нормальной фс удалить стоит столько-же, сколько и каталог. А вот удалить «папку» значительно сложнее, что очевидно.

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

это важно только для венды. В Linux ты можешь удалить файл, при этом работая с этим файлом. Попробуй сам:

~$ mkdir testdir
~$ cd testdir/
~/testdir$ rmdir ../testdir/
~/testdir$ ls ../testdir
/bin/ls: невозможно получить доступ к ../testdir: Нет такого файла или каталога
$ ls -la .
итого 0

Вообще говоря это тупость венды - в нельзя получить доступ к открытому файлу. Что-бы удалить файл, приходится сначала его открыть, усечь до 0, потом закрыть и собственно удалить. В Linux ты можешь файл сначала удалить, а потом освободить место. Т.о. каталог становится пустым ЗАДОЛГО ДО удаления файлов в нём. В венде очевидно можно удалять несколько файлов одновременно, потому и удаление файлов быстрее в 2 приёма (если в каталоге 1.5 файлов, то удалять два таких файла одновременно не получается, если ещё и каталоги надо. А если не надо, то получается).

практика

руки кривые.

Запись начинает падать до десятков файлов в секунду.

не запись, а СОЗДАНИЕ. ФС оптимизирована на ДОСТУП. Доступ ложится пропорционально O(log(N)), что мало заметно (если файлов в 1000000 раз больше, доступ дольше в 20 раз примерно)

не, я это всё к тому, что в винде и в POSIX-системах каталог должен быть пустым, чтобы его можно было удалить вызовом unlink() или RemoveDirectory()

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

YYYY/MM/DD/f40e7bff300851a3554dda25e28af470.jpg Разумно. глупо. Зачем тут хеширование? раньше оно нужно было для многоступенчатости, а сейчас?

не, я это всё к тому, что в винде и в POSIX-системах каталог должен быть пустым, чтобы его можно было удалить вызовом unlink() или RemoveDirectory()

что по твоему «пустой каталог»? в линуксе это такой каталог, в котором нет имён файлов, за исключением . и ..

Вот только такой каталог удалить и можно. Только он НЕ УДАЛИТСЯ, пруф

$ stat .
  Файл: «.»
  Размер: 0         	Блоков: 8          Блок В/В: 4096   каталог
Устройство: 803h/2051d	Inode: 40627       Ссылки: 0
Доступ: (0755/drwxr-xr-x)  Uid: ( 1001/ drbatty)   Gid: (  100/   users)
Доступ: 2012-11-05 15:50:06.207789348 +0400
Модифицирован: 2012-11-05 15:49:39.352376161 +0400
Изменён: 2012-11-05 15:50:07.140907943 +0400
 Создан: -

300 тыс. файлов лет за пять — это в среднем по 165 файлов в день. В этом варианте разбивка по часам не обязательна, я уже прикидывал. Даже по месяцам будет по 5000 файлов в каталоге. С точки зрения нагрузки на ФС — нормально. Правда, работать ручками с таким вариантом неудобно. Так что, скорее всего, по дням сделаю.

Кстати, исходный вариант вообще не позволяет посмотреть бегло из консоли, скажем, все файлы залитые сегодня. Ещё один недостаток, с которым столкнулся на практике, но не упомянул в топикстарте.

исходный вариант вообще не позволяет посмотреть бегло из консоли, скажем, все файлы залитые сегодня. Ещё один недостаток, с которым столкнулся на практике, но не упомянул в топикстарте.

т.е. команды типа:

find -ctime -2 -type f 

все файлы залитые сегодня

Если есть сведения о файлах в базе - то только утилиты писать.

Кстати, реализация .git/objects на хэшах, но несколько иной механизм. Там учитывается (вероятно) идентичность объекта, что дает определенную экономию.

Зачем тут хеширование? раньше оно нужно было для многоступенчатости, а сейчас?

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

Хеширование до сих пор активно используется в squid, git например. Но там другие алгоритмы чем просто «часть хэша».

реально захлебываются?

им надо ВСЕ файлы просмотреть. Сложность O(N). Однако можно показать, что сложность можно и уменьшить, если сделать многоступенчатую структуру в зависимости от даты. В предельном случае будет O(log(N)) что и достигается в любой (нормальной)ФС для доступа к одному файлу ПО ИМЕНИ. А дата - извини, ФС по ней индекс не строит. Либо сам наворачивай ступени по дате, либо возьми СУБД с двумя индексами (если нужен доступ по имени и по дате).

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

«тесты» это не замена чтению документации. про твои ФС читать тебе, а вот про ext* я расскажу:

man mke2fs

dir_index Use hashed b-trees to speed up lookups in large directories.

оно включено по умолчанию ещё в ext3.

Хеширование до сих пор активно используется в squid, git например. Но там другие алгоритмы чем просто «часть хэша».

дык понятно, что это полезно и нужно, но наворачивать хеш поверх хеша просто бесполезно. К тому же, криптостойкость md5 тут обычно не нужна. (ну то есть она спасёт от некоторых атак, но только при некоторых условиях, о которых ТС даже не думал. Например нужна какая-то уникальная соль, заранее неведомая злоумышленнику.)

«тесты» это не замена чтению документации. про твои ФС читать тебе,

Я уж почитаю не беспокойся)) Но, полагаться архитектуре прикладного стореджа на ФС равносильно лишней зависимости (привязанности) к особенностям ФС. Бездумно лепить хэши тоже никто не собирается. Необходим разумный компромисс.

оно включено по умолчанию ещё в ext3.

Но ведь тормозит по утверждению ТС!

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

Просто сменить алгоритм схемы «хеширования» на более эффективную. Если не хочется использовать БД, а именно ФС.

К тому же, криптостойкость md5 тут обычно не нужна.

В данной ситуации больше актуальна уникальность хранимых объектов.

какая-то уникальная соль, заранее неведомая злоумышленнику

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

т.е. команды типа

Это костыль. Ну будет у тебя список файлов. Его ещё привести в порядок надо, отсортировать как надо. И в лучшем случае на такой поиск уходит несколько минут. В случае с разбивкой по датам же мы имеем то же самое мгновенно.

Если есть сведения о файлах в базе - то только утилиты писать.

Угу. Опять что-то писать :) Я же писал уже пару раз выше, что все вопросы можно решить и обойти. Но — костылями. В то время, как при отказе от хеширования в этом стиле вопрос решается автоматически и без костылей.

Я уж почитаю не беспокойся)) Но, полагаться архитектуре прикладного стореджа на ФС равносильно лишней зависимости (привязанности) к особенностям ФС. Бездумно лепить хэши тоже никто не собирается. Необходим разумный компромисс.

дело в том, что создатели ФС оптимизируют их для быстрого доступа по имени файла. Очевидно, с таким подходом страдают ВСЕ остальные характеристики. Ситуация, когда основная операция - доступ по имени, является типичной для ФС. Точнее считается типичной. Ну а дальше - типичный матан: минимальное время доступа - O(log(N)) определяется тем, что структура должна быть многоуровневой, при этом число уровней пропорционально log(N), что и приводит нас к сильноветвящимся b-деревьям. Ничего принципиально иного ещё не придумали, и даже более того - математики ЕМНИП даже сумели доказать, что ничего лучшего и быть не может. Т.е. _любая_ _другая_ ФС будет _хуже_ в типичной ситуации.

Просто сменить алгоритм схемы «хеширования» на более эффективную. Если не хочется использовать БД, а именно ФС.

кстати, в ext3|4 можно не только отключить, но и поменять хеширование.

hash_alg This relation specifies the default hash algorithm used for the new filesystems with hashed b-tree directories. Valid algorithms accepted are: legacy, half_md4, and tea.

Что касается СУБД, то нужно учитывать, что они оптимизимрованны на ВЫБОРКУ, т.е. например можно БЫСТРО сделать выборку от 12345 до 12377. В ФС такого обычно нет, т.е. придётся взять ВСЕ имена, отсортировать, а потом уже делать выборку. Или обойти ВСЕ файлы в каталоге(как делает find). Надо оно или не надо - от задачи зависит. Впрочем, некоторые выборки можно делать (под)каталогами. Например выборка для быстрого доступа к дням можно сделать вида YYYYMMDD/XXXXXXXXXX, где XXX это какой-то хеш или просто имя(если оно уникально в пределах суток). Вот только проблема в доступе по конкретному имени. Можно сделать ещё и один большой каталог с именами-хардлинками.

В данной ситуации больше актуальна уникальность хранимых объектов.

если так, то пойдёт и CRC32, которая на порядки быстрее.

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

не, я к тому, что враг может создать 100500 хешей начинающихся на 0xABCDXXXXXXXXX, и этим затормозит работу с каталогом AB/CD/, в котором будет 100500 файлов. DoS называется. Врагу это не сложно, ибо каждый 65536й случайный файл имеет хеш 0xABCD*. Была-бы неизвестная врагу соль, он-бы не смог подобрать такие файлы(криптостойкий хеш не разложим на две части, даже если одна из них известна. Только перебором). В качестве соли можно взять например ID процессора + дата в микросекундах от начала эпохи.

не, я к тому, что враг может создать 100500 хешей начинающихся на 0xABCDXXXXXXXXX, и этим затормозит работу с каталогом AB/CD/

Это в случае, если враг имеет доступ на запись - по другому изменить схему хеширования невозможно, не имея доступа к скриптам.

если так, то пойдёт и CRC32, которая на порядки быстрее.

или для скорости тогда уж «сверх короткие хэши»

математики ЕМНИП даже сумели доказать, что ничего лучшего и быть не может

Кроме случая N=1 )) И случаев оптимального N

минимальное время доступа - O(log(N)) определяется тем, что структура должна быть многоуровневой

О каких уровнях идет речь извиняюсь за прямоту?

выборка для быстрого доступа к дням можно сделать вида YYYYMMDD/XXXXXXXXXX

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

Это в случае, если враг имеет доступ на запись - по другому изменить схему хеширования невозможно, не имея доступа к скриптам.

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

или для скорости тогда уж «сверх короткие хэши»

для наших CPU и наших накопителей вычисление CRC32 уже не тормозит процесс доступа к файлам. А вот md5 пока ещё требует значительных ресурсов. ИЧСХ, скорость io пока ещё увеличивается, а вот скорость CPU упёрлось в предел.

математики ЕМНИП даже сумели доказать, что ничего лучшего и быть не может

Кроме случая N=1 )) И случаев оптимального N

случай N=1 и какое-то «оптимальное N» на практике не интересен. В случае N=1 (1файл) и так всё мгновенно ищется. При _любой_ структуре.

О каких уровнях идет речь извиняюсь за прямоту?

ну есть множество файлов в N эл-тов. Очевидно, поиск 1 эл-та потребует O(N) операций. Это если элементы в беспорядке. Однако, ты можешь разделить N эл-тов на N1 множеств, в каждом из которых N2=N/N1 эл-тов. Очевидно, что теперь тебе надо N1 операций для выбора множества и N2 операций для выбора нужного эл-та. К примеру для множества в 65536 понадобится не 32768 операций, а всего 128+128 операций. Это если N1==N2 (что оптимально). Это будет при N1==N2==sqrt(N). Однако, поиск можно ещё больше ускорить, если уровней ещё больше. Т.е. Всего N1 множеств по N2 подмножества по N3... по N(M) эл-тов. Несложно показать, что оптимальное M == log(N) (основание логарифма здесь суть арность дерева. Для бинарного двоичный логарифм. арность дерева на асимптоту не влияет, ибо константа выносится) Потому для 65536и эл-тов нужно дерево высотой 16, если это дерево бинарное. В этом случае поиск нужного узла не превышает 16и операций и в среднем составляет где-то 13 (не 8, потому-что большинство узлов лежит ближе к листьям. Например половина(32768) - листы). Это _теоретический_ минимум.

На 3-и года хватит, потом начнет подтормаживать

нет. 3 года == 1000 с небольшим файлов-дней. Тыщу файлов и FAT легко сожрёт.

Пока, найденное решение ТС оптимально для его ситуации.

хранить данные в виде YYYY/MM/DD/XXXXXXXXXXXX? Зависит от числа файлов в день, на самом деле. В любом случае, ИМХО полезно прошедший мес. стирать нафиг, и делать YYYYMMDD.tar.xz

Провёл комплексную оптимизацию системы на счёт разгрузки работы с диском, параметров монтирования. Выкинул из rsync'а кеши. Получил время копирования около 6 минут. Уже не те четыре с лишним часа, что были изначально, но всё ещё много.

Это ещё без редизайна, в оригинальном варианте.

Вообще, в последний год или около того, ext4 стала сильно хуже, чем была раньше. Раньше работала прекрасно под высокой нагрузкой без всякого тюнинга, а теперь приходится поднимать commit, вырубать barrier, ставить noatime. А то машина вся уходит в непрерывное журналирование уже на commit=60.

Смотрю, как работает find /var/www/balancer.ru/htdocs/cache -atime +14 -type f -delete (с idle) в iotop и фигею. Читает по 20..60кбайт/с. Иногда по 400. Потом рывками пишет по 20Мбайт/с. Всё время жрёт 99.8% io и страшно тормозит систему.

При чём на свежей системе такого и близко не было. Походу, деградация ФС налицо. Не знаю, дело в структуре на диске (фрагментация?) или в ухудшении работы с ext4 в последних ядрах (выше ругался, что такое, кажется, есть).

Походу, нужно попробовать выносить кеши на отдельный раздел и периодически (на выходных, когда нагрузка на пересоздание кеша поменьше) его тупо вообще форматировать…

Теперь, вот, придётся переделывать на логику YYYY/MM или даже YYYY/MM/DD.

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

elliptic, mongo. На выходе можно добавить nginx кеширующим прокси.

По монге мне приводили такие цифры: на 3 терабайта котиков хватает несколько гигабайт дискового кеша (прокси), а самой монге хватает 8 гигов памяти.

Под бакапы просто реплика делается.

По монге мне приводили такие цифры

Вот только отдавать статику придётся не прямо с диска, а скриптом. Что почти на порядок снизит производительность по исходной задаче. А если потребуется отдавать с закачкой, то всё равно придётся сохранять промежуточный результат на диск. Или key-value научились читать блобы с заданной позиции и заданной длины? Делать по блобам seek?

Ведь основная задача — не быстрый бэкап. А быстрая отдача клиенту. Бэкап — задача побочная.

База -> Скрипт -> [nginx прокси с кешем на диске] -> Юзеры

Нормально будет. Я ж привел данные с рабочей системы, это городской портал ебурга. Причем у них в лоб 30 питонских процессов, а ля похапе. На вопрос, почему не сделали асинхронную раздачу, ответили, что тогда драйверы монги были кривые, а сейчас «ну и так работает, хватает».

В элиптике сики точно оптимизированы. На яке было видео, где они рассказывали о 4-кратном профите по сравнению с обычной ФС. Насчет монговского гридфс не в курсе.

У скриптов тупак обычно в пыхе на блокировках - вешают на FCGI 10 процессов, а потом кто-то запрашивает 30 картинок, и перевед-медвед. Ну дык не надо такое на пыхе делать, ясен пень.

Ведь основная задача — не быстрый бэкап. А быстрая отдача клиенту. Бэкап — задача побочная.

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

запас по скорости большой. Но мне нужны реплики.

т.е. все блобы (большие и маленькие включая мелкие (картинки)) лежат в key-value сторедже и собственно отдача идет скриптом по общей схеме типа:

blob = storage.get(k)
out(blob)

Клястья не буду, но по-моему в ебургском сторадже именно так как вы сказали. Но учтите, что там кеширующий прокси обязателен. Мне было интересно, сколько дискового кеша в реальной жизни надо на несколько терабайт котиков. Оказалось, меньше 10 гигов.

А я планирую нодовскими стримами из монги раздавать, сделав размер буфера килобайт 30-100К. Мелкие картинки выгребутся одним чанком. Крупные - кусками. Просто надо следующий чанк из базы вытягивать не когда предыдущий полностью отправлен, а слегка заранее. Тогда и явных тормозов не случится. Должно по идее даже без прокси работать быстро. Другое дело, что я на этом прокси планирую ленивый ресайз картинок селать.

У элиптика своя раздавалка, деталей не знаю.