Design And Implementation Of Cache Replacement Algorithm Under Faulty Mode

The buffer cache plays an essential role in smoothing the gap between the upper-levelcomputational components and the lower-level storage devices. A good buffer cachemanagement scheme should be beneficial to not only the computational components, butalso to the storage components by reducing disk I/Os. Existing cache replacementalgorithms are well optimized for disks in normal mode, but inefficient under faultyscenarios, such as a parity-based disk array with faulty disk(s).To address this issue, we propose a novel asymmetric buffer cache replacementstrategy, named Victim (or faulty) Disk(s) First (VDF) cache, to improve the reliabilityand performance of a storage system consisting of a buffer cache and disk arrays. Thebasic idea is to give higher priority to cache the blocks on the faulty disks when the diskarray fails, thus reducing the I/Os directed to the faulty disks. AS one request to the failuredisk will be transformed into several requests to the surviving disks by the RAIDalgorithm layer, reducing the I/O request to the failure disk can reduce the total accesstimes to the disks under faulty mode. The bandwidth of RAID is limited, thus thebandwidth saved by VDF can be used by the other application or reconstruction and thenimprove the reliability and service rate.To verify the effectiveness of the VDF cache, we have integrated VDF into twopopular cache algorithms LFU and LRU, named VDF-LFU and VDF-LRU, respectively.We have conducted extensive simulations as well as a prototype implementation. Thesimulation results show that VDF-LFU can reduce disk I/Os to surviving disks by up to42.3%and VDF-LRU can reduce those by up to36.2%. We also apply VDF to Linux kerneland integrate VDF into the replacement algorithm of page-cache. The experimental resultsshow that VDF can reduce the reconstruction time up to17.2%under spare-rebuilding modeand improve the system service rate up to15.9%under degrade mode.