Івкін І
Вступ.
Одна із серйозних проблем при зберіганні такої великої кількості файлів – необхідність інтенсивної роботи з ними. У разі, якщо ці файли постійно потрібно переміщати, оновлювати, видаляти чи додавати нові файли, різко зростає навантаження файлову систему. По-перше, доводиться постійно оновлювати файлову таблицю, по-друге, зростає фрагментація, по-третє, нераціонально витрачається вільний простір на накопичувачі. Досить вузьким місцем є розмір кластера, що заздалегідь виділяється у файловій системі. У тому випадку, якщо файлів дуже багато, і вони настільки невеликі, що не перевищують розміру кластера (наприклад, 32 кілобайти), накладні витрати на їх зберігання можуть бути порівняні із загальним розміром даних, що зберігаються.
Визначення вихідних даних.
Кількість файлів має бути досить великою. У багатьох сучасних файлових системах використовується певна реалізація файлової таблиці (що представляє собою базу даних), в якій зберігається інформація про вміст томів зовнішнього пристрою. Наприклад, у файловій системі NTFS таку функцію виконує MFT – Master File Table – у ній рядки відповідають файлам тома, а стовпці – атрибутам файлів. При значній кількості файлів кількість записів у цій таблиці стає більшою настільки, що це уповільнює роботу з файловою системою. У ході практичної діяльності було виявлено, що при використанні файлової системи NTFS робота суттєво уповільнюється за кількох сотень мільйонів файлів. Таким чином, потрібна кількість файлів для зберігання повинна перевищувати 200 мільйонів та обмежуватися приблизно мільярдом файлів.
Проектування структури даних для зберігання файлів.
Така стратегія розміщення даних усховище називається довільним зберіганням. У стратегії довільного зберігання, зазвичай, досить висока ефективність вставки нових даних, вона оцінюється як О(1). При цьому існує проблема потенційно низького часу вилучення, однак ця проблема вирішується використанням індексів.
Розмір даних можна не використовувати. У такому випадку необхідно буде зчитувати дані до першої послідовності байт, що зустрічається, яка умовно буде названа «розділювачем». Цей метод припустимо, але експеримент показав, що у такому разі дещо знижується швидкодія читання, оскільки зчитувати дані доводиться невеликими порціями і кожної порції необхідно перевіряти, чи не зустрівся роздільник. Отже, для кожного запису в індексі необхідно зберігати такі дані, як зміщення щодо початку файлу та розмір даних, що зберігаються.
Зберігання усунення як кількості байт від початку файлу є неефективним з наступних міркувань. У тому випадку, якщо як контейнер для цього значення використовується 32-бітове беззнакове ціле число, максимально можливе значення може бути тільки 2 32 або 4 гігабайти даних. Це досить невеликий розмір даних, який за наявності великої кількості файлів буде швидко перевищений. Отже, необхідно буде використовувати 64-бітове ціле число, що відразу призводить до необхідності зберігати 8 байт для кожного усунення щодо початку файлу. Неважко підрахувати, що для мільйона файлів витрати на зберігання інформації про усунення виявляться приблизно рівними 8 мегабайтам, а для ста мільйонів - 800 мегабайтам. Така витрата пам'яті є неефективною, тому необхідно вибрати інший показник.
Зокрема, у файловій системі NTFS розмір блоку становить 512 байт. Цеозначає, що дані повинні записуватися (і зчитуватися) на зовнішній пристрій блоками по 512 байт або порціями, розмір яких кратний 512 (у такому випадку розбиття на блоки буде здійснювати сама файлова система). Для того, щоб уникнути проблем з кінцевими даними, розмір яких не крадений 512, необхідно передбачити запис вирівнювання, яке дозволить зробити розмір даних, що залишилися, кратним 512.
Таким чином, можна зберігати зсув щодо початку бінарного об'єкта в кількості блоків зумовленого розміру, а при виконанні операції доступу до даних це значення може бути легко перетворено на фактичну кількість байт.
Таким чином, дані повинні додаватися у великий бінарний об'єкт послідовно, при додаванні нових даних також буде модифікуватися індекс. При видаленні даних з бінарного об'єкта дані про нього видалятимуться з індексу.
Індекс за даними, що розміщуються, повинен, відповідно, ґрунтуватися на наступних показниках:
1) ідентифікатор файлу (це може бути, наприклад, хеш-функція від його назви, глобальний унікальний ідентифікатор GUID і т.п.) - ймовірно, повинен займати 8 байт (64-бітове ціле);
2) усунення щодо початку бінарного об'єкта – 4 байти;
3) обсяг збережених даних – 4 байти;
4) у разі використання кількох об'єктів ідентифікатор бінарного об'єкта – приблизно 1 байт, дозволяє використовувати 256 бінарних об'єктів, які матимуть загальний розмір у системі NTFS близько половини петабайту.
Для швидкості пошуку індекс має бути організований як структури, що дозволяє здійснювати швидкий і ефективний пошук. Як така структура пропонується до використання червоно-чорне дерево пошуку.
На основі цієї мета-Індекс індекс може бути відновлений, однак, очевидно, що при роботі алгоритму відновлення індексу, великий бінарний об'єкт буде недоступний для читання і запису. Це можна назвати часом простою чи «холодним запуском» системи, що відповідає за зберігання бінарного об'єкта. Таким чином, кожен запис у великому бінарному об'єкті має складатися з мета-інформації, фактичних даних та вирівнювання та має структуру, представлену на малюнку.
Рисунок 1 – Структура запису у великому бінарному об'єкті
Для керування даними у великому бінарному об'єкті використовується ознака або прапор, його значення може встановлюватися в діапазоні від 0 до 2, що означає, відповідно, «активно», «віддалено», «в очікуванні». Для видалення даних з об'єкта достатньо позначити запис прапором «видалено» і видалити дані з індексу, при цьому при наступній перебудові індексу видалені записи просто пропускатимуться. Значення "в очікуванні" використовується при додаванні даних. Якщо нові дані займають більш ніж 512 байт разом з мета-інформацією, є ймовірність, що при програмних або апаратних збоях вони будуть додані не повністю, оскільки операція повного додавання цих даних в об'єкт не буде атомарною. Щоб уникнути потенційних проблем, пов'язаних із пошкодженням даних, при додаванні нових даних, вони спочатку додаються з прапором «в очікуванні», а після завершення додавання прапор змінюється на «активно». При перебудові індексу запису з прапором «в очікуванні» також виключаються, оскільки це означає, що вони були пошкоджені, і процес запису не завершився остаточно.
Для контролю цілісності даних використовується контрольна сума, яка зберігається в мета-інформації кожного запису. Вона обчислюється на основі даних,що містяться в бінарний об'єкт, а при отриманні даних вона розраховується ще раз і порівнюється зі значенням, що зберігається в мета-інформації. Це дозволяє уникнути помилок, пов'язаних з пошкодженням даних при транспортуванні по мережі та подібних до них, а також свідомого спотворення даних, що зберігаються, наприклад, у разі злого наміру.