重複ファイルを探す
ここで言う重複ファイルとは名前は違うけど、中身は同じファイルのことです
どうやって探すか？という話と、どこまでやれば良いかを考えました
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の内に差分があれば高速に処理が進みます
ただ、同じサイズで先頭の100kbyteくらいが同じなら、同じである確率高そうです。
そんな正確じゃなくても早く表示してほしいと思ったので自分で作ってみました
fdupesのissueに正確じゃなくても, 先頭Xbyteで処理を打ち切るのはどう？って話してる方は居ましたが、
正確じゃなく危険ということでfdupesには入らなそうですね
jdupesなら、fdupesで出来ない先頭4096byteだけで重複ファイルを判断するオプション(-TTオプション)があります
使ってみたのですが、4096byteで処理を打ち切ると、自分の環境では一部メディアファイルで誤検知があったので今回は使わずに自作しました
実装
こんな感じで作りました
今回は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かと
重複を削除して、データ削減が目的ならzfsやbtrfsの様なファイルシステムの重複排除機能を使う手もあります。（メモリはたくさん必要ですが）
URIがハッシュ値なipfsならネットワーク上で同じファイルを持つ人を見つける事も出来るのでこちらも活用できたら面白いかもしれないです
Discussion