1

This is just my comment from How to cache or otherwise speed up `du` summaries? formulated as a question of its own:

Are there any extended discussions about creating a filesystem in which the total size of each directory (think du) is saved and "bubbles up" (i.e., is propagated upwards in the tree so that all parent directory sizes are correct as well) whenever changed e.g. due to a write to a file, deletion, etc., so that du would be instant?

From the answer I linked above, it's clear that I/O performance would suffer as a result of doing this, I just wonder by how much. Would it decrease by orders of magnitude or just a couple (dozen) percent?

Closely related to this is the concept of "bubbling up" mtimes in the same manner, so that each directory's mtime reflects the most recent change within its entire sub-tree. Both of these features together could, for instance, speed up rsync's --update mode considerably for trees with many deeply nested files.

7
  • 1
    Doesn't seem likely to me. I can't imagine that anyone would find this useful enough to write (or hack) a filesystem just to do this. If it's really important to you, just use separate partitions/filesystems (or zfs datasets or btrfs sub-volumes) and use df (or zfs list/btrfs subvolume list)....but note that mv-ing files between different partitions is a copy-and-delete operation, not just a quick move.
    – cas
    May 20, 2021 at 9:30
  • 1
    As for performance impact, it would be (very roughly) n times the performance impact of atime vs noatime (with n being the average depth of the filesystem tree). for du. and again for mtime. I can't see it improving rsync performance much, if at all....timestamp comparison isn't what takes a lot of time with rsync - that's lightweight compared to calculating and comparing file checksums AND sending the comparison data between source and dest systems.
    – cas
    May 20, 2021 at 9:37
  • @cas Thanks for the depth×atime/noatime suggestion, that does seem like a good way to get a rough estimate. Regarding rsync (--update), according to its manpage, it doesn't use checksums to determine whether files have changed unless --checksum is given. By default, it only uses mtime and file size, so for updating large deeply nested trees in which not much has changed, having both of these available immediately for the entire tree and each sub-tree should speed things up considerably. But I agree this is a niche situation compared to regular usage requiring top I/O performance.
    – smheidrich
    May 20, 2021 at 13:11
  • 1
    What about hard links, i.e. one single file present in several directories? Should each directory update its overall size? (that's not how du works) What about mounting points? Do you make the "bubble" go past the mounting point up to /? If you don't, rsync may erroneously think nothing has changed. If you do, what about Linux's mount namespaces? what about bind-mounts, i.e. directory dir/a bind-mounted over dir/b => should dir's size be updated twice? Etc. This isn't worth the trouble in my opinion.
    – xhienne
    May 20, 2021 at 17:26
  • @xhienne Files with several hard links would have to update each parent directory, and as pointed out in the answer I linked above, that would entail having to store for each file which directories it is in, requiring slightly more space for metadata. With bind mounts one would probably run into trouble with "infinitely recursing" hierarchies so they would have to be ignored, I guess (perhaps also bubbling up a flag saying that the directory contains a bind mount and so its size is not reliable).
    – smheidrich
    May 20, 2021 at 18:52

1 Answer 1

1

Modern filesystems such as zfs / btrfs / bcachefs actually go in an opposite direction and allow / encourage sharing extents between files. With this, the notion of "how much data does a directory occupy" becomes less well-defined (though this was already true to some extent due to hard links): using reflinks, it's possible to create a directory that apparently contains much more data than would even fit on the filesystem (at least as far as simple disk analysis tools like du or ncdu can understand it). One way to rephrase the question would be "how much free space would be freed if this directory was deleted", which is less ambiguous but not all that much useful, because as soon as you create a snapshot, then most directories will now have a unique size of 0 (because their data also is reachable via the snapshot).

I have also encountered the problem of:

  • It's difficult to understand space usage on filesystems which allow data sharing
  • Analyzing the space usage on large filesystems takes too much time (I/O)

For this reason, I created btdu, a sampling disk usage profiler, which solves these problems for btrfs.

As for the general "bubbling up" concept: I'm not sure about other filesystems but this does actually resemble the way btrfs works internally, where there is one main root (b-)tree which recursively references other trees. When any tree (many levels deep) is updated, a new copy is written elsewhere on the disk (hence the COW aspect of btrfs) and the parent is updated to point to the new copy, which in turn causes its parent to get updated in the same way, and so on up until the root tree. (In practice, the implementation employs many optimizations to preserve its invariants but keep the performance reasonable.)

2
  • Interesting! btrfs's FAQ mentions: The upwards-cascading effect of the CoW process means that in the metadata trees, the transid of every block in the metadata must be lower than or equal to the transid of the block above it in the tree. - So if I understand this correctly, if this transid could be accessed (and so far it seems to me like it can't, except for subvolumes, for which you can show the "generation", which is the same thing AFAICT), a "btrfs-aware rsync" could store the root transid somewhere on the target and simply skip over everything with the same transid on the next sync?
    – smheidrich
    Jun 8, 2021 at 16:47
  • 1
    Yes. That's actually exactly how tools such as bees keep track of which filesystem changes they've analyzed so far. Also I think that's how btrfs subvolume send/receive works, when sending incremental changes since a parent snapshot. Jun 8, 2021 at 23:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .