23 сентября 2015 г.

BFS - перевод статьи Эндрю Хадсона (файловая система Haiku)

Антон Якушев подготовил перевод статьи Эндрю Хадсона, рассказывающей о внутреннем устройстве файловой системы BFS (Be File System), изначально разработанной для операционной системы BeOS и используемой в настоящее время открытым проектом Haiku.

Недавно наткнулся на статью Эндрю Хадсона: "The BeOS file system: an OS geek retrospective" и счел ее довольно интересной. Потихоньку начал переводить для себя, но подумал, что это может быть интересно и другим. Разговор пойдет о файловой системе BFS (или BeFS дабы не путать с Boot File System).

Файловая система для BeOS, известная так же как BFS, используется в Haiku, BeOS, и SkyOS. Когда она была создана в конце 90-х как часть злополучного проекта BeOS, своим набором функций получила признание среди гиков-энтузиастов. Этот набор функций включает в себя:
  • 64-битное адресное пространство.
  • Журналируемая файловая система.
  • Большая скорость чтения в режиме многопоточности.
  • Поддержка расширенных атрибутов файлов.
  • Оптимизация для потокового доступа к файлам.
В этой короткой статье, мы взглянем на легендарную BFS, начиная с некоторого файловой основы и перейдем к обсуждению особенностей. Также включены в конце статьи 2 интервью: первое с человеком, который разработал BFS для Be, а второе с разработчиком версии BFS с открытым исходным кодом.

Немного истории

BFS разработали в 1997 году Dominic Giampaolo и Cyril Meurillon, оба работали на Be. Она проектировалась как легкая, с поддержкой многопоточности, файловая система для поддержки больших объемов и потокового мультимедиа. Также была предназначена для поддержки функций базы данных предыдущей файловой системы Be. Хотя она была написана в то время, когда типичные компьютеры имели 8MB оперативной памяти, а жесткий диск имел объем 9GB, дальновидный дизайн позволил BeFS быть актуальной и сегодня.

В 2002 году Аксель Дёрфлер (Axel Drfler) переписал оригинальный драйвер BFS для Haiku, как проект с открытым исходным кодом.

Прежде чем мы сможем говорить о том, что же в BFS такого особенного, сначала поговорим немного об основах файловой системы.

Основы файловой системы

На базовом уровне, файловая система существует для управления данными на носителях информации. Функции, общие для большинства файловых систем, включают в себя:
  • Создание файлов и каталогов.
  • Открытие, чтение, запись, удаление и переименование файлов.
  • Чтение, запись и обновление метаданных или атрибутов файла.
  • Дополнительные возможности включают в себя символические ссылки, списки управления доступом, а также распределение памяти.
Для более детального обзора многочисленных файловых систем, обратитесь к статье От BFS к ZFS: прошлое, настоящее и будущее файловых систем. Для углубленного изучения HPFS, NTFS, EXT2, XFS circa 2000, обратитесь к 3 главе Practical File System Design.

Следующие термины являются общими в обсуждении файловых систем, поэтому желательно взглянуть на список и ознакомиться с терминами, о которых Вы еще не знаете:

Диск: устройство хранения информации определенного размера. Минимальной адресуемой областью данных на жёстком диске является сектор. Размер сектора традиционно равен 512 байт, но он теперь приближается к 4096 байтам для более новых дисков.

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

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

Раздел: подмножество всех блоков на диске. Диск может иметь несколько разделов.

Логический диск: часть долговременной памяти компьютера, рассматриваемая как единое целое для удобства работы.

Суперблок: в суперблоке определяется размер файловой системы, максимальное число файлов в разделе, объем свободного пространства - и содержится информация о том, где искать незанятые участки.

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

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

I-node: место, где файловая система хранит все необходимые метаданные о файле. I-node также обеспечивает подключение к содержимому файла и любым другим данным, связанных с файлом. Термин «i-node» (который мы будем использовать в этой статье) является историческим и возник в Unix. I-node также известен как блок управления файлом (FCB) или файл записи.

Атрибут: имя и значение, связанное с именем. Значение может иметь определенный тип (строка, целое и т.д.), или это могут быть просто произвольные данные.

