03 Февраля 1999

Немалую тему я зацепил. Получив пару писем, понял, что, говоря о развитии операционных систем, нельзя не говорить и про файловые системы, так как иначе вопрос с Extended Attributes несколько повисает.

Итак, что происходило с файловыми системами.

ДОСовский FAT был рожден как файловая система для дискет. Спроектированный весьма стереотипно и незатейливо, он и на дискетах-то не являл собой идеала. К примеру, FAT  размещен с краю диска, тогда как опытные разработчики при проектировании файловых систем ключевые структуры данных размещают в середине. Почему? А потому как к середине добираться от любого места диска в среднем вдвое ближе. Далее, блоки, из которых состоит файл в FAT, были перечислены простым последовательным списком. Это значит, что для нахождения 50-го блока нужно сделать по списку 50 шагов, что, в зависимости от того, "как разлеглась фишка" дает от одного до пятидесяти (!!) считываний с диска.

Для сравнения, файловая система Юникса тех времен, хоть и сделана была изрядно "наколенным" способом, все же писалась людьми, знакомыми с классической программистской литературой и приемами программирования. Списки блоков в ней уже тогда были сделаны в виде дерева, что кардинально сокращает время на поиск. То есть не в разы, а логарифмически. Проще говоря, файловая система Юникса гарантировала нахождение номера блока файла за одно обращение для файлов до 13 блоков в размере, за два - для файлов до 128*13 = 1664, за три для 128*128*13 = 212992, и так далее.

Отметим, что FAT создавался на продажу, а файловая система Юникса - по приколу. Чем объяснить такую беспечность авторов первого - я не знаю.

Далее пойдем немного по Юниксовой ветке. Традиционная (от версии 7 Юникса) Юниксовская ФС тоже была не подарок, если честно. Но все же лучше, лучше. К примеру, в ней была реализована концепция "файл - отдельно, имя - отдельно". То есть имя не являлось атрибутом файла! Файл мог иметь множество ссылающихся на него имен, а мог и вообще не иметь имени. :-) Для этого файл достаточно было создать, и не закрывая удалить. При этом удалялось имя, а сам файл, так как на него ссылался открывший его процесс, существовал до тех пор, пока не закрыт. Напоминает Гаррисоновское "мы существуем, пока ты нас помнишь", но прочь фантастику - все реально. :-) Для создания временных файлов это было (и есть) крайне удобно.

С другой стороны, Юниксовская ФС, как и FAT, не уделяла никакого внимания фрагментации дискового пространства. При увеличении файла блоки ему выделялись где бог послал, и результаты были плачевны.

Интересно, что у FAT были все средства для борьбы с этой проблемой, а именно - собственно FAT, в котором относительно несложно выполнять операции поиска существенных свободных кусков дискового пространства. Это же таблица - беги по ней, да считай размеры пустот. Элементарно! Юниксу такое не светило. Пул свободных блоков в нем представлял собой неупорядоченное дерево, и выкопать в нем два блока подряд было занятием на полдня - все пересортировать, все обыскать... ужас.

И тем не менее, к борьбе с фрагментацией первым шагнул Юникс. Была разработана концептуально новая файловая система. Свободное место в ней расписывалось битовыми картами, в которых каждый бит отвечал за свой блок на диске и говорил - свободен тот, или занят. В итоге поиск крупных залежей свободного места или ответ на вопрос "свободно ли место на диске за концом данного файла" превратились в элементарные и быстрые операции.

Более того, битовые карты было решено расположить не в кучу в одном месте, а частями разложить по всему диску, разделив его на части, преремежаемые картами. Части были названы группами цилиндров (ГЦ), а нахождение карты каждой ГЦ рядом с ней снижало время на "беготню" головок диска при работе с данной ГЦ.

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

Правда, в угоду производительности пришлось принести одну жертву. Оказалось, что при заполнении диска до 95% производительность файловой системы падает примерно вдвое, а при заполнении более 90% никакие силы не смогут бороться с фрагментированием диска. Поэтому в Юниксе лишь суперпользователь может превысить некий граничный процент заполнения диска, остальным же предписывается оставлять свободными не менее 8% диска. Впрочем, цифра эта может быть изменена при разметке файловой системы...

