9 ms·

Ordering Requests to Accelerate Disk I/O

46 points by pkolaczk 6y ago

the8472 6y ago
A few things that can make walking HDDs by physical layout even faster: * also do it when walking directories! on ext4 you can FIEMAP the directories while walking them. * keep a readahead buffer that spans multiple files, that way you can keep X megabytes in flight even when the files are small * do readaheads on directories (can only be done as root for ext4) * do drop-behind to prevent page cache thrashing * even when writing synchronous code you can use io_uring to batch syscalls such as statx(), open() and fadvise() I wrote crates for some of those points: https://crates.io/crates/platter-walk https://crates.io/crates/platter-walk https://crates.io/crates/reapfrog https://crates.io/crates/reapfrog
- rbanffy 6y ago
  If you keep many accesses in flight simultaneously, you give the OS the chance to reorder your operations to minimize seek times. This is one of the reasons why async disk IO is cool. Even on an SSD, if you group your accesses, you’ll end up reading a flash block only once for all files that live on it, and the same will happen with writing.
  - dataflow 6y ago
    Is this one of those things that hypothetically could happen in the future or are there kernels that actually do this right now?
    - wiml 6y ago
      Reordering disk io requests to minimize seek time and rotational latency has been a standard OS behavior since the 1970s, at least. Whether it's still effective in an SSD+io_uring world I don't know but I'm curious.
      - astrange 6y ago
        If you can issue multiple requests at once then they can go into the SSD controller's queues where it can reorder them, so it is beneficial. As usual with parallelism, it's hard to find if you look for it bottom-up, so running multiple processes is a better way to take advantage of it.
    - doctor_eval 6y ago
      I learned about “elevator algorithms” in CS in the early 90s, well before Linux was a thing... I think it was common even then.
  - tinus_hn 6y ago
    Doesn’t the kernel read a whole flash block regardless of how small a part you request? Seems like the smart thing to do.
    - fulafel 6y ago
      Flash block size generally affects only writing (and things related to that happen on the on-device FTL, not in the kernel, except for embedded raw flash devices that require specialized filesystems). There is a general readahead in Linux though, see eg blkdev(8). For many use cases the small randomish iops rate is the bottleneck (think database index), and because of the small latencies in flash storage you often want to keep the readahead modest absent some detected pattern of sequential io.
Neil44 6y ago
NCQ also tries to do this. I think that’s at block level though rather than whole file level. I’m surprised that giving more commands in parallel made things slower if NCQ was working. https://en.m.wikipedia.org/wiki/Native_Command_Queuing https://en.m.wikipedia.org/wiki/Native_Command_Queuing
- staticassertion 6y ago
  The author actually addresses this in a reddit topic. https://www.reddit.com/r/rust/comments/mk2nz8/ordering_requests_to_accelerate_random_disk_io/gte63ud https://www.reddit.com/r/rust/comments/mk2nz8/ordering_reque... "NCQ does it's best to order all of the outstanding commands at a moment in time (so maybe 32). This is instead submitting the commands in the optimal order to start with." The thread contains more details.
- dale_glass 6y ago
  NCQ has a tiny limit of a maximum of 32 commands. The absolute best case would probably be if you could submit a request for all the blocks in all the files in the directory at once to the hard disk, and let it figure out the optimal order in which to answer. But we don't have such a thing.
PeterisP 6y ago
This brings to mind Knuth's Art of Computer Programming which included algorithms that were optimized for processing data on a physical tape, where (unlike random access memory) the physical ordering and seeking distance and other factors are even more meaningful than for hard drives.
- bombcar 6y ago
  I've heard stories about rewriting computer programs from the era of drum memory to make sure everything synced up with the drum speed - having the next instruction under the read head meant a LOT when otherwise you'd have to wait for a full drum rotation. What's interesting is the improvements made for a specific hardware situation can often end up slowing it down when the assumptions no longer apply (the most obvious example of this is the assumption about access times vs seek times applied to RAM vs spinning disk vs SSD vs NVME, etc). If you're writing code "for the long term" and have optimization routines, it's good to have an option to disable them; perhaps in the future disk will be as fast as RAM (or someone's using a RAMDISK) and disabling optimizations for HDD will help.
  - sliken 6y ago
    Not sure how common that was, but it did gain some amount of fame in "The Story of Mel, a Real Programmer", which is easily to find.
