10 June 2008 - 12:20Grid design patterns - de-normalized data

I am watching with a great deal of interest developments in the grid and large scale computing environment because I always found distributed computing interesting.

One very interesting thing that I come across pretty often is the fact that in large scale computing data tends to get de-normalized, basically it grows so large that you cannot fit the entities and the relationships between entities in the same database (this infoQ article is pretty good).
Let me give an example: suppose that you have table of users and a table or messages between users having these columns:
users: userID int, firstName String, lastName String, email String
user_messages: fromUserID int, toUserID int, messageTest String.
In the initial design a message from user A to user B would have only one record in user_messages and each user will be able to get the messages it has sent and the messages it has received from this table.
Now let’s say that the number of users sky-rockets to the point where you need to partition your database horizontally into a series of identical replicas. The problem that you will face now is where to store the data that is shared between these replicas, namely the table user_messages. You cannot store it either in the replica hosting user A’s data, neither in the replica hosting user B’s data and neither in its own instance because it will grow too large and because you will need to carry out a join over 2 physically remote databases. The solution is to drop user_messages for received_user_messages (from_user_name, from_user_email, message_text) and sent_user_messages (to_user_name, to_user_email, message_text) which will store the messages that a user has sent and the ones that it had received. Each database replica will have its own instance of these 2 tables each mapped to the user table. As you can see we are not storing the userID in the message tables, but rather the user information which was previously retrieved via joins.
Sending a message from user A to user B in this environment typically involves updating 2 tables in 2 separate database instances which usually is treated as a distributed transaction. However, you cannot carry out this distributed transaction because it is very costly so sometimes you resort to updating one table and sending a message to update the second table asynchronously (the overhead for delivering a JMS message is way less than the overhead for locking rows in the second database). In the case of updating the second table asynchronously you are still enforcing the relationships between the user table and the user message tables, but at a later point in time.
De-normalized data comes with synchronization costs: when you are updating the user information on the users table you will need to propagate the changes to received_user_messages and sent_user_messages so that the data stored in these tables will be up-to-date. This could be done via asynchronous processing as well, sending a message about data being changed on an ESB and having the concerned parties listening for and processing it. Synchronization costs should be watched very carefully because they could spawn a very high number of messages. Ideally we would synchronize data which is updated rarely (such as user information) in order to keep the number of synchronization messages down. Carrying out synchronization procedures in batches could be a way to deal with a large number of synchronization messages with the side effect that it may increase the latency with which the synchronization takes place.

Large scale computing typically seems to resolve around asynchronous processing (because in transactions message passing is cheaper than database access) and de-normalized data across with the overhead implied by it. The relationships previously enforced by normalizing data are usually enforced by passing JMS messages which carry out the data changes asynchronously. This design is driven primarily by the large volume of data which cannot be serviced by only one database and by the costs of carrying out a distributed transaction spanning 2 databases.
This is one design that I see emerging for large scale computing: de-normalized data along with asynchronous processes which are enforcing the relationships between entities via message passing.

It remains to be seen if this type of grid architecture will prevail in the future. Working against it is the emergence of multi-core processors which would allow for scaling up cheaply as envisaged by Brian Goetz in this article. If chips with hundreds of multi-cores and with large amounts of memory become reality scaling out could end-up costing more than scaling up and all the above could become history pretty fast. Scaling out will continue to make sense in some environments with humongous amounts of data (think Amazon, Google, eBay, etc…) but for the current fastest growing segment in grid applications, typically applications processing moderately large amounts of data, it may make sense to scale up once chips with a large number of multi-cores become a reality.

To watch…

P.S. These shifts in data processing (moving to a grid-type of architecture in order to accommodate the increase in data and then back to a single-box architecture because of the appearance of chip with a large number of cores) makes a pretty good case for abstraction in order to lower the costs of transition from one architecture to another. Ideally the architecture and the environment in which an application runs should not affect the business logic of that application. One way to insulate your application’s business logic from these infrastructure issues is by abstraction.