Life is subdued to constant evolution. So is our data, be it in research, business or personal information management. As such it’s surprising that databases usually just keep the current state. With the advent, however of flash drives as for instance SSDs, which are much faster in randomly accessing data in stark contrast to spinning disks and not very good at erasing or overriding data, we are now capable of developing clever versioning algorithms and storage systems to keep past states while not impeding efficiency/performance. Search/insertion/deletion-operations should therefore be in logarithmic time (O(log(n)), to compete with commonly used index structures.
Sirix is a storage system, which is log-structured at it’s very core. Reads can be random and writes are batched and synced to disk during a transaction commit. Data is never written back to the same place and thus not modified in-place. Instead, Sirix uses copy-on-write (COW) at the record-level (thus, it creates page-fragments and usually doesn’t copy whole pages). Everytime a page has to be modified records, which have changed arewritten to a new location. Which records exactly are copied depends on the versioning algorithm used. It’s thus especially well suited for flash-based drives as for instance SSDs. Snapshots, that is revisions of the data are stored during each transaction commit in a postorder-traversal of the internal index. Apart from a numerical revision-ID, the timestamp is serialized. A revision can afterwards be opened either by specifying the ID or the timestamp. Using a timestamp involes a binary-search on an array of timestamps, stored persistently in a second file and loaded in memory on startup. The search ends if either the exact timestamp is found or the closest revision to the given point in time.
Changes to a database/resource occur within a resource-bound transaction. Therefore a ResourceManager has to be opened to create a write-transaction. At any time only one write-transaction concurrently to N-read transactions is permitted. Each transaction is bound to one revision, whereas they can be opened on any revision, it doesn’t matter which one.
The following shows a simple Java code to create a database, a resource within the database and the import of an XML-document. It will be shredded to our internal representation (which can be thought of as a persistent DOM implementation, thus both an in-memory layout as well as a binary serialization format is involved).
The native storage of JSON will be the next. In general every kind of data could be stored in Sirix as long as it can be fetched by a generated sequential, stable record-identifier, which is assigned by Sirix during insertion and a custom serializer/deserializer is plugged in. However, we are working on several small layers for natively storing JSON data.
Vert.x on the other hand is closely modeled after Node.js and for the JVM. Everything in Vert.x should be non blocking. As thus a single thread called an event-loop can handle a lot of requests. Blocking calls have to be handled on a special Thread Pool. Default are two event-loops per CPU (Multi-Reactor Pattern).
We are using Kotlin, because it’s simple and concise. One of the features, which is really interesting are coroutines. Conceptually they are like very lightweight threads. Creating threads is very expensive on the otherhand. The cool thing about coroutines is, that they allow to write asynchronous code almost like sequential. Whenever a coroutine is going to be suspended, the underlying thread is not blocked and can be reused. Under the hood each suspending function gets another parameter through the Kotlin compiler, a continuation, which stores where to resume the function (normal resuming, resuming with an exception).
Keycloak is used as the authorization server via OAuth2 (Password Credentials Flow), as we decided not to implement authorization ourselves.
In order to get an access-token, first a request has to be made against a POST /login — route with the username/password credentials sent in the body as a JSON-object.
The implementation looks like this:
The coroutine-handler is a simply extension function:
Coroutines are launched on the Vert.x event loop (the dispatcher).
In order to execute a longer running handler we use
Vert.x uses a different thread pool for these kind of tasks. The task is thus executed in another thread. Beware that the event loop isn’t going to be blocked, the coroutine is going to be suspended.
Now we are switching the focus to our API again and show how it’s designed with examples. We first need to set up our server and Keycloak.
Once both servers are up and running, we’re able to write a simple HTTP-Client. We first have to obtain a token from the
/login endpoint with a given "username/password" JSON-Object. Using an asynchronous HTTP-Client (from Vert.x) in Kotlin, it looks like this:
This access token must then be sent in the Authorization HTTP-Header for each subsequent request. Storing a first resource looks like this(simple HTTP PUT-Request):
First, an empty database with the name
database with some metadata is created, second the XML-fragment is stored with the name
resource1. The PUT HTTP-Request is idempotent. Another PUT-Request with the same URL endpoint would just delete the former database and resource and recreate the database/resource.
The HTTP-Response should be 200 and the HTTP-body yields:
We are serializing the generated IDs from our storage system for element-nodes.
GET HTTP-Request to
https://localhost:9443/database/resource1 we are also able to retrieve the stored resource again.
However, this is not really interesting so far. We can update the resource via a
POST-Request. Assuming we retrieved the access token as before, we can simply do a POST-Request and use the information we gathered before about the node-IDs:
The interesting part is the URL, we are using as the endpoint. We simply say, select the node with the ID 3, then insert the given XML-fragment as the first child. This yields the following serialized XML-document:
Every PUT- as well as POST-request implicitly
commits the underlying transaction. Thus, we are now able send the first GET-request for retrieving the contents of the whole resource again for instance through specifying a simple XPath-query, to select the root-node in all revisions
GET https://localhost:9443/database/resource1?query=/xml/all-time::* and get the following XPath-result:
In general we support several additional temporal XPath axis: future::, future-or-self::, past::, past-or-self::, previous::, previous-or-self::, next::, next-or-self::, first::, last::, all-time::
The same can be achieved through specifying a range of revisions to serialize (start- and end-revision parameters) in the GET-request:
or via timestamps:
We for sure are also able to delete the resource or any subtree thereof by an updating XQuery expression (which is not very RESTful) or with a simple
This deletes the node with ID 3 and in our case as it’s an element node the whole subtree. For sure it’s committed as revision 3 and as such all old revisions still can be queried for the whole subtree (or in the first revision it’s only the element with the name “bar” without any subtree).
If we want to get a diff, currently in the form of an XQuery Update Statement (but we could serialize them in any format), simply call the XQuery function
sdb:diff which is defined as:
sdb:diff($coll as xs:string, $res as xs:string, $rev1 as xs:int, $rev2 as xs:int) as xs:string
For instance via a GET-request like this for the database/resource1 we created above, we could make this request:
Note that the query-String has to be URL-encoded, thus it decoded it’s
The output for the diff in our example is this XQuery-Update statement wrapped in an enclosing sequence-element:
database is opened in the first revision. Then the subtree
<xml>foo<bar/></xml> is appended to the node with the stable node-ID 3 as a first child.
This is it for now.
Happy coding :-)