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

51–59 of 59 posts

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

#51

Post by xani_ »

sakras wrote: post #43
xani_ wrote: post #35

Earlier quoted context omitted.

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.

Pedantic and wrong, good fucking luck saturating whole SSD from single thread on anything else than pure benchmark code

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

#52

Post by BeeOnRope »

sitkack wrote: post #48
BeeOnRope wrote: post #44

Earlier quoted context omitted.

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.

Yes, that's true though "blocks" is an overloaded term (e.g., people will talk about what "block size" they are reading at at the application layer).

In any case I'm mostly disputing your characterization of SSDs as behaving like hard drives: having long setup time then faster reading of subsequent blocks. Unless you are talking about command latency, they don't really work like that.

To a first order approximation you can think of SSDs a ideal page-wise parallel random access devices, with a certain read latency and the ability to be processing up to N reads at once. As long as the queue depth can keep up to N reads in progress at once, the maximum bandwidth or a substantial fraction, can be achieved.

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

#53

Post by BeeOnRope »

marginalia_nu wrote: post #31
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

SSDs read at page granularity. SSDs don't really have an equivalent to a HD seek: there is latency but this can over overlapped with the latency of dozens of other commands.

Some SSDs may support reading an entire block in a faster way than page-by-page commands, but because of the FTL a read of a logical block worth of data may be split across many physical blocks, so you cannot necessarily take advantage of this.

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

#54

Post by stingraycharles »

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…

A lot of the cloud is based on iSCSI, which, although “random access” time is relatively constant, still has an increased latency compared to local storage. As such, you definitely do want to benefit from things such as read-ahead, and designing your storage structures around these types of mechanisms yields significantly better results.

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

#55

Post by sitkack »

BeeOnRope wrote: post #52
sitkack wrote: post #48

Earlier quoted context omitted.

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.

Yes, that's true though "blocks" is an overloaded term (e.g., people will talk about what "block size" they are reading at at the application layer). In any case I'm mostly disputing your characterization of SSDs as behaving like hard drives: having long setup time then faster reading of subsequent blocks. Unless you are talking about command latency, they don't really work like that. To a first order approximation y…

We are definitely in the weeds.

When used via an OS, you get better performance when you treat an SSD like a fast tape than you do if you do random IO (in the application domain, in the SSD domain at a high enough granularity yes, they are random access). There is setup time in opening a page, writing blocks within the page, sealing the page. If your writes are less than an SSD block, it has to copy the existing data to a buffer, write it, append the new data, seal the block. Or it applies a translation layer. SSDs are complex devices and are not fundamentally random access, no more so than DRAM, which is also not random access.

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

#56

Post by GuB-42 »

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…

I generally agree but:

> Anyway, today there are only 3 kinds of secondary storage worth caring about: flash (sector granularity, but no seeks), cloud (like S3), and archive (like Glacier).

"cloud" and "archive" are not storage devices, they are network architecture, and a service. There is a whole lot to write about that, but this is not on the same layer.

"The cloud" uses flash memory and spinning rust, and they need to care about how to get the best performance out of the hardware they use. Maybe there is not much left to discover, and maybe fewer people need to know about that, but it still matters. Same thing for "archive", with less flash and more tape.

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

#57

Post by charleslmunger »

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…

Write amplification is a concern on flash memory. The other secret is that just like flash didn't eliminate the cost of seeks, RAM isn't as fast for random access as sequential. All modern systems benefit from data locality, to varying degrees.

A CPU has layers of caches in front of memory, which then has its own caches on front of NVMe, which has its own controller usually with an SLC cache in front of MLC, which often times is being used as a cache on front of the network or slower storage.

For many problems modern hardware is fast enough, but if your problem is attempting to make use of all modern hardware offers, you need to optimize for it. Meaningfully saturating a 100gbps network connection, for example, is hard to do without considering data locality.

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

#59

Post by BeeOnRope »

sitkack wrote: post #55
BeeOnRope wrote: post #52

Earlier quoted context omitted.

Yes, that's true though "blocks" is an overloaded term (e.g., people will talk about what "block size" they are reading at at the application layer). In any case I'm mostly disputing your characterization of SSDs as behaving like hard drives: having long setup time then faster reading of subsequent blocks. Unless you are talking about command latency, they don't really work like that. To a first order approximation y…

We are definitely in the weeds. When used via an OS, you get better performance when you treat an SSD like a fast tape than you do if you do random IO (in the application domain, in the SSD domain at a high enough granularity yes, they are random access). There is setup time in opening a page, writing blocks within the page, sealing the page. If your writes are less than an SSD block, it has to copy the existing data…

You were talking about reads and I responded about reads.

I'll repeat my claim: SSDs largely behave as random access devices for page-aligned random reads of an integer multiple of pages. In particular, without any performance footguns activated in the application & OS stack, you can get a substantial portion or all the throughput with such a random read workload compared to the most sequential read workload you can imagine.

This is totally unlike disks (resp. tapes) where you have the hard physical reality of average seek time in the milliseconds (resp. seconds) making random read loads orders of magnitude slower (resp. even more orders) than sequential ones.

Writes are different and more complicated, but they also behave as random write devices if you choose your granularity to be "block size" and even at page size (if you can avoid write amplification, which is not always possible).

You have page and block reversed in your description: a page is smaller than and contained within a block.

SSDs to do not "open a block, overwrite a page and then seal the block": they write newly written pages to a freshly erased block, using a variety of possible strategies, which sometimes give an advantage to nearby-in-time writes to the same block or sometimes not.

Post reply on HN