An Efficient Directory Entry Lookup Cache With Prefix-Awareness for Mobile Devices
- 6 March 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 39 (12) , 4575-4586
Abstract
Modern mobile devices, such as smartphones, maintain a directory cache to accelerate directory and file accesses. However, the original directory cache recursively walks through all the components of a path name for each directory entry (dentry) lookup operation, leading to low lookup efficiency. In this paper, we first investigate intrinsic characteristics of dentry lookup operations in smartphones and make several interesting findings: (1) File path lookup operations are called frequently (up to 104 times per second) by mobile applications; (2) File path lookup operations present high temporal and spatial locality; (3) The latency of a file path lookup is linear to the depth of the path name. Based on our findings, we further propose an efficient directory entry lookup cache architecture, named Dynamic Skipping Cache (DS-Cache), which adopts an ASCII-based hash table to simplify the path lookup complexity. In DS-Cache, a dynamic skip lookup algorithm is proposed to skip the common prefixes of different accessing paths. A rename algorithm and a delete algorithm are designed to promise the consistence of DS-Cache and the backend file system. We also design a prefix-aware cache replacement scheme to optimize the DSCache 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 81%, and further reduce the completion time of real-world mobile applications by up to 67%.Keywords
Funding Information
- National Science Foundation for Young Scientists of China (61902218)
- Fundamental Research Funds of Shandong University (2019HW032)
- Shenzhen Science and Technology Foundation (JCYJ20170816093943197)
- National Natural Science Foundation of China (61702357)
- Research Grants Council of the Hong Kong Special Administrative Region, China (GRF 15273616, GRF 15206617, GRF 15224918)
- Direct Grant for Research, The Chinese University of Hong Kong (4055096)
This publication has 29 references indexed in Scilit:
- Enhancement of cooperation between file systems and applications — on VFS extensions for optimized performanceScience China Information Sciences, 2015
- Librispeech: An ASR corpus based on public domain audio books2015
- A Small Non-Volatile Write Buffer to Reduce Storage Writes in Smartphones2015
- Performance analysis and modeling of SQLite embedded databases on flash file systemsDesign Automation for Embedded Systems, 2013
- Direct lookup and hash-based metadata placement for local file systems2013
- A Formal Model of a Virtual Filesystem SwitchElectronic Proceedings in Theoretical Computer Science, 2012
- AndroBench: Benchmarking the Storage Performance of Android-Based Mobile Devices2012
- Learning generative visual models from few training examples: An incremental Bayesian approach tested on 101 object categoriesComputer Vision and Image Understanding, 2007
- The Design of efficient initialization and crash recovery for log-based file systems over flash memoryACM Transactions on Storage, 2006
- NewsWeeder: Learning to Filter Netnews1995