Learn
Lesson · Storage Engines and Indexes · The cost model

Sequential vs Random I/O

A read costs a seek for every place it starts and a byte for every byte it moves. Reading a gigabyte in one sweep is one seek and ten seconds; reading the same gigabyte four kilobytes at a time is a quarter of a million seeks and forty-two minutes. The bytes term never moved, which is why size ÷ bandwidth is a model of one access pattern rather than a model of reading.

time = seeks × t_seek + bytes / bandwidth 1 GB, one sweep 1 seek 10.00 ms + 10.00 s = 10.01 s 1 GB, 4 kB at a time 250 000 seeks 41.7 min + 10.00 s = 41.8 min 250.75× as long crossover chunk = t_seek × bandwidth = 10 ms × 100 MB/s = 1 MB
One formula, two access patterns, and the chunk where the terms are equal

Core ideas

What this lesson establishes

One formula and two readings of it. Every disagreement about storage performance is a disagreement about which of its two terms is doing the work.

1

A read has a fixed cost and a per-byte cost

The first term, seeks × t_seek, is paid once for every place the read starts: the arm moves, the platter turns, nothing is transferred. The second term, bytes/bandwidth, is paid for the bytes themselves. A sequential read of a gigabyte pays the first term once and a 4 kB random read of the same gigabyte pays it 250 000 times. The bytes are identical; the bill is not.

2

The chunk size sets the seek count

Reading B bytes in chunks of c costs ⌈B/c⌉ seeks. At c = 4 kB over a gigabyte that is 250 000 of them, and at 10 ms each they are 2 500 s of waiting against 10 s of transfer. Halving the chunk doubles the first term and leaves the second exactly where it was, which is why the ratio between the two patterns moves so violently.

3

The two terms are equal at one chunk size

Set one seek equal to one chunk of transfer, t_seek = c/bandwidth, and solve: c = t_seek × bandwidth. On a 10 ms, 100 MB/s disk that is 1 MB. Below it the arm decides the time and the size of each read barely matters; above it the bandwidth decides and the seek barely matters. It is one multiplication and it tells you which half of the formula you are in.

The material

Seeks, bytes, and the chunk size between them

Why the same gigabyte is ten seconds or forty-two minutes, and what the number in the middle is.

Definition · Read time

For a read of B bytes issued as s separate accesses on a device with seek time t_seek and sequential bandwidth bw, the read time is s × t_seek + B/bw. A sequential read is the case s = 1. A random read in chunks of c bytes is the case s = ⌈B/c⌉.

There are not two formulas here. What changes between the two rows of any comparison is s, and s is a property of the access pattern rather than of the data or of the device.

The habit worth building is to write the two terms down separately and look at them before adding. 10.00 ms + 10.00 s and 41.7 min + 10.00 s are the same gigabyte off the same disk. The second term is identical in both, to the digit. Every one of those forty-two minutes is first-term.

1 GB = 10⁹ B t_seek = 10 ms bw = 100 MB/s sequential s = 1 1 × 10 ms + 10⁹/10⁸ s = 0.01 s + 10 s = 10.01 s random c = 4 kB, s = 10⁹/4 000 = 250 000 250 000 × 10 ms + 10⁹/10⁸ s = 2 500.00 s + 10 s = 2 510 s ratio 2 510 / 10.01 = 250.75
Example · The same gigabyte on solid state

Hold the gigabyte and the 4 kB chunk and change the device: 100 µs of seek and 500 MB/s of bandwidth. The sequential read is 2.0001 s, the random read is 27 s, and the ratio falls from 250.75 to 13.50. The access pattern still costs more than an order of magnitude. What changed is that it costs thirteen times rather than two hundred and fifty.

Where the two terms are equal

Ask for the chunk size at which one seek costs exactly what one chunk of transfer costs. t_seek = c/bw rearranges to c = t_seek × bw, and the reason the answer is easy to carry around is that it is a multiplication of the two numbers a device is sold on. The disk above gives 10 ms × 100 MB/s = 1 MB; the solid-state device gives 100 µs × 500 MB/s = 50 kB.

Call that chunk c*. Then the whole comparison collapses to one division, because the random time over the sequential time is about 1 + c*/c whenever the sequential read is dominated by its bytes term. On the disk: 1 + 10⁶/4 000 = 251, against the 250.75 the lab computes exactly. At c = c* the ratio is 2; at 64 kB it is 16.61; at 4 MB it is 1.25. One number, c*, generates the entire table.

Example · Faster hardware does not always narrow the gap

The NVMe preset is 20 µs of seek and 3000 MB/s of bandwidth. Its crossover chunk is 60 kB — larger than the SATA device's 50 kB — and its 4 kB ratio is 16.00, slightly worse than the SATA device's 13.50. Bandwidth grew by six and the seek fell by five, and since c* = t_seek × bw the crossover went up. The penalty for a bad access pattern is not a fact about how old the device is.

