7 ms·

LearnDB: Learn how to build a database

269 points by niklabh 8y ago

dominotw 8y ago
I realized how little i knew about how databases work until I watched this lecture series. https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA Does anyone have DB internal book recommendation that inst' boring as hell.
- johan_larson 8y ago
  You might try this collection of papers about DB technology. http://www.redbook.io/ http://www.redbook.io/ Fair warning: this is not for beginners. If you find the going too hard, start with a DB textbook. Also, that site doesn't seem to include the papers themselves. But most of those papers are very famous, so if you search for the titles, you should find copies. Worst case, you might need to visit a university library.
  - interesthrow2 8y ago
    > Fair warning: this is not for beginners. If you find the going too hard, start with a DB textbook. which one can teach how to build a DB system from scratch? I'm not talking about SQL theory or implementing a SQL parser but the actual persistence, indexing part.
    - johan_larson 8y ago
      Both of them, really. There's a lot to know if you want to build a modern database system. But no work I am aware of addresses the specific question of how to build a database system from scratch. A reasonable approach might be to start with this high-level paper, and follow papers they reference until they get specific enough to address your specific questions: Joseph M. Hellerstein, Michael Stonebraker, James Hamilton. Architecture of a Database System. Foundations and Trends in Databases, 1, 2 (2007). For the sort of low-level issues that you are interested in, it might be useful to study a well-regarded persistence package, such as Berkeley DB. https://en.wikipedia.org/wiki/Berkeley_DB https://en.wikipedia.org/wiki/Berkeley_DB Another system that might be worth studying is SQLite. https://www.sqlite.org/index.html https://www.sqlite.org/index.html
      - SQLite 8y ago
        If the Hellerstein/Stonebraker/Hamilton paper is the kind of overview you are looking for, then a better link for the SQLite equivalent is https://sqlite.org/arch.html https://sqlite.org/arch.html
- mountaineer 8y ago
  After hearing DDIA (https://dataintensive.net https://dataintensive.net) recommended a few times, I picked it up and have been working through it recently. The book includes an incredible amount of references that provide further reading on individual areas.
  - skyde 8y ago
    I confirm DDIA is awesome book, I would recommend to anyone working with database and distributed systems.
- ggaughan 8y ago
  I found this one very good and easy to read: https://www.amazon.co.uk/Database-Management-Systems-Raghu-Ramakrishnan/dp/0071230572/ https://www.amazon.co.uk/Database-Management-Systems-Raghu-R...
- stu__b 8y ago
  Pro SQL Server Internals by Dmitri Korotkevitch https://www.apress.com/gb/book/9781484219638 https://www.apress.com/gb/book/9781484219638 It's specific to MS SQL Server but I found the chapters on log file management, indexes & isolation levels to be accessible and enjoyable.
- skyde 8y ago
  Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) ISBN-13: 978-1558605084 https://www.amazon.com/dp/1558605088/?coliid=IYEILMZI5DVNM&colid=3A6FL78THXMIS&psc=0&ref_=lv_ov_lig_dp_it https://www.amazon.com/dp/1558605088/?coliid=IYEILMZI5DVNM&c... and Transaction Processing: Concepts and Techniques (The Morgan Kaufmann Series in Data Management Systems) ISBN-13: 978-1558601901 https://www.amazon.com/dp/1558601902/?coliid=I2GWJZ9XJ5D4JI&colid=3A6FL78THXMIS&psc=0&ref_=lv_ov_lig_dp_it https://www.amazon.com/dp/1558601902/?coliid=I2GWJZ9XJ5D4JI&...
