unique contribution of folder to disk usage

Question

I have a backup containing folders for daily snapshots. To save space, identical files in different snapshots are deduplicated via hard links (generated by rsync).

When I'm running out of space, one option is to delete older snapshots. But because of the hard links, it is hard to figure out how much space I would gain by deleting a given snapshot.

One option I can think of would be to use du -s first on all snapshot folders, then on all but the one I might delete, and the difference would give me the expected gained space. However, that's quite cumbersome and would have to be repeated when I'm trying to find a suitable snapshot for deletion.

Is there an easier way?

---

After trying out and thinking about the answers by Stéphane Chazelas and derobert, I realized that my question was not precise enough. Here's an attempt to be more precise:

I have a set of directories ("snapshots") which contain files which are partially storage-identical (hard linked) with files in another snapshot. I'm looking for a solution that gives me a list of the snapshots and for each the amount of used disk storage taken up by the files in it, but without that storage which is also used by a file in another snapshot. I would like to allow for the possibility that there are hard links within each snapshot.

The idea is that I can look at that list to decide which of the snapshots I should delete when I run out of space, which is a trade-off between storage space gained by deletion and value of the snapshot (e.g. based on age).

Answer 1

You could do it by hand with GNU find:

find snapshot-dir -type d -printf '1 %b\n' -o -printf '%n %b %i\n' |
   awk '$1 == 1 || ++c[$3] == $1 {t+=$2;delete c[$3]}
   END{print t*512}'

That counts the disk usage of files whose link count would go down to 0 after all the links found in the snapshot directory have been found.

find prints:

• 1 <disk-usage> for directories
• <link-count> <disk-usage> <inode-number> for other types of files.

We pretend the link count is always one for directories, because when in practice it's not, its because of the .. entries, and find doesn't list those entries, and directories generally don't have other hardlinks.

From that output, awk counts the disk usage of the entries that have link count of 1 and also of the inodes which it has seen <link-count> times (that is the ones whose all hard links are in the current directory and so, like the ones with a link-count of one would have their space reclaimed once the directory tree is deleted).

You can also use find snapshot-dir1 snapshot-dir2 to find out how much disk space would be reclaimed if both dirs were removed (which may be more than the sum of the space for the two directories taken individually if there are are files that are found in both and only in those snapshots).

If you want to find out how much space you would save after each snapshot-dir deletion (in a cumulated fashion), you could do:

find snapshot-dir* \( -path '*/*' -o -printf "%p:\n" \) \
  -type d -printf '1 %b\n' -o -printf '%n %b %i\n' |
   awk '/:$/ {if (NR>1) print t*512; printf "%s ", $0; next}
        $1 == 1 || ++c[$3] == $1 {t+=$2;delete c[$3]}
        END{print t*512}'

That processes the list of snapshots in lexical order. If you processed it in a different order, that would likely give you different numbers except for the final one (when all snapshots are removed).

See numfmt to make the numbers more readable.

