I'm in the process of getting to know (modern) filesystems. As part of it, I came across log structured filesystems that also handle allocations in a log structured way. I wonder how they handle allocation of space in the most efficient way and if they probably use a data structure, I'm not aware of.
As far as I understood, an allocation related log entry, stored on the disk, basically consists of:
+------------------------+
| offset | length | type |
+------------------------+
Where offset is the offset on disk (or within a region of it), length as the amount of blocks (or bytes) and type as either allocation operation or free operation.
Once read from disk, these entries are managed and merged within a specific (tree-like) data structure using just one type, i.e. merge all allocations the be able to tell about offsets that start a free space area up to length length.
It's easy to sort this structure by offset, since this value is unique. But for allocation operations, it'd be easier to have a separate structure where the data is managed by length, i.e. I want to allocate x blocks, search for x and if the result is less than x, give me the next entry that is larger than x and use it's offset for an allocation operation of the type alloc(offset, x).
Naturally, such a data structure would need to handle duplicates, since the same length (of free blocks) can be available at multiple offsets.
- So which data structure would be the best for this job? As far as I know, rb-tree, AVL tree or b-tree (and it's variants) do require unique keys?!
- Add-On question: How's the allocation strategy of filesystems that use a log based structure? Did I misunderstood the log-entry on disk?
An approach I could think of, would be using an rb-tree similar to the one provided by the Linux kernel and extend the rb-tree node (with length as key) by an array/linked list of offsets with the same length. But both, array and linked list, seem to be suboptimal approaches to the problem.
