As a sibling comment pointed out, this is about the page (or block) size. Both disks and SSDs share the property that reads are done in a block, 256KB or more. So even if you're reading a few bytes you are actually reading the entire block. In the linear (sequential) read case, you are using it all.
The block size is a parameter in the theoretical model for I/O-efficient computation.
SSDs generally read at the page level, so you can get full performance or close to it from much smaller reads than 256KB or more.
For example, you may be able get maximum performance from 4K or 8K byte reads. Of course, there are a few layers between you and the SSD so you have to make sure you have the SSD actually sees enough pending requests at all times for maximum performance. If you just read one 4K block before submitting the next one, you'll get terrible performance because at queue depth of 1 the SSD is utilized most of the time (i.e., the bandwidth delay product is much lager than 4096 bytes).
This effect can lead the erroneous conclusion that small block sizes are slow when queue depth is actually the confounding factor (large blocks effectively feed many page-sized read requests to the SSD at once, so you can get away with a lower queue depth).
Writes are different but you also don't need gigantic block sizes. For SSDs available as EC2 local storage, for example, a 4K random write load can extract full performance if you get the other parameters right.
Okay. Does this imply that I should see similar SSD read speeds when reading 10 blocks contiguously vs randomly?
If I can fit, say, 2k records into a single block, then I would expect reading the first 4k pieces of data to have similar SSD read performance compared to reading 2k from the first and 2k from the last? (Haven't coded the experiment yet, but that would be the prediction?)
And: to the point of using block size as a parameter, do you have suggestions on further reading for techniques people have used to incorporate that into the design of their structures? Or is it basically the same as efficient paging algorithms?
From my experience as long as you can do that access multithreaded you won't really be penalized for random reads. Single threaded access I've seen as much as read performance halved (used fio for testing), but that didn't translate into multithreaded benchmarks
Just to be a bit pedantic, what you really want is several concurrent IOs, doesn’t have to be multithreaded. For example, io_uring can kick off many concurrent IOs off a single (userspace) thread.
But yes, if you don’t have io_uring you need to use threads, and if you use a lot of them context switches can have a nontrivial overhead from my experience.
> Okay. Does this imply that I should see similar SSD read speeds when reading 10 blocks contiguously vs randomly?
Yes, with some caveats:
1. Not sure if you can read block-aligned data from high-level code.
2. There might be some read-ahead heuristics in the I/O stack.
> techniques people have used to incorporate that into the design of their structures?
I haven't kept up with the research. You can try searching on scholar.google.com for "I/O-efficient" algorithms and data structures. Also "cache-oblivious". There should be some good surveys now, since this is not a new research area.
Note that most of the algorithms that were optimized for disk reads did not typically take into consideration sequential vs random reads. The model simply assumed that reading a block of size B has a unit cost and the performance of algos/ds was expressed in terms of the number of these units.
The block size is a parameter in the theoretical model for I/O-efficient computation.