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 | +------------------------+
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
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
Naturally, such a data structure would need to handle duplicates, since the same
length (of free blocks) can be available at multiple
- 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.