dfox 6y ago
Probably every operating system that can somehow do block IO asynchronously has a layer that tries to sort IO requests to spinning rust disk as to minimize seek distances between the requests. And in fact all of the current "canonical" Unix filesystems even have on-disk layout that is somewhat motivated by minimizing the seek distances (and in fact, this idea is what the first F as in "Fast" in "BSD FFS" stands for).
earthboundkid 6y ago
Spectre and Meltdown but for Disk I/O
tzs 6y ago
I worked at a place in the '90s that was trying to develop products to improve DOS/Windows and Mac performance. One of the things we looked at was I/O reordering. We eventually found that we could do a whole bunch of random I/O to a disk and from the timing infer the underlying disk geometry, the rotation speed, and a reasonable model of seek speed. From that we could predict the fastest order for a given sequence of I/Os. This was a decent performance enhancement, but the step of characterizing the disk took a long time (at least a day or two if I recall correctly), and we decided that consumers would not put up with that and so never turned this into a product. Another thing we played around with was monitoring for files that were consecutive on the disk (and thanks to defraggers that was common) and that tended to be read consecutively, but had places where the reader consistently spent enough time between reads that they would blow a rev on the disk. We would then purposefully refragment that file at those spots, arranging the fragments so that when the reader was ready to issue the next read the disk was in the right position. We decided that would probably be a viable product, but thought we could do better so didn't pursue it much past that. We did later do a Mac degfragger, but without the purposeful fragging of some file, so the time spent on defraggers turned out not to be wasted. The next approach built on the approach of monitoring I/O and looking for things that happened repeatedly and finding ways to optimize those. What we hit on was caching during program launch. This was a time when big GUI apps like browsers, word processors, Photoshop, etc. took 10 seconds or more to start. If we could shave a few seconds off of that it would be very noticeable. When things like that launch, they open and read from many files (the main program file, dynamic libraries it uses, config files, fonts, template files, and who knows what else). For many of these files they are opened and partly read (a header, say), and then other things are read and processed, and then it comes back to that earlier file and reads some more. If you have something that recognizes when a program is launching, looks to see if it is something that it has seen a few times before and that has a lot of the same I/O patterns each launch, and if it does looks at the size of the system's read cache, it can use its knowledge of what I/O will be happening in what order over the next several seconds to preload the cache. For instance, if it knows that the program is going to read a 1 block header on file A, then several seconds latter is going to read another 5 blocks after that header, it can preload the cache with all 6 blocks using a single read of A. This turns out to work quite well. We were knocking something 50% off the launch time off many of the bug GUI programs, sometimes even more. This did become a product and did reasonably well, although it had a stupid name (Superfassst!) [1]. Someone slipped a copy to Jerry Pournelle at Comdex as he went to the meeting where BYTE would decide their Best of Comdex awards, he tried it during the meeting, and it almost became Best Utility. (Later, though, he hit some stability problems, so couldn't fully recommend it). (Search for "superfasst" in this [2] if you want to see his remarks). A few US distributors wanted to distribute it. One was a relatively small, relatively new and unknown distributor who thought our product could be the thing that establishes them. The best deal, though, was offered by one whose previous big product had been one of those RAM doublers. That turned out to be a fraud (VxD that was basically just the sample from the DDK, and an interface that lied). That troubled us, and the explanation they offered is that the developer had lied to them. We would not have believed them...except our CEO/Owner knew that developer, it turned out. The develop had been his co-founder at his previous company. In that company, our owner was in charge of producing the product, which he did by hiring a bunch of people from Caltech (where he had went to school) in Pasadena, while the other guy dealt with the business end of things up in Silicon Valley. The other guy ended up arranging things so that he got most of the money, our owner got almost nothing, and a lot of employees didn't get fully paid. Later that other guy was involved in other sleazy things in Silicon Valley, things where he ended up largely unscathed with others taking the blame or suffering the damage. It was quite believable that he was behind that RAM double fraud and that the business people at their company did not know--that would be par for the course for him. Anyway, we ended up going with them. They wanted a more showy interface, which we added, and they came up with a pretty cool name for the thing: Windrenalin. That got some good reviews [3]. I played around a bit to see if this same sort of thing would work on Linux. I used strace to log activity during several launches of Netscape. Then wrote a Perl script that looked at that, figured out what files were being read, and which parts of them were being read. It would then write out a shell script that consisted of a bunch of cat or dd commands to read the files or the parts of the files in an order that should leave the cache in a good state for Netscape, and then would exec Netscape. Subsequently launching Netscape via that shell script on a freshly booted system was substantially faster than launching Netscape directly. [1] That came about because a Japanese distributor asked us to make a Japanese version of an earlier product of ours, a CD-ROM cache. They gave the Japanese version a Japanese name. When we asked the what that name meant, they said "Superfassst!". Or CEO/Owner inexplicably liked that name, and slapped it on the hard disk accelerator. [2] https://archive.org/stream/eu_BYTE-1997-03_OCR/BYTE-1997-03_OCR_djvu.txt https://archive.org/stream/eu_BYTE-1997-03_OCR/BYTE-1997-03_... [3] https://www.anandtech.com/show/9 https://www.anandtech.com/show/9
eMGm4D0zgUAVXc7 6y ago
Can Java be used to access the FIEMAP or at least inode information to apply this technique in Java software?
- the8472 6y ago
  You can get the inode number with java SE APIs, but not in the way that's necessary to gain performance. On linux you want it during directory iteration from the getdents syscall because that doesn't require opening the file or even grabbing its metadata, just reading the directory entries is enough. If you obtain the inode number by fetching the metadata you're already accessing the inode, defeating a part of the optimization. Maybe there are libraries that will do that. Or if not, project panama will make it easier to just call the relevant libc function.
  - pkolaczk 6y ago
    > If you obtain the inode number by fetching the metadata you're already accessing the inode, defeating a part of the optimization Actually this is what fclones does, because it needs other metadata of the file as well (e.g. its length). I've found fetching metadata is lot faster than reading anything from a file, so most of the gains of this optimization are still there.
    - the8472 6y ago
      Then this should work in java long ino = (Long)Files.getAttribute(file, "unix:ino");
      - eMGm4D0zgUAVXc7 6y ago
        Thanks! :) Will use it!
