1. Intro

Distributed systems are hard by definition. Thats why its important to not mix the complexity of distributivity with the complexity of the data domain and keep them separated.

In this post we’ll present Syncler – a distributed, optimistic replication backend for KiokuJS. Syncler will keep several replicas of arbitrary data synchronized, in real-time.

Syncler is unobtrusive and does not require from developer to understand all the mechanics of replication.  Replica is simply a set of Joose classes and/or native JavaScript data structures. Application uses accessors to mutate the attributes of classes, and Syncler takes care about all replication details. To be informed about updates in own replica, application can subscribe to various events using the observable pattern.

Syncler has been designed after Bayou (described in this paper). Using the classification of optimistic replication systems from this paper, Syncler can be characterized as the system with:

• operations transfers and semantic conflicts resolution
• many masters (though a single master is being used for updates stabilization)
• real-time updates propagation schedule
• a star topology for updates propagation
• eventual consistency (with very low replicas divergence period due to real-time updates)

To understand the advantages and drawbacks of these design choices please refer to the mentioned papers and other papers on the same topic. Most of the design choices were inherited from Bayou, however Bayou is more focused on off-line usage and Syncler – on real-time synchronization.

In addition to that, Syncler is cross-platform (runs equally well in browsers and NodeJS) and non-blocking.

In fact, Syncler is not a backend per se, but a special role, which can turn any KiokuJS backend into distributed system. Despite that at the moment there’s only one backend (for CouchDB), writing new ones is trivial (backend for Riak looks very promising).

As the transport, Syncler uses Socket.IO. Due to relative instability of most of the Socket.IO transports, at this moment, Syncler work correctly only with websockets.

2. Optimistic replication

Optimistic replication is a special type of replication, in which all masters apply own updates (and “see” the results) immediately. It can be said that every master is optimistic about that his update won’t cause any conflict.

Naturally, because the updates are applied without coordination among all replicas, the state of replicas may slightly diverge in the course of time, but the final state of all replicas is guaranteed to be the same (so called “eventual” or “weak” consistency).

Optimistic replication creates an illusion of zero network latency for own updates and greatly improves the responsiveness of the UI.

3. Applications

The application areas for Syncler is quite wide – it can be used as the basement of any kind of collaborative environment, where is a need to synchronize the operations,  originating from multiple users. Syncler is currently not bound to some specific data domain area.

3.1 Cooperative editing systems.

Probably the most obvious and well-known application area is so called “group-ware”. Typically its the graphical editor which allows several users to simultaneously edit some graphical scene, consisting from various graphical primitives. As the showcase of Syncler, we’ve developed such drawing application “ShareBoard”  (see section 6).

But naturally, the application doesn’t have to focus on graphic edition and can be used in any data domain.

3.2 Online multi-player games

Another very perspective area is the multi-player games, as games can be thought as some special kind of collaboration. This area is gaining interest along with modern browsers gaining visualization capabilities.

Syncler can greatly reduce the “entry barrier” for the creation of a new game as it handles a lower-level question of game scene synchronization, allowing the developers to focus on the gameplay process itself.

4. Architecture and realization

In this section we’ll shortly cover the architecture of the application, based on Syncler along with typical implementation patterns. Everything is still preliminary and subject for refactoring. We’ll use the code fragments from the ShareBoard system.

4.1 Replica

Replica is simply a set of Joose classes, having a `Syncler.Object` role. Currently replica also need to have a special “topic” class, with `Syncler.Topic` role (this requirement will be removed).

For example the board scene is modeled with the following class:

Class('ShareBoard.Model.Board', {

    does            : Syncler.Topic.UUID,

    has : {
        createdBy       : null,
        createdAt       : Joose.I.Now,

        elementsByUUID  : Syncler.I.Object,

        ...
    },

    methods : {

        add: function (element) {
            this.elementsByUUID.set(element.uuid, element)

            return element
        },

        remove : function (element) {
            this.elementsByUUID.remove(element.uuid)
        },

        each : function (func, scope) {
            return this.elementsByUUID.each(func, scope || this)
        },

        ...
    }
})

As you can see, board is generally a collection of board elements. And a base class for board element looks like:

Class('ShareBoard.Model.Board.Element', {

    does         : [
        'Syncler.Object',
        'KiokuJS.Feature.Class.OwnUUID'
    ],

    has : {
        board           : { required : true },

        x               : { required : true },
        y               : { required : true },

        color           : 'blue',

        ....
    },

    methods : {

        getBubbleTarget : function () {
            return this.board
        },

        remove : function () {
            this.board.remove(this)
        },

        moveTo : function (x, y) {
            this.setX(x)
            this.setY(y)
        }
    }
})

There are several subclasses of `Board.Element`, which add additional presentation logic.

4.2 Updates

To update the replica, application just calls the accessors methods. For example to move the board element (graphical primitive) to another position one can call the `moveTo` method, which looks as simple as:

    moveTo : function (x, y) {
        this.setX(x)
        this.setY(y)
    }

