这篇科普文章介绍了我们发表在FSE2016的研究工作“Crash consistency validation made easy”[1]。
先设想一个场景:你熬夜写完了论文,终于觉得可以喘一口气,然后舒舒服服地按下了CTRL+S保存文件。就在这时,你家的猫大爷拔掉了你的电源,你的文件还在吗(图片来自网络)?
你肯定会想:这软件那么多用户,那么多专业的程序员,肯定没事吧?最多就是我最后没保存的几个错别字没改过来呗。
这可不一定哦!这个问题更学术一点的定义叫“崩溃一致性(crash consistency)”。这个概念最早出现在文件系统的研究中——文件系统是一个庞大的数据结构,而一个文件操作通常需要对数据结构的多个部分进行修改,因此在诸如断电、系统故障等情况下保持文件系统的一致性就成为了一个挑战。崩溃一致性的基本概念在Remzi的经典教科书“Operating Systems: Three Easy Pieces”[2]中可以找到。
之前的研究工作表明,无论是SSD硬件[3]、数据库系统[4]还是系统软件[5],在现有的文件系统实现(ext4, btrfs, NTFS, ...)上多少都有一些崩溃一致性的问题。连那么厉害的专业程序员、久经考验的开源和商业项目都没搞定的事情,想必遍地的新手程序员们也会犯类似的错误吧(在读完宗师大佬们的文章以后,我的内心就是这么想的)?你猜对了。
事实是,你的文本编辑器真的有可能摧毁你的文件。不仅文本编辑器有这个问题,相当多的其他类型的应用软件也存在这个问题。我们的论文就解决一个问题:
让检测应用程序崩溃一致性bug的过程尽量简单,简单到只要按一个键就可以了。
我是一名苦逼的程序员,为了养家糊口在外包公司做一个文本编辑器的项目。今天我完成的功能是存盘,在按下存盘键以后,将打开的文件保存。小case,我在Stackoverflow上搜索了“Java write file”,然后搞到了如下(简化的)代码:
void writeTextFile(String path, String content) { PrintWriter writer = new PrintWriter(path); writer.write(content); writer.close(); }
作为一名优秀的程序员,我想了想这样好像不太对……万一在write的时候出了什么状况,用户的文件不就丢了么?所以最好先做个备份,肯定就万无一失了。于是我把代码改成了下面这样,跑完测试就愉快地回家逗猫玩了。
void safelyWriteTextFile(String path, String content) { backupPath = path + ".tmp"; writeTextFile(backupPath, content); deleteItem(path); renameItem(backupPath, path); }
然而事情没那么简单。POSIX说,你确实是按照open -> write -> delete -> rename的顺序执行了操作,但我才没有规定从文件系统的角度看,它们是按照你执行的顺序完成的呢!什么?这意味着……
如果系统偷偷调换write和delete操作的顺序,并且在删除操写入磁盘后立即断电,那不就等于把用户的文件给删掉了么?也就是说,如果猫大爷真的在保存文件的时候拔掉了电源,这文件整个就没了啊(论文就没有了啊喂)!更可怕的是,现在的文件系统(比如默认设置下的ext4)因为只保留了元数据的日志而没有保存数据操作的日志,这样的“乱序”是真正能被观察到的[5, 6]!
这段代码来自文本编辑器Ted,所幸的是这个bug成功地被我们的工具检测到。
现在我们有足够的动机去做一个工具检测应用程序的崩溃一致性了。对于程序猿来说,最好的工具就是拿来就能用的工具。所以我们的工具Crash Consistency Checker (C3)只需要被测程序的可执行文件和一个测试用例,方法大致分为3步(对技术细节没有兴趣的可以直接跳过):
运行一遍程序,取得我们认为对于应用来说“正确”的文件系统快照。
什么是“正确”的快照呢?我们认为程序猿不会傻傻地把重要的用户文件删掉。所以,我们认为所有元数据操作执行完毕后,内存中的文件系统快照代表了程序猿定义的“正确”状态。实现上,我们用ptrace拦截程序发出的系统调用,并在系统调用结束后从内存中抓取快照。 回到之前保存文件的例子,“正确”的快照中至少包含一个文件的内容。
使用一个虚拟的磁盘捕获所有的I/O请求,然后生成可能的崩溃现场。这个技术和已有的技术[4,5,6]十分类似。
实现上,我们写了一个ramdisk的驱动,它从外面看表现得和正常的磁盘一模一样,但在后台悄悄记录了所有I/O操作的内容。根据这些I/O操作,就可以生成在Linux设备驱动规约允许条件下的各种崩溃现场。
对于之前保存文件的例子,我们将会得到原文件被删除、备份文件尚未写入的一个文件系统快照。
对每个崩溃现场计算与“正确”文件系统快照的编辑距离,如果距离很大,那这个崩溃现场就看起来很可疑。
两个文件系统快照的编辑距离定义为通过连续内容的删除/移动/重命名操作将一个快照变为另一个的最小次数。不过直接计算这个编辑距离是NP-Complete的,我们用了一些小技巧做了一个近似,求解一个它的下界(我才不会告诉你最后就是给你两个数组A和B,判断能不能把A里删掉一些元素重排以后变成B,现在小学生都会做这个题啦!)。
显然,对于一个没有任何数据的文件系统快照,是无法通过编辑操作变成一个有数据的“正确”快照的,自然就被报告为可疑的bug了。
我们从两大类(命令行工具和生产力工具)挑选了总共25个应用,并对每个应用的一个简单测试用例进行了测试,测试软件在ext4默认设置下的崩溃一致性。结果是我们找到了14个崩溃一致性bug,其中11个是开发者先前未知的bug,让我们看一看:
列举一些有代表性的bug:
在惊讶于这么多程序都有这类bug的同时,我们也对剩下通过测试的应用提出表扬,比如著名的Vim和Emacs。
[1] Y Jiang, H Chen, F Qin, C Xu, X Ma, J Lu. Crash consistency validation made easy. In Proceedings of the Symposium on the Foundations of Software Engineering (FSE), 133--143, 2016.
[2] R H Arpaci-Dusseau, A C Arpaci-Dusseau. Operating Systems: Three Easy Pieces (v0.91), Arpaci-Dusseau Books, 2015.
[3] M Zheng, J Tucek, F Qin, M Lillibridge. Understanding the robustness of SSDS under power fault. In Proceedings of the USENIX Conference on File and Storage Technologies (FAST), 271--284, 2013.
[4] M Zheng, J Tucek, D Huang, F Qin, M Lillibridge, E S Yang, B W Zhao, S Singh. Torturing databases for fun and profit. In Proceedings of the Conference on Operating Systems Design and Implementation (OSDI), 449--464, 2014.
[5] T S Pillai, V Chidambaram, R Alagappan, S Al-Kiswany, A C Arpaci-Dusseau, R H Arpaci-Dusseau. All file systems are not created equal: On the complexity of crafting crash-consistent applications. In Proceedings of the Conference on Operating Systems Design and Implementation (OSDI), 433--448, 2014.
[6] J Yang, C Sar, D Engler. EXPLODE: A lightweight, general system for finding serious storage system errors. In Proceedings of the Conference on Operating Systems Design and Implementation (OSDI), 131--146, 2006.
论文信息:“Crash consistency validation made easy”的 论文 、 会议报告 和 相关代码 。
作者简介:本文作者包括南京大学博士生 蒋炎岩 、俄亥俄州立大学的博士生陈海骋和 秦锋 教授、南京大学的 许畅 、 马晓星 和吕建教授。