2009-08-25

Zero-Latency Internet GUIs Using "Multiple Worlds"

I have discovered an interesting way to write zero-latency user interfaces for internet services.

It's similar in spirit to Alice ML's first-class futures, promises.

The basic idea is that every user operation that hasn't been acked yet by the server, results in a new "possible world" in some part of the user interface, that may have to be rolled back (if the server fails, for example).

The model (if you're a MVC person) is represented as a tree of operands, which are basically futures, containers for variables that reside on the server. GUI widgets subscribe to operands as listeners, and GUI operations are represented as first-class objects that change an operand.

/** A usually high-latency action that changes the states of one or
more operands. */
interface Operation {
public String getDescription();
}

interface OperandListener<OP extends Operand> {
public void onOperandChange(OP operand);
public void onOperandFailure(OP operand);
}

/** An observable variable with a last known state (usually retrieved
from the server), and optionally a pending operation and a
tentative state (a state that the pending operation would like the
operand to have, but that hasn't been acked by the server yet).

Clients of the operand should usually just call getState(), which
returns the operand's tentative state if there is one, or the last
known state otherwise. This guarantees that the user sees an
up-to-date image of the operation's progress. (There is a danger
however, in that the tentative state of an operand may be invalid
from the client's perspective.)

There can be only one pending operation on an operand at one time,
and trying to start a new operation on an operand with a pending
operation will result in an error. */
abstract class Operand<T> {
protected T lastKnownState;
protected T tentativeState;
protected Throwable currentFailure;
protected Operation pendingOperation;
protected Set<OperandListener> listeners;
}

A GUI operation simply puts an operand in a tentative state, which locks the operand, so that it cannot be changed (by another operation) until the server has acked the change.

This means that a user can edit multiple objects on the screen, and each of these changes results in a zero-latency screen update to the new tentative state, and a background thread that tries to update the state on the server.

(I haven't implemented this yet, but it would also be possible to merge commutative operations.)

7 comments:

Anonymous said...

Maybe you should review what continuations are. You can get your full rollback without wasting time infinitely searching into the future.

Vladimir Sedach said...

This is just a limited form of timestamp/multi-version concurrency control, isn't it?

Manuel J. Simoni said...

Yeah, it does have similarities. I think that the use for GUIs is novel (or unusual, at least), though.

Manuel J. Simoni said...

Also, it just appears to be limited, when in fact it is a very programmable system.

In an outliner I am writing, I have the following operations:

GetEntryOperation (which immediately yields a future for an entry (outline item), and loads it in the background),

PostNewEntryOperation (which posts a new entry, and adds it to the parent's child pointers, i.e. it changes two entries),

EditEntryOperation (which updates the contents of an entry),

RemoveEntryOperation, and

DragAndDropEntryOperation (which changes the child lists of the drag source and drop target entries).

So the simplicity of the system makes it possible to have very application-specific operations.

Vladimir Sedach said...

What I meant by "limited" was that it's applied to an async one client one server system as opposed to multiple readers and writers.

It is new as a pattern to be applied to async client/server GUIs. Other web apps kind of do it for some operations (I know GMail does), but it's not systematic and I've never heard it described as a pattern.

schwaj said...

See Chapter 4 ("Worlds: Controlling the Scope of Side Effects") of Alex Warth's Experimenting with Programming Languages paper. I believe that it addresses your use-case, and does so at the language level, so you don't have to explicitly/tediously reify every possible undoable operation.

Manuel J. Simoni said...

Thanks, I'll read that (again).