BT

New patterns and middleware architecture needed for true linear scalability?

by Johan Strandler on Aug 03, 2007 |
Is there a need for new patterns and middleware-architectures when building linearly scalable applications? Nati Shalom, CTO at GigaSpaces, believes that existing middleware designed for a tier-based approach cannot be used for a true linearly scalable architecture. Instead he proposes a new middleware stack based on self-sufficient processing units that supports a partitioned/scale-out model.  While Shalom proposes a new middleware stack, Pat Helland at Microsoft, some years ago proposed some new transactional patterns and formalizations to be used in what he calls almost-infinite scalable systems.

Nati Shalom argues that the tiered approach (messaging, data and business processing) is a dead-end, since it introduces a lot of state and "messaging ping-pong" in and between each tier, only for the purpose of keeping the shared data in sync. He means that the tiered approach is bound to provide a non-linear scalability, making it necessary to exponentially add new CPUs in order to achieve linear increase of throughput.

Instead, Nati suggests a different architectural approach where these tiers has been put together in one processing unit, keeping the messaging, data and processing in the same address space. Combined with a share-nothing architecture between processing units, this gives a linear scalable solution by just adding machines as the processing needs increases. This model is of course very suitable for stateless applications, but for stateful applications things get a bit more complicated. Nati previously   spoke about how to scale a stateful app by giving two basic rules:

  1. You need to reduce contention on the same data source
  2. You need to remove dependency between the various units in your application. You can only achieve linear scalability if each unit of work is self-sufficient and shares nothing with other units

These are basic principles of scalability. A common pattern to achieve these two principles in a stateful environment is through partitioning, i.e., you break your application into units of work, with each unit handling a specific sub-set of your application data. You can then scale by simply adding more Processing Units.

If the data is dividable in these disjunct sub-sets of application-data, an application can be scaled-out to many independent processing units where each unit owns all the data for a sub-set. An example of typical data that is dividable in this way would be session information for a web application. This partitioning model does not work however when many application processes needs to access/update the same shared data. Shalom says that: "In such cases the data can be referenced through a remote partition i.e. the business logic and messaging would seat in one processing-unit and the data in a remote separate partition - in this way you still the get the scaling at the cost of latency."

But what if the volumes of the shared data is huge? One solution is to partition same type of data into different data-store partitions, but this solution gives two major problems to address:

  • Aggregation. How to perform query over a non centralized data store (i.e. one query over many data store partitions)
  • Use of atomic transactions vs. not using atomic transactions. Distributed transactions doesn't scale well, so some other solution is needed.

Shalom gives a solution for the aggregation problem:

You parallelize the query such that each query runs against each partition. By doing so you leverage the CPU and Memory capacity in each partition to truly parallelize your request. Note that the client issuing the queries can be unaware of the physical separation of the partitions and get the aggregated results as if it was running against a single gigantic data store with one main difference - it will be much faster!

In order to find a solution for the atomic transaction problem, we turn to Pat Helland, who has addressed this problem in a paper, "Life beyond Distributed Transactions: an Apostate’s Opinion", he made during his time at Amazon.com. In the paper he concludes that one basically shouldn't use cross-system transactions in large scale systems. 

Reacting to the lack of well known terminology for concepts and abstracts used in building scalable systems, Helland defines:

- Entities are collections of named (keyed) data which may be atomically updated within the entity but never atomically updated across entities.

- Activities comprise the collection of state within the entities used to manage messaging relationships with a single partner entity.

Workflow to reach decisions, as have been discussed for many years, functions within activities within entities. It is the fine-grained nature of workflow that is surprising as one looks at almost-infinite scaling.

By this, Helland means that two entities can not be updated in the same transaction. Instead he assumes "multiple disjoint scopes of transactional serializability", where he later in the paper defines this scope as an Entity. An update of multiple entities can not with this definition be performed within a single atomic transaction, but has to be done through messaging across entities in a peer-to-peer fashion between entities. This messaging introduces the need for managing conversational state by itself, and Helland defines this management of state for each entity partner as an Activity. He gives an example:

