Interleaving (disk storage)
Arranges sectors non-sequentially to match processing speed.
Interleaving is a method for arranging data on block storage devices like hard drives to boost performance. Instead of storing sequentially accessed data in consecutive sectors, it places them in non-sequential sectors. The gap between these logical sectors is measured by the interleave skip factor, or simply skip factor. This technique was designed to synchronize the moment a program was ready to transfer data with the moment that data actually passed under the drive's read head.
On early storage devices, information is stored in small units called sectors or blocks, arranged in concentric tracks on the disk surface. While a simple sequential order (1, 2, 3, 4…) might seem logical, it was impractical for early computers. Data being read or written is temporarily held in a buffer—a special region of reusable memory. When reading, data moves from the disk into the buffer, then into system RAM. Many early computers were too slow to read a sector, move its data out of the buffer, and be ready for the next sector before that next sector arrived under the read head.
If sectors were in direct order, after reading sector 1, the computer might let sectors 2, 3, and 4 pass by before it was ready again. It would then have to wait for the disk to spin all the way around to sector 2, slowing the transfer rate. To compensate for this processing delay, an interleave of 1:4 could be used, arranging sectors like 1, 8, 6, 4, 2, 9, 7, 5, 3. After reading sector 1, the computer processes it while sectors 8, 6, and 4 pass by, so that sector 2 arrives just as the CPU is ready. A 1:1 interleave (skip factor of 0) places sectors in sequential order.
Historically, interleaving was employed to minimize missed rotations when computers stored instructions on drum memory, and to order block storage on drums, floppy disks, and hard drives. Matching the interleave to the computer's processing speed accelerated data transfer, but a poor interleave could make the system much slower. Interleaving was common before the 1990s but faded as processing speeds increased. Modern disk storage does not use interleaving, and modern operating systems do not apply it to, for example, paging files. Today, data is often stored in clusters (groups of sectors), and buffers are large enough to read all sectors in a block at once with no delay between them.
- Skip factor definition
- The number of physical sectors between consecutive logical sectors.
- Example interleave
- 1:4 interleave orders sectors as 1 8 6 4 2 9 7 5 3.
- 1:1 interleave
- Places sectors sequentially (skip factor of 0).
Lore & Background
Historically, interleaving was used in minimizing missed rotations between instructions on computers storing instructions on drum memory, and in ordering block storage on devices such as drums, floppy disk drives, and hard disk drives. Information is typically stored on disks in small pieces called sectors or blocks, arranged in concentric rings called tracks. While it may be simplest to order blocks directly on each track as 1 2 3 4 5 6 7 8 9, for early computing devices serial ordering was not practical.
Data to be written or read is saved to a special region of reusable memory called a buffer. When data needed to be written, it was moved into the buffer and then written to the disk; when read, the reverse process transferred data first into the buffer and then to system RAM. Most early computers were not fast enough to read a sector, move the data from the buffer to system RAM, and be ready to read the next sector by the time that next sector appeared under the read head. If sectors were arranged in direct order, after the first sector was read, the computer might have several sectors pass under the read head before it was ready to receive data again, forcing a wait for the disk to spin around to the next sector.
To correct for processing delays, the ideal interleave for a given system would be, for example, 1:4, ordering sectors so that after reading sector 1, the computer processes it while three sectors pass by, and when the CPU becomes ready again, sector 2 is arriving just as needed. A 1:1 interleave (skip factor of 0) places sectors sequentially. Interleaving was common prior to the 1990s but faded from use as processing speeds increased.
Reader's Guide
Interleaving was significant because it allowed early storage systems to achieve higher effective data transfer rates by matching the physical layout of sectors to the processing speed of the computer. Without interleaving, a system that was too slow to process a sector before the next one arrived would waste rotations waiting for the desired sector to come around again, dramatically reducing throughput. By choosing an appropriate interleave skip factor, the computer could read a sector, process it while several other sectors passed by, and then have the next needed sector ready just as it became available. An incorrect interleave could make the system perform markedly slower.
Its legacy is that it solved a fundamental timing mismatch between mechanical storage and electronic processing in an era when CPUs and memory buses were far slower than they are today. Modern disk storage is not interleaved; modern operating systems do not use interleaving for, for example, paging files. Modern block storage devices do not require interleaving because data is now commonly stored as clusters (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. The technique thus became obsolete as processing speeds increased and buffer sizes grew.
Did You Know?
- The number of physical sectors between consecutive logical sectors is called the interleave skip factor or skip factor.
- An incorrect interleave can make the system perform markedly slower.
More in Computer Storage 1-24
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced