A CAL webapp with persistent data using GWT, STM and BDB

aka, attack of the TLAs.

This webapp’s architecture is depicted below:

Webapp Architecture

Any data structure can be built on top of TVars — and each TVar is a mutable reference, these are not functional data structures.

In this application a simple hashmap is used. Skiplists and relaxed balance btrees are other data structures which might allow reasonable concurrency too, while also providing features like in-order traversal.

This illustrates the relationship between the CAL objects in the CAL ExecutionContext and key-value pairs in the BDB:

cal-gwt-stm-persistence.png

The root of the persistent data structure is a TVar with a ‘well-known’ id — 1 in the example, which is created by a constant applicative form function. This TVar will retrieve its value from the BDB when it is created, or if no value exists for its id, it will be initialised with a default value, which in the case of a hashmap is an array of TVars, each containing an empty list of key-value pairs. A value stored in a TVar is persisted to the BDB by serialising it using CAL’s default output function and Xstream, which can serialize and deserialize instances which are not serializable and do not have accessible constructors.

TVars themselves have transient values, so only the id is persisted — the value is lazily loaded when required, using the id. So even though a TVar may persist a complicated tree of CAL algebraic values, this stops at the first TVar. (The root TVar is never persisted itself — only its value is stored).

You can get a snapshot here — just unpack it and run ant run, then point your browser at http://localhost:8080/caltest.html. Or browse the source.

The ant build script includes a target run-tests which runs some Selenium tests. Stop the server before running that target.

Note that the source code includes various bits of half-baked rubbish, in addition to that described above!

2 Comments

  1. Raoul Duke
    Posted April 2, 2008 at 4:58 am | Permalink

    since i just got Okasaki’s book for my birthday i have to ask what you think about taking a functional-data-structure approach? how would that play with STM etc.? thanks for any thoughts.

  2. Tom Davies
    Posted April 2, 2008 at 6:20 am | Permalink

    Hi Raoul — I believe that functional data structures don’t suit STM, because while you can update, e.g. a tree without replacing many nodes, you are always going to replace the root node, so any concurrent transactions which have read or written the TVar which holds it will retry — which means any transaction which is concurrent with an update, as everyone who accesses the tree will read the root node.

    There may be some non-STM approach which would work when concurrent updates are infrequent (e.g. all updates can be performed by one thread). Because purely functional data structures are ‘persistent’ (as defined by Okasaki) you could have one mutable reference which is updated by the writing thread each time it performs an update, and is read by the other threads periodically — they will always have a consistent view of your data structures.

    But that limitation to one writer makes this sound fundamentally non-scalable and unsound — like Prevayler, for instance.

One Trackback

  1. [...] There are two ways of integrating CAL and Java. The first is to dynamically load and compile a workspace at run time, and then reflectively call functions in the workspace’s modules. I’ve used this approach in the past, for example for CAL/GWT integration. [...]

Post a Comment

Your email is never shared. Required fields are marked *

*
*