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.
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.
The only thing SPDK buys you is somewhat lower latency, which isn't that important for most applications because modern high-performance I/O schedulers usually are not that latency sensitive anyway.
The downside of SPDK is that it is unreasonably painful to use in most contexts. When it was introduced there were few options for doing high-performance storage I/O but a lot has changed since then. I know many people that have tested SPDK in storage engines, myself included, but none that decided the juice was worth the squeeze.
OFC, If your block size is large enough and/or your design is batching enough etc. that you already don't spend much time in issuing IO/reaping completion then as you say, SPDK will not provide much of a gain.
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.
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.
As part of the problem domain in index lookups, issuing multiple requests at the same time is not possible, unless as part of some entirely guess-based readahead scheme thay may indeed drive up disk utilization but are unlikely to do much else. Large blocks are a solution with that constraint as a given.
That paper seems to mostly focus on throughput via concurrent independent queries, rather than single-query performance. It's arriving at a different solution because it's optimizing for a different variable.
In most search engines the top few tree layers are in ram cache, and can also have disk addresses for the next levels. So maybe that can let you start some concurrent requests.
Large block reads are just a readahead scheme where you prefetch the next N small blocks. So you are just stating that contiguous readahead is close enough to arbitrary readahead especially if you tune your data structure appropriately to optimize for larger regions of locality.
Well I mean yes, you can use io_uring to read the 128KB blocks as 8 4KB blocks, but that's a very roundabout way of doing it that doesn't significantly improve your performance since with either method, the operation time is more or less the same. If a 128 KB read takes roughly the same time as a 4K read, 8 parallel 4K reads isn't going to be faster with io_uring.
Also, an index with larger block sizes is not equivalent to a structure with smaller block sizes with readahead. The index structure is not the same since having larger coherent blocks gives you better precision in your indexing structure for the same number of total forward pointers, as there's no need to index within each 128 KB block, the forward pointer resolution that would have gone to distinguishing between 4K blocks can instead help you rapidly find the next relevant 128 KB block.
> 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.
> 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).
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.
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.
> 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/e7c01c7781dcd...
[2] https://github.com/MidnightCommander/mc/issues/2193
[3] https://github.com/MidnightCommander/mc/commit/933b111a5dc7d...
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.
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
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.
Thanks for sharing this !
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
SPDK is what folks who really care about this use, I think.
The only thing SPDK buys you is somewhat lower latency, which isn't that important for most applications because modern high-performance I/O schedulers usually are not that latency sensitive anyway.
The downside of SPDK is that it is unreasonably painful to use in most contexts. When it was introduced there were few options for doing high-performance storage I/O but a lot has changed since then. I know many people that have tested SPDK in storage engines, myself included, but none that decided the juice was worth the squeeze.
Depending on the IOPS rate for your app; SPDK can result in less CPU time spent in issuing IO/reaping completions compared to ex. io_uring.
See Ex. https://www.vldb.org/pvldb/vol16/p2090-haas.pdf What Modern NVMe Storage Can Do, And How To Exploit It: High-Performance I/O for High-Performance Storage Engines
for actual data on this.
OFC, If your block size is large enough and/or your design is batching enough etc. that you already don't spend much time in issuing IO/reaping completion then as you say, SPDK will not provide much of a gain.
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.
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.
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.
As part of the problem domain in index lookups, issuing multiple requests at the same time is not possible, unless as part of some entirely guess-based readahead scheme thay may indeed drive up disk utilization but are unlikely to do much else. Large blocks are a solution with that constraint as a given.
That paper seems to mostly focus on throughput via concurrent independent queries, rather than single-query performance. It's arriving at a different solution because it's optimizing for a different variable.
In most search engines the top few tree layers are in ram cache, and can also have disk addresses for the next levels. So maybe that can let you start some concurrent requests.
Large block reads are just a readahead scheme where you prefetch the next N small blocks. So you are just stating that contiguous readahead is close enough to arbitrary readahead especially if you tune your data structure appropriately to optimize for larger regions of locality.
Well I mean yes, you can use io_uring to read the 128KB blocks as 8 4KB blocks, but that's a very roundabout way of doing it that doesn't significantly improve your performance since with either method, the operation time is more or less the same. If a 128 KB read takes roughly the same time as a 4K read, 8 parallel 4K reads isn't going to be faster with io_uring.
Also, an index with larger block sizes is not equivalent to a structure with smaller block sizes with readahead. The index structure is not the same since having larger coherent blocks gives you better precision in your indexing structure for the same number of total forward pointers, as there's no need to index within each 128 KB block, the forward pointer resolution that would have gone to distinguishing between 4K blocks can instead help you rapidly find the next relevant 128 KB block.
4KB is much slower than 512KB if you are using the whole data. Smaller should be better if there is read amplification
> 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.
> 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).
Beginner(?) question: why is the model
and not (or using set<> in lieu of list<> as appropriate)?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.
Currently it looks like this:
list<positions> positions;Think you also meant to remove the pair in map<pair>?
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.