Файловая система BSD: История и особенности реализации.

Введение

Файловая система, используемая многими Unix и Unix-подобными операционными системами, реализация файловой системы в некоторых операционных системах Unix и BSD. Целью BSD FFS является попытка локализовать связанные блоки данных и метаданные в одной группе цилиндров и, в идеале, всё содержимое каталога (как данные, так и метаданные всех файлов) в одной или соседних группах цилиндров, тем самым уменьшая фрагментацию, вызванную рассеиванием содержимого каталога по всему диску. Некоторые параметры производительности в суперблоке включали количество дорожек и секторов, скорость вращения диска, скорость движения головок и выравнивание секторов между дорожками. В полностью оптимизированной системе головка могла перемещаться между близкими дорожками для чтения разбросанных секторов с чередующихся дорожек, ожидая вращения диска. По мере увеличения размеров дисков оптимизация на уровне секторов устарела (особенно на дисках с линейной нумерацией секторов и переменным количеством секторов на дорожку). С увеличением размеров дисков и файлов фрагментированные чтения стали более серьёзной проблемой. Для борьбы с этим BSD первоначально увеличил размер блока файловой системы с одного сектора до 1 КБ в 4.0 BSD; а в FFS – увеличил размер блока файловой системы с 1 КБ до 8 КБ. Это имеет несколько последствий. Вероятность непрерывного расположения секторов файла значительно возрастает. Уменьшается объём служебной информации для перечисления блоков файла, при этом увеличивается количество байтов, представимых заданным числом блоков. Также становятся возможными диски большего размера, поскольку максимальное количество блоков ограничено фиксированной разрядностью номера блока. Однако при больших размерах блоков диски с множеством мелких файлов будут неэффективно использовать пространство, поскольку каждый файл должен занимать как минимум один блок. В связи с этим BSD добавил фрагментацию на уровне блоков, также называемую субалокацией блоков, объединением хвостов или упаковкой хвостов, когда последний частичный блок данных из нескольких файлов может быть сохранён в одном "фрагментном" блоке вместо нескольких почти пустых блоков. Работа над Berkeley FFS была широко принята другими производителями Unix, а семейство файловых систем, произошедших от неё, коллективно известно как UFS.

File system used by many Unix and Unix like operating systems
the file system implementation in some Unix and BSD operating systems

The intent of BSD FFS is to try to localize associated data blocks and metadata in the same cylinder group and, ideally, all of the contents of a directory (both data and metadata for all the files) in the same or nearby cylinder group, thus reducing fragmentation caused by scattering a directory's contents over a whole disk. Some of the performance parameters in the superblock included number of tracks and sectors, disk rotation speed, head speed, and alignment of the sectors between tracks. In a fully optimized system, the head could be moved between close tracks to read scattered sectors from alternating tracks while waiting for the platter to spin around. As disks grew larger and larger, sector level optimization became obsolete (especially with disks that used linear sector numbering and variable sectors per track). With larger disks and larger files, fragmented reads became more of a problem. To combat this, BSD originally increased the filesystem block size from one sector to 1 K in 4.0 BSD; and, in FFS, increased the filesystem block size from 1 K to 8 K. This has several effects. The chance of a file's sectors being contiguous is much greater. The amount of overhead to list the file's blocks is reduced, while the number of bytes representable by any given number of blocks is increased. Larger disk sizes are also possible, since the maximum number of blocks is limited by a fixed bit width block number. However, with larger block sizes, disks with many small files will waste space, since each file must occupy at least one block. Because of this, BSD added block level fragmentation, also called block suballocation, tail merging, or tail packing, where the last partial block of data from several files may be stored in a single "fragment" block instead of multiple mostly empty blocks. The work on Berkeley FFS was widely adopted by other Unix vendors, and the family of filesystems derived from it are collectively known as UFS.

Реализация

