@dang, an idea for GitHub URLs: could the URL truncator keep two path components instead of just one? The second part is the project name and often the more recognisable and interesting component.
Thanks, but I think the level of effort I’ll put into distracting these good people with my feature request is going to be proportionate to how useful I think my request will be. (“Not much” and “not very”, respectively.)
I don't think putting stuff in an extra src/ dir was very common in 1999. Pretty sure that became popular with websites like github. And once you have started without one, there is fairly little incentive for this project to change.
I've always wondered why file systems don't have a dedupe feature similar to defragment. Imagine an inode filled with all zeroes for example, tons of files have large segments that are all zeroes, what if they all get deduped and point to the same inode when the identical bytes are >= the inode size? There must be inode caching speedups for this I'd think. Saved disk space is also an advantage, especially if you work with large uncompressed files a lot (e.g. media editing/archiving).
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!
> Imagine an inode filled with all zeroes for example, tons of files have large segments that are all zeroes, what if they all get deduped and point to the same inode when the identical bytes are >= the inode size?
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.
Windows does, for both NTFS and ReFS. It works flawlessly in my experience. You can enable deduplication with one PowerShell command.
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.
Just to be precise, it’s not part of the filesystem. It’s implemented on top of the filesystem as a background process that moves duplicate data into a “chunk store” and replaces the files with reparse points that route accesses to the deduplication driver. This is ostensibly to keep deduplication out of the write path for performance reasons.
Recent versions of MacOS with AFS can do this to some extent: At the time you make a copy of a file with the Finder, MacOS makes a COW (copy-on-write) copy of the file which behaves like a hardlink until you modify one of the copies, at which point the modified one becomes a separate file with its own identity.
But AFAIK MacOS doesn't attempt to proactively dedupe the file system.
Very useful for identifying files that may need to get deduplicate or that can be removed entirely. Unfortunately, I don't think this will also find identical directories.
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.
> 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.
It's also a memory hog, and I feel like there were other caveats but I don't remember for sure
Huge memory impact, that never goes away - if you turn of dedup, you still need the massive deduplication map in ram for things that already where deduplicated.
I sent a pull request to zfs that adds support for fiduperange, which makes all these tools work without having to turn on the large scale online deduplication. Instead it uses block cloning.
Test it if you are willing!
> Unfortunately, I don't think this will also find identical directories.
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 :/
Funny to see this here, recently I decided to clean up my personal NAS that had 60 million files and 17 TB used. I tried various tools, but this NAS was the backup target for many of my machines over a decade or more of time. I finally gave up and wrote a multi-threaded c++ program to "inventory" every file and then I imported that into sqlite and started building out scripts to do bulk actions, set a flag on for files to delete and some scripting to show the files that would be deleted etc. It was quite a project and took me "spare" time of a month to trim.
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?
My bet: They will toss it in a closet, but it will not be discovered in 1000 years. It will be gone before then. If you want future generations to see your photos, print them out. People will have too much else to worry about than decrypt old storage media.
My 30 years paper photos are mostly lost now.. too many house moves, too much physical stuff.
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 figure our human level general AI assistant (if it doesn't kill us) will sort through my mess of backups in a nanosecond in about ten years, so I'm not gonna start worrying until then lol.
> I finally gave up and wrote a multi-threaded c++ program to "inventory" every file and then I imported that into sqlite and started building out scripts to do bulk actions, set a flag on for files to delete and some scripting to show the files that would be deleted etc.
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).
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.
I've recently started using rdfind for this kind of thing. It does something that fdupes doesn't AFAICT, which is replacing all but one copy of the duplicated files with symlinks.
rdfind and jdupes can replace copies with hardlinks too. Hardlinks have the advantage that they're all identically "real", so there's no heuristic needed to figure out which file should be the "real" one and which ones should be the symlinks.
Hardlinks have the disadvantage that they only work on a single disk partitition, while symlinks can span partitions.
My preferred solution is rmlint [https://github.com/sahib/rmlint] mostly because it also looks at duplicate directories. It produces a bash script instead of deleting anything itself, so you can examine it before running the script it made.
rmlint has a neat feature where it can write the checksum to the file's xattr (along with the mtime when it's calculated) so that it doesn't need to recalculate it in future passes.
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.
Writing a program like this is one of the first exercises I give myself when learning a new programming language, because it touches a little bit of everything (reading files, output, CLI, using libraries, hashmaps, functions, loops, conditionals, etc) and isn't too onerous to implement.
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.
(Warning: rambling ahead, since in the past I've spent a decent amount of time on the same problem)
> 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...
This isn't the first time I've heard concerns about using hashes for checking file equality. I've considered adding a "paranoid mode" to do the direct byte-for-byte checks for such folks that don't even want to introduce a so-remote-it's-virtually-impossible theoretical chance for a collision to occur.
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.
"The math" only matters for random collisions, which are effectively impossible (less likely than the CPU malfunctioning). However that tells you nothing about maliciously constructed files. Even if a hash function has no known collisions today, doesn't mean that they won't be found someday.
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.
> that tells you nothing about maliciously constructed files. Even if a hash function has no known collisions today, doesn't mean that they won't be found someday.
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.
> 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.
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.
> But the ideal tool should also try to handle the opposite case well too... a huge collection of unique ~100KiB files.
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.
So, my deduplication is about merging various archives I have of various things I've pulled off of 4chan since 2005. My algorithm is a bit backward because it starts with the proposition that all files are the same. This will turn out to save on comparisons.
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.
I like the strategy of only hashing the first part of a file as a multiphase approach of deduping in order to quickly eliminate unique files, I wish I had done it that way with my util. Maybe for v2!
I think my next pass at it will be to merge the MD5 and SHA-1 steps so that we get two outputs at the end, this way I would save on the file-reading.
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.
> I'm not concerned about malicious, forced collisions
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
Checking the file size first is good, but reading every byte of every file that has at least one file of matching size and and doing a ton of XOR steps (or whatever BLAKE3 is) for all those bytes can't be optimal when different files probably differ within the first few bytes.
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.
I've considered adding a "just check the first {user-configged-bytes}" mode, which would offer enough of the speed up you describe, which I think jdupes does (maybe? It's been awhile since I looked at it). I think the speed of opening the file and reading the first buffered page of bytes would dominate the time of the operation, especially if one were to do async reads (which my program does NOT do. I should look into it.)
200 lines of Nim [1] seems to run about 9X faster than the 8000 lines of C in fdupes on a little test dir I have. If you need C, I think jdupes [2] is faster as @TacticalCoder points out a couple of times here. In my testing, `dups` is usually faster than `jdupes`, though (but usually only ~1.5..2.0X faster in hot cache settings -- for this problem "really slow" usually comes from IO, though).
fdupes is really nice and fast, but (as far as I remember) it was lacking two features that I needed for my use case, which were 1°/ list duplicate dirs (without listing all of the duplicate sub-contents), and 2°/ being able to identify that all the contents in one dir would be included in another part of the FS (regardless of files/dir structures), which is particularly useful when you have a bigmess/ directory that you progressively sort-out in a clean/ directory. Said differently : fdupes helps to regain space but was not able to help me much to reorganize a messy drive...
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).
Funny, I just used this to help recover a harddrive of a family member that crashed. The directory structure was gone, but the files were still (mostly) readable so using a combination of ddrescue (to pull the remainder of the drive into a partition of another drive), photorec (to recover all of the files that were still readable) and fdupes (to remove all of the duplicates as a result of multiple back-ups on that some drive) I managed to get pretty much all of the data off the drive. 5500 files worth or so, not a huge number but some of them were precious and the only reason this drive was accessed was because it was the backup when another drive had failed entirely. Photorec was a bit weird in that it insisted having the data on the partition of an actual drive, it couldn't work straight off an image. No idea why that limitation is there, it would seem pretty straightforward to allow it to work on an image file instead.
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.
What impresses me about it is that it just 'fire and forget'. It takes a while to run (a few weeks, in my case) but it will do its level best to get your data off the drive and to see the amount of unrecoverable space slink steadily over the days was really neat. In the end I think it recovered 99.9% or so of the drive but the directory structure was still damaged so much that whole sections of the tree were gone. But without ddrescue only a few 10's of files were visible.
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).
80 comments
[ 4.7 ms ] story [ 161 ms ] threadAccording 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
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.
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.)
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)
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.
Hardlinks have the disadvantage that they only work on a single disk partitition, while symlinks can span partitions.
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.
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...
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!
It works on various cloud storage too, not just the local disk.
[1] https://github.com/c-blake/bu/blob/main/dups.nim
[2] https://github.com/jbruchon/jdupes
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).
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).
https://github.com/PJDude/dude