Archive for October, 2008

Mutable properties

Thursday, October 30th, 2008

All of the fields of a Correspondence object are immutable. They are set at the time of construction. They define the identity of an object, so they cannot be allowed to change.

How, then, can you represent mutable properties in Correspondence? By doing the only thing that Correspondence allows you to do: create more objects.

A class for each atomic operation
A Correspondence object represents an atomic operation. It records the fact that someone has made a change. So one such change could be the modification of a property. Let's express the atomic operations of a project and one of its mutable properties:

  • CreateProject(): Project
  • SetProjectName(project: Project, name: string)

Since we have two atomic operations, we define two Correspondence classes. The class that represents the CreateProject operation is the Project itself. The class that represents the SetProjectName operation will be called ProjectName.

Define prerequisites
It is apparent from the definitions of these two atomic operations that the Project is a prerequisite for the ProjectName. You can't name a project before you create it. And in order for the ProjectName to make sense, you must know which Project you are talking about.

image So if Project is the only prerequisite for ProjectName, we can have an object model like the diagram on the right. If we set the project name three times, we end up with three ProjectName objects that are equal successors of the Project object.

There's one significant problem with the model just described. It is impossible to tell from the model alone which is the correct name of the project. It was set three times, and nothing about the diagram tells us which is the intended name. We could go by the time of creation, but that is insufficient in light of synchronization. One user might have set the name on one machine, while another user set the name on a different machine. We can't see the intent of the users in the model, so we can't make a reasonable decision.

Current knowledge is a prerequisite
The solution is to capture that intent by adding prerequisites. The prerequisites of an atomic operation are not just the parameters required for the operation to make sense in isolation. They also include the operations that have come before. The operation was performed by a user with a certain set of knowledge. If we capture that knowledge as prerequisites, we can glean the user's intent.

image In our case, we are going to capture the current project name as a prerequisite for any new project name. The user knew that the project was called WSE when he changed it to Indigo. Later, he knew that it was Indigo when changing it to WCF. This changes the diagram to the one on the left.

This diagram captures the intent of the user. He was changing the project name with the knowledge of the prior project name. And now the diagram clearly shows what the current name is: it is the last in the chain of succession.

Detect conflicts
image So what about the case of the two users on different machines? What if the developer chose the name Indigo while the analyst chose WCF? Both of those decisions were made with the knowledge of the name WSE, and so you get the diagram on the right.

From this diagram, it is apparent that there is a conflict. We no longer have just one leaf of the tree of ProjectNames. Now we have two leaves. Both of these siblings are just as worthy in the chain of succession of representing the current name of the project.

Correspondence makes no assumptions about how to resolve conflicts. But it does make it obvious when they have occurred. It is now up to the application to decide on a conflict resolution strategy. Knowing that there was a problem is the first step.

Fields of a Correspondence object are immutable. Modifiable properties are implemented as a pattern involving a new class, prior operations as prerequisites, and conflict detection. Conflict resolution is the responsibility of the application.

Correspondence

Thursday, October 23rd, 2008

