The Abstraction Trap

Abstractions exist so that we can take shortcuts when building stuff.  They readily implement some of the messy necessities behind things like, for example, network access in distributed systems – but too often they’re used as an alternative to in-depth understanding rather than a reusable way to render a system.

Staying with our distributed system example; understanding the latency between nodes, synchronisation and blocking (and their impact on concurrent work), transport overhead and reliability, and what the behaviour will be if you don’t hear back from the remote service are all critical to the success of a complex project.  Without having to explicitly program these things it’s too easy to just drop something into a pipe or throw it at a web service and merrily continue on with life having never even considered those neatly masked complexities.  Until go live.

It’s the difference between something that functions on the bench and something that will work reliably in real life’s volatile conditions.

On the infrastructure side I see the same pattern emerging with virtualisation – we’ve now got this nifty and easy to use platform which takes us another step further away from the metal.  On the plus side we can stamp out more nodes really quickly and move instances of a server around from hardware to hardware to accommodate growth and failure, but on the minus side correlating what’s happening on pretend CPUs with a real CPU and oversubscribing hosts makes capacity planning a degree harder.

All these environments are designed to abstract things away from us so that we don’t have to worry about them or recreate them every time – but that’s not the same as saying we no longer need to understand the basics of what happens under the hood.

You’ll always have better product when your engineers have the low level knowledge (primitives and patterns) needed to design and build systems and understand how they will behave.  That’s different to simply knowing how to drive the tools.

Availability or Control?

In the web business, we usually consider availability to be paramount - and given that motivation, we're getting pretty good at things like graceful degradation and partial failure. But now that you've pulled your system apart and neatly isolated all the features, how do you cope with the situation where no service is preferable to partial service?

This can be true. Consider, if you will, a trading system operated by a team of risk managers. You have built the system to be fault tolerant and allow partial failures - and this usually works out great - but what happens if a failure in the infrastructure or application results in the risk managers no longer being able to administer the system? It's still running publicly (thanks to you awesome failure isolation) so customers are still buying and selling. You cant change your prices and respond to changing market conditions - uh oh - exposure. What do we do?

One answer is a word we don't like - especially if we just built a reasonably decoupled system - dependency. Yuck, but there is no shame in creating some intentional dependencies that support the business rules. If you never want to execute trades unless you can manage your position, then what is the advantage to running the trading system without the liability tool? Nothing - if anything it's an undesirable risk.

So draw up some service dependencies, or make the applications depend on their monitors at runtime. It might not appeal to how we'd like to run the system, but the truth is it accurately reflects how we'd like to run the business.

What Your Network Guy Knows

So you're getting into distributed systems; maybe you've got some real scalability issues on the horizon, or perhaps you want to better isolate failure, or be able to cope with more concurrent change in the system. So how do you do this webscale thing then?

Time for some homework. Listening to some vendor pitches, maybe reading some books, or getting an expensive consultant or two in for a while (I'll take your money from you if that's what you want) might possibly do it. But before all this gets out of hand, did you realize you're probably sitting right next to a distributed systems fountain of knowledge? You already have someone, right there in your team, who has spent their entire career working with the largest eventually consistent multi-master distributed systems in the world - the trick is they might not even know it themselves - and that someone is your network guy.

Let's test this assertion against a couple of technologies that network engineers deal with every day, and look at what we can take from them into our distributed systems thinking.

How about something fundament - routing protocols. Networking gurus have a small army of acronyms at their disposal here; OSPF, EIGRP, IS-IS, BGP, and the sinister sounding RIP. These are essentially applications that run on network devices (and sometimes hosts themselves), map out the network topology, and provide data for devices to make packet forwarding decisions.

So what can we import from this technology?
1. Partitioning - networks are broken down into manageable chucks (subnetworks) which scope load (broadcasts), ringfence groups of systems for security, and limit traffic across slow and expensive links.
2. Scalability - routing protocols allow massive global networks to be established by summarizing contiguous groups of networks again and again, and ensuring any node can establish end-to-end connectivity without having to understand every single path in the network (just a default route).
3. Failure isolation - subnets are bordered by routing protocols, which form a natural boundary to most forms of network malarky. In the event that a network becomes unpredictable (flapping), some routing protocols are able to mark them down for predetermined time, which aids in local stabilization and prevents issues spilling over into healthy networks.
4. Self healing - when a failure in a network or a link between networks occurs, routing protocols observe the problem (by missing hellos or interfaces going down) and take action to to reestablish reachability (work around the problem using alternate paths etc). Each node will recompute it's understanding of the networks it knows how to reach, learn who it's neighbors are and the networks they can reach, and then return to business as usual via a process called convergence (this is a really simple study in eventual consistency and variable consistency windows).
5. Management - for the most part, networks separate their control messages from the data they transport. A good practice, especially when combined with techniques like QoS, because it significantly reduces the risk of losing control of the infrastructure under exceptional load conditions.

