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.

  • probably look at the source code for ZFS or the dedup filesystem bits for things like opendedup or bedup.
    – gbjbaanb
    Commented Nov 6, 2014 at 10:49
  • @gbjbaanb I hoped I could avoid searching through implementations, but seems to be only option to get a definitive answer... Commented Nov 6, 2014 at 11:41
  • I'd have given you a proper answer if I knew, but I would go searching the BTFS mailing list or similar to glean the information you want. Your question here is a bit broad.
    – gbjbaanb
    Commented Nov 6, 2014 at 14:30

1 Answer 1


There's good information to be found on this topic in the paper on the implementation of Venti (Plan 9's deduplicating filesystem) and its data structure approach.

In addition, Marco Peereboom has some implementation resources on his work on Epitome (which was heavily inspired by Venti). You can see some slides or a paper from which the slides were based that was presented at AsiaBSDCon in 2010. These slides also include a discussion around network transport for such a filesystem. In addition, source can be found through the wiki page, though it doesn't seem that there's been any public work on this project in some years.

Finally, if you're up for some serious reading, see this Masters thesis work: "Online De-duplication in a Log-Structured File System for Primary Storage" by Stephanie Jones of UCSC. It provides at a minimum a decent study of the algorithms and data structures used in such storage systems, as well as some performance metrics in common real-world workloads. If nothing else for you, it has a wealth of references to other papers on the topic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.