6

I had to write a Bash script to delete duplicate files today, using their md5 hashes. I stored those hashes as files in a temporary directory:

for i in * ; do
    hash=$(md5sum /tmp/msg | cut -d " " -f1) ;
    if [ -f /tmp/hashes/$hash ] ;
    then
        echo "Deleted $i" ;
        mv $i /tmp/deleted ;
    else
        touch /tmp/hashes/$hash ;
    fi ;
done

It worked perfectly, but led me to wonder: is it a time-efficient way of doing that? I initially thought of storing the MD5 hashes in a file, but then I thought "no, because checking whether a given MD5 is in this file requires to re-read it entirely every time". Now, I wonder: is it the same when using the "create files in a directory" method? Has the Bash [ -f ] check linear, or quasi-constant complexity when there are lots of file in the same directory?

If it depends on the filesystem, what's the complexity on tmpfs?

4

4 回答 4

2

我喜欢使用正确的工具来完成这项工作。在这种情况下，您只想查看重复文件。我已经针对我可以使用的数千个文件对此进行了测试，并且重新阅读该文件似乎没有任何问题。另外，我注意到我有数百个重复文件。当我将哈希存储在单独的文件中，然后处理大量文件时，我的系统在一个目录中大约有 10,000 个哈希文件之后慢慢地爬行。将所有哈希值放在一个文件中大大加快了速度。

# This uses md5deep.  An alternate is presented later.
md5deep -r some_folder > hashes.txt

# If you do not have md5deep
find . -type f -exec md5sum \{\} \;

这为您提供了所有内容的哈希值。

cut -b -32 hashes.txt | sort | uniq -d > dupe_hashes.txt

这将用于cut获取每个文件的哈希，对哈希进行排序，然后找到任何重复的哈希。这些是在dupe_hashes.txt没有附加文件名的情况下写入的。现在我们需要将哈希映射回文件。

(for hash in $(cat dupe_hashes.txt); do
    grep "^$hash" hashes.txt | tail -n +2 | cut -b 35-
done) > dupe_files.txt

这对我来说似乎并不慢。Linux 内核在将此类文件保存在内存中而不是频繁地从磁盘中读取它们方面做得非常好。如果您更愿意将其强制存储在内存中，您可以使用/dev/shm/hashes.txt而不是hashes.txt. 我发现在我的测试中这是不必要的。

这为您提供了每个重复的文件。到目前为止，一切都很好。您可能需要查看此列表。如果您还想列出原始的，请tail -n +2 |从命令中删除该位。

当您对可以删除每个列出的文件感到满意时，您可以将内容通过管道传输到 xargs。这将删除 50 个一组的文件。

xargs -L 50 rm < dupe_files.txt
于 2015-09-30T19:43:45.960 回答
1

我将尝试定性地回答 tmpfs 上的文件存在测试有多快，然后我可以建议您如何使整个程序运行得更快。

首先，tmpfs 目录查找依赖于（在内核中）目录条目缓存哈希表查找，它对目录中的文件数量不那么敏感。它们受到影响，但是是次线性的。这与正确完成哈希表查找需要一些恒定时间这一事实有关O(1)，无论哈希表中的项目数量如何。

test -f为了解释，我们可以看一下[ -f X ]由 coreutils ( gitweb ) 完成的工作：

case 'e':
   unary_advance ();
   return stat (argv[pos - 1], &stat_buf) == 0;
... 
case 'f':                   /* File is a file? */
   unary_advance ();
   /* Under POSIX, -f is true if the given file exists
      and is a regular file. */
   return (stat (argv[pos - 1], &stat_buf) == 0
           && S_ISREG (stat_buf.st_mode));

所以它stat()直接使用文件名。没有明确列出目录test，但运行时stat可能会受到目录中文件数量的影响。调用的完成时间stat将取决于底层文件系统的实现。