Особенности BFS

Теперь, когда мы узнали некоторые основные термины, давайте посмотрим на некоторые особенности, которые делают BFS уникальной.

Во-первых, BFS поддерживает 64-битную адресацию, что означает как бы не был велик объем дисков в будущем, Вы сможете отформатировать весь диск в BFS. Вы можете создавать разделы более 8 экзабайт и, в зависимости от размера блока, создавать файлы размером больше 30GB.

Одной из наиболее важных и разрекламированных особенностей BFS является поддержка расширенных атрибутов. Например важность атрибутов иллюстрируется на примере mp3 файлов. Информационные поля, важные для файла mp3, были бы: название песни, группа, альбом, дата выпуска, битрейт, продолжительность, количество прослушиваний песни. Если Вы хотите связать эту информацию с каждым файлом mp3, используя обычную файловую систему, Вам, возможно, придется создать Вашу собственную базу данных, чтобы поддерживать поиск, создание, обновление, или удаление этих атрибутов, поскольку Ваша коллекция музыки растет и изменяется.С BFS, напротив, эти атрибуты, или любые другие атрибуты, могут быть добавлены к файловой системе непосредственно.
Это означает, что программа для редактирования или проигрывания mp3 не должна создавать или поддерживать базу данных, потому что файловая система обработает эти функции для Вас. BFS ассоциирование атрибутов файлов или в рамках программного управления или из командной строки. Атрибуты могут быть найдены и отсортированы файловой системой в качестве расширения к любому приложению. Как это делается, будет обсуждаться в дальнейшем.

BFS поддерживает возможность создавать постоянный или «живой» запрос, который отслеживает изменения файлов. Это запрос, который подключается к файловой системе, проверяя файлы соответствующие критериям поиска. В Haiku, эти запросы легко создаются и расходуют удивительно небольшой объем системных ресурсов.

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

BFS использует кодировку символов UTF-8 для имен каталогов и файлов. Это означает, что можно использовать практически любой язык, в естественном виде, в Haiku. Без лишних усилий можно использовать имена файлов на китайском, с немецкими символами умляуты или использовать рукописный арабский язык.

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

Архитектура BFS

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

I-nodes: как и в большинстве файловых системах Unix подобных ОС, BFS использует структуру данных для отслеживания дисковых ассигнований. Структураbfs_inode показана ниже. I-node обрабатывает основные метаданные файла включая время создания файла, владельца, размер файла, монопольного использования группы, где хранятся данные файла на диске, и т.д. BFS не обновляет размер файла, пока файл не закрыт. При тестировании было установлено, что это дает существенный выигрыш в производительности. Вновь используется магическое число в bfs_inode для проверки корректности и восстановления при ошибках. Магические числа одинаковы для BeOS и Haiku для совместимости, но различны с реализацией их в SkyOS. UID, GID и mode используется для соответствия стандарту POSIX.

Data_streams: структура i-node содержит основные атрибуты файла, но не актуальные данные самого файла. Это сделано через структуру компонента данных. Компонент данных определяется в data_stream. Структура data_stream отображает данные от физического диска до API потока файла. Доступ с использованием data_streams оптимизирован для пропускной способности, минует системый кэш, и использует DMA (прямой доступ к памяти) в и из использованной памяти. В бенчмарках, BFS в состоянии достигнуть высокой пропускной способности, которая приближается к пиковым дисковым скоростям.

Функции базы данных, использование расширенных атрибутов

Как уже упоминалось ранее, обработка атрибутов является важной функцией файловой системы. Mac HFS первая файловая система, которая стала широко использовать атрибуты файлов для поддержки GUI. Учтите, что оконные ОС должны сохранять и управлять многими атрибутам графического интерфейса, такими как размер фрейма, расположение, цвет, текст и т.д., и нуждается в оптимизации для быстрого отклика.