eps 6y ago
In a similar tone, there is a couple of interesting tools for Windows that measure perfomance impacts of different IO strategies. One is ccsiobench and another is hdtune. [1] https://ccsiobench.com https://ccsiobench.com [2] https://hdtune.com https://hdtune.com
londons_explore 6y ago
It's really sad that just throwing all the requests to the hard drive and letting the hardware decide the most efficient read order doesn't work. Clearly ordering by block address is suboptimal on drives that remap blocks. Drives are also aware that certain seeks take longer than others, and that many reads take less than a full rotation. It's a shame hard drives can't be trusted to just take all the requests and find a neqr-opyimal order to execute them in.
- kevincox 6y ago
  The problem here is that the code doesn't throw all the requests at once. In the previous version they where using a small number of threads which did provide a notable performance increase but issuing ~8 requests at a time doesn't allow for that much reordering. It would be interesting to try a version that used async IO to try and read literally all of the files at the same time and let the kernel send you the data as the disk spins to it.
  - pkolaczk 6y ago
    It would be interesting to try, but probably that wouldn't work as a general-purpose solution. This would require opening all these files at the same time, risking hitting the open-file number limit. Although the limit could be technically raised, I don't think a user would like to do it only to be able to use the tool. Note we're talking about hundreds thousands or even millions of files here.
    - kevincox 6y ago
      Yeah. I would except something to fall over, but it would be interesting to try.
    - londons_explore 6y ago
      But if the disk is presented with a hundred thousand possible blocks to read next, I suspect it'll find pretty much the perfect option. I doubt a million options will be any better.

