association-list

The idea is to write some­thing that can per­sis­tently store values for appli­ca­tions where a data­base is overkill.

I sup­pose, ulti­mately, that my com­plaint isn’t with data­bases as an idea, it’s more with SQL and with their ubiq­uity and phi­los­o­phy. the Berke­ley data­base system is kind of like what I’m think­ing of, archi­tec­turally, but I would like to allow both net­work and memory access to the data­base as well as allow­ing more dynamic query­ing of that Berke­ley allows, but keep­ing the speed of some­thing like BDB as much as pos­si­ble. Also, it would be nice to see just how simple and prim­i­tive I can make the system, so it can be applied to as many prob­lem domains as pos­si­ble. In the end, it would be nice to have writ­ten some­thing so simple and gen­eral that it’s quite easy to write a simple layer to get this system to act just like a SQL, Object, or Berke­ley database.

Abstract.

Essen­tially there are a couple of stan­dard, built-​​in types, from which all other types can be con­structed, up to and includ­ing objects. It should be easy, at the end, to write a very thin layer for things like per­sis­tence 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. Some­thing like object preva­lence layers for simple types, but a tad more robust (i.e. with built in net­work­ing and smart to-​​disk streaming).

The whole idea comes from hating data­bases and think­ing that SQL sucks, so I’m not going to write any sup­port for the most ‘advanced’ fea­tures of those sys­tems. It’s overkill and really a bit too slow for a lot of high per­for­mance usage, and it makes it dif­fi­cult to detect errors at run­time with­out a lot of expen­sive string pars­ing. There will be a per-​​thread errno and a ps_​perror() which will explain, clearly, what went wrong, so the pro­gram using the store will be able to react appropriately.

Details.

Types:

• byte is the basic stor­age type. Any­thing can be expressed as an array of bytes, except per­haps booleans, which are a spe­cial case that I’m not really inter­ested in sup­port­ing. although this will be the only type that’s defined at base level, there will be sev­eral ‘typedef-​​ed’ types avail­able at the user level and for pro­gram­ming convenience
• int: name of a class of types includ­ing s8, u6, s16, u16, s32, u32, s64, u64, etc.. stored in a machine inde­pen­dent order that be the same as net­work order so we don’t have to trans­late them for send­ing over the wire, so can just send them out with­out trans­lat­ing the order.
• strings: arrays of bytes meant for hold­ing char­ac­ters. There will be sub­types for Uni­code strings as well. strings over a cer­tain size (1k or so) will be com­pressed by default.
• blobs: basi­cally strings with no implied struc­ture. an ordered array of unsigned bytes (or words, if that’s faster). also com­pressed by default.
• dates: a spe­cial type of u64 with some assumed infor­ma­tion about the con­tent, which will be the number of sec­onds from the stan­dard Unix epoch.
• han­dles: a spe­cial type of u64 which refers to another object known about by the same server. These han­dles are per­ma­nent and unique, and used for fast access to stored data.

Com­pres­sion and other speed stuff:

• going to use libLZF, because, as the author says, it’s essen­tially free on modern CPUs. All items will be stored in mar­shalled, com­pressed for­mats 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 run­ning on the same machine, the client library should trans­par­ently move to faster ipc meth­ods than send­ing pack­ets over the loop­back inter­face. oth­er­wise, the client side should just use sock­ets to talk to the server.
• chat­ter between the client and the server should be in a highly opti­mized binary format.
• not sure about threaded .vs event driven. will at least need some form of thread­ing so that network/​IPC speed doesn’t lead to block­ing 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 work­ing set should be stor­able in memory. This is easy to get around, though. Most of the huge data­bases that I’ve heard of are stor­ing giant binary blobs, which you can work around by just writ­ing them out as files and then stor­ing the file handle, and using already in place raid and backup mech­a­nisms for safety, since I don’t think that stor­ing this stuff in a data­base vs. stor­ing it on a file system buys you much.

Access:

• Should be able to define new types from prim­i­tive 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 trans­ferred over to the server into a spe­cial store.
• queries are a sticky issue. not really inter­ested in pro­vid­ing joins or other advanced and gen­er­ally less useful-​​that-​​you-​​think data­base fea­tures. The idea here is that CMS of some sort should be able to be imple­mented with­out all of the pain of set­ting up and tuning a data­base, although, ulti­mately it stems from my desire to write MMO server sys­tems that don’t use data­bases. Not that I do that for a living, but, hey, a man can dream.
• a store call on the client side, if suc­cess­ful, should return an 8-​​byte handle (drawn from a pool of han­dles that are basi­cally u64 inte­gers). This should allow for space effec­tive client side caching of fetched information.
• labels will also be allowed, which will allow a-​​list type access for search­ing for han­dles that you don’t know about. unla­beled items will not have a space in the store’s label hash, and cannot be searched for, except in rela­tion to struc­tures that hold the handle for those objects.
• edit­ing struc­tures to have new mem­bers and migrat­ing all of the cur­rent data over should be easy, although it might be space expen­sive. There are a lot of issues here that would be best addressed after the process of writ­ing the app has started, though, so it isn’t entirely useful to spec­u­late on it now.
• trans­ac­tions and other func­tion­al­ity can be sim­u­lated by request­ing locks. I don’t want to build this in, really, as I think that it’s an incor­rect assump­tion that every­thing will need to be accessed by mul­ti­ple clients. Stores may or may not be atomic by default, I’ve yet to decide.
• rela­tional store/​fetch (rela­tional in terms of struc­ture) should be easy.
• free­ing memory allo­cated by the client is always the caller’s responsibility.
• finally, named stores, which I feel that I should men­tion since I’m trying to be exhaus­tive, though it would seem intuitive.

Exam­ples:

• The client cre­ates (or per­haps has pre­de­fined) a struc­ture called ‘char­ac­ter’. This struc­ture has sev­eral mem­bers and goes in a store of the same name. Each of the mem­bers, e.g. hp, class, mana, his­tory, 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 with­out error, fetch all of the infor­ma­tion about that char­ac­ter and mutate the character_​struct struc­ture with the infor­ma­tion 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 char­ac­ters on the server by max_​hp, say, it would then call a multi item fetch on the char­ac­ter store, grab­bing the character’s name and the handle of the asso­ci­ated 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 opti­miz­ing code is easier than opti­miz­ing data­base queries.