Constrained Tree Schemas (CTS) and applications (CTA) for extreme OLTP (XTP)

Writing extreme transaction processing applications (XTP).

This article describes how to write extreme transaction processing applications using ObjectGrid. It will show the common characteristics of these applications and illustrate how to put the various characteristics together. This article is not an introduction to ObjectGrid programming but it will help illustrate how to write XTP applications using ObjectGrid.

Constrained Tree Schemas

It’s difficult to write an XTP application using a generic data schema. XTP works best using constrained tree schemas. There are many examples of such schemas. The most familiar one is probably something like “Customer has Orders has OrderItems”. Another would be “User -> Permissions” or “Customer has Account has Account Transactions”. These schemas have a root entity object like Customer and User. These root entities have zero to many relationships with what I’d call sub-entities. A sub-entity only exists if it’s owned by a root entity. You can only navigate to a sub-entity by first finding the root entity. These schemas also don’t have references to other root entities. Each customer is independent of all other customers. The same behavior applies to users. This type of schema lends itself to partitioning. Each constrained tree schema can be partitioned using the key of the root entity.

Schemas such as “Customer has Account has Account Transactions” probably immediately raise alarm bells. What happens when there are lots and lots of transactions for a single account? Will we run out of memory? Of course is the answer if that’s what we do but obviously we need to archive transactions. The application designers may decide to keep no more than 30 days of transactions in memory or 1000 transactions. The actual number that can be kept in memory completely depends on the size of address spaces, the number of partitions per address space and the size of the entries. The application needs to archive them to a database and if data is needed that’s not in memory then pull it in temporarily. Most transactions will not need all the data. The archived data can be summarized and the summary data held in memory and updated whenever new data is archived. This keeps the in-memory footprint is kept constant. If an application needs everything and the number of records is unbounded then it’s not an application that can exploit XTP and such an application will have problems scaling in an unlimited fashion.

Constrained Tree Applications

Once we have a constrained tree schema (CTS) then we can think about applications using use these schemas, constrained tree applications (CTA). These are applications that use constrained tree schemas and only execute transactions that use a single root entity at a time. This means that transactions don’t span a partition and complex protocols such as two-phase commit are not needed. A one phase or native transaction is enough to work with a single root entity given it is fully contained within a single transaction.

Transactions sometimes need access to data that is shared between root entities but typically this is read only reference data. This data can be replicated so that it’s contained in every partition or it can be stored in a separate grid and then accessed remotely.

Application and data collocation

If an application can arrange that its transaction logic runs in the same address space as the data that it uses then performance will significantly improve as all the data needed by the transaction is in memory data with almost no access cost or network latency. The issue now becomes routing the transaction request to the server hosting the data needed by the transaction. This means the root entity key must be part of the transaction request data and this is implied in any case when using a constrained tree schema.

If a Transaction needs to modify a number of root entities then the application will use a chain of N transactions where N is the number of root entities impacted. There are a couple of approaches for implementing this chain. The easiest approach is to store the current state of the chain itself within a CTS keyed by chain transaction id. This means the chain state itself is modified transactionally. Each the chain progresses from step to step then it executes an idempotent transaction against the root entity for that step in the chain. Idempotent means that if the server holding the chain crashed while waiting for the sub transaction to complete then when it is restarted, it should just re-execute the transaction. This assumes the sub transaction can be run multiple times safely without causing bad side effects such as withdrawing funds from an account multiple times. Traditionally, this chain can be implemented using a workflow engine or a state machine implemented in an XTP style on top of products such as ObjectGrid.

Summary

This article explains the kinds of data model schemas you need in order to have real linear scalability. It also explains the limitations on transaction logic and things like transaction and data collocation. You can think of these as limitations but these are really enablers, not limitations. If you think these are limitations then wait till you try to scale an application that’s designed without these ‘limitations’. Now what’s a limitation? If an application isn’t designed with these enablers in mind then basically it’s going to be very expensive and difficult to make it scale. Almost every “high performance” application that starts off without these enablers eventually runs in to a scalability crisis and then discovers the golden enablers described in this article. Once the application is enabled like this, it can scale linearly at low cost and to extreme levels.

Comments

[Damien Wintour]

Billy,

After digesting the H-store article by Stonebaker et al and being envious of the XTP benchmarks mentioned therein, I found your blog post about CTA/CTS - clearly the major requirement of schema partitioning for in-memory grid operation. My question is... how do you convert traditional many-to-many relationships to CTS?

[sreeni]

I am looking for some blogs or training material on websphere App server, RAD, Spring, JSF, Hibernate.
Can you please send me some links that can help me.

Thank you

[Mahendra K. Pingale]

Hi Billy,

Great and very informative blog! Thanks.

One question: You say here that, "This means that transactions don’t span a partition and complex protocols such as two-phase commit are not needed." I assume, you mean 2PC is not required for the in-memory transactions. When it comes to committing these transactions to the backend datastore through write-behind, they would need 2PC and "other complex protocols," depending on how complicated the backend datastores are.

Correct? Thanks again.

[Billy]

2PC isn't needed because transactions cannot span two partitions. The interaction between the back end and the grid is assumed idempotent so again 2PC isn't needed there either. Idempotent means all transactions can be repeated safely. We guarantee order on the write behind transactions so worst case on a failover, the transaction would be 'reapplied' on the newly promoted primary.

[Hyang04]

This is informative and interesting. In place of 2pc, you said that there are several approaches and detailed one. Let's take paypal as an example, we need to implement money transfer between 2 members, and they are potentially on different partitions. I wonder if you can provide some sample code snippets as to how it is done in extremescale.

Also can you briefly describe the other alternatives, or provide a reference link to them.

Thanks.