Consider the processing of an order comprising many items for purchase. Reserving inventory for shipment of each separate item will be a separate activity. There will be an entity for the order and separate entities for each item managed by the warehouse. Transactions cannot be assumed across these entities.

Within the order, each inventory item will be separately managed. The messaging protocol must be separately managed. The per-inventory-item data contained within the order-entity is an activity. While it is not named as such, this pattern frequently exists in large-scale apps.

The lack of transactional atomicity between entities and the messaging introduced by this, causes new problems that lurks it's way all up to the business logic; message retries and processes that must be able to handle idempotence. Also, the need of asynchronous messaging between entity-peers enforces implementation of fine granular workflow's - including tentative operations with the following cancellation/confirm operations.

This architecture desribed by Nati Shalom has been implemented in GigaSpaces platform, which recently released version 6.  Pat Helland's paper is timeless and definitely worth a thorough read.

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Server down by Martin Probst

Uh ha - Gigaspaces.com seems to have some performance problems currently ;-)

Re: Server down by Nati Shalom

works for me

New patterns and middleware architecture needed for true linear scalability by Nati Shalom

Johan you covered this topic quite well.


The lack of transactional atomicity between entities and the messaging introduced by this, causes new problems that lurks it's way all up to the business logic; message retries and processes that must be able to handle idempotence. Also, the need of asynchronous messaging between entity-peers enforces implementation of fine granular workflow's - including tentative operations with the following cancellation/confirm operations.


That's part of the reason why were seeing a move toward Even Driven Architecture (EDA), High Performance SOA as the architecture of choice for building scalable applications rather then the synchronous tier based approach.

Quoting Werner Vogels the CTO - Amazon.com from his post a a word on scalability"Why is scalability so hard? Because scalability cannot be an after-thought."

As Werner argues, we cannot treat scalability as just an optimization, it needs to be part of our architecture. The main challenge is to make it simple enough so that users not familiar with all the theory behind scalability would be able to build scalable applications. As a lesson from JEE experience, the key for success is simplicity. By simplicity i mean how simple it would be to design, implement, test and deploy this style of applications.

So far all we saw coming from the industry is new acronym's in different shapes and forms promising that the future will be brighter and nicer but very little focus has been put on providing a clear path on how i can take my existing tier based application and move it to this new style of scale-out model

Our approach to that challenge was expose similar programming model to the one used in exiting middleware stack and focus on replacing the underlying implementations of those programming models in a way that will fit the scale-out model that Johan covered in this article. In this way the transition from existing tier based approach becomes significantly simpler and intuitive. Using Spring as the underlying platform makes the transition even smoother especially for those already familiar with Spring. There are few code examples that shows how simple it could be to write such application here

Nati S.
GigaSpaces
Write Once Sale Anywhere

New patterns and architecture available for true linear scalability by Cameron Purdy

In addition to supporting all of the models described above (e.g. Data Grid dynamic partitioning, parallel query and parallel aggregation were all originally introduced in our Coherence software), we have added once-and-only-once processing guarantees in a distributed environment, including during failover and re-balancing conditions, and including support for both scalar and aggregate operations. This means that you can achieve information reliability without sacrificing scalability and even without having to hold open two-phase commits, even for multi-server operations occurring in parallel, even if they are mutating operations. As anyone doing serious distributed software systems will tell you, once-and-only-once guarantees are one of the "holy grails" of distributed system.

Coupled with our partitioned data affinity support, many of the "cross-system transactions" can be reduced to one guaranteed once-and-only-once atomic transaction that occur with 100% data locality. In more complex cases, a distributed EDA (using the same guarantees) can create a reliable series of such transactions, each atomic and with 100% data locality.

The end result: Systems with continuous availability, information reliability, better scalability, and much higher transaction rates.

Peace,

Cameron Purdy
Oracle Coherence: The Java Data Grid

Re: New patterns and middleware architecture needed for true linear scalabi by Steven Devijver

Nati,

Thanks for your interesting views. I can testify from the business end of scalability that, well there is nothing simple about it.

The biggest problem with scalability is that either customers don't want/think they don't need it or if they want it/think they need it most of the time they don't get it.

