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

11–20 of 59 posts

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

#11

Post by dsp »

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…

In the random case you’re reading a whole page to get some tiny struct.

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

#12

Post by gniv »

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…

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.

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

#13

Post by memset »

gniv wrote: post #12
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…

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 size as a parameter, do you have suggestions on further reading for techniques people have used to incorporate that into the design of their structures? Or is it basically the same as efficient paging algorithms?

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

#14

Post by nindalf »

Designing Data Intensive Applications is the book you want. The first section of the book covers data structures used to store data on disk in detail, specifically B-Trees, LSM Trees and how they’re used by various databases.

If you want to dive deeper on the subject of persistence, the book Operating Systems: Three Easy Pieces has a section devoted to it.

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

#15

Post by amelius »

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…

Once you mmap() a file the OS will (probably) use the same algorithms for accessing data as it uses for virtual memory. So you probably want to read:

https://news.ycombinator.com/item?id=19302299

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

#16

Post by jltsiren »

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…

Disk-based and in-memory algorithms and data structures need similar techniques these days. The numbers are just different.

RAM latency is something like 100 ns, or maybe a bit less. Sequential read speed ranges from tens to hundreds of gigabytes per second. However, if you divide cache line size by latency, you are still orders of magnitude below that. If an algorithm accesses the memory randomly and waits for the results before continuing, it's often much slower than an algorithm that reads sequentially, even when the structs are conveniently the size of a cache line.

SSD read latency is around 100 µs, or three orders of magnitude higher. Sequential read speed is gigabytes per second, or 1-2 orders of magnitude lower. Again, if you divide page size by latency, you are nowhere near the peak throughput. Reading sequentially can be much faster, because the OS and the controller can guess your intent and read ahead.

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

#17

Post by gniv »

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…

> Okay. Does this imply that I should see similar SSD read speeds when reading 10 blocks contiguously vs randomly?

Yes, with some caveats:

1. Not sure if you can read block-aligned data from high-level code.

2. There might be some read-ahead heuristics in the I/O stack.

> techniques people have used to incorporate that into the design of their structures?

I haven't kept up with the research. You can try searching on scholar.google.com for "I/O-efficient" algorithms and data structures. Also "cache-oblivious". There should be some good surveys now, since this is not a new research area.

Note that most of the algorithms that were optimized for disk reads did not typically take into consideration sequential vs random reads. The model simply assumed that reading a block of size B has a unit cost and the performance of algos/ds was expressed in terms of the number of these units.

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

#18

Post by mamcx »

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…

You will like this https://ayende.com/blog/posts/series/195587-B/implementing-a... and https://www.reddit.com/r/databasedevelopment/ where it talks about this kind of stuff.

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

#19

Post by chubot »

Taking into account the comment by tlb@ about "do you really want that?"

If you really want that then I think a good keyword to search for is "External memory algorithms" (or also I think secondary storage), e.g. this 2001 survey:

External Memory Algorithms and Data Structures: Dealing with Massive Data

https://users.cs.duke.edu/~reif/courses/alglectures/vitter.p...

I think there is at least one other survey out there which would have references. Of course not all these algorithms have actually been tried in production :) Which is what I tend to look for

And this is pre-cloud, which changes things a lot for "massive data"

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

#20

Post by denniskubes »

I think you may be interested in file structures. There are relatively few books published and they are all 20+ years old but they describe the kind of on disk data structures that power many of today's databases and datastores. For search specific file structures look for information retrieval books and one title called managing gigabytes.
Post reply on HN