AppBackplane - A Framework for Supporting Multiple Application Architectures
Monday, March 25, 2013 at 10:36AM
HighScalability Team in Strategy, architecture, multithreading

Hidden in every computer is a hardware backplane for moving signals around. Hidden in every application are ways of moving messages around and giving code CPU time to process them. Unhiding those capabilities and making them first class facilities for the programmer to control is the idea behind AppBackplane.

This goes directly against the trend of hiding everything from the programmer and doing it all automagically. Which is great, until it doesn't work. Then it sucks. And the approach of giving the programmer all the power also sucks, until it's tuned to work together and performance is incredible even under increasing loads. Then it's great.

These are two different curves going in opposite directions. You need to decide for your application which curve you need to be on.

AppBackplane is an example framework supporting the multiple application architectures we talked about in Beyond Threads And Callbacks. It provides a scheduling system that supports continuous and high loads, meets critical path timing requirements, supports fair scheduling amongst priorities; is relatively easy to program; and supports higher degrees of parallelism than can be supported with a pure tasking model.

It's a bit much for simple applications. But if you are looking to go beyond a basic thread per request model and think of an application as a container where a diverse set of components must somehow all share limited resources to accomplish work, then some of the ideas may prove useful.

In case you are still wondering where the name AppBackplane comes from, it's something I made up a while ago as a takeoff of computer backplane:

A group of electrical connectors in parallel with each other, so that each pin of each connector is linked to the same relative pin of all the other connectors forming a computer bus. It is used as a backbone to connect several printed circuit boards together to make up a complete computer system.

Frameworks Encourage Poor Threading Models

Frameworks often force an application architecture. Your application architecture shouldn't be determined by a servlet or a database or anything but the needs of your application.

Sure, a single threaded approach may work fine for a stateless web back end. But what if you are doing a real application on the backend like handling air traffic control or a manufacturing process? Or what if creating a reply to a REST request requires integrating the results of dozens of different requests, each with their own state machine?

In these cases a single threaded approach makes no sense because a web page is just one of a thousand different events an application will be handling. All events are not created equal. Threads, queues, priorities, CPU limits, batching, etc are all tools you can use to handle it all.

It has a lot to do with viewing your application performance as a whole, instead of a vertical slice in time. With a multi threaded approach you can create the idea of quality of service. You can have certain work done at higher priorities. You can aggregate work together even though it came in at different times. You can green light high priority traffic. You can reschedule lower priority traffic. You can drop duplicate work. You can limit the CPU usage for work items so you don't starve other work. You can do lots of things, none of which you can do with single task that runs until completion.

Programmers commonly talk about upping the number of threads in a thread pool or tuning garbage collection or tuning memory limits as their primary scalability tactics at the application level, but they don't talk about priorities, deadlock, queuing, latencies, and a lot of other issues to consider when structuring applications.

For example, on an incoming request from a browser you want to setup the TCP/IP connection immediately so that the browser doesn't have to retry. Retries add load and make the user experience horrible. Instead, what you would like to do is set up the connection, then queue up the request and satisfy it later after having immediately setup the connection. But if each request is handled by a single thread then you can't implement this sort of architecture and your responsiveness will appear horrible as you run out of threads or threads run slow, or threads block other threads on locks, when in fact you have tons of CPU resources available.

Based on the source of the request you could assign the work a specific priority or drop it immediately.

You can also do things like assign priorities to different phases of a process. If one phase hits the disk you know that takes a lot of time relative to other in memory operations. As your application scales you decide if that phase of the work is more important and give it a higher priority or you can possible drop work elsewhere because you don't want to a request to fail once it has reached a certain processing point.

Consider if an application must process a UI request, servlet work, and database work. The work could be organized by priority. Maybe you want to handle the UI work first so it queues ahead. But if you keep getting
UI work it will starve the other clients so you give other clients a chance to process work. 

With your typical application architecture you don't have much control over any of this. That's what we'll address next, giving you control.

AppBackplane

As a note, in this post Hermes refers to a general messaging infrastructure that implements subscribe and publish functionality and remote method invocation. The target environment is C++ so the major compositional structure is a framework based on interfaces and virtual functions. Other languages would no doubt express the same ideas in their own way.

AppBackplane is an application framework that:

We want to make it easy for applications to select an architecture . It should be relatively simple to switch between 1-1, 1-N, M-N, event, and parallel state machine architectures. 

Conceptual Model

In general the AppBackplane approach combines the event scheduling with parallel state machines using a thread pool (1 or more threads).

The basic idea is to represent an application by a class that separates application behaviour from threading. Then one or more applications can then be mapped to a single thread or a thread pool.

If you want an event architecture then all applications can share a single thread.

If you want N applications to share one thread then you can instantiate N applications, install them into an AppBackplane, and they should all multiplex properly over the single thread.