对于每个文件系统，stat 会将路径拆分为目录组件，然后向下走。例如，对于 path /tmp/hashes/the_md5：首先/，获取它的 inode，然后在其中查找tmp，获取该 inode（它是一个新的挂载点），然后获取hashesinode，最后是测试文件名及其 inode。您可以期望一直/tmp/hashes/缓存 inode，因为它们在每次迭代中都会重复，因此这些查找速度很快并且可能不需要磁盘访问。每个查找将取决于父目录所在的文件系统。在该/tmp/部分之后，查找发生在 tmpfs 上（这一切都在内存中，除非您内存不足并需要使用交换）。

linux中的tmpfs依赖于simple_lookup获取目录中文件的inode。tmpfs 位于树linux mm/shmem.c中的旧名称下。tmpfs，很像 ramfs，似乎并没有实现自己的数据结构来跟踪虚拟数据，它只是依赖于 VFS 目录条目缓存（在Directory Entry Caches下）。

因此，我怀疑在目录中查找文件的 inode 就像查找哈希表一样简单。我想说，只要你所有的临时文件都适合你的内存，并且你使用 tmpfs/ramfs，那么有多少文件并不重要——每次都是 O(1) 查找。

然而，像 Ext2/3 这样的其他文件系统会产生与目录中存在的文件数量成线性关系的惩罚。

将它们存储在内存中

正如其他人所建议的那样，您还可以通过将 MD5 存储在 bash 变量中来将它们存储在内存中，并避免文件系统（和相关的系统调用）的惩罚。将它们存储在文件系统上的好处是，如果要中断循环，您可以从离开的位置恢复（您的 md5 可能是指向其摘要匹配的文件的符号链接，您可以依赖它，在随后的运行中），但是慢点。

MD5=d41d8cd98f00b204e9800998ecf8427e
let SEEN_${MD5}=1
...
digest=$(md5hash_of <filename>)
let exists=SEEN_$digest
if [[ "$exists" == 1 ]]; then
   # already seen this file
fi

更快的测试

你可以使用[[ -f my_file ]]而不是[ -f my_file ]. 该命令是内置的 bash，并且比为每次比较[[生成一个新进程 ( ) 快得多。/usr/bin/[它会产生更大的不同。

什么是 /usr/bin/[

/usr/bin/test和/usr/bin/[是两个不同的程序，但[(lbracket.c) 的源代码与 test.c 相同（同样在 coreutils 中）：

#define LBRACKET 1
#include "test.c"

所以它们是可以互换的。

于 2015-12-02T02:24:52.900 回答
0

在读取包含散列的文件的内容和在作为散列的文件名目录中查找散列之间的选择基本上归结为“内核在读取目录时更快还是程序在读取文件时更快”。两者都将涉及对每个散列的线性搜索，因此您最终会得到几乎相同的行为。您可能会争辩说内核应该快一点，但余量不会很大。请注意，大多数情况下，线性搜索将是详尽的，因为散列不存在（除非您有很多重复文件）。因此，如果您正在处理几千个文件，则搜索将总共处理几百万个条目——这是二次行为。

如果您有数百或数千个文件，您可能会使用两级层次结构做得更好 - 例如，包含两个字符子目录 00 .. FF 的目录，然后存储名称的其余部分（或全名）在子目录中。terminfo例如，在目录中使用了这种技术的一个小变种。优点是内核只需要读取相对较小的目录来查找文件是否存在。

于 2015-08-04T22:45:58.370 回答
0

我没有“散列”这一点，但我会尝试将你的 md5sum 存储在 bash 散列中。

请参阅如何在 Bash 中定义哈希表？

将 md5sum 存储为键，如果需要，将文件名存储为值。对于每个文件，只需查看密钥是否已存在于哈希表中。如果是这样，您不关心该值，但可以使用它打印出原始重复文件的名称。然后删除当前文件（使用重复键）。不是我开始寻找的 bash 专家。

于 2015-08-06T15:43:27.423 回答