An Event Based Datastore

Whilst working on Briefly I have been researching and developing a new type of Datastore that is a variant of an event based store. Given my lack of a formal computer science background, I have found it difficult to document it in a format that holds any weight in terms of academia and so thought I would detail the idea, its implementation and my experience with it here in the hope that it will aid in taking this technology forward.

Conventional Data Storage for Web Applications

The first thing to understand is that this is not a technology designed to replace the likes of MongoDB or MySQL. It is a system that builds on top of these technologies to provide a different pattern of data access and performance implications. At Briefly, the system is implemented on top of a MongoDB database, but it could equally use any SQL or NoSQL database with varying degrees of ease.

In a conventional REST API, requests would have a scripted set of mutations to provide based on the provided input. For example, take a simple photo sharing API with functionality akin to imgur. A POST request to /photos/ would cause an image object to be created in the database, and its attributes would be set to a predefined set of points. The crucial part is if the user then wants to rename this image, another request would be sent to an endpoint something like this: PUT /photo/123456 with a body something like:

{
    “name”: “Alex’s new photo”
} 

This request would then cause a destructive mutation to the database, whereby the original name is directly overwritten, causing the loss of the previous name.

A request to the photo endpoint would now return the correct name, but without strange implementations we are unable to recover the previous name.

Hypothesise that at this point a decision is taken to allow users to reverse name changes, or to simply view what the image has previously been called. This quite obviously poses an initial problem because we have been destroying them since the start of history, so we cannot recover them from before. Even then, when we launch our new version with this feature we would have to implement custom logic in the database to store the changes. One common solution to this is to store every version of the object in the database, which is clearly not the optimal way to solve the problem ( not least because it lacks context as to what each version represents ).

A Brief Interlude - The PAdic Datastore

My proposed solution is what I am calling a PAdic datastore ( Side note this is taken from but doesn’t share meaning with p-Adic numbers. It is based on a misunderstanding I had whilst at school which led me to creating this system ).

The PAdic datastore is based around the idea of having a naked BaseObject, to which Events are pinned as the objects lifecycle in the application progresses.

Each event can contain MetaData and applying the events in chronological order ( oldest first ) will yield the latest state of the object represented by the BaseObject.

A PAdic datastore relies on the following core principals:

  1. Every base object represented in the datastore has a BaseObject which consists of an ID and a type.

  2. An Event consists of its type, its creation time, which BaseObject’s it affects and it’s metadata.

  3. Each event defines an applyEvent method, which takes the current state of the constructed response and the authentication level it is built with, and returns a delta of properties to merge into the response.

This leaves us with an event class which looks something like as follows:

class Event {

    constructor(createdAt, type, concerns, metaData)

    applyEvent(transientObject, authenticationLevel)

}

The Photo Example - Powered by PAdic

The Photo example would now work something like follows. When a User goes to create an image we take the following steps:

  1. POST /photos which creates and returns a BaseObject of type photos. It might look something like this:
{
    “type”: “Photo”,
    “id”: “123”
}
  1. POST /events with the following body:
{
    “type”: “PhotoCreate”,
    “concerns”: “123”,
    “metaData”: {
        “name”: “My Original Name”,
        “image_url”: ”https://s3.links.here/image.png”
    }
}

Our image is now in the datastore, and assuming we applied the metaData directly to the transient object during construction we would get an image back that was representative of the events that have been applied to it (i.e. creation with a name and url )

Harnessing the power

Let’s now assume that a user wants to change the name of the image. We can define a new type of event called “PhotoModify”. We might send that to look something like this:

{
    “type”: “PhotoModify”,
    “concerns”: “123”,
    “metaData”: {
        “name”: “My New Image Name”
    }
}

Now when we retrieve the image, it would apply first the Creation Event and then the Modify event, which would overwrite the name and set it to the new one. This means that when we request the photo resource it would now have the new name.

But let’s say we wanted to look at the edit log for this? Simply requesting a list of the events gives us all the data we need to do this. Seeing as each event is stored in the datastore, we can discreetly request them and provide that historical view.

Say instead we wanted to look at the object on a given day in history? We simply only apply events that have a creation date less than the date we are looking at. This can then be composed to create the user.

Performance

I do not yet have strongly founded statistics on performance but their are a few crucial optimisations that can be made to reduce computation time and also a few critical points to realise.

  • An object is only computed at request time, this allows lazy evaluation of data, which for certain access patterns represents a significant saving on compute.

  • An object can be cached using a unique key of the id it represents alongside the access level that represented it composed with the following formula:

Let f() be defined as the function that takes three string arguments, a Unique Identifier, an Access Level and the Number of Events used in the computation such that:

f(uuid, access_level, event_number) = uuid + access_level + event_number

where + is the operator of string concatenation.

In the case that events cannot be destroyed or deleted, only hidden, the event number cannot decrement and so the event number is a strongly unique indicator of a particular event/object composition set when coupled with the other factors.

Therefore a cache method which stores the final computation result tied to the above key cannot cause a Security breach or data leak and allows for caching that would result in a sole computation for each data object.

There is an inherent performance difficulty at very large scale. The computation process runs complexity of O(n) so as the event set for an object grows the speed would diminish. In the event that a very large amount of data needed to be stored and accessed in realtime with a very large number of event tied to each object then a PAdic store is not likely to be a good solution until further algorithmic complexity improvements and ideas are brought to it.

Intended Use

At Briefly, we use this as our API. We engineer our client side app around sending home events, and this works just great for us. However an arguably better system for some use cases would be a conventional restful API where only the data was served from a PAdic Store.

I have a vision that this could be made into a SAAS service where users could log in and create events, provide implementation code for their lifecycle events on a web dashboard and then use the SAAS as their datastore. Due to the inherently shardable nature of the concerns field, scale is not a problem and expansion costs are very low.

The SAAS could contain some really cool features like tracking inferred user analytics by looking at event patterns and making the creation of events really easy by specifying the fields they require and if they are required or optional.