4 ms·

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly

> The key insight is that file operations in separate directories don’t (for the most part) interfere with each other, enabling parallel execution. i'm clearly missing something here parallel execution helps when operations are cpu bound file operations are (almost always) io bound and totally unclear how directories represent an "interference" boundary bizarre

charcircuit 4y ago
What I would suppose is that it reduces the amount of redundant IO where a directory is edited, flushed to disk, and then later updated again. If all these updates happen in a batch there will be less IO overall.
- preseinger 4y ago
  sure, but the fs cache does all of this kind of stuff for you, right?
mort96 4y ago
Parallel execution absolutely helps when operations are IO bound, if they're more or less independent. Making two network requests in parallel is twice as fast as making them sequentially, if the payload is small enough so that latency dominates and bandwidth is negligible. The question is, how independent are IO operations in separate directories. And the article is claiming that they're fairly independent and don't block each other.
- preseinger 4y ago
  making two io-bound requests in parallel is twice as fast as making them sequentially, only if they don't contend for the same io resource -- bandwidth, disk iops, etc. maybe this is what you mean by independent? but the thing is that in disk io, directory structure is (as far as i know) basically unrelated to relevant contentious resources, when measuring speed maybe if you're doing a billion small files than overhead begins to matter, but copying 3 big files from 3 different directories is gonna take just as long if you do them in parallel vs. if you do them sequentially that may not be true if they're on different disks, but that kind of proves my point, the directory isn't the factor, the underlying disk is > The question is, how independent are IO operations in separate directories. And the article is claiming that they're fairly independent and don't block each other. yeah and in this sense the article is misleading, because (as far as i know) directories are basically unrelated to independence in the general case
imtringued 4y ago
Synchronous file system IO throughput is inversely correlated with latency. If you have a remote network then using multiple connections at the same time allows linear performance improvements until you have maxed out the throughout of your network link or remote filesystem.
- preseinger 4y ago
  yes, or the remote network link, or any middlebox between you and they but this is all a bit tangential as the article is about file system stuff
SUPERCILEX 4y ago
Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory." Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/fast-unix-commands#contention https://alexsaveau.dev/blog/projects/performance/files/fuc/f... --- > file operations are (almost always) io bound This is a common misconception. It was presumably true a decade ago, but PCIe is getting exponentially faster every 3 years: https://arstechnica.com/gadgets/2022/06/months-after-finalizing-pcie-6-0-pci-sig-looks-to-double-speeds-again-with-pcie-7-0/ https://arstechnica.com/gadgets/2022/06/months-after-finaliz... The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s. Assuming a single core can produce 64 bytes (an entire cache line!) per cycle running at 5GHz, you're still only at 320/512=62.5% saturation. This napkin math is a little BS, but my point is that individual cores are quickly going to be outpaced by bandwidth availability. > and totally unclear how directories represent an "interference" boundary To add a bit more color here, it depends on how your file system is implemented. I belive Windows stores every file's metadata in a global database, so segmenting operations by directory yields no benefits. On the other hand, Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory. [1]: https://en.wikipedia.org/wiki/NVM_Express#Comparison_with_AHCI https://en.wikipedia.org/wiki/NVM_Express#Comparison_with_AH...
- preseinger 4y ago
  > The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s is disk IO bottlenecked by NVMe/PCIe limits, or by disk iops limits? > Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory. again, you're handwaving on what "interfere" means do "inode mappings" represent resources with no shared resource constraints? is reading one "inode mapping" as fast as you can with one core independent from reading a different "inode mapping" as fast as you can with a separate core? afaik it is not, am i wrong?

charcircuit 4y ago

What I would suppose is that it reduces the amount of redundant IO where a directory is edited, flushed to disk, and then later updated again. If all these updates happen in a batch there will be less IO overall.

preseinger 4y ago
sure, but the fs cache does all of this kind of stuff for you, right?

mort96 4y ago

Parallel execution absolutely helps when operations are IO bound, if they're more or less independent. Making two network requests in parallel is twice as fast as making them sequentially, if the payload is small enough so that latency dominates and bandwidth is negligible. The question is, how independent are IO operations in separate directories. And the article is claiming that they're fairly independent and don't block each other.

preseinger 4y ago
making two io-bound requests in parallel is twice as fast as making them sequentially, only if they don't contend for the same io resource -- bandwidth, disk iops, etc. maybe this is what you mean by independent? but the thing is that in disk io, directory structure is (as far as i know) basically unrelated to relevant contentious resources, when measuring speed maybe if you're doing a billion small files than overhead begins to matter, but copying 3 big files from 3 different directories is gonna take just as long if you do them in parallel vs. if you do them sequentially that may not be true if they're on different disks, but that kind of proves my point, the directory isn't the factor, the underlying disk is > The question is, how independent are IO operations in separate directories. And the article is claiming that they're fairly independent and don't block each other. yeah and in this sense the article is misleading, because (as far as i know) directories are basically unrelated to independence in the general case

imtringued 4y ago

Synchronous file system IO throughput is inversely correlated with latency. If you have a remote network then using multiple connections at the same time allows linear performance improvements until you have maxed out the throughout of your network link or remote filesystem.

preseinger 4y ago
yes, or the remote network link, or any middlebox between you and they but this is all a bit tangential as the article is about file system stuff

SUPERCILEX 4y ago

Added a small clarification: "The intuition here is that directories are a shared resource for their direct children and must therefore serialize concurrent directory-modifying operations, causing contention. In brief, file creation or deletion cannot occur at the same time within one directory." Plus accompanying benchmark: https://alexsaveau.dev/blog/projects/performance/files/fuc/fast-unix-commands#contention https://alexsaveau.dev/blog/projects/performance/files/fuc/f... --- > file operations are (almost always) io bound This is a common misconception. It was presumably true a decade ago, but PCIe is getting exponentially faster every 3 years: https://arstechnica.com/gadgets/2022/06/months-after-finalizing-pcie-6-0-pci-sig-looks-to-double-speeds-again-with-pcie-7-0/ https://arstechnica.com/gadgets/2022/06/months-after-finaliz... The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s. Assuming a single core can produce 64 bytes (an entire cache line!) per cycle running at 5GHz, you're still only at 320/512=62.5% saturation. This napkin math is a little BS, but my point is that individual cores are quickly going to be outpaced by bandwidth availability. > and totally unclear how directories represent an "interference" boundary To add a bit more color here, it depends on how your file system is implemented. I belive Windows stores every file's metadata in a global database, so segmenting operations by directory yields no benefits. On the other hand, Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory. [1]: https://en.wikipedia.org/wiki/NVM_Express#Comparison_with_AHCI https://en.wikipedia.org/wiki/NVM_Express#Comparison_with_AH...

preseinger 4y ago
> The NVMe protocol has extremely deep queues [1] and leaving them empty means leaving performance on the table. I think you'll find it surprisingly difficult to saturate the PCIe bus with just one core: PCIe 7 will support 512GB/s is disk IO bottlenecked by NVMe/PCIe limits, or by disk iops limits? > Unix FSs tend to store file_name to inode mappings per directory, so creating a new mapping in one directory doesn't interfere with another directory. again, you're handwaving on what "interfere" means do "inode mappings" represent resources with no shared resource constraints? is reading one "inode mapping" as fast as you can with one core independent from reading a different "inode mapping" as fast as you can with a separate core? afaik it is not, am i wrong?