Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Books on designing disk-optimized data structures?

news.ycombinator.com

Post reply on HN
Print view View original

31–40 of 59 posts

Re: Ask HN: Books on designing disk-optimized data structures?

#31

Post by marginalia_nu »

tlb wrote: post #5

These 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…

Flash still effectively has "seeks". Sequential IO is still faster than random IO, since its a block operation.

Especially for writing, sustained random small writes is disastrously bad on an SSD. https://en.m.wikipedia.org/wiki/Write_amplification

Re: Ask HN: Books on designing disk-optimized data structures?

#32

Post by wtallis »

memset wrote: post #10
tlb wrote: post #5

These 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…

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.

Re: Ask HN: Books on designing disk-optimized data structures?

#33

Post by kadoban »

sitkack wrote: post #23
tlb wrote: post #5

These 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 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?

Re: Ask HN: Books on designing disk-optimized data structures?

#34

Post by xani_ »

stingraycharles wrote: post #27
tlb wrote: post #5

These 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…

While what you’re saying is valid, what you classify as bullshit (log-structured storage) is still immensely popular and important in the world of flash. In my experience, read-ahead is still extremely important, even when you have SSDs, and unless all your writes are >4kb, you’re still going to benefit from a certain amount of “sequential-ness” of your writes. Optimizing things for disk storage still does pay of tre…

If you're writing on SATA SSD, yes.

If you're writing on NVMe, well, there is a good chance that if you're not at the high end (big site, a lot of things to do), you can just ignore that as the IOPS will be "good enough"

Like, single relatively shitty NVMe can still sustain ~700MB/s of random(4k block) writes. Use good ones, and use more than one and you quickly hit CPU barrier before you hit NVMe performance.

You still want to keep it kinda grouped together but that's mostly for the wear levelling reasons

Re: Ask HN: Books on designing disk-optimized data structures?

#35

Post by xani_ »

memset wrote: post #13
gniv wrote: post #12

Earlier quoted context omitted.

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.

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

Re: Ask HN: Books on designing disk-optimized data structures?

#36

Post by xani_ »

tlb wrote: post #26
memset wrote: post #10

Earlier 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…

That program's data set is only 0.8 GB, which is like $10 of RAM. The time difference you're measuring between random & sequential access is probably mostly due to CPU cache and TLB, not flash. Whatever real-world application you have in mind, this probably isn't representative. It pays to have realistic benchmarks before spending much time optimizing.

Shouldn't matter as long as you do direct IO for benchmarking

Re: Ask HN: Books on designing disk-optimized data structures?

#37

Post by formercoder »

xani_ wrote: post #34
stingraycharles wrote: post #27

Earlier quoted context omitted.

While what you’re saying is valid, what you classify as bullshit (log-structured storage) is still immensely popular and important in the world of flash. In my experience, read-ahead is still extremely important, even when you have SSDs, and unless all your writes are >4kb, you’re still going to benefit from a certain amount of “sequential-ness” of your writes. Optimizing things for disk storage still does pay of tre…

If you're writing on SATA SSD, yes. If you're writing on NVMe, well, there is a good chance that if you're not at the high end (big site, a lot of things to do), you can just ignore that as the IOPS will be "good enough" Like, single relatively shitty NVMe can still sustain ~700MB/s of random(4k block) writes. Use good ones, and use more than one and you quickly hit CPU barrier before you hit NVMe performance. You st…

Doesn’t the chip on the drive deal with wear leveling?

Re: Ask HN: Books on designing disk-optimized data structures?

#40

Post by xani_ »

formercoder wrote: post #37
xani_ wrote: post #34

Earlier quoted context omitted.

If you're writing on SATA SSD, yes. If you're writing on NVMe, well, there is a good chance that if you're not at the high end (big site, a lot of things to do), you can just ignore that as the IOPS will be "good enough" Like, single relatively shitty NVMe can still sustain ~700MB/s of random(4k block) writes. Use good ones, and use more than one and you quickly hit CPU barrier before you hit NVMe performance. You st…

Doesn’t the chip on the drive deal with wear leveling?

It does but it's always easier if you allocate/deallocate big blocks. Especially if you just put sub-block-size data on disk
Post reply on HN