BFS поддерживает расширенные атрибуты, в виде ключ/значение, ассоциаций файлов. Ключи имеют фиксированный тип и могут быть добавлены в любое время. Возможные типы: string, time, double, float, int, boolean, raw, и image. Если ключ индексирован, основной поиск сильно оптимизирован. Следующие команды нужны для управления расширенными атрибутами файла.
  • addattr key value filename: добавляет пару ключ/значение в указанный файл.
  • catattr key filename: отображает значение указанного поля.
  • listattr filename: перечисляет связанные атрибуты файла, их типы, и их размеры, в байтах.
  • rmattr key filename: удаляет атрибут из указанного файла.
Новые поля создаются на глобальном уровне с mkindex. Например:
  • mkindex --type=indextype index: создает новый индекс типа long, в текущем томе.
  • reindex sourcefile filename: добавляет ключ файла к индексу, если индекс создан после атрибутов файлов.
  • rmindex index: удаляет атрибут из текущего тома, делая его недоступным для использования.
  • lsindex: список всех атрибутов.
В Haiku доступ к атрибутам файлов поддерживается в графическом режиме с помощью Tracker, а также с использованием «горячих» клавиш. Любой графический объект в Haiku имеет набор атрибутов _trk/pinfo_le задающих позицию иконки файла. BEOS:TYPE содержит прикладную ассоциацию для файла. Больше информации об использовании атрибутов файла можно найти здесь.

Дополнительная информация и примеры использования атрибутов файлов расположена здесь и здесь.

Поиск с помощью Query

Query - инструмент командой строки, используемых для поиска соответствующих атрибутов. Это удобнее чем утилита «find» в Unix.

Вот некоторые примеры синтаксиса запроса:

query "((name="**")&&(BEOS:TYPE=="audio/x-wav"))" - finds all files with MIME type of "wav". Useful if you have wav files that are missing the .wav extension.

query "(last_modified >= %yesterday%)" - finds files older than yesterday

Вывод от запроса может использоваться со средствами создания сценариев из командной строки следующим образом:

touch 'query ((last_modified< %yesterday%)&&(BEOS:TYPE=="audio/mpeg"))'

Это обновит last_modifed у всех mp3 файлов, с last_modifed старше вчерашнего.

Дополнительная информация относительно создания сценария с запросом предоставлена здесь.

Использование атрибутов приложениями

Haiku Mail Kit пример приложения, которое активно использует атрибуты. Haiku mail не имеет собственной базы данных для хранения и управления электронными сообщениями. Вместо этого оно сохраняет каждое электронное сообщение непосредственно в файловую систему BFS и использует больше 15 специфичных для электронной почты атрибутов для поиска и сортировки. Можете ли вы представить себе суммарный объем сообщений электронной почты в 8 экзабайт? Haiku делает это теоретически возможным.

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

Оптимизация поисковых атрибутов

Так как каждый файл на BFS потенциально может иметь множество дополнительных атрибутов, и потенциально может быть сотни тысяч файлов, существует острая необходимость в оптимизации доступа к атрибутам. В BFS, каждый индекс осуществлен в виде структуры данных B+tree. B+tree сбалансирован, древовидная сортировка структуры данных обеспечивает очень быстрый поиск и хорошую масштабируемость. Не удивительно, что это также используется для управления структурами каталогов и широко применяется в других файловых системах, к примеру ntfs. BFS индексы оптимизированы для поиска в таком виде:

query "(name=="temp")"  or query "(name >"111")"

Индексы BFS не оптимизированы для регулярных выражений вида:

query "(name==[aA][bB][cC])"

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

Запросы, которые используют регулярные выражения, но начинаются с фиксированного выражения, оптимизированы в Haiku, например запрос "(name==temp[1234])" будет работать быстрее чем запрос "(name==[tT]emp[1234])".

Журнал

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

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

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

Рассмотрим пример работы журнала. Предположим что пользователь создает новый файл и сохраняет его. Данные должны быть сохранены на диск, также должна быть сохранена новая директория с правильными метаданными. До выполнения этих дисковых операций, BFS запирает не записанные блоки в оперативную память и ведет записи в журнал файловой системы для каждого блока, который должен быть записан. После того как каждый блок успешно записывается на диск, журнал помечает запись как выполненную. Если система будет перезагружена прежде, чем блоки будут успешно сохранены, в журнале будут помечены не выполненные операции. При рестарте системы, она проверяет журнал на наличие невыполненных операций. Эти записи могут быть “переиграны” для успешного выполнения операции или может быть выполнен “откат” и операция прервется. Так или иначе, но файловая система остается в согласованном состоянии, где структура каталогов и метаданных точного соответствует данным файла.

