Скрябин Иван P34092 335146
- FSFS в качестве постоянного хранилища данных и метаданных использует один файл/блочное устройство
- Внутри имеется кэш метаданных, представляющий из себя дерево файлов и каталог. Кэш данных отсутствует(однако в каком-то виде предоставлен ядром)
- По умолчанию всем файлам и каталогам владельцем устанавливается root, однако он при желании может это изменить при помощи
chown. Управление доступом на уровне файловой системы не реализовано, она лишь хранит текущую маску(которую можно изменить при помощиchmod), проверкой наличия прав занимается ядро. - FSFS позволяет создавать файлы и каталоги, со стандартным ограничением: длина имени не больше 255 символов.
- FSFS позволяет изменять размер, читать и записывать данные в файлы
- FSFS допускает многопоточный доступ. При возникновении конфликтов система остается в валидном состоянии(либо один из запросов выполняется, второй отклоняется, либо оба отклоняются)
- Операции над файловой системой реализованы таким образом, что при возникновении ошибок, они откатывают изменения и система остается в валидном состоянии.
- При непредвиденном отключении FSFS остается всегда в валидном состоянии
FSFS монтируется в /tmp/fsfs
Создание директорий
Запись и чтение файлов
Здесь находятся скрипты, для тестирования
Один из тестовых сценариев
dd if=/dev/random of=/tmp/fsfs_test_data bs=4096 count=100
dd if=/tmp/fsfs_test_data of=/tmp/fsfs/small bs=1 count=1
dd if=/tmp/fsfs_test_data of=/tmp/fsfs/small bs=1 count=10
dd if=/tmp/fsfs_test_data of=/tmp/fsfs/small bs=1 count=100
dd if=/tmp/fsfs_test_data of=/tmp/fsfs/small bs=1 count=1000
dd if=/tmp/fsfs_test_data of=/tmp/fsfs_test_cut bs=1 count=1000
cmp /tmp/fsfs/small /tmp/fsfs_test_cut
Весь файл(блочное устройство) делится на 3 зоны:
- Метаданные. Зона разбивается на равные по размеру блоки, в каждом блоке хранится одна из записей - метаданные файла, метаданные директории или расширение метаданных файла(поскольку список блоков данных может быть довольно длинным). Полная структура
type MetadataDTOBlock =
| FileDTO of FileMetadataDTO
| FileExtensionDTO of FileMetadataExtensionDTO
| DirectoryDTO of DirectoryMetadataDTO- Строки. Зона разбивается на блоки по 256 байт, в каждом блоке хранится название файла/директории(без пути)
- Данные. Зона разбивается на блоки по 4096 байт, они предназначены для хранения данных записываемых в файл. Структура метаданных устроена так, что каждый файл ссылается на родительскую директорию, соответственно нет нужды в отдельных блоках хранящих данные о файлах в директории.
BitmapAllocator - сердце этого проекта. Он используется почти везде. В частности менеджментом блоков в каждой зоне занимается BitmapAllocator(по одному на каждую зону).
BitmapAllocator - аллокатор, который базируется на битовой маске, в которой 1 означает занятый блок, а 0 - свободный. В оперативной памяти он представлен классом BitmapAllocator, который владеет изменяемым массивом uint64. Аллокатор допускает многопоточный доступ и реализован по принципу lock-free при помощи атомарных операций. Для ускорения работы используются особые битовые операции: поиск первого ненулевого бита и количество ненулевых бит(обе операции на большинстве процессоров представлены одной инструкцией)
Процесс поиска свободных блоков и создание, соответствующих масок, реализован в виде чистых функций. Каждый поток обращающийся в аллокатор, считывает текущее состояние и осуществляет на нем поиск и создание масок, затем он атомарными И или ИЛИ пытается применить их к общему состоянию. В случае неудачи, он отбрасывает найденную маску, берет актуальное состояние и начинает процесс поиска и применения заново. Таким образом логика аллокатора отделяется от логики управления изменяемым состоянием.
Помимо того, что BitmapAllocator управляет блоками в зонах, используется в реализации ObjectPool, при помощи которого, в свою очередь, реализован весь многопоточный ввод-вывод(для того, чтобы каждому потоку мог быть предоставлен независимый доступ к файлу)
В хранилище BitmapAllocator представлен сырым массивом бит. За установку значений отвечает BitmapAllocatorPersister
Внутри программы файловая система представлена в виде дерева файлов и трех вышеописанных зон, над которыми можно осуществлять операции ввода-вывода и аллокации и освобождения блоков. Это состояние общее для всех потоков
Внутреннее представление дерева отличается от представления в хранилище.
В хранилище оно спроектировано для оптимального хранения в виде блоков и достижения наибольшей локальности по блокам при изменениях. Например при добавлении файла/каталога в директорию записывается только один блок метаданных, который содержит данные о файле и адресе родительского каталога, сам блок родительского каталога остается неизменным.
Внутреннее представление спроектировано для снижения алгоритмической сложности при поиске соответствуюшего узла. Например каталог содержит в себе ссылки на все дочерние файлы и каталоги. Внутри программы дерево оно реализовано при помощи обычного неизменяемого дерева. В будущем его возможно заменить на неизменияемое дерево префиксов.
Перевод между представлением в хранилище и представлением в программе реализован "в лоб" в виде чистых функций.
Интересным моментом является сериализация структур метаданных. Изначально был план воспользоваться механизмом F# Type Providers, который позволяет на основе, например JSON схемы, сгенерировать в runtime типы для работы с обьектами. Однако во время изучения темы я нашел очень интересную библиотеку FsPickler. В её основе лежит статья Andrew Kennedy о pickler combinators. Простыми словами этот подход описан здесь. Меня привлек данный подход и я принял решение попробовать использовать в проекте именно его. К сожалению сложных типов, требующих явного задания правил сериализации, в проекте не нашлось, и я пользовалься лишь автосгенерированными пиклерами, так и не раскрыв весь потенциал.
Одной из заявленных функций является толерантность к ошибкам, а именно способность системы оставаться валидной в случае возникновения ошибок(как внутренних, так и внешних) во время выполнения операций.
Этого позволяет достичь применения паттерна компенсирующих транзакций. Я не нашел готовой реализации, поэтому я реализовал ее своими руками. Поскольку она имеет общую природу с Result, я добавил соответствующие вспомогательные функции для интеграции моего типа CompensativeResult со стандартным Result.
Хороший пример использования 1
Хороший пример использования 2
Fuse, в моем варианте использования, навязывает собственную модель исполнения, поэтому нужно было придумать решение в рамках существующих ограничений.
Если упростить, то всё что требуется от реализации файловой системы - предоставить обработчики запросов и указать возможно ли их исполнять параллельно. Fuse сам неким образом получает запросы из ядра, вызывает наши обработчики, обрабатывает результат и передает его обратно в ядро.
В связи с этим была реализована следующая модель исполнения команд:
- Общее состояние делится между всеми потоками
- Дерево файлов и каталогов представлено изменяемой ссылкой на неизменяемое дерево
- Всё время исполнения обработчики работают с локальной, неизменяемой копией дерева. Если возникает необходимость внести изменения, берется самая акутальная версия дерева, с ней выполняются операции и после при помощи CAS операции осуществляется попытка применения изменений. Всё это повторяется, пока не получится применить изменения, либо пока в ходе применения операций не возникнет ошибка.
- Таким образом вся логика работы описывается в иммутабельном стиле, а работа с изменяемым состоянием локализована.