Part 5 of 7 · 4 min read
Random and sequential
Think of a postman. Delivering 100 letters to one street takes one trip. Delivering 100 letters to 100 different towns takes 100 trips, and the postman spends the day driving. The analogy stops in one place: on a disk the distance between two requests changes the wait only through the seek, and a short seek is cheap.
In plain words: A sequential workload reads blocks that are next to each other, so the arm moves once and the data then streams past the head. A random workload jumps to a new place for each request, so it pays the full fixed cost every time. On the made-up drive, random 4 KiB reads give 0.31 MB/s and sequential reads give 98.70 MB/s, a ratio of about 318. OSTEP shows the same shape on two real Seagate drives of its time: about 0.66 and 0.31 MB/s random against 125 and 105 MB/s sequential.
A worked example. An application must read 1 GiB, which is 1,073,741,824 bytes. At the sequential rate of 98.70 MB/s the read takes about 10.9 s. In 4 KiB random reads it takes 262,144 reads at 13.208 ms each, which is about 3,462 s, or 58 minutes. The data and the drive are the same. Only the access pattern changed.
The key lines. A program can measure the gap. It opens a file with O_DIRECT, which skips the page cache, reads 20,000 blocks of 4 KiB in order, and then reads 20,000 blocks at random positions.
#define _GNU_SOURCE
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#define BLK 4096
#define N 20000
static double now(void) {
struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
return t.tv_sec + t.tv_nsec / 1e9;
}
int main(int argc, char **argv) {
if (argc < 2) return 1;
int fd = open(argv[1], O_RDONLY | O_DIRECT);
if (fd < 0) { perror("open"); return 1; }
long blocks = lseek(fd, 0, SEEK_END) / BLK;
char *buf; if (posix_memalign((void **)&buf, BLK, BLK)) return 1;
srand(1);
double t0 = now();
for (long i = 0; i < N; i++)
if (pread(fd, buf, BLK, (long)(i % blocks) * BLK) != BLK) { perror("seq"); return 1; }
double ts = now() - t0;
t0 = now();
for (long i = 0; i < N; i++)
if (pread(fd, buf, BLK, ((long)rand() % blocks) * BLK) != BLK) { perror("rnd"); return 1; }
double tr = now() - t0;
printf("sequential: %.1f MB/s (%.1f us per read)\n", N * (double)BLK / ts / 1e6, ts / N * 1e6);
printf("random: %.1f MB/s (%.1f us per read)\n", N * (double)BLK / tr / 1e6, tr / N * 1e6);
return 0;
}
On the test machine, with a 1 GiB file of random bytes, two runs printed:
sequential: 115.9 MB/s (35.4 us per read)
random: 83.0 MB/s (49.3 us per read)
sequential: 115.1 MB/s (35.6 us per read)
random: 119.8 MB/s (34.2 us per read)
The gap is small and it changes between runs. A virtual flash disk has no arm and no spinning platter, so a random read costs about the same as a sequential one. On a real spinning disk the same program would show a gap of two orders of magnitude.
Sequential and random access
Sequential access reads or writes blocks in order of increasing address, so the device pays the positioning cost once. Random access reads or writes blocks at unrelated addresses, so the device pays the positioning cost for each request.
Example: copying one large video file is sequential. A database that looks up 4 KiB rows by key is random.
Read it as
The advice of every disk textbook is one sentence. If the I/O cannot be sequential, make each request as large as possible, because that spreads the fixed cost over more bytes.
Check yourself:
1. Why does the same read of 1 GiB take 58 minutes in one pattern and 11 seconds in another?
2. Why does O_DIRECT matter in the measuring program?
3. Why are the two runs of the test program different from each other?