11 ms·
Let’s Build a Simple Database (2017)
- gigatexal 8y agoThis is so cool! I’ve been wanting to do just this!
- parthdesai 8y agodoes anyone know if there is a similar tutorial in Rust?
- nkozyra 8y agoOf course[1], but this tutorial isn't about the language, per se, you should be able to translate it pretty trivially. These sorts of tutorials are more about the inner workings of database operation; I recall doing something like this in grad school but you're reminded quickly how more complex databases are than you think about when all you're doing is using them. And hell, I'm not even that good at using them. [1] http://nikhilism.com/post/2016/writing-simple-database-in-rust-part-1/ http://nikhilism.com/post/2016/writing-simple-database-in-ru...
- parthdesai 8y agoYeah, looks like translating it is a great way to learn both rust and how a db actually works internally.
- chalst 8y agoI'd say that if you want to learn Rust, then this is an excellent project. I'm not convinced that if you want to learn how databases work that Rust is a better language than C: it's more complex in that the checker makes you think about lots of non-db things, and simpler in maybe a non-helpful way, in that the language provides lots of high-level facilities that it might be good to work out explicitly.
- parthdesai 8y agoConsidering that i'll have to learn C for this as well, i think going with Rust just looks more interesting.
- sten 8y agoCould I trouble you to give me an example of the second one? Something rust provides that might be better to learn the hard way?
- MehdiHK 8y agoAnd anything in Go?
- tyingq 8y agoAnother exercise that's fun is playing with Sqlite virtual tables and/or the Sqlite VFS layer. Virtual tables: https://www.sqlite.org/draft/vtab.html https://www.sqlite.org/draft/vtab.html A simple example of using VFS to add a useful feature: https://github.com/Metalnem/sqlite-vfsdemo https://github.com/Metalnem/sqlite-vfsdemo
- titanix2 8y agoThanks a lot. I planned to implement virtual SQL tables for a project and wasn’t aware of existing product. This probably will save me a lot of time.
- bshipp 8y agoDon't forget about the 'ATTACH DATABASE' option as well. It is great for linking up individual SQLite databases when you need to do a broad-based query across multiple sources. https://www.sqlite.org/lang_attach.html https://www.sqlite.org/lang_attach.html If you use a GUI front-end like SQLiteStudio (https://sqlitestudio.pl/ https://sqlitestudio.pl/), attaching databases is ridiculously easy to do. Just add the database name from the left column in front of the table or table.column label for the database you want to reference. Most SQLite GUI's will do the attach command for you internally. I add the database name to my queries instinctively now in SQLiteStudio, so that no matter which DB is currently in focus/opened the query runs on the one I intended it to run on.
- mappu 8y agoYou might also be interested in https://github.com/src-d/go-mysql-server https://github.com/src-d/go-mysql-server , a Go library for putting a MySQL-compatible frontend over a custom virtual data source.
- titanix2 8y agoI know nothing about Go but the project is indeed interesting. Thanks.
- charlysl 8y ago
- stevoski 8y agoAwesome stuff. Java programmers: if you are curious about how an SQL database works, take a look at H2's source (https://github.com/h2database/h2database https://github.com/h2database/h2database). You can even try to fix an outstanding issue. It is illuminating - and much easier than you would have thought.
- thomascgalvin 8y agoFor a while now, I've used H2 as the in-memory database for a bunch of Selenium and Spring Boot integration tests. The primary advantages are 1. speed and 2. simplicity. Simplicity is the big thing here; I can configure Spring to launch an in-memory H2 database and not have to worry about state, clearing and reseeding, or any of that stuff. The integration tests can just run. I've been so happy with it that I'm pushing a customer to use H2 in production. I would normally use Postgres, but my customer doesn't really have an IT staff, and an embedded database will be a lot easier for them to keep up and running.
- jsight 8y agoYeah, H2 is amazingly good. I've used it for things that most Java developers insist it can't be used for. :) Just understand that any use that even vaguely resembles production will usually get pushback from people who think it is only a dev-level in-memory-only toy that causes constant slowdowns. This will be true even if it is only used for a few hundred rows worth of data.
- esfandia 8y agoWouldn't your customer lose all their data if the app crashes?
- geeio 8y agoH2 has a disk persistence mode. Though I’d probably use SQLite for this use case
- bozoUser 8y agoHey @stevoski can you recommend one of the very basic issues to look at for someone to ramp up on the codebase ? Thanks
- eunos 8y agoVery interesting! However I wonder whether it's possible to do it on OOP languages such as Java.
- bunderbunder 8y agoWhy wouldn't it be?
- jimbokun 8y agohttps://news.ycombinator.com/item?id=19582150 https://news.ycombinator.com/item?id=19582150
- macintux 8y agoThe good news is that an OOP language is a superset of imperative languages like C. The more general answer is that all Turing-complete languages are functionally equivalent. The misery level varies, as does the applicability to any given project, but anything you can do in C you can also do in Java, Python, Lisp, Erlang, Forth, ad nauseum.
- p4bl0 8y agoIt's already almost the case. Juste rename structure X in class X and make every X_xxx functions a xxx method of class X and you're almost set.
- mschaef 8y agoReally glad to see this... this has often seemed to me to be a nice sort of capstone project for an undergraduate degree program. (Covers real implementation of everything from networking, datastructures, language parsing, etc.)
- kakaoscott 8y agoHey thanks a lot for making an education program for a simpleton like myself.
- MuffinFlavored 8y agoI can't tell if this is "finished" or not. It'd be cool if somebody benchmarked this to show just how "fast" SQLite is comparatively, even if they are by no means equal functionality wise.
- bshipp 8y agoI tend to use postgresql in my daily work now but I will always carry a flame for sqlite, my first DB experience. I still use it for rapidly parsing and normalizing huge text files, as well as the backend for numerous one-off webscrapers. I contend there are few faster ACID-compliant database options for high-speed input, without moving toward a complex multi-machine distributed solution. Combined with a high-speed SSD or an in-memory database, that single write-worker can often put any high-concurrency single-machine database to shame, as long as some thought is put into the code. There is something deeply satisfying about writing a short python script and then watching a 5gb text file or a huge directory of log files get chewed up and spit out into a tidy little perfectly normalized and portable database. Bliss. Just between you and me, sometimes I download a hundred thousand files to process just for fun. It's not right.
- MuffinFlavored 8y agoDo you know how Elastisearch/Splunk are all the rage these days? I feel like those are super heavy. What are your thoughts on https://github.com/brandonros/log-indexer https://github.com/brandonros/log-indexer?
- bshipp 8y agoAs with anything, it depends on what you want to do. One of my SQLite databases has a text column that's 500 million rows (it's an 80GB file). Even with a standard COLLATE NOCASE b-tree index, searching out a word in the middle of a tuple takes a ridiculously long time (although finding that word at the beginning of the tuple is amazingly quick). A solution like Elasticsearch, while indeed heavier, is designed to deal with that kind of issue so, in my humble opinion, makes sense when you actually need a broad search capability. As for the solution in https://github.com/brandonros/log-indexer https://github.com/brandonros/log-indexer, it seems like a tidy little solution to the problem of having to parse log files later. Not only does it provide a rapid way of looking up information when you're trying to solve a problem, but SQLite also acts as a compression archive of sorts as well. I didn't look all that closely at the internals of the index.js script in that repo, but if it's still storing any of the records as JSON you can still access the internal data held inside the log record with SQLite's own JSON1 extension (https://www.sqlite.org/json1.html https://www.sqlite.org/json1.html). That would save a pile of time compared to a broad-based directory search for text file contents. A few lines for a SQL query and instantly you'd have every occurrence of that error since the program started logging. I'd think that's a very useful tool!
- ignoramous 8y agoFolks interested in this sort of thing might like Anatomy of a Database System by Stonebreaker et al, which I think is the most concise treatment on the subject: http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf Also, see Redbook for the latest ensemble of research ideas in databases. http://www.redbook.io http://www.redbook.io
- alexchamberlain 8y agoThe Redbook looks like an awesome resource. I think it's a real shame that find resources at the intermediate level of database system design is so hard; feels very much like the "how to draw an owl" meme
- mathnmusic 8y ago> it's a real shame that find resources at the intermediate level of database system design is so hard This is a common problem across subjects. Learning resources need to be curated topic-wise, format-wise, & difficulty-wise. Some of us have started doing this over here: https://github.com/learn-awesome/learn-awesome https://github.com/learn-awesome/learn-awesome Join in and help curate the database systems topic? https://github.com/learn-awesome/learn-awesome/blob/master/databases.md https://github.com/learn-awesome/learn-awesome/blob/master/d...
- barbecue_sauce 8y agoAlso, Andy Pavlo's CMU Database Group courses on Youtube.
- ccleve 8y agoI have spent quite a lot of time building a database in Java. It's not a small undertaking. I've gone through as many books and papers as I can, and there is only one, one, that gives an overview and actual examples of building a system that processes SQL. Everything else is theoretical or so general that you don't get enough direction to get started. It's "Database Design and Implementation" by Sciore. It's a little dated, but not by much. It is an underappreciated resource.
- fgonzag 8y agoYou could have read the source to the processor of one of the many open source SQL databases though (off the top of my head: MySQL, PostgreSQL, SQLite, Derby, H2, HSQLDB). Many of them have very clean code, SQLite would be my choice if you know C otherwise one of the java databases (though I've never actually read their source)
- macspoofing 8y agoThis. Here's an anecdote: one my friends worked for a startup that at the height of NoSQL hype (circa 2012) decided to build their product on Cassandra. The data they dealt with was highly relational with hard requirements on consistency. He told me working on a NoSQL database taught him a lot about relational databases, because he scoured the Postgres source code to learn how to implement consistent and durable commits across distributed/sharded nodes.
- haggy 8y agoOK I'll say it... Your friend chose wrong. HORRIBLY wrong. I have a lot of experience with both Postgres and Cassandra and the fact that your friend chose Cassandra despite their data model being relational AND having high consistency requirements shows that they chose Cassandra for the wrong reason(s). Before you come back saying something about scalability, I've run both databases at way above average scale so what you choose should come down to what you need, which is not what was done in this case (your friend)
- mathgladiator 8y agoI love this kind of stuff since I started my own database from a different angle. Namely, I code generate everything do all indexing in memory. It's been fun, and rock solid for single host monolith web app.
- alecco 8y agoCMU Andy Pavlo’s lectures on YouTube are great and also shows state of the art. Start there.
- zerr 8y agoNot sure, I've watched several lectures and I've got an impression that they are too theoretic. As I remember they even don't implement the database system, but some very specific part in some existing system.
- charlysl 8y agoBut can you really build a db system without knowing some theory first (at the very least, key concepts and implementations), and learning from past mistakes and hits, and learning db history and know where and why things might be going?
- zerr 8y agoOf course I see your point. Nevertheless, there are theoretic and practical/engineering approaches to education. The above mentioned lectures lacked the latter one, at least that's my impression.
- charlysl 8y agoBut those are just the lectures. The course also includes several substantial labs that consist of extending sqlite ([1], under Projects; starting code in [2]). This course gives you both. I don't think you have a chance of doing these labs without knowing some non-trivial theory first, never mind creating a production ready db that adds any value (and this includes algorithm and OS theory/systems programming, and maybe distributed systems too, prereqs for any db course, and also in practice). My motto: If you skip the theory, you will start sooner. If you know the theory, you will finish sooner (or at all). [1] https://15445.courses.cs.cmu.edu/fall2018/assignments.html https://15445.courses.cs.cmu.edu/fall2018/assignments.html [2] https://github.com/Nov11/15-445 https://github.com/Nov11/15-445
- lmilcin 8y agoWriting a database is a good exercise I could recommend to everybody. Writing a general purpose database is very difficult. On the other hand, if you know what kind of load you can expect and when you have an idea of performance and consistency requirements it may become much simpler. I have rolled out my own transactional database for a commercial project. This was a decade ago, the device had at most 1MB of memory budget for compiled code, stack, heap, and database storage. The database was to be stored on a non-wear-leveled flash requiring precise control of which bytes and how frequently were erased. We required ability to store small objects (tens to few hundreds of bytes at most) of varying size and be able to record changes to multiple objects at the same time, transactionally (think modifying two accounts). The requirement was that the database stayed consistent no matter what happened, regardless of any application error or power cycles. These devices were operated by hundreds of thousands of customers and power cycled liberally whenever anything didn't work. The database run in constant memory. It allowed the application to register hooks to calculate deltas between two versions of records and to apply delta to base version to produce result version. The database didn't care how the data was encoded, this was application detail. The database was stored as transaction log. During operation, all writes were directed to the end of the log. When the log reached half of the available memory, all live records would be coalesced and written to the other half of the space and the original space would be erased. The read algorithmic complexity was horrible with some algorithms being cubic(!) complexity. This was absolutely ok, since there could never be enough records that would make it a problem. Having extremely simple algorithms allowed for the entire code to be very simple and compact. Everything fit about 200 lines or so lines of code. I really enjoyed the project.
- fizwhiz 8y agoHow long did it take to implement, and how large was the team?
- lmilcin 8y agoI did this alone. The database itself was only about 200 lines of code but took about three weeks of effort which included writing the initial implementation, refactoring it, writing performance test, optimizing the implementation for the intended load and integrating in the application. The application was much larger, about 40k LOC and took about two and a half years to complete, certify and deploy to production.
- cryptokernel 8y agojust leaving this here: https://coincircle.com/l/50VVxbObg3 https://coincircle.com/l/50VVxbObg3
- chirau 8y agoI believe the simplest database is this: #!/bin/bash db_set () { echo "$1,$2" >> database } db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1 }
- pmccarren 8y agoLet's optimize! #!/bin/bash db_set () { echo "$1,$2" >> database } db_get () { # read database line by line in reverse, stopping at first match tac database | grep -m 1 "^$1," | sed -e "s/^$1,//" }
- stickmanpagemov 8y agomore like butt