[HN Gopher] Ask HN: Books on designing disk-optimized data struc...
___________________________________________________________________
Ask HN: Books on designing disk-optimized data structures?
Are there canonical books, resources, or readings for how to design
data structures that will be primarily read and written to a _disk_
rather than memory? Most of what I learned in school about big-O
assumes that, for example, random access is O(1). However, random
disk reads are really slow due to spacial locality. People who
write databases obviously have solutions to this problem - for
example, DuckDB is based on a number of papers that have come out
over the years on this topic. If I wanted to design, ie, a tree
structure which was intended to be read/written from a disk, are
there general principles or patterns the have been developed to
take advantage of locality of reference, minimize random reads, or
decrease the overhead of writes, that I could familiarize myself
with? What is the CLRS for disk?
Author : memset
Score : 50 points
Date : 2022-09-24 17:59 UTC (5 hours ago)
| boulos wrote:
| 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 < Noun > 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
| trasz wrote:
| Anything that describes external sort algorithms perhaps?
| DamonHD wrote:
| It may be a bit obvious, but (books/papers on) disc filesystems
| themselves, eg ufs or ext4.
| kadoban wrote:
| Just to spice things up a bit, you may be interested in "Cache-
| oblivious" algorithms and data structures. The name is a bit
| counter-intuitive, they're data structures that care about memory
| hierarchies without encoding the specifics about the block
| sizes/cache lines.
| chubot wrote:
| 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"
| avl999 wrote:
| 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.
| nindalf wrote:
| _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.
| pknerd wrote:
| You might like to visit the code of your favorite DB/Storage
| engine and see how it works? A couple of years during COVID
| lockdown I started exploring Golang, I produced two libs: GoCache
| and Fehrist to understand what algo is used by Memcache and
| Elasticsearch respectively. Blog posts about them are given
| below:
|
| - http://blog.adnansiddiqi.me/gocache-lru-cache-implementation...
|
| - http://blog.adnansiddiqi.me/fehrist-document-indexing-librar...
| efficax wrote:
| 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!)
| aslak wrote:
| This is definitely a case where you should look into traditional
| disk-oriented DBMS architecture.
|
| Google the two CMU db courses, advanced and intro, they have the
| required material and references to understand, it's a case where
| practice > theory
|
| For example, to reduce random reads in a b+tree (data structure
| used for indexes), you leave room for the index data to grow in
| the node, so your DBMS doesn't need to allocate a new page
| immediately (this new page read would be a random, non-sequential
| access on a later read). Google "index fragmentation" to find out
| more
| tlb wrote:
| 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 sequential reads & writes
| on disks were much faster than random access, because you had to
| (a) move the head, and (b) wait for the sector you're interested
| in to come around. At 7200 RPM, this is up to 4.2 milliseconds,
| so it was worth burning 10000s of CPU instructions to try to sort
| read requests in some order that might avoid waiting for another
| rotation. Many popular disk controllers couldn't read sequential
| sectors, so it was better to sort write requests so that it hit
| every second sector or something. Madness.
|
| 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).
|
| But if you're working with some old-timey environment and really
| need to know about optimizing for spinning disks, most of the
| ideas were published in the late 80s and 90s. This book
| https://www.amazon.co.uk/Design-Implementation-Operating-Add...
| (McKusick et al) is excellent, and describes a filesystem that
| works well on a wide variety of workloads. Or see the references
| in the Blackwell paper above.
| anonymoushn wrote:
| > 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.
| mgraczyk wrote:
| 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.
| sitkack wrote:
| 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.
| kadoban wrote:
| 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?
| memset wrote:
| 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 running on an SSD, but
| clearly there are other tricks the OS (or hardware?) is doing
| to optimize for the linear case.
|
| I'm looking to better understand why I'm observing that
| performance difference and how I can better design software
| around it, even though (intuitively) it seems like it should
| not matter with non-mechanical disks.
| wtallis wrote:
| 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.
| tlb wrote:
| 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.
| xani_ wrote:
| Shouldn't matter as long as you do direct IO for
| benchmarking
| memset wrote:
| 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.
| dsp wrote:
| In the random case you're reading a whole page to get some
| tiny struct.
| amelius wrote:
| 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
| jltsiren wrote:
| 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 us, 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.
| gniv wrote:
| 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.
| memset wrote:
| 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?
| gniv wrote:
| > 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.
| mamcx wrote:
| You will like this https://ayende.com/blog/posts/series/1
| 95587-B/implementing-a... and
| https://www.reddit.com/r/databasedevelopment/ where it
| talks about this kind of stuff.
| xani_ wrote:
| 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
| stingraycharles wrote:
| 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.
| xani_ wrote:
| 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
| formercoder wrote:
| Doesn't the chip on the drive deal with wear leveling?
| marginalia_nu wrote:
| 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
| denniskubes wrote:
| 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.
| dapids wrote:
| 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.
| alexott wrote:
| Have you seen Database Internals? https://www.databass.dev/
| memset wrote:
| Had not seen that, thank you!
___________________________________________________________________
(page generated 2022-09-24 23:00 UTC)