重複ファイルを探す

7 min read読了の目安(約6700字

ここで言う重複ファイルとは名前は違うけど、中身は同じファイルのことです
どうやって探すか?という話と、どこまでやれば良いかを考えました

TL;DR

  • 重複ファイルを探すコマンドfdupesを使っておけば大抵OK
  • ただ処理を省いて早く処理する方法はあるよ(厳密ではなくなるけど)

重複ファイルの探し方

まず以下のようなファイルを考えます

$ ls -l
total 20
-rw-r--r-- 1 root root    1 May  6 00:53 a.dat
-rw-r--r-- 1 root root    2 May  6 00:53 b.dat
-rw-r--r-- 1 root root 1024 May  6 01:00 c.dat
-rw-r--r-- 1 root root 1024 May  6 01:00 d.dat
-rw-r--r-- 1 root root 1024 May  6 01:00 e.dat

こんな感じの小さいファイルだったら以下のように全ファイルのハッシュを計算しても良いのですが、工夫してみます
(ハッシュ値の計算はmd5でもsha-1でも何でも良いですが、fdupesと同様軽いmd5でやっています)

$ md5sum * | perl -nalE 'push(@{$u{$F[0]}},$F[1])}{for(keys %u){say"@{$u{$_}}"if@{$u{$_}}>1}'
c.dat e.dat

まず、a.dat, b.datについてはそれぞれファイルサイズが1byte, 2byteになっているので計算しなくてもユニークだと分かります
次にc.dat, d.dat, e.datのハッシュ値を計算する前に先頭の10byteだけ計算してみます

$ head -c 10 c.dat | md5sum
f6513d74de14a6c81ef2e7c1c1de4ab1  -
$ head -c 10 d.dat | md5sum
660f54f5a7658cbf1462b2a91fbe7487  -
$ head -c 10 e.dat | md5sum
f6513d74de14a6c81ef2e7c1c1de4ab1  -

こうするとd.datはユニークだと分かりました
こんな感じで、いきなり全体を計算するのではなく、先頭のXbyteを先に計算して比較することで早くなる場合があります。
例えば、c.dat, d.datが10Gbyteのファイルだと、ハッシュ計算に20Gbyte読む必要がありますが、
先頭10byte内に差分があれば、読み込むデータは20byteだけになるので大幅に早くなります。

fdupesは最初の4096byteをまず計算しているようです
なので4096byteの内に差分があれば高速に処理が進みます

fist-step

ただ、同じサイズで先頭の100kbyteくらいが同じなら、同じである確率高そうです。
そんな正確じゃなくても早く表示してほしいと思ったので自分で作ってみました

fdupesのissueに正確じゃなくても, 先頭Xbyteで処理を打ち切るのはどう?って話してる方は居ましたが、
正確じゃなく危険ということでfdupesには入らなそうですね

https://github.com/adrianlopezroche/fdupes/issues/79

jdupesなら、fdupesで出来ない先頭4096byteだけで重複ファイルを判断するオプション(-TTオプション)があります
使ってみたのですが、4096byteで処理を打ち切ると、自分の環境では一部メディアファイルで誤検知があったので今回は使わずに自作しました

実装

こんな感じで作りました

https://github.com/yaasita/chofuku

今回はSQLiteのインメモリモードを使いましたが、重複さえ数えられれば何でもOKです
まず、名前とファイルを記録します。
今回ハードリンクを考慮していませんが、考慮する場合はこの時点でi-node番号を記録し、同じものはハッシュ計算なしに出せばOKです。あとシンボリックリンクは飛ばしています。

SELECT * FROM files;
name size head100k_hash full_hash
a.dat 1
b.dat 2
c.dat 1024
d.dat 1024
e.dat 1024
f.dat 1150976
g.dat 1150976
h.dat 1150976

以下のSQLで重複を数えます(重複を数えるときはいつもこのクエリを使います)

SELECT size, head100k_hash, full_hash, json_group_array(name) FROM files GROUP BY size, head100k_hash, full_hash HAVING count(*) > 1;
size head100k_hash full_hash json_group_array(name)
1024 ["c.dat","d.dat","e.dat"]
1150976 ["f.dat","g.dat","h.dat"]

サイズが同じファイルのリストが出ました
-size-onlyオプションが指定されていた場合はここで処理を打ち切ります

次にサイズが同じファイルに対して 先頭100kbyteのハッシュ値を計算します
0byteのファイルはハッシュ計算をスキップします

name size head100k_hash full_hash
a.dat 1
b.dat 2
c.dat 1024 2f2bf74e24d26a2a159c4f130eec39ac
d.dat 1024 fc65c6cb47f6eed0aa6a34448a8bfcec
e.dat 1024 2f2bf74e24d26a2a159c4f130eec39ac
f.dat 1150976 595cd4e40357324cec2737e067d582b1
g.dat 1150976 595cd4e40357324cec2737e067d582b1
h.dat 1150976 595cd4e40357324cec2737e067d582b1

同様に重複を数えます

SELECT size, head100k_hash, full_hash, json_group_array(name) FROM files GROUP BY size, head100k_hash, full_hash HAVING count(*) > 1;
size head100k_hash full_hash json_group_array(name)
1024 2f2bf74e24d26a2a159c4f130eec39ac ["c.dat","e.dat"]
1150976 595cd4e40357324cec2737e067d582b1 ["f.dat","g.dat","h.dat"]

-100k-onlyオプションが指定された場合はここで処理を打ち切ります

まだ重複しているファイルに関して、ファイル全体のハッシュ値を計算します
100Kbyteに満たないファイルは計算をスキップします
ハッシュ値計算部分は並列化できますが、ファイルを開ける限界値(ulimit -nの値)を越えないようにする必要があります
今回はシーケンシャルにやっています

name size head100k_hash full_hash
a.dat 1
b.dat 2
c.dat 1024 2f2bf74e24d26a2a159c4f130eec39ac
d.dat 1024 fc65c6cb47f6eed0aa6a34448a8bfcec
e.dat 1024 2f2bf74e24d26a2a159c4f130eec39ac
f.dat 1150976 595cd4e40357324cec2737e067d582b1 ca2e51ae14747a1f1f0dcb81e982c287
g.dat 1150976 595cd4e40357324cec2737e067d582b1 067d1eed705e0f7756ceb37a10462665
h.dat 1150976 595cd4e40357324cec2737e067d582b1 ca2e51ae14747a1f1f0dcb81e982c287

重複を数えて出力します

SELECT size, head100k_hash, full_hash, json_group_array(name) FROM files GROUP BY size, head100k_hash, full_hash HAVING count(*) > 1;
size head100k_hash full_hash json_group_array(name)
1024 2f2bf74e24d26a2a159c4f130eec39ac ["c.dat","e.dat"]
1150976 595cd4e40357324cec2737e067d582b1 ca2e51ae14747a1f1f0dcb81e982c287 ["f.dat","h.dat"]

ファイル全体ハッシュを求めるまでやるくらいならfdupesを使った方が全然早いです
-100k-onlyか-size-onlyを指定しないのであればこのプログラムを使う意味は無いと思います
(ただし-size-onlyは実用上使い物にならないと思います)

まとめ

こんな感じでハッシュ計算を100kbyteで打ち切っても、fdupesの結果と同じでした。
ただし、これは自分の環境だけの話なので、世の中には先頭100kbyteが共通ヘッダとして使われるファイルもあるかもしれません。状況に合わせて方法を変えた方が良いかと思います
大抵の場合はfdupesでOKかと
重複を削除して、データ削減が目的ならzfsbtrfsの様なファイルシステムの重複排除機能を使う手もあります。(メモリはたくさん必要ですが)
URIがハッシュ値なipfsならネットワーク上で同じファイルを持つ人を見つける事も出来るのでこちらも活用できたら面白いかもしれないです