46 points by pkolaczk 6y ago

A few things that can make walking HDDs by physical layout even faster: * also do it when walking directories! on ext4 you can FIEMAP the directories while walking them. * keep a readahead buffer that spans multiple files, that way you can keep X megabytes in flight even when the files are small * do readaheads on directories (can only be done as root for ext4) * do drop-behind to prevent page cache thrashing * even when writing synchronous code you can use io_uring to batch syscalls such as statx(), open() and fadvise() I wrote crates for some of those points: https://crates.io/crates/platter-walk https://crates.io/crates/platter-walk https://crates.io/crates/reapfrog https://crates.io/crates/reapfrog

rbanffy 6y ago
If you keep many accesses in flight simultaneously, you give the OS the chance to reorder your operations to minimize seek times. This is one of the reasons why async disk IO is cool. Even on an SSD, if you group your accesses, you’ll end up reading a flash block only once for all files that live on it, and the same will happen with writing.
- dataflow 6y ago
  Is this one of those things that hypothetically could happen in the future or are there kernels that actually do this right now?
  - wiml 6y ago
    Reordering disk io requests to minimize seek time and rotational latency has been a standard OS behavior since the 1970s, at least. Whether it's still effective in an SSD+io_uring world I don't know but I'm curious.
    - astrange 6y ago
      If you can issue multiple requests at once then they can go into the SSD controller's queues where it can reorder them, so it is beneficial. As usual with parallelism, it's hard to find if you look for it bottom-up, so running multiple processes is a better way to take advantage of it.
  - doctor_eval 6y ago
    I learned about “elevator algorithms” in CS in the early 90s, well before Linux was a thing... I think it was common even then.
- tinus_hn 6y ago
  Doesn’t the kernel read a whole flash block regardless of how small a part you request? Seems like the smart thing to do.
  - fulafel 6y ago
    Flash block size generally affects only writing (and things related to that happen on the on-device FTL, not in the kernel, except for embedded raw flash devices that require specialized filesystems). There is a general readahead in Linux though, see eg blkdev(8). For many use cases the small randomish iops rate is the bottleneck (think database index), and because of the small latencies in flash storage you often want to keep the readahead modest absent some detected pattern of sequential io.

Neil44 6y ago

NCQ also tries to do this. I think that’s at block level though rather than whole file level. I’m surprised that giving more commands in parallel made things slower if NCQ was working. https://en.m.wikipedia.org/wiki/Native_Command_Queuing https://en.m.wikipedia.org/wiki/Native_Command_Queuing

staticassertion 6y ago
The author actually addresses this in a reddit topic. https://www.reddit.com/r/rust/comments/mk2nz8/ordering_requests_to_accelerate_random_disk_io/gte63ud https://www.reddit.com/r/rust/comments/mk2nz8/ordering_reque... "NCQ does it's best to order all of the outstanding commands at a moment in time (so maybe 32). This is instead submitting the commands in the optimal order to start with." The thread contains more details.
dale_glass 6y ago
NCQ has a tiny limit of a maximum of 32 commands. The absolute best case would probably be if you could submit a request for all the blocks in all the files in the directory at once to the hard disk, and let it figure out the optimal order in which to answer. But we don't have such a thing.

PeterisP 6y ago

This brings to mind Knuth's Art of Computer Programming which included algorithms that were optimized for processing data on a physical tape, where (unlike random access memory) the physical ordering and seeking distance and other factors are even more meaningful than for hard drives.

bombcar 6y ago
I've heard stories about rewriting computer programs from the era of drum memory to make sure everything synced up with the drum speed - having the next instruction under the read head meant a LOT when otherwise you'd have to wait for a full drum rotation. What's interesting is the improvements made for a specific hardware situation can often end up slowing it down when the assumptions no longer apply (the most obvious example of this is the assumption about access times vs seek times applied to RAM vs spinning disk vs SSD vs NVME, etc). If you're writing code "for the long term" and have optimization routines, it's good to have an option to disable them; perhaps in the future disk will be as fast as RAM (or someone's using a RAMDISK) and disabling optimizations for HDD will help.
- sliken 6y ago
  Not sure how common that was, but it did gain some amount of fame in "The Story of Mel, a Real Programmer", which is easily to find.

