Let’s Build a Simple Database (2017)
cstack.github.io
cstack.github.io
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.
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.
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)
Yeah, obviously. Also, he didn't choose anything. The tech stack was mandated on him.
And it is a skill, I also had a lot of trouble with it initially, but diving into several open source projects was the perfect way to practice it, and it helped me tremendously in my professional development.
For example, I would make sure to read about B+ trees first, before reading the implementation of indexes in SQLite or PostgreSQL.
I find that without knowing where to direct my attention, it is really hard to avoid getting distracted.
https://ocw.mit.edu/courses/electrical-engineering-and-compu...
Also, see Redbook for the latest ensemble of research ideas in databases. http://www.redbook.io
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
Join in and help curate the database systems topic? https://github.com/learn-awesome/learn-awesome/blob/master/d...
Virtual tables: 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://www.sqlite.org/lang_attach.html
If you use a GUI front-end like SQLiteStudio (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.
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.
The application was much larger, about 40k LOC and took about two and a half years to complete, certify and deploy to production.
This notion that a database must be a difficult and complex thing and best left for experts is just turning people off from exploring and learning.
When it doesn't need to be general purpose, has only one thread accessing it, stores at most 1MB of data, has only KV access (so basically persistent hashmap) and doesn't have to be blazing fast, the resulting code may be very simple.
In early 2001, for the project I was working on then, we needed something like a SQLite-lite. (SQLite existed, but was less than a year old and was still way bigger than our needs.) One of the other engineers and I paired to build something that worked well enough to run with over the course of a weekend, and then polished and improved it along the way, until the project was abandoned a few months later, because of the dot-com bomb.
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
} #!/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,//"
}Java programmers: if you are curious about how an SQL database works, take a look at H2's source (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.
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.
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.
Though I’d probably use SQLite for this use case
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.
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.
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, 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). 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!
> A solution like Elastisearch, 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.
Hmm... at a high level, how do Elasisearch a) consist huge amounts of data to disk and b) making searching 80gb and way way up of logs fast?
Basically it examines each record you want to index and generates a set of features and metadata to aid in rapidly finding what you're looking for. Some of the features listed on that site are:
ranked searching -- best results returned first
many powerful query types: phrase queries, wildcard queries, proximity queries, range queries and more
fielded searching (e.g. title, author, contents)
sorting by any field
multiple-index searching with merged results
allows simultaneous update and searching
flexible faceting, highlighting, joins and result grouping
fast, memory-efficient and typo-tolerant suggesters
pluggable ranking models, including the Vector Space Model and Okapi BM25
configurable storage engine (codecs)
Lucene notes the position of each word in a text string and has a number of techniques to figure out which records have words similar to the ones you're looking for, at relatively similar positions (i.e. close to each other, in the same order, etc) and narrows the search scope to those records. In short, it's not searching the individual records, it's searching it's own database for what it already knows about the contents of that record.
EDIT: however, for a log search a b-tree would still be fine, because every log entry generally would have a similar structure. For example, if you're looking for a specific error message, that message is not going to dramatically change from one moment to the next. So having that table/column indexed with a b-tree would allow you to search for that specific error string and quickly pull up all the results, regardless of size.
Just make sure you set up your SQL query to have a line like:
WHERE column.errorvalue LIKE 'Generic Error Code 1%'
WHERE column.errorvalue LIKE '%Code 1%'
That said, if you think you're going to get to 80GB you might want to look at an alternatively solution to SQLite or, at the very least, version your databases by month and then use the ATTACH DATABASE command if you need to mine historical data (or even write a small script to search each database individually). SQLite isn't really designed to separate tables across different disks and it's not fun to regularly have to back up 80GB files.
What a time to be alive! I've just started populating the sqlite virtual fts table. I will report back with my findings!
The reason it ran out of disk space is that I included 3 columns to index on (in this case: name, path, filename) and it ballooned my 66GB db to 185GB!
However, every single query afterward was instantaneous. Literally milliseconds to pull 90K results from three full-text columns across 500 million rows. And the search words were anywhere in the column, not just the beginning. Incredible. I'm simply blown away.
All I did was this single command: CREATE VIRTUAL TABLE fts USING fts5(hash UNINDEXED, title, path, filename);
and then wrote a normal INSERT statement to populate it like I would a regular table. It was so painless.
Just be aware that each column appears to drastically increase the size of the DB.
I'm so excited! I have so many other databases to try this out on!
EDIT: now I'm going to move it off the SSD to a mechanical drive and see if it still holds the same performance.
Also it is all just very interesting.
> The next step should be splitting internal nodes. Until then!
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
How different is this book from his class notes, titled "Database Management: A Systems Approach Using Java"?
I wonder if his SimpleDB [1] is the same SimpleDB that is used in the MIT and Berkeley db intro courses, that would be a great match.
Do you happen to know of any other books, not about databases, that do a similar job for other complex systems? For instance, for OSs there is xv6 and its companion book [2].
EDIT:
Just one observation: the first lab in the CMU course consists of implementing a Buffer Pool Manager. This basically means bypassing the OS virtual memory management, which is too general and far from optimal for a disk storage db, and implementing you own, in this case a sqlite extension in C++ (the idea seems to me sort of similar to implementing a bespoke, optimized malloc, not exactly, of course). Now, Sciore's SimpleDB is written in Java, so I suppose that this can't be done, so it's a much simpler system, and passes over what is a key issue in a production class system.
This is also relevant for one more reason, which is that, although this CMU intro course doesn't really focus on memory caching issues (disk access trumps the cache), Pavlo's follow up course, Advanced DBs [3], is about in-memory db systems, and here the memory cache is very much a central issue, and I doubt, again, that a db written in Java can take this into account, I suspect that you need a systems programming language to handle this. So, this might be a reason to favour the CMU course, I am not sure, I am new to the game.
[1] http://www.cs.bc.edu/~sciore/papers/SIGCSE07.pdf
The MIT OCW SimpleDB seems different from Sciore's though, simpler, but is also in Java, I wonder whether they have adapted it or whether it is entirely different system.
Sciore's old db course, might help figure out how much material to pack into a terms-worth of learning, but the notes aren't there, you will find then in the internet if you know where to look :) https://web.archive.org/web/20081028011620/http://www.cs.bc....
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.
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-ru...
https://doc.rust-lang.org/reference/dynamically-sized-types....