Now let's look at something application layer - DNS. This should be a somewhat more familiar tool (or you're kind of reading the wrong blog) and we touch it quite regularly but probably don't appreciate what goes on in the background. At it's most basic level, DNS is a client/server system for providing a mapping between human-readable hostnames and machine-friendly IP addresses. Oh but it's so much more...

So what can we import from this technology?
1. Partitioning - DNS is hideously, frighteningly big, there are hundreds of thousands of nodes in this system, from the dozen or so root servers all the way down to the corporate internet access edge servers. It is a good example of dividing up a problem; to find us you'd work right to left through a fully qualified domain name, starting with the "." (root), we're in the "com" container (hosted by a registrar), then the "betfair" container (hosted by us), and finally you'd get back some data from a record matching "www" and arrive at our place.
2. Scalability - did I mention DNS is big? DNS uses a classic combination of master/slave nodes and caching on the client and server side to scale out. At the corporate edge, DNS proxies resolve addresses on behalf of internal clients and keep answers in a local cache, ISPs and those who run their own zones keep a number of slaves (many read only) and spread queries out amongst them, and finally an expiry timestamp (TTL) is set on query results permitting client side caching.
3. Resilience - clients can be configured with a list of servers, which they will cycle through should they receive no answer. Additionally, the DNS protocol is stateless, making it easy to move servers around hot and load balance using simple, lightweight algorithms.
4. CAP - DNS definitely prefers availability over consistency, the window for an updated record to be propagated around the internet being ~24hrs in most cases. It's also highly tolerant to network segmentation, individual servers being happy to live separated from the rest of the DNS infrastructure for long periods of time, answering queries, and then catch up with all the changes in the zones they host once connectivity is reestablished.
5. Operations - the hierarchical way the namespace is organized is perfectly matched to how authority is delegated. If you're going to have a massive system spread around the globe, you've got to think about how you're going to operate it, and the DNS model for this is based on allocating administration with ownership. This gives complete flexibility and control to namespace owners without risking the integrity of the system as a whole and let's us operate the biggest distributed system in the world without employing the biggest IT team in the world.

So buy your network guy a coffee. Ask him how his world works. If you can draw the philosophical parallels, it might be the most valuable couple of hours you've spent in ages.

Oh and by the way - distributed systems are all about the network, so you're going to need a friend here anyway...

Parallel vs Distributed

The difference between parallel computing and distributed computing is another important piece of theory to keep in mind when designing a system. The concepts are significantly different, but far from mutually exclusive - for example you can run a number of parallel computing tasks on different nodes inside a distributed system.

The confusion, if it exists, arises from what the parallel and distributed concepts share in common - the division of a problem into multiple smaller units of work that can be independently solved with a degree of autonomy.

