Disk schedulers for solid state drivers

ABSTRACT

In embedded systems and laptops, flash memory storage such as SSDs (Solid State Drive) have been gaining popularity due to its low energy consumption and durability. As SSDs are flash memory based devices, their performance behavior differs from those of magnetic disks. However, little attention has been paid on how to exploit SSDs from the disk scheduling algorithm view point. In this paper, we first describe behaviors of SSDs that inspires us to design a new disk scheduler for the Linux operating system. Specifically, read service time is almost constant in an SSD while write service time is not. Moreover, appropriate grouping of write requests eliminates any ordering-related restrictions and also maximizes write performance. From these observations, we propose two disk schedulers: IRBW-FIFO and IRBW-FIFO-RP. Both schedulers arrange write requests into bundles of an appropriate size while read requests are independently scheduled. Then, the IRBW-FIFO scheduler provides complete FIFO ordering to each bundle of write requests and each individual read requests while the IRBW-FIFO-RP scheduler gives higher priority to read requests than the bundles of write requests. We implement these schedulers in Linux 2.6.23, and results of executing our set of benchmark programs shows that performance improvements of up to 17% compared to existing Linux disk schedulers are achieved.

REFERENCES

• 1: R. D. Eager and A. M. Lister, Fundamentals of Operating Systems, New York: Springer-Verlag, 1995.
• 2: M. K. McKusick, W. N. Joy, S. J. Leffler and R. S. Fabary, "A Fast File System for UNIX," ACM Transactions on Computer Systems, vol. 2, no. 3, pp. 181--197, 1984.
• 3: E. J. O'Neil, P. E. O'Neil and G. Weikum, "The LRU-K Page Replacement Algorithm For Database Disk Buffering," in Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 297--306.
• 4: T. Johnson, D. Shasha and I. Novell, "2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm," in Proceedings of the 20th International Conference on Very Large Data Bases, pp. 439--450, 1994.
• 5: N. Megiddo and D. S. Modha, "ARC: A Self-Tuning, Low Overhead Replacement Cache," in Proceedings of the 2nd USENIX Conference on File and Storage Technologies, pp. 115--130, 2003.
• 6: S. Jiang and X. Zhang, "LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance," in Proceedings of the 2002 ACM SIGMETRICS, pp. 31--42.
• 7: D. Lee, J. Choi, J. H. Kim, S. H. Noh, S. L. Min and Y. Cho, "LRFU: A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies", IEEE Transactions on Computers, vol. 50, no. 12, pp. 1352--1361, 2001.
• 8: S.-W. Lee, B. Moon, C. Park, J.-M. Kim and S.-W. Kim, "A Case for Flash Memory SSD in Enterprise Database Applications," in Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 1075--1086.
• 9: A. Leventhal, Flash Storage Memory, Communications of the ACM, vol. 51, no. 7, pp. 47--51, July, 2008.
• 10: "512M x 8Bit / 256M x 16Bit NAND Flash Memory (K9K4Gxxx0M) Data Sheets," Samsung Electronics, Co., 2003.
• 11: "1G x 8Bit / 2G x 8Bit NAND Flash memory (K9L8G08U0M) Data Sheets," Samsung Electronics, Co., 2005.
• 12: "Understanding the Flash Translation Layer (FTL) Specification," Intel Corporation, 1998.
• 13: Flash-Memory translation layer for NAND flash (NFTL), M-Systems.
• 14: J. Kim, J. M. Kim, S. H. Noh, S. L. Min and Y. Cho, A Space-efficient Flash Translation Layer for CompactFlash Systems, IEEE Transactions on Consumer Electronics, vol. 28, no. 2, pp. 366--375, 2002.
• 15: M. Rosenblum and J. K. Ousterhout, The Design and Implementation of a Log-Structured File System, ACM Transactions on Computer Systems, vol. 10, no. 1, pp. 26--52, 1992.
• 16: S. W. Lee, D. J. Park, T. S. Chung, D. H. Lee, S. Park and H.-J Song, A Log Buffer based Flash Translation Layer using Fully Associative Sector Translation, ACM Transactions on Embedded Computing Systems, vol. 6, no. 1, Feb., 2007.
• 17: J. H. Yoon, E. H. Nam, Y. J. Seong, H. Kim, B. S. Kim, S. L. Min and Y. Cho, Chameleon: A High Performance Flash/FRAM Hybrid Solid State Disk Architecture, IEEE Computer Architecture Letters, vol. 7, no. 1, pp. 17--20, 2008.
• 18: H. Kim, J. H. Kim, S. Choi, H. Jung and J. Jung, A Page Padding Method for Fragmented Flash Storage, Lecture Notes in Computer Science, vol. 4705, pp. 164--177, 2007.
• 19: H. Kim and S. Ahn, "BPLRU: A Buffer Management Scheme for Improving Random Writes in Flash Storage," in Proceeding of the 6th USENIX Conference on File and Storage Technologies, pp. 239--252, 2008.
• 20: N. Agrawal, V. Prabhakaran, T. Wobber, J. D. Davis, M. Manasse and R. Panigrahy, "Design Tradeoffs for SSD Performance," in Proceedings of the USENIX 2008 Annual Technical Conference, pp. 57--70.
• 21: "Solid State Drive MSP-SATA 7035 3.5-inch Product Specification", MTRON, Co., 2007
• 22: S. Iyer and P. Druschel, "Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O," in Proceedings of the Eighteenth ACM SOSP, pp. 117--130, 2001.
• 23: IOmeter project. http://www.iometer.org/.
• 24: J. Axboe, FIO - Flexible I/O Tester. http://freshmeat.net/projects/fio/.
• 25: F. Chen, D. A. Koufaty and X. Zhang, Understanding Intrinsic Characteristics and System Implications of Flash Memory based Solid State Drives, in Proceedings of the 11th International Joint Conference on Measurement and Modeling of Computer Systems, ACM SIGMETRICS '09, pp. 181--192, 2009.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Design, Experimentation, Performance

Keywords:
Linux, disk scheduler, implementation study, solid state drive