14 ms·

Yes, sequential I/O bandwidth is closing the gap to memory. [1] The I/O pattern to watch out for, and the biggest reason why e.g. databases do careful caching t

Yes, sequential I/O bandwidth is closing the gap to memory. [1] The I/O pattern to watch out for, and the biggest reason why e.g. databases do careful caching to memory, is that _random_ I/O is still dreadfully slow. I/O bandwidth is brilliant, but latency is still disappointing compared to memory. Not to mention, in typical Cloud workloads, IOPS are far more expensive than memory. [1]: https://github.com/sirupsen/napkin-math https://github.com/sirupsen/napkin-math

marginalia_nu 4y ago
Depending on how your madvise is set up, it's often the case that sequential disk reads are memory reads. You're typically only paying the price for touching the first page in a sequential run, that or subsequent page faults come at a big discount. If you read 1,000,000 random bytes (~1 Mb) scattered across a huge file (let's say you're fetching from some humongous on-disk hash table), it will to a first order be about as slow as reading 4 Gb sequentially. This will incur the same number of page faults. There are ways of speeding this up, but only so much. Although, I/O is like an onion of caching layers, so in practice this may or may not hold up depending on previous access patterns of the file, lunar cycles, whether venus is in retrograde.
- Sirupsen 4y ago
  `madvise(2)` doesn't matter _that_ much in my experience with [1] on modern Linux kernels. SSD just can't read _quite_ as quickly as memory in my testing. Sure, SSD will be able to re-read a lot into ram, analogous to how memory reading will be able to rapidly prefetch into L1. I get ~30 GiB/s for threaded sequential memory reads, but ~4 GiB/s for SSD. However, I think the SSD number is single-threaded and not even with io_uring—so I need to regenerate those numbers. It's possible it could be 2-4x better. [1]: https://github.com/sirupsen/napkin-math https://github.com/sirupsen/napkin-math
  - marginalia_nu 4y ago
    I think the effects of madvise primarily crop up in extremely I/O-saturated scenarios, which are rare. Reads primarily incur latency, with a good SSD it's hard to actually run into IOPS limitations and you're not likely to run out of RAM for caching either in this scenario. MADV_RANDOM is usually a pessimization, MADV_SEQUENTIAL may help if you are truly reading sequentially, but may also worsen performance as pages don't linger as long. But as I mentioned, there's caching upon caching, and also protocol level optimizations, and hardware-level considerations (physical block size may be quite large but is generally unknown). It's nearly impossible to benchmark this stuff in a meaningful way. Or rather, it's nearly impossible to know what you are benchmarking, as there are a lot of nontrivially stateful parts all the way down that have real impact on your performance. There are so many moving parts I think the only meaningful disk benchmarks consider whatever application you want to make go faster. Do the change. Is it faster? Great. Is it not? Well at least you learned.
  - menaerus 4y ago
    > I get ~30 GiB/s for threaded sequential memory reads, but ~4 GiB/s for SSD. However, I think the SSD number is single-threaded and not even with io_uring—so I need to regenerate those numbers. It's possible it could be 2-4x better. Assuming that you run the experiments on NVMe SSD which is attached to PCIe 3.0, where theoretical maximum is around 1GB/s per each lane, I am not sure I understand how do you expect to go faster than 4 GiB/s? Isn't that already a theoretical maximum of what you can achieve?
    - formerly_proven 4y ago
      PCIe 4.0 SSDs are pretty common nowadays and are basically limited to what PCIe 4.0 x4 can do (around 7 GB/s net throughput).
      - menaerus 4y ago
        I don't think they're that common. You would have to have quite recentish motherboard and CPU that both support PCIe 4.0. And I'm pretty sure that parent comment doesn't own such a machine because otherwise I'd expect 7-8GB/s figure to be reported in the first place.
      - dagmx 4y ago
        I really doubt they’re that common. They only became available on motherboards fairly recently, and are quite expensive. I’d guess that they’re a small minority of devices at the moment.
        robocat 4y ago
        PCIe 5.0 has just recently started showing up on consumer motherboards. 4.0 might not be common, but surprisingly it is now the previous generation!
    - Sirupsen 4y ago
      You might be very right about that! It's been a while since I did the SSD benchmarks. Glad to hear it's most likely entirely accurate at 4 GiB/s then!
  - shitlord 4y ago
    How'd you measure the maximum memory bandwidth? In Algorithmica's benchmark, the max bandwidth was observed to be about 42 GBPS: https://en.algorithmica.org/hpc/cpu-cache/sharing/ https://en.algorithmica.org/hpc/cpu-cache/sharing/ I'm not sure how they calculated the theoretical limit of 42.4 GBPS, but they have multiple measurements higher than 30 GBPS.
jonstewart 4y ago
Random I/O with NVME is slower than sequential I/O still, but the gap between the two has been narrowed considerably and is quite high in historical/comparative absolute terms. To get close to peak random I/O limits, you need to dispatch a lot of commands in parallel—that’s an I/O idiom that doesn’t really exist in high level languages, and I think that’s where a lot of the challenge is.
- crote 4y ago
  The problem is that a lot of workloads using random I/O have dependencies between the different I/O operations. A database traversing a tree-like index cannot issue the next read until the previous one has finished. You are limited by latency, which for NVMe is still orders of magnitude worse than memory.
  - the8472 4y ago
    Those are rarely the slow ones though. Lots of software simply has not been written to keep IO queues full. They read a bit of data, process it, read the next bit and so on. On a single thread. This makes all kinds of IO (including network) way slower than it has to be. For example a tree-index can be parallelized by walking down different branches. On top of that one can issue a prefetch for the next node (on each branch) while processing the current ones.
    - ilyt 4y ago
      Yup, a lot of software is (was?) written with assumptions that mattered with spinning rust. And even if author didn't intend to, serial code generates serial, dependent IO.
  - jlokier 4y ago
    > A database traversing a tree-like index cannot issue the next read until the previous one has finished. This applies to a single point query in a single tree. The latency is reduced by overlap in obvious ways as soon as you have (1) a range query because it can read multiple subtrees in parallel, or (2) a query that reads multiple indexes in parallel, or (3) multiple queries from the application to the database in parallel. This is why it's useful to design applications to make multiple queries in parallel. Web applications are a great example of this. Most applications where I/O performance matters at all have some natural way to parallelise queries. Less obviously, the interior blocks of a B-tree are a relatively small part of a B-tree. I.e. most of the space is in used leaf blocks. If the database's cache strategy gives preference to interior nodes, and even more preference to nodes closer to the root of a tree, often several interior layers of the tree can fit entirely in RAM and the effect is is to reduce the latency of tree lookups further once the cache is warmed up. Then even in large databases (a few TB), the latency of a single point query is reduced to a one or two read IOPS (because the leaf page to read which contains the query result is calculated from in-memory data). The application-visible query time is very similar to the I/O subsystem's timing characteristics, and a few MQPS are achievable (= "million queries per second"). Not many database engines achieve this, because they were designed in an area where I/O was much slower, but the I/O architecture does support it. Source: Wrote a performance-optimised database engine for blockchain archive data, which is extremely random access (because of hashing), in the multiple terabytes range, and the application is bottlenecked on how many queries per second it can achieve. It's like the ideal case for working on random-access I/O performance :-)
ShredKazoo 4y ago
I thought for SSDs it didn't matter whether data was adjacent on disk?
- crote 4y ago
  Well, yes and no. With spinning rust you have to wait for the sector you want to read to rotate underneath the read head. For a fast 10.000 RPM drive, a single rotation takes 6 milliseconds. This means that for random access the average latency is going to be 3 milliseconds - and even that's ignoring the need to move the read head between different tracks! Sequential data doesn't suffer from this, because it'll be passing underneath the read head in the exact order you want - you can even take the track switching time into account to make this even better. SSDs have a different problem. Due to the way NAND is physically constructed it is only possible to read a single page at a time, and accessing a single page has a latency of a few nanoseconds. This immediately places a lower limit on the random read access time. However, SSDs allow you to send read commands which span many pages, allowing the SSD to reorder the reads in the most optimal way, and do multiple reads in parallel. This means that you only have to pay the random access penalty once - not to mention that you have to issue way fewer commands to the SSD. SSDs try to make this somewhat better by having a very deep command queue: you can issue literally thousands of random reads at once, and the SSD will reorder them for faster execution. Unfortunately this doesn't gain you a lot if your random reads have dependencies, such as when traversing a tree structure, and you are still wasting a lot of effort reading entire pages when you only need a few bytes.
  - ShredKazoo 4y ago
    Interesting, thanks! So it sounds like it's not so much "random" I/O that's slow, but rather "unbatched" I/O or something like that? Curious to hear your thoughts on this thread if you have time to share: https://news.ycombinator.com/item?id=33752870 https://news.ycombinator.com/item?id=33752870
  - jonstewart 4y ago
    You really need an NVME interface to the SSD, though. SATA3 is the bottleneck for SATA SSDs
derefr 4y ago
> _random_ I/O is still dreadfully slow. I/O bandwidth is brilliant, but latency is still disappointing compared to memory. The wondrous thing about modern CPU architectures (e.g. Zen3), though, is all the PCIe lanes you get with them. If you really need high random IOPS, you can now cram 24 four-lane NVMe disks into a commodity server (with PCIe M.2 splitter cards) and saturate the link bandwidth on all of them. Throw them all in a RAID0, and stick a filesystem on them with the appropriate stripe width, and you'll get something that's only about 3x higher-latency for cold(!) random reads, than a read from RAM. (My company provides a data-analytics SaaS product; this is what our pool of [shared multitenant, high concurrency] DB read-replicas look like.)
- Dylan16807 4y ago
  I thought NVMe flash latency was measured in tens of microseconds. 3x RAM would be a fraction of a microsecond, right?
  - derefr 4y ago
    Under ideal conditions, yes. But the 3x difference I see in practice is less about NVMe being just that good; and more about operations against (main) memory getting bottlenecked under high all-cores concurrent access with no cross-workload memory locality to enable any useful cache coherence. And also about memory accesses only being “in play” when a worker thread isn’t context-switched out; while PCIe-triggered NVMe DMA can proceed while the thread has yielded for some other reason. In other words, when measured E2E in the context of a larger work-step (one large enough to be interrupted by a context-switch), the mean, amortized difference between the two types of fetch becomes <3x. Top of my wishlist for future architectures is “more, lower-width memory channels” — i.e. increased intra-CPU NUMAification. Maybe something CXL.mem will roughly simulate — kind of a move from circuit-switched memory to packet-switched memory, as it were.
    - MonaroVXR 4y ago
      How do you figure these things out, do you have special software to look at this?
BulgarianIdiot 4y ago
> Yes, sequential I/O bandwidth is closing the gap to memory. Hilariously meanwhile, RAM has become significantly slower compared to CPU performance, i.e. you spend a disproportionate time to read and write to memory, so despite RAM is faster, CPU is way faster. Which means I/O remains a bottleneck...
PeterZaitsev 4y ago
It is not just about IO itself but all the Processing which Database (or OS) needs to do for cache management, which in OLTP cases can be very significant. If you just need few bytes from that 8K/16K page you have to read there is little way around 2 orders of magnitude difference. What we would really benefit is storage which is efficient in small (cpu cache line) size IO

marginalia_nu 4y ago

Depending on how your madvise is set up, it's often the case that sequential disk reads are memory reads. You're typically only paying the price for touching the first page in a sequential run, that or subsequent page faults come at a big discount. If you read 1,000,000 random bytes (~1 Mb) scattered across a huge file (let's say you're fetching from some humongous on-disk hash table), it will to a first order be about as slow as reading 4 Gb sequentially. This will incur the same number of page faults. There are ways of speeding this up, but only so much. Although, I/O is like an onion of caching layers, so in practice this may or may not hold up depending on previous access patterns of the file, lunar cycles, whether venus is in retrograde.

Sirupsen 4y ago
`madvise(2)` doesn't matter _that_ much in my experience with [1] on modern Linux kernels. SSD just can't read _quite_ as quickly as memory in my testing. Sure, SSD will be able to re-read a lot into ram, analogous to how memory reading will be able to rapidly prefetch into L1. I get ~30 GiB/s for threaded sequential memory reads, but ~4 GiB/s for SSD. However, I think the SSD number is single-threaded and not even with io_uring—so I need to regenerate those numbers. It's possible it could be 2-4x better. [1]: https://github.com/sirupsen/napkin-math https://github.com/sirupsen/napkin-math
- marginalia_nu 4y ago
  I think the effects of madvise primarily crop up in extremely I/O-saturated scenarios, which are rare. Reads primarily incur latency, with a good SSD it's hard to actually run into IOPS limitations and you're not likely to run out of RAM for caching either in this scenario. MADV_RANDOM is usually a pessimization, MADV_SEQUENTIAL may help if you are truly reading sequentially, but may also worsen performance as pages don't linger as long. But as I mentioned, there's caching upon caching, and also protocol level optimizations, and hardware-level considerations (physical block size may be quite large but is generally unknown). It's nearly impossible to benchmark this stuff in a meaningful way. Or rather, it's nearly impossible to know what you are benchmarking, as there are a lot of nontrivially stateful parts all the way down that have real impact on your performance. There are so many moving parts I think the only meaningful disk benchmarks consider whatever application you want to make go faster. Do the change. Is it faster? Great. Is it not? Well at least you learned.
- menaerus 4y ago
  > I get ~30 GiB/s for threaded sequential memory reads, but ~4 GiB/s for SSD. However, I think the SSD number is single-threaded and not even with io_uring—so I need to regenerate those numbers. It's possible it could be 2-4x better. Assuming that you run the experiments on NVMe SSD which is attached to PCIe 3.0, where theoretical maximum is around 1GB/s per each lane, I am not sure I understand how do you expect to go faster than 4 GiB/s? Isn't that already a theoretical maximum of what you can achieve?
  - formerly_proven 4y ago
    PCIe 4.0 SSDs are pretty common nowadays and are basically limited to what PCIe 4.0 x4 can do (around 7 GB/s net throughput).
    - menaerus 4y ago
      I don't think they're that common. You would have to have quite recentish motherboard and CPU that both support PCIe 4.0. And I'm pretty sure that parent comment doesn't own such a machine because otherwise I'd expect 7-8GB/s figure to be reported in the first place.
    - dagmx 4y ago
      I really doubt they’re that common. They only became available on motherboards fairly recently, and are quite expensive. I’d guess that they’re a small minority of devices at the moment.
      - robocat 4y ago
        PCIe 5.0 has just recently started showing up on consumer motherboards. 4.0 might not be common, but surprisingly it is now the previous generation!
  - Sirupsen 4y ago
    You might be very right about that! It's been a while since I did the SSD benchmarks. Glad to hear it's most likely entirely accurate at 4 GiB/s then!
- shitlord 4y ago
  How'd you measure the maximum memory bandwidth? In Algorithmica's benchmark, the max bandwidth was observed to be about 42 GBPS: https://en.algorithmica.org/hpc/cpu-cache/sharing/ https://en.algorithmica.org/hpc/cpu-cache/sharing/ I'm not sure how they calculated the theoretical limit of 42.4 GBPS, but they have multiple measurements higher than 30 GBPS.

jonstewart 4y ago

Random I/O with NVME is slower than sequential I/O still, but the gap between the two has been narrowed considerably and is quite high in historical/comparative absolute terms. To get close to peak random I/O limits, you need to dispatch a lot of commands in parallel—that’s an I/O idiom that doesn’t really exist in high level languages, and I think that’s where a lot of the challenge is.

crote 4y ago
The problem is that a lot of workloads using random I/O have dependencies between the different I/O operations. A database traversing a tree-like index cannot issue the next read until the previous one has finished. You are limited by latency, which for NVMe is still orders of magnitude worse than memory.
- the8472 4y ago
  Those are rarely the slow ones though. Lots of software simply has not been written to keep IO queues full. They read a bit of data, process it, read the next bit and so on. On a single thread. This makes all kinds of IO (including network) way slower than it has to be. For example a tree-index can be parallelized by walking down different branches. On top of that one can issue a prefetch for the next node (on each branch) while processing the current ones.
  - ilyt 4y ago
    Yup, a lot of software is (was?) written with assumptions that mattered with spinning rust. And even if author didn't intend to, serial code generates serial, dependent IO.
- jlokier 4y ago
  > A database traversing a tree-like index cannot issue the next read until the previous one has finished. This applies to a single point query in a single tree. The latency is reduced by overlap in obvious ways as soon as you have (1) a range query because it can read multiple subtrees in parallel, or (2) a query that reads multiple indexes in parallel, or (3) multiple queries from the application to the database in parallel. This is why it's useful to design applications to make multiple queries in parallel. Web applications are a great example of this. Most applications where I/O performance matters at all have some natural way to parallelise queries. Less obviously, the interior blocks of a B-tree are a relatively small part of a B-tree. I.e. most of the space is in used leaf blocks. If the database's cache strategy gives preference to interior nodes, and even more preference to nodes closer to the root of a tree, often several interior layers of the tree can fit entirely in RAM and the effect is is to reduce the latency of tree lookups further once the cache is warmed up. Then even in large databases (a few TB), the latency of a single point query is reduced to a one or two read IOPS (because the leaf page to read which contains the query result is calculated from in-memory data). The application-visible query time is very similar to the I/O subsystem's timing characteristics, and a few MQPS are achievable (= "million queries per second"). Not many database engines achieve this, because they were designed in an area where I/O was much slower, but the I/O architecture does support it. Source: Wrote a performance-optimised database engine for blockchain archive data, which is extremely random access (because of hashing), in the multiple terabytes range, and the application is bottlenecked on how many queries per second it can achieve. It's like the ideal case for working on random-access I/O performance :-)

ShredKazoo 4y ago

I thought for SSDs it didn't matter whether data was adjacent on disk?

crote 4y ago
Well, yes and no. With spinning rust you have to wait for the sector you want to read to rotate underneath the read head. For a fast 10.000 RPM drive, a single rotation takes 6 milliseconds. This means that for random access the average latency is going to be 3 milliseconds - and even that's ignoring the need to move the read head between different tracks! Sequential data doesn't suffer from this, because it'll be passing underneath the read head in the exact order you want - you can even take the track switching time into account to make this even better. SSDs have a different problem. Due to the way NAND is physically constructed it is only possible to read a single page at a time, and accessing a single page has a latency of a few nanoseconds. This immediately places a lower limit on the random read access time. However, SSDs allow you to send read commands which span many pages, allowing the SSD to reorder the reads in the most optimal way, and do multiple reads in parallel. This means that you only have to pay the random access penalty once - not to mention that you have to issue way fewer commands to the SSD. SSDs try to make this somewhat better by having a very deep command queue: you can issue literally thousands of random reads at once, and the SSD will reorder them for faster execution. Unfortunately this doesn't gain you a lot if your random reads have dependencies, such as when traversing a tree structure, and you are still wasting a lot of effort reading entire pages when you only need a few bytes.
- ShredKazoo 4y ago
  Interesting, thanks! So it sounds like it's not so much "random" I/O that's slow, but rather "unbatched" I/O or something like that? Curious to hear your thoughts on this thread if you have time to share: https://news.ycombinator.com/item?id=33752870 https://news.ycombinator.com/item?id=33752870
- jonstewart 4y ago
  You really need an NVME interface to the SSD, though. SATA3 is the bottleneck for SATA SSDs

derefr 4y ago

> _random_ I/O is still dreadfully slow. I/O bandwidth is brilliant, but latency is still disappointing compared to memory. The wondrous thing about modern CPU architectures (e.g. Zen3), though, is all the PCIe lanes you get with them. If you really need high random IOPS, you can now cram 24 four-lane NVMe disks into a commodity server (with PCIe M.2 splitter cards) and saturate the link bandwidth on all of them. Throw them all in a RAID0, and stick a filesystem on them with the appropriate stripe width, and you'll get something that's only about 3x higher-latency for cold(!) random reads, than a read from RAM. (My company provides a data-analytics SaaS product; this is what our pool of [shared multitenant, high concurrency] DB read-replicas look like.)

Dylan16807 4y ago
I thought NVMe flash latency was measured in tens of microseconds. 3x RAM would be a fraction of a microsecond, right?
- derefr 4y ago
  Under ideal conditions, yes. But the 3x difference I see in practice is less about NVMe being just that good; and more about operations against (main) memory getting bottlenecked under high all-cores concurrent access with no cross-workload memory locality to enable any useful cache coherence. And also about memory accesses only being “in play” when a worker thread isn’t context-switched out; while PCIe-triggered NVMe DMA can proceed while the thread has yielded for some other reason. In other words, when measured E2E in the context of a larger work-step (one large enough to be interrupted by a context-switch), the mean, amortized difference between the two types of fetch becomes <3x. Top of my wishlist for future architectures is “more, lower-width memory channels” — i.e. increased intra-CPU NUMAification. Maybe something CXL.mem will roughly simulate — kind of a move from circuit-switched memory to packet-switched memory, as it were.
  - MonaroVXR 4y ago
    How do you figure these things out, do you have special software to look at this?

BulgarianIdiot 4y ago

> Yes, sequential I/O bandwidth is closing the gap to memory. Hilariously meanwhile, RAM has become significantly slower compared to CPU performance, i.e. you spend a disproportionate time to read and write to memory, so despite RAM is faster, CPU is way faster. Which means I/O remains a bottleneck...

PeterZaitsev 4y ago

It is not just about IO itself but all the Processing which Database (or OS) needs to do for cache management, which in OLTP cases can be very significant. If you just need few bytes from that 8K/16K page you have to read there is little way around 2 orders of magnitude difference. What we would really benefit is storage which is efficient in small (cpu cache line) size IO