The reason for this is due in part to a host of economical and business practice realities, all of which can be changed given some time.

But they don't change and for a good reason: new approaches that diverse from the beaten track - for example new approaches to scalability - create cognitive dissonance, starting at the moment one is introduced with the new topics.

If you open one book Entity means this and if you open any other one Entity means something entirely different. Cognitive dissonance.

Scalability cannot be an afterthought yet I can migrate my layered application - where scalability never even has been considered - to a fully scalable beast. Cognitive dissonance.

And so it continues. Sure, banks and the CIA know how to do scalability. The challenge is to spread whatever they are doing beyond them. History shows that this is almost never possible except for trivial technologies that work, always.

Examples are transactions and web services. Distributed memory is vastly different since most people's brain starts to hurt when they start thinking about how this affects them.

Cognitive dissonance by Julian Browne

I'd agree that it's difficult to cross the scalability-need dissonance chasm, but by no means impossible. Businesses certainly do exhibit tendencies to either not know they need scalability or not prioritise it, but that's to be expected as they tend to live in the very tangible world of functional requirements.

When it comes to enlightening them on their need for scalability, though (a classic non-functional) it's illustrating the lack of it that makes them sit up in their chairs. Marketing might start falling asleep at the sight of TPS profile curves, but if they hear they'll loose millions of dollars because no more than 200 customers can get on the web site at lunchtimes, they suddenly develop an interest in the subject.

It also needn't be expensive (at least not compared to migration costs later) or overly complex - Gigaspaces, Coherence and others conveniently hide a lot of the transactional details so you can concentrate on other things.

If your business is selling spanners online then you'll probably find that a tiered architecture will do just fine, but you don't need to be up into thousands of transactions per second to benefit from a grid approach - the availability and event-processing capabilities can make the business case on their own.

Re: New patterns and middleware architecture needed for true linear scalabi by Nati Shalom

The biggest problem with scalability is that either customers don't want/think they don't need it or if they want it/think they need it most of the time they don't get it.


Look at the architectures of Google, Amazon, eBay, MySpace, LiveJournal and other Web stalwarts. They have all come to the same conclusion - with different nuances. They have all realized that the level of scalability, reliability and performance they need -- while keeping cost and complexity down -- will not come from a J2EE app server + database + messaging. It will not come from an n-tier architecture. Instead, they moved to a scale-out architecture, which aims for a shared-nothing approach.

The above references obviously represent the very high-end organization that where first to hit the wall in terms of scalability. With the emergence of Web 2.0, the exponential growth in the volume of data applications need to process and the requirement to process this increasing amount of data at a shorter time and yet at lower cost drives lots of other organizations for scale-out approach. Regardless of the solution they choose they all realize that getting the required level of scalability cannot be met just by twiking the data-base or application server.


The reason for this is due in part to a host of economical and business practice realities, all of which can be changed given some time.


I have to disagree with you on this one.
The economical drive is very clear and quite big.

Imagine an application that can handle 100 transaction/sec. That application doesn't scale linearly due to contention around the database ( a typical scenario in most tier based applications). Let's say that to meet the 100 transactions/sec it need a single a single server with 4 cores which cost $5k.
Now instead of 100 transaction/sec you are asked to support 500 msg/sec. Since the scale is not linear you can't just put 5 machines to handle that 5 times growth, instead you need 10 machines - (that already doubles the cost). Now imagine the case where the requirement now grows to 5000 transactions/sec - at this level the application is totally saturated and limited by the centralized db approach. That means that regardless of the amount of HW resources you will add you wouldn't be able to meet the requirement. Now go figure the cost in such case! - Add to all that the cost related to complexity of scaling, the cost for testing and managing such environment as well as the cost for continues changes to your application to apply the necessary optimization and you'll get a clear economical justification for scaling.

HTH
Nati S.

New Patterns by Frank Bolander

A lot of this stuff sounds like particle systems. Most current research is about graphics systems and physical modelling, but there is no reason the concepts couldn't be translated to business processes.

Re: New patterns and middleware architecture needed for true linear scalabi by Arnon Rotem-Gal-Oz


