Fdupes: Identify or delete duplicate files
github.com
github.com
On a related note in 2019 Apple destroyed all my music copies in one of the itunes updates, and part of this process I gathered all forms of media into various zfs datasets and de-duped and managed to find all my mp4's from the '90s lol.
It's amazing how much digital garbage we can accumulate, I often wonder what my kids will do when I pass, will they try and sift through all of it, or just toss it in a closet somewhere to be discovered in 1,000 years by some digital archeologist?
On the other hand, my high school projects from decades ago, as well as my first digital photos, are still with me, somewhere in the "archive" folder. They are only a few megabytes after all, an insignificant amount of space for a long time. It's easier to keep copying entire "archive/" to new machines rather than sort it.
And for photos in particular, I know there is an archive on each machine I owned, and on many external drives, at least a dozen copies. I'd say the chances of them surviving 1000 years in are pretty high, much higher than physical photos.
I still believe the physical photos have a larger chance of actually seeing the light of day.
One with is to print albums yearly and send out to friends and family. Some of them will probably survive for a long time. Nothing stops you from hanging on to your digital archive aswell.
I did something not dissimilar. Basically at some point, years ago, I got fed up of deleting for the ten times that one picture I already had deleted in the past.
So I created a little database of files that are "tagged", based on their size first, then on their hash.
The "tag" is basically: "File with this size and hash can always be deleted, no matter what". Or "File with this size and hash and this name can always be renamed to this-or-that-name".
I've also got a few rules: "Empty directory with that name can always be deleted".
Then I launch my "berzerker" on HDDs/SDDs/SD cards and whatnots I have on shelves and get rid of thousands of files. It always feel insanely good.
When it comes to old CDs/DVDs (I know with your 17TB these aren't going to be a thing for you but I still have CDs and DVDs from the 90s and 2000s and once in a rare while I'll still burn a DVD), I copy them to my computer, run the berzerker, and burn a new DVD. Then when all is good and well, I physically destroy the old CD/DVD.
I also transcode movies (say family movies) for which I don't care that much about the quality to a much smaller size (say to x265) and then immediately tag the old file as "can always be deleted" in my database.
Also I haven't inventoried every single file. But I'll typically use "jdupes" (much faster than "fdupes") to find the worst offenders: biggest files appearing often are the ones I tend to inventory first.
What's really great with such inventories/tags is that it's something you basically do once. Once a file (and its size + hash) is tagged for deletion, that file has lost the war.
It's over: my berzerker shall regularly run and it shall find it. And the file is gone.
The files tagged for deletion are "dead files walking".
> It's amazing how much digital garbage we can accumulate, I often wonder what my kids will do when I pass, will they try and sift through all of it, or just toss it in a closet somewhere to be discovered in 1,000 years by some digital archeologist?
They'll use a dumb but convenient "AI": find me all the pictures, movies and writings from my dad and sort them, de-dupe them, rate them and show all that to me chronologically and nicely sorted.
At times I'm wondering why I even bother cleaning that mess. I could just wait and have some software sort it for me in 20 years (or if I'm dead by then, my kid shall do it).
Now that said: we're not the first ones to come up with our own DB of files that can always be deleted, always be renamed, etc. I'm kinda surprised there's not yet some open-source software out there doing just that.
Mine is not shippable as it's Clojure code I run directly from the REPL.
P.S: for the hash, to be really quick, I use Blake3 (which may not suit everybody as it's kinda recent but, darn, is Blake3 quick -- and automatically running in parallel).
While I do deduplication with a Perl script and hashes, I don't use a DB, which is a nice idea to add.
But: how do you make sure that the last remaining original doesn't "loose the war" ...?
OP did it more professionally than I did though: with a "real" SQL DB. I just have strings (from scripts) with filesize+hash but it's still a DB and it's versioned (in Git).
> But: how do you make sure that the last remaining original doesn't "loose the war" ...?
So I'm very cautious when I tag files for deletion: for example a copy of all the tagged files is first sent to a directory where I do a review before confirming it's to be always deleted. If I'm not cautious, I can potentially tag for deletion a file that I want to keep and then I'm kinda toast.
Now as to not lose the last file due to de-duplication: I do have lots and lots of backups (online/on-site [several computers], online/off-site [dedicated servers], offline/on-site [HDDs/SSDs on shelves, DVDs and probably soon BluRay discs] and offline/off-site [family members' house, wife's SME, etc.]).
I mean, in a way backups are what prompted me to go the "forever delete + de-deduplicate". Which is a bit ironic but...
I don't care too much if some backup somewhere contains a file I want to be deleted / de-duplicated but which is not. What's important to me is that should I need to reach for all the files on the backup I can then quickly delete all the files I already tagged for deletion.
My latest (it's a few years old at this point) is lsdup (rust version) using blake3 for hashing the content: https://github.com/redsaz/lsdup/
All it does is list the groups of duplicate files, grouped by hash, groups ordered by size. I'll usually pipe the output to a file, then do whatever I want to the list, and run a different script to process the resulting list. It works fine enough.
> using blake3 for hashing the content
Using any hash algorithm isn't a good design, at least for SSD storage.
First, it invites some degree of cryptographic risk. i.e. if a collision is ever discovered in the hash then your program can be tricked into discovering a false duplicate. Whether that is a problem depends on the use case, but isn't ideal.
Worse, though, is that it just doesn't make any sense algorithmically. Consider the simple example of having two 1TB files and you want to discover if they're identical. You could do a cryptographic hash of each of them and (barring any malicious collisions) tell whether they're the same.
However, now imagine that those two files differed in the very first byte. Now it seems that you could have figured out they're different a lot faster, right?
So what you really want to do is read both files chunk-by-chunk (probably some number of disk blocks at a time) so you can detect the files-are-different case early. (After all, the common case of files that differ is that they'll differ early!). You could still compare the chunks using a cryptographic hash, but now there is no benefit: you can just compare the two blocks of memory directly faster than you can take a crypto hash of them. C's memcmp() works fine but since you are probably working on fixed-sized aligned blocks you can do slightly better with a hand-rolled SIMD loop.
The one advantage that a cryptographic hash gives you is that it provides a memory-efficient way of reading all of file A and then all of file B. Therefore if disk seeks are expensive, it can be a benefit (again, if you can accept the risk of a malicious false-positive). However if the files are SSD backed and you have enough RAM to read a decent sized chunk of each file into memory simultaneously this ceases to be a problem.
To extend this from 2 files to many, first stat() all of the files and group them by file size. After all, two files of different sizes aren't going to ever be equal. You can think of the size as a "hash" of the contents that you get for free. Any files that are 0 bytes are (of course) duplicates of each other so you can just return those as "hits". Any file that has a unique size (which thankfully is often the common case) is not a duplicate of anything and you don't even have to open it. If you care about hardlinks, you also want to track the inode numbers at this step so you can avoid comparing two files that are actually the same inode.
Then for any group of files with the same size, read each block in turn. The tricky part is that you want to subdivide the group by the contents of the file. i.e. if you have 4 same-sized files and two have contents "AAAA..." and the other two have contents "BBBB..." then you didn't find any unique files yet, but you need to split the set of 4 files into two new subsets of 2 files each. Data-structure wise, keep a worklist of items containing of (1) a set of (at least two) files that could be duplicates and (2) how many bytes you've already verified are the same among them. Then when you encounter this "split" scenario you can just push a new worklist item and continue working on one of the groups.
The bit you need to be careful of is not introducing bad worst-case performance here in a hard case (e.g. you have a million potentially-duplicate files, and reading one block separates them into 5000 groups each with 200 members). Just a decent hash-table is enough with the key being the whole disk block.
Because maintaining this hash table adds a bit of complication, it can seem worthwhile to build a special-case for groups of exactly two files, where you can just do the simple read-and-compare. But then you can re-combine this by observing that the case where you have N files that are all the same is also worth optimizing for. So instead, just do the read-and-compare on all of the files until you find the first two that are different -- only then start building the hashtable when you have two different blocks and more files still to read. That way the common-ish case where you have many files all the same can be handled as fast as possible.
There are things that operating systems could provide that would make this even better:
1. It would be nice if it were easy to estimate the likely seek cost before picking an algorithm. If the file system would simply indicate whether it thought it was backed by spinning rust that would be great.
2. Also if you could ask for the filesystem to read a non-fixed number of bytes (without resorting to async-I/O) that would be helpful. ("Give me up to 1MB of the file, but stop early if you have to seek to a new extent"). Having the ability to basically read the file extent-by-extent instead of block-by-block would mean we could be seek-efficient while reading multiple files in parallel.
3. Finally, it would be great if there was some portable way to access any block-hash metadata the filesystem itself keeps. A filesystem that does its own deduplication work might already know that two blocks must have different contents without reading them because it already scanned them. On the flip-side, if the filesystem supports copy-on-write file snapshots then it could tell us in advance that two inodes are really the same underlying file before we open them.
I'd go into the math about how remote of a chance it would be (barring any discovered hash collisions) but others have explained it better than me elsewhere.
But as I tried to describe (probably in way too much detail) the real problem with "hash everything, compare hashes afterwards" is that it implies that you'll be doing I/O to read all of the file's contents even when it isn't needed to prove uniqueness. For a lot of common use cases (big files, few dupes) this can mean doing 1000x more I/O than you need.
Once you design the solution around avoiding unneeded I/O, you find that hashing also stops being useful.
This is what I meant by "barring any discovered hash collisions" but in retrospect I didn't make that clear enough.
Though, if you're crafting your own malicious different-content-same-size files and storing them in your NAS to cause a hash collision to make them appear the same, then I bet several governments are willing to pay top dollar for your abilities :D
Or, different scenario, say you're hosting a Dropbox-like service and you're storing files for hundreds of thousands of users, then you shouldn't be using a duplicate-file-finding util anyway, it'd be better if it was implemented at a different layer anyway.
The scenario you describe (lots of big files of same sizes, few dupes) I agree hashing the entire file would be wasteful. From my experience on my file server, when I had two or more files of the same size, and the size was larger than a few MB, they likely had the same content.
Put another way, if multiple files of the same sufficiently-large size are encountered, expect to read the entirety of those files anyway, whether hashing or checking byte-for-byte, because they are likely dupes. So, there's still potential for perf gains by avoiding hashing, but I'm willing to bet it isn't as much as one would hope/expect.
(You do have me curious as to how much difference it could make, though)
Edit: I'm also willing to admit that I have so many dupes because my backup strategy is TRASH and I have dupes everywhere, and so my scenario could be more unusual than other people.
Yes, if the number of files is small enough, then "notice unique file sizes" is really the only optimization that ends up mattering much. If you have a few thousand files and they're each multiple gigabytes then hopefully you'll get lucky and no two will have the same size.
But the ideal tool should also try to handle the opposite case well too.
First, imagine if you have a huge collection of unique ~100KiB files. Now the "birthday paradox" means that size collisions are inevitable so optimizing the total I/O needed to prove two files are different starts to belp.
But the pathological case is even worse -- what if nearly all of your files are about the same size? For instance, suppose you have a program that is recording time-series data from a sensor and rotating the file every time it grows to 10MB. This sort of thing happens all the time dealing with scientific data sets -- you might have a directory with thousands of large files, all exactly the same size. If you want to quickly verify none of the files are dups, reading one block from each is far more efficient than hashing them all.
and
> But the pathological case is even worse -- what if nearly all of your files are about the same size?... If you want to quickly verify none of the files are dups, reading one block from each is far more efficient than hashing them all.
I agree this is a worthy consideration. No sense in reading the entirety of each of those files when only reading the first block would do, in order to remove the uniques early. If I were to redo the util, it'd probably be something like:
1. Group all files into lists of same file sizes.
2. After all files are read, eliminate any groupings with just one file, these are unique files
3. Read first N bytes to pare down files in those lists, (so now the key is filesize and hash-of-first-N-bytes or even filesize and first-N-bytes if N is small enough, either way)
4. After each filesize-group is subgrouped by first-N-bytes evaluation, eliminate any subgroupings with just one file, these are unique.
5. What remains are files fairly likely to be duplicates.
5a. For users that consider this "good enough", allow them to stop here. (Some deduper tools do this)
5b. For everybody else, in order to make sure the files are dupes or not, the files can next be subgrouped by fully byte-for-byte comparison and/or hashed, whatever the user is good with.
6. The remaining groupings of two or more files are dupes.
In the end I opted not to go for this rewrite, at least not yet, because I got sidetracked thinking about how the whole reason I'm doing this in the first place is because the way I've backed up data across all my machines for years is pretty horrible, all things considered, and now I've got my wife's data to consider too, and I still want my data to be locally available on my laptop, and I don't want to entirely rely on cloud services for syncing, and, and, and... so now I'm making a tool for all that. And then when it is finished, somebody can come along and say "you could've just used owncloud and syncthing and rclone and a pair of external drives, good grief man."
Still though, I might rework the deduper logic anyway.
Differentiators start with file size difference (obv), then an MD5 of the first one percent of the file, then a SHA-1 of the first one percent of a file, then a MD5 of the first ten percent, and so on. The byte-by-byte comparison is the last ditch effort. A differentiator is only triggered by a having two or more files together in a subgroup, and the results are stored in a database.
So we start with a massive group of all of the files. Then subgroups are made by file size. Some subgroups might only have one member and so we stop there. If not, we start with the MD5 of the first one percent ...
I will probably work on image matching, eventually.
The other reason I made it was so that after the dupes were detected, I wanted custom rules as to what to do with them.
I know Microsoft had a metadata dream about files and while I don't disagree with it, most people just ... don't do it or they do it inconsistently. I've worked with librarians, people who would agree on where to put a given book in a vast series of shelves, but when it comes to digital works, they get all sloppy. I think one of the better possible frontiers for AI is tagging out documents and images. But it's still quite aways-away. Just as an example, one would think that Microsoft would have a spellchecker for filenames by now.
But after that, I think one percent of the end of the file. Then ten percent of the start of the file, then ten percent of the end of the file ...
Given that metadata is typically at the end or beginning of a file, those seem like the best place to look for differences.
I would be open to other hashes so long as they were drop-in easy. I'm not concerned about malicious, forced collisions because they would have to overcome two different kinds of hashing, and the most it would earn is a delay, since there's always a byte-by-byte comparison at the very end.
I suspect I would similarly want to use multiple fingerprinting methods for the visual characteristics of an image file.
Consider taking a look at xxh3, possibly. It seems a pretty decent contender, hashing speed-wise, to trade off of secure hashing: https://github.com/Cyan4973/xxHash
If you only have two files, read them X bytes at a time in parallel and XOR the bytes directly, stopping at the first different byte. For more than 2 files, to a first approximation, you have your list of file pointers, you read the first X-number of bytes for all of them and then sort your list in-place based on those first X bytes (sorting is a linear operation if all the X bytes are the same), then you iterate over that sorted list processing each run of identical X bytes in a depth-first fashion. If you have just one element that starts with a given set of X bytes, it's unique and you don't have to process it anymore, otherwise repeat the process reading the next X bytes but only for the files that started with the same bytes. X is probably 8, so that you can efficiently XOR 64 bits together for your comparisons.
Worth some performance measurements, anyway!
If the file comes up as a dupe candidate again (when its size matches another file's) and if its current mtime matches the one in the xattr, then it will use the hash from the checksum.
In practice, I've only had this break a couple times. In both cases, it was because it scanned an incomplete download from a tool configured to set mtime to the server's Last-Modified date. When the download was later finished, the downloader backdated the mtime again. So the mtime matches but the content no longer matches the checksum. So you end up with a false negative on the completed file until that attribute is cleared. Which I'm ok with.
https://github.com/jm-fn/duplicate-destroyer
It's still rough around the edges, but it usually works quite well. (Btw, I would be happy for any suggestions for improvements.)
According to https://github.com/jbruchon/jdupes/commit/2984bd77f4712359, it's at https://codeberg.org/jbruchon/jdupes now.
Unless I've read a lie repeated a million times, it doesn't.
Thanks a ton
Lots of lessons to be learned here, 1 backup really isn't good enough (of course you already knew that) and organizing 5500 files after you've lost the names is still quite a bit of work. But better to have files without names than no files at all. They'll be busy for a while re-labeling all of them, but that is fortunately not my work to do.
If the original owner of the drive had not tried to recover the data themselves first I'm fairly sure that I would have been able to retrieve even more of it because connecting the crashed drive to a windows laptop probably caused it to try to write to the crashed drive (there is no prompt to mount a drive RO before mounting it on windows).
If deleting files isn't what you want, I'd suggest looking into deduplicating tools.
ZFS has its own de duplicator built in, which is nice. It should just deduplicate files and individual extents of files by itself once you enable it. Probably not a good idea on very write-heavy disks, but it's an option.
Other file systems with extent level deduplication can use https://github.com/markfasheh/duperemove to not only deduplicaye files, but also deduplicate individual extents. This can be very useful for file systems that store a lot of duplicate content, like different WINE prefixes. For filesystems without extent deduplication, duperemove should try hard linking files to make them take up practically no disks space.
It's also a memory hog, and I feel like there were other caveats but I don't remember for sure
Generate a hash over the list of hashes for a directory's content. That would allow you to detect identical directories. That directory hash is rather volatile and would need regeneration every so often, but that shouldn't be a major problem.
Hardlinking files would be a dangerous idea, in my opinion
What is good with the FIDEDUPERANGE ioctl is that everything is transparent from the user space point of view: whatever are the files, whatever they are used for, nothing have changed
When you hardlink, you see that, at the current moment, files are the same, but then you assume that userspace wants those files to stay the same
To me, this sounds like a recipe for a disaster
This ioctl lives at the vfs layer. As of now, btrfs and xfs has implemented it. There is a merge request lurking around for zfs, and I have yet to check what is bcachefs' status on this The only top player left is ext4 :/
(disclosure: I work on duperemove)
rclone dedupe --by-hash /path/to/files
It works on various cloud storage too, not just the local disk.
There's also compression, and compression ends up deduplicating data fairly naturally.
Other filesystems with compression (like bcachefs) also naturally manage some level of deduplication through compression.
ZFS does it live, checking the hash of any block that is to be written against the hashes of all existing blocks. That requires keeping those hashes in memory, costing you a non-trivial amount of RAM if you turn it on. It also forces a slower block hash than ZFS would normally choose because collisions matter more. It can be great for read speeds and storage, but write speeds suffer.
Btrfs instead writes normally, but has a command you can run to deduplicate existing blocks. There is also an option to do this at a file level instead of the block level, which decreases the overhead but leads to fewer storage gains.
Our experience with zfs dedupe was that it was ok for some workloads, like remote desktop stuff, but not for most, not worth the overhead. ZFS compression, on the other hand, was well worth the extra CPU time.
But fdupes is great for finding files exactly the same, great tool!
Transparent compression of ZFS handles trivial cases like this quite easily. It even has a 'zle' (Zero Length Encoding) compression mode expressly for such, blocks with all zeros only, instances. Although, of course, the default 'lz4' compression should cover such trivial instances equally well.
> I've always wondered why file systems don't have a dedupe feature similar to defragment.
Because dedup is enormously expensive to do in the otherwise non-trivial cases. ZFS can do it live, and it requires an in memory hash table to track each deduped block. Which, if you imagine a ZFS filesystem with a recordsize of 8K or 16K blocks, this can be enormously RAM intensive. btrfs supposedly does dedup with less overhead(?), but I'd be interested to hear about instance where the combination of compression and filesystem clones isn't more practical.
I’m sure Microsoft would enable it for Windows 11, instead of just Windows 2022, if it didn’t eat directly into juicy margins on increased storage in an industry where product customization / personalization is like 10% of revenues but 40% of profits.
That one step would probably free up global exabytes of disk space.
https://learn.microsoft.com/en-us/windows-server/storage/dat...
But AFAIK MacOS doesn't attempt to proactively dedupe the file system.
This is why I wrote https://github.com/karteum/kindfs (which indexes the fs into an sqlite DB and then enables various ways to process it).
Hardlinks have the disadvantage that they only work on a single disk partitition, while symlinks can span partitions.