dfox 6y ago

Probably every operating system that can somehow do block IO asynchronously has a layer that tries to sort IO requests to spinning rust disk as to minimize seek distances between the requests. And in fact all of the current "canonical" Unix filesystems even have on-disk layout that is somewhat motivated by minimizing the seek distances (and in fact, this idea is what the first F as in "Fast" in "BSD FFS" stands for).

earthboundkid 6y ago

Spectre and Meltdown but for Disk I/O

tzs 6y ago

I worked at a place in the '90s that was trying to develop products to improve DOS/Windows and Mac performance. One of the things we looked at was I/O reordering. We eventually found that we could do a whole bunch of random I/O to a disk and from the timing infer the underlying disk geometry, the rotation speed, and a reasonable model of seek speed. From that we could predict the fastest order for a given sequence of I/Os. This was a decent performance enhancement, but the step of characterizing the disk took a long time (at least a day or two if I recall correctly), and we decided that consumers would not put up with that and so never turned this into a product. Another thing we played around with was monitoring for files that were consecutive on the disk (and thanks to defraggers that was common) and that tended to be read consecutively, but had places where the reader consistently spent enough time between reads that they would blow a rev on the disk. We would then purposefully refragment that file at those spots, arranging the fragments so that when the reader was ready to issue the next read the disk was in the right position. We decided that would probably be a viable product, but thought we could do better so didn't pursue it much past that. We did later do a Mac degfragger, but without the purposeful fragging of some file, so the time spent on defraggers turned out not to be wasted. The next approach built on the approach of monitoring I/O and looking for things that happened repeatedly and finding ways to optimize those. What we hit on was caching during program launch. This was a time when big GUI apps like browsers, word processors, Photoshop, etc. took 10 seconds or more to start. If we could shave a few seconds off of that it would be very noticeable. When things like that launch, they open and read from many files (the main program file, dynamic libraries it uses, config files, fonts, template files, and who knows what else). For many of these files they are opened and partly read (a header, say), and then other things are read and processed, and then it comes back to that earlier file and reads some more. If you have something that recognizes when a program is launching, looks to see if it is something that it has seen a few times before and that has a lot of the same I/O patterns each launch, and if it does looks at the size of the system's read cache, it can use its knowledge of what I/O will be happening in what order over the next several seconds to preload the cache. For instance, if it knows that the program is going to read a 1 block header on file A, then several seconds latter is going to read another 5 blocks after that header, it can preload the cache with all 6 blocks using a single read of A. This turns out to work quite well. We were knocking something 50% off the launch time off many of the bug GUI programs, sometimes even more. This did become a product and did reasonably well, although it had a stupid name (Superfassst!) [1]. Someone slipped a copy to Jerry Pournelle at Comdex as he went to the meeting where BYTE would decide their Best of Comdex awards, he tried it during the meeting, and it almost became Best Utility. (Later, though, he hit some stability problems, so couldn't fully recommend it). (Search for "superfasst" in this [2] if you want to see his remarks). A few US distributors wanted to distribute it. One was a relatively small, relatively new and unknown distributor who thought our product could be the thing that establishes them. The best deal, though, was offered by one whose previous big product had been one of those RAM doublers. That turned out to be a fraud (VxD that was basically just the sample from the DDK, and an interface that lied). That troubled us, and the explanation they offered is that the developer had lied to them. We would not have believed them...except our CEO/Owner knew that developer, it turned out. The develop had been his co-founder at his previous company. In that company, our owner was in charge of producing the product, which he did by hiring a bunch of people from Caltech (where he had went to school) in Pasadena, while the other guy dealt with the business end of things up in Silicon Valley. The other guy ended up arranging things so that he got most of the money, our owner got almost nothing, and a lot of employees didn't get fully paid. Later that other guy was involved in other sleazy things in Silicon Valley, things where he ended up largely unscathed with others taking the blame or suffering the damage. It was quite believable that he was behind that RAM double fraud and that the business people at their company did not know--that would be par for the course for him. Anyway, we ended up going with them. They wanted a more showy interface, which we added, and they came up with a pretty cool name for the thing: Windrenalin. That got some good reviews [3]. I played around a bit to see if this same sort of thing would work on Linux. I used strace to log activity during several launches of Netscape. Then wrote a Perl script that looked at that, figured out what files were being read, and which parts of them were being read. It would then write out a shell script that consisted of a bunch of cat or dd commands to read the files or the parts of the files in an order that should leave the cache in a good state for Netscape, and then would exec Netscape. Subsequently launching Netscape via that shell script on a freshly booted system was substantially faster than launching Netscape directly. [1] That came about because a Japanese distributor asked us to make a Japanese version of an earlier product of ours, a CD-ROM cache. They gave the Japanese version a Japanese name. When we asked the what that name meant, they said "Superfassst!". Or CEO/Owner inexplicably liked that name, and slapped it on the hard disk accelerator. [2] https://archive.org/stream/eu_BYTE-1997-03_OCR/BYTE-1997-03_OCR_djvu.txt https://archive.org/stream/eu_BYTE-1997-03_OCR/BYTE-1997-03_... [3] https://www.anandtech.com/show/9 https://www.anandtech.com/show/9

