Структура данных и алгоритм для представления / выделения свободного места в файле

Question

У меня есть файл с «дырами», и я хочу заполнить их данными;Мне также нужно иметь возможность освободить «использованное» пространство и освободить пространство.

Я думал об использовании би-карты, которая отображает смещение и длину.Тем не менее, я не уверен, что это лучший подход, если в файле действительно есть небольшие пробелы.Растровое изображение будет работать, но я не знаю, как его можно легко переключить динамически для определенных областей пространства.Может быть, стоит использовать какое-то основополагающее дерево?

Что бы это ни стоило, я в курсе современного дизайна файловой системы (ZFS, HFS +, NTFS, XFS, ext ...) и я нахожуих решения крайне неадекватны.

Мои цели - довольно хорошая экономия места (отсюда и забота о небольших фрагментах).Если бы меня это не волновало, я бы просто выбрал два дерева сплайнов ... Одно отсортировано по смещению, а другое отсортировано по длине с разорванными связями по смещению.Обратите внимание, что это дает вам амортизированный журнал (n) для всех операций с рабочим установленным временем записи журнала (м) ... чертовски хорошо ... Но, как упоминалось ранее, не решает проблемы, связанные с высокой фрагментацией.

Answer 1

Я бы порекомендовал создать настраиваемую файловую систему (может, конечно, содержать один файл) на основе FUSE . Существует множество доступных решений для FUSE , на которых вы можете основываться - я рекомендую выбирать не связанные, но самые простые проекты, чтобы учиться легко.

Какой алгоритм и структуру данных выбрать, он сильно углубляется под ваши потребности. Это может быть: карта, список или файл, разбитый на куски со сжатием / распаковкой на лету.

Предлагаемые вами структуры данных являются хорошими идеями. Как вы ясно видите, есть компромисс: фрагментация против сжатия.

С одной стороны - лучшее уплотнение, наибольшая фрагментация - сплай и многие другие виды деревьев.

С другой стороны - наименьшая фрагментация, наихудшее уплотнение - связанный список.

Между ними есть B-деревья и другие.

Как вы понимаете, вы указали в качестве приоритета: экономия места - при заботе о производительности.

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

• вид списка смежных блоков данных
• вид дерева для текущей операции добавления / удаления
• когда данные требуются по запросу, выделять из дерева. При удалении следите за тем, что «удалено», также используя дерево.
• смешивание -> во время каждой операции (или в моменты простоя) выполняйте «пошаговую» дефрагментацию и применяйте изменения, хранящиеся в дереве, к смежным блокам, перемещая их медленно.

Это решение дает вам быстрый ответ по требованию, при этом «оптимизируя» материал во время его использования (например, «каждое чтение 10 МБ данных -> дефрагментация 1 МБ) или в моменты простоя».

Answer 2

Я отправил коммерческое программное обеспечение, которое делает именно это. В последней итерации мы закончили сортировку блоков файла по «типу» и «индексу», чтобы вы могли прочитать или записать «третий блок типа foo». Файл в итоге был структурирован как:

1) Заголовок файла. Указывает на мастер тип списка. 2) Данные. Каждый блок имеет заголовок с типом, индексом, логическим размером и дополненным размером. 3) Массивы (смещение, размер) кортежей для каждого данного типа. 4) Массив (тип, смещение, количество), который отслеживает типы.

Мы определили это так, чтобы каждый блок был атомной единицей. Вы начали писать новый блок и заканчивали писать, прежде чем начинать что-либо еще. Вы также можете «установить» содержимое блока. Начало нового блока всегда добавляется в конец файла, так что вы можете добавлять столько, сколько хотите, без фрагментации блока. «Установка» блока может повторно использовать пустой блок.

Когда вы открыли файл, мы загрузили все индексы в оперативную память. Когда вы очищаете или закрываете файл, мы перезаписываем каждый индекс, который изменился, в конце файла, затем перезаписываем индекс индекса в конце файла, затем обновляем заголовок спереди. Это означает, что все изменения в файле были атомарными - либо вы фиксируете в точке, где обновляется заголовок, либо нет. (Некоторые системы используют две копии заголовка на расстоянии 8 кБ для сохранения заголовков, даже если сектор диска выходит из строя; мы не зашли так далеко)

Один из блоков "types" был "free block". При перезаписи измененных индексов и при замене содержимого блока старое пространство на диске было объединено в свободный список, содержащийся в массиве свободных блоков. Смежные свободные блоки были объединены в один больший блок. Свободные блоки использовались повторно, когда вы «устанавливали содержимое» или для обновленных индексов блоков типа, но не для индекса индекса, который всегда записывался последним.

Поскольку индексы всегда хранились в памяти, работа с открытым файлом была очень быстрой - обычно всего одно чтение, чтобы получить данные одного блока (или получить дескриптор блока для потоковой передачи). Открытие и закрытие было немного сложнее, так как нужно было загружать и очищать индексы. Если это станет проблемой, мы могли бы загружать вторичный индекс типа по требованию, а не авансом, чтобы амортизировать эти затраты, но это никогда не было проблемой для нас.

Главный приоритет для постоянного (на диске) хранилища: надежность! Не теряйте данные, даже если компьютер теряет питание во время работы с файлом! Второй приоритет для хранения на диске: не делайте больше операций ввода-вывода, чем необходимо! Ищет дорого. На флеш-накопителях каждый отдельный ввод-вывод дорог, а запись - вдвойне. Попробуйте выровнять и пакетировать ввод / вывод. Использование чего-то вроде malloc () для хранения на диске, как правило, не очень хорошо, потому что оно выполняет слишком много операций поиска. Это также причина, по которой мне не нравятся файлы с отображением в памяти - люди склонны относиться к ним как к ОЗУ, и тогда шаблон ввода-вывода становится очень дорогим.

Answer 3

Для управления памятью я являюсь поклонником подхода BiBOP *, который обычно эффективен при управлении фрагментацией.

Идея состоит в том, чтобы разделять данные на основе их размера.Таким образом, в «сумке» у вас есть «страницы» маленьких блоков одинакового размера:

• нет необходимости явно хранить размер, это известно в зависимости от того, в какой сумке вы находитесь
• нет «реальной» фрагментации внутри сумки

В сумке хранится простой список доступных страниц.На каждой странице хранится свободный список доступных единиц хранения в оверлее над этими единицами.

Вам нужен индекс, чтобы сопоставить размер с соответствующей сумкой.

Вам также необходим специальный режим для "«ненормативные» запросы (т. е. запросы, которые запрашивают выделение, превышающее размер страницы).

---

Это хранилище чрезвычайно эффективно по объему, особенно для небольших объектов, поскольку накладные расходы не относятся к объектамОднако есть один недостаток: вы можете получить «почти пустые» страницы, которые по-прежнему содержат один или два занятых блока памяти.

Это можно устранить, если у вас есть возможность «перемещать» существующие объекты.Что позволяет эффективно объединять страницы.

(*) BiBOP: Big Bag Of Pages

Answer 4

Самым простым решением является свободный список : сохраните связанный список свободных блоков, используя свободное место для сохранения адреса следующего блока в списке.