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

21–30 of 59 posts

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

#21

Post by boulos »

Edit: duh, a sibling comment (https://news.ycombinator.com/item?id=32965989) did say BTrees and LSMs an hour ago... Sorry.

Btw, because nobody has said it explicitly yet: you should start at BTrees [1]. As you guessed, the database folks were the primary "we have to deal with spinning disk and it really matters to be fast" people.

There's also the Log-Structured universe of things which 'tlb is pointing you at. Roughly, you turn random writes into appends (to a "log"), often followed by periodic compaction to make reads reasonable (since in-place updates to a "file" are now appended at the end of the log, you've suddenly made reads worse).

[1] https://en.m.wikipedia.org/wiki/B-tree

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

#22

Post by anonymoushn »

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…

> 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).

We mostly read from spinning magnets attached to computers, since flash is expensive and cloud is expensive and slow. I guess this is true if you're fine with throwing away lots of money, but the question sort of presupposes that you are not.

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

#23

Post by sitkack »

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.

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

#24

Post by mgraczyk »

anonymoushn wrote: post #22
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…

> 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). We mostly read from spinning magnets attached to computers, since flash is expensive and cloud is expensive and slow. I guess this is true if you're fine with throwing away lots of money, but the question sort of presupposes that you are not.

There is reason to believe that won't be true much longer, for example

https://wikibon.com/qlc-flash-hamrs-hdd/

It's likely within the next 10 years HDDs will no longer be viable. In terms of TCO with replacement costs we may already be there.

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

#25

Post by avl999 »

Designing Data Intensive applications- specifically chapter 3 and 4 which deal with strategies and algorithms for storing and encoding data to be stored on disk and their pros and cons.

Once you read that, I'll suggest reading the source of a simple embedded key-value database, I wouldn't bother with RDBMs as they are complex beasts and contain way more than you need. BoltDB is a good project to read the source of https://github.com/boltdb/bolt, the whole thing is <10k lines of code and is a full blown production grade system with ACID semantics so packs a lot in those 10k and isn't just merely a toy.

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

#26

Post by tlb »

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…

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.

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

#27

Post by stingraycharles »

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 tremendously, it’s just that the way things are optimized are very different, and perhaps much more nuanced.

Where before it was just as easy as saying “just read/write things sequential, random access is expensive”, nowadays you need to think about how the kernel interacts with storage, and sector sizes and whatnot. There definitely are do’s and don’ts when optimizing data structures for this.

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

#28

Post by efficax »

https://www.google.com/books/edition/File_Structures/cqwrnwE... this is classic in the genre, however it predates SSDs, which makes structures like LSM trees and other append-only structures much more optimal for write-heavy workloads (for read-heavy workloads the B-Tree is still the order of the day!)

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

#29

Post by dapids »

I think most commenters are completely gleaning over the contrived systems which are embedded systems.

Sure, on higher performance systems you will be dealing with bigger demons such as cache and TLB performance depending on data size. But many embedded systems are performance limited for cost and power reasons. There is nothing here cloud will solve, nor anything else than more expensive NAND flashes, which require more power, and money. Hence why designing algorithms for critical data throughput are not as simple as using cloud or a filesystem.

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

#30

Post by memset »

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.

Understood - it sounds like the idea of a “minimal working code example” will give misleading results. I’ll pay more attention to this when testing, I appreciate it.
Post reply on HN