Balancing Spatial Locality with Parallelism in Solid State Disks

Objectives: Modern flash memory based storage systems, such as Solid State Disks (SSDs), are actively utilizing the channel/way interleaving to exploit parallelism among multiple NAND chips. Methods/Statistical Analysis: However, the flip side of the interleaving is that it disperses data with spatial locality across different NAND blocks, which eventually causes a high garbage collection overhead. To overcome this problem, we propose a spatial locality-aware allocation policy, called SLAP. It uses the notion of stream, which is defined as a set of data having consecutive Logical Page Numbers (LPN). Findings: By allocating a stream into a NAND block separately, it can preserve the spatial locality. In addition, by handling multiple streams simultaneously, it can obtain the parallelism among NAND chips. Also, we discuss that SLAP can balance between locality-preserving and parallelism by providing a spectrum from a traditional parallelism-oriented allocation to a strict locality-preserving one. We have implemented SLAP on a page-level mapping Flash Translation Layer (FTL) that is being used as a default FTL in many commercial SSDs. Improvements/Applications: Trace-driven simulation based experimental results have shown that SLAP can improve performance by up to 35.3% with an average of 13.1%, compared with the traditional allocation policy for the three workload considered.