Структура каталогов тоже стала древообразной. Не в том смысле, что имена файлов укладываются в дерево - это-то в Юниксе было с самого начала. Теперь деревом внутри себя стал каждый отдельный каталог.

Иллюстрирую. У меня в каталоге d:\winnt\system32 - более 1000 файлов. В FAT список имен этих файлов представлял собой псевдо-файл с тысячей записей. Нетрудно догадаться, что среднее время поиска имени в нем занимало перебор пятисот записей. В новой файловой системе Юникса каталоги перестали быть просто линейными списками и стали древообразными, из-за чего поиск в них ускорился столь же круто, сколь и поиск блока по дереву вместо списка. То есть для нахождения файла даже в очень крупном каталоге требуются единицы считываний.

Еще одна победа - фрагменты блоков. Тут дело вот в чем. С точки зрения производительности, чем большего размера блоки, из которых состоит файл, тем лучше. Если выделять файлу четырехкилобайтные блоки, то производительность, как правило, будет выше, чем если выделять вдвое больше двухкилобайтных. На крайне крутой аппаратуре эффект этот может быть меньше, но файловые системы используются не только на крайне крутой аппаратуре, правда? :-) С другой стороны, чем больше эти самые блоки, тем больше потери на хвостах файлов. Если блок - 4К, то 100-байтный файл на диске будет занимать эти самые 4К, то есть примерно 3.9К вылетят в трубу. В среднем при блоке в 4К будет теряться примерно 2К на файл. Жалко? Конечно. Поэтому новая файловая система научилась выделять блоки двояко. Все кроме последнего - крупными кусками, а на хвосте "добивать" файл фрагментами блока - четвертушками или осьмушками. Для этого файловая система выполняла операцию "вам порезать?" для некоторых блоков и обрезками этими "добивала" сразу несколько файлов. Это позволило не потерять скорость и не проиграть в объеме.

Кроме того, Юникс, у которого и до того имена файлов могли иметь до 14 символов, отрастил их еще больше - до 255.

В общем, файловая система получилась знатная. Это - повод попить чаю, продолжим после рекламной паузы. :-)

Реклама

Что такое XtraViewTM Technology, что значит "угол обзора 160° по горизонтали и вертикали"? Это то, что отличает новые модели высокотехнологичных ЖК-мониторов NEC - LCD400, LCD1510, LCD2000. Презентации, цифровая обработка изображений, графические и мультимедийные приложения - лучшего ответа на этот вопрос еще никто не давал.

Ну так вот, файловую систему себе Юникс отрастил - просто на завсить соседям. Соседи поглядели-поглядели, да и... поперли ее у него. Правда, по дороге еще подлатали и кой-чего существенного добавили.

Результат стал называться HPFS, и появился в OS/2 1.X. От оригинала он отличался одним принципиальным свойством и некоторыми мелочами. Принципиальным изменением было вот что - если в юниксе файл был линейной последовательностью байт, то в HPFS с файлом стало возможно ассоциировать произвольное количество последовательностей байт. Идея эта проистекала, по всей видимости, от Макинтошевских файловых систем, где у каждого файла были data fork (то, что Юникс и ДОС, собственно, называют файлом) и resource fork - еще одна часть файла, где лежала дополнительная информация. Те же иконки... :-).

Тут надо учесть, что HPFS, по сути, это не файловая система, а целый класс файловых систем. Пользуясь базовыми правилами, можно породить прорву разных HPFS-ов, удовлетворяющих спецификации. Они даже будут частично совместимы - то есть любой драйвер HPFS сумеет с той или иной степенью успешности "сожрать" чужой вариант HPFSa. Как правило - прочесть из нее собственно данные.

