Archive for the ‘Synchronization’ Category

Correspondence code cadence

Sunday, September 26th, 2010

As a follow up to the demonstration of Correspondence on Windows Phone 7, I’ve added a feature to the Reversi app. This demonstrates the cadence of coding with Correspondence.

The cadence is:

  • Fact
  • Community
  • Query
  • View Model

First, you define a fact in the model. A fact represents an action taken by a user. It is a fact that a player sent a message in a game.

Second, you add that fact to the community. When the user presses “Send”, call Community.AddFact(new Message()).

Third, you write a query in a related fact. Query a game for all of the messages.

Fourth, you expose that query through the view model. Data bind to the collection of messages.

Watch this video for an example of that code cadence as I add the chat feature to Reversi, both in WPF and in Windows Phone 7.

Coding Correspondence on WP7 and WPF from Michael L Perry on Vimeo.

Bonus question: what step is usually part of a client\server application that you do not see in this cadence?

Correspondence on Windows Phone 7

Sunday, September 26th, 2010

Correspondence is the ideal platform for creating phone applications. Express your model once, and it generates local storage and network communications. Here’s a demo of Reversi running on Windows Phone 7, and a quick walkthrough of the code.

Correspondence on Windows Phone 7 from Michael L Perry on Vimeo.

A better Ignite Dallas video

Thursday, March 11th, 2010

Here’s a high quality video of last weekend with slides included.

Ignite video online

Sunday, March 7th, 2010

How do we collaborate through software?

  • The CAP Theorem – Eric Brewer
  • Eventual Consistency – Werner Vogels
  • Event Sourcing – Greg Young and Udi Dahan
  • Partial Order

Download the slides

How do we collaborate through software: Take 2

Thursday, February 25th, 2010

It is official. I have been invited to speak at Ignite Dallas.

In my prior recording of the talk, I neglected to mention the names of some folks who have been influential in collaborative application design. This new recording remedies that oversight.

I also modified the second half of the talk to tell the partial ordering story a little better. It still needs the slides in order to really get it, but fortunately those are coming along.

Give it a listen. Hope to see you next Wednesday!

How do we collaborate through software?

Saturday, February 20th, 2010

I am preparing for the upcoming Ignite Dallas event. 5 minutes, 20 slides that auto advance every 15 seconds. The final speaker list has not yet been determined, but I’m hopeful that I’ll have a chance to present.

I will be talking about the current thinking in collaborative applications.

  • The CAP Theorem
  • Eventual Consistency
  • Event Sourcing
  • Partial Ordering

The challenge is to condense all of this learning into 5 minutes, make it accessible, and make it entertaining. You can help.

Please take five minutes (actually 4:45) to listen to my rough draft. Leave comments on what I can improve, what I didn’t make clear, and anything I could leave out.

Then order your tickets to the event and see some really great performances. Or submit one of your own.

Correspondence Reversi

Wednesday, January 27th, 2010

Correspondence is a library for creating collaborative smart client applications in .NET. When you express a model in Correspondence, it provides three things:

  • Storage
  • UI updates
  • Synchronization

This open source library includes a demo application to illustrate its collaborative capabilities. Correspondence Reversi is a WPF rendition of a popular two player game. Download the client to play against a friend, or to randomly join in a game with a stranger. Download the source code to learn how Correspondence makes collaboration easy.

Applications typically store their data in a relational database. But they act upon that data by loading objects into memory. To bride the gap, application designers can choose from several object-relational mappers (ORMs).

The problem with the ORM approach is that it requires the application designer to express their model three times:

  • Database schema
  • Objects
  • Mapping configuration

Keeping these three in synch becomes a maintenance task each time the model changes. And deploying a new version requires that the data be migrated to the new schema.

Correspondence is not an ORM. The application model is not reflected in a relational database schema. When the model changes, only the objects are changed. The schema remains consistent. This allows for new versions to be deployed without changing the database or migrating data. And it eliminates the need for mapping configuration, as the library stores all models the same way.

UI updates
Correspondence is built on top of Update Controls, a library for keeping UI controls up-to-date. While most UI update libraries require you to manage your own dependencies, Update Controls discovers them for you and manages them on your behalf. The only thing that Update Controls requires is that your model alert it when a property is accessed or modified.

Correspondence takes on the responsibility of notifying Update Controls. A Correspondence model can be bound to a Winforms or WPF user interface – even through an intermediate View Model – to provide automatic dependency discovery and change notification. A Correspondence application developer will never see INotifyPropertyChanged or ObservableCollection.

By far the most compelling feature of Correspondence is that it automatically synchronizes a data model among clients. Two or more people collaborating on the same data on different machines will automatically see each other’s changes. The automatic UI updates provided by Update Controls ensure that changes made on one machine automatically appear on the screen of another.

Most smart client applications switch from off-line mode to on-line mode based on the availability of the network. While on-line, smart clients communicate changes that the user makes with a server. It runs queries on the server to bring back information that the user wants to see. While off-line, they switch into a mode where data storage and queries are performed locally. Typically, smart client synchronization occurs during the switch between modes.

Correspondence works differently. It offers a consistent programming model whether the network is available or not. Objects created in Correspondence are stored locally, regardless of network availability. A background thread constantly synchronizes the local storage with a server when available, and silently waits when it is not. By eliminating the switch between modes, Correspondence simplifies the task of smart-client development, and improves the end-user experience.

Correspondence Reversi synchronizes with a cloud service running in Windows Azure. This service collects data from each client, and redistributes that data to other clients who need it. Two people playing a game together will see each other’s moves. But they will not see any of the traffic from other games. This is not a special feature of the Reversi game model. This is a feature of Correspondence. A different model will be synchronized just as intelligently, and will work with the same synchronization service. There is nothing application-specific about the cloud service.

Please download the client and play against your friends. Then explore the source code and see what you can do with Correspondence.

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.

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.