[Перевод] Что есть файловая система?
Вам когда-нибудь требовалось отформатировать новый жёсткий диск или USB-накопитель, и были даны варианты выбора из аббревиатур, таких как FAT, FAT32 или NTFS? Или вы однажды пытались подключить внешнее устройство, но ваша операционная система не смогла его определить? Вас иногда расстраивает, сколько времени требуется вашей операционной системе на поиск файла?
Если вы сталкивались с чем-то из вышеперечисленного или просто кликнули мышью, чтобы найти файл или приложение на своём компьютере, значит, вы на собственном опыте узнали, что такое файловая система.
Многие люди могут не использовать явную методологию организации их личных файлов на ПК (статья_что_такое_файловая_система.docx). Однако абстрактная концепция организации файлов и каталогов для любого устройства с постоянной памятью должна быть очень систематичной при чтении, записи, копировании, удалении и взаимодействии с данными. Эта задача операционной системы обычно назначается файловой системе.
В этой статье мы глубоко погрузимся в то, как современные компьютеры решают эти проблемы. Мы рассмотрим различные роли файловой системы в более широком контексте операционной системы и физических дисков, и в дополнение к тому, как файловые системы разработаны и реализованы.
▍ Постоянные данные: Файлы и каталоги
Современные операционные системы становятся всё более сложными и нуждаются в управлении различными аппаратными ресурсами, планировании процессов, виртуализации памяти и многих других задачах. Когда дело доходит до данных, многие аппаратные средства, типа кэша и ОЗУ, были разработаны для ускорения времени доступа и обеспечения того, чтобы часто используемые данные находились «рядом» с процессором. Однако после выключения компьютера останется только информация, хранящаяся на постоянных устройствах, таких как жёсткие диски (HDD) или твердотельные накопители (SSD). Таким образом, ОС должна особенно заботиться об этих устройствах и данных внутри, поскольку именно здесь пользователи будут хранить нужные им данные.
Две самые важные абстракции, разработанные за всё время для хранения — это файл и каталог. Файл — это линейный массив байтов, каждый из которых вы можете прочитать или записать. В то время как в пользовательском пространстве мы можем придумать умные имена для наших файлов, под капотом обычно находятся числовые идентификаторы для отслеживания имён файлов. Исторически сложилось так, что эта базовая структура данных часто ссылается на её индексный дескриптор inode. Интересно, что сама ОС мало что знает о внутренней структуре файла (т. е. является ли он изображением, видео или текстовым файлом); Фактически, всё, что ему нужно знать, — это как записать байты в файл для постоянного хранения и убедиться, что он сможет извлечь их позже при вызове.
Вторая основная абстракция — это каталог. На самом деле, под капотом, каталог — это просто файл, но он содержит очень специфический набор данных: список удобочитаемых имён сопоставленных с низкоуровневыми именами. На практике, это означает, что он содержит список других каталогов или файлов, которые в совокупности могут формировать дерево каталогов, в котором хранятся все файлы и каталоги.
Такая организация достаточно выразительна и масштабируема. Всё, что вам нужно, это указатель на корень дерева каталогов (это будет первый индексный дескриптор inode в системе), и оттуда вы сможете получить доступ к любым другим файлам на этом разделе диска. Эта система также позволяет создавать файлы с одинаковыми именами, если у них не один и тот же путь (т. е. они находятся в разных местах дерева файловой системы).
Технически вы можете назвать файл как угодно, но обычно принято обозначать тип файла с разделением точкой (например, .jpg в картинка.jpg), хотя и не обязательно. Некоторые операционные системы, такие как Windows, настоятельно рекомендуют использовать эти соглашения чтобы файлы открывались в соответствующем приложении, но содержимое самого файла не зависит от его расширения. Расширение — это всего лишь подсказка для операционной системы о том, как интерпретировать байты, содержащиеся в файле.
Как только у вас появятся файлы и каталоги, у вас должна быть возможность работать с ними. В контексте файловой системы это означает возможность считывать и записывать данные, управлять файлами (удалять, перемещать, копировать и т.д.) и управлять разрешениями для файлов (кто может выполнять все вышеперечисленные операции?). Как реализованы современные файловые системы, позволяющие выполнять все эти операции быстро и масштабируемым образом?
▍ Организация файловой системы
Размышляя о файловой системе обычно необходимо учитывать два аспекта. Первый — это структуры данных файловой системы. Другими словами, какие типы дисковых структур используются файловой системой для организации своих данных и метаданных? Второй аспект — это методы доступа: как процесс может открывать, читать или записывать в свои структуры?
Начнём с описания общей организации на диске элементарной файловой системы.
Первое, что вам нужно сделать, это разделить ваш диск на блоки. Обычно используемый размер блока составляет 4 КБ. Предположим, у вас очень маленький диск с объемом памяти 256 КБ. Первый шаг — разделить это пространство равномерно, используя размер вашего блока, и назначить номер каждому блоку (в нашем случае, обозначив блоки от 0 до 63):
Теперь давайте разберём эти блоки на разные регионы. Давайте отложим большую часть блоков для пользовательских данных и назовём это областью данных. В этом примере, давайте зафиксируем блоки 8–63 в качестве нашей области данных:
Если вы заметили, мы поместили область данных в последнюю часть диска, оставив первые несколько блоков для использования файловой системой в других целях. В частности, мы хотим использовать их для отслеживания информации о файлах, такой как местоположение файла в области данных, его размер, владелец и права доступа, а также прочая информация. Эта информация является ключевой частью файловой системы и называется метаданными.
Для хранения этих метаданных мы будем использовать специальную структуру данных, называемую индексным дескриптором (inode). В текущем примере давайте зададим 5 блоков в качестве indoe и назовём эту область диска таблицей inode:
Индексы inode обычно не очень большие, например 256 байт. Таким образом, блок размером 4 КБ может содержать около 16 inode, а наша простая файловая система выше содержит всего 80 inode. Это число на самом деле значительно: это означает, что максимальное количество файлов в нашей файловой системе составляет 80. С большим диском вы, безусловно, можете увеличить количество inode, напрямую переводя их в большее количество файлов в вашей файловой системе.
Осталось ещё несколько вещей для завершения нашей файловой системы. Нам нужно отслеживать, являются ли inode или блоки данных свободными или распределёнными. Эта структура распределения может быть реализована в виде двух отдельных битовых массивов, одно для inode, а другое для области данных.
Битовый массив — это очень простая структура данных: каждый бит соответствует тому, является ли объект/блок свободным (0) или используемым (1). Мы можем назначить битовый массив индекса и битовый массив области данных их собственному блоку. Хотя это излишне (блок может использоваться для отслеживания объектов размером до 32 КБ, но у нас есть только 80 inode и 56 блоков данных), это удобный и простой способ организации нашей файловой системы.
Наконец, для последнего оставшегося блока (который, по совпадению, является первым блоком на нашем диске) нам нужен суперблок. Этот суперблок является своего рода метаданными для метаданных: в блоке мы можем хранить информацию о файловой системе, такую как количество inode (80) и где находится блок inode (блок 3) и так далее. Мы также можем поместить для файловой системы некоторый идентификатор в суперблок, чтобы было понятно как интерпретировать нюансы и детали различных файловых систем (например, мы можем отметить, что эта файловая система основана на Unix, файловая система ext4 или, возможно, NTFS). Когда операционная система считывает суперблок, у неё может быть схема того, как интерпретировать различные данные на диске и получать к ним доступ.
▍ Индексный дескриптор Inode
До сих пор мы упоминали структуру данных inode в файловой системе, но ещё не объяснили, какой это важный компонент. Inode — это сокращение от index node, и это историческое имя, данное в UNIX и более ранних файловых системах. Практически все современные системы используют концепцию inode, но могут называть их по-разному (например, dnode, fnode, и т. д.).
По сути, inode — это индексируемая структура данных, то есть специфичная информация, которая позволяет вам перейти в определённое местоположение (индекс) и узнать, как интерпретировать следующий набор битов.
На конкретный inode ссылается число (i-number), и это низкоуровневое имя файла. Получив i-number, вы можете просмотреть его информацию, быстро перейдя к его местоположению. Например, из суперблока мы знаем, что область inode начинается с адреса 12 КБ.
Поскольку диск не адресуется по байтам, мы должны знать, к какому блоку обращаться, чтобы найти наш индекс. С помощью довольно простой математики мы можем вычислить идентификатор блока на основе i-number, размера каждого inode и размера блока. Впоследствии мы можем найти начало inode внутри блока и прочитать желаемую информацию.
Inode содержит практически всю необходимую информацию о файле. Например, это обычный файл или каталог? Каков его размер? Сколько блоков ему выделено? Какие разрешения выданы для доступа к файлу (т. Е. Кто является владельцем и кто может читать или записывать)? Когда файл был создан или к нему в последний раз обращались? И многие другие флаги или метаданные о файле.
Один из наиболее важных элементов информации, хранящейся в inode это указатель (или список указателей) где в области данных находятся нужные данные. Они известны как прямые указатели. Концепция хороша, но для очень больших файлов у вас могут закончиться указатели в небольшой структуре данных inode. Поэтому, многие современные системы имеют специальные косвенные указатели: вместо прямого перехода к данным файла в области данных вы можете использовать косвенный блок в области данных, чтобы увеличить количество прямых указателей для вашего файла. Таким образом, файлы могут стать намного больше, чем ограниченный набор прямых указателей, доступных в структуре данных inode.
Неудивительно, что вы можете использовать этот подход для поддержки ещё больших типов данных, используя двойные или тройные косвенные указатели. Этот тип файловой системы известен как имеющий многоуровневый индекс и позволяет файловой системе поддерживать большие файлы, например, в диапазоне гигабайт или больше. Распространённые файловые системы, такие как ext2 и ext3, используют многоуровневые системы индексирования. Более новые файловые системы, такие как ext4, имеют концепцию экстентов, которые представляют собой несколько более сложные схемы указателей.
Хотя структура данных inode очень популярна благодаря своей масштабируемости, было проведено множество исследований, чтобы понять её эффективность и степень, в которой необходимы многоуровневые индексы. Одно исследование показало кое-какие интересные измерения в файловых системах, в том числе:
• Большинство файлов на самом деле очень маленькие (2 КБ — наиболее распространённый размер)
• Средний размер файла растёт (в среднем почти на 200k)
• Большинство байтов хранится в больших файлах (несколько больших файлов занимают большую часть пространства)
• Файловые системы содержат много файлов (в среднем почти 100k)
• Файловые системы заполнены примерно наполовину (даже по мере роста дисков файловые системы остаются заполненными на ~50%)
• Каталоги, как правило, маленькие (во многих из них мало записей, 20 или меньше)
Все это указывает на универсальность и масштабируемость структуры данных inode, а также на то, как она прекрасно поддерживает большинство современных систем. Было реализовано множество оптимизаций для повышения скорости и эффективности, но основная структура за последнее время мало изменилась.
▍ Каталоги
Под капотом каталоги — это просто очень специфичный тип файлов: они содержат список записей, использующих систему сопряжения (имя записи с i-number). Номер записи, как правило — человеко-читаемое имя, а соответствующий i-number отражает его «имя» в файловой системе.
Каждый каталог обычно также содержит 2 дополнительные записи указателей помимо списка имён пользователей: одна запись — «текущий каталог», а другая — «родительский каталог». При использовании терминала командной строки вы можете «изменить каталог», введя:
cd [имя каталога]
или переместиться ближе к корню используя:
cd ..
где »…» — абстрактное имя указателя родительского каталога.
Поскольку каталоги обычно являются просто «специальными файлами», управление содержимым каталога обычно так же просто, как добавление и удаление пар внутри файла. Каталог обычно имеет свой собственный inode в линейном дереве файловой системы (как описано выше), но в некоторых современных файловых системах, таких как XFS, были предложены и использованы новые структуры данных, такие как B-trees (B-деревья).
▍ Методы доступа и оптимизации
Файловая система была бы бесполезна, если бы вы не могли читать и записывать в неё данные. Для этого шага вам требуется чётко определённая методология, позволяющая операционной системе получать доступ к байтам в области данных и интерпретировать их.
Основные операции с файлом включают открытие файла, чтение файла или запись в файл. Эти процедуры требуют огромного количества операций ввода-вывода (I/O) и обычно разбросаны по диску. Например, проход по дереву файловой системы от корневого узла к интересующему файлу требует перейти от inode к файлу каталога (потенциально мультииндексированному) и к расположению нужного файла. Если файл не существует, то требуются некоторые дополнительные операции, такие как создание записи inode и назначение требуемых разрешений.
Многие технологии, как аппаратные, так и программные, были разработаны для улучшения времени доступа и взаимодействия с хранилищем. Очень распространённой аппаратной оптимизацией является использование твердотельных накопителей, которые значительно увеличивают время доступа благодаря своим твердотельным свойствам. Жёсткие диски, с другой стороны, обычно имеют механические части (движущийся шпиндель), что означает, что существуют физические ограничения на то, как быстро вы можете «перепрыгивать» с одной части диска на другую.
Хотя твердотельные накопители обеспечивают быстрый доступ к диску, этого обычно недостаточно для ускорения чтения и записи данных. Операционная система обычно использует более быстрые, энергозависимые структуры памяти, такие как оперативная память и кэш, чтобы сделать данные «ближе» к процессору и ускорить операции. Фактически, сама операционная система обычно хранится в файловой системе, и одна из основных оптимизаций заключается в постоянном хранении общих файлов ОС, доступных только для чтения, в оперативной памяти, чтобы обеспечить быструю и эффективную работу операционной системы.
Не вдаваясь в подробности файловых операций, отметим, что для управления данными используются кое-какие интересные оптимизации. Например, при удалении файла одной из распространённых оптимизаций является простое удаление inode, указывающего на данные, и эффективная маркировка областей диска как «свободной памяти». В этом случае данные на диске физически не стираются, но доступ к ним удаляется. Чтобы полностью «удалить» файл, можно выполнить определённые операции форматирования, чтобы записать все нули (0) в удаляемые области диска.
Другой распространённой оптимизацией является перемещение данных. Как пользователи, мы можем захотеть переместить файл из одного каталога в другой в зависимости от наших личных предпочтений организации. Однако файловой системе просто необходимо изменить минимальные данные в нескольких файлах каталогов, а не фактически перемещать биты из одного места в другое. Используя концепцию inode и указателей, файловая система может очень быстро выполнить операцию «перемещения» (в пределах того же диска).
Когда дело доходит до «установки» приложений или игр, это просто означает копирование файлов в определённое место и установку глобальных переменных и флагов для их выполнения. В Windows установка обычно запрашивает каталог, а затем загружает данные для запуска приложения и помещает их в этот каталог. В установке нет ничего особенного, кроме автоматизированного механизма записи множества файлов и каталогов из внешнего источника (онлайн или физического носителя) на выбранный диск.
▍ Популярные Файловые Системы
Современные файловые системы имеют множество подробных оптимизаций, которые работают рука об руку с операционной системой для повышения производительности и предоставления различных функций (таких как безопасность или поддержка больших файлов). Некоторые из наиболее популярных файловых систем сегодня: FAT32 (для флэш-накопителей и, ранее, Windows), NTFS (для Windows) и ext4 (для Linux).
На высоком уровне все эти файловые системы имеют схожие структуры на диске, но отличаются деталями и функциями, которые они поддерживают. Например, формат FAT32 (Таблица распределения файлов) был первоначально разработан в 1977 году и использовался на заре персональных компьютеров. Он использует концепцию связанного списка для доступа к файлам и каталогам, которая, хотя проста и эффективна, может быть медленной для больших дисков. Сегодня это широко используемый формат для флэш-накопителей.
Файловая система NTFS (New Technology File System), разработанная компанией Microsoft в 1993 году, устранила многие недостатки FAT32. Она повышает производительность за счёт хранения различных дополнительных метаданных о файлах и поддерживает различные структуры для шифрования, сжатия, разреженных файлов и ведения системного журнала. NTFS всё ещё используется сегодня в Windows 10 и 11. Аналогичным образом, устройства macOS и iOS используют проприетарную файловую систему, созданную Apple, HFS+ (также известная как Mac OS расширенная) была стандартом до того, как они представили файловую систему Apple (APFS) относительно недавно в 2017 году, и она лучше оптимизирована для более быстрых носителей данных, а также для поддержки расширенных возможностей, таких как шифрование и повышенная целостность данных.
Четвёртая «расширенная файловая» система, или ext4, является четвёртой итерацией файловой системы ext, разработанной в 2008 году, и системой по умолчанию для многих дистрибутивов Linux, включая Debian и Ubuntu. Она может поддерживать файлы больших размеров (до 16 тебибайт) и использует концепцию экстентов для дальнейшего улучшения inode и метаданных файлов. Она использует систему отложенного распределения для уменьшения записи на диск и имеет множество улучшений для контрольных сумм файловой системы для целостности данных, а также поддерживается в Windows и Mac.
Каждая файловая система предоставляет свой собственный набор функций и оптимизаций и может иметь множество различий в реализации. Однако, по сути, все они выполняют одну и ту же функцию поддержки файлов и взаимодействия с данными на диске. Некоторые файловые системы оптимизированы для лучшей работы с различными операционными системами, поэтому файловая и операционная системы очень тесно переплетены.
▍ Файловые системы Нового Поколения
Одной из наиболее важных особенностей файловой системы является ее устойчивость к ошибкам. Аппаратные ошибки могут возникать по разным причинам, включая износ, случайные скачки напряжения или спады (из-за разгона процессора или других оптимизаций), случайные удары альфа-частиц (также называемые мягкими ошибками) и многие другие причины. На самом деле, аппаратные ошибки являются настолько дорогостоящей проблемой для выявления и отладки, что и Google, и Facebook опубликовали статьи о том, насколько важна устойчивость в масштабировании, особенно в центрах обработки данных.
С этой целью большинство файловых систем следующего поколения фокусируются на более высокой отказоустойчивости и более быстрой безопасности. Эти функции обходятся дорого, обычно приводя к снижению производительности, чтобы включить больше функций избыточности или безопасности в файловую систему.
Поставщики оборудования обычно включают различные механизмы защиты для своих продуктов, такие как защита ECC для оперативной памяти, опции RAID для резервирования дисков или полномасштабное резервирование процессора, такое как недавний полностью автономный чип Tesla (FSD). Однако этот дополнительный уровень защиты программного обеспечения через файловую систему не менее важен.
Корпорация Майкрософт уже много лет работает над этой проблемой в своей реализации устойчивой файловой системы (REFS). ReFS изначально была выпущена для Windows Server 2012 и предназначена для замены NTFS. REFS использует B+ деревья для всех своих структур на диске (включая метаданные и данные файлов) и использует подход, ориентированный на отказоустойчивости для реализации. Это включает контрольные суммы для всех независимо хранящихся метаданных, и политику распределения при записи. По сути, это снижает нагрузку на администраторов от необходимости периодически запускать средства проверки на ошибки, вроде CHKDSK, при использовании ReFS.
В мире с открытым исходным кодом Btrfs (произносится как «better FS» или «Butter FS») набирает обороты с аналогичными функциями ReFS. Опять же, основное внимание уделяется отказоустойчивости, свойствам самовосстановления и простоте администрирования. Она также обеспечивает лучшую масштабируемость, чем ext4, обеспечивая примерно в 16 раз большую поддержку данных.
▍ Итоги
Хотя сегодня используется множество различных файловых систем, основная цель и высокоуровневые концепции мало изменились с течением времени. Для создания файловой системы вам потребуется кое-какая базовая информация о каждом файле (метаданные) и масштабируемая структура хранения для записи и чтения из различных файлов.
Базовая реализация inode и файлов вместе образуют очень расширяемую систему, которая была доработана и изменена, чтобы предоставить нам современные файловые системы. Хотя мы можем не задумываться о файловых системах и их функциях в нашей повседневной жизни, это является истинным свидетельством их надёжности и масштабируемого дизайна, которые позволили нам наслаждаться и пользоваться нашими цифровыми данными на компьютерах, телефонах, консолях и различных других системах.