eMGm4D0zgUAVXc7 6y ago

Can Java be used to access the FIEMAP or at least inode information to apply this technique in Java software?

the8472 6y ago
You can get the inode number with java SE APIs, but not in the way that's necessary to gain performance. On linux you want it during directory iteration from the getdents syscall because that doesn't require opening the file or even grabbing its metadata, just reading the directory entries is enough. If you obtain the inode number by fetching the metadata you're already accessing the inode, defeating a part of the optimization. Maybe there are libraries that will do that. Or if not, project panama will make it easier to just call the relevant libc function.
- pkolaczk 6y ago
  > If you obtain the inode number by fetching the metadata you're already accessing the inode, defeating a part of the optimization Actually this is what fclones does, because it needs other metadata of the file as well (e.g. its length). I've found fetching metadata is lot faster than reading anything from a file, so most of the gains of this optimization are still there.
  - the8472 6y ago
    Then this should work in java long ino = (Long)Files.getAttribute(file, "unix:ino");
    - eMGm4D0zgUAVXc7 6y ago
      Thanks! :) Will use it!

eps 6y ago

In a similar tone, there is a couple of interesting tools for Windows that measure perfomance impacts of different IO strategies. One is ccsiobench and another is hdtune. [1] https://ccsiobench.com https://ccsiobench.com [2] https://hdtune.com https://hdtune.com

londons_explore 6y ago

It's really sad that just throwing all the requests to the hard drive and letting the hardware decide the most efficient read order doesn't work. Clearly ordering by block address is suboptimal on drives that remap blocks. Drives are also aware that certain seeks take longer than others, and that many reads take less than a full rotation. It's a shame hard drives can't be trusted to just take all the requests and find a neqr-opyimal order to execute them in.

kevincox 6y ago
The problem here is that the code doesn't throw all the requests at once. In the previous version they where using a small number of threads which did provide a notable performance increase but issuing ~8 requests at a time doesn't allow for that much reordering. It would be interesting to try a version that used async IO to try and read literally all of the files at the same time and let the kernel send you the data as the disk spins to it.
- pkolaczk 6y ago
  It would be interesting to try, but probably that wouldn't work as a general-purpose solution. This would require opening all these files at the same time, risking hitting the open-file number limit. Although the limit could be technically raised, I don't think a user would like to do it only to be able to use the tool. Note we're talking about hundreds thousands or even millions of files here.
  - kevincox 6y ago
    Yeah. I would except something to fall over, but it would be interesting to try.
  - londons_explore 6y ago
    But if the disk is presented with a hundred thousand possible blocks to read next, I suspect it'll find pretty much the perfect option. I doubt a million options will be any better.