Look at the architectures of Google, Amazon, eBay, MySpace, LiveJournal and other Web stalwarts. They have all come to the same conclusion - with different nuances. They have all realized that the level of scalability, reliability and performance they need -- while keeping cost and complexity down -- will not come from a J2EE app server + database + messaging. It will not come from an n-tier architecture. Instead, they moved to a scale-out architecture, which aims for a shared-nothing approach.


Right - but and it wasn't a data grid either - they all came to the conclusion that it is better to put an emphasis on partitioning (which is by the way the idea behind SOA) and availability. The other result of that (as explained in CAP) they've settled for consistent eventually

Arnon

Re: New patterns and middleware architecture needed for true linear scalabi by Nati Shalom


They all came to the conclusion that it is better to put an emphasis on partitioning


I agree - Partitioning is clearly the common denominator in terms of architecture but it has little to do with SOA.


Right - but and it wasn't a data grid either - they all came to the conclusion that it is better to put an emphasis on partitioning (which is by the way the idea behind SOA) and availability. The other result of that (as explained in CAP) they've settled for consistent eventually


Arnon i think that your missing the point.
1. The suggestion i'm making is not to use DataGrid as a solution for scalability - i actually argued in several occasions in the past that DataGrid is only part of the solution.
2. My second argument is that SOA is too broad and there is a need for a more specific pattern/blueprint that defines how you can utilize SOA/EDA and Paritioining concepts to scale stateful low-latency applications - this is where Space Based Architecture comes to place.

HTH
Nati S.

Not so fast ;-) by Cameron Purdy


Look at the architectures of Google, Amazon, eBay, MySpace, LiveJournal and other Web stalwarts. They have all come to the same conclusion - with different nuances. [..]


Right - but and it wasn't a data grid either - they all came to the conclusion that it is better to put an emphasis on partitioning (which is by the way the idea behind SOA) and availability. The other result of that (as explained in CAP) they've settled for consistent eventually


Actually, all the ones mentioned above do use distributed caching and/or Data Grid products to achieve their scalability.

Peace,

Cameron Purdy
Oracle Coherence: The Java Data Grid

Re: Not so fast ;-) by Geva Perry


Actually, all the ones mentioned above do use distributed caching and/or Data Grid products to achieve their scalability.


Correct, and the links above mention it explicitly.

Re: Not so fast ;-) by Arnon Rotem-Gal-Oz

I don't know enough about Google's architecture
but when I spoke with Randy Shoup (Ebay Architect) this was not what I understood regarding their architecture.
Ebay only caches immutable (or slow changing) data. and they actually partition their data carefully rather then use it in a data-grid like manner both of you are selling (at least the way I understand Tangosol and Gigaspaces i.e. a data cluster which is universally accessible)
Also if you listen to Amazon's Werner presentation here on InfoQ - you'd hear the same ideas as Ebay's

Arnon

Old ideas, new people by Humphrey Bogart

There is nothing new here, it is just new to the transaction processing crowd.

Look at CATOCS for a parallel example. You need to base this stuff on the business logic to solve it. It just doesn't fit in the platform layer because you don't know enough about the contention and process there and you end up doing full transactions and synchronization where you don't need it. doi.acm.org/10.1145/168619.168623

Entities are what the business world calls "documents", and activities are what the business world calls "conversations". Business people solved these problems on paper hundreds of years ago with manual procedures.

Once your typical OO programmer gets his hands on the carving knife (IDE), the documents gets replaced with objects (de-reified) and the conversations disappear (de-reified), and the knowledge of the process is replaced by global synchs and locks that become exclusive. Very few software projects have fully reified formal descriptions for document and conversation types.

Take a look at SWIFT or FIX. There are 10,000s of corporations exchanging messages with less problems and more scalability than the typical one team app discussed here. This is because they have both messages and conversations well defined.

Pat is right, but not new.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

14 Discuss

Educational Content

General Feedback
Bugs
Advertising
Editorial
InfoQ.com and all content copyright © 2006-2014 C4Media Inc. InfoQ.com hosted at Contegix, the best ISP we've ever worked with.
Privacy policy
BT