Итак, спецификация HPFS гласила, что файл может иметь произвольное число "ветвей" - линейных потоков данных. Из них один является основным, то есть доступным через обычные posix open/read/write без ухищрений. Остальные - как совесть подскажет. Совесть подсказала, что вторую ветвь нужно использовать под расширенные атрибуты - некоторый аналог Mac OS resource fork. Это в стандартной HPFS. Более поздняя версия HPFS для серверов (HPFS386) использовала дополнительную ветвь под хранение прав доступа, плюс имена файлов в ней могли быть двухбайтовыми - для поддержки национальных версий OS/2, работающих с двухбайтовыми кодировками.

Ничто не мешало, в принципе, сделать и третий вариант HPFS. Случай выдался когда Microsoft стал делать NT. Вариант, правда, поимел собственное имя и стал называться NTFS, но в корне был все тем же, и даже расширенные атрибуты хранить умел. Правда, по неясной причине (уж не из ревности ли) Microsoft с мясом выдрал из NT все цивильные способы добраться до расширенных атрибутов, и теперь увидеть их можно, только если клиент под OS/2 работает с сервером под NT. Сервер их как-то умудряется поддерживать. Видимо, интерфейс есть, но засекречен. :-)

HPFS, который NTFS, получил еще одно существенное добавление - транзакционность. То есть существенную защиту от сбоев, которая гарантирует быстрое восстановление файловой системы после сбоя. Кстати, в Юниксе такие ФС тоже есть, не подумайте, что он отстал. :-)

Лишив, фактически, пользователя расширенных атрибутов, NT предложила взамен относительно легкий доступ к дополнительным "ветвям" файла, но он как-то не прижился. В отличие от расширенных атрибутов в OS/2, которые были весьма кстати и пользовались популярностью.

Справедливости ради - добраться до них можно и в NT, но настолько ненадежным и неудобным способом, что мало, кто решается им воспользоваться. Я бы, например, не решился.

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

Любопытное письмо на тему борьбы с registry. Вообще-то у меня об этом много писем, но те, что требуют обсуждения, я пока придерживаю. Спасибо всем, кто написал, я эту тему продолжу на днях.

From: Alexey Vaiman Subject: Registry. Здравствуйте, Дмитрий. Вот решение типа "волки сыты - овцы целы". Оно ПОЧТИ реализовано в NT и в мастдайках. Это hives (ульи, для пчелок). Эти hives являются просто файлами, в которых находятся куски реестра и которые отображены (mapped) на определенную ветку основного реестра. Ветка может быть только "подкорневой" (под HKEY_LOCAL_MACHINE или HKEY_USERS). Если бы МS немножко бы расстаралась, то сделала бы возможность мапить не только под корень, но и куда угодно, а также мапить не только скомпиленный реестр, но и обычные файлы вроде INI. Таким образом, мечты Ваши осуществились бы так : в каталоге приложения лежал бы INI файльчик (текстовый), который был бы замаплен в реестр, например в HKEY_LOCAL_MACHINE\Software\Far. При нескольких пользователях можно положить его в Profile. При переносе приложения методом копирования с ним уехал бы и INI (или при копировании Profile). Затем пускаем Far, он не обнаруживает своего ключа, бежит к себе в каталог (или опять в Profile), мапит INI в реестр и ра-а-адуется. Обидно, что оно ПОЧТИ реализовано. Но вот то, что "ПОЧТИ", уже все портит. С другой стороны, а на кой черт тогда вообще реестр нужен (если есть INI)? Только для CLSID, AppID, COM интерфейсов и прочей COM-чешуи? Так он для этого и был придуман изначально... Александр Корсуков Алексей Вайман

Возможно, это было бы разумным решением. Но частичным. Идеальным было бы сделать файловую систему, которая бы не требовала примочек в виде registry, а обеспечивала бы необходимую функциональность и производительность сама. Есть же вот в Be OS база данных в составе файловой системы!

Джентльмены. Я уже сожалею, что сказал, что нельзя копировать registry FAR-ом. А не Volkov Commander-ом. Я знаю и обладаю плагином для фара, который лазит по регистри, но при чем тут плагин, чорт меня побери. К FTP мне тоже плагин привинчивать? А к почтовой программе? И так далее. Файловая система хороша тем, что понимается всеми программами. А регистри плохо тем, что понимается лишь исключительными.