The wrappers for native JS data structures (which are required in the absence of proxies) provides obvious accessors for typical opeartions, for example to add/remove the board element to/from board, one can call `add/remove` method,
which updates the key in the underlaying JS Object.

    add: function (element) {
        this.elementsByUUID.set(element.uuid, element)

        return element
    },

    remove : function (element) {
        this.elementsByUUID.remove(element.uuid)
    }

The updates gets applied immediately and will propagate to other replicas in the background. As you can see, all the replication logic is packed into the meta-layer, the application is free from it.

Syncler assumes that any update can be rolled back (thats one of the design decisions of Bayou), thus all updates captures the “precondition” information which is being used for consistency checks.

4.3 Observable

To know about updates in replica, application should subscribe to various mutation events, which will be emitted by the meta-class. For example, to listen to mutation of any attribute in the underlying `model` instance, the base widget class can do the following:

Class('ShareBoard.View.Board.Element', {

    has : {
        boardWidget     : { is : 'rw', required : true },
        model           : { is : 'rw', required : true },

        ...
    },

    methods : {

        initialize : function () {
            this.model.on(
                '/mutation/apply/Syncler.Mutation.Class.Attribute',
                this.onAttributeMutate,
                this
            )
        },

        onAttributeMutate : function (event, mutation) {
            var attributeName       = mutation.attributeName

            if (attributeName == 'status')
                this.updateStyle()
            else
                this.updatePosition()
        },
        ...
    }
})

Another example – the board widget listen to `onNewInstanceOf` event of the replica itself and add widgets as new model elements appears:

        replica.onNewInstanceOf(
            'ShareBoard.Model.Board.Element',
            this.onNewBoardElement,
            this
        )

        onNewBoardElement : function (event, element, e) {
            var widgetClass = Joose.S.strToClass(element.widgetClass)

            var widget = new widgetClass({
                boardWidget : this,
                model       : element
            })

            this.addWidget(widget)

            widget.render()
        }

One more example – the board widget listen to the `remove` event of the underlying set of elements – and removes the widgets:

board.elementsByUUID.on(
    '/mutation/commit/Syncler.Mutation.Object.Remove',
    this.onBoardElementRemove,
    this
)

4.4 MVC

Its worth to note, that Syncler gently but insistently structures the application in MVC pattern.

Any Syncler application naturally has a Model (which is a replica being synchronized). Then, when implementing the UI (View), its not possible to put any Model logic in View, it must only listen the events from Model. The reason is simple – otherwise, UI will ignore the updates from other collaborators.

So, the distributed nature of the application, when there is an external source of model mutations, already implies the separation between Model and View. The only needed step for pure MVC is making the View as much stateless as possible, and moving the processing logic to Controllers. This step is not as obvious as the 1st one though and requires certain qualification level from the programmer.

5. Status and roadmap

Syncler is still on very early development stage. In fact, even the name of the framework isn’t final yet. However, it has an extensive test suite (including a stress load test) so it can already host simple applications ala ShareBoard.

The roadmap items list is quite long, among the other things are:

• Write some simple multi-player game to better research the capabilities of current approach.
• Research the possibilities of using state-transfer algorithms and multi-master storage schemes.
• Implementing a backend for KiokuJS, based on some graph database. This should be a very welcome addition, as graph databases usually have query languages and hopefully some of them even will provide certain form of referential integrity.
• Adopting the other Socket.IO transports.

6. The showcase system – ShareBoard

ShareBoard is the proof of concept showcase of Syncler. Its a simple collaborative graphical editor, which allows several users to edit the same “online white-board” scene.

Try it yourself (in web-socket enabled browser, like Chrome): http://shareboard.joose.it

Tip: After creation of the board – open several browser windows with it side-by-side, or drop the link to you friend.

7. Conclusion

We’ve presented Syncler – a distributed system, implemented as the backend for KiokuJS.

The creation of the showcase system “ShareBoard” has proved, that the demonstrated approach is very simple (so far as this word can be applied to distributed computing) and clean from the architectural point of view.

Syncler is still on very early development stage so further research directions were defined.

What

KiokuJS is a persistence layer for Joose. Its a freestyle port of KiokuDB which does the same thing in the Moose world.

KiokuJS provides transparent storing/retrieving for instances of Joose classes. Native data structures (Object/Array/etc) can be stored as well. “Transparent” means that class can be stored without any modifications to its declaration (see also But).

KiokuJS is cross-platform – it runs equally well in browsers and NodeJS. KiokuJS is non-blocking – all interactions with DB are asynchronous.

Why

Remember the last Web2.0 project you worked on. Quite probably it was looking as:

Note, that you need to define the serialization procedure 4(!) times. Even if you use some kind of client-side helpers of modern frameworks, you still need to (manually) map your client-side JavaScript data structures to the storage layer.

Meanwhile, nowadays its obvious, that JavaScript has evolved from client-side animation libraries into full-stack platform. There are no reasons why your applications can’t be fully written in JavaScript and benefit from the homogeneous environment both on client and server.

