Archive for November, 2008

Correspondence storage strategy provider model

Sunday, November 30th, 2008

The Correspondence library synchronizes object models between memory and storage. Eventually, it will synchronize object models between machines. But for right now, let's talk about storage.

The storage mechanism for Correspondence is not relational. Correspondence is not an ORM. But it is sometimes useful to implement Correspondence storage on top of a relational container. For one thing, relational databases already exist and are easy to use. For another, Correspondence can interface with relational data. It would be beneficial to have one transactional boundary around both the Correspondence data and the relational data.

The storage mechanism used to persist Correspondence objects is isolated from the core library itself. This allows you to select the most appropriate storage mechanism for your application. A provider for storage implements the StorageStrategy interface. You select a storage strategy when you configure your Community.

Mementos and IDs
A StorageStrategy does not deal directly with CorrespondenceObjects. It is isolated from your code by dealing with Mementos. A Memento stores the immutable state of a Correspondence object. This includes the type name and version number, the predecessors, and the fields. Successors are not immutable, so they are not part of the Memento.

A Memento's size is strictly limited to 1024 bytes. If you create a CorrespondenceObject whose fields contain more than 1K of data, you have to break it up. This hard limit is there to protect the memory, storage, and network components. It prevents buffer overrun attacks, helps ensure scalability, and makes the system more performant.

A Memento calculates a hash code, which is used as a first check to see if two Correspondence objects are equal. Remember that a Correspondence object's identity relies upon its predecessors and fields. If these are the same, then it is the same object. A Memento contains only these identifying attributes, so its hash code is used for identity checks.

But the hash code itself is not sufficient. We know that a hash is not unique. So in addition, the StorageStrategy deals with ObjectIDs. An ObjectID is nothing more than a wrapper for a 64 bit integer. These integers are unique only within a given database. Since the Memento uses ObjectIDs, a Memento is also specific to a database. Mementos and ObjectIDs do not make sense in application code. In fact, unless you create your own StorageStrategy, you will only encounter the Memento type in the constructors of your objects. These constructors are used to load a Correspondence object from storage.

The StorageStrategy interface
The StorageStrategy interface has very few methods. The most interesting ones are described here:

public interface StorageStrategy {

	Memento load(ObjectID id) throws CorrespondenceException;
	ObjectID save(Memento memento) throws CorrespondenceException;
	ObjectID findExistingObject(Memento memento) throws CorrespondenceException;
	Iterable<Pair<ObjectID, Memento>> executeQuery(QueryDefinition queryDefinition, ObjectID id) throws CorrespondenceException;

}

The load and save methods are the workhorses of the strategy. Given an ObjectID, the strategy needs to load a Memento. Or given a Memento, it needs to save it and return its ObjectID. If a matching Memento is already in storage, the ObjectID of that Memento will be returned instead.

Like save, findExistingObject will return the ObjectID of a matching Memento. But unlike save, it will not store the Memento if it doesn't already exist. This method is used for getObject, whereas save is used for addObject.

The last method is the most interesting. A Query is a collection of joins. Each join is either to a successor or a predecessor. When a Query is observed, it calls executeQuery and sends its QueryDefinition to the storage strategy. The storage strategy returns the collection of objects that satisfy that query. The storage strategy is free to use whatever means necessary to execute the query, including dynamically generating SQL.

Not relational
It's pretty easy to see from this interface that Correspondence does not offer all of the features of a relational database. The only relationships allowed between objects are predecessor/successor relationships. And predecessors can't change. There is (currently) no arbitrary lookup by field, like you have with a relational query by column. Correspondence works by its own limited set of rules.

But that limitation is also a strength. Because relational databases have to deliver on so many difficult promises, they cannot synchronize as easily as a Correspondence model. The set of operations that Correspondence allows was specifically selected to make it easy to share data from memory, to storage, across the network, and with other users. It's a different programming model, but one that you will eventually come to find as natural as relational or OO.

Existing and future storage strategies
I currently have Correspondence libraries written in C# and Java. In the Java version, I have implemented the Postgres storage strategy. In .NET, I have implemented SQL Server, SQL CE, and Access. I also have an in-memory version in both platforms strictly for unit testing. In the future, I plan to support MySQL, and to port storage strategies between .NET and Java. In addition, I'll create stand-alone strategies based on flat files or memory-mapped files.

But for now, I'm releasing the Java version of Correspondence with the Postgres storage strategy. Check back later this week for a download and instructions.