So what makes distributed distributed and parallel parallel? Both involve doing smaller units of processing on multiple separate CPUs, thusly contributing to a larger overall job. The key difference is in where those CPUs reside (and note that we'll treat "CPU" and "core" as synonymous for our purposes today). Simple answer:

Parallel is work divided amongst CPUs within a single host.

Distributed is work divided amongst CPUs in separate hosts.

How you break down work so that parts of it can be done concurrently, whether parallel or distributed, is largely governed by a single constraint - data dependency. Way back in the day a systems architect at IBM came up with a set of guidelines for assessing the degree to which this can be achieved, and a way to estimate the maximum benefit it will deliver. This simple rule bears his name today.

The key design considerations around parallel or distributed processing are in how you tackle this data dependency. In parallel computing, you need to use synchronization and blocking techniques to manage the access to common memory by the various threads you've split your problem up amongst. Solving the same issue with distributed computing simplifies your memory/thread management within each host, but you put the complexity back into state tracking, cluster management, and data storage.

It's arguably fair to say that, as a rule, parallel computing is more performant and distributed computing is more scalable. When crunching through a lot of work via many threads in one box, everything is done at silicon speeds, your only physical throttle being memory bandwidth and the pins between cores. The downside here being a hard limit to the amount of work you can do concurrently, which pretty much maps to the number of cores you can fit into your system - and scaling that up gets pricy. Doing the same work in a distributed system faces only theoretical constraints to how much work can be done concurrently, the question being how scalable your network and cluster management is, and it's usually cheap to add more systems and hence cores. The downside here being latency, as messages need to traverse networks many times slower than internal system buses, and of course you need a process to collect and reassemble results from all your nodes before you can confidently write your answers down to disk.

Like most technology, there are problems to which one is more suitable than the other, and also like most technology, there are many times when it is simply a matter of taste. Some of us are from big box school and feel more comfortable managing threads and memory space within a vast, single environment. Some of us are from cloud school, at rest amongst a dynamic mesh of cheap, disposable nodes, investing ourselves in the communications fabric between them.

The Law of Conservation of Complexity

The law of conservation of complexity states that there is a minimum amount of trouble you need to go to in order to achieve a certain outcome. You can always make it harder, but you can never simplify beyond a certain minimum level without compromising the result. Imagine a system with 3 components all of which are at their least complex, by further simplifying one component of this system you do not reduce the minimum overall amount of complexity required, because another of the components must become more complex in compensation.

A couple of real life examples:

Something customer facing. Let's say we're selling car parts online and we need to check availability from manufacturers before we accept orders, and we'd quite like to do this in real time so we don't set our customers expectations wrongly. We could do this in the back end by making complimentary calls from our application to the manufacturers inventory system as we receive requests from our customers. This might be a smart solution because we'd be able to do some short-term caching of results for popularly looked-up items. We could do this in the front end by getting our users browsers to fetch the stock levels directly from the manufacturers website or (if we're lucky) API. This might be a smart solution because it would reduce the load our application takes.

So we can simplify the front end at the expense of the back end, or we can simplify the back end at the expense of the front end. Either way we can't escape the need to make that request somehow without changing the functionality of the system [being aware of stock levels].

Something platform. Let's say we've got a distributed application that we need to provide strongly consistent data storage for. Since consistency is one of our requirements, and assuming we don't want to centralize the system, we need a way to make sure that when we write to a piece of data in one place, a contradictory update is not being made in another. We could do this on the storage side, by using a distributed locking algorithm or electing certain partitions to be the designated 'writer' for certain data items. This might be a smart solution because it's more portable. We could do this in the application by making the storage client responsible for locking every copy of a datum, or sending a message to all it's peers advising them of updates it wants to make. This might be a smart solution because it simplifies our data administration.

So we can simplify the application at the expense of the storage system, or we can simplify the storage system at the expense of the application. Either way we can't escape the need to govern writes somehow without changing the functionality of the system [keeping consistent data].

Just as energy is never lost, the minimum amount of complexity an entire system must have to achieve its goals can never be reduced, it can only be moved around.

Hot Maintaining Communication Systems

A while ago Joe Armstrong posted a few simple ideas for hot maintenance on his blog (and I heart hot maintenance).  It starts from a position of a fair few assumptions, such as your clustering service being OK with nodes arbitrarily joining and leaving, and any central data or state storage being OK with heterogeneous nodes connecting to it.  But hey - good design principles anyway, so for arguments sake let's just call those assumptions validated...

Someone posted a very relevant question on the comments - what about upgrades that require changes to the protocol between nodes?  This is a vital issue to address, because if you can't come up with a good solution for hot maintaining your communications glue, you have a limited amount of overall hot maintenance you can practically achieve.

The answers to this question are as varied as there are design patterns, but using the same set of assumptions we read into Joe's original post, here are 3 techniques that should be fairly portable:

Dual-headed.  If you're changing transports you can introduce nodes that communicate using both protocols.  You duplicate traffic (if you do it fairly unscientifically) but it's viable for a rolling upgrade.

Versioned interfaces.  If you're changing the message format, version the messages.  This will let you gradually move nodes onto the new build and give you some added benefits like A/B testing, faster future upgrades and rollbacks.

Translation gateway.  So far we've assumed a group of nodes in a single location.  For a distributed system with collections of nodes in distinct places, a gateway that speaks protocol 'old' on one side and protocol 'new' on the other might work best, letting you upgrade cluster-by-cluster without taking down the whole system.

To get the right answer for any given system the first thing to do is study the communication pattern - how much is management vs. service, what is node to node vs. node to DB, and how much crosses geographical locations?  This gives you your architectural options, beyond which you just need to keep your state tracking heterogeneous, your data partitionable, and (to make your own life easier) your inconsistency window as long as the business rules allow.

CAP

