Data structure and algorithm for representing / allocating free space in a file

Question

I have a file with “holes” in it and I want to fill them with data; I should also be able to free up the "used" space and make free space.

I was thinking about using a bi-map that displays offset and length. However, I'm not sure if this is the best approach if there are very small spaces in the file. The bitmap will work, but I don’t know how it can be easily switched to dynamically for certain areas of space. Maybe some base tree is the way to go?

For what it's worth, I look forward to a modern file system design (ZFS, HFS +, NTFS, XFS, ext ...), and I find their solutions extremely inadequate.

My goals are to have pretty good space savings (hence the concern for small fragments). If it didn’t bother me, I would just go after two trees ... One is sorted by offset, and the other is sorted by length with associated broken offsets. Please note that this gives you an amortized log (n) for all operations with working hours of the log (m) ... Pretty good ... But, as already mentioned, it does not handle the problems associated with high fragmentation.

Answer 1

I sent commercial software that does just that. In the last iteration, we ended up sorting the file blocks into "type" and "index" so you can read or write the "third block of type foo". The file was structured as:

1) The title of the file. Points in the list of basic types. 2) Data. Each block has a heading with type, index, logical size and extra size. 3) Arrays (offset, size) of tuples for each given type. 4) An array (type, offset, count) that tracks types.

We defined it so that each block is an atomic unit. You started writing a new block and finished writing before starting anything else. You can also “set” the contents of a block. Starting a new block is always added at the end of the file, so you can add as many as you want without fragmenting the block. A “set” block can reuse an empty block.

When you opened the file, we loaded all the indexes into RAM. When you blushed or closed the file, we rewrote each index that was changed at the end of the file, then re-wrote the index index at the end of the file, and then updated the header in front. This means that the changes in the file were atomic - either you passed the point at which the header was updated or not. (Some systems use two copies of the 8 kB header from each other to save the headers, even if the disk sector goes wrong, we are not so far)

One of the "types" of the block is the "free block". When rewriting index changes and replacing the contents of a block, the old disk space was merged into a free list stored in an array of free blocks. Adjacent free blocks were combined into one larger block. Free blocks were reused when you “installed content” or for updated type block indexes, but not for the index index that was always written last.

Since indexes were always stored in memory, working with an open file was very fast - usually just a single read to get the data of one block (or get a block descriptor for streaming). Opening and closing was a bit more complicated as it required loading and dumping indexes. If this becomes a problem, we can load the secondary type index on demand and not up to amortize this cost, but this has never been a problem for us.

Priority for storage on your hard drive (on disk): Reliability! Do not lose data, even if the computer loses power while working with the file! Second priority for disk storage: do not do more I / O than necessary! Claims are expensive. On flash drives, each individual I / O is expensive, and recordings are double. Try aligning and doing batch I / O. Using something like malloc () to store to disk is usually not very large, because it is looking for too much. This is also the reason why I don't really like memory mapped files - people tend to think of them as RAM, and then the I / O pattern becomes very expensive.

Answer 2

For memory management, I am a fan of the BiBOP * approach, which is usually effective in managing fragmentation.

The idea is to split the data based on its size. Thus, in the “bag” you have only “pages” of small blocks with the same dimensions:

• No need to explicitly store the size, it is known depending on the bag in which you are located.
• no “real” fragmentation in the bag.

The bag keeps a simple list of available pages. Each page stores a list of available storage units in an overlay over these units.

You need an index to match the size with the corresponding package.

You also need a special appeal to out-of-band requests (that is, requests requesting a distribution exceeding the page size).

---

This storage is extremely economical, especially for small objects, because the overhead is not intended for each object, but there is one drawback: you can create “almost empty” pages that still contain one or two busy storage units.

This can be facilitated if you have the ability to "move" existing objects. This effectively allows you to combine pages.

(*) BiBOP: Large Page Bag

Answer 3

I would recommend creating a custom file system (can contain one file, of course) based on FUSE . There are many solutions available for FUSE that you can build on - I recommend choosing not related, but simple projects to learn easily.

Which algorithm and data structure to choose, it goes deep into your needs. It can be: a map, list or file is broken into pieces using compression / decompression on the fly.

The data structures you presented are good ideas. As you can see clearly, there is a tradeoff: fragmentation and compaction.

On the one hand - the best compaction, the highest fragmentation - leafing and many other types of trees.

On the other hand - the smallest fragmentation, the worst list associated with compaction.

Between them there are B-trees and others.

As I understand it, you have declared as a priority: saving space - while taking care of performance.

I would recommend you a mixed data structure to achieve all requirements.

• list view of adjacent data blocks
• tree view for the current add / remove operation
• when data is required on demand, isolated from the tree. When deleting, track what is “deleted” using the tree.
• mixing → during each operation (or at unused moments) de-fragmentes “step by step” and applies the changes stored in the tree to adjacent blocks when moving them slowly.

This solution gives you a quick response on demand, while "optimizing" the material during its use (for example, "everyone reads 10 MB of data → 1 MB defragmentation) or at idle moments.

Answer 4

The simplest solution is a free list : save the linked list of free blocks, reuse free space to store the address of the next block in the list.