Cancel a Javascript drop-down on click

Tuesday, November 25th, 2008

I'm working on a web application with a drop-down color picker. Click a button to show a box, and click a color to select it. If you click outside the box, it cancels.

Showing and hiding a div is easy. The div's position is "absolute" so that it doesn't cause any layout. I could toggle style.display between "none" and "block", but in this case I'm just creating and destroying the DOM element. It's that "click outside the box" feature that gets interesting.

Body onclick
A quick search reveals that the standard method for dismissing a drop-down when clicking outside of the box is to handle body.onclick. If you click anywhere in the body, this event gets fired. So handle it, see if you have a drop-down open, and close it.

The trick is that the event gets fired even if a child element has already handled the click. This is actually a good thing, because that other child element doesn't know to dismiss your drop-down. Letting body.onclick do its thing means that the drop-down will be closed whether the user clicks a link, a button, an input box, or whitespace.

Isolate the drop-downs
This page may have several controls on it, each with different drop-down behavior. So I chose a pattern that would allow a drop-down to install its behavior in isolation, but still play nice with its neighbors. Instead of having one page-wide function that manages all drop-downs, each one installs its own body.onclick.

When the page is initialized, I set up the first body.onclick. This is just a simple no-op placeholder.

function initialize() {
	document.body.onclick = function() {};
}

YAHOO.util.Event.onDOMReady(initialize);

Then, when a drop-down appears, it calls any body.onclick that may have been previously installed, then installs its own.

	var cancelPickColor = function() {
		if (colorPicker != null) {
			groupTagListDiv.removeChild(colorPicker);
			colorPicker = null;
		}
	};

	this.beginPickColor = function() {
		document.body.onclick();

		// Create a color picker div.
		colorPicker = document.createElement('div');
		colorPicker.className = 'colorPicker';
		groupTagListDiv.appendChild(colorPicker);

		// ...

		document.body.onclick = cancelPickColor;
	};

Following this pattern, I don't need to change existing drop-downs when I add another.

The picker does not appear
This is where the trouble starts. When I tested this code, I found that the color picker did not show up. Placing a breakpoint in Firebug, I saw that it in fact was appearing, but then immediately disappearing. Someone was calling cancelPickColor without my permission!

As I said, body.onclick is called even if a child element has handled the click message. This includes the button that the user just clicked to show the drop-down. After I install my own function inside of onclick, body.onclick fires, calls my function, and hides the drop-down.

The clever bit
I can't prevent body.onclick from firing. I need to let it happen and install my function afterward. So after a little thought, I changed the last line of beginPickColor to this:

		document.body.onclick = function() { document.body.onclick = cancelPickColor };

And it works! The new body.onclick function fires, installs the cancelPickColor function, and the color picker remains visible. Sometimes hacking feels good.

The Correspondence Community

Thursday, November 20th, 2008

Correspondence is about agreement. Every person, every application, every machine involved in the correspondence network comes to agree upon the history of the objects that they share. This set of people, applications, and machines is collectively known as the Community.

The Community object
In code, the Community is represented by a Community proxy object. This proxy is the center of all Correspondence operations. We've already seen the addObject method, which puts a Correspondence object into the system. Here's a complete list of methods:

  • addObject(T prototype) : T {where T extends CorrespondenceObject}
  • getObject(T prototype) : T {where T extends CorrespondenceObject}
  • setModules(List<Module> modules)
  • addType(Class correspondenceObjectClass) : Community
  • addFieldSerializer(Class fieldType, FieldSerializer fieldSerializer) : Community

The addObject method is by far the most used. It shares an object with the rest of the community. It places it in the database, attaches it to related objects (via queries), and sends it out over the network.

The addObject method takes a prototype. An object's predecessors and fields define its identity. So if an object matching the prototype is already in the Community, that existing object is returned. If no matching object is in the Community, the new object is added and returned.

The getObject method also takes a prototype and returns an object. The difference is that getObject will return null if the object is not currently in the Community. AddObject is used to express intent, whereas getObject is used just to look something up.

Initializing the Community
The other three fields are used to initialize the Community. SetModules assigns a list of Module objects. A Module is an interface with only one method: registerTypes. RegisterTypes takes the Community object and calls the other two methods: addType and addFieldSerializer. This pattern allows collections of Correspondence object types to be grouped together as reusable components.

