DS-Cache: A Refined Directory Entry Lookup Cache with Prefix-Awareness for Mobile Devices
Lei Han1,a, Bin Xiao1,b, Xuwei Dong2, Zhaoyan Shen3 and Zili Shao4
1Department of Computing, The Hong Kong Polytechnic University
acslhan@comp.polyu.edu.hk
bcsbxiao@comp.polyu.edu.hk
2School of Computer Science, Northwestern Polytechnical University
dongxuwei@mail.nwpu.edu.cn
3School of Computer Science and Technology, Shandong University
shenzhaoyan@sdu.edu.cn
4Department of Computer Science and Engineering, The Chinese University of Hong Kong
shao@cse.cuhk.edu.hk
ABSTRACT
Our modern devices are filled with files, directories upon directories. Applications generate huge I/O activities in mobile devices. Directory cache is adopted to accelerate file lookup operations in the virtual file system. However, the original directory cache recursively walks all the components of a path for each lookup, leading to inefficient lookup performance and lower cache hit ratio. In this paper, we for the first time fully investigate the characteristics of the directory entry lookup in mobile devices. Based on our findings, we further propose a new directory cache scheme, called Dynamic Skipping Cache, which adopts an ASCII-based hash table to simplify the path lookup complexity by skipping the common prefixes of paths. We also design a novel lookup scheme to optimize the directory cache hit ratio. We have implemented and deployed DS-Cache on a Google Nexus 6P smartphone. Experimental results show that we can significantly reduce the latency of invoking system calls by up to 57.4%, and further reduce the completion time of realworld mobile applications by up to 64%.
Keywords: Mobile devices, Directory cache, Lookups.
