Very nice! If you wanted it to save to disk instead of living wholly in memory, how would you do that in C?
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
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?
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
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 !
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.
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
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.
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.
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...)
I call that a win! What was the logging mechanism--something bespoke? What was your solution?
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.
Welcome to systems programming....
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.