1

Is there a hash-based filesystem, where:

  • There is a store of blocks (perhaps 512b, 4KB or 128KB) indexed by the hash of their contents.
  • Each block has a usage count. When it reaches zero, the block's storage is freed.
  • Files are just a length and a list of the block hashes.

This would enable many optimisations, such as:

  • Large files can be copied almost for free (in terms of both time and required storage).
  • Copies of large files use Copy-on-Write to store alterations with minimal disk usage.
  • File equality becomes quick to calculate.

Does such a filesystem already exist?

If not, is it not feasible or is it not a good idea?

2
  • What about 0 length files? They all have the same hash. What about copied files? Both original and copy have the same hash. – waltinator Nov 6 '20 at 14:03
  • 0 length files have no blocks, so no blocks need to be stored for them. Copied files shared their blocks, with reference counting, so that the only space a copied file occupies is its length field and the list of its block's hashes. – fadedbee Nov 6 '20 at 14:10
1

It sounds like you're talking about a copy-on-write filesystem with deduplication. Both ZFS and Btrfs work like this to some degree. Btrfs has offline deduplication tools that can merge duplicate blocks some time after they've been written. ZFS can do online deduplication.

Is online deduplication a good idea? It depends on your use case, but probably not. According to the Wikipedia article for ZFS, "effective use of deduplication may require large RAM capacity; recommendations range between 1 and 5 GB of RAM for every TB of storage." Offline deduplication is probably practical in many more cases.

1
  • It you don't mind a reaper you could save vast tracts of kernel allocated memory with offline deduplication. Have the filesystem maintain block checksums and provide a syscall mechanism whereby a user-space process could read the list of block checksums and merge identical blocks – roaima Nov 6 '20 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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