Продавцы некоторых проприетарных систем Unix, таких как SunOS / Solaris, System V Release 4, HP UX и Tru64 UNIX, а также открытых систем Unix, таких как illumos, приняли UFS. Большинство из них адаптировали UFS к собственным нуждам, добавив проприетарные расширения, которые могут быть не распознаны другими версиями Unix. Многие продолжали использовать оригинальный размер блока и ширину полей данных, как в оригинальном UFS, поэтому некоторая степень совместимости при чтении сохраняется между платформами. Совместимость между реализациями в целом оставляет желать лучшего. Начиная с Solaris 7, Sun Microsystems включила UFS Logging, которая внедрила журналирование файловой системы в UFS, и эта функция до сих пор доступна в текущих версиях Solaris и illumos. Solaris UFS также имеет расширения для больших файлов и дисков, а также другие возможности. В 4.4BSD и BSD Unix системах, производных от неё, таких как FreeBSD, NetBSD, OpenBSD и DragonFlyBSD, реализация UFS1 и UFS2 разделена на два уровня: верхний уровень, обеспечивающий структуру каталогов и поддерживающий метаданные (права доступа, владение и т. д.) в структуре inode, и нижние уровни, предоставляющие контейнеры данных, реализованные как inodes. Это было сделано для поддержки как традиционной FFS, так и LFS-системы файлов с общим кодом для общих функций. Верхний уровень называется "UFS", а нижние уровни называются "FFS" и "LFS". В некоторых из этих систем термин "FFS" используется для обозначения комбинации нижнего уровня FFS и верхнего уровня UFS, а термин "LFS" — для обозначения комбинации нижнего уровня LFS и верхнего уровня UFS. Кирк Маккусик реализовал перераспределение блоков — технику, которая переупорядочивает блоки в файловой системе непосредственно перед записью, чтобы уменьшить фрагментацию и контролировать старение файловой системы. Он также реализовал мягкие обновления — механизм, который поддерживает целостность файловой системы, не ограничивая производительность, как это делал традиционный режим синхронизации. Это имеет побочный эффект снижения необходимости проверки файловой системы после сбоя или отключения питания. Для устранения оставшихся проблем после сбоя была введена фоновая утилита fsck. В UFS2 Кирк Маккусик и Пол Хеннинг Камп расширили слои FreeBSD FFS и UFS, чтобы добавить 64-битные указатели блоков (позволяющие создавать тома объёмом до 8 зебибайт), блоки переменного размера (аналогичные экстентам), расширенные поля флагов, дополнительные метки времени создания, расширенную поддержку атрибутов и POSIX ACL. UFS2 стала поддерживаемой версией UFS, начиная с FreeBSD 5.0. FreeBSD также представила мягкие обновления и возможность создания снимков файловой системы как для UFS1, так и для UFS2. Эти функции были портированы в NetBSD, но в конечном итоге мягкие обновления (называемые мягкими зависимостями в NetBSD) были удалены из NetBSD 6.0 в пользу менее сложного механизма журналирования файловой системы под названием WAPBL (также называемого журналированием), который был добавлен в FFS в NetBSD 5.0. OpenBSD поддерживает мягкие обновления с версии 2.9 и имеет поддержку UFS2 (FFS2) (без ACL) с версии 4.2. OpenBSD теперь сделала UFS2 версией UFS по умолчанию, и она будет включена в релиз 6.7. Начиная с FreeBSD 7.0, UFS также поддерживает журналирование файловой системы с использованием провайдера GEOM gjournal. FreeBSD 9.0 добавляет поддержку легковесного журналирования поверх мягких обновлений (SU+J), что значительно снижает необходимость в фоновом fsck и поддерживает NFSv4 ACL. FreeBSD, NetBSD, OpenBSD и DragonFly BSD также включают систему Dirhash, разработанную Яном Доусом. Эта система поддерживает хэш-таблицу в памяти для ускорения поиска в каталогах. Dirhash решает ряд проблем с производительностью, связанных с большими каталогами в UFS. Linux включает реализацию UFS для обеспечения двоичной совместимости на уровне чтения с другими Unix-системами, но поскольку нет стандартной реализации для расширений поставщиков UFS, Linux не имеет полной поддержки записи в UFS. Нативная файловая система Linux ext2 была вдохновлена UFS1, но не поддерживает фрагменты, и нет планов по реализации мягких обновлений. (В некоторых системах, производных от 4.4BSD, слой UFS может использовать слой ext2 в качестве контейнерного слоя, как и FFS и LFS.) NeXTStep, производная от BSD, также использовала версию UFS. В Mac OS X от Apple она была доступна как альтернатива HFS+, их проприетарной файловой системе. Однако, начиная с Mac OS X Leopard, установка Mac OS X на том, отформатированный в UFS, стала невозможной. Кроме того, нельзя обновить старые версии Mac OS X, установленные на томах, отформатированных в UFS, до Leopard; обновление требует переформатирования загрузочного тома. В Mac OS X существовало ограничение на размер файла в 4 ГБ для дисков, отформатированных в UFS. Начиная с Mac OS X Lion, поддержка UFS была полностью прекращена.