If you want N applications to share M threads then you can create an AppBackplane for that as well.

Locking is application specific. An application has to know its architecture and lock appropriately.

Increased Parallelism Without Large Thread Count Increases

One of the key motivations behind AppBackplane is to be able to support higher degrees of parallelism without radical increases in thread counts. This allows us to do is have more peer-to-peer protocols without worrying about how they impact threading.

For example, if multiple applications on a node want to talk with 30 other nodes using a peer-to-peer approach, then 30 threads per application will be used. This adds up to a lot of threads in the end.

Using the backplane all the protocols can be managed with far fewer threads which means we can expand the use of peer-to-peer protocols.

Bounding Process Times

If an application is using an event or parallel state machine model it is responsible for creating bounded processing times.

This means that whoever is doing work must give up the CPU so as to satisfy the latency requirements of the backplane. If, for example, an application expects a max scheduling latency of 5ms then you should not do a synchronous download of 1000 records from the database.

How Modules are Supported

A Module is a way of looking at a slice of software as a unit that can have dependencies on other modules and that the modules must be brought up in some sort of dependency order. The state machine and complexity of the dependencies depends on your application. 

Whatever your approach, the backplane needs to work within the module infrastructure. Applications need to be dependent on each other yet still work over the same backplane.

We need AppComponents installed into the backplane to be driven by the backplane in accordance with the same state machine that brings up the entire application.

Dispatching Work to Ready Queues

Requests like Hermes messages come in from a thread different than the thread in the backplane that will execute the command. A dispatch step is required to dispatch the work to an object and then to a ready queue. Dispatch happens in the thread of the caller.

Dispatching in the caller's thread saves an intermediate queue and context switch.

If the dispatch can happen quickly then all is right with the world. Dispatching can be fast if it is based on the message type or data in the request.

Sometimes dispatching is a much more complicated process which could block the caller too long.