A couple of months ago I wrote a little about the architectural concepts ACID and BASE, two descriptions of two very different systems.  In a company like ours, the business (and it's pseudo-techie product managers) fail to recognize the mutual exclusivity involved in various combinations of ACID and BASE, desiring the benefits of both concurrently.  This is a pretty vast comprehension chasm to cross without a good tool to help us explain the tradeoffs - enter Eric Brewer's CAP theorem.

CAP stands for Consistency, Availability and tolerance to network Partitions and works a little like the great software triangle (scope, cost, time) in that you may only have 2 of the 3 properties in any given implementation.  Note that we talk about an implementation here because it is perfectly valid, and in many cases quite sensible, to build different features within a single system to different CAP tradeoffs.

Consider a system with high availability requirements.  From this starting point you may chose to design in strong consistency (the data is always the same from any perspective) but you will not be able to distribute the system across any network boundary.  Your other choice would be network tolerance (it will run nicely geographically separated) but you will have to accept a window of inconsistency in both normal and failure modes.  If you have the option of doing away with your availability requirement then you might build something partitioned and consistent but you'll always have to fail to guarantee consistency through any network event.

Trying to keep a widely distributed data set highly available and 100% consistent at any given moment will bring you up against certain laws of physics.  Good luck with that.

Isolating Failure

A few weeks ago we launched our Sportsbook, our flagship risk-taking product, into the Italian market.  It's a very strategic product both because of how it fits into our international expansion plans and because of how it's built.  We intended for this system to get big fast so we built it wide - distributed, message based and API driven.

Just days after launch the one thing we can always guarantee will happen happened - part of the system failed.  Our bet placement engine hung [bad news] but the rest of the system continued to work [good news] so while our customers couldn't place any bets, they could hit the site, view the markets, register, login, deposit, manage risk... everything else basically.  This kind of failure scenario would see a lot of more monolithic web systems firing out 404s or 500s in the blink of an eye.

This is exactly the benefits you look for when you build decoupled functionality and minimize dependencies, consciously seeking to isolate features from each other.  The next step for us is automatic detection and repair - working to minimize human intervention.

A Better Way to Say 'State'

I wrote a little bit about state in this post and recently came up with a much simpler description.  Here goes:

Tracking state is necessary when a part of my application needs to make a decision based on your previous activity.  That previous activity could be a trail of things you did along the way (collected items in your basket) or a more binary prerequisite test you'll either pass or fail (logged in or not).

Something closely related to state is session, and I picked this up from Jeff Atwood while I was trawling around for something totally unrelated.  I think it's one of the best plain-English explanations I've read on the topic and, since he explains it better than me, I'd encourage you to take a look.

So that's all pretty simple but, as I always say, the basics are what everything's built on - and where this starts to get interesting is when you're building distributed systems.  It's easy to partition stateless functionality but what do you do when you need to track state or keep persistent session information?  Well that's easy, you share your state from a centralised place - that'll see you through for a little while but what about when you need to scale that horizontally?

There are a lot of systems already doing this (AFS, DNS, LDAP, NFS) but there are no standard solutions for distributed state management, these systems all implement their own unique consistency and conflict resolution methods.  We're now seeing a lot of webscale businesses hitting these scalability walls - requirements are forcing the production of customized infrastructure services like Google's Bigtable + Chubby and Amazon's S3.  We're balancing on the edge of this wall ourselves and given what a difficult but rewarding challenge it is, I feel fear and anticipation in equal measure!

ACID and BASE

Here's a couple of classic ideas that are still good distributed system thinking exercises today - the ACID/BASE concepts are essentially a pair of acronyms describing two opposing extremes of system attributes.  ACID is a fairly established computer science principle from way back in the DB-centric days (it's what school taught us was important to systems) and BASE is what more and more of today's systems are being forced towards through web scalability problems.  Let's take a look at both:

ACID

ACID stands for Atomicity, Consistency, Isolation and Durability and usually describes the behavior of a tightly bound, data centric system.

DB people will have no trouble with atomicity, this is the property of a database operation which offers the "all or nothing" guarantee - for example we won't credit your account if we can't debit your credit card.  Works on the principle that you'd rather not do one without the other (like our banking example).