rodw 8y ago
For complicated reasons I was involved in a successful project to develop an open-source, Oracle-SQL-compatible, transactional-integrity-preserving, extensible database designed for in-memory performance in Java. In the process of this development "suddenly" the reasons for a whole bunch of performance and syntax oddities in databases like Oracle and PostgreSQL became very clear. I was shocked to learn that was 15 years ago when I looked up the link to share, but if you are interested in the topic of "how to implement a database" it may be worth a look. For what it is worth it was listed (not by me) on the C2 Wiki on the "Programs to Read" Page, where it was described as "[A] database written in Java with good unit tests and ShortMethods." [1] Both statements are true, for a complete working example of a production database (it supported a commercial product for at least 10 years) it is actually a pretty accessible and well documented code-base. The project is called AxionDB and can be found at [2]. [1] http://wiki.c2.com/?ProgramsToRead http://wiki.c2.com/?ProgramsToRead [2] http://axion.tigris.org/source/browse/axion/ http://axion.tigris.org/source/browse/axion/
- skunkworker 8y ago
  Yup, a good way to understand why RDBMS are they way they are is to try to make your own in whatever language you choose. I've done this on a very elementary scale making a built in DB for a past project, at first it was single threaded, but when you start considering indexing and the datas structures necessary, it makes you understand and appreciate the man hours that have gone into projects like SQLite, PostgreSQL etc. At first you think, oh I can just write my own database, but when you start getting into areas and the CAP theorem starts to create problems, you really understand why anything past a local machine only ephemeral KV store is asking for trouble.
  - rodw 8y ago
    Exactly. We sort of backed into this project by starting with HSQL (http://hsqldb.org/ http://hsqldb.org/) a low-end pure-Java "database" that was popular at the time. The more we used HSQL the more it became clear that it was more like a SQL-parser wrapping a simple key/value store than a full-on ACID database. We created AxionDB precisely because we needed the kinds of capabilities you mention and at the time HSQL did not provide them and wasn't remotely architected to support them. To be honest though, creating a moderately robust RDBMS from "scratch" turned out not to be the most ambitious or complex part of the overarching project that spawned AxionDB. The harder part was trying to use Java's primitive, built-in HTML-renderer to create something approximating a fully featured browser. The effort and complexity behind something like Gecko, WebKit, Edge, Blink, etc. is very easy to underestimate. It's a hard problem, made much harder by having to tackle the kinds of content you find "in the wild. Frankly building a database was a much more straightforward problem than that.
Mr_P 8y ago
How is this #2 on Hacker News? There's literally nothing here about how to actually build a database (yet?) Instead, there's just a key-value store implemented on top of a javascript hashmap and a filesystem.
- capkutay 8y ago
  This has to be a joke? This looks more like 'how to use a k-v store 101 for non programmers' I don't want to put more content under a terrible post, but the best resource for this material Jennifer Widom's MOOC. https://cs.stanford.edu/people/widom/DB-mooc.html https://cs.stanford.edu/people/widom/DB-mooc.html
  - pedrosorio 8y ago
    I took this back in 2011 and don’t remember there being much on “building a database”. Is there more advanced content now?
- thrower123 8y ago
  I'd be very interested in a book or blog series similar to the scads of "how to build an os from scratch" or the raytracer projects, like Peter Shirley's little One Weekend series. Is there anything that scatches that itch?
  - dymk 8y ago
    Nand2Tetris is a fan-favorite: https://www.nand2tetris.org/ https://www.nand2tetris.org/ Build a working Tetris game from literal logic gates up.
- elrodeo 8y ago
  I closed the page right after I read JavaScript.
hu3 8y ago
> teaches you how to create a database system from scratch with Node.js and JavaScript This can't possibly be serious
dymk 8y ago
Why would a pedagogical project choose JavaScript of all languages? Unless the project specifically needed to leverage features of the language, or a web browser, it's an incredibly poor choice for building anything with well maintained abstractions. Or anything at all ready, when the language is covered in warts. I imagine the author hasn't yet discovered for themselves why it's a poor choice, given only a key-value store has been implemented (using JSON.stringify, no less)
- gtowey 8y ago
  This was my thought as well. I'm curious to know if the author has previous experience building actual databases or if this is a case of follow-along-while-I-figure-this-out.
- interesthrow2 8y ago
  > Why would a pedagogical project choose JavaScript of all languages? I don't think the JS part is the issue. Node.js does I/O, files and co. The issue is that the article doesn't teach how to build a database at all. It doesn't explain how to efficiently persist and fetch data from a file, indexing strategies with trees, concurrent file access,locking, basic transaction... that's what I expect from a tutorial about how to build a basic DB system.
  - dymk 8y ago
    Plenty of languages do I/O, files, and co. Why choose a language plagued with warts and a half-baked ecosystem for something pedagogical? A language with all sorts of peculiarities from the '95 browser era, and not at least leverage browser technology? A language which gives you very non-interesting coarse control over resource, and has no concept of parallelism?
    - raxxorrax 8y ago
      Easy access and fast results. Learning isn't about creating the best possible implementation. Python wpuld have been another suggestion from me personally. What language would you have used? A lot of people without a formal educational background start with established scripting languages. I you handle data, chances are that you will get in contact with javascript at some point. Using coffeescript or typescript would be a worse choice for learning, even if they counter some disadvantages of the base language in question.
alphabettsy 8y ago
Why the votes? There’s nothing there.
pictur 8y ago
just vote for the title.. this place is really very funny..
hugofirth 8y ago
Not a lot of content yet, but building databases (even toys) is an incredibly interesting exercise which I encourage many more people to try out, so +1! For anyone else who is interested in learning how to build a database, can I thoroughly recommend following along with Andy Pavlo's Advanced Database Systems course from CMU[1]. Every lecture is accompanied by reading lists, notes, and assignments. Whats more, I find Andy's style to be very easy to parse even on complex topics. Even if you think you know a fair bit about this domain, you will likely learn a lot! [1]https://www.youtube.com/playlist?list=PLSE8ODhjZXjYplQRUlrgQKwIAV3es0U6t https://www.youtube.com/playlist?list=PLSE8ODhjZXjYplQRUlrgQ...
theyoungwolf 8y ago
why the hell would you share this when its nowhere near done
truth_seeker 8y ago
Since you are creating a new file for each entry, I think BTRFS would be a good choice. https://en.wikipedia.org/wiki/Btrfs https://en.wikipedia.org/wiki/Btrfs

269 points by niklabh 8y ago

I realized how little i knew about how databases work until I watched this lecture series. https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA https://www.youtube.com/channel/UCHnBsf2rH-K7pn09rb3qvkA Does anyone have DB internal book recommendation that inst' boring as hell.

johan_larson 8y ago
You might try this collection of papers about DB technology. http://www.redbook.io/ http://www.redbook.io/ Fair warning: this is not for beginners. If you find the going too hard, start with a DB textbook. Also, that site doesn't seem to include the papers themselves. But most of those papers are very famous, so if you search for the titles, you should find copies. Worst case, you might need to visit a university library.
- interesthrow2 8y ago
  > Fair warning: this is not for beginners. If you find the going too hard, start with a DB textbook. which one can teach how to build a DB system from scratch? I'm not talking about SQL theory or implementing a SQL parser but the actual persistence, indexing part.
  - johan_larson 8y ago
    Both of them, really. There's a lot to know if you want to build a modern database system. But no work I am aware of addresses the specific question of how to build a database system from scratch. A reasonable approach might be to start with this high-level paper, and follow papers they reference until they get specific enough to address your specific questions: Joseph M. Hellerstein, Michael Stonebraker, James Hamilton. Architecture of a Database System. Foundations and Trends in Databases, 1, 2 (2007). For the sort of low-level issues that you are interested in, it might be useful to study a well-regarded persistence package, such as Berkeley DB. https://en.wikipedia.org/wiki/Berkeley_DB https://en.wikipedia.org/wiki/Berkeley_DB Another system that might be worth studying is SQLite. https://www.sqlite.org/index.html https://www.sqlite.org/index.html
    - SQLite 8y ago
      If the Hellerstein/Stonebraker/Hamilton paper is the kind of overview you are looking for, then a better link for the SQLite equivalent is https://sqlite.org/arch.html https://sqlite.org/arch.html
mountaineer 8y ago
After hearing DDIA (https://dataintensive.net https://dataintensive.net) recommended a few times, I picked it up and have been working through it recently. The book includes an incredible amount of references that provide further reading on individual areas.
- skyde 8y ago
  I confirm DDIA is awesome book, I would recommend to anyone working with database and distributed systems.
ggaughan 8y ago
I found this one very good and easy to read: https://www.amazon.co.uk/Database-Management-Systems-Raghu-Ramakrishnan/dp/0071230572/ https://www.amazon.co.uk/Database-Management-Systems-Raghu-R...
stu__b 8y ago
Pro SQL Server Internals by Dmitri Korotkevitch https://www.apress.com/gb/book/9781484219638 https://www.apress.com/gb/book/9781484219638 It's specific to MS SQL Server but I found the chapters on log file management, indexes & isolation levels to be accessible and enjoyable.
skyde 8y ago
Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery (The Morgan Kaufmann Series in Data Management Systems) ISBN-13: 978-1558605084 https://www.amazon.com/dp/1558605088/?coliid=IYEILMZI5DVNM&colid=3A6FL78THXMIS&psc=0&ref_=lv_ov_lig_dp_it https://www.amazon.com/dp/1558605088/?coliid=IYEILMZI5DVNM&c... and Transaction Processing: Concepts and Techniques (The Morgan Kaufmann Series in Data Management Systems) ISBN-13: 978-1558601901 https://www.amazon.com/dp/1558601902/?coliid=I2GWJZ9XJ5D4JI&colid=3A6FL78THXMIS&psc=0&ref_=lv_ov_lig_dp_it https://www.amazon.com/dp/1558601902/?coliid=I2GWJZ9XJ5D4JI&...

rodw 8y ago

For complicated reasons I was involved in a successful project to develop an open-source, Oracle-SQL-compatible, transactional-integrity-preserving, extensible database designed for in-memory performance in Java. In the process of this development "suddenly" the reasons for a whole bunch of performance and syntax oddities in databases like Oracle and PostgreSQL became very clear. I was shocked to learn that was 15 years ago when I looked up the link to share, but if you are interested in the topic of "how to implement a database" it may be worth a look. For what it is worth it was listed (not by me) on the C2 Wiki on the "Programs to Read" Page, where it was described as "[A] database written in Java with good unit tests and ShortMethods." [1] Both statements are true, for a complete working example of a production database (it supported a commercial product for at least 10 years) it is actually a pretty accessible and well documented code-base. The project is called AxionDB and can be found at [2]. [1] http://wiki.c2.com/?ProgramsToRead http://wiki.c2.com/?ProgramsToRead [2] http://axion.tigris.org/source/browse/axion/ http://axion.tigris.org/source/browse/axion/

skunkworker 8y ago
Yup, a good way to understand why RDBMS are they way they are is to try to make your own in whatever language you choose. I've done this on a very elementary scale making a built in DB for a past project, at first it was single threaded, but when you start considering indexing and the datas structures necessary, it makes you understand and appreciate the man hours that have gone into projects like SQLite, PostgreSQL etc. At first you think, oh I can just write my own database, but when you start getting into areas and the CAP theorem starts to create problems, you really understand why anything past a local machine only ephemeral KV store is asking for trouble.
- rodw 8y ago
  Exactly. We sort of backed into this project by starting with HSQL (http://hsqldb.org/ http://hsqldb.org/) a low-end pure-Java "database" that was popular at the time. The more we used HSQL the more it became clear that it was more like a SQL-parser wrapping a simple key/value store than a full-on ACID database. We created AxionDB precisely because we needed the kinds of capabilities you mention and at the time HSQL did not provide them and wasn't remotely architected to support them. To be honest though, creating a moderately robust RDBMS from "scratch" turned out not to be the most ambitious or complex part of the overarching project that spawned AxionDB. The harder part was trying to use Java's primitive, built-in HTML-renderer to create something approximating a fully featured browser. The effort and complexity behind something like Gecko, WebKit, Edge, Blink, etc. is very easy to underestimate. It's a hard problem, made much harder by having to tackle the kinds of content you find "in the wild. Frankly building a database was a much more straightforward problem than that.

Mr_P 8y ago

How is this #2 on Hacker News? There's literally nothing here about how to actually build a database (yet?) Instead, there's just a key-value store implemented on top of a javascript hashmap and a filesystem.

capkutay 8y ago
This has to be a joke? This looks more like 'how to use a k-v store 101 for non programmers' I don't want to put more content under a terrible post, but the best resource for this material Jennifer Widom's MOOC. https://cs.stanford.edu/people/widom/DB-mooc.html https://cs.stanford.edu/people/widom/DB-mooc.html
- pedrosorio 8y ago
  I took this back in 2011 and don’t remember there being much on “building a database”. Is there more advanced content now?
thrower123 8y ago
I'd be very interested in a book or blog series similar to the scads of "how to build an os from scratch" or the raytracer projects, like Peter Shirley's little One Weekend series. Is there anything that scatches that itch?
- dymk 8y ago
  Nand2Tetris is a fan-favorite: https://www.nand2tetris.org/ https://www.nand2tetris.org/ Build a working Tetris game from literal logic gates up.
elrodeo 8y ago
I closed the page right after I read JavaScript.

hu3 8y ago

> teaches you how to create a database system from scratch with Node.js and JavaScript This can't possibly be serious

dymk 8y ago

Why would a pedagogical project choose JavaScript of all languages? Unless the project specifically needed to leverage features of the language, or a web browser, it's an incredibly poor choice for building anything with well maintained abstractions. Or anything at all ready, when the language is covered in warts. I imagine the author hasn't yet discovered for themselves why it's a poor choice, given only a key-value store has been implemented (using JSON.stringify, no less)

gtowey 8y ago
This was my thought as well. I'm curious to know if the author has previous experience building actual databases or if this is a case of follow-along-while-I-figure-this-out.
interesthrow2 8y ago
> Why would a pedagogical project choose JavaScript of all languages? I don't think the JS part is the issue. Node.js does I/O, files and co. The issue is that the article doesn't teach how to build a database at all. It doesn't explain how to efficiently persist and fetch data from a file, indexing strategies with trees, concurrent file access,locking, basic transaction... that's what I expect from a tutorial about how to build a basic DB system.
- dymk 8y ago
  Plenty of languages do I/O, files, and co. Why choose a language plagued with warts and a half-baked ecosystem for something pedagogical? A language with all sorts of peculiarities from the '95 browser era, and not at least leverage browser technology? A language which gives you very non-interesting coarse control over resource, and has no concept of parallelism?
  - raxxorrax 8y ago
    Easy access and fast results. Learning isn't about creating the best possible implementation. Python wpuld have been another suggestion from me personally. What language would you have used? A lot of people without a formal educational background start with established scripting languages. I you handle data, chances are that you will get in contact with javascript at some point. Using coffeescript or typescript would be a worse choice for learning, even if they counter some disadvantages of the base language in question.

alphabettsy 8y ago

Why the votes? There’s nothing there.

pictur 8y ago

just vote for the title.. this place is really very funny..

hugofirth 8y ago

Not a lot of content yet, but building databases (even toys) is an incredibly interesting exercise which I encourage many more people to try out, so +1! For anyone else who is interested in learning how to build a database, can I thoroughly recommend following along with Andy Pavlo's Advanced Database Systems course from CMU[1]. Every lecture is accompanied by reading lists, notes, and assignments. Whats more, I find Andy's style to be very easy to parse even on complex topics. Even if you think you know a fair bit about this domain, you will likely learn a lot! [1]https://www.youtube.com/playlist?list=PLSE8ODhjZXjYplQRUlrgQKwIAV3es0U6t https://www.youtube.com/playlist?list=PLSE8ODhjZXjYplQRUlrgQ...

theyoungwolf 8y ago

why the hell would you share this when its nowhere near done

truth_seeker 8y ago

Since you are creating a new file for each entry, I think BTRFS would be a good choice. https://en.wikipedia.org/wiki/Btrfs https://en.wikipedia.org/wiki/Btrfs