Fast File System

Fast File System (FFS, Быстрая файловая система) — это файловая система, разработанная в 1980-х годах для операционной системы Unix в Калифорнийском университете в Беркли. Она представляет собой усовершенствованную версию оригинальной файловой системы Unix (UFS) и стала основой для многих современных файловых систем, включая UFS2, ext2, ext3 и ext4. Основное нововведение FFS заключалось в оптимизации размещения данных на диске для повышения производительности при последовательном и случайном доступе, а также в поддержке более крупных дисков и длинных имён файлов.

История

Предпосылки создания

Оригинальная файловая система Unix, разработанная в начале 1970-х годов в Bell Labs, была простой и эффективной для своего времени, но имела серьёзные ограничения. Она поддерживала только диски объёмом до 64 мегабайт, имена файлов длиной до 14 символов и неэффективно использовала дисковое пространство. К началу 1980-х годов, с появлением более крупных и быстрых дисков, эти ограничения стали критическими. Кроме того, производительность оригинальной системы страдала из-за фрагментации данных: файлы часто разбивались на множество мелких фрагментов, разбросанных по диску, что замедляло чтение и запись.

Разработка в Беркли

В 1983 году группа исследователей из Калифорнийского университета в Беркли, работавшая над проектом Berkeley Software Distribution (BSD) Unix, начала разработку новой файловой системы. Руководителем проекта был Маршалл Кирк МакКузик, а ключевыми участниками — Джон Остерхаут и Джойс Вуд. Целью было создание системы, которая могла бы эффективно работать с дисками объёмом до 1 гигабайта, поддерживать длинные имена файлов (до 255 символов) и обеспечивать высокую скорость доступа за счёт оптимизации размещения данных.

Релиз и влияние

Первая версия FFS была включена в состав 4.2BSD, выпущенного в 1983 году. Она быстро стала стандартной файловой системой для всех производных BSD, включая SunOS, Ultrix и NeXTSTEP. В 1990-х годах идеи FFS были адаптированы для Linux (файловая система ext2), а затем и для других операционных систем. В 2001 году в OpenBSD была представлена улучшенная версия FFS — UFS2, которая поддерживала диски объёмом более 1 терабайта и расширенные атрибуты файлов.

Архитектура и устройство

Структура диска

FFS делит диск на логические блоки, называемые фрагментами и блоками. Блок — это минимальная единица выделения пространства для файла, обычно размером 4 или 8 килобайт. Фрагмент — это часть блока (например, 1/8), которая используется для хранения концов файлов, чтобы избежать потерь пространства при записи файлов, размер которых не кратен размеру блока. Диск разбивается на группы цилиндров (cylinder groups), каждая из которых содержит:

• Суперблок (superblock) — копия метаданных файловой системы, включая размер блока, количество групп цилиндров и список свободных блоков.
• Карту битов (bitmap) — таблицу, указывающую, какие блоки и фрагменты заняты, а какие свободны.
• Таблицу инодов (inode table) — массив инодов, каждый из которых описывает файл или каталог.
• Область данных — непосредственно блоки, в которых хранятся содержимое файлов.

Иноды

Каждый файл или каталог в FFS представлен инодом (inode) — структурой данных, содержащей метаинформацию о файле:

• Тип файла (обычный, каталог, символьная ссылка, устройство).
• Права доступа (владелец, группа, режим).
• Временные метки (время создания, последнего доступа, последней модификации).
• Размер файла.
• Количество ссылок (жёстких ссылок).
• Указатели на блоки данных (до 12 прямых указателей, один косвенный, один двойной косвенный и один тройной косвенный).

Размещение данных

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

Классификация

Версии FFS

• FFS (Original) — версия, включённая в 4.2BSD. Поддерживает диски до 1 ГБ, имена файлов до 255 символов, размер блока 4 или 8 КБ.
• UFS (Unix File System) — обобщённое название для FFS и её производных. В разных Unix-системах (Solaris, HP-UX) UFS может иметь свои особенности.
• UFS2 — улучшенная версия, представленная в OpenBSD 2001 года. Поддерживает диски до 2^64 байт, расширенные атрибуты, мягкие обновления (soft updates) для повышения надёжности.
• FFS2 — экспериментальная версия, разработанная в 1990-х годах в Калифорнийском университете в Беркли, включающая поддержку журналирования.

Производные файловые системы

• ext2 — файловая система для Linux, созданная в 1993 году Реми Кардом. Основана на архитектуре FFS, но не включает фрагментацию.
• ext3 — расширение ext2 с журналированием.
• ext4 — дальнейшее развитие ext3 с поддержкой больших дисков и экстентов.
• JFS — файловая система IBM, также использующая идеи FFS.

Применение

Операционные системы

FFS и её производные используются в большинстве Unix-подобных операционных систем:

• BSD-системы (FreeBSD, OpenBSD, NetBSD) — FFS/UFS2 является основной файловой системой.
• Linux — ext2/ext3/ext4, хотя и не являются прямыми копиями FFS, унаследовали её архитектуру.
• macOS — до перехода на APFS в 2017 году использовала HFS+, которая также основана на идеях FFS.
• Solaris — UFS является одной из поддерживаемых файловых систем.

Встраиваемые системы

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

Критика и ограничения

Производительность

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

Надёжность

FFS не является журналируемой файловой системой, что делает её уязвимой к сбоям питания. При внезапном отключении питания может возникнуть повреждение метаданных, требующее длительной проверки (fsck). В UFS2 и некоторых версиях FFS добавлено журналирование, но оно не является обязательным.

Поддержка современных дисков

Оригинальная FFS не поддерживает диски объёмом более 1 ТБ без специальных настроек. UFS2 решает эту проблему, но всё же уступает более современным файловым системам, таким как ZFS или Btrfs, в масштабируемости и функциях (например, сжатие, дедупликация, снимки).

Интересные факты

• Название «Fast File System» было выбрано, чтобы подчеркнуть основное преимущество перед оригинальной файловой системой Unix. Однако в документации BSD она часто называется просто «Unix File System».
• Разработчики FFS впервые применили концепцию «групп цилиндров», которая позже стала стандартом для многих файловых систем.
• В 1984 году за создание FFS Маршалл Кирк МакКузик получил премию ACM Software System Award.
• FFS оказала влияние на разработку файловых систем для Windows (NTFS) и macOS (HFS+), хотя они не являются прямыми копиями.

Источники

• Marshall Kirk McKusick, William N. Joy, Samuel J. Leffler, Robert S. Fabry. «A Fast File System for UNIX» (1984). ACM Transactions on Computer Systems.
• Marshall Kirk McKusick, George V. Neville-Neil. «The Design and Implementation of the FreeBSD Operating System» (2004). Addison-Wesley.
• «Unix File System» — документация FreeBSD.
• «UFS2» — документация OpenBSD.
• «Ext2 — файловая система для Linux» — документация ядра Linux.