The strategy for getting around blocking the client is to queue the operation to a high priority '''digester'' object.

The digester object runs in the backplane and can take its time figuring out how to dispatch the work.

Objects Considered State Machines

Objects may or may not be implement as FSMs. An object's operations may all be stateless in which case it doesn't care. Using a state machine model makes it easier to deal with asynchronous logic.

Parallelism

Parallelism is by object and is made possible by asynchronous operation. This means you can have as many parallel operations as there are objects (subject to flow control limits). The idea is:

An application can have N objects capable of performing the same operation. The AppBackplane can load balance between available objects.

Or if an operation is stateless then one object can handle requests and replies in any order so the object does not need to be multiplied.

It may still be necessary to be able to interrupt low priority work with a flag when high priority work comes in. It is not easy to decompose iterators to an async model. It may be easier to interrupt a loop in the middle.

Per Object Work Queue

Without a per object queue we won't be able to guarantee that work performed on an object is performed in order.

The Actor queue fails because eventually you get to requests in the queue for an object that is already working on a request. Where do the requests go then?

In an async system a reply is just another message that needs to be fed to the FSM. There are also other requests for the same object in the queue. If the reply is just appended to the queue then that probably screws up the state machine because it's not expecting a new request. So the reply must be handled so that it is delivered before any new requests. This isn't that obvious how this should be done.

All Operations are Actions

The universal model for operations becomes the Action. The AppBackplane framework derives a base class called AppAction from Action for use in the framework.

All operations must be converted to AppActions by some means.

The reasoning is:

Requests are converted to actions in the thread queueing the request. The actions are added to the object that is supposed to handle them. The Action/conversion approach means that the type of a message only has to be recovered once. From then on out the correct type is being used. Parallelism can be implemented by the application having more than one object for a particular service.

Ready and Wait Queues

The ready and wait queues take the place of the single Actor queue. AppBackplane is the event scheduler in that it decides what work to next. AppComponents are multiplexed over the AppBackplane.

Handling Replies

An object can have only one outstanding reply so we don't need dynamic memory to keep track of an arbitrary amount of outstanding requests.

If an object is expecting reply the object is put on the wait queue until the reply comes in. The reply is queued first in the object's work queue. The object is then scheduled like any other object with work to do.

Client Constraints

Clients can not send multiple simultaneous requests and expect any order. Order is maintained by a client sending one request to a service at a time and not duplicating requests.

Steps to Using AppBackplane

Class Structure

   
 
            +-- ISA ----[Module]
            |
[AppBackplane]--HAS N ----[AppComponent]
            |
            +-- HAS 1 ----[AppScheduler]
       
   

[AppScheduler]-- HAS N ----[AppWorkerThread]
          | |
          | +-- HAS N ----[WorkQueue]
          |
          +-- HAS 1 ----[WorkQueue]


            +-- ISA ----[Module]
            |
[AppComponent]-- HAS N ----[AppObject]
            |
            +-- HAS N ----[AppEndpoint]

                          
[AppWorkerThread]-- ISA ----[Task]
  
[AppObject]-- HAS N ----[AppAction]

[AppAction]-- ISA ----[Action]

[AppEndpoint]

[MsgHandlerEndpoint]-- ISA ----[AppEndpoint,MsgHandler]
                   
[HermesImplement]-- ISA ----[MsgHandlerEndpoint]

[DbAdd]-- ISA ----[HermesImplement]

Hermes Request Processing Example

This is an example how application requests over Hermes are handled using AppBackplane. Note, there's a lot of adapter cruft to integrate an external messaging layer into AppBackplane. But it's quite common to use a third party messaging library, so we have to have a way to take a blob of bytes over the wire and turn it into a typed message and then determine where the message should be processed. With a messaging layer that knows about AppBackplane it can be much cleaner.

Scheduling Algorithm

AppBackplane implements a scheduling layer on top of OS thread scheduling. An extra scheduling layer is necessary to handle fairness, low latency for high priority work, and throttling in a high continuous load environment.

The scheduling algorithm is based on:

Backplanes are Not Organized by Priority

It is tempting to think of backplanes as being organized by thread priority. This is not really the case. Any application has a mix of work that can all run at different thread priorities.

You probably don't wan't to splat an application across different backplanes, though technically it could be done.

The reason is backplanes are more of a shared data domain where latency contracts are expected to be followed. Different backplanes won't share the same latency policies, lock policies, or ready queue priorities and quotas.

Thus backplanes can't be thought of as able to cooperated with each other.

CPU Throttling

CPU throttling is handled by the scheduler.

Request Throttling

Requests are throttled by having a per component operation limit. When a component reaches its limit and a new operation comes in then the component is asked to make room for new work, if the component can't make room then the request is failed with an exception.

The client can use the exception as a form of back pressure so that it knows to wait a while before trying the request again.

Priority Inheritance for Low Priority Work

Low priority work should have its priority raised to that of the highest work outstanding when the low priority work is blocking higher priority work that could execute. The reasoning is...

Work is assigned to threads to execute at a particular priority.

Thread priorities are global. We must assign thread priorities on a system wide basis. There doesn't seem to be a way around this.

Each backplane has priority based ready queues that are quota controlled. High priority work that hasn't met its quota is executed. By priority we are talking ready queue priority, not thread priority. Thread priority is determined by the work.

Ready queue priorities and quotas are primarily determined by the backplane. They are ultimately constrained by a CPU limit on the backplane.

Lower priority work is scheduled when there is no higher priority work or higher priority work has met its quota.

When lower priority work has been assigned to a thread higher priority work can come in.

The lower priority work's task may not be scheduled because a higher priority task is executing elsewhere in the system. This causes the lower priority work not the be scheduled and to not get a chance to run. In fact, it can be starved.

The lower priority work is causing the higher priority work not to execute, even if the higher priority work would run at a task priority higher than the currently running task that is blocking the lower priority work from running.

By upping the task priority of the lower priority work's task to that of the higher priority work's task priority we give the lower priority work a chance to run so it can complete and let the higher priority work run.

The lower priority work can run to completion or it can use global flags to know if it should exit its function as soon as possible so the higher priority work can run.

The priority inheritance works across backplanes so high priority work in any backplane will not block on lower priority work in any other backplane. The higher priority work is present flag is global.

Even if the lower priority work doesn't not give up the critical section immediately, just giving it a chance to run will make it so the higher priority work can get scheduled sooner.

Backplane Doesn't Mean No Mutexes

Mutexes can still be used within a backplane, but they should not be shared with threads outside the backplane because there can be no guarantees about how they are used.

Applications inside a backplane should be able to share mutexes and behave according to a shared expectation of how long they will be taken and when they will be taken.

Fair sharing is implemented by a max CPU usage being assigned to each backplane.

 

Yep, it's complicated.

A lot of the complication has to do with mapping different work input sources (messages, timers) into a common framework that can execute in an AppBackplane. Some form of this has to be done unless you really want have multiple threads running through your code without any discipline other than locks. That's a disaster waiting to happen.

Other complications are the typical complexity you have with decoding and routing messages to handlers. This is always necessary however.

There's complication around thinking about dependencies between components and the different states your application can be in, like start, initializing, primary, secondary, down. A lot of this is usually hidden in an application with lots of hacks to get around the weird dependencies that grow over time. I think it's better to make dependencies a first class component of your application architecture so you can gain some power out of it instead of it being a constant source of bugs.

And then there's the actual scheduling, which is complicated, but it does allow you to tune what work gets done when, which is the point of at all as you start trying to handle  more and more load while minimizing latencies and guaranteeing SLAs. 

It's something to think about anyway.

Article originally appeared on (http://highscalability.com/).
See website for complete article licensing information.