ChunkFS и Продолжающие Иноды
----------------------------
ChunkFS это идея, к которой Arjan van de Ven и Val Henson пришли для борьбы с кризисом fsck. Она схожа с идеей для улучшения Lustre на уровне распределённой ФС разрабатываемой в настоящее время в Cluster File Systems, Inc. Для объяснения мы начнём с версии идеи, которая не работает.

В начале 2006 Val Henson начал изучать идею уменьшения времени работы fsck в ext2. Ext2 удивительная ФС - быстрая, надёжная, простая но имеющая раздражающее требование полного fsck после отказа. Её первоначальной идеей было пометить отдельные группы блоков как грязные или чистые в зависимости от были ли они модифицированы, и затем затем модифицировать fsck для пропускания чистых груп, таким образом уменьшая среднее время fsck (прим перев - ну вот, ещё одна женщина и снова с тряпкой и шваброй, но без них мужики давно заросли бы грязью ;) ). Первоначальные измерения показали что подход разделяй-и-властвуй дб обещающим, поскольку максимально 25% груп блоков были грязными в любое время для тяжелонагруженной ФС и большинство груп были чистыми больше чем 90% времени под нормальной нагрузкой в ноутбуке. Однако эта схема потерпела неудачу вследствие того что ссылки ФС не содержатся внутри груп блоков. Если fsck хочет знать правилен ли битмап выделения группы блоков для данного блока, то ей придётся строить блоковый битмап пробегая всю ФС поскольку любой инод в произвольной группе может ссылаться на на любой блок в любой группе. Вместо этого она реализовала бит "грязноты" для всей ФС показывающий грязна ли ФС целиком позволяя системе пропускать fsck если система отказала когда ФС была чиста.

Arjan van de Ven был удивлён: что, если если мы разделим эту ФС на малые ФС - "куски" (chunks) каждая с её собственным битом "загрязнения", так что время работы fsck будет более предсказуемым? Это быстро развилось в схему, в которой пользователь видит набор небольших ФС (с любой формой гарантии согласованности - бит "загрязнения" не обязателен) как одну большую ФС, причём малые ФС способны восстанавливаться индивидуально. Суть в том, чтобы позволить файлам и директориям переходить границы ФС создавая "иноды продолжения" в других ФС. Например, если файл вырастает слишком большим для своего "чанка", мы создаём "инод продолжения" в другом "чанке" и указываем на него. Новый инод имеет обратный указатель на оригинальный инод. Для директории имеющей линк на файл в другом чанке мы создаём инод продолжения для этой директории в новом чанке и выделяем директорный вход (directory entry) для этого линка в том же чанке, где находится сам файл. Это имеет тёмную сторону в том, что число хард-линков (hard links) ограничено свободным местом в этом чанке; однако большое число хард-линков встречается редко. Эта проблема мб уменьшена резервированием минимального числа хард-линков для создаваемого инода. Другая возможность заключена в выделении инода продолжения для линкуемого файла в том же чанке, где находится директория и скрепить различные хард-линки вместе, используя связный список, чтобы предусмотреть случай удаления оригинального линка.

Важными инвариантами является то, что на блоки могут ссылаться только иноды в том же чанке, и что любые иноды с через-чанковыми линками имеют явные обратные указатели на родительский инод. Fsck нужно проверить только локальные иноды для восстановления битмапа блоков и локальные иноды плюс обратные указатели этих инодов для проверки числа ссылок на иноды. Запоминаемой выдержкой из этого обсуждения была: "Если вы хотите проверить это, вам придётся зачанкать это."

В идеале fsck на chunkfs должен быть реализован на по-файловой системе, в он-лайн, на основе по-требованию. Если чанк испытывает ошибку ввода/вывода или ФС обнаруживает несоответствие чексумм, этот чанк может быть выведен в оффлайн индивидуально и проверен с меньшим влиянием на остальную часть этой ФС (здесь дб взята в рассмотрение иерархия директорий; возможно разумнее реплицировать директории у корня этой ФС или позволить независимые монтирования файлов в отдельных чанках).

