12 ms·
Writing a SQLite clone from scratch in C
- flunhat 9y agoVery nice! If you wanted it to save to disk instead of living wholly in memory, how would you do that in C?
- kevingadd 9y agommap! I mean, not really, but it's a surprisingly viable starting point for simple problems. I've shipped it. Some production-grade software still uses mmap, albeit with a bunch of additional complexity to make sure it works okay in weird cases. See this old comment thread I dug up that might be relevant: https://news.ycombinator.com/item?id=3982514 https://news.ycombinator.com/item?id=3982514 It seems like Redis might currently make use of mmap for some of its data, but I couldn't find an up-to-date source for that, just some old blog posts by the developer.
- pjc50 9y agoThe trouble is that naive mmap doesn't give you the control over write ordering that you need to implement reliability. Sadly, about 50% of database design is trying to ensure the thing has a decent chance of starting up again if it crashes or loses power. This mostly consists of fighting file systems and disk caches.
- lsllc 9y agoThere's `msync`
- valarauca1 9y agoThis is why msync is for. You can sync page by page and ensure ordering yourself.
- drfuchs 9y agoYou think you can, but you can't! Linux always sync's the whole file; see https://lwn.net/Articles/502612/ https://lwn.net/Articles/502612/ for a discussion of why fixing this horrible bug is too dangerous.
- icedchai 9y agoI used to work on a system that used mmap for basically everything, including a proprietary database that processed financial transactions. The original production system ran on a commercial Unix. (It's been about 15+ years, but I think it was AIX.) At one point, we ported it to a different Unix platform which had slightly different mmap semantics. It looked like everything worked, except for one minor detail: the data was never actually synced to disk. Ever. Until shutdown. Unfortunately, since the system ran 24/7, it effectively never synced. First time the system had a power failure, there was massive data loss on startup. Oops. (We were able to recover through log replay...)
- tomcam 9y ago> (We were able to recover through log replay...) I call that a win! What was the logging mechanism--something bespoke? What was your solution?
- imtringued 9y agoThat sounds like a terrible idea even if it were 100% reliable. When you shut down it will have to flush the entire memory at once. If you're syncing to a hdd it can mean several minutes of downtime.
- pjc50 9y agoA correctly working system will "flush behind", so there should be no difference between a clean shutdown and a power loss. If there's several minutes of unsynced data that's data that will be lost on power off.
- zero_iq 9y agoJust going to chip in here to mention LMDB, which essentially provides an mmap btree database with single writer + multi-reader snapshot concurrency, ACID transactions, and is extremely robust. If you think something may benefit from a shared memory data store, lmdb may be worth considering as a fast, reliable, high concurrency alternative to reinventing wheels with raw mmap + manual sync.
- switchbak 9y agoNot the OP here, but why the downvotes? Is this person off-base, or is that a poor solution?
- ovao 9y agoThe poster's comment reads a bit like an advertisement, but LMDB would be a good solution for persisting data, in my opinion. It has a pretty simple C API and it's been described by its authors as "crash-proof".
- pletnes 9y agoWhy not really? From the sqlite docs: Beginning with version 3.7.17 (2013-05-20), SQLite has the option of accessing disk content directly using memory-mapped I/O and the new xFetch() and xUnfetch() methods on sqlite3_io_methods.
- dkersten 9y agoI would say its less that you can’t or shouldn’t use mmap, and more that its not as simple as throwing mmap at it - if you care about crash recovery/not corrupting data (which most databases should care about), but that certainly doesn’t mean that mmap can’t be a part of the solution.
- convolvatron 9y agoi think that topic is larger than the presentation thus far. hopefully memory mapped flash will obviate the need for alot of this but: o you need to make an on-disk structure (i.e. btree) to let you search your tables (indices) o that has to be fronted by an in memory cache o your on-disk structure should maintain consistency even if the power fails and some writes get lost - often but not always this is facilitated by keeping a separate write-optimized structure called a write-ahead-log - if you use a WAL, you'll also need to implement the replay mechanisms to get the primary indices back up to date on a failure o because the disk operations are expensive and high latency you'll need to start managing concurrency explicitly back ends are alot of work. unfortunately this is a place where the lack of decent concurrency mechanisms in your language and OS interface can really cause alot of headache. pedagogically, i guess you would start with a completely synchronous non fault tolerant btree? or a maybe just the log, and introduce trees as a read accelerator?
- noam87 9y agoWhat are some good readings / places to start on this topic?
- convolvatron 9y agothats a really good question, unfortunately everything I learned was by working with people who knew more than I did. its pretty sad that alot of systems work is that way. this book looks to be pretty comprehensive, and explicitly discusses on-disk structures, write ahead logging, and recovery. http://infolab.stanford.edu/~ullman/dscb.html relational languages and transactions get alot more playin the academy..i think its because you can make sense of them in some abstract way without getting sucked into involved discussions about caching heuristics and OS write guarentees, scheduling and fussy performance characteristics
- jwhitlark 9y agoI like http://dataintensive.net/ http://dataintensive.net/, though it's a slightly different focus.
- flavio81 9y ago> Very nice! If you wanted it to save to disk instead of living wholly in memory, how would you do that in C? The idea would be to map your memory space to disk space (using random access as provided by C stdlib); the problem would then be: 1. Caching - i guess you should then provide your cache implementation. And i would guess this opens a can of sync problems... 2. Finding a way to efficiently write the data on disk (i.e. which data should stay contiguous?; how much "slack" space should i leave on "extents" (oracle slang for a container for many data blocks)? Should you do column-store? 3. Compacting the data (removing slack) etc etc. I think it's not easy at all !
- ddorian43 9y agoLmdb ?
- 72deluxe 9y agoC++ solution (the solution you didn't ask for, sorry) for saving to disk from memory (as some sort of periodic expensive sync) would be to write a stream operator for your objects and stream them to disk. Loading would involve reading them back; would only work on the same OS and architecture. Alternative approach: For Windows, you could just use disk but pass FILE_ATTRIBUTE_TEMPORARY to CreateFile to force it to be in memory if the file is small enough.
- somehnreader 9y agoHi, TUM has a lecture for this in which the students build a database in C and learning fundamentals along the way. I attended a few years back and learnt an awful lot, this is the course page: https://db.in.tum.de/teaching/ws1516/imlab/index.shtml?lang=en https://db.in.tum.de/teaching/ws1516/imlab/index.shtml?lang=... Haven't found the accompanying slides yet, but they must be somewhere on their website.
- stevoski 9y agoIf you prefer Java to C, I recommend taking a look at the source for H2, a pure Java SQL database engine. It is surprisingly easy to follow. I've contributed to the H2 source code a few times, and in the process I got to learn much about how a database engine is implemented. H2 home: http://www.h2database.com/ http://www.h2database.com/ H2 Github repo: https://github.com/h2database/h2database https://github.com/h2database/h2database
- mlvljr 9y agoAllen Holub did something like that for his patterns book, btw :)
- Luker88 9y agoThis comes right at a time when I started attempting something similar (though I don't care that much about documenting it) You might want to read some overviews on: * postgres atomicity: https://brandur.org/postgres-atomicity * postgres disk format: http://rachbelaid.com/introduction-to-postgres-physical-storage/ I have not read much on replication, though. Does anyone have any pointers?
- flavio81 9y ago> Does anyone have any pointers? Sure, here you are: void *x= malloc(16384) (Couldn't resist)
- mcguire 9y agoWelcome to systems programming, home of bad jokes and worse problems...
- flavio81 9y ago"I called the janitor the other day to see what he could do about my dingy linoleum floor. He said he would have been happy to loan me a polisher, but that he hadn't the slightest idea what he had done with it. I told him not to worry about it - that as a programmer it wasn't the first time I had experienced a buffer allocation failure due to a memory error." --- "Q: Why did the concurrent chicken cross the road? A: the side other To to get" (These were copied from the S.O. website)
- mcguire 9y agoOne piece of advice I'll never forget: Never grep a yacc by the i-node.
- wruza 9y agoI thought replication pointer would come from strdup() at least.
- robotresearcher 9y ago
- 14113 9y agoOn a related note (and this seems a good forum to ask), are there any typed databases available similar to sqlite?
- oblio 9y agoWhat do you mean by typed? :-?
- striking 9y agoSQLite will ignore most type information, instead choosing to focus on "type affinity": https://www.sqlite.org/datatype3.html https://www.sqlite.org/datatype3.html
- etatoby 9y agoI didn't know SQLite was dynamically typed. That's a strange choice for a database, to say the least. I would look into Berkeley DB (BDB) which is one of the most widely-used embedded databases, albeit not a SQL-based one. Otherwise take a look at the list of embedded databases on Wikipedia: https://en.wikipedia.org/wiki/Embedded_database https://en.wikipedia.org/wiki/Embedded_database
- herge 9y agoBerkley DB just stores byte arrays, so it is not 'typed' either.
- cat199 9y agoInitially (v < 3), all data fields in sqlite were text internally - type information was accepted for SQL compatibility, but ignored. This is actually an improvement. I'm not sure of the rationale; perhaps it's easier to keep the code / database files portable amongst different systems this way, and since it was designed for embedded use, many systems (and thus incompatibilites) were envisioned?
- herge 9y ago
- DLA 9y agoFollowing with interest. I would also LOVE to see a SQLite clone in pure Go. That would be amazing.
- pzduniak 9y agoIt's not a clone per se, but there's https://github.com/cznic/ql https://github.com/cznic/ql
- geodel 9y agoI think this one is sqlite: https://github.com/cznic/sqlite https://github.com/cznic/sqlite
- DLA 9y agoThanks geodel. Almost a win here, but if you look in sqlite/internal/bin/ you'll see cznic embeds the _entire_ SQLite c source.
- SwellJoe 9y agoI like short variable/type names much as the next guy, but this project takes that to a difficult-to-read extreme.
- marktangotango 9y agoWhat use case do you have such that the current crop of SQLite go bindings do not suffice?
- dkersten 9y agoEspecially given how battle tested (and unit tested!) SQLite is, while a clone.. would not be.
- DLA 9y agoUse case is mostly to learn how to be a Go ninja by building something as powerful as SQlite 100% in Go. For anything production grade the existing Go drivers or wrappers for SQLite are perfectly good. It would be nice to get a single binary, no dependency Go program though.
- piinbinary 9y agoOff topic: I appreciate how fast that site renders.
- Twirrim 9y agopingdom's insight is interesting: Other 43.1 % 20.36 KB Script 30.9 % 14.62 KB Image 15.5 % 7.33 KB CSS 5.3 % 2.52 KB HTML 5.1 % 2.40 KB Split out between: Image 25.0 % 2 Script 25.0 % 2 Other 25.0 % 2 HTML 12.5 % 1 CSS 12.5 % 1 So just 8 requests to build the page. 14.05 KB of the javascript is google analytics, so likely cached in the browser already. Nice, small, simple = quick :)
- rdslw 9y agoI'm also shocked. About two things: by the pure speed, and for me being surprised how fast it loads. Being surprised about webspeed in 2017 sounds like heresy.
- hollander 9y agoTo be honest, it always shocks me how long it takes for the average modern webpage to load. All the build up of things, the time it takes, and how unexpected it still is that you think you can click somewhere, and just 0.1 second before you click something else renders and moves everything up or down, making you click something else, which causes another page to load etc. I have a relatively new Mac with 8GB RAM - it should just work, but no...
- karmicthreat 9y agoIs there anything even close to SQLite in terms of reliability? Its pretty much the standard for embedded systems.
- amirouche 9y agowhat about wiredtiger?
- tyingq 9y agoInterbase is similar in purpose and has a good reputation. Not free or open source though.
- dfox 9y agoThere is Firebird which is essentially an opensouce InterBase (IIRC it is forked from IB5 source). It is probably more widely used than new commercial versions of IB. One interesting feature is that it is probably only opensource DBMS that not only works with multiple engines accessing same database stored on Windows share but it is actually supported usecase.
- noselasd 9y agoIf it's for embedded systems, Polyhedra from Enea is used in quiet a few high reliable and rugged systems.
- lifeisstillgood 9y agoThis strikes me as an interesting way to define a syllabus for comp sci / internship What other build X from scratch would be needed to cover much of what we think a grad should know? - build a language (compiler) from scratch - build a graphics engine from scratch - build a network stack (and firewall ?) Err?
- timClicks 9y agoCollaborative text editor (e.g. Etherpad/Google Docs)
- theprotocol 9y agoThis sort of question could make a really cool Ask HN topic!
- DLA 9y agoAdding to the 'from scratch' list... - build a simple virtual machine (pair with compiler) - build a distributed storage system (perhaps like S3) - build a traditional file system, perhaps as a FUSE (Filesystem in Userspace) - build a job scheduler (bonus: distributed cluster work scheduler) - build a memory allocator and/or a garbage collector - build a web server - build a crypto package (for learning only; don't really do this!)
- pjc50 9y agoRealistically as an undergraduate people might have time for one "build X from scratch", apart from tiny examples. My own attempt was a filesystem.
- dfox 9y agoI built webserver from scratch as a term project at university. Due that the fact that it actually did something self-contained and useful I got away with turning in C99 project for C++ course :) (and probably also because I wrote my own talloc/apr_pool-style malloc wrapper to base that on, when presenting the thing that was about as far as I got and then was told, "well, this is C++ course, but you got A and now go away") For another MSc. level course the whole term project assignment was: "choose or design some language and try to somehow conjure compiler and if required VM for that". "somehow conjure" is significant because nobody said you have to do that from scratch, hacking tcc/gcc/lcc/llvm to accept your language was fine and basing your language on top of some Smalltalk VM (preferrably ST/X ;)) or Common Lisp was essentially encouraged.
- wruza 9y agoA bit shameless to ask a question under top HN record, but I always wondered why do not SQL engines give access to their SQL AST to generate queries. Of course, one can combine a query from strings with placeholders, and it takes not so much comparing to actual querying process, but it feels so hacky. Why not provide something like: Query *q = db_select(db); db_add_from(q, "persons"); db_left_join(q, "companies", db_expr(DB_EQ, "per_id", "com_id")); Query *q = db_create_table(db); db_add_column(q, "id", DB_TYPE_INT | DB_COL_NOT_NULL | DB_COL_PRIMARY); db_set_table_name(q, "persons"); ... and so on? That way we could combine and generate queries for specific engines without that ugly string joining/parsing.
- xyzzy_plugh 9y agoI know a lot (a lot) of non-technical SQL users. SQL is a widespread abstraction from the underlying databases. It's very powerful. What you describe is useful from a programmer's point of view, but maybe the wrong abstraction. You could write such a thing which actually generates SQL from an API like you've defined. You could write an alternate ODBC engine. But there is a lot of overhead for database authours to actually provide an API like you describe. It's far simpler to provide something SQL-compliant with an ODBC or JDBC driver and now you can plug in almost anywhere. I have used a database engine that exposes primitives to build filters and similar programs to what you describe, and selectively push them to the server. It's not a very deep abstraction.
- deleted 9y ago[deleted]
- wcrichton 9y agoThis is essentially what an ORM does, e.g. SQLAlchemy [1]. Except instead of providing a slightly nicer API to generate query strings, an ORM tends to be more tied to the host language and use its object system to abstract out most of the SQL complexity and make declaring SQL tables/queries look like normal operations on the data themselves instead of the database. Django's ORM [2] for example autogenerates joins for you under certain query conditions, which is super handy. [1] http://docs.sqlalchemy.org/en/latest/orm/tutorial.html http://docs.sqlalchemy.org/en/latest/orm/tutorial.html [2] https://docs.djangoproject.com/en/1.11/topics/db/queries/ https://docs.djangoproject.com/en/1.11/topics/db/queries/
- zaidf 9y agoI wish someone would show how to rewrite Redux for React Native.
- ralusek 9y agoI can't tell if this was a joke or not, I'm assuming that it is. If not: Redux works the same way for React Native as it does for React or anything else.
- Sharma 9y agoYou mean something like this? https://zapier.com/engineering/how-to-build-redux/ https://zapier.com/engineering/how-to-build-redux/ http://www.jamasoftware.com/blog/lets-write-redux/ http://www.jamasoftware.com/blog/lets-write-redux/
- elymar 9y agoSQLite had a very rigorous testing methodology to comply with aeronautics standards. Cloning the tests would be a decade worth of work. But cool idea nonetheless. https://sqlite.org/testing.html https://sqlite.org/testing.html
- corndoge 9y agoBut the reference SQLite implementation is a single c file...
- asveikau 9y agoIt's actually written as several files and the "amalgamation" you download from the website represents those files concatenated together. See this explanation: http://sqlite.org/amalgamation.html http://sqlite.org/amalgamation.html
- devty 9y ago> The amalgamation file is more than 180,000 lines long and over 6 megabytes in size.
- nytopop 9y agoTo be fair, only 125,367 lines of that is actual c.
- asveikau 9y agoYes, but the article also says that file is generated by a makefile from more than a hundred .c and .h files, and that it's done for ease of distribution and because optimizers do better with a single compilation unit. It's not like the authors spend a lot of time working on the amalgamation and that's the way the project is developed.
- eberkund 9y agoDoes anyone know what software they used for creating those colored diagrams?
- Someone 9y agoThey are copied from http://sqlite.org/arch.html http://sqlite.org/arch.html, which is built from (see http://sqlite.org/download.html http://sqlite.org/download.html) data in Fossil at https://www3.sqlite.org/cgi/docsrc/timeline https://www3.sqlite.org/cgi/docsrc/timeline, which leads me to e.g. https://www3.sqlite.org/cgi/docsrc/artifact/d22a2c9642d584b8 https://www3.sqlite.org/cgi/docsrc/artifact/d22a2c9642d584b8, which seems to contain the right strings, so presumably is the file describing https://www.sqlite.org/images/arch2.gif https://www.sqlite.org/images/arch2.gif and its copy on https://cstack.github.io/db_tutorial/assets/images/arch2.gif https://cstack.github.io/db_tutorial/assets/images/arch2.gif That's fig source. So, I guess this was made by some GUI that uses fig as its native file format. My guess would be xfig (http://mcj.sourceforge.net http://mcj.sourceforge.net)
- std_throwaway 9y agoIsn't SQLite an application calling for a clean implementation in Rust?
- alecco 9y agoWhy? SQLite is one of the highest quality codebases out there! For fun, sure. But I think you are underestimating the size of the SQLite project and it's tests. Just because the library is small it doesn't mean it's simple.
- steveklabnik 9y agoIt's massive testing means that it would be easier to implement in another language; you'd be pretty sure of conformance with a port. That said, it's one of the most reliable projects in existence so why rewrite it?
- pygy_ 9y agoTo reboot WebSQL? IIRC Mozilla's main gripe with it was the fact that there was only one implementation, and no standard beyond "Whatever Sqlite3 does".
- acdha 9y agoHow would a rewrite change that? Addressing that objection would require some sort of open standards process and commitment to follow it, which is a rather orthogonal concern and would be somewhat expensive as well.
- pygy_ 9y agoYou'd also need to turn "whatever sqlitev3.x does" into a spec, indeed which is a lot of work that will never happen as there's only one implementation that passes the test suite.
- gr__or 9y ago
- maxpert 9y agoStill waiting for SQLite4 with it's awesome LSM engine :P (shameless plug I ported the engine over to windows https://github.com/maxpert/lsm-windows https://github.com/maxpert/lsm-windows and it works :D). I wish somebody can do a detailed architecture about SQLite4, that kind of knowledge is scares and valuable.
- beagle3 9y agoLSM engines tend to have great average but inconsistent performance. How does sqlite4's LSM fair? Last time I looked at benchmarks, sqlite4 with an LMDB backend was faster on average and had much lower variation in performance. Is that still the case?
- SQLite 9y agoFWIW, I'm presenting a talk on exactly this topic tomorrow at 12:30 at the http://www.db-tech-showcase.com/dbts/tokyo http://www.db-tech-showcase.com/dbts/tokyo - unfortunately I do not think it will be recorded.
- RainaRelanah 9y agoSlightly off topic, but thank you for your work on sqlite and fossil. I've used both daily for years and am always impressed by how consistently fantastic they are.
- sigzero 9y agoThat's pretty cool really.
- MBCook 9y agoI don't know why but unfortunately the various parts are effectively unreadable on an iPhone. The screen zooms in and out as you scroll, so that when you scroll the text is a little too tiny and when you stop the text is cut off on the left edge. I'm going to give it a try on my iPad. Just a heads up. Edit: works fine on an iPad. Interesting.
- gravypod 9y agoI'm very interested in seeing DROP implemented in this. It will be cool to see the author handle fragmentation.
- mopsy 9y agoThe language to access a relational database is always SQL. So much than a lot of people doesn't make any difference between SQL and a DBMS. Aren't we in the same situation as Javascript on the web? I always had wondered why there is no effort like Webasm for relational database. I would love to see a more vibrant scene with different syntax, paradigm and ideas. What would be the rust equivalent of a relational language, the Go equivalent? As an example, I had a lot of pleasure to read that blog : http://www.try-alf.org/blog/2014-12-03-what-would-a-functional-sql-look-like http://www.try-alf.org/blog/2014-12-03-what-would-a-function...
- belst 9y agoFor rust it would literally be Iterators
- nojvek 9y agoThis is exactly what I wanted. Thanks for sharing.