В BFS журнал регистрирует любые изменения произведенные в каталоге, в блоке bitmap, i-node и расширенных атрибутах. Таким образом ведение журнала защищает файловую систему, но не обеспечивает возможности восстановления файлов как избыточный массив дисков или RAID.

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

Усовершенствования Haiku BFS в сравнении с BeOS

Версия Haiku BFS имеет ряд улучшений по сравнению с оригинальной реализацией BeOS BFS. B+tree более надежен. Haiku BFS использует кэш данных файла, в дополнении к кэшу блоков. Это привело к десятикратному увеличению скорости. POSIX atime file был убран из BeOS BFS для увеличения производительности. Haiku BFS включает оптимизированный запрос для гибридных регулярных выражений, которое позволяет смешивать статическую строку с регулярным выражением. Новые инструменты bfsinfo, bfswhich, chkindex, и recover были добавлены в Haiku BFS. Для улучшения индексации расширенных атрибутов добавлена команда reindex.

Короткое интервью с ведущим разработчиком BeOS, который работал над BFS.
(Он попросил не использовать его имени, чтобы выполнить пожелания своего нынешнего работодателя)

Как много уходит времени на написание и отладку кода от концепции до релиза?

Десять или одиннадцать месяцев. В написании кода, который обрабатывал текст в виде косвенных блоков в файл.

Какие инструменты Вы используете для разработки и отладки BFS?

Emacs, make, и gcc.

Что было самой большой проблемой при разработке BFS?

Пытаться сделать за такой короткий срок поддержку всех функций, которые мы хотели.

Повлияла ли BFS на дизайн последующих файловых систем?

Вряд ли.

Что на сегодня представляет наибольший интерес в файловых системах?

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

По Вашему мнению, в каком фильме, из жанра научной фантастики, показан самый лучший компьютер?

Хммм..., не уверен. Star Trek? Их компьютеры делают все и имеют интерфейс мультитач. И при обращении с ними не нужно никакого шаманства.

Аксель Дёрфлер (Axel Drfler), разработчик Open Source BFS

Был ли у Вас опыт работы с файловыми системами до BFS?

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

Что было самым трудным в переписывании BFS?

Обеспечение правильной реализации B+tree, используемая в оригинальной BFS (как указано в книге Доминика) была очень неустойчивой и неэффективной.

Что было самым простым?

Реализация BFS “только для чтения” (read-only) поскольку я мог использовать большое количество кода, который я писал для восстановления данных.

Обсуждали ли Вы с Домиником BFS?

Да, но не очень подробно его недостатки, а мою реализацию.

Что бы вы изменили в BFS 2.0?

Большую часть.

Как долго Вы занимались кодингом?

Честно, я не помню. Я думаю, что только изучение заняло приблизительно недели две или около того, в то время как на написание ушло гораздо больше времени, и еще больше времени на совместимость BFS в BeOS

Какие уроки Вы получили при переписывании BFS?

При написании файловой системы, гораздо проще иметь рабочую VFS.

И наконец, какой компьютер используете сейчас для разработки?

В зависимости от того, где я, это или ThinkPad T60, или двухгодичный Core 2 Quad со встроенной графикой от Intel.

Благодарности

Эта статья, в значительной степени, опирается на книгу Practical File System Design with the Be File System. Это редкость, что файловая система описана в таких деталях и в удобочитаемом стиле. Благодарность Аксель Дёрфлер (Axel Drfler) в проверке фактов.

Ссылки

Practical File System Design with the Be File System
Haiku File System Modules
BFS File System Construction Kit
From BFS to ZFS
NTFS
Haiku Attributes
The BeOS Bible
Scot Hacker
File Systems in Linux
EXT2 File System

Об авторе

Эндрю Хадсон независимый технический менеджер проектов во Флориде, США. В свое свободное время (которого у него много) он любит изучать пещеры и заниматься восстановлением антикварных автомобилей.

Комментариев нет:

Отправить комментарий