BLOCS: Block Correlation Aware Sequential Pattern Mining based Caching Algorithm for Hybrid Storages

Lee， Seong-jin; Youjip Won

Journal of The Korea Society of Computer and Information

Abbr : JKSCI
2014, 19(7), pp.113-130
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Lee， Seong-jin ¹, Youjip Won ²

¹한양대학교
²한양대학교

ABSTRACT

In this paper, we propose BLOCS algorithm to find sequence of data that should be saved incache device of hybrid storage system which uses SSD as a cache device. BLOCS algorithm whichuses a sequence pattern mining scheme, creates a set of frequently requested sectors with respectto requested order of sectors. To compare the performance of the proposed scheme, we introduce Distance (DIST) based scheme, Request Frequency (FREQ) based scheme, and Frequency timesSize (F-S) based scheme. We measure the hit ratio and I/O latency of different caching schemesusing hybrid storage caching simulator. We acquired booting workload along with ten scenarios oflaunching applications and use the workloads as input to the cache simulator. After experimentwith booting workload, we find that BLOCS scheme gives hit ratio of 61% which is about 15%higher than the least performing DIST scheme.
KEYWORDS

Sequence patternMining, Caching Algorithm, Hybrid Storage, Cache Simulator
REFERENCES (22)

[web] Seagate / Desktop HDD ST4000DM000specification / http://www.seagate.com/internal-hard-drives/desktop-hard-drives/desktop-hdd

[web] Samsung / 512GB 2.5-inch SSD 840 pro series / http://www.samsung.com/us/computer/memory-storage/MZ-7PD512BW-specs

[other] Samsung / 2006 / 1g x 8 bit / 2g x 8 bit / 4g x 8 bit NAND flash memory (K9K8G08U0A)

[other] Samsung / 2007 / 1g x 8 bit / 2g x 8 bit NAND flash memory (k9lag08u1a)

[web] Samsung / What is V-NAND and how is it different to existing technology? / http://www.samsung.com/global/business/semiconductor/html/product/flash-solution/vnand/overview.html

[web] / High-Capacity SSDs Finally Match the per-GB Prices of Smaller SSDs / http://dealnews.com/features/High-Capacity-SSDs-Finally-Match-the-per-GB-Prices-of-Smaller-SSDs/622014.html

[web] / Solid-State Drives Will Complement, Not Replace / Hard-Disk Drives in Data Centers / https://www.gartner.com/doc/2427717/solidstate-drives-complement-replace-harddisk

[journal] Jae-Duk Lee / 2002 / Effects of floating-gate interference on NAND flash memory cell operation / Electron Device Letters / IEEE 23 : 264~266

[confproc] T. Kgil / 2008 / Improving NAND Flash Based Disk Caches / Computer Architecture, 2008. ISCA '08. 35th International Symposium on

[confproc] J. -W. Hsieh / 2007 / Energy-efficient and performance enhanced disks using flash-memory cache / presented at the Proceedings of the 2007international symposium on Low power electronics and design

[confproc] T. Bisson / 2007 / Reducing Hybrid Disk Write Latency with Flash-Backed I/O Requests / Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2007. MASCOTS '07. 15th International Symposium on : 402~409

[confproc] Y. Joo / 2009 / Improving application launch times with hybrid disks / presented at the Proceedings of the 7th IEEE/ACM international conference on Hardware/software codesign and system synthesis : 373~382

[confproc] Y. Joo / 2011 / FAST: quick application launch on solid-state drives / presented at the Proceedings of the 9th USENIX conference on File and storage technologies : 19~

[confproc] R. Koller / 2013 / Write policies for host-side flash caches / presented at the Proceedings of the 11th USENIX conference on File and Storage Technologies : 45~58

[confproc] D. A. Holland / 2013 / Flash caching on the storage client / USENIX ATC'13 Proceedings of the 2013USENIX conference on Annual Technical Conference : 127~138

[journal] M. Zaki / 2001 / SPADE: An Efficient Algorithm for Mining Frequent Sequences / Machine Learning 42(1-2) : 31~60

[confproc] J. Ayres / 2002 / Sequential PAttern mining using a bitmap representation / presented at the Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining : 429~435

[confproc] X. Yan / 2003 / CloSpan:Mining Closed Sequential Patterns in Large Datasets / In proceedings of the third SIAM International conference on data mining : 166~177

[confproc] Z. Li / 2004 / C-Miner: mining block correlations in storage systems / Proceedings of the 3rd USENIX conference on File and storage technologies : 13~

[web] / DiskMon / http://technet.microsoft.com/en-us/sysinternals/bb896646.aspx

[web] / NTFSInfo / http://technet.microsoft.com/en-us/sysinternals/bb897424

[report] California Software Labs / 2002 / I/O file system filter driver for Windows NT / CSWL INC
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools