[deleted]
Ask HN: Books on designing disk-optimized data structures?
41–50 of 59 posts
Re: Ask HN: Books on designing disk-optimized data structures?
#42Earlier quoted context omitted.
Thank you for this! Here is my question, though. I have an example C program that uses mmap() to read data from a file. It can do this linearly or select random records. I'm running it on my M1 mac. https://gist.github.com/poundifdef/e748c467d354662ed034b5f64... The script runs orders of magnitude slower when I do random reads rather than linear. Theoretically this seems like it should not be the case since it is run…
As a sibling comment pointed out, this is about the page (or block) size. Both disks and SSDs share the property that reads are done in a block, 256KB or more. So even if you're reading a few bytes you are actually reading the entire block. In the linear (sequential) read case, you are using it all. The block size is a parameter in the theoretical model for I/O-efficient computation.
SSDs generally read at the page level, so you can get full performance or close to it from much smaller reads than 256KB or more.
For example, you may be able get maximum performance from 4K or 8K byte reads. Of course, there are a few layers between you and the SSD so you have to make sure you have the SSD actually sees enough pending requests at all times for maximum performance. If you just read one 4K block before submitting the next one, you'll get terrible performance because at queue depth of 1 the SSD is utilized most of the time (i.e., the bandwidth delay product is much lager than 4096 bytes).
This effect can lead the erroneous conclusion that small block sizes are slow when queue depth is actually the confounding factor (large blocks effectively feed many page-sized read requests to the SSD at once, so you can get away with a lower queue depth).
Writes are different but you also don't need gigantic block sizes. For SSDs available as EC2 local storage, for example, a 4K random write load can extract full performance if you get the other parameters right.
Re: Ask HN: Books on designing disk-optimized data structures?
#43Earlier quoted context omitted.
Okay. Does this imply that I should see similar SSD read speeds when reading 10 blocks contiguously vs randomly? If I can fit, say, 2k records into a single block, then I would expect reading the first 4k pieces of data to have similar SSD read performance compared to reading 2k from the first and 2k from the last? (Haven't coded the experiment yet, but that would be the prediction?) And: to the point of using block…
Someone did test exactly that: https://panthema.net/2019/0322-nvme-batched-block-access-spe... From my experience as long as you can do that access multithreaded you won't really be penalized for random reads. Single threaded access I've seen as much as read performance halved (used fio for testing), but that didn't translate into multithreaded benchmarks
Just to be a bit pedantic, what you really want is several concurrent IOs, doesn’t have to be multithreaded. For example, io_uring can kick off many concurrent IOs off a single (userspace) thread.
But yes, if you don’t have io_uring you need to use threads, and if you use a lot of them context switches can have a nontrivial overhead from my experience.
Re: Ask HN: Books on designing disk-optimized data structures?
#44These days, most people need the opposite. They're probably using systems optimized for spinning disks but they're running it on flash, and all the layers of complexity added over the years to optimize disk latency are just slowing things down. Like, this is the kind of bullshit people used to do research on: https://tlb.org/docs/usenixw95.pdf (I'm an author). This paper (and 100s of others) exist only because sequen…
Reading from RAM, SSD and even spinning disk all share the same property that there is a significant setup time and then a lower cost for each block read.
That is not really true for SSD, which provide random access at the same performance, at least when a "suitable" block size is reached.
This must be the case in fact because SSDs do not lay out data in the same order as the linear addressing used to access them: rather, logical addresses are mapped to physical ones inside a flash translation layer meaning that "most" access effectively looks random at page granularity.
Re: Ask HN: Books on designing disk-optimized data structures?
#45I bought the "Algorithms and Data Structures for Massive Datasets" book recently, haven't had a chance to read it yet. "Massive" datasets should automatically imply using (mostly) on-disk data structures...
Edit: add link:
https://www.manning.com/books/algorithms-and-data-structures...
Re: Ask HN: Books on designing disk-optimized data structures?
#46Earlier quoted context omitted.
Thank you for this! Here is my question, though. I have an example C program that uses mmap() to read data from a file. It can do this linearly or select random records. I'm running it on my M1 mac. https://gist.github.com/poundifdef/e748c467d354662ed034b5f64... The script runs orders of magnitude slower when I do random reads rather than linear. Theoretically this seems like it should not be the case since it is run…
If you want to get good random read performance out of an SSD, you can't use mmap. A thread can only page fault on one address at a time, but full random IO performance requires giving the SSD many requests to work on in parallel.
This, you should open the fd in O_DIRECT, non-mmap'ed
You have a lot more control this way
Re: Ask HN: Books on designing disk-optimized data structures?
#47These days, most people need the opposite. They're probably using systems optimized for spinning disks but they're running it on flash, and all the layers of complexity added over the years to optimize disk latency are just slowing things down. Like, this is the kind of bullshit people used to do research on: https://tlb.org/docs/usenixw95.pdf (I'm an author). This paper (and 100s of others) exist only because sequen…
I recall (>20 years ago) reading TAOCP, and laughing to myself about how obsolete the section on sorting using multiple tape drives. And here we are.
There are newer editions (2004, 2014) of the McKusick et al book, s/4.4 BSD/FreeBSD/1 for the updated title. If you don't want any taint of knowledge of fast flash drives, maybe go with the 2004 edition.
Re: Ask HN: Books on designing disk-optimized data structures?
#48Earlier quoted context omitted.
Reading from RAM, SSD and even spinning disk all share the same property that there is a significant setup time and then a lower cost for each block read.
That is not really true for SSD, which provide random access at the same performance, at least when a "suitable" block size is reached. This must be the case in fact because SSDs do not lay out data in the same order as the linear addressing used to access them: rather, logical addresses are mapped to physical ones inside a flash translation layer meaning that "most" access effectively looks random at page granularit…
The flash _blocks_ are 64kB or larger. If one is doing writes smaller than this, than potentially one could get write amplification on the device depending on how it buffers and coalesces writes.
Re: Ask HN: Books on designing disk-optimized data structures?
#49Earlier quoted context omitted.
Reading from RAM, SSD and even spinning disk all share the same property that there is a significant setup time and then a lower cost for each block read.
That sounds quite a bit less true for RAM and SSD, typically as long as you're reading cache-line or block size, respectively, isn't it consistent costs for each read?
They would be consistent, but some fraction would be still be setup time. RAM behaves more like a serial device than a truly random one.
https://stackoverflow.com/questions/56086993/what-does-strea...
Re: Ask HN: Books on designing disk-optimized data structures?
#50Assuming you’re looking for physical HDD advice. Most opt for a b-tree with the data stored in a scan optimal extent - large enough that the data can be read with a sizable disk spindle efficiency (shoot for 75%+, which today equates to around 16MB on random reads), while maintaining the metadata in a higher cache tier. Typically RAM or SSD. Recently Log Structure Merge arrangements have become more common, but the decision to use one over the other is based upon the read/write ratio, with LSM being favored by write heavy workloads.
I’d recommend reading up on WAFL filesystem design. ARIES. WAL. The real race horses of this space today are on HPC file systems. Check out the Top 500 file systems. The new Chinese file systems have some impressive metrics, beating the Intel ones significantly. I believe the Chinese ones are taking advantage of RocksDB (LSM).
At a higher level, the outer diameter of an HDD is significantly faster than the inner diameter for sequential reads/writes. The LBA addressing starts at the outer diameter. Typically systems will maintain access metrics on their data, and relocate the hotter data to the Outer, and colder data to the Inner.
While accessing the drive, optimizing for reads, using an adaptive prefetch algorithm will maintain sequential disk access patterns without wasting the time of the head dwelling over data that will be discarded.
If you have a battery backed write back cache, you now have the luxury of optimizing writes to the disk. To maintain optimal disk write performance, you’ll want to maintain your writes in an ordered manner, and present them to the disk with a high queue depth. Ideally you will take advantage of HDD queues, and send latency sensitive reads to a higher priority queue, or head of queue. Additionally, with write back cache, you have the opportunity to enable write cache on the HDD. Each HDD vendor/model have slightly different write cache handling mechanism, so I’d recommend testing.
I’ve been impressed with PingCap’s use of some of the new algorithms. Check out their YouTube architecture overview talks which provide details on exactly which papers/algorithms they’re using.
If your goal is to use Shingled Magnetic Recording drives, these optimizations become even more complex, with best practices not yet fully defined.