Interleaving (disk storage)
In disk storage and drum memory, interleaving is a technique used to improve access performance of storage by putting data accessed sequentially into non-sequential sectors. The number of physical sectors between consecutive logical sectors is called the interleave skip factor or skip factor.[1][2]
Historically, interleaving was used in ordering block storage on storage devices such as drums, floppy disk drives and hard disk drives. The primary purpose of interleaving was to adjust the timing differences between when the computer was ready to transfer data, and when that data was actually arriving at the drive head to be read. Interleaving was very common prior to the 1990s, but faded from use as processing speeds increased. Modern disk storage is not interleaved.
Interleaving was used to arrange the sectors in the most efficient manner possible, so that after reading a sector, time would be permitted for processing, and then the next sector in sequence is ready to be read just as the computer is ready to do so. Matching the sector interleave to the processing speed therefore accelerates the data transfer, but an incorrect interleave can make the system perform markedly slower.
Information is commonly stored on disk storage in very small pieces referred to as sectors or blocks. These are arranged in concentric rings referred to as tracks across the surface of each disk. While it may seem easiest to order these blocks in direct serial order in each track, such as 1 2 3 4 5 6 7 8 9, for early computing devices this ordering was not practical.
Data to be written or read is put into a special region of reusable memory referred to as a buffer. When data needed to be written, it was moved into the buffer, and then written from the buffer to the disk. When data was read, the reverse took place, transferring first into the buffer and then moved to where it was needed. Most early computers were not fast enough to read a sector, move the data from the buffer to somewhere else, and be ready to read the next sector by the time that next sector was appearing under the read head.
When sectors were arranged in direct serial order, after the first sector was read the computer may spend the time it takes, for example, for three sectors to pass by before it is ready to receive data again. However, with the sectors in direct order, sector two, three, and four have already passed by. The computer doesn't need sectors 4, 5, 6, 7, 8, 9, or 1, and must wait for these to pass by, before reading sector two. This waiting for the disk to spin around to the right spot slows the data transfer rate.
To correct for the processing delays, the ideal interleave for this system would be 1:4, ordering the sectors like this: 1 8 6 4 2 9 7 5 3. It reads sector 1, processes for three sectors whereby 8 6 and 4 pass by, and just as the computer becomes ready again, sector two is arriving just as it is needed.
A 1:1 interleave (skip factor of 0) places the sectors sequentially—1 2 3 4 5 6 ... .
Modern disk storage does not need interleaving. Data is now more commonly stored as clusters which are groups of sectors, and the data buffer is sufficiently large to allow all sectors in a block to be read at once without any delay between sectors.
References
- "Function Requests Specification".
- "Disk 'skip factor' explained". Archived from the original on May 27, 2016.