11 ms·
Database Fundamentals
- abriosi 3y agoThank you very much for putting the article together
- praveer13 3y agoGreat article. The book Database Internals looks amazing. Are there any other such books that deep dive into internals?
- cmrdporcupine 3y agoNot a book, but I recommend the database class lectures from @apavlo's group at CMU. https://www.youtube.com/c/cmudatabasegroup https://www.youtube.com/c/cmudatabasegroup All the classes (intro and advanced) are online, as well as presentations and lectures about industry products. They are very useful. Also, from a more high level theoretical CS and less physical-implementation focused POV, the "Alice" book ("Foundations of Databases") is amazing (though very dense and mathematical). Focuses on the relational algebra and Datalog (and the translation of that into the Rel Algebra). Getting print copies is hard now (my used copy arrived with a broken spine and pages falling out), but the entire book is online: http://webdam.inria.fr/Alice/ http://webdam.inria.fr/Alice/
- senderista 3y agoAnother excellent DB textbook covering both theory and implementation is Weikum & Vossen: https://www.google.com/books/edition/_/wV5Ran71zNoC?hl=en&gbpv=1&pg=PP1&dq=Weikum+%26+Vossen https://www.google.com/books/edition/_/wV5Ran71zNoC?hl=en&gb... In case you can't afford to donate $150 to Elsevier: https://www.dropbox.com/scl/fi/r0fros5y2kzeqv57v7myz/Transactional-Information-Systems-Theory-Algorithms-and-the-Practice-of-Concurrency-Control.pdf?rlkey=f28gwoeh1kc1w41fk59xc6swu&dl=0 https://www.dropbox.com/scl/fi/r0fros5y2kzeqv57v7myz/Transac...
- flashgordon 3y agoAnother book I found very useful (though this DI book is more modern) is Raghu Ramakrishnan Database Management Systems book.
- why-el 3y agoThere is a another famous one, focusing on Postgres: https://www.interdb.jp/pg/ https://www.interdb.jp/pg/.
- big_whack 3y agoThis is a good paper for a similar kind of overview: https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
- exacube 3y agoNice article! There is a bug in the compaction method: def compact(sstables, output_sstable): # Ordered by ascending key. pop() results in the item of the smallest key. heap = heapq.heapify([(sstable.next(), sstable) for sstable in sstables]) while (item, sstable) := heap.pop() if not item.is_tombstone(): output_sstable.write(item) You should only skip tombstones when you are compacting the final (i.e., largest) level, instead of between every level. Otherwise, an entry in a lower level will unmask itself because the tombstone in the upper level was compacted away. It's one of the properties of LSM-based DBs that deletions/tombstones records linger for a long time, though some databases (eg RocksDB) put in some optimizations to get around this.
- tontinton 3y agoYou're right this was purposefully left out for brevity, in dbeel it is handled.
- exacube 3y agoAh, makes sense :)
- vlovich123 3y agoWhat kind of optimizations does RocksDB do? I know they have some stuff around range deletions but not sure I’ve read anything about point deletions.
- conqrr 3y agoVery nice article and looks like a great way to get hands dirty for anyone wanting to think like a DB engineer. Related question, for all the Database engineers out there. I have always had a keen interest to work on Databases. Having worked at one of the cloud providers and burn my high amount of ops and oncall, I am of the opinion most of the Database engineers usually have a bad wlb. Given the depth and complexity of all Database internals, Any major impact would take a few quarters to roll out, and its not a job for everyone. Is this mostly true?
- cmrdporcupine 3y agoI worked at a DB product startup, doing DB internals development [storage engine, etc], for a few months (before my personal/family situation forced me to have to move on), and WLB seemed pretty reasonable -- though there was a mandatory on-call rotation, that's kind of expected at most startups in the cloud space. People were very smart and friendly, and took vacations and all that kind of stuff. I'd say the "worst" part of working there was the amplification of my impostor syndrome? I don't know if that's typical for the industry as a whole. I'd definitely like to get back into DB internals dev at some point, it's one of the few places in our industry where you get to do fundamental systems dev. The job I had was in many ways my "dream job" but family situation at the time meant I couldn't manage it.
- senderista 3y agoI had the most fun of my entire career writing a DB from scratch at my previous job. It was fun while it lasted (i.e., until the money ran out)...
- aNoob7000 3y agoI think it depends on the environment. Yes, most production and even some test databases are critical to businesses. Any downtime or severe performance issues cause a lot of finger-pointing. Where I work, most database patches are applied to test environments and let soak for a couple of months before rolling out to production. And yes, I work a lot on weekends. My only complaint about my career as a DBA is that most of our work is behind the scenes and goes unnoticed until something breaks.
- twoodfin 3y agoI recall an hn post a bit back that cataloged all the ways POSIX guaranteed atomicity, which might help bashdb. Rename is the first thing I’d explore. Maybe this from 2010 is what I was remembering from a repost, alas the link has rotted: https://news.ycombinator.com/item?id=1035100 https://news.ycombinator.com/item?id=1035100
- __alias 3y agoThis article made me laugh because it's synonymous to me trying to start a project and going down different rabbit holes. The author at step 1. of a project trying to pick the tech stacks, decides to read a book on databases to help with choosing a DB Then proceeds to segue to writing his own database. Then writes a blog about said process I wonder how that original project has come along? I'm looking forward to when the author gets to the stage of picking a frontend framework
- JoshGlazebrook 3y agoDon't forget about the part where you actually do start on the project, but then you read one article or find another tool/software package that makes you second guess everything you've already done and you go back down another rabbit hole.
- pphysch 3y agoIME this "second-guessing" is more often right than wrong. You can always return to a project that motivates you, but you can't get back time spent digging a hole deeper, and often it leads to tunnel vision and bad habit formation. Not every "project" needs to become "finished" or "product".
- JoshGlazebrook 3y agoMy problem is scope creep. It's much harder to tell myself no vs. being on an engineering team at a company and there being a set process.
- loeber 3y agoYak Shaving: https://seths.blog/2005/03/dont_shave_that/ https://seths.blog/2005/03/dont_shave_that/
- spelunker 3y agoWhen doing personal projects I have to constantly be reeling myself back in from doing x thing "The Right Way", because I end up doing a bunch of useless crap and not actually making progress on the personal project. Easy to fall into that trap when 1) it's just you and 2) there is little accountability because it's just you!
- i_am_a_squirrel 3y agoGreat read! Thank you! Now do OLAP :p
- adontz 3y ago"Consistency - This one doesn't really belong on ACID as a property of databases, as it is a property of the application." Damn, that is not good on so many levels. First of all, ACID are not properties of a database, they are properties of database transaction. Article kind of says it, but I feel it is phased ambiguous. Consistency is the property of a database transaction which can be easily illustrated by foreign keys. AUTHORS | author_id | name | | 1 | Mary | | 2 | John | ARTICLES | article_id | author_id | title | | 11 | 2 | About small animals | | 12 | 1 | About big machines | Now ARTICLES cannot have author_id non existent in AUTHORS. If a tuple is inserted in ARTICLES, then author_id should reference a valid tuple from AUTHORS. If a tuple is deleted from AUTHORS, then all ARTICLES tuples referencing said AUTHORS tuple should be deleted too; or deleting from AUTHORS should be rejected. That is consistency and that is a property of a database transaction. Transaction must fail if one tries to insert an article with author_id equal 5. At the end of transaction article 11 must be deleted if author 2 was deleted. Now real life databases are much more complex, but idea is basically the same. Also, consistency is between tuples. Not having "31-February-2001" as a date is integrity, not consistency.
- joshxyz 3y agodamn right sir, and there is also the term "consistency levels" which vary from one db to another.
- deleted 3y ago[deleted]
- tontinton 3y agoThanks, that's something I didn't know! I'll fix it later, and change the wording to say that these are properties of a database transaction
- senderista 3y agoI think the "C" in ACID indeed refers to application-defined integrity constraints (or "invariants"). Referential integrity is just one example; unique key constraints are another. This has nothing to do with the "C" in CAP, which is best interpreted (IMO) as linearizability. (Aside: IMO the "C" in ACID implies "I" and specifically serializability, because that is the only isolation level guaranteed to preserve arbitrary application invariants.)
- dpc_01234 3y agoThe atomicity in the bash version can be "simply" achieved by copying the file to a temporary, modyfing it, then using `sync; mv; sync`, right?
- tontinton 3y agoOh you're right I'll add that in later.
- n3storm 3y agoI would go : 1. count records 2. make copy 3. insert 4. ensure records = records + 1 5 if records != records +1 or file can be grepped, stat, filesize, then assume is corrupted and rollback to copy
- o11c 3y agoUse `look` to get `O(log(n))` lookups (writes are still slow, but you could use a multi-level chain I guess). `join` does not use binary search even though it could have.
- tontinton 3y agono waaay, I have never seen look before, thanks!
- deleted 3y ago[deleted]
- ncruces 3y agoAlso, while you're copying you can inverse grep filter to avoid duplicates. And since you're copying, you could maybe ensure sorting, but I don't think doing that with "bash" (plus off the shelf utils) makes a lot of sense. That's what DJBs CDB (cdbget, cdbmake, etc) is for: https://cr.yp.to/cdb.html https://cr.yp.to/cdb.html
- deleted 3y ago[deleted]
- pphysch 3y agoI love how the article starts out by demystifying "database" by implementing a trivial one as a bash "one liner". Great hook.
- PeterCorless 3y ago"So basically it has a document API like in MongoDB with leaderless replication like in Cassandra and thread-per-core architecture like in ScyllaDB." Very cool design. And all in Rust!
- tontinton 3y agoThanks :)
- bob1029 3y ago> The books piqued my curiosity enough to write my own little database I think many developers go through this phase at some point. I wouldn't even try to fight it. You learn so much about what won't work by doing this. Extremely valuable lessons, if you can spare the time. Building my own databases gave me more respect for the existing solutions than anything else. Getting the bytes to & from disk quickly isn't the hard part. It's doing it reliably for years on end while supporting use cases you couldn't have even dreamed of.
- derefr 3y ago> while supporting use cases you couldn't have even dreamed of. I often wonder: given how much of the complexity of modern DBMSes exists because of constraints imposed by certain use-cases that only pertain in certain business domains... what efficiencies could we gain if we designed a domain-specific DBMS with the knowledge that use-cases outside of the domain are off-limits and can be ignored? For example, I currently use general-purpose DBs to deal with datasets that are fundamentally append-only. But what if I had a DB that only supported working with append-only data? A DB that literally has no concept of an update or delete of existing rows — you've got insert, and maybe dropping a table/dataset entirely, and that's it. Could such a DB get away with not implementing MVCC transactions? Could such a DB avoid using a write-ahead log (because the tables are each their own write-ahead logs)? Would it store data more efficiently? Could its indexing be chunkwise-atomic rather than whole-table-atomic and so require less locking? Etc.
- diatone 3y agoCheck out TigerBeetle!
- lichtenberger 3y agoHave a look into my DB project: https://sirix.io https://sirix.io | https://github.com/sirixdb/sirix https://github.com/sirixdb/sirix https://sirix.io/docs/concepts.html https://sirix.io/docs/concepts.html and in progress tutorial https://sirix.io/docs/jsoniq-tutorial.html https://sirix.io/docs/jsoniq-tutorial.html may be especially helpful. It basically turns updates into appends and is based on a persistent tree structure (the header with a reference to the (revision) root page has to be swapped atomically. Other than that the revision indexes for new data are always appended. In order to reduce copy-on-write overhead for updated page (fragments) a sliding snapshot for the data pages is applied. Naturally, unchanged pages are simply referenced (e.g. through offsets into the file, thus sharing unchanged pages between revisions). What's also special is a path summary of all unordered paths in a resource, which enables user-defined smaller tailored secondary indexes and other query rewrites :-)
- LAC-Tech 3y agoTangential but I'm a bit blown away by that mongoDB mention - that it just flushes every 100ms, so you can lose writes. The link in the article is invalid, but from https://www.mongodb.com/docs/current/core/journaling/ https://www.mongodb.com/docs/current/core/journaling/ we see: "In between write operations, while the journal records remain in the WiredTiger buffers, updates can be lost following a hard shutdown of mongod." Does Mongodb acknowledge writes as soon as they've hit the buffers or do they wait for an fsync? Because if the former, that's... shocking for a database people use as a source of truth.
- tontinton 3y agoThanks for pointing out the link is bad! I just fixed it. And yeah this was shocking to me as well.
- dgottlieb 3y agoWrites in MongoDB are persisted before the server returns acknowledgement. For a typical replica set deployment, this additionally means replicated and made durable on disk for a majority of nodes. MongoDB has tunable durability guarantees; clients can opt-out of this behavior. The layers are deep, but this is the function that handles waiting before acknowledgement: https://github.com/mongodb/mongo/blob/20f42d9dc89999d119f35ab3261a0d3ae6e85087/src/mongo/db/write_concern.cpp#L276-L279 https://github.com/mongodb/mongo/blob/20f42d9dc89999d119f35a...
- dvas 3y agoEnjoyed reading it! Great overview of different concepts involved while building DB's. From mentioning SIMD to squeeze out performance on a single machine all the way to consensus algorithms. While on the topic of DB's, reliability and distributed systems. Formal methods and how they can be applied in these situations and formally apply to Database internals for anyone else wishing to read up on as another concept. Interesting paper on the S3 team using TLA+ to model. [0] Use of Formal Methods at Amazon Web Services https://lamport.azurewebsites.net/tla/formal-methods-amazon.pdf https://lamport.azurewebsites.net/tla/formal-methods-amazon.... [1] How Amazon Web Services uses formal methods https://www.amazon.science/publications/how-amazon-web-services-uses-formal-methods https://www.amazon.science/publications/how-amazon-web-servi...
- pyrolistical 3y ago> Please avoid using distributed systems when non distributed solutions suffice. I would give the opposite advice. Every non-trivial production system is a distributed system. At the very least your database is a replica set and therefore a distributed system. So avoid learning distributed systems at your own peril. Check out https://jepsen.io/ https://jepsen.io/ and https://raft.github.io/ https://raft.github.io/
- emerongi 3y ago> Every non-trivial production system is a distributed system. In the HN bubble, yes. From the perspective of the average business, definitely not. Or at least, doesn't have to be.
- eatonphil 3y agoNot to get reductionist but if you interact with more than one (e.g. Linux) process, it's already a distributed system. > A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. https://en.wikipedia.org/wiki/Distributed_computing https://en.wikipedia.org/wiki/Distributed_computing
- nrr 3y agoI'm unsure whether it's worth splitting hairs over the definition of what a distributed system is. If you have to linearize concurrent access to shared resources, that's where the bulk of your pain will come from. In the distributed system case, at least as far as that term is commonly understood by technologists, that linearization also has to take into account odd behaviors in interconnects that you don't typically see within a single machine.
- vlovich123 3y agoYou wouldn’t classify storage as an odd behaving interconnect?
- zackmorris 3y agoThis is a great article! But fsyncgate makes me cry inside. It sounds like PostgreSQL made the decision to crash instead of retry forever upon fsync errors (which is the wrong way to do it). But it wasn't their fault, because OSs and filesystems don't always perform correctly when they run out of disk space. And they were able to avoid data loss by continuing from the last point in the log before the crash (and maybe have a supervisor process relaunch the database) so in the end, it may not matter. The 2010s were a strange time. People went to great lengths to work around perceived limitations in the tooling. Stuff like, MongoDB would sometimes lose data, even when it claimed that a write completed. And people were ok with that, because they wanted the speed and freedom in order to iterate quickly and make money. When we really should have been formally addressing problems from first principles. Because if our OS can't recover gracefully when the disk fills up, then we don't really have anything. And so many OSs (including our desktops) panic when the disk fills up, that we don't really have anything. At a low enough level, all of the tools we rely upon are trash. But the point I wanted to make is: there's no such thing as exceptional behavior, there's only how many edge cases have been handled. Programs can be converted from imperative to functional by replacing exceptions with blocking (or spin-locking) retries so that their logic eventually finishes executing. In this case, by letting programs wait until the user has cleared off disk space, rather than forcing the user to orchestrate relaunching processes. In other words, synchronous blocking logic can be converted to a spreadsheet (flowchart) and reasoned about. But asynchronous nonblocking logic allows state explosion by forcing the user to deal with meta eventualities outside the core business logic. So it's understandable how PostgreSQL made the decision to go with a nonblocking fault instead of blocking in 2018. But in 2023, a better approach might be to write something like a container with proper fsync behavior to protect PostgreSQL from immature filesystems.
- marcosdumay 3y agoI really envy your optimism, but no, filesystems at 2023 are fucked too, both on the host and the guest. Disks are still fucked in that they will tell you they saved your data, and still lose it due to some failure, or when they are full. The disk communication bus is a bit less fucked though, so that's improvement. But anyway, you still can't rely on good behavior from your fsync, or even that a successful fsync means your data is safe.
- hiAndrewQuinn 3y agoArticles like this remind me I could basically make an entire career and some version of every web service I could ever want off of PostgreSQL, Django, and React at this point. We're living in good times my friends.
- deleted 3y ago[deleted]
- fjwyasdf 3y agoWhat tool do you use to make those diagrams? They look great!
- mahastore 3y agoThere has been nothing man made in the world that is more elegant and beautiful than Unix.
- zschoche 3y agoQuick question: what are the NP-hard problems in the database area?
- PartiallyTyped 3y agoSolving for constraints and inverting queries i.e. from query -> data with filtering and all that.
- vaidhy 3y agoOne quick comment on consistency - There is db consistency and app consistency. For e.g, you can achieve A, I and D on one table at a time, but fail on a multi-table write. Once you deal with transactions which can update multiple tables at the same time, then consistency comes to play. All the tables should be updated at the same time or none.
- tontinton 3y agoOh that is a great example, I'll update the post tomorrow.
- tonymet 3y agoMany people learn databases by learning sql. I recommend people learn DBs by doing a class like this and understanding b-trees. Nearly Everything about the strengths & weaknesses of RDBMS is understood through knowing btrees and how they affect key insertion, lookup & ordering. Most people try to speed up a DB by adding indexes -- but when you realize you're just adding one tree on top of another you're just masking the problem. Some problems are well suited toward b-trees, and many aren't. SQL is just a query interface to a remote b-tree system.
- lichtenberger 3y agoWell, it may be a B-tree, or an LSM-tree, a trie or whatever index structure suits... Also, of course you may have covering indexes.
- ljm 3y agoI think this is too reductive. A b-tree isn't the only indexing strategy, and it's well understood that an index is intended to improve read performance at the expense of write performance because the common case is that your DB handles a lot more reads than writes. > but when you realize you're just adding one tree on top of another you're just masking the problem. What is the problem and how do you propose to solve it without touching indexes? They are a hard requirement for any decent sized table.
- tonymet 3y agoIf you are using oracle, mysql , mssql you are typically using b-tree index. mysql supports hash index but i rarely see it applied in prod (probably just habits or lack of familiarity).
- roetlich 3y agoYes, but a lot of the cool, new DBs use LSM trees. The post we're currently discussing also spends more time explaining LSM trees + WAL, than it does B-trees. But your point is still valid. :)
- 3y ago
- lichtenberger 3y ago"Database Design and Implementation" by Edward Sciore is also a very great read with a lot of examples written in Java (actually a small DBS). For actual research I'd recommend all stuff from Andy (Pavlo), Viktor Leis, Thorsten Grust, Thomas Neumann...
- dxtrous 3y agoI was hoping to see an LSMT implementation in bash and left slightly disappointed.
- buglungtung 3y agoDatabase is the most interesting topic that I could not stop curious about it. I used to hosted a techtalk for my teammate about how to write a db with LSM tree ans SSTable but I could not go so far as your article Sent it to my teammate and hope they can use your article as a note to explore more topics about the database Thanks for amazing article
- deleted 3y ago[deleted]
- anonzzzies 3y agoSlightly offtopic; I am quite well vetted in the relational database models (starting with the Date book in uni in the 80s; I worked with DBs before that, but didn't know how they worked or relational theory), however are there similar theories for other types of databases; more specific graph databases? But any other type would suffice. For instance, I can find a lot of implementation detail about columnar databases, but not a lot of theory (probably my inability to search for the right phrases).
- einpoklum 3y agoThat page should be titled _transactional_ DB fundamentals. If you're doing analytical work, all of those tree-like structures are just uselessly slow, for example.