Thinking aloud about a database alternatve

20 May 2006

The idea is to write something that can persistently store values for applications where a database is overkill.

I suppose, ultimately, that my complaint isn’t with databases as an idea, it’s more with SQL and with their ubiquity and philosophy. the Berkeley database system is kind of like what I’m thinking of, architecturally, but I would like to allow both network and memory access to the database as well as allowing more dynamic querying of that Berkeley allows, but keeping the speed of something like BDB as much as possible. Also, it would be nice to see just how simple and primitive I can make the system, so it can be applied to as many problem domains as possible. In the end, it would be nice to have written something so simple and general that it’s quite easy to write a simple layer to get this system to act just like a SQL, Object, or Berkeley database.

Abstract.

Essentially there are a couple of standard, built-in types, from which all other types can be constructed, up to and including objects. It should be easy, at the end, to write a very thin layer for things like persistence of C++ or Python objects, but that isn’t the main goal. The main goal is to have a super quick and low resource server where you can store/retrieve data. Something like object prevalence layers for simple types, but a tad more robust (i.e. with built in networking and smart to-disk streaming).

The whole idea comes from hating databases and thinking that SQL sucks, so I’m not going to write any support for the most ‘advanced’ features of those systems. It’s overkill and really a bit too slow for a lot of high performance usage, and it makes it difficult to detect errors at runtime without a lot of expensive string parsing. There will be a per-thread errno and a ps_perror() which will explain, clearly, what went wrong, so the program using the store will be able to react appropriately.

Details.

Types:

• byte is the basic storage type. Anything can be expressed as an array of bytes, except perhaps booleans, which are a special case that I'm not really interested in supporting. although this will be the only type that's defined at base level, there will be several 'typedef-ed' types available at the user level and for programming convenience
• int: name of a class of types including s8, u6, s16, u16, s32, u32, s64, u64, etc.. stored in a machine independent order that be the same as network order so we don't have to translate them for sending over the wire, so can just send them out without translating the order.
• strings: arrays of bytes meant for holding characters. There will be subtypes for Unicode strings as well. strings over a certain size (1k or so) will be compressed by default.
• blobs: basically strings with no implied structure. an ordered array of unsigned bytes (or words, if that's faster). also compressed by default.
• dates: a special type of u64 with some assumed information about the content, which will be the number of seconds from the standard Unix epoch.
• handles: a special type of u64 which refers to another object known about by the same server. These handles are permanent and unique, and used for fast access to stored data.

Compression and other speed stuff:

• going to use libLZF, because, as the author says, it's essentially free on modern CPUs. All items will be stored in marshalled, compressed formats so that once they're located in memory or on disk they can be sent or copied immediately.
• when the server and the client are running on the same machine, the client library should transparently move to faster ipc methods than sending packets over the loopback interface. otherwise, the client side should just use sockets to talk to the server.
• chatter between the client and the server should be in a highly optimized binary format.
• not sure about threaded .vs event driven. will at least need some form of threading so that network/IPC speed doesn't lead to blocking on query fetches.
• the entire store set will be mmaped by default. This really isn't meant to take more than a couple of gigs of data, and the entire working set should be storable in memory. This is easy to get around, though. Most of the huge databases that I've heard of are storing giant binary blobs, which you can work around by just writing them out as files and then storing the file handle, and using already in place raid and backup mechanisms for safety, since I don't think that storing this stuff in a database vs. storing it on a file system buys you much.

Access:

• Should be able to define new types from primitive types on the client side. not sure whether this should happen on the client or server side. could just happen on the client side and then get transferred over to the server into a special store.
• queries are a sticky issue. not really interested in providing joins or other advanced and generally less useful-that-you-think database features. The idea here is that CMS of some sort should be able to be implemented without all of the pain of setting up and tuning a database, although, ultimately it stems from my desire to write MMO server systems that don't use databases. Not that I do that for a living, but, hey, a man can dream.
• a store call on the client side, if successful, should return an 8-byte handle (drawn from a pool of handles that are basically u64 integers). This should allow for space effective client side caching of fetched information.
• labels will also be allowed, which will allow a-list type access for searching for handles that you don't know about. unlabeled items will not have a space in the store's label hash, and cannot be searched for, except in relation to structures that hold the handle for those objects.
• editing structures to have new members and migrating all of the current data over should be easy, although it might be space expensive. There are a lot of issues here that would be best addressed after the process of writing the app has started, though, so it isn't entirely useful to speculate on it now.
• transactions and other functionality can be simulated by requesting locks. I don't want to build this in, really, as I think that it's an incorrect assumption that everything will need to be accessed by multiple clients. Stores may or may not be atomic by default, I've yet to decide.
• relational store/fetch (relational in terms of structure) should be easy.
• freeing memory allocated by the client is always the caller's responsibility.
• finally, named stores, which I feel that I should mention since I'm trying to be exhaustive, though it would seem intuitive.

Examples:

• The client creates (or perhaps has predefined) a structure called 'character'. This structure has several members and goes in a store of the same name. Each of the members, e.g. hp, class, mana, history, etc., will be a handle to some value in another store. So you would then be able to do a fetch(char_store_handle, "label", &character_struct); and the client library would, if it returns without error, fetch all of the information about that character and mutate the character_struct structure with the information that it fetches. It would then store the handle for fast store access when it needs to update or delete that structure.
• if the client wanted to sort all of the characters on the server by max_hp, say, it would then call a multi item fetch on the character store, grabbing the character's name and the handle of the associated value within the max_hp store. from there, how you get to the data, sort it and then present it are up to you, on the theory that optimizing code is easier than optimizing database queries.