Deduplicating photos on Network Attached Storage
Tags: bash
Published: 2020-11-15 22:50:03

In this post I'd like to show you how to find and remove duplicated files.

I have several computers at home, and had some more in the past, which lead to situation where some disk drives contain backup copies of drives from other machines, which in turn might contain some even older backups. It's a mess. And then I've tried to back that up to Network Attached Storage (NAS) via various ways (either by syncing specific directories on local machines to directories on the NAS, or by some backup tools, etc.) which lead to even more copies of copies of copies. And then I've run out of space on the NAS.

If I were to start this all over from scratch, I'd probably use `git` - it nicely deduplicates the files (with same hash) under the hood giving you the comfort of logical and familiar directory structure (once you check out). And point in time recovery, as a bonus:)

But it's too late for that, at least til I free up some space on NAS:)

So, I wrote [deduper](https://github.com/qbolec/deduper) - bash script combining `find`, `md5sum`, `sort`, `awk` and `xargs` to find all big files, compute MD5 hashes of their content, group'em by hash, and remove unneeded copies, optionally replacing them with symlinks to original.

You can find description of how to use the tool in its [README](https://github.com/qbolec/deduper/blob/main/README.md), and explanation of the implementation in the source comments of the [deduper.sh](https://github.com/qbolec/deduper/blob/main/deduper.sh) script.

In this article I'd like to focus on something which you can't usually find in a README or source comments, which is: how do I actually wrote this?

First, I had to figure out the algorithm in broad strokes:
find files from several directories, compare their contents, then delete all except one identical files.
I knew I want to compare content, not just name, as I realized names are not unique.
Also, this made me realize that there might be bazillion empty files, which would all appear "equal", and also that small files are probably not the biggest part of the problem with running out of space, both of which suggest I should put some lower-bound on size of files to bother with.
To compare two files directly it's probably easiest to use `comm` or `diff`, but to avoid having to compare each of O(n^2) pairs - which would be way to slow - it's faster to compute hash of the content of each file once, and then group files with same hash by sorting (say, in O(nlgn), ideally in O(n) using radix sort).
So, the sketch of the idea was: find all big files, hash their content, group files with equal hash, and then keep just one from each group.

Then I had to decide on technology. I knew it's going to be executed on a NAS which has a bash shell and that what I aim to do is related to simple operations on files, like finding, computing a hash or sorting, each of which is already implemented in standard bash toolset. If I had to do something completely new, which can't be decomposed to such building blocks, I might be forced to write something in a scripting language like JS or Python, perhaps expressing the most performance critical part in C++. But here, the most performance critical part would probably be I/O and computing hashes, for which specialized and quick programs already exist. So, I decided to write this as a bash script.
I hate bash (in particular I felt a shiver down my spine when thinking about the problems with escaping spaces and other characters in filenames). But, I really like the LEGO bricks nature of incrementally constructing longer and longer pipe of small programs.

I like TDD. I am too lazy for a full blown and solid approach to it, but I like at least to have some way to test what I'm doing, while I'm doing it. I just feel insecure when writing code blindly without having any test at all. So, I've created three directories and put some overlapping subsets of photos in them. Then, to make it more difficult, I added spaces to some filenames - because when I expect something to be a hard part of the problem, I don't avoid it, but rather make sure I gonna hit the wall soon. I know - sometimes it makes sense to start with a simple test case, make sure you pass it, then gradually add more and more complicated cases. But, as I've said, I'm too lazy for a proper TDD, and if I'm going to have just one test, then it's better be realistic. Also, my intuition was that a solution which properly handles white space in filenames is very different from the simplest solution which doesn't has to deal with it, so the incremental approach wouldn't really be incremental, but rather could require a rewrite and debugging an already long bash script. 

When I write bash scripts, I try to make them one long string of pipes. I don't know why. It just feels more elegant to me when things are stateless, almost like some Monad expression. Maybe this is because I hate "bash as a scripting language" but tolerate "bash as a declarative way to bind several processes together"?

So, I start with deciding what will be the first process in the pipe, which will produce the data. Sometimes it's just a `cat` of some file or a `grep` for some pattern. Here it was natural to start with `find` to list all the files. I often put `|head` immediately after first process, so that I have just a sample of first 10 items to work with, which is usually enough to expose some problem in my thinking or solution, without overwhelming my brain's capacity. 
So:
```
#!/bin/bash
find | head
```

Then, I recalled I wanted to specify a list of directories to scan. So, probably I'll need `$@` or `$*` or `"$@"` or `"$*"` or .. argh! I'll be frank with you: I usually get through this stage by voo-doo programming. Also, I think it's nice to give a name to the thing, so I tried stuff like:
```
#!/bin/bash
dirs="$@"
find "$dirs" | head
```
or
```
#!/bin/bash
dirs=$@
find "$dirs" | head
```
or various other combinations of putting `"` in various places until I gave up. Yes, there are probably some rules which govern that..apparently 
```
dirs=("$@")
find "${dirs[@]}" | head
```
works, but c'mon! This is ridiculous! Know when to stop :) So, I've just used `find "$@" | head` which just works for some reason I don't wanna know.

Don't get me wrong - it's important to be curious, open, and not blame the tools for your ignorance. But if there was some beautiful simple rule to be learned here, I've somehow missed it during last 10 years, and my mental model now is: "bash syntax is an evolutionary accident". So, I just try to satisfy the beast and move on.
It's important though to get escaping to work correctly, even without understanding why particular incantation works, because otherwise you often risk a huge security hole. Even without external malicious attacker, you can hurt yourself if `rm "one file"` becomes `rm one file`. And this is one of the reasons why I made sure directories and filenames in my test contain spaces from the start - so that I can get it right by trial and error even if I couldn't figure it out by armchair reasoning.

Then, I've added criteria for filename, filesize etc. to `find`. I've just googled it, frankly. I always find it unnatural, that `find` requires to list paths before the search predicates - it's not how `grep` or `git blame` or pretty much any other tool works, which first let you specify what you want to do, and then - where. 

Then, I knew I want to do something for each file, and for that it would make sense to use `xargs`. I thought I'll start with simple `xargs ls -l` just to see if the pipe works as it should.
I was naive enough to think that since `find` will report one file in one line, then `xargs -L1` will process one line at a time. It turns out that while `xargs -L1` will indeed "process" one line at a time, it will "process" it by treating spaces in names as delimiters between items, which effectively means (for programs like `ls` or `rm` or `md5sum`) that they'll think we ask them to process several files. Ugh.
Googling again, I've learned that the only way to get the behavior I want is to use `xargs -0`, which means I need to make sure paths are separated using `\0` not `\n`. Thankfully `find` has `-print0` option for that.
It also has `-exec`, which lets you execute something for each found file, which I also flirted with, when I've realized that `find` outputs not just files, but also directories. But then I've dropped the idea of using `-exec` as I've realized it will spawn a new process for each file processed, and that I can just use `-type f` to force it to report just files.

Then, I had a problem with said `md5sum` which for some reason worked differently in Git Bash on my Windows than on NAS: the output format included a `*` before each filename, which googling taught me indicates a binary file. Whatever. Thankfully such small corrections can be easily done with `sed`, which let's you apply some replacement rule to each line. I knew what expression to search for: `[a-f0-9]{32} [*]?` (32 hexadecimal characters followed by space and optionally a star). Yeah, there's probably a name for "hexadecimal class", but I never remember if it is `[:hex:]` , `[:hexadec:]`, `[[:hex:]]` or `[::hex::]` or what, and before I figure this out, I'm done typing `a-f0-9`. Also, there's probably a way to escape `*` character properly, but as said earlier figuring the amount of slashes which will make bash's, sed's and regular expression's parsers happy is beyond my brain capabilities, so I've learned to simply put problematic character inside `[` and `]`, as in this context rules are simpler to grasp.
But then, this optional `?`..I never remember which tools (`sed`, `git grep`, `grep`?) understand this notation, so I decided to use `[ *]*` instead, as this always works, even though it means something different. I prefer to know a few tricks which simply work in several contexts than to burden my brain with peculiarities of a given tool.
And I never remember if I need `-e` ("..xtended, ..xpressions") or `-r` ("..gular, ..rules") to make `sed` understand my dialect anyway. Turns out, by trial and error, it was `-r`. 
Also, I knew I need to remove the `*` but keep the part with the hash, which means that the replacement string needs to reference the first capture group, and I guess I'll never learn if it is `\1`, `\\1`, `\$1`, `\\$1` or what, so again by trail and error, I've arrived at:
```
| sed -r 's/^([a-f0-9]{32})[* ]*/\1 /g'
```
(**EDIT**: initially I forgot `^` in the regexp, which seemed to work, but only because I had no files with long alphanumeric names during testing. In real world, svn directories contain a lot of filenames with long hashes as their names, which got chopped by the faulty regexp)

While I'm struggling with such `sed` regexp, there is a background thread in my brain which is scanning for simpler solutions using `cut` or `awk` or maybe `grep -o`. It didn't found anything before I was finished with `sed`, though :)

So far I had something which writes a list of `md5sum`s of files.
Next step was to `sort` it. As the hash and path column were in the proper order already, one can simply use `sort` to rearange the list so that the files with same hash are next to each other in the sorted output. And if path and hash were in the opposite order, I'd be screwed anyway, as then all those white spaces in filenames would make it difficult to figure out any structure.
Much later I recalled that I wanted the list of directories to be a priority list, so that decision which copy to keep and which to delete was supposed to rely on the order of arguments to the script, and not on their lexicographic ordering. This can be easily fixed by specifying that `sort` should sort by the first column (`-k1,1`) only and that it should use a stable sort (`-s`) to maintain the original relative order of (equal) elements.

Then, the idea was to keep just the first file from each group. If we wanted to output the first filename from a group it would be trivial, as this is what `uniq` can do for us. But we actually want the opposite, as we are constructing a list of files to delete, not to keep. Thus we need to pass all the duplicates down the pipe, and silence the first occurrence.
For cases like this, I'm glad I've learned `awk`. If you don't know at least a little of `awk`, do yourself a favor and learn it - it's very much like JS or C (even more like LUA) with the difference being that your code is implicitly treated as a body of `while` loop over all lines. Thus expressing a thing we need to do here is as simple as:
```
awk '{ if($1==last_hash){ print $0 }else{last_hash=$1} }'
```
where `$1` references the first word in the line and `$0` is the whole line.
Or to put it even more succinctly:
```
awk '($1==last_hash){ print } {last_hash=$1}'
```
by exploiting the fact that `awk` program is actually a list of `(optional condition){what to do}` rules and `print` by default writes the current line.

I try to use `awk` when I can't express something in `sed`, and `sed` if I can't express it with `cut` or `tr` or `grep`, and so on - there is a hierarchy in my head of how "Turing complete" and "overkill" a tool is, and I prefer to use the simplest.
Why? I don't know.

Finally, I had something I wanted to output: a list of files to delete. But I also wanted to keep building the pipe, to finally get to the place where `xargs rm` will remove the files.
So, I wanted to see what's in the pipe at this stage, but also to continue processing.
For such "debugging hooks", if you will, I interject `|tee filename.log|` which forks the flow of the data, so that it goes both to the `filename.log` and to standard output.

There are a few more commands down the pipe, but nothing new I could tell about my approach: just keep building the pipe, one step at the time, verifying that the output is what you expect it to be, using `|head` or `tee` and substituting something safe like `echo` or `xargs ls` in place of more risky things like `rm`.

Actually, I've decided to finish the pipe before getting to `rm`.
When writing programs I prefer to separate the safe, stateless, functional, read-only part, from the dangerous, stateful, imperative, which modifies the state.
It's always easy to combine two scripts into one later on if one needs to automate two steps, than it would be to separate a tangled mess into two when such need arises.
So, if you can make the decision to split early, do it, while it's cheap.
You'll be glad that you had occasion to verify the list of files to delete before actually running `rm` on them :) And in case you have to debug the script, it's much easier if you don't have to be afraid of it's side-effects.