I’ve talked a bit about databases, and it’s an open secret that I’m doing some unusual stuff with mine. Here is an example of how I approached a problem that is familiar to anyone who has worked with databases.
Groups: in typical DB parlance you say there’s a many to many relationship between groups and users.
The big idea is to answer these questions:
- What groups is user X enrolled in?
- What users & groups are enrolled in group Y?
RethinkDB is a startup that is ‘Rethinking Databases’, they are making a new databases optimized for today’s hardware (like fast random-access disks) and research (like append only databases).
Lots of their blog posts are pretty interesting, especially to me since my project, FormLis, is powered by a database I wrote myself. So I contrast how they solve problems and how I did.
It sounds to me like they have a thread per cpu that accesses the database, and these threads request resources and block until they are ready (they probably wait on a disk-fetching thread). Multiple threads from a program talk to these database threads, so the database threads don’t like to wait for the disk, when they could be doing work for a different program thread.
Previously they implemented blocking and notification with call backs, but found it unsatisfactory, because you had to split your logic into several parts — the forward parts and the callback parts — implement them as methods and bundle them into a class. You also had to keep your variables as instance variables.
Using co-routines, you can do a more C-like approach. Instead of using objects-representing-logic, you make callbacks by cloning the stack and bundling it into a co-routine. Because you copied the stack, both the co-routine callback and the original caller can see and (safely) modify your existing local variables. The effect is that callback code is written inline with regular code, and can use local variables; its a lot like a closure, but more heavy-weight.
So, how does FormLis do it? Well for starters I only have 1 database, sitting in (essentially) unpartitioned space. RethinkDBs use case is multiple databases on multiple drives, operating concurrently with (say) apache that’s reading files almost at random. So for them it makes a lot of sense to not wait, but go on and access the next file. For me, I only have 1 databases that has structures to multiplex to multiple clients, It makes sense to wait.
RethinkDB also uses their co-routines for high level operations that do block. Here FormLis is different, because there is no (long term) blocking at the high level (the only waits are for mutexes). My use case is many, many more readers than writers (an assumption RethinkDB can’t make). I designed my database so that every transaction runs (successfully) to completion, and only when they try to commit do I throw an error that essentially says “Oh sorry, another transaction collided with you, and you’ve been toast for a while now.” At this point my transaction just does a GOTO back to where the transaction started and reruns it.
Thats another advantage to my database, because of my restricted domain, every transaction comes from only a few places in my Lisp code. I don’t have to handle transactions in a generic sense like a SQL db. So when a transaction fails, I don’t have to examine what it did to try it again, I just GOTO.
“Today the main applications are all database applications; the real-time applications having been replaced by turnkey systems that connect serially. The main applications are RT order entry, billing, PFT/Exercise data and ABG lab data. There are over 5,000 blocks of active Forth source code – perhaps”
Most languages have some libraries to connect to databases; modern languages often include one in the standard distribution. Forth is an exception. There don’t seem to be libraries to connect to standard SQL databases, and forth programmers don’t care. When forth programs need a database, they don’t use familiar ones. Read the rest of this entry »