Vendors of some proprietary Unix systems, such as SunOS / Solaris, System V Release 4, HP UX, and Tru64 UNIX, and open Unix derived systems like illumos, have adopted UFS. Most of them adapted UFS to their own uses, adding proprietary extensions that may not be recognized by other vendors' versions of Unix. Many have continued to use the original block size and data field widths as the original UFS, so some degree of read compatibility remains across platforms. Compatibility between implementations as a whole is spotty at best. As of Solaris 7, Sun Microsystems included UFS Logging, which brought filesystem journaling to UFS, which is still available in current versions of Solaris and illumos. Solaris UFS also has extensions for large files and large disks and other features. In 4.4BSD and BSD Unix systems derived from it, such as FreeBSD, NetBSD, OpenBSD, and DragonFlyBSD, the implementation of UFS1 and UFS2 is split into two layers: an upper layer that provides the directory structure and supports metadata (permissions, ownership, etc.) in the inode structure, and lower layers that provide data containers implemented as inodes. This was done to support both the traditional FFS and the LFS log structured file system with shared code for common functions. The upper layer is called "UFS", and the lower layers are called "FFS" and "LFS". In some of those systems, the term "FFS" is used for the combination of the FFS lower layer and the UFS upper layer, and the term "LFS" is used for the combination of the LFS lower layer and the UFS upper layer. Kirk McKusick implemented block reallocation, a technique that reorders the blocks in the file system just before the writes are done to reduce fragmentation and control file system aging. He also implemented soft updates, a mechanism that maintains the file system consistency without limiting the performance in the way the traditional sync mode did. This has the side effect of reducing the requirement of file system checking after a crash or power failure. To overcome the remaining issues after a failure, a background fsck utility was introduced. In UFS2, Kirk McKusick and Poul Henning Kamp extended the FreeBSD FFS and UFS layers to add 64 bit block pointers (allowing volumes to grow up to 8 zebibytes), variable sized blocks (similar to extents), extended flag fields, additional 'birthtime' stamps, extended attribute support and POSIX1. e ACLs. UFS2 became the supported UFS version starting with FreeBSD 5.0. FreeBSD also introduced soft updates and the ability to make file system snapshots for both UFS1 and UFS2. These have since been ported to NetBSD, but eventually soft updates (called soft dependencies in NetBSD) was removed from NetBSD 6.0 in favor of the less complex file system journaling mechanism called WAPBL (also referred as logging), which was added to FFS in NetBSD 5.0. OpenBSD has supported soft updates since version 2.9 and has had UFS2 (FFS2) support (no ACLs) since version 4.2. OpenBSD has now made UFS2 the default UFS version and will be included with the 6.7 release. Since FreeBSD 7.0, UFS also supports filesystem journaling using the gjournal GEOM provider. FreeBSD 9.0 adds support for lightweight journaling on top of soft updates (SU+J), which greatly reduces the need for background fsck, and NFSv4 ACLs. FreeBSD, NetBSD, OpenBSD, and DragonFly BSD also include the Dirhash system, developed by Ian Dowse. This system maintains an in memory hash table to speed up directory lookups. Dirhash alleviates a number of performance problems associated with large directories in UFS. Linux includes a UFS implementation for binary compatibility at the read level with other Unixes, but since there is no standard implementation for the vendor extensions to UFS, Linux does not have full support for writing to UFS. The native Linux ext2 filesystem was inspired by UFS1 but does not support fragments and there are no plans to implement soft updates. (In some 4.4BSD derived systems, the UFS layer can use an ext2 layer as a container layer, just as it can use FFS and LFS.) NeXTStep, which was BSD derived, also used a version of UFS. In Apple's Mac OS X, it was available as an alternative to HFS+, their proprietary filesystem. However, as of Mac OS X Leopard, it was no longer possible to install Mac OS X on a UFS formatted volume. In addition, one cannot upgrade older versions of Mac OS X installed on UFS formatted volumes to Leopard; upgrading requires reformatting the startup volume. There was a 4 GB file limit for disks formatted as UFS in Mac OS X. As of Mac OS X Lion, UFS support was completely dropped.