/dev/null

Distributed Systems as Organisms

I have been having a long converstation by phone and email with Bill Venners of Artima regarding distributed systems. Over the past few years, I have often talked about how distributed systems have evolved from being a "collection of introverted servers" to being a "social organism", but I've never taken the time before to write it all down. What follows is my explanation to him:

There are two vastly different approaches to distributed software, which I can sum up as traditional and organic. In a traditional distributed system, each server, each process is an isolated unit, like a single-celled organism. It exists as an independent unit that must fend for itself within its environment, and must always assume the worst, because it is the last -- likely the only -- line of defense for the responsibilities that it carries. For example, it must assume that failure to communicate with another part of the distributed system results in indeterminable conditions, such as in-doubt transactions. As a result, it must consolidate those indeterminate conditions into its own condition, likely preventing it from continuing processing. One would expect this in any two-phase commit system responsible for deterministic outcomes, when the system experiences an unknown outcome in any transaction branch.

Traditional systems utilize "recovery" to achieve deterministic results even when servers fail. The measurement of the likelihood of failure is referred to as MTBF, or Mean (average) Time Between Failure. More importantly, though, is the MTTR, or the Mean Time To Recovery. In a traditional system, the outcome of an in-doubt transaction branch is unavailable until the server on which the branch existed is fully recovered.

Clustering is a proven approach to resolving such dilemmas by significantly reducing -- almost to the point of eliminating -- recovery time. The clustering approach was made popular first in mainframe architectures, and eventually it bubbled down to mid-range UNIX systems. Server redundancy with dedicated "clustering interconnects" allowed a second stand-by server to stay in lock-step with the primary server, allowing the second server to immediately stand in for the responsibilities of the primary server in the event that the primary server failed.

Today, what we refer to as "clustering" is significantly different, although it is intended to achieve the same result. For example, in modern architectures such as Java EE application servers, clustering refers to very high level interconnects, such as TCP/IP sockets, that allow servers to stay in virtual lock-step, and for one server to detect the failure of another server. Conceptually, clustering allows failure to be handled without recovery, by having redundant copies of the state (such as a transaction log) that would otherwise have to be recovered.

The two-server hardware clusters and the more modern software clustering implementations are the origin of what I refer to as "organic systems", which represent multi-cellular organisms that are designed to survive the loss of individual cells. In other words, a distributed system is no longer a collection of independent organisms, but is itself an organism composed of any number of servers that can continue processing -- without any loss of data or transactions -- even when server failure occurs.

This does require a fundamental adjustment in the assumptions behind distributed systems. In particular, in a traditional distributed system, the loss of communication to a particular server would cause all other servers that were communicating with that server to wait for the recovery of that server's responsibilities, whether by server migration, service failover, or actual repair (e.g. reboot) of that server.

On the other hand, in the case of an organic system, the organism is always prepared for the death of any cell, and is never dependent on the survival of any particular cell. In such a system, if a particular server dies, all of its responsibilities can be handled by the other similar servers, and all of the in-flight transactions can be re-routed from the dead server to those other servers. To accomplish this, each state change and each in-flight transaction must be accomplished on at least two servers, just as it is in the well-known clustered hardware implementations. The difference, though, is that an organic system is not limited to only two servers, and it can organize itself as an increasingly resilient mesh of servers, where the failure of any server has a smaller and smaller effect on each other server as the number of servers increases.

No longer is "recovery" the primary mechanism for re-establishing the availability of the system when a server fails. Instead, the technical challenges are the rapid detection of server failure and the need to isolate the failed server from the overall distributed system. I will attempt to explain these two challenges in detail, and why they are so fundamental to the correct and continuous operation of an organic system.

First, when a server fails, it is rather unlikely to have predicted its own demise, and as a failed server, it is also unlikely to be able to communicate its own failed condition. The responsibility for the detection of server failure therefore falls to the organism itself, which is composed of all of the surviving servers. The algorithms for determining server failure are referred to as "death detection algorithms", and typically use a combination of error indications and statistics to ascertain server failure beyond a reasonable doubt. When a server has been determined to have failed, the other servers then assume the responsibilities that the failed server had, and processing of those responsibilities continues without loss of data or in-flight transactions.

A serious problem, known as the "split brain syndrome," occurs when the failed server may not be aware of its own demise, and it may attempt to continue processing after the other servers have determined it to have failed. This is the role of isolation, which means that the organism is fully aware of the failure of the server, and isolates that failed server from the rest of the organism. This accomplishes two things: First, it prevents the failed server from corrupting the state of the system, because the system is the organism and the organism is the system. Second, it provides the failed server with an unambiguous sign that it (the failed server) has indeed been isolated from the organism. Since the organism is dynamic, growing and shrinking as necessary, the failed server can re-join the organism, but it can only re-join once it understands that it failed, and once it agrees to join with no pre-existing assumptions, just as if it were a new server.

When external resources, such as a database, are also affected by the processing of the organism, the isolation must also prevent a failed server from affecting those resources. To accomplish this, a failed server must respect its isolated state, and it does so through the use of a quorum. A quorum is the defined minimum size for an organism, which could be defined as an absolute number of servers, as the minimum number of servers necessary to provide a particular quality of service or capacity, or as a percentage of the recent size of the organism (before the server was isolated from it). When a server is isolated from the organism, it can form its own single-celled organism (composed only of itself), or it can even form a small multi-celled organism in some split-brain scenarios. In either case, its failure to achieve quorum will cause it to restrict its affects on external resources, thus ensuring that failed servers do not cause damage to the state of either the surviving organism or the external resources that the surviving organism depends on and affects.

(A more complex quorum and continuation logic is used for failover of entire datacenters, in which a split brain could allow either datacenter to provide its own quorum, yet only one datacenter must continue to process.)

In summary, the failure of a server is no longer an exceptional condition, and it affects neither the availability of the overall system nor the state of the data and transactions being managed by the overall system. Thus, an application may still have to deal with the potential for failure, but not the failure of a particular server. Instead, an application must deal with the failure to achieve quorum; in other words, an application must deal with the fact that it is on the server that failed, and in exchange, it no longer has to worry about the failure of some other server.

There are several additional considerations that should be addressed. First of all, a distributed system cannot maintain its availability in the event of a complete network failure; this can be addressed by eliminating single points of failure in the network infrastructure itself. Second of all, a distributed system cannot maintain its availability if all of the servers fail at once, which can happen if the servers lose power; this too can be addressed through the use of battery backups, generators and redundant power systems. However, applications should be built with an understanding of both of these risks, and this leads to the last goal of an organic system: Recoverability.

In the case of a server failure in a traditional system, each server was its own single-celled organism, and each server had to be able to recover itself, for example by using a transaction log. In the case of an organic system, the organism must also be able to recover itself. It typically accomplishes recovery by relying on long-term recoverable storage, such as is provided by relational database systems (RDBMS) to act as its system of record. Recoverability is accomplished by reloading the state of the system from its recoverable storage, and using the completion of the recovery as a pre-requisite of making the organism available to process new requests.

If the benefits of an organic model sound familiar, then you're probably already using the world's most innovative distributed system. If you're still struggling with traditional exception-based or recovery-based approaches to distributed systems (e.g. CORBA, JINI, RMI), then you have my deepest sympathy, but it's not too late to switch (e.g. download, wiki, javadoc, forums).

Posted at 10:00PM Aug 13, 2006 by Cameron Purdy in Technology  |  Comments[30]