So the goals of KiokuJS are:

• eliminate all the serialization boilerplate from the application
• use a single model definition both on client and server
• encapsulate all the storage-layer details in high-level interface

Example

// class declaration

Class('Person', {

    has : {
        self    : null,

        name    : null,

        spouse  : null
    },

    methods : {

        initialize : function () {
            this.self = this // circular ref
        }
    }
})

// arbitrary data structure

var Homer = new Person({
    name    : "Homer"
})

var Marge = new Person({
    name    : "Marge"
})

Homer.spouse = Marge
Marge.spouse = Homer

// handler setup

var handle = new KiokuJS.Backend.CouchDB({
    dbURL   : 'http://local:5984/someDB'
})

// storing

var scope = handle.newScope()

scope.store(Homer, Marge).andThen(function (homerID, margeID) {
    ...
})

// retrieving

var scope = handle.newScope()

scope.lookUp(homerID, margeID).andThen(function (Homer2, Marge2) {

    // Homer2.self   === Homer2
    // Homer2.spouse  === Marge2

    // Marge2.self   === Marge2
    // Marge2.spouse  === Homer2
})

How

From the KiokuJS viewpoint, the data structures represents a cyclic, directed graph:Data graph is then serialized into JSON structures like:

{
    "className": "Person",
    "ID": "2D9E24EE-89BA-A361-B0E6-2D8A6C1226F6",
    "isRoot": true,
    "data": {
        "self": {
            "$ref": "2D9E24EE-89BA-A361-B0E6-2D8A6C1226F6"
        },
        "name": "Homer",
        "spouse": {
            "$ref": "0CFB5A77-8B58-BC7F-9B7D-DBDD78A29AC2"
        }
    },
    "$entry": true
}

{
    "className": "Person",
    "ID": "0CFB5A77-8B58-BC7F-9B7D-DBDD78A29AC2",
    "isRoot": true,
    "data": {
        "self": {
            "$ref": "0CFB5A77-8B58-BC7F-9B7D-DBDD78A29AC2"
        },
        "name": "Marge",
        "spouse": {
            "$ref": "2D9E24EE-89BA-A361-B0E6-2D8A6C1226F6"
        }
    },
    "$entry": true
}

There are a number of options, defining the serialization details (implemented as attribute traits). When required, its also possible to provide a custom serialization format for specific class.

Its worth to note, that all asynchronous interfaces in Kioku are implemented using the continuation-passing style extension for Joose, which provides a precise control over the asynchronous methods. The previous storing example can be elaborated like this:

// storing

UI.maskScreen("Please wait")

scope.store(Homer, Marge).then(function (homerID, margeID) {

    alert('Objects stored successfully')

    this.CONTINUE()

}).CATCH(function (e) {

    alert('There were an exception [' + e + '] during storing operation')

    this.CONTINUE()

}).FINALLY(function () {

    UI.unMaskScreen()

}).now()

But

Persistence is mostly transparent, but there are some limitations. Generally any closures-related magic won’t be recognized, simply because there are no according introspection capabilities in the language. For example, if you have a function, tied to a scope with some closures, as the value of the attribute:

var closure = { foo : 'bar' }

homer.magic = function () { return closure.foo }

then KiokuJS will store the function declaration only, not the scope it was defined in. So after retrieving the instance from the backend and running “homer.magic()” there will be an exception like [“closure” is not defined].

Another limitation is related to searching. Searching is constrained to backends capabilities only.

Backends

Kioku is backend-agnostic, but currently mostly target NoSQL (key/value) backends because of their simplicity, native JSON support and HTTP APIs, which allows to directly access the DB from the browsers.  With some additional efforts can be implemented a relational backend, either static (when classes definitions will be generated from the relational schema) or dynamic (when the relational schema will be adjusted to the classes definition).

For the development and testing there is a “Hash” backend. For the production – CouchDB backend.

Test suite of Kioku is organized that way, that makes it possible to run for each backend.

There is also a special backend (actually a role for backend) – KiokuJS.Backend.Batch, intended for usage in browsers. It allows to combine the individual requests for separate documents into batches, saving a lot of HTTP requests.

Writing new backends is easy – they only need to define 4 methods.

Status

KiokuJS is at 0.01 version. This means its “stable enough”, has the extensive test suite, but is mostly intended for early adopters, which are welcome to Joose IRC channel with any questions. Currently there is no documentation.

To install Kioku, run

> npm install kiokujs

You may also want to install CouchDB backend with:

> npm install kiokujs-backend-couchdb

After that this mini demo app should just work from NodeJS, supposing you have correct value for NODE_PATH environment variable (see items 3.x in Joose installation).

Roadmap

• Add more backends – Riak and MongoDB are 1st candidacies.
• Try to implement backends for graph databases (very promising).
• Syncler (draft name) – real-time backend, which use the optimistic replication to synchronize the state of replicas between clients.