Bytes on this course are decimal: 1 kB = 1000 B and 1 GB = 10⁹ B. That is not pedantry here, because it moves the headline. The same gigabyte in 4 kB random reads is 250.75 times the sequential time in decimal units and 262.9 times it in binary ones, so a reader checking the figure against their own arithmetic has to know which two hundred and fifty is being quoted. The lab says so on its face.

What the formula does not carry is a queue, a read-ahead, or a second request in flight. A device serving many concurrent random reads overlaps some of the waiting, so the honest form of the claim is that the seek term is work the device must do rather than necessarily time one request must wait. Queues and Utilisation is where waiting under concurrency gets its own arithmetic. The subject here is the work.

Interactive

Sequential against random, in seeks and bytes

One gigabyte is ten seconds or forty-two minutes, and the difference is the seek count

The pattern, not the sizetime = seeks × tseek + bytes / bandwidth, both ways
sequentialrandomcrossover chunklog scale

Method

Pricing an access pattern

Four lines, and the first of them is the whole discipline: count the seeks before you touch the size.

1

Count the seeks first

s = 1 for a sweep, s = ⌈B/c⌉ for chunks of c. This is the only number that distinguishes the two rows of the comparison, so write it down before anything else and the rest is arithmetic.

2

Evaluate the two terms separately

s × t_seek and B/bw, side by side, in the same unit, and do not add them yet. The question you are answering is which one is bigger, and adding first is what hides it.

3

Decide which term you are fighting

If the seek term dominates, more bandwidth buys nothing and a larger chunk buys everything. If the bytes term dominates, the device is already working as hard as it can and the only lever left is reading fewer bytes.

4

Compute c* and place yourself on it

c* = t_seek × bw, then ratio ≈ 1 + c*/c. That is a one-line check on whatever you just computed: at c = c* the ratio is 2, at a tenth of c* it is about 11, and at c*/250 it is about 251.

Seeks, bytes and the crossover

Score 0 / 0

One gigabyte off a 10 ms, 100 MB/s disk

Two rows, one formula, and the difference written out so that it can be pointed at rather than described.

B = 1 GB = 10⁹ B t_seek = 10 ms = 0.01 s bw = 100 MB/s = 10⁸ B/s sequential s = 1 seek term 1 × 0.01 s = 0.01 s bytes term 10⁹ / 10⁸ = 10.00 s total 10.01 s random c = 4 kB, s = 10⁹ / 4 000 = 250 000 seek term 250 000 × 0.01 s = 2 500.00 s bytes term 10⁹ / 10⁸ = 10.00 s total 2 510.00 s = 41.8 min ratio 2 510.00 / 10.01 = 250.75 crossover c* = 0.01 s × 10⁸ B/s = 1 000 000 B = 1 MB check 1 + c*/c = 1 + 10⁶/4 000 = 251 ✓ against 250.75

The bytes term is 10.00 s on both rows. Nothing about the amount of data changed, the disk did not get slower, and the read still took two hundred and fifty times as long.

The check on the last line is worth keeping. ratio ≈ 1 + c*/c is a good approximation whenever the sequential time is dominated by its bytes term, and it turns the whole comparison into one division. It also explains the shape of the lab's table: every halving of the chunk roughly doubles the ratio, until the chunk passes c* and the ratio settles toward 1.

For a faded rehearsal, take the same gigabyte on the SATA solid-state preset — 100 µs and 500 MB/s. The supplied first move is the crossover, c* = 50 kB. From it, predict the 4 kB ratio before computing either time; then compute both times and check the prediction. Then answer the question the numbers exist for: which chunk size on the slider reads the gigabyte in under three seconds? Run the lab at your answer before opening the quiz.

Common mistakes

1
Quoting size ÷ bandwidth as the read timeThat is the second term alone, and it is the whole time only when s = 1. It gives 10 s for a gigabyte that takes 41.8 min on the same hardware — an answer wrong by a factor of two hundred and fifty, produced by a formula that looks like physics. Writing the seek count down first makes the error impossible.
2
Reading a device's specification as its throughput on your workload100 MB/s is what the disk does when s = 1. A workload of 4 kB random reads on that disk moves 10⁹/2 510 ≈ 400 kB/s, and both numbers are true of the same device. The specification is the bandwidth term; your workload chooses the seek term.
3
Assuming newer hardware makes the pattern stop matteringIt shrinks the ratio and never removes it: 250.75 on the spinning disk, 13.50 on the SATA device and 16.00 on the NVMe one, all at 4 kB. The last of those is larger than the one before it, because c* is t_seek × bandwidth and bandwidth grew faster than the seek fell.

Check your understanding

✓
Finish when you reach for the seek count before you reach for the size.

You should be able to price a read both ways on a stated device, compute the crossover chunk in one multiplication, and say, for any workload you are handed, which of the two terms the answer is made of.

Note: The crossover chunk is the first of several numbers on this course that are one multiplication and settle an argument. “The Height of a B-tree” is another: the levels a tree needs are found by multiplying the fanout into an accumulator until it passes the key count, and the answer is a single digit for far more data than anyone expects.

Kept in this browser only, for you. Nothing is sent anywhere and nothing checks it. Carry it to another device.

Feedback and recommendations

Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.

No recommendations yet for this lesson.