The addType method registers a Correspondence object type with the Community. In order for addObject, getObject, and Query to work properly, a type must be registered with the Community. AddType is typically called from within a Module. This method returns the Community itself, so that it can be chained with other calls to addType.

The addFieldSerializer method is used less often. It registers a strategy object that reads and writes fields to binary streams. The common data types (int, float, string, date, UUID, etc.) are registered by default. You can define a custom data type, implement the FieldSerializer interface, and register it within a Module. Most of the time, however, the predefined field types are sufficient.

The getCommunity method
Every Correspondence object has direct access to its Community. Call the getCommunity method within a Correspondence object any time you want to perform an action. The typical pattern (as we've seen with mutable properties) is to call getCommunity().addObject( new ChildObject(this, more parameters)).

Adding an object to the Community causes it to be returned from relevant Queries. If that Query is used to get a list of children, then the object appears in that collection. If it is used to get the value of a mutable property, that new value appears. If it is used to cause the exists method to return false, the appropriate object is deleted. All of these changes take place automatically. Queries are dependent behavior; adding an object to the Community is independent behavior.

Coming soon
I realize that this is a lot of talk about code without being able to compile any of it. I'm getting the Java version of Correspondence ready to share with you. Within a week or two, you will be able to download a JAR file and sample code. The C# version is about a month behind. In the mean time, there is one last concept I'd like to present, so the next post will talk about the StorageStrategy interface.

Coding mutable properties

Wednesday, November 12th, 2008

image

Fields in a Correspondence object are immutable. To represent a mutable property, you create a new object for each change. The object not only records the new value of the property, it also records the prior objects that it replaces. These become predecessors of the new object, and form a tree of version history. Only the leaves of the tree have not been replaced, and therefore contribute to the current value of the property.

This pattern requires five steps to code. You define:

  • A class to represent the property.
  • A predecessor set to represent prior versions.
  • An exists method to hide prior versions.
  • A query to get the current version (or versions, in case of a conflict).
  • Get and set methods.

Let's walk through these five steps in the bug tracker example.

The property class
We want to add a mutable property to the Project class. This property will be the project name. We will therefore create a new class called ProjectName.

Every time the project name changes, an instance of ProjectName is created. One predecessor is, of course, the Project. In addition, ProjectName stores the name as a field.

@Correspondence
public class ProjectName extends CorrespondenceObject {

	private PredecessorObj<Project> project;

	private @Field String name;

	public ProjectName(Project project, String name) {
		this.project = new PredecessorObj<Project>(this, "project_name", project);

		this.name = name;
	}

	public ProjectName(Memento memento) throws CorrespondenceException {
		this.project = new PredecessorObj<Project>(this, "project_name", memento);
	}

	public String getName() {
		return name;
	}

}

Every time a ProjectName is created, we want to record the current knowledge about the project name. This helps us piece together the history and later determine which names were replaced by another. We add a predecessor set to record all prior ProjectNames. By convention, these predecessors use the role name "next".

@Correspondence
public class ProjectName extends CorrespondenceObject {

	private PredecessorObj<Project> project;
	private PredecessorSet<ProjectName> prior;

	private @Field String name;

	public ProjectName(Project project, ObjectList<ProjectName> prior, String name) {
		this.project = new PredecessorObj<Project>(this, "project_name", project);
		this.prior = new PredecessorSet<ProjectName>(this, "next", prior);

		this.name = name;
	}

	public ProjectName(Memento memento) throws CorrespondenceException {
		this.project = new PredecessorObj<Project>(this, "project_name", memento);
		this.prior = new PredecessorSet<ProjectName>(this, "next", memento);
	}

	public String getName() {
		return name;
	}

}

The exists method
A ProjectName replaces its predecessors. Those predecessors cease to exist. We add an exists method to ProjectName that returns true only when there are no successors. To find successors, we need a query.

@Correspondence
public class ProjectName extends CorrespondenceObject {

	private PredecessorObj<Project> project;
	private PredecessorSet<ProjectName> prior;

	private Query<ProjectName> next = new Query<ProjectName>(this)
		.joinSuccessors("next");

	private @Field String name;

	public ProjectName(Project project, ObjectList<ProjectName> prior, String name) {
		this.project = new PredecessorObj<Project>(this, "project_name", project);
		this.prior = new PredecessorSet<ProjectName>(this, "next", prior);

		this.name = name;
	}

	public ProjectName(Memento memento) throws CorrespondenceException {
		this.project = new PredecessorObj<Project>(this, "project_name", memento);
		this.prior = new PredecessorSet<ProjectName>(this, "next", memento);
	}

	@Override
	protected boolean exists() {
		return next.isVoid();
	}

	public String getName() {
		return name;
	}

}

Notice that the exists method uses isVoid rather than isEmpty. The difference is significant. An empty query is one that currently returns no objects. A void query is one that never has. Objects that return false from exists are not included in query results. So if a successor is created and then "destroyed", the query will again be empty. It will not, however, be void.

When the project began, its name was first set to "WSE". Later, the name was changed to "Indigo". The ProjectName "Indigo" replaced "WSE" and caused its next query to return an empty result set. Some time later, the ProjectName "WCF" was created. It caused "Indigo" exists to return false, which in turn caused the "WSE" next query to return a non-empty result set. If exists was based on isEmpty, then "WSE" would again show up as a project name. That's not what we want, so we use isVoid instead. Once isVoid is true, it can never go back to being false.

The property query
The Project needs to know about its ProjectName successors to determine its current name. So we add a query to the Project class to find them. This query will only return the ProjectNames that still exist. Because of their exists method, this will only be the leaves of the tree. Any ProjectName that has been replaced will have a successor and therefore no longer exist.

@Correspondence
public class Project extends CorrespondenceObject {

	private Query<ProjectName> name = new Query<ProjectName>(this)
		.joinSuccessors("project_name");
	private Query<Issue> issue = new Query<Issue>(this)
		.joinSuccessors("project_issue");

	private @Field UUID id;

	public Project() {
		id = UUID.randomUUID();
	}

	public Project(Memento memento) {
	}

	public Iterable<Issue> getIssues() {
		return issue;
	}

}

The getter and setter
The property query gives us all the information we need to get and set the property value. The current value of the property is based on the leaves of the version history tree, which is precisely what the query returns. If there is no conflict, then there is only one leaf. If there is a conflict, then we can resolve it. For now, we'll take the easy way out and return the most recent conflicting version. Other strategies are possible.

When setting the property, we want to replace all current versions of it. The predecessors of the new ProjectName are all of the leaves of the version history tree. This technique allows the user to resolve a conflict by entering the correct value of the property. All of the conflicting versions are replaced by the one correct version. The branches of the tree are grafted together and we end up with just one leaf. No more conflict.

@Correspondence
public class Project extends CorrespondenceObject {

	private Query<ProjectName> name = new Query<ProjectName>(this)
		.joinSuccessors("project_name");
	private Query<Issue> issue = new Query<Issue>(this)
		.joinSuccessors("project_issue");

	private @Field UUID id;

	public Project() {
		id = UUID.randomUUID();
	}

	public Project(Memento memento) {
	}

	public String getName() {
		// Get the most recent leaf.
		ProjectName leaf = name.getLast();
		if (leaf == null)
			return "<New Project>";
		else
			return leaf.getName();
	}

	public void setName(String name) {
		getCommunity().addObject(new ProjectName(this, this.name.getObjectList(), name));
	}

	public Iterable<Issue> getIssues() {
		return issue;
	}

}

By following these five steps, we define a mutable property for a Correspondence object. Instead of allowing mutation to be a primitive of the system, we implement mutation as a pattern. This allows the core system to remain synchronization friendly while giving us the behavior that users expect.

How to delete a Correspondence object

Wednesday, November 5th, 2008

A Correspondence object records the fact that an atomic operation has taken place. No matter what happens in the future, the fact remains that that operation occurred. No action can truly expunge an object.

But one atomic operation can negate the effect of another. It can leave the system as a whole in a state equivalent to one in which the first operation never happened. At least from an application point-of-view.

So the way to delete a Correspondence object is to create a successor that negates it.

The exists method
The CorrespondenceObject base class defines a method called exists. A derived class overrides this method to return true if the object exists, or false if it does not. This test must be performed by examining the results of queries. So the method returns true if the query for negating objects returns an empty set.

Suppose we want the ability to delete an issue in our bug tracking system. To do so, we have to define a new class called IssueDelete that causes the issue not to exist. We'll start with this simple definition.

@Correspondence
public class IssueDelete extends CorrespondenceObject {

	// Issue that was deleted.
	private PredecessorObj<Issue> issue;

	public IssueDelete(Issue issue) {
		this.issue = new PredecessorObj<Issue>(this, "issue_delete", issue);
	}

	public IssueDelete(Memento memento) throws CorrespondenceException {
		this.issue = new PredecessorObj<Issue>(this, "issue_delete", memento);
	}
}

The Issue class is modified to query for IssueDelete successors and to cease to exist when one is found.

@Correspondence
public class Issue extends CorrespondenceObject {

	// The project to which this issue belogs.
	private PredecessorObj<Project> project;

	// Query for deletion of this issue.
	private Query<IssueDelete> delete = new Query<IssueDelete>(this)
		.joinSuccessors("issue_delete");

	// Identity.
	private @Field UUID id;

	public Issue(Project project) {
		this.project = new PredecessorObj<Project>(this, "project_issue", project);
		this.id = UUID.randomUUID();
	}

	public Issue(Memento memento) throws CorrespondenceException {
		this.project = new PredecessorObj<Project>(this, "project_issue", memento);
	}

	public Project getProject() {
		return project.getObject();
	}

	@Override
	protected boolean exists() {
		return delete.isEmpty();
	}

	public void delete() {
		getCommunity().addObject(new IssueDelete(this));
	}
}

The delete query looks for successors in the "issue_delete" role of the type IssueDelete. If any such objects are created, the results of this query will no longer be empty. That will cause the exists method to return false. Just such an object is created in the delete method. Notice that the object is added to the Community, which is the repository for all Correspondence objects. We'll have a lot more to say about the Community in later posts.

Restore a deleted object
But this feature is not finished. While the IssueDelete class makes it possible to delete an issue, that deletion cannot be undone. Just like any other atomic operation, the fact that the deletion occurred cannot be expunged. In order to undo the deletion, we need to delete IssueDelete.

We do this by creating a class called IssueRestore.

@Correspondence
public class IssueRestore extends CorrespondenceObject {

	// The deletion to undo.
	private PredecessorObj<IssueDelete> delete;

	public IssueRestore(IssueDelete delete) {
		this.delete = new PredecessorObj<IssueDelete>(this, "undo", delete);
	}

	public IssueRestore(Memento memento) throws CorrespondenceException {
		this.delete = new PredecessorObj<IssueDelete>(this, "undo", memento);
	}
}

And then we modify IssueDelete to exist only when there are no such successors:

@Correspondence
public class IssueDelete extends CorrespondenceObject {

	// Issue that was deleted.
	private PredecessorObj<Issue> issue;

	// Query for restore.
	private Query<IssueRestore> restore = new Query<IssueRestore>(this)
		.joinSuccessors("undo");

	public IssueDelete(Issue issue) {
		this.issue = new PredecessorObj<Issue>(this, "issue_delete", issue);
	}

	public IssueDelete(Memento memento) throws CorrespondenceException {
		this.issue = new PredecessorObj<Issue>(this, "issue_delete", memento);
	}

	@Override
	protected boolean exists() {
		return restore.isEmpty();
	}
}

Uniqueness of a deletion
We are almost done. There's just one last problem. Delete an issue, and it disappears. Restore it, and it comes back. But if we delete it a second time, nothing happens. Why?

The set of an object's predecessors and fields is its identity. If you create an instance of the same class with the same predecessors and fields, you will get the same object. The second time we attempt to delete an issue, we only succeed in reasserting the existence of the first deletion. For this system to work, deletions must be unique.

To make an object unique, we give it a unique field. We add a UUID to IssueDelete:

@Correspondence
public class IssueDelete extends CorrespondenceObject {

	// Issue that was deleted.
	private PredecessorObj<Issue> issue;

	// Query for restore.
	private Query<IssueRestore> restore = new Query<IssueRestore>(this)
		.joinSuccessors("undo");

	// Identity.
	private @Field UUID id;

	public IssueDelete(Issue issue) {
		this.issue = new PredecessorObj<Issue>(this, "issue_delete", issue);
		id = UUID.randomUUID();
	}

	public IssueDelete(Memento memento) throws CorrespondenceException {
		this.issue = new PredecessorObj<Issue>(this, "issue_delete", memento);
	}

	@Override
	protected boolean exists() {
		return restore.isEmpty();
	}
}

And so with this pattern a Correspondence object can be deleted, restored, and deleted again. Deletion and restoration both represent atomic operations, and are therefore both recorded as new objects. Although they represent modifications of the object graph from an application point-of-view, these Correspondence objects adhere to the law that an object is immutable. As we've discussed in previous posts, this is the law that makes synchronization possible.