比ls快8倍?百万级文件遍历的奇技淫巧

1.问题背景

在Linux下当我们操作一个文件数较少的目录时,例如执行ls列出当前目录下所有的文件,这个命令可能会瞬间执行完毕,但是当一个目录下有上百万个文件时,执行ls命令会发生什么呢,带着疑问,我们做了如下实验(实验中使用的存储设备为NVMe接口的SSD):

[root@localhost /data1/test_ls]# for i in {1..1000000}; do echo 'AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA' > $i.txt ; done[root@localhost /data1/test_ls]# time ls -l | wc -l1000001real    0m5.802s
user    0m2.544s
sys      0m3.328s

可以看到,统计一个包含1000000个小文件的目录下的文件个数花费了将近6秒的时间,那么文件个数多造成ls缓慢的原因是什么呢,且听我们详细分析。

2.原理分析

众所周知,strace是分析系统调用的利器,所以我们用strace来分析在大目录下执行ls命令的结果,其中这样的输出引起了我们的注意:

...getdents(3, /* 1024 entries */, 32768)  = 32768getdents(3, /* 1024 entries */, 32768)  = 32768getdents(3, /* 1024 entries */, 32768)  = 32768getdents(3, /* 1024 entries */, 32768)  = 32768brk(0)                                  = 0x12e8000brk(0x1309000)                          = 0x1309000getdents(3, /* 1024 entries */, 32768)  = 32768mremap(0x7f93b6246000, 2461696, 4919296, MREMAP_MAYMOVE) = 0x7f93b5d95000getdents(3, /* 1024 entries */, 32768)  = 32768getdents(3, /* 1024 entries */, 32768)  = 32768getdents(3, /* 1024 entries */, 32768)  = 32768brk(0)                                  = 0x1309000brk(0x132a000)                          = 0x132a000...

可以看到,在大目录下执行ls命令会频繁调用getdents这一系统调用,实际上我们通过查看coreutils的ls.c源码可以发现:

ls会首先调用opendir打开一个目录,然后循环调用readdir这个glibc中的函数直到遇到目录流的结尾,也即读完所有的目录项(dentry)为止。我们首先看一下man page里面对于readdir的定义:

struct dirent *readdir(DIR *dirp);

readdir返回一个指向dirent结构体的指针,指向目录流dirp中的下一个目录项,所以在print_dir的循环中,每次从目录流中取出一个目录项并赋值给next变量。既然说到目录流(directory stream),我们顺便看一下glibc中对它的定义:

从上面的定义中可以看到,目录流实则维护一个buffer,这个buffer的大小由allocation来确定,那么问题来了,allocation值什么时候确定,其实是在opendir过程中确定下来的。opendir的调用路径如下所示:

__opendir-->__opendirat-->__alloc_dir

__alloc_dir中,

会分配sizeof(DIR) + allocation大小的内存空间,最后将allocation赋值给目录流dirp的allocation变量。allocation的默认值通过比较4*BUFSIZ的大小和dirent64结构体的大小(<32768)来确定,BUFSIZ的大小在以下几个头文件中定义:

stdio.h:        #define BUFSIZ _IO_BUFSIZ
libio.h:        #define _IO_BUFSIZ _G_BUFSIZ
_G_config.h:    #define _G_BUFSIZ 8192

回看一下strace中的输出,getdents第三个参数以及返回值32768就是这么来的。 讲完目录流的buffer大小是怎么确定的之后,让我们回到readdir的glibc实现。

这段代码的逻辑还是比较清晰的,首先判断目录流的偏移量有没有超过buffer的大小,如果超过,则说明已经读完缓冲区中的所有内容,需要重新调用getdents读取,getdents一次最多读取32768个字节(有_DIRENT_HAVE_D_RECLEN定义时为dirp->allocation),并将读取到的buffer返回给dirp->data,读取到的字节数返回给dirp->size,然后重置偏移量为0。如果没有超过buffer大小,则从dirp->offset开始读,然后将偏移量增加reclen个字节作为下次读取的起点,reclen记录在目录项结构体direntd_reclen变量中,表示当前目录项的长度,dirent(DIRENT_TYPE)这个结构体的定义如下所示:

struct dirent{
    __ino_t d_ino;  /* inode number */
    __off_t d_off;  /* offset to the next dirent */
    unsigned short int d_reclen;   /* length of this record */
    unsigned char d_type;   /* type of file */
    char d_name[256];   /* filename */};

总结一下以上整个过程就是,ls命令每次调用readdir都会从目录流中读取一个目录项,如果目录流的buffer读完,就会重新调用getdents填充这一buffer,下次从新buffer的开头开始读,buffer的默认大小为32K,这也就意味着如果一个目录下有大量的目录项(目录项的总大小可以通过ls -dl查看),则执行ls命令时将会频繁地调用getdents,导致目录下的文件数越多时ls的执行时间越长。

3.解决方法

既然glibc中readdir的buffer大小我们没法控制,何不绕过readdir直接调用getdents,在这个系统调用中我们可以直接控制buffer的大小,以下就是一个简单的例子listdir.c:

在这段代码中,我们将getdents的buffer大小设置为5M,编译执行这段代码,我们得到如下结果:

[root@localhost /data1]# time ./listdir test_rm | wc -l1000016real    0m0.755s
user    0m0.432s
sys     0m0.320s

统计目录中的文件数由默认的5.802s缩短为0.755s,可以看到提升还是较为明显的。

4. 总结

其实不止是ls命令,其他一些命令如rm -r等的实现中都会用到glibc中的readdir函数,所以如果遇到操作百万级文件的大目录这种场景(当然实践中不提倡一个目录下放这么多文件),不妨直接调用getdents并加上自己的一些逻辑,这样就可以在实现标准命令功能的基础上,还能获得其不具备的性能提升。

原文发布于微信公众号 - IT技术精选文摘(ITHK01)

原文发表时间:2018-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java工会

这些快捷键,让你的编码速度快一倍

CTRL+N 查找类 CTRL+SHIFT+N 查找文件 CTRL+SHIFT+ALT+N 查找类中的方法或变量 CIRL+B ...

12910
来自专栏cloudskyme

分布式文件存储的数据库——Mongodb

什么是mongodb MongoDB是一个基于分布式文件存储的数据库。由C++语言编写。旨在为WEB应用提供可扩展的高性能数据存储解决方案。    MongoD...

44260
来自专栏点滴积累

linux下快速列出文件列表的方法

前言 这两天碰到一个很棘手的问题,需要读取出ubuntu系统中某个目录下所有文件,由于服务器中存储的文件实在太多,导致此过程效率十分低下,动辄需要等待一个小时之...

37150
来自专栏DeveWork

解决WordPress 打开Feed页面“This page contains the following errors…”的问题

趁着国庆假,今天解决了 Jeff的阳台 的Geekwork主题的几个bug。其中一个是打开feed页面(即http://www.jianhui.org/feed...

273100
来自专栏程序员互动联盟

【高级编程】Linux read系统调用

最近一个项目做了一个模拟u盘的设备,但是在read虚拟u盘的内容时必须每次都从磁盘内读取,而不是从系统的cache中读取,由于这个问题,就查资料看了下read的...

398110
来自专栏代码GG之家

深入Android源码系列(一)

? 本文讲解内容有 loadLibrary流程 linker ELF ndk开发以及配置调试版本 ndk-...

35460
来自专栏漏斗社区

安全运维中基线检查的自动化

安全运维工作中经常需要进行安全基线配置和检查,所谓的安全基线配置就是系统的最基础的安全配置,类比木桶原理的那块最短的木板,安全基线其实是系统最低安全要求的配置,...

1.9K30
来自专栏java工会

这些快捷键,让你的编码速度快一倍

CTRL+N 查找类 CTRL+SHIFT+N 查找文件 CTRL+SHIFT+ALT+N 查找类中的方法或变量 CIRL+B ...

15830
来自专栏任浩强的运维生涯

nginx关于限制请求数和连接数

nginx轻巧功能强大,能承受几百并发量,ddos攻击几乎没有影响到nginx自身的工作,但是,太多的请求就开始影响后端服务了。所以必须要在nginx做相应的限...

21100
来自专栏杂烩

一种海量日志存储、分析解决方案V1.1 原

针对上一个版本https://my.oschina.net/shyloveliyi/blog/786337,有如下更新:

12030

扫码关注云+社区

领取腾讯云代金券