That assumes all files are on the same filesystem. If not, you can replace %i with %D:%i (if they're not all on the same filesystem, that would mean you'd have a mount point in there which you couldn't remove anyway).

Answer 2

If your file names don't contain pattern characters or newlines, you can use find + du's exclude feature to do this:

find -links +1 -type f \
    | cut -d/ -f2- \
    | du --exclude-from=- -s *

The find bit gets all the files (-type f) with a hardlink count greater than 1 (-links +1). The cut trims off the leading ./ find prints out. Then du is asked for disk usage of every directory, excluding all the files with multiple links. Of course, once you delete a snapshot, it's possible there are now files with only one link that previously had two — so every few deletes, you really ought to re-run it.

If it needs to work with arbitrary file names, it'd require some more scripting to replace du (those are shell patterns, so escaping is not possible).

Also, as Stéphane Chazelas points out, if there are hardlinks inside of one snapshot (all the names of the file reside within a single snapshot, not hardlinks between snapshots), those files will be excluded from the totals (even though deleting the snapshot would recover that space).

Answer 3

Since I wrote this answer, Stéphane Chazelas has convinced me that his answer was right all along. I leave my answer including code because it works well, too, and provides some pretty-printing. Its output looks like this:

              total               unique
--T---G---M---k---B  --T---G---M---k---B
     91,044,435,456          665,754,624  back-2018-03-01T06:00:01
     91,160,015,360          625,541,632  back-2018-04-01T06:00:01
     91,235,970,560          581,360,640  back-2018-05-01T06:00:01
     91,474,846,208          897,665,536  back-2018-06-01T06:00:01
     91,428,597,760          668,853,760  back-2018-07-01T06:00:01
     91,602,767,360          660,594,176  back-2018-08-01T06:00:01
     91,062,218,752        1,094,236,160  back-2018-09-01T06:00:01
    230,810,647,552       50,314,291,712  back-2018-11-01T06:00:01
    220,587,811,328          256,036,352  back-2018-11-12T06:00:01
    220,605,425,664          267,876,352  back-2018-11-13T06:00:01
    220,608,163,328          268,711,424  back-2018-11-14T06:00:01
    220,882,714,112          272,000,000  back-2018-11-15T06:00:01
    220,882,118,656          263,202,304  back-2018-11-16T06:00:01
    220,882,081,792          263,165,440  back-2018-11-17T06:00:01
    220,894,113,280          312,208,896  back-2018-11-18T06:00:01

---

Since I wasn't 100% happy with either of the two answers (as of 2018-11-18) – though I learned from both of them – I created my own tool and am publishing it here.

Similar to Stéphane Chazelas's answer, it uses find to obtain a list of inodes and associated file / directory sizes, but doesn't rely on the "at most one link" heuristic. Instead, it creates a list of unique inodes (not files/directories!) for each input directory, filters out the inodes from the other directories, and them sums the remaining inodes' sizes. This way it accounts for possible hardlinks within each input directory. As a side effect, it disregards possible hardlinks from outside of the set of input directories.

bash-external tools that are used: find, xargs, mktemp, sort, tput, awk, tr, numfmt, touch, cat, comm, rm. I know, not exactly lightweight, but it does exactly what I want it to do. I share it here in case someone else has similar needs.

If anything can be done more efficiently or foolproof, comments are welcome! I'm anything but a bash master.

To use it, save the following code to a script file duu.sh. A short usage instruction is contained in the first comment block.

#!/bin/bash

# duu
#
# disk usage unique to a directory within a set of directories
#
# Call with a list of directory names. If called without arguments,
# it operates on the subdirectories of the current directory.


# no arguments: call itself with subdirectories of .
if [ "$#" -eq 0 ]
then
    exec find . -maxdepth 1 -type d ! -name . -printf '%P\0' | sort -z \
        | xargs -r --null "$0"
    exit
fi


# create temporary directory
T=`mktemp -d`
# array of directory names
dirs=("$@")
# number of directories
n="$#"

# for each directory, create list of (unique) inodes with size
for i in $(seq 1 $n)
do
    echo -n "reading $i/$n: ${dirs[$i - 1]} "
    find "${dirs[$i - 1]}" -printf "%i\t%b\n" | sort -u > "$T/$i"
    # find %b: "The amount of disk space used for this file in 512-byte blocks."
    echo -ne "\r"
    tput el
done

# print header
echo "              total               unique"
echo "--T---G---M---k---B  --T---G---M---k---B"

# for each directory
for i in $(seq 1 $n)
do
    # compute and print total size
    #   sum block sizes and multiply by 512
    awk '{s += $2} END{printf "%.0f", s * 512}' "$T/$i" \
        | tr -d '\n' \
        | numfmt --grouping --padding 19
    echo -n "  "

    # compute and print unique size
    #   create list of (unique) inodes in the other directories
    touch "$T/o$i"
    for j in $(seq 1 $n)
    do
        if [ "$j" -ne "$i" ]
        then
            cat "$T/$j" >> "$T/o$i"
        fi
    done
    sort -o "$T/o$i" -u "$T/o$i"
    #   create list of (unique) inodes that are in this but not in the other directories
    comm -23 "$T/$i" "$T/o$i" > "$T/u$i"
    #   sum block sizes and multiply by 512
    awk '{s += $2} END{printf "%.0f", s * 512}' "$T/u$i" \
        | tr -d '\n' \
        | numfmt  --grouping --padding 19
    #   append directory name
    echo "  ${dirs[$i - 1]}"
done

# remove temporary files
rm -rf "$T"