为什么ncdu这么快?
我们组的开发模式是多人共用一台开发机,因此开发机的磁盘空间成了常见问题,三天两头就会出现No space left on device
的错误。
上周磁盘再次爆满,同事使用ncdu
查看磁盘占用情况,发现我就是导致磁盘满的罪魁祸首。他分享的截图类似于下面这样:
我也登上机器,在根目录执行了ncdu
。令我惊讶的是,ncdu
的速度相当快,几乎10秒钟就扫描完了1.3T的磁盘空间。
而平时如果在根目录执行du -sh /
,则需要将近一分钟的时间。这不禁让我好奇:ncdu
为什么这么快?
探索过程
最初我猜想ncdu
是否使用了多线程进行扫描,于是我查看了ncdu
的Release Note
。发现ncdu
直到2.0版本用Zig重写
后才支持多线程扫描。而我使用的是1.20版本,所以并非多线程扫描。随后我又阅读了ncdu
的源码,想看看它是否用了什么神奇的
算法。它扫描文件的核心代码如下:
/* Walks through the directory that we're currently chdir'ed to. *dir contains * the filenames as returned by dir_read(), and will be freed automatically by * this function. */ static int dir_walk(char *dir) { int fail = 0; char *cur; fail = 0; for(cur=dir; !fail&&cur&&*cur; cur+=strlen(cur)+1) { dir_curpath_enter(cur); memset(buf_dir, 0, offsetof(struct dir, name)); memset(buf_ext, 0, sizeof(struct dir_ext)); fail = dir_scan_item(cur); dir_curpath_leave(); } free(dir); return fail; }
代码看起来也平平无奇,就是遍历目录下的文件,然后调用dir_scan_item
扫描文件,无法解释ncdu
为什么这么快。
最后我在Google上搜索了”Why ncdu is fast”,发现有人提出了类似问题:Why is du -sh faster after running ncdu?
看到这个问题时,答案已经呼之欲出了——这是因为Page Cache
的作用。ncdu
本身并不特别快,但当我同事预先使用ncdu
扫描了磁盘后,Page Cache
中已经缓存了部分文件信息,所以当我
第二次执行ncdu
时,只需10秒钟就能完成扫描。
为了验证我的猜想,我使用echo 3 > /proc/sys/vm/drop_caches
清空了Page Cache
,然后再次执行ncdu
。果然,ncdu
的速度和du -sh /
相近,都需要将近一分钟的时间。
在此基础上,我进一步分别测试了:
echo 1 > /proc/sys/vm/drop_caches
(清除页面缓存)
echo 2 > /proc/sys/vm/drop_caches
(清除目录项和inode缓存)
它们的执行时间如下所示:
echo 3 > /proc/sys/vm/drop_caches (60秒)
echo 1 > /proc/sys/vm/drop_caches (60秒)
echo 2 > /proc/sys/vm/drop_caches (16秒)
这是因为ncdu
扫描文件系统时,需要完成两项工作:
- 读取文件夹的内容,获取该文件夹下的文件和inode信息(此时使用page cache,因为文件夹本质上是一种特殊文件)
- 根据文件名,获取inode信息以及文件大小等信息(此时使用dentries和inodes缓存,获取文件大小不需要读取文件内容)
所以当Page Cache
被清空后,ncdu
每次扫描文件都需要重新发起磁盘I/O操作。
而仅清空dentries and inodes cache
后,ncdu
只需要重新获取文件的inode信息,读取量相较于完全清空Page Cache
时少了很多,所以速度会快很多。
为了进一步验证我的猜想,我使用perf
工具对du
进行了性能分析:
sudo perf stat -e major-faults -e minor-faults sudo du -sh /
出乎意料的是,无论Page Cache
是否被清空,du
的major-faults
都是0,而minor-faults
的数量也大体一致。
这似乎表明并没有发生磁盘I/O操作。但是执行速度确实有很大差异,而且CPU的利用率也证实了这一点:缓存被清空后的du
的CPU利用率仅为
20%,而有缓存时的du
的CPU利用率几乎达到100%。这表明当缓存被清空后,CPU的时间主要花在了等待磁盘I/O上。
这个问题困扰了我很久,直到我回顾之前编写xv6
的经验,才意识到page faults
仅仅指的是访问内存时发生的缺页中断次数,只有当使用mmap
时,
Page Cache Miss
和Page faults
才有直接关系。这意味着我花了很长时间,却在测量一个与问题无关的指标。:(
衡量Page Cache的命中率
那么如何正确地衡量Page Cache
的命中率呢?perf工具似乎并没有提供相关的观测手段。此时,我想这是一个绝佳的机会来学习eBPF
——通过hook相关的系统调用,统计Page Cache
的命中率。在DeepSeek的帮助下,我很快就得到了一个eBPF
程序(实现原理类似于cachestat
工具):
#!/usr/bin/env python3 from bcc import BPF from time import sleep, strftime import signal # signal handler def signal_ignore(signal, frame): print() # define BPF program bpf_text = """ #include <uapi/linux/ptrace.h> struct key_t { u32 nf; }; enum { NF_APCL, NF_MPA, NF_MBD, NF_APD, }; BPF_HASH(counts, struct key_t); static int __do_count(void *ctx, u32 nf) { struct key_t key = {}; key.nf = nf; counts.atomic_increment(key); return 0; } int do_count_apcl(struct pt_regs *ctx) { return __do_count(ctx, NF_APCL); } int do_count_mpa(struct pt_regs *ctx) { return __do_count(ctx, NF_MPA); } int do_count_mbd(struct pt_regs *ctx) { return __do_count(ctx, NF_MBD); } int do_count_apd(struct pt_regs *ctx) { return __do_count(ctx, NF_APD); } int do_count_apd_tp(void *ctx) { return __do_count(ctx, NF_APD); } """ # load BPF program b = BPF(text=bpf_text) if BPF.get_kprobe_functions(b'filemap_add_folio'): b.attach_kprobe(event="filemap_add_folio", fn_name="do_count_apcl") else: b.attach_kprobe(event="add_to_page_cache_lru", fn_name="do_count_apcl") if BPF.get_kprobe_functions(b'folio_mark_accessed'): b.attach_kprobe(event="folio_mark_accessed", fn_name="do_count_mpa") else: b.attach_kprobe(event="mark_page_accessed", fn_name="do_count_mpa") # Function account_page_dirtied() is changed to folio_account_dirtied() in 5.15. # Both folio_account_dirtied() and account_page_dirtied() are # static functions and they may be gone during compilation and this may # introduce some inaccuracy, use tracepoint writeback_dirty_{page,folio}, # instead when attaching kprobe fails, and report the running # error in time. if BPF.get_kprobe_functions(b'folio_account_dirtied'): b.attach_kprobe(event="folio_account_dirtied", fn_name="do_count_apd") elif BPF.get_kprobe_functions(b'account_page_dirtied'): b.attach_kprobe(event="account_page_dirtied", fn_name="do_count_apd") elif BPF.tracepoint_exists("writeback", "writeback_dirty_folio"): b.attach_tracepoint(tp="writeback:writeback_dirty_folio", fn_name="do_count_apd_tp") elif BPF.tracepoint_exists("writeback", "writeback_dirty_page"): b.attach_tracepoint(tp="writeback:writeback_dirty_page", fn_name="do_count_apd_tp") else: raise Exception("Failed to attach kprobe %s or %s or any tracepoint" % ("folio_account_dirtied", "account_page_dirtied")) b.attach_kprobe(event="mark_buffer_dirty", fn_name="do_count_mbd") # check whether hash table batch ops is supported htab_batch_ops = True if BPF.kernel_struct_has_field(b'bpf_map_ops', b'map_lookup_and_delete_batch') == 1 else False # header print("%-8s %8s %8s %8s %8s" % ("TIME", "HITS", "MISSES", "DIRTIES", "BUFFDIRTIES")) exiting = 0 while 1: try: sleep(1) except KeyboardInterrupt: exiting = 1 signal.signal(signal.SIGINT, signal_ignore) counts = b["counts"] apcl = 0 mpa = 0 mbd = 0 apd = 0 for k, v in counts.items(): if k.nf == 0: # NF_APCL apcl = max(0, v.value) if k.nf == 1: # NF_MPA mpa = max(0, v.value) if k.nf == 2: # NF_MBD mbd = max(0, v.value) if k.nf == 3: # NF_APD apd = max(0, v.value) misses = apcl - apd total = mpa - mbd hits = total - misses if misses < 0: misses = 0 if total < 0: total = 0 if hits < 0: misses = total hits = 0 if total > 0: ratio = float(hits) / total else: ratio = 0 print("%-8s %8d %8d %8d %8d" % (strftime("%H:%M:%S"), hits, misses, apd, mbd)) counts.clear() if exiting: print("Detaching...") exit()
通过这个程序,我清楚地观察到:当冷启动ncdu
时,会有大量的Cache Miss;而当Page Cache
被预热后,几乎所有的访问都是Hit。这也完美解释了为什么ncdu
第二次扫描会如此快速。
总结
正如jyy在南大操作系统课上所说,计算机没有魔法,它本质上就是一个状态机,一切都可以找到一个解释。
Don’t panic, just Keep calm and Debug on.