Correspondence is a base class library (currently in Java and C#) for historic data models.

A historic data model is one in which the objects represent atomic operations rather than entities. To record that an operation has taken place, you create an object. You can then observe the history of related objects to determine the current state.

Anatomy of a correspondence object
The base class is CorrespondenceObject. A correspondence object has fields (simple data types) and predecessors (references to other correspondence objects). These fields and predecessors are assigned at construction and never change.

I'll demonstrate with the Java version of the library. Here is a simple correspondence object representing a project in a bug tracking system:

@Correspondence
public class Project extends CorrespondenceObject {

	private @Field UUID id;

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

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

	public Project(Memento memento) {
	}

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

And here's a bug:

@Correspondence
public class Issue extends CorrespondenceObject {

	private PredecessorObj<Project> project;

	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();
	}
}

A correspondence object has two constructors. One is used by the application to create the first instance of a new object. The other is used by the library to rehydrate an existing object from a memento.

Notice that both of these objects have id fields that are initialized to unique random numbers. This is how identity is assured in Correspondence. The identity of a correspondence object is the set of its predecessors and fields. If you try to create another object with the same predecessors and fields, you get back the same object.

These predecessors and fields cannot be changed. You cannot move an issue from one project to another. That is why you don't see project name or issue name as fields. These should be modifiable properties. We'll see how to make modifiable properties in a later post.

The list of issues for a project is dependent. It is represented by a query for all successors of the project. When a new issue is created, it will be returned from this query. You don't write code to add the issue to the list. Instead, the library updates this query when the new issue is created.

Data storage
The library takes care of persisting and caching objects and their relationships with one another. When you set up your correspondence project, you select a storage strategy. In Java, I have implemented MySQL and PostgreSQL storage strategies so far. In C#, I have ADO, DAO, and SQL Server CE. The Memento class is the intermediary that separates correspondence objects from the storage strategy and make that possible.

Although all of the storage strategies that I've implemented so far are built on relational databases, don't confuse Correspondence for an ORM. It does not map objects to a relational schema. The database does not resemble your object model in any way. It has two tables: Object and Predecessor. If you love relational data, do us both a favor and don't look in the database.

Even though it does not produce a database that you would want to use for reporting (or anything else, for that matter), the Correspondence library takes care of the persistence and caching of your objects automatically. You write an object model, and you get storage and caching for free. When you create an object, it gets stored. When you follow a reference to a predecessor, it gets cached. When you execute a query, the results are cached.

Next, we'll continue the development of the bug tracking system to demonstrate some of the common patterns that occur while using Correspondece.

Partial order of transactions

Tuesday, October 21st, 2008

Prerequisites define a partial order among transactions.

We've established that an object's state is dependent upon its history. All of the operations in the object's history are transactions. As such, they obey all four of the ACID principles.

An operation performed on an object is atomic. Remember that there is no method body for an operation. The system simply records that it has occurred. Since there are no imperative steps required to complete the operation, it cannot be partially done. It has either occurred, or it hasn't.

An operation is consistent. It exercises only one degree of freedom. Everything that depends upon that operation is represented by dependent data. When the operation is performed, and the dependent data is subsequently observed, it will be found to be consistent with the results of the operation.

An operation is durable. The system permanently records that it has occurred. When the object is observed later, the operation will be visible.

An operation is isolated from other operations occurring simultaneously. Again, since there are no imperative steps, this is easy to achieve. But there's more to it than that. Either of two operations that have occurred simultaneously could be assumed to have taken place before the other. There is no order prescribed between them. Instead of imposing a full order on the set of operations, we can only define a partial order.

Prerequisites of an operation
Every operation performed on an object is made within the context of prior information. All of the transactions that lead up to the current state of the object are known. These are prerequisites of the next operation.

Prerequisites are operations that must have occurred prior to a given operation. If those prerequisites themselves have prerequisites, we can trace a tree back to its root. This gives us a list of operations that must have occurred in the given order. But parallel branches of this tree that split off from the root could have occurred before or after any other branch.

Going back to the canonical chess board example, we have three operations:

  • CreatePlayer(): Player
  • CreateGame(black: Player, white: Player): Game
  • MakeMove(from: int, to: int, game: Game, prior: Move ?): Move

chess-game-model.pngA game must have two players. Those player objects must have been created prior to the game. Each move is made within the context of one game. The prior move must have been made before the current one. The first move will have a null prior, hence the question mark.

This chain of prerequisites constrains the moves such that they must have been made in the specified order. It makes no sense to play the moves out of order. But if the players decide to start a parallel game, that one is completely isolated. It could have occurred before, after, or during the current game, with no loss of integrity.

Summary
With this, we have enough theory to build a robust synchronization system. This system uses atomic operations for persistence, representation, caching, and communication. It relies upon the three axioms that we've just discussed:

  • All object behavior is either dependent or independent.
  • An object’s state is dependent upon its history.
  • Prerequisites define a partial order among transactions.

Now it's time to turn the theory into practice.

Synchronization of history, not state

Friday, October 17th, 2008

An object's state is dependent upon its history.

When an object is constructed, it is initialized to a starting state. From then on, every action performed on that object changes its state. If you constructed another object and performed exactly the same actions on it, then it would end up in exactly the same state.

Suppose the object is a chess board. Its initial state has the two teams facing off against each other. Each move alters that state by one or two pieces. Start a new game and make the same moves, and the board will end up in the same position.

Store history
Caching aside, it is better to store independent data than dependent data. The dependent data can be calculated from the independent data, so there is no loss of information.

But the converse is not true. Several different sequences of moves could lead to the same board position. Given a board position, it is impossible to determine exactly which path was taken to get there.

The current state of an object is usually sufficient to make business decisions. That's why most of our business systems can get by with storing state, not history. A chess player makes his next move based solely on the current position of the pieces.

But the current state of an object does not carry sufficient information for synchronization. Synchronization is all about bringing two or more discrete representations into agreement. If I claim that an object is in one state, and you claim that it is in another, who is right? To decide, we have to go back through the histories and see where they diverge.

Calculate state
In an imperative object-oriented language, every mutating operation performed on an object causes changes to its member variables. Code inside the body of the method assigns new values to the members of the object. The prior state of the object, combined with the parameters of the method, determine what values get assigned.

If we allow our languages to be more functional and declarative, we could instead express the current state as a function of history. Suppose that there was no code in the method. The object just records the fact that the method was called. Now, move the code to the member variable. Its job is to calculate the value of that member variable given the history of method calls.

With this new declaration of an object, the current state is calculated based on history. From the outside it looks the same. You can call a method, then observe the state of the object to see that it has changed. The difference is that the method call did not imperatively change the state of the object, it just recorded a fact. It was the observation of that object's state, seeing this new fact, that caused the change. And now that the object retains history, it can be easily synchronized.

My synchronization system uses history, not state, to persist, exchange, and represent objects.

Dependent and independent object data

Wednesday, October 15th, 2008

An object has two kinds of data: dependent and independent. Independent data can be changed at any time by a user action. Dependent data is derived from other data in the system.

For example, a Person object has three properties: FirstName, LastName, and FullName. The user can directly set the first and last name, but the full name is derived. The user has no direct control over the full name. She can only influence it by changing the first or last name.

Sometimes it's hard to see the difference between dependent and independent data. Both kinds of data change in response to a user action. The key question is not "when does it change", but rather "what determines its value".

The UI might allow the user to enter a full name. When she types a new value, the UI parses the text she enters and determines the first and last names. It sets these two independent properties, and then calculates the full name. If the user entered well-formed input, the calculated output will be exactly the same. If not, the system will have "fixed" her mistakes (extra spaces, inconsistent formatting, etc.)

The number of independent properties is exactly equal to the number of degrees of freedom that an object has. Ideally, independent properties are unconstrained. Constraints are codified in the dependent properties.

Keep the data flowing
There are several strategies for updating dependent data. The most straight forward strategy is to recalculate dependent properties directly when an independent property is changed. I could code my person object to set the full name every time the first or last name is changed. This solution is easy to code, but breaks down quickly. For example, when I import a person from a CSV file, the importer writes both the first and last names. My naive implementation would calculate the full name twice.

Another strategy is to keep a marker for dependent data that is out-of-date. When the independent data changes, set the marker. When someone asks for the dependent data, check the marker. This postpones the update and therefore avoids redundancy.

When dependent data in one object relies upon independent data in another, things get even more interesting. If you take the direct approach of notifying the dependent object from the independent one, you end up with tightly coupled objects. The observer pattern breaks that coupling. There are several other patterns that offer benefits over observer (including my own) that are too numerous to list here.

Now add to the mix the fact that dependent data may rely on other dependent data. So a change to an independent property should result in the update of all of its direct and indirect dependencies. This could be accomplished through cascading notifications, whereby the direct dependent upon receipt of notice turns around and notifies the indirect dependent. But to avoid potential redundancy or cycles, this is more often handled through dependency analysis. That is certainly too deep for this post.

Ebb and flow
No matter which strategy you use to update dependent properties, these two types of data create an ebb and flow within a system. A user action directly changes one or more independent properties. Those changes flow back toward the user in the form of dependent properties.

My synchronization framework starts with this fundamental concept. All object behavior is either dependent or independent.

Object representations and transformations

Monday, October 13th, 2008

An object has many representations. In a relational database, objects are represented as related tuples. In an object-oriented language, objects are instances of classes that have properties and behaviors. In an XML file, objects are elements conforming to a schema, belonging to other elements, and having both attributes and child elements.

Each representation of an object obeys certain rules. A relational database has foreign key constraints. An object-oriented language has a type system. XML must be well-formed.

Each representation of an object has certain limitations. In a relational database, all related objects must be co-located. In an object-oriented language, not all objects can be loaded into memory simultaneously. In XML, only one narrow branch of a hierarchy can be represented in a single document.

Each representation of an object has its own concept of identity. A relational database has keys. An object-oriented language has references. XML has paths.

When an object crosses the boundary between two representations, it must simultaneously conform to two sets of constraints. To load an object graph from a database into memory, we map ids to references, we map data types, and we store related objects in collections. To turn that object graph into an XML document, we traverse the collections hierarchically, convert non-hierarchical references into paths, and serialize it according to a documented schema.

I am building a framework for moving objects across boundaries while preserving their integrity. This system has its own concept of identity, its own set of rules, and its own limitations. Rather than trying to accommodate all of the other possible representations, I've started from scratch. In the coming posts, I'll define the system.

Moving bits

Friday, October 10th, 2008

I'm solving the same problem again. I have an object written in C# that I need to store in a database.

Even though I've expressed the object in C#, I need to also express the same object in XSD and in SQL. I've run "xsd.exe" to generate a memento class that contains the data but no business logic. I've written code to move the data from the business object into the memento class, serialize it to XML, and send it to the server. On the server, I've written code to receive the XML, deserialize it back to a memento, and turn it into a stored procedure call. I've written the stored procedure to update the row, unless it does not exist in which case it inserts.

I've done all this before. Every time the domain model changes, I do it all over again. Every year some new technology comes out that replaces part of the old stack, and I start writing the same code for that.

This stops now.