Chunkfs имеет мног ополезных свойств. Chunkfs мб создана с различными инодовыми отношениями и размерами. Файлы мб легко выделены в чанки на основе размера для уменьшения фрагментации. Возможно файл создаётся в чанке малых файлов и когда он растёт создаётся его инод продолжения в чанке больших файлов. Это мб полезно для случаев когда зачитываются только несколько первых байтов файла, таких как команда file и просмотрищики изображений. 32-битные указатели блоков достаточны для chunkfs, поскольку невероятно что мы захочем иметь чанки размером терабайты. Chunkfs накладывает несколько ограничений на реализацию ФС внутри каждого чанка и возможно мб реализована как общий слой используемый с любой локальной ФС. Расширение ФС тривиально - добавьте новые чанки и уменьшение упрощено, поскольку данные могут быть передвинуты целым чанком сразу.

Вообще, chunkfs была одной из редких идей, которые выглядели тем лучше, чем больше мы думали о них. Мы будем обсуждать её далее на в списке Linux fsdel (http://vger.kernel.org/vger-lists.html#linux-fsdevel) в ближайшем будущем.

Doublefs
--------
Doublefs это идея, к которой Theodore Ts'o и Val Henson пришли пару лет назад, пытаясь получить преимущества COW файловых систем без болезненной необходимости выделения новых блоков и вычисления пространства необходимого для апдейта. Поскольку место на диске дёшево, почему бы не выделить заранее две копии всех метаданных, включая блоки директорных входов (directory entry). Когда происходит апдейт ФС, переписывается только одна копия метаданных и помечается номером транзакции. Когда полный набор апдейтов отправлен на диск, происходит возврат и апдейт второй, старой копии метаданных в любое свободное время. Полу-апдейченые метаданные отслеживаются некой формой мапа или списка загрязнения на диске, так что если ФС падает в середине апдейта, мы можем возвратиться и очистить её при помощи копирования старой или новой копии метаданных через вторую копию в зависимости когда мы упали. Разногласия между копиями улаживаются проверкой номера транзакции и чексуммы.

Одно замечательное свойство этой системы заключено в том, что две копии не нужно располагать по порядку или даже около друг друга, поскольку их запись разделена по времени. Это увеличивает шанс, что только одна копия будет попорчена ошибкой ввода/вывода. Другое замечательное свойство в том, что вторую копию нужно писать только для того, чтобы уменьшить время восстановления при ребуте (и шанс что хорошая копия испорчена перед тем, как вторая копия проапдейтилась). Zach Brown и Aaron Grier приложили некоторые усилия для прототипирования doublefs.

Иноды в Директорных Входах
--------------------------
Ещё одна главная идея, обсуждённая на конференции, это сделать директорный вход (directory entry) главным хранилищем метаданных файла, а не в отдельном иноде как предложил Linus Torvalds. В настоящее время директорный вход содержит только две главные части информации: имя линка на файл и инодовый номер файла. Может иметь смысл иакже включить сам инод в директорный вход. Статья описывающая одну из реализаций этой схемы: Встраиваемые иноды и чвная группировка: Используя пропускную способность диска для малых файлов (http://www.ece.cmu.edu/~ganger/papers/cffs.html) Greg Ganger и тд.

Одна из трудностей связана с тем что случается когда файл создаётся в одной директории, ещё линк создаётся из другой директории и оригинальный линк удаляется. Этот инод должен быть мигрирован в другую директорию посредством некоторого связного списка. Это означает, что частный номер инода не располагается в статичном месте, усложняя всё что должно искать файлы по номеру инода. Сейчас только NFS серверам нужно искать файлы по номеру инода вследствие реализации идентификаторов файлов в NFS. Также мы можем изменить номер инода, когда передвигаем его в другую директорию, по причинам внутренней архитектуры ФС. Одно из решений - иметь видимый пользователю номер инода постоянный на протяжении всей жизни файла и внутренний номер инода, который может меняться.

Перемещение инодов в директорный вход открывает способ лёгкого добавления в него некоторого количества данных. До некоторого предела данные файла могут быть упакованы в директорный вход вместе с его инодом. Это значительно уменьшает дисковую фрагментацию из-за частично-использованных блоков данных. Чтение всей информации о файле за одину операцию ввода-вывода улучшает производительность многих нагрузок, поскольку обычно чтение холодного кеша данных файла требует три разныз операции ввода-вывода: сначала найти директорный вход, затем прочитать инод и наконец прочитать данные указываемые этим инодом. Главное в упаковке данных файла это то, что её реализация способствует багам и трудна в достижении правильного варианта вследствие необходимости корректной переупаковки данных если размер файла меняется. Однако, мы видим, что очень маленькие файлы обычно создаются и удаляются атомарно и наоборот редко изменяются. Одно правило, которое может работать, состоит в упаковке данных файла в директорном входе в момент первоначального создания файла (используя отложенное выделение для избежания создания файла до тех, пор пока данные не будут записаны). Если файл растёт или изменяется необходимо немедленно перетащить данные из директорного входа и никогда не возвращать их назад. Christoph Hellwig предложил, что возможно будет легко сделать прототип этого в XFS.

Включение инодов и/или данных файла в директорный вход влияет на производительность сложным образом. Одна из фундаментальных уступок в производительности ФС это производительность readdir() против stat() против cat на большом числе файлов. Если всё, что вы делаете, это пролистывание всего содержимого директории, то вы обычно читаете директорный вход и затем немедленно делаете stat() над этим файлом, читая пачку ненужных данных с диска. Однако, если вы обычно читаете директорный вход и затем немедленно делаете stat над этим файлом, читая его инод, тогда имеет смысл включить его инод в его директорный вход, даже если это снижает производительность перед по сравнению со случаем чистого readdir. Тот же аргумент работает для stat, за которым следует чтение данных файла - включение некоторого количества данных может ускорить случай stat + cat, ценой замедления случая чистого stat.

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

Вторая уступка, которую вы можете назвать stat-против-cat менее очевидна. Как часто мы делаем stat файлов и как часто cat их же? Работая на ZFS мы сделали некоторые измерения производительности и обнаружили что увеличение размера инодов достаточное для включения нескольких сотен байт данных серьёзно повлияло на производительность случая stat, потому что это уменьшило плотность нужных нам данных и потребовало чтения данных с диска в несколько раз больших чем необходимо. В конце концов наиболее эффективный размер инодов зависит от нагрузки ФС и должен быть тщательно изучен.

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

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

Простейшая техника это отложенное выделение - ожидание в течение некоторого времени после записи чтобы увидеть не будет ли дописано ещё данных. Другое решение, используемое сейчас в BSDишной реализации FFS в течение нескольких лет это перевыделение блоков. Когда происходит запись в файл, целый файл может быть перетащен куда-либо на диск, включая ранее выделенные блоки в более пригодное место. Другая техника, функция POSIX fallocate(), говорит системе выделить N байт на диске для указанного файла, что полезно для программ, подобных tar и пакет-менеджеров заранее знающих размер файла. Если программа выделяет больше места чем ей нужно она должна явно укоротить файл. Некий флаг для реализации этого был бы удобен.

Большая часть дискуссии крутилась вокруг получения подсказок от приложения о том как файлы будут создаваться и использоваться. Одна точка зрения говорит, что приложения уже дают нам подсказки о размере, пермишенах и других атрибутах: они называются "имена файлов". Если файл назван "*.log", то довольно логично предположить что он будет вначале небольшим, будет медленно расти, сьанет очень большим и будет только дописываться. Если файл имеет строку "lock" в его имени, вероятно он будет нулевой длины, над ним часто будет делаться stat и он будет удалён в будущем. Если он называется "*.mp3", то вероятно он будет записан один раз, будет последовательно читаться много раз и иметь размер несколько мегабайт. Другие атрибуты файла, такие как пермишены дают ценные подсказки для предсказания будущего файла. Daniel Ellard и другие написали несколько статей на эту тему: Полезность имён файлов (http://www.eecs.harvard.edu/~ellard/pubs/tr-05-03.pdf), Предсказание имён файлов на основе атрибутов (http://www.eecs.harvard.edu/~ellard/pubs/able-usenix04.pdf). Вторая статья описывает систему, которая автоматически выводит корреляции между паттернами имён файлов и их атрибутами и будущей файловой активностью, задавая следы активности ФС, так что вам не нужно вручную изменять оптимизации на основе имён файлов, например когда будет популярен новый аудио формат.

Многие из этих политик выделения могли бы быть реализованы в слое VFS и дополнительно использоваться файловыми системами, а не быть напрямую реализованы в каждой ФС. Многие люди хотели бы видеть код резервирования написанный Mingming Cao доступным посредством некоторой портируемой формой для других ФС.

Одно изменение в наших предположениях, которое влияет на выделение, это факт необходимости делать чистку для обнаружения и ликвидации ошибок до того, как они станут неликвидируемыми. Поскольку нам необходимо просматривать ФС, мы можем быть способны делать другие вещи пока мы здесь, такие как непрерывная дефрагментация ФС. Одна из техник для значительного уменьшения стоимости чистки и дефрагментации называется "планирование свободных блоков"(http://www.pdl.cmu.edu/Freeblock/index.html). Идея заключается в том, что пока диск обслуживает важные "передние" обращения, читающая головка свободна во время поисков или ожидает пока диск повернётся к нужным данным. Если мы имеем очередь известных "фоновых" обращений мы можем прочитать эти блоки во время прохождения над ними, когда обслуживаются "передние" обращения, вызывая небольшое или вообще не вызывая потери их производительности. Один недостаток этой системы это то, что она работает лучше всего с детальным знанием устройства диска; однако эти идеии всё ещё полезны для уменьшения стоимости фоновых задач поддержки диска.

Краткосрочные Нужды Файловых Систем Linux
-----------------------------------------
Мы посвятили часть времени после обеда второго дня конфы обсуждению свойств необходимых файловым системам Linux в следующем году. В списке был высокоприоритетным любой метод для борьбы с медленными восстановлением ФС. Уменьшение количества данных, которые необходимо проверить при помощи пометки чести метаданных как неиспользуемых или чистых должно помочь, как в подходе постепенной пометки используемых инодов ext2/3 когда необходимо. Многие реализации fsck сильно оптимизированы, но мб ещё место для оптимизации. Просто владение инфой как долго ФС должна восстанавливаться позволяет админу решить предпринимать ли попытку восстановления или поднимать её из back-up.

Другой ближнесрочный подход предлагает добавить стратегически чексуммы и обработку ошибок в существующие ФС. Один пример есть в "IRON ФС" (http://www.cs.wisc.edu/adsl/Publications/iron-sosp05.pdf), сделанной в University of Wisconsin, Madison. Это привело к обсуждению сложности передачи кода написанного исследователями в главное дерево разработки с открытыми исходниками. Было предложение сдвинуть фокус исследователей на производство данных, которые могут быть использованы разработчиками главного дерева при разработке кода, поскольку вообще говоря приём кода не уместен для обычного разработчика ФС.

Следующим в списке была поддержка принудительного отмонтирования, способности принудительно отмонтировать ФС, даже если она имеет открытые файлы. Это черта нескольких существующих ФС и она полезна для отмонтирования ФС без выгрузки всей операционной системы. Большая часть принудительного отмонтирования модет быть реализована на уровне VFS (например заменой VFS опсов открытых файлов на опсы VFS всегда возвращающие EIO), но некоторые ФС потребуют тестирования и работы чтобы быть способными безопасно отмонтировать в случае ошибок. Вероятно принудительное отмонтирование мб реализовано за несколько месяцев работы и быть доступным для использования в production в течение года. Это свойство должно идти рука об руку с хорошим тестированием на ошибки ввода-вывода, иначе наши усилия по изоляции ошибок ФС будут не очень успешны.

Другой вопрос заключён в факте что производительность ФС обычно тестируется на относительно молодой не фрагментированной ФС. Коммьюнити разрабатывающее ФС должно работать с исследователями над лучшими способами быстрого создания "пожилых" ФС. В одна идее предлагалось вставить множество вызовов sync() во время ускоренного переигрывания следов ФС так, что ФС не может использовать умные политики выделения которые могут быть не доступны в настоящей пожилой ФС. Последние исследования на переигрывание следов ФС сделано Ningning Zhu и остальными в статье "Масштабируемое и точное переигрывание следа ФС для оценки ФС" (http://www.ecsl.cs.sunysb.edu/tr/TR1533.pdf). Хорошая статья на пожилые ФС написана Keith Smith и другими: "Старение ФС - увеличение значимости бенчмарков ФС" (http://www.eecs.harvard.edu/margo/papers/sigmetrics97-fs/paper.pdf).

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

День Третий: Планы
------------------
Последний день конфы был посвящён тому, чтобы сделать Linux ФС следующего поколения реальностью, другими словами мы распределяли работу. Было также утро субботы после двух ужасных дней и ночей непрерывного обсуждения ФС. Чудесным образом почти все участники конфы возвратились в последний день.

Первым в нашем списке to-do было убедить Linux комьюнити включая компании работать вместе над разработкой новых ФС. Нам нужно поставить комьюнити перед фактом временнОго кризиса fsck и необходимости разработки новой ФС сейчас, поскольку требуется около 5 лет для доведения ФС от концепции до использования в production. Участники конфы работают над коллекциями слайдов собирая требования и создавая статьи в надежде повлиять на комьюнити и компании посвятить ресурсы разработке Linux ФС. Нам нужно продолжить работу над существующими ФС, такими как ext2/3, reiserfs, XFS так чтобы они заполнили промежуток времени пока новые ФС в разработке. Мы организуем встречи между производителями железа, исследователями и разработчиками ФС для обмена данными и идеями. Последующая конфа на Linux ФС предварительно запланирована быть вместе с пятой конференцией USENIX FAST в San Jose, CA в феврале 2007. Мы не запланировали ничего формального для Ottawa Linux Symposium но вы можете захотеть посетить выступление Val Henson об "уменьшении времени fsck в ext2" (http://www.linuxsymposium.org/2006/view_abstract.php?content_key=112), поскольку оно охватывает другие темы в Linux ФС.

Что касается кодирования, мы имеем несколько идей для создания прототипов:
* поддержка принудительного размонтирования
* переменный размер инодов и влияние на нагрузки stat против нагрузки cat
* постепенная инициализация таблицы инодов в ext3
* прототип chunkfs используя существующие ФС
* прототип doublefs
* инод и данные файла в директорном входе
* планирование свободных блоков
* добавление флагов к stat() для запроса части данных stat

Если вы или ваша организация заинтересовалась в работе с любыми из этих идей или вовлечении в разработку любым способом пошлите емейл в список Linux fsdevel (http://vger.kernel.org/vger-lists.html#linux-fsdevel).

Формальная часть конфы закончилась по полудню но несколько упёртых душ приняли приглашение посетить Пивной Linux Summit организованный Kristen Carlson Accardi (заведующий док-станцией) и спонсированной Гуглом. Обсуждения ФС продолжились заполночь после замечательного домашнего пива, и Inaky Perez-Gonzalez (поддерживает Ultra-wide-band) предложил для всех возбуждающую поездку на медленном тракторе.

День первый

http://www.linux.org.ru/jump-message.jsp?msgid=1506610#1507623

А где взять оригинал?

введение: http://lwn.net/Articles/190222/

день первый: http://lwn.net/Articles/190223/

день второй и третий: http://lwn.net/Articles/190224/

что, англичанка тыщи без оригинала не принимает? ;)

> ...Иноды в Директорных Входах

Я хочу выразить благодарность за перевод, и высказать пожелание. Как я понимаю, речь идёт о Directory Entries, мне было крайне трудно читать перевод этого устойчивого термина как "директорный вход". Здесь вместо "вход" гораздо больше подходит термин "запись". Да и само слово "директорная", это какой-то прямолинейный перевод, скорее подошло бы слово "каталожная". Получается "каталожная запись", что означает "запись в каталоге", что даже соответствует истине. Т.е. я не проф. переводчик, но чтение "директорных входов" мне постоянно приходилось транслировать мысленно, чтобы понять о чём речь. Про иноды ничего не скажу, для меня это устойчивая калька.

> Как я понимаю, речь идёт о Directory Entries, мне было крайне трудно читать перевод этого устойчивого термина как "директорный вход". Здесь вместо "вход" гораздо больше подходит термин "запись". Да и само слово "директорная", это какой-то прямолинейный перевод, скорее подошло бы слово "каталожная". Получается "каталожная запись", что означает "запись в каталоге", что даже соответствует истине. Т.е. я не проф. переводчик, но чтение "директорных входов" мне постоянно приходилось транслировать мысленно, чтобы понять о чём речь.

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

обшибся немного, суперблоком принято называть маджик намбер плюс несколько других параметров, в ext2 (http://www.linux-tutorial.info/modules.php?name=Tutorial&pageid=274), битмапы инодов, блоков и таблица инодов идут сразу за ним, но не входят в суперблок, а каталог находится и вовсе в специальных directory files (http://www.linux-tutorial.info/modules.php?name=Tutorial&pageid=277). Это в s5fs битмапы были в суперблоке, а список инодов с названиями файлов находился сразу за суперблоком, именно это я и назвал неправильно суперблоком, впрочем в наследниках s5fs (как в ext2, например) каталог расположен всё равно не здесь, а в directory files, которые лучше назвать файлами каталога, что позволяет иметь неограниченное число файлов в разделе (что не позволяла s5fs).

я бы оставил Directory Entries на английском ибо "каталожная запись" ничем не лучше "Директорных Входов"

Нет. Английйский я сдал уже давно. Не люблю переводы.

> Нет. Английйский я сдал уже давно. Не люблю переводы.

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