3 ms·

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 bl

by memset 4y ago

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?

gniv 4y ago
> 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.
mamcx 4y ago
You will like this https://ayende.com/blog/posts/series/195587-B/implementing-a-file-pager-in-zig https://ayende.com/blog/posts/series/195587-B/implementing-a... and https://www.reddit.com/r/databasedevelopment/ https://www.reddit.com/r/databasedevelopment/ where it talks about this kind of stuff.
xani_ 4y ago
Someone did test exactly that: https://panthema.net/2019/0322-nvme-batched-block-access-speed/ https://panthema.net/2019/0322-nvme-batched-block-access-spe... 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
- sakras 4y ago
  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.
  - xani_ 4y ago
    Pedantic and wrong, good fucking luck saturating whole SSD from single thread on anything else than pure benchmark code

by memset 4y ago

gniv 4y ago

> 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.

mamcx 4y ago

You will like this https://ayende.com/blog/posts/series/195587-B/implementing-a-file-pager-in-zig https://ayende.com/blog/posts/series/195587-B/implementing-a... and https://www.reddit.com/r/databasedevelopment/ https://www.reddit.com/r/databasedevelopment/ where it talks about this kind of stuff.

xani_ 4y ago

Someone did test exactly that: https://panthema.net/2019/0322-nvme-batched-block-access-speed/ https://panthema.net/2019/0322-nvme-batched-block-access-spe... 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

sakras 4y ago
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.
- xani_ 4y ago
  Pedantic and wrong, good fucking luck saturating whole SSD from single thread on anything else than pure benchmark code