Joose blog

Blog about Joose – advanced class system for JavaScript

Syncler – distributed applications for human beings

with 9 comments

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.

moveTo : function (x, y) {
this.setX(x)
this.setY(y)
}add: function (element) {
this.elementsByUUID.set(element.uuid, element)return element
},remove : function (element) {
this.elementsByUUID.remove(element.uuid)
}

Written by Nickolay Platonov

April 8th, 2011 at 2:13 pm

  • http://profiles.google.com/jessesanford Jesse Sanford

    This is very exciting. I would like to know about some more real-world use. What type of apps have you produced other than the simple shareboard. Is there any reason this wouldn’t also benefit the ui latency when used for single client server communication? I am talking about simple ajax applications that don’t involve “shared” concurrent state between the clients?

    • http://profiles.google.com/nickolay8 Nickolay Platonov

      Thanks. ShareBoard is currently a single system. I’m planning to write some simple multiplayer game soon.

      As about “single client server communication” – yes, also thinking about such approach. Its very tempting to instantly have a transparent (and real-time with low latency) persistence for usual applications. But some questions arise with this approach – first of all security and some others.

  • http://cscott.net C. Scott Ananian

    I discussed this a bit at http://cananian.livejournal.com/64330.html.  The syncler work is very interesting; it’s a shame that the lack of ‘yield’ on certain platforms is forcing the use of a rather ugly CPS form.  Havoc further discusses the use of ‘yield’ here: http://blog.ometer.com/2010/11/28/a-sequential-actor-like-api-for-server-side-javascript/

    • http://profiles.google.com/nickolay8 Nickolay Platonov

      Thanks.

      About CPS – it is ugly only compared with some native language construct. Comparing with “raw” callbacks (and other CPS abstractions libraries, like Step, etc) its very readable and has intuitive syntax.

  • C. Scott Ananian

    I’d like to learn more about how conflicts and rollback are handled. Bayou let applications choose between accessing the “committed state” or the “tentative state”. Do you have a mechanism for doing this? When you state that the app is MVC factored, do you mean that the view must be able to handle arbitrary rollback in the model at anytime? You mention that updates capture preconditions–is this fine-grained, or us this just the client’s version vector at the time of the update?

    • http://profiles.google.com/nickolay8 Nickolay Platonov

      > I’d like to learn more about how conflicts and rollback are handled.

      Right now its always “first win”. I’m planning to add the “last win” option to all standard operation (which covers manipulations with standard data types – object/array/date/etc). Any more complex processing (like merging conflicts) should be provided by user (via creation of own operation).

      > Bayou let applications choose between accessing the “committed state” or
      the “tentative state”. Do you have a mechanism for doing this?

      Not yet, but this feature is in roadmap with high priority. Currently its always “tentative state”.

      > When you state that the app is MVC factored, do you mean that the view
      must be able to handle arbitrary rollback in the model at anytime?

      Yes. Rollback however is just the “reverse” update, so I believe there will be a possibility to generalize “forward/reverse” updates.

      > You mention that updates capture preconditions–is this fine-grained, or
      us this just the client’s version vector at the time of the update?

      Its the fine-grained mechanism till certain degree (ie when updating some key in the object, it only captures the value of that key, not whole object).

      • http://cscott.net C. Scott Ananian

        How is the programmer-supplied conflict-merging code written?  Maybe there’s an example in ShareBoard you could quote?

        And what about preconditions that (say) read several fields of several different objects before deciding to write a field.  Is that properly captured, or are you just recording the prior contents of the field which is eventually mutated?

        • http://profiles.google.com/nickolay8 Nickolay Platonov

          > How is the programmer-supplied conflict-merging code written?  Maybe there’s an example in ShareBoard you could quote?

          No “custom” conflict resolution logic in Shareboard. It uses “first-win” policy.

          Take a look on the Mutation (update) Role: https://github.com/SamuraiJack/Syncler/blob/master/lib/Syncler/Mutation.js

          Any class can implement this role, for example, mutation for the object key: https://github.com/SamuraiJack/Syncler/blob/master/lib/Syncler/Mutation/Object/Set.js. The “merge” method of the class will be called in case preconditions do not match the captured ones. “Merge” is supposed to return the new mutation, which will be applied to replica instead of conflicting one. So all the conflict resolution logic should happen in it. As you can see, right now all “merge” methods return “void” update (first-win)

          > And what about preconditions that (say) read several fields of several
          different objects before deciding to write a field.  Is that properly
          captured, or are you just recording the prior contents of the field
          which is eventually mutated?

          Yes, preconditions can be captured from several objects just fine – just need to add additional attributes to the mutation class.

  • Asdf

    test