Дані що створюються програмами необхідно десь зберігати для подальшого використовування, і вони повинні бути якось структуровані, щоб ми могли швидко знайти необхідну інформацію. Файлова система (ФС) відповідає за цю задачу і надає нам шар абстракції над пристроями зберігання інформації, на яких дані фізично зберігаються.
В цій статті ми вивчимо концепти які використовуються файловими системами і як їх зібрати докупи та створити свою власну ФС.
Структура диска
Коли дані зберігаються на жорстких дисках (HDD) або на твердотілих накопичувачах (SSD), вони записуються в маленькі комірки що називають секторами (або сторінками, у випадку з SSD). Накопичувачі не мають жодної інформації про те, що представляє цей шматок даних, це просто гігантський масив секторів. Завдання файлової системи - зрозуміти все це.
Файлова система ділить диск на блоки фіксованого розміру. FS використовує більшість із цих блоків для зберігання даних користувачів, але деякі блоки використовуються для зберігання метаданих, які є важливими для роботи файлової системи.
На наступному малюнку наведено приклад того, як файлова система структурує інформацію на диску:
У наступних розділах ми зрозуміємо, що означає кожен тип блоку.
Суперблок та бітові карти (bitmaps)
Суперблок зберігає більшість метаданих про файлову систему, такі як: розмір блоку, позначки часу (timestamps), скільки блоків і файлів використовується і скільки вільних, тощо.
Бітові карти - це один із способів відстеження того, які блоки даних та inode є вільними. Індекс у бітовій карті, встановлений на 0 вказує на вільний слот, а індекс, встановлений на 1 вказує на зайнятий слот.
Inode
Inode - це структура, яка зберігає метадані про файл. В inode зберігаються такі атрибути, як дозволи доступу, розмір, розташування блоків даних, що утворюють файл, та інші.
Inode зберігаються в блоках, які разом утворюють таблицю inode, як показано на наступному малюнку.
Для кожного слота в бітовій карті inode, встановленому в 1, у таблиці буде відповідний inode. Індекс слота такий же, як індекс і в таблиці. Це пояснює назву inode, що є короткою назвою для index node.
Блоки даних
Як випливає з назви, блоки даних - це блоки, куди записуються фактичні дані які належать файлу. Ці блоки також використовуються для різних цілей, які ми скоро побачимо.
Вказівники на дані
Inode повинен мати спосіб вказувати на блоки даних, з яких складається файл. Найпростіший спосіб - це прямі вказівники. У цьому випадку кожен вказівник вказує на блок, який містить деякі дані файлу. Проблема в тому, що великі файли; де розмір перевищує кількість прямих покажчиків, які може мати інод; не підтримуються в цьому режимі. Одним із способів подолання цієї проблеми є використання непрямих покажчиків , які замість того, щоб зберігати дані користувачів, вони зберігають вказівники на блоки, що містять дані користувачів. Для великих файлів додається ще один шар непрямого використання з подвійними непрямими вказівниками. А для ще більших файлів використовуються потрійні непрямі вказівники.
Щоб дати уявлення про найбільший розмір файлу, який дозволяє кожен рівень, перевіримо на прикладі, враховуючи, що розмір кожного блоку становить 4 КіБ. Дослідження показали, що більшість файлів є малими[1], тому 12 прямих покажчиків дозволять вказувати файли розміром до 48 КіБ. Враховуючи, що кожен вказівник займає 4 байти, тоді один непрямий вказівник дозволяє вказувати на файл розміром приблизно до 4 Мб:
(12 + 1024) * 4 КіБ
З додаванням подвійних непрямих покажчиків розмір зросте приблизно до 4 ГіБ:
(12 + 1024 + 1024 2 ) * 4 КіБ
І нарешті, за допомогою потрійних непрямих покажчиків розмір файлів може бути приблизно 4 Тб:
(12 + 1024 + 1024 2 + 1024 3 ) * 4 КіБ
Цей підхід може бути не дуже ефективним для обробки великих файлів. Наприклад, файл розміром 100 Мб вимагає виділення 25600 блоків. Продуктивність може сильно постраждати, якщо блоки були фрагментовані на диску.
Деякі файлові системи використовують екстенти, щоб допомогти у цій ситуації. У цьому підході існує єдиний вказівник і довжина, яка повідомляє, що дані починаються з адреси вказівника і займають вказаний діапазон блоків. У нашому прикладі вище, для опису одного і того ж файлу буде використаний один розмір розміром 100 Мб. Для підтримки більших файлів можна використовувати кілька екстентів.
Каталоги
Можливо, ви помітили, що для каталогів не існує конкретної структури. Причиною цього є той факт, що inode представляють як файли, так і каталоги. Різниця полягає в тому, що зберігається у відповідних блоках даних. Каталоги - це просто список усіх файлів, які він включає. Кожен запис має вигляд, (name, index number) тому, шукаючи певний файл (або інший каталог), система використовує name для пошуку відповідного inode.
Пошук файлу може бути повільним, якщо каталог містить велику кількість файлів. Цю проблему можна пом'якшити, підтримуючи відсортований список та використовуючи бінарний пошук, або замість того, щоб представляти його як список, також може використовуватися хеш-таблиця або збалансоване дерево пошуку.
Шляхи доступу
Читання
Під час читання з файлу, файловій системі потрібно пройти весь шлях, відвідуючи кожен inode по дорозі, поки не дійде до inode потрібного файлу. Припускаючи, що користувач має дозвіл на доступ до файлу, файлова система перевіряє, які блоки пов'язані з ним, а потім зчитує з них запитувані дані.
Запис
Під час запису у файл повинен відбутися той самий процес, щоб знайти відповідний inode. Якщо для запису потрібен новий блок, файлова система повинна виділити його, оновити відповідну інформацію (бітова карта та inode) та записати в блок. Отже, одна операція запису вимагає п’яти операцій вводу-виводу: одне зчитування з бітової карти, один запис, щоб позначити новий блок як зайнятий, дві для читання та запису в inode, і одна для запису даних у блок. Це число може збільшуватися під час створення нового файлу, оскільки тепер пов'язану інформацію з каталогу також потрібно прочитати та записати, щоб відобразити цей новий файл, і виконати операції зі створення нового inode.
GotenksFS
Як допоміжний проект, я вирішив написати власну файлову систему на Rust, оскільки я вивчаю цю мову. На деякі аспекти мене надихнула файлова ситсема ext4 [2], і в цьому розділі ви дізнаєтесь про це більше. Файлова система використовує FUSE[3], а диск представлений як звичайний файл. Розмір блоку можна налаштувати як 1 КіБ, 2 КіБ або 4 КіБ. Файли можуть мати розмір до 4 ГіБ для розміру блоків 4 КіБ, тоді як файлова система теоретично може мати розмір до 16 Тб.
mkfs
Першим кроком є створення самого образу зі значеннями конфігурації для файлової системи. Це досягається за допомогою команди mkfs:
$ ./gotenksfs mkfs disk.img -s "10 GiB" -b 4096
Після запуску команди, створюється образ загальним розміром 10 ГіБ, а кожен блок у файловій системі має розмір 4 КіБ.
На цьому кроці значення конфігурації та інші структури, такі як кореневий каталог, записуються в образ в першого блоку: суперблок. Відповідні записи бітової карти та дані також записуються. Ці значення будуть необхідні для наступного кроку: монтування файлової системи.
mount
Після створення образу нам потрібно змонтувати його, щоб ми могли почати його використовувати. Для цого скористаємося командою mount:
$ ./gotenksfs mount disk.img gotenks
І ви можете побачити інформацію про файлову систему:
Структура на диску
Суперблок записаний у перші 1024 байти і містить значення конфігурації, вказані в команді mkfs.
pub struct Superblock {
pub magic: u32,
pub block_size: u32,
pub created_at: u64,
pub modified_at: Option,
pub last_mounted_at: Option,
pub block_count: u32,
pub inode_count: u32,
pub free_blocks: u32,
pub free_inodes: u32,
pub groups: u32,
pub data_blocks_per_group: u32,
pub uid: u32,
pub gid: u32,
pub checksum: u32,
}
Наступні два блоки представляють бітову карту даних та бітову карту inode. Далі n блоків використовуються для inode таблиці. І наступні блоки - це ті, куди будуть записані дані користувача.
Інод визначається наступним чином:
pub struct Inode {
pub mode: libc::mode_t,
pub hard_links: u16,
pub user_id: libc::uid_t,
pub group_id: libc::gid_t,
pub block_count: u32, // should be in 512 bytes blocks
pub size: u64,
pub created_at: u64,
pub accessed_at: Option,
pub modified_at: Option,
pub changed_at: Option,
pub direct_blocks: [u32; DIRECT_POINTERS as usize],
pub indirect_block: u32,
pub double_indirect_block: u32,
pub checksum: u32,
}
Як ви можете бачити вище, inodes підтримують подвійні непрямі вказівники, що означає, що для диску з розміром блоку 4 КіБ максимальний розмір файлу становить 4 ГіБ. Кількість прямих покажчиків встановлено на 12:
pub const DIRECT_POINTERS: u64 = 12;
При першому запуску FS буде створено кореневий каталог, використовуючи наступне визначення:
pub struct Directory {
pub entries: BTreeMap,
checksum: u32,
}
Групи блоків
Бітова карта inode має 4 КіБ, що означає, що кожен блок бітової карти матиме розмір у 32768 inode. Припустимо, ми округлимо розмір Inode до 128 байт; для відповідної таблиці inode потрібно 4 Мб місця. Одним із способів їх структурування було б мати багато блоків, виділених бітовим картам, потім відповідні числові блоки для зберігання інодів та блоки що залишилиься для даних користувача.
Замість цього ми можемо створити групи блоків, які завжди матимуть один блок для бітової карти даних та один для бітової карти inode. Наступні 1024 блоки містять таблицю inode, а за нею - 32768 блоки, які використовуються для даних користувачів.
Читання та запис у файли
Тепер, коли “диск” налаштовано, ми можемо почати записувати та читати з нього файли. Створення нового каталогу за допомогою mkdir:
Процес, що відбувається, полягає в наступному: система шукає inode кореневого каталогу, шукає, в який блок даних записується вміст, виділяє новий inode та блок даних для нового каталогу, записує запис у кореневий каталог і, нарешті, записує новий каталог у свій блок даних.
Створення нового файлу відбувається за аналогічним сценарієм. Система проходить шлях поки не досягне кінцевого каталогу і додає запис, що представляє новий файл.
Функція запису подає шлях, буфер з даними, зміщення та структуру інформації про файл, яка може містити дескриптор файлу разом із додатковою інформацією про файл:
fn write(&mut self, path: &Path, buf: &[u8], offset: u64, file_info: &mut fuse_rs::fs::WriteFileInfo)
У цьому випадку, замість повторного проходження шляху, щоб знайти inode, система використовує дескриптор файлу (FS попередньо встановлює його при створенні файлу). Маючи на руках inode, FS може побудувати структуру, шукаючи точне місце, куди Inode був записаний:
fn inode_offsets(&self, index: u32) -> (u64, u64) {
let inodes_per_group = self.superblock().data_blocks_per_group as u64;
let inode_bg = (index as u64 - 1) / inodes_per_group;
let bitmap_index = (index as u64 - 1) & (inodes_per_group - 1);
(inode_bg, bitmap_index)
}
fn inode_seek_position(&self, index: u32) -> u64 {
let (group_index, bitmap_index) = self.inode_offsets(index);
let block_size = self.superblock().block_size;
group_index * util::block_group_size(block_size)
+ 2 * block_size as u64
+ bitmap_index * INODE_SIZE
+ SUPERBLOCK_SIZE
}
Тепер, коли FS має інформацію про те, які блоки даних наразі призначені для Inode, він може використовувати їх, щоб знайти точне місце, куди записувати дані, у процесі, подібному вищевказаного. Нові блоки спочатку додаються до Inode масиву прямих блоків, і якщо розмір файлу перевищує (12 * BLOCK_SIZE), FS виділяє номер, indirect_block що містить числа які ідентифікують інші блоки, де зберігаються дані користувача. А у випадку, якщо файл ще більший і вимагає більшої кількості блоків, система додає додатковий шар непрямого використання, використовуючи double_indirect_block поле, яке вказує на більшу кількість непрямих блоків. Читання з файлу відбувається за тим же методом. Ви можете побачити, як він працює тут:
Висновок
Ідея файлової системи полягає у визначенні структури вмісту на диску, що дозволяє системі працювати поверх неї під час створення, запису та читанні з файлів та каталогів.
Ми дізналися деякі поняття, що використовуються для формату диску, як представлені каталоги та файли. Один цікавий аспект - використання непрямих покажчиків, що дозволяють зберігати великі файли. Якщо ви зацікавлені дізнатись більше про файлові системи, я рекомендую прочитати більше про інші техніки що використовуються, такі як ведення журналів, копіювання під час запису, структуровані файлові системи, а також про те, як сучасні файлові системи застосовують ці та інші методи. Можливо, почніть вивчати ту, яку ви використовуєте зараз.
З кодом GotenksFS можна ознайомитися тут: carlosgaldino/gotenksfs.
Список літератури
- [1] Agrawal, N., Bolosky, W.J., Douceur, J.R. and Lorch, J.R., 2007. A five-year study of file-system metadata. ACM Transactions on Storage (TOS), 3(3), pp.9-es.
- [2] ext4.wiki.kernel.org. 2020. Ext4 Disk Layout - Ext4. Available at: https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Overview.
- [3] en.wikipedia.org. 2020. Filesystem In Userspace. Available at: https://en.wikipedia.org/wiki/Filesystem_in_Userspace.
Джерело ENG: blog.carlosgaldino.com
Ще немає коментарів