Consistency is a massive topic on its own but if forced into a one-liner I'd say it's a measurement of identicalness for any given data set no matter where or how many times it appears in a system.  Assuming ACID consistency means strong consistency (and from context that's a safe bet) an example here is an East-West replica set where if you change your password via a client of one DB our system dictates that change must appear in our other DB as instantly as the speed of light allows - because no matter when or where that unit of data is observed from every copy must always be the same.

The next property, isolation, can almost be described as locking (but can't the whole thing?).  It is the process by which data being updated is hidden away from other processes/nodes until it whatever value-changing operation is completed and the changes are committed.  Isolation ensures integrity (for example I can't spend the same money twice from my back account no matter how quickly I put my card in another ATM) but is the enemy of concurrence.  A lot of people think durability is about availability and it kind of is, just not the sort of availability I settle for.

Durability is that property of a data store that promises to keep your information safe - in other words once the system has satisfied atomicity you will always be able to recall that data accurately.  This is usually about writing to persistent storage and journalling changes in a transaction log.  If, for example, the disks that the database files reside on are destroyed then I should be able to replay said logs against my most recent copy (do backups or die) and end up right back where I was.

BASE

BASE stands for Basically Available, Soft state and Eventual consistency and describes the attributes of a loosely coupled system valuing availability and tolerance over strict consistency and isolated operations.

Basically available is recognizing that the availability of a system as a whole should never be the same as the availability of any individual node/feature/service within that system - your system should survive the death of it's component parts.  It's saying we never try to guarantee that a given data store will always be here (as ACID assumes) we just build a lot of tolerance into the system so that there is usually enough of it alive at any given point in time to present something usable.  More than that, basic availability is about saying we'd rather deal with conflict resolution and versioning issues than pay a scalability and availability price with isolation.

State [in this context] is essentially whether we're required to track, remember and somehow use preceding events in a flow of activity (stateful) or whether we can provide the right responses to requests without knowing what the immediately preceding activities and their results were (stateless).  Stateful operations tend to be unique to individuals (or groups); for example account management - you want to make sure a user has successfully logged in before you let them edit their address or payment details.  Stateless operations tend to be wider in scope; for example pushing out price feeds or updating a product catalogue - you usually want everyone to see the same thing no matter where they are.  Traditional state management is about recording a series of values in a centralized storage point so that other processes or nodes can retrieve it whenever they need to make decisions based on what you did before.  Soft state is about pushing back the use of state until the last possible moment it's needed and using techniques like leasing/refreshing and partitioning to reduce dependencies created by a single source of truth.

Now we're left with eventual consistency which says that when a distributed/replicated item of data is created or changed in one location it will be changed everywhere else after a period of time rather than immediately in ACID's strong consistency model.  Continuing with our product catalogue example you'd want to have that set in a few locations so that it was close to where your customers were (performance) and you can be sure could always show a list/search result (availability).  When you add a new iron to your homeware section does it really matter if it doesn't show up in every location for 10 minutes?  Of course the benefits are based on the premise that we'd rather have a quick answer that isn't 100% up to date than a slow one that is (or no answer at all).

So...

Webscale systems are moving along towards BASE as we realize how valuable a commodity availability is and how difficult it is to scale systems to meet the demand the Internet creates.  We're suddenly faced with challenges that are impossible (or grossly unprofitable) to meet with traditional thinking and are forced to start making tradeoffs that just don't match ACID - relax consistency to buy availability?  Relax isolation to buy scale?

One last thing that's worth noting is different parts of the same system can occupy a different point along the ACID/BASE continuum.  Thinking about that iron we added to homeware we might not be bothered about it instantly showing in every replica of our catalogue (eventual) but what if we realise we made a mistake on the price and we're selling them for much less than they cost us?  We might want that sort of update to be immediately pushed out super quick (strong).

The Great Divide

I'm into availability at the moment, so much so that I'm leading an organization-wide change initiative that targets cultural, technical and process habits (busting established, forming new) in order to deliver a more consistent experience.  Our goal is to always have something to offer our customers regardless of any maintenance we're performing or failures we're experiencing.

This is how I discovered The Great Divide.  The namesake of this post is that gap between the infrastructure and the software - because of which we offer our product to our users much less often than we could.

Here is how it works:

We've got a pairs of firewalls that can fail over while maintaining session state.  We've got tiers of load balancers that can reroute traffic around down network devices.  We've got clustered databases that can move active systems between nodes in a couple of minutes.

But guess what else we've got?

We've got applications that lose session information without contiguous sequence numbers.  We've got applications that cant match users to activity if their traffic suddenly comes from another IP address.  We've got applications that depend so heavily on their databases that death occurs within a few seconds of separation.

Damn.

You don't get any partial credit in product uptime - your customers will not award you a bonus point if your site is down but your servers are up.  If they cant log in they cant log in, if they cant place orders they cant place orders; they're quite a binary bunch.

For us product = infrastructure + software + operational know-how to run it.  We need to stop worrying about server/network availability and start worrying about product availability - because guess what, that's what our customers are measuring us on.

Close that gap and let your customers see the benefit of those cool devices.