4 ms·

Faster Index I/O with NVMe SSDs

172 points by ingve 1y ago

marginalia_nu 1y ago
I urge you to read the papers and articles I linked at the end if any of this is your jam. They are incredible bangers all of them.
- 6r17 1y ago
  Thanks for sharing this !
kvemkon 1y ago
> 256 KB vs 512 B > A counter argument might be that this drives massive read amplification, For that, one need to know the true minimal block size SSD controller is able to physically read from flash. Asking for less than this wouldn't avoid the amplification.
jeffbee 1y ago
Fun post. One unmentioned parameter is the LBA format being used. Most devices come from the factory configured for 512B, so you can boot NetWare or some other dumb compatibility concern. But there isn't a workload from this century where this makes sense, so it pays to explore the performance impact of the LBA formats your device offers. Using a larger one can mean your device manages io backlogs more efficiently.
kvemkon 1y ago
> 128 KB appears a point of diminishing returns, larger block sizes yield similar or worse performance. Indeed, 128 KB is a well-known long lasted optimal buffer size [1], [2]. Until it has been increased to 256 KB recently (07.04.2024) [3]. [1] https://github.com/MidnightCommander/mc/commit/e7c01c7781dcdfeed5a65047937ee53a7132deba#diff-735970a83320f0b1949304ceaab06d15bb25a788d8ed5f8d524c6f3ff0096377 https://github.com/MidnightCommander/mc/commit/e7c01c7781dcd... [2] https://github.com/MidnightCommander/mc/issues/2193 https://github.com/MidnightCommander/mc/issues/2193 [3] https://github.com/MidnightCommander/mc/commit/933b111a5dc7dfdcce70636173eee45016ea84b2 https://github.com/MidnightCommander/mc/commit/933b111a5dc7d...
- marginalia_nu 1y ago
  I wonder if a more robust option is to peek in the sysfs queue info on Linux. It has some nice information about hardware io operation limits, and also an optimal_io_size hint. https://www.kernel.org/doc/html/v5.3/block/queue-sysfs.html https://www.kernel.org/doc/html/v5.3/block/queue-sysfs.html
- jandrewrogers 1y ago
  This doesn't generalize. In 2014, the common heuristic was 256kB based on measurements in many systems, so the 128kB value is in line with that. At the time, optimal block sizing wasn't that sensitive to the I/O architecture so many people arrived at the same values. In 2024, the optimal block size based on measurement largely reflects the quality and design of your I/O architecture. Vast improvements in storage hardware expose limitations of the software design to a much greater extent than a decade ago. As a general observation, the optimal I/O sizing in sophisticated implementations has been trending toward smaller sizes over the last decade, not larger. The seeming optimality of large block sizes is often a symptom of an I/O scheduling design that can't keep up with the performance of current storage hardware.
  - marginalia_nu 1y ago
    I think what you're trying to accomplish is a factor here. If you just want to saturate the bandwidth, to move some coherent blob of data from point A to point B as fast as possible (say you're implementing the `cp` command), then using large buffers is the best and easiest way. Small buffers confer no additional benefit other than driving more complicated designs, forcing io_uring with registered buffers and fds, etc. If you want to maximize IOPS, then by the fact that we just established that large buffers saturate the bandwidth better, small buffers is the only viable option, but then you need to whittle down the per-read overhead, and end up with io_uring or even more specialized tools.
codeaether 1y ago
Actually, to fully utilize NVME performance, one really need to try to avoid OS overhead by leveraging AsyncIO such as IO_Uring. In fact, 4KB page works quite well if you can issue enough outstanding requests. See a paper from the link below by the TUM folks. https://dl.acm.org/doi/abs/10.14778/3598581.3598584 https://dl.acm.org/doi/abs/10.14778/3598581.3598584
- dataflow 1y ago
  SPDK is what folks who really care about this use, I think.
  - vlovich123 1y ago
    SPDK requires taking over the device. OP is correct if you want to have a multi tenant application where the disk is also used for other things.
    - dataflow 1y ago
      Not an expert on this but I think that's... half-true? There is namespace support which should allow multiple users I think (?), but it does still require direct device access.
      - vlovich123 1y ago
        Namespaces are a hack device manufacturers came up with to try to make this work anyway. Namespaces at the device level are a terrible idea IMP because it’s still not multi tenant - your just carving up a single drive into logically separated chunks that you have to decide on up front. So you have to say “application X gets Y% of the drive while application A gets B%”. It’s an expensive static allocation that’s not self adjusting based on actual dynamic usage.
        deleted 1y ago
        [deleted]
mgerdts 1y ago
> Modern enterprise NVMe SSDs are very fast…. This is a simple benchmark on a Samsung PM9A1 on a with a theoretical maximum transfer rate of 3.5 GB/s. … It should be noted that this is a sub-optimal setup that is less powerful than what the PM9A1 is capable of due to running on a downgraded PCIe link. Samsung has client, datacenter, and enterprise lines. The PM9A1 is part of the OEM client segment and is about the same as a 980 Pro. Its top speeds (about 7GB/s read, 5GB/s write) are better than the comparable datacenter class drive, PM9A3. This top speeds comes with less consistent performance than you get with a PM9A3 or an enterprise drive like a PM1733 from the same era (early PCIe Gen 4 drives).
dataflow 1y ago
Beginner(?) question: why is the model map<term_id, list<pair<document_id, positions_idx>> > inverted_index; and not map<term_id, map<document_id, list<positions_idx>> > inverted_index; (or using set<> in lieu of list<> as appropriate)?
- marginalia_nu 1y ago
  This is to be seen as metaphorical to give a mental model for the actual data structures on disk so there's some tradeoff to finding the most accurate metaphor for what is happening. I actually think you are right, list<pair<...>> is a bit of a weird choice that doesn't quite convey the data structures quite well. Map is better. The most accurate thing would probably be something like map<term_id, map<document_id, pair<document_id, positions_idx>>>, but I corrected it to just a map<document_id, positions_idx> to avoid making things too confusing.
  - sour-taste 1y ago
    Currently it looks like this: map<term_id, map<pair<document_id, positions_idx>> inverted_index; list<positions> positions; Think you also meant to remove the pair in map<pair>?
    - marginalia_nu 1y ago
      Haha, apparently very hard to get this right. Fixed again.
curtisszmania 1y ago
[dead]

172 points by ingve 1y ago

I urge you to read the papers and articles I linked at the end if any of this is your jam. They are incredible bangers all of them.

6r17 1y ago
Thanks for sharing this !

kvemkon 1y ago

> 256 KB vs 512 B > A counter argument might be that this drives massive read amplification, For that, one need to know the true minimal block size SSD controller is able to physically read from flash. Asking for less than this wouldn't avoid the amplification.

jeffbee 1y ago

Fun post. One unmentioned parameter is the LBA format being used. Most devices come from the factory configured for 512B, so you can boot NetWare or some other dumb compatibility concern. But there isn't a workload from this century where this makes sense, so it pays to explore the performance impact of the LBA formats your device offers. Using a larger one can mean your device manages io backlogs more efficiently.

kvemkon 1y ago

> 128 KB appears a point of diminishing returns, larger block sizes yield similar or worse performance. Indeed, 128 KB is a well-known long lasted optimal buffer size [1], [2]. Until it has been increased to 256 KB recently (07.04.2024) [3]. [1] https://github.com/MidnightCommander/mc/commit/e7c01c7781dcdfeed5a65047937ee53a7132deba#diff-735970a83320f0b1949304ceaab06d15bb25a788d8ed5f8d524c6f3ff0096377 https://github.com/MidnightCommander/mc/commit/e7c01c7781dcd... [2] https://github.com/MidnightCommander/mc/issues/2193 https://github.com/MidnightCommander/mc/issues/2193 [3] https://github.com/MidnightCommander/mc/commit/933b111a5dc7dfdcce70636173eee45016ea84b2 https://github.com/MidnightCommander/mc/commit/933b111a5dc7d...

marginalia_nu 1y ago
I wonder if a more robust option is to peek in the sysfs queue info on Linux. It has some nice information about hardware io operation limits, and also an optimal_io_size hint. https://www.kernel.org/doc/html/v5.3/block/queue-sysfs.html https://www.kernel.org/doc/html/v5.3/block/queue-sysfs.html
jandrewrogers 1y ago
This doesn't generalize. In 2014, the common heuristic was 256kB based on measurements in many systems, so the 128kB value is in line with that. At the time, optimal block sizing wasn't that sensitive to the I/O architecture so many people arrived at the same values. In 2024, the optimal block size based on measurement largely reflects the quality and design of your I/O architecture. Vast improvements in storage hardware expose limitations of the software design to a much greater extent than a decade ago. As a general observation, the optimal I/O sizing in sophisticated implementations has been trending toward smaller sizes over the last decade, not larger. The seeming optimality of large block sizes is often a symptom of an I/O scheduling design that can't keep up with the performance of current storage hardware.
- marginalia_nu 1y ago
  I think what you're trying to accomplish is a factor here. If you just want to saturate the bandwidth, to move some coherent blob of data from point A to point B as fast as possible (say you're implementing the `cp` command), then using large buffers is the best and easiest way. Small buffers confer no additional benefit other than driving more complicated designs, forcing io_uring with registered buffers and fds, etc. If you want to maximize IOPS, then by the fact that we just established that large buffers saturate the bandwidth better, small buffers is the only viable option, but then you need to whittle down the per-read overhead, and end up with io_uring or even more specialized tools.

codeaether 1y ago

Actually, to fully utilize NVME performance, one really need to try to avoid OS overhead by leveraging AsyncIO such as IO_Uring. In fact, 4KB page works quite well if you can issue enough outstanding requests. See a paper from the link below by the TUM folks. https://dl.acm.org/doi/abs/10.14778/3598581.3598584 https://dl.acm.org/doi/abs/10.14778/3598581.3598584

dataflow 1y ago
SPDK is what folks who really care about this use, I think.
- vlovich123 1y ago
  SPDK requires taking over the device. OP is correct if you want to have a multi tenant application where the disk is also used for other things.
  - dataflow 1y ago
    Not an expert on this but I think that's... half-true? There is namespace support which should allow multiple users I think (?), but it does still require direct device access.
    - vlovich123 1y ago
      Namespaces are a hack device manufacturers came up with to try to make this work anyway. Namespaces at the device level are a terrible idea IMP because it’s still not multi tenant - your just carving up a single drive into logically separated chunks that you have to decide on up front. So you have to say “application X gets Y% of the drive while application A gets B%”. It’s an expensive static allocation that’s not self adjusting based on actual dynamic usage.
      - deleted 1y ago
        [deleted]

mgerdts 1y ago

> Modern enterprise NVMe SSDs are very fast…. This is a simple benchmark on a Samsung PM9A1 on a with a theoretical maximum transfer rate of 3.5 GB/s. … It should be noted that this is a sub-optimal setup that is less powerful than what the PM9A1 is capable of due to running on a downgraded PCIe link. Samsung has client, datacenter, and enterprise lines. The PM9A1 is part of the OEM client segment and is about the same as a 980 Pro. Its top speeds (about 7GB/s read, 5GB/s write) are better than the comparable datacenter class drive, PM9A3. This top speeds comes with less consistent performance than you get with a PM9A3 or an enterprise drive like a PM1733 from the same era (early PCIe Gen 4 drives).

dataflow 1y ago

Beginner(?) question: why is the model map<term_id, list<pair<document_id, positions_idx>> > inverted_index; and not map<term_id, map<document_id, list<positions_idx>> > inverted_index; (or using set<> in lieu of list<> as appropriate)?

marginalia_nu 1y ago
This is to be seen as metaphorical to give a mental model for the actual data structures on disk so there's some tradeoff to finding the most accurate metaphor for what is happening. I actually think you are right, list<pair<...>> is a bit of a weird choice that doesn't quite convey the data structures quite well. Map is better. The most accurate thing would probably be something like map<term_id, map<document_id, pair<document_id, positions_idx>>>, but I corrected it to just a map<document_id, positions_idx> to avoid making things too confusing.
- sour-taste 1y ago
  Currently it looks like this: map<term_id, map<pair<document_id, positions_idx>> inverted_index; list<positions> positions; Think you also meant to remove the pair in map<pair>?
  - marginalia_nu 1y ago
    Haha, apparently very hard to get this right. Fixed again.

curtisszmania 1y ago

[dead]