text:
Marc Brooker's Blog 2019-08-12T15:56:56+00:00 http://brooker.co.za/blog/ Marc Brooker firstname.lastname@example.com Kindness, Wickedness and Safety 2019-08-12T00:00:00+00:00 http://brooker.co.za/blog/2019/08/12/kind-wicked
Kindness, Wickedness and Safety

We must build kind systems.

David Epstein's book Range: Why Generalists Triumph in a Specialized World turned me on to the idea of Kind and Wicked learning environments, and I've found the idea to be very useful in framing all kinds of problems.1 The idea comes from The Two Settings of Kind and Wicked Learning Environments. The abstract gets right to the point:

Inference involves two settings: In the first, information is acquired (learning); in the second, it is applied (predictions or choices). Kind learning environments involve close matches between the informational elements in the two settings and are a necessary condition for accurate inferences. Wicked learning environments involve mismatches.

The authors go on to describe the two environments in terms of the information that we can learn from L (for learning), and information that we use when we actually have to make predictions T (for target). They break environments down into kind or wicked depending on how L relates to T. In kind environments, L and T are closely related: if you learn a rule from L it applies at least approximately to T. In wicked environments, L is a subset or superset of T, or the sets intersect only partially, or are completely unrelated.

Simplifying this a bit more, in kind environments we can learn the right lessons from experience, in wicked environment we learn the wrong lessons (or at least incomplete lessons).

From the paper again:

If kind, we have the necessary conditions for accurate inference. Therefore, any errors must be attributed to the person (e.g., inappropriate information aggregation). If wicked, we can identify how error results from task features, although these can also be affected by human actions. In short, our framework facilitates pinpointing the sources of errors (task structure and/or person).

This has interesting implications for thinking about safety, and the role of operators (and builders) in ensuring safety. In kind environments, operator mistakes can be seen as human error, where the human learned the wrong lesson or did the wrong thing. In wicked environments, humans will always make errors, because there are risks that are not captured by their experience.

Going back to Anatoly Dyatlov's question to the IAEA:

How and why should the operators have compensated for design errors they did not know about?

Dyatlov is saying that operating Chernobyl was a wicked environment. Operators applying their best knowledge and experience, even flawlessly, weren't able to make the right inferences about the safety of the system.

Back to the paper:

Since kind environments are a necessary condition for accurate judgments, our framework suggests deliberately creating kind environments.

I found reading this to be something of a revelation. When building safe systems, we need to make those systems kind. We need to deliberately create kind evironments. If we build them so they are wicked, then we set our operators, tooling and automation up for failure.

Some parts of our field are inherently wicked. In large and complex systems the set of circumstances we learn from is always incomplete, because the system has so many states that there's no way to have seen them all before. In security, there's an active attacker who's trying very hard to make the environment wicked.

The role of the designer and builder of systems is to make the environment as kind as possible. Extract as much wickedness as possible, and try not to add any.

Footnotes

 The book is worth reading. It contains a lot of interesting ideas, but like all popular science books also contains a lot of extrapolation beyond what the research supports. If you're pressed for time, the EconTalk episode about the book covers a lot of the material.

 When Redundancy Actually Helps 2019-06-20T00:00:00+00:00 http://brooker.co.za/blog/2019/06/20/redundancy
When Redundancy Actually Helps

Redundancy can harm more than it helps.

Just after I joined the EBS team at AWS in 2011, the service suffered a major disruption lasting more than two days to full recovery. Recently, on Twitter, Andrew Certain said:

We were super dependent on having a highly available network to make the replication work, so having two NICs and a second network fabric seemed to be a way to improve availability. But the lesson of this event is that only some forms of redundancy improve availability.

I've been thinking about the second part of that a lot recently, as my team starts building a new replicated system. When does redundancy actually help availability? I've been breaking that down into four rules:

The complexity added by introducing redundancy mustn't cost more availability than it adds.

The system must be able to run in degraded mode.

The system must reliably detect which of the redundant components are healthy and which are unhealthy.

The system must be able to return to fully redundant mode.

This might seem like obvious, even tautological, but each serves as the trigger of deeper thinking and conversation.

Don't add more risk than you take away

Andrew (or Kerry Lee, I'm not sure which) introduced this to the EBS team as don't be weird.

So I think it reinforces two lessons:

1/ Don't be weird
2/ Modality is bad
— Andrew Certain (@tacertain) July 20, 2019

This isn't a comment on people (who are more than welcome to be weird), but on systems. Weirdness and complexity add risk, both risk that we don't understand the system that we're building, and risk that we don't understand the system that we are operating. When adding redundancy to a system, it's easy to fall into the mistake of adding too much complexity, and underestimating the ways in which that complexity adds risk.

You must be able to run in degraded mode

Once you've failed over to the redundant component, are you sure it's going to be able to take the load? Even in one of the simplest cases, active-passive database failover, this is a complex question. You're going from warm caches and full buffers to cold caches and empty buffers. Performance can differ significantly.

As systems get larger and more complex, the problem gets more difficult. What components do you expect to fail? How many at a time? How much traffic can each component handle? How do we stop our cost reduction and efficiency efforts from taking away the capacity needed to handle failures? How do we continuously test that the failover works? What mechanism do we have to make sure there's enough failover capacity? There's typically at least as much investment in answering these questions as building the redundant system in the first place.

Chaos testing, gamedays, and other similar approaches are very useful here, but typically can't test the biggest failure cases in a continuous way.

You've got to fail over in the right direction

When systems suffer partial failure, it's often hard to tell what's healthy and what's unhealthy. In fact, different systems in different parts of the network often completely disagree on health. If your system sees partial failure and fails over towards the truly unhealthy side, you're in trouble. The complexity here comes from the distributed systems fog of war: telling the difference between bad networks, bad software, bad disks, and bad NICs can be surprisingly hard. Often, systems flap a bit before falling over.

The system must be able to return to fully redundant mode

If your redundancy is a single shot, it's not going to add much availability in the long term. So you need to make sure the system can safely get from one to two, or N to N+1, or N to 2N. This is relatively easy in some kinds of systems, but anything with a non-zero RPO or asynchronous replication or periodic backups can make it extremely difficult. In small systems, human judgement can help. In larger systems, you need an automated plan. Most likely, you're going to make a better automated plan during daylight in the middle of the week during your design phase than at 3AM on a Saturday while trying to fix the outage.
 Is Anatoly Dyatlov to blame? 2019-06-17T00:00:00+00:00 http://brooker.co.za/blog/2019/06/17/chernobyl
Is Anatoly Dyatlov to blame?

Without a good safety culture, operators are bound to fail.

(Spoiler warning: containers spoilers for the HBO series Chernobyl, and for history).

Recently, I enjoyed watching HBO's new series Chernobyl. Like everybody else on the internet, I have some thoughts about it. I'm not a nuclear physicist or engineer, but I do think a lot about safety and the role of operators.

The show tells the story of the accident at Chernobyl in April 1986, the tragic human impact, and the cleanup and investigation in the years that followed. One of the villains in the show is Anatoly Dyatlov, the deputy chief engineer of the plant. Dyatlov was present in the control room of reactor 4 when it exploded, and received a huge dose of radiation (the second, or perhaps third, large dose in his storied life of being near reactor accidents). HBO's portrayal of Dyatlov is of an arrogant and aggressive man whose refusal to listen to operators was a major cause of the accident. Some first-hand accounts agree2, 3, 6, and others disagree1. Either way, Dyatlov spent over three years in prison for his role in the accident.

There's little debate that the reactor's design was deeply flawed. The International Nuclear Safety Advisory Group (INSAG) found4 that certain features of the reactor "had a primary influence on the course of the accident and its consequences". During the time before the accident, operators had put the reactor into a mode where it was unstable, with reactivity increases leading to higher temperatures, and further reactivity increases. The IAEA (and Russian scientists) also found that the design of the control rods was flawed, both in that they initially increased (rather than decreasing) reactivity when first inserted, and in that they machinery to insert them moved too slowly. They also found issues with the control systems, cooling systems, and the fact that some critical safety measures could be manually disabled. Authorities had been aware of many of these issues since an accident at the Ignalina plant in 19834, page 13, but no major design or operational practice changes had been made by the time of the explosion in 1986.

In the HBO series' telling of the last few minutes before the event, Dyatlov was shown to dismiss concerns from his team that the reactor shouldn't be run for long periods of time at low power. Initially, Soviet authorities claimed that the dangers of doing this was made clear to operators (and Dyatlov ignored procedures). Later investigations by IAEA found no evidence that running the reactor in this dangerous mode was forbidden 4, page 11. The same is true of other flaws in the plant. Operators weren't clearly told that pushing the emergency shutdown (aka SCRAM, aka AZ-5) button could temporarily increase the reaction rate in some parts of the reactor. The IAEA also found that the reactors were safe in "steady state", and the accident would not have occurred without the actions of operators.

Who is to blame for the 1986 explosion at Chernobyl?

In 1995, Dyatlov wrote an article in which he criticized both the Soviet and IAEA investigations5, and asked a powerful question:

How and why should the operators have compensated for design errors they did not know about?

If operators make mistakes while operating systems which have flaws they don't know about, is that "human error"? Does it matter if their ignorance of those flaws is because of their own inexperience, bureaucratic incompetence, or some vast KGB-lead conspiracy? Did Dyatlov deserve death for his role in the accident, as the series suggests? As Richard Cook says in "How Complex Systems Fail"7:

Catastrophe requires multiple failures – single point failures are not enough. ... Each of these small failures is necessary to cause catastrophe but only the combination is sufficient to permit failure.

And

After accidents, the overt failure often appears to have been inevitable and the practitioner's actions as blunders or deliberate willful disregard of certain impending failure. ... That practitioner actions are gambles appears clear after accidents; in general, post hoc analysis regards these gambles as poor ones. But the converse: that successful outcomes are also the result of gambles; is not widely appreciated.

If Dyatlov and the other operators of the plant had known about the design issues with the reactor that had been investigated following the accident at Ignalina in 1983, would they have made the same mistake? It's hard to believe they would have. If the reactor design had been improved following the same accident, would the catastrophe had occurred? The consensus seems to be that it wouldn't have, and if it did then it would have taken a different form.

From "How Complex Systems Fail":

Most initial failure trajectories are blocked by designed system safety components. Trajectories that reach the operational level are mostly blocked, usually by practitioners.

The show's focus on the failures of practitioners to block the catastrophe, and maybe on their unintentional triggering of the catastrophe seems unfortunate to me. The operators - despite their personal failings - had not been set up for success, either by arming them with the right knowledge, or by giving them the right incentives.

From my perspective, the show is spot-on in it's treatment of the "cost of lies". Lies, and the incentive to lie, almost make it impossible to build a good safety culture. But not lying is not enough. A successful culture needs to find the truth, and then actively use it to both improve the system and empower operators. Until the culture can do that, we shouldn't be surprised when operators blunder or even bluster their way into disaster.

Footnotes

 BBC, Chernobyl survivors assess fact and fiction in TV series, 2019

 Svetlana Alexievich, "Voices from Chernobyl".

 Serhii Plokhy, "Chernobyl: The History of a Nuclear Catastrophe". This is my favorite book about the disaster (I've probably read over 20 books on it), covering a good breadth of history and people without being too dramatic. There are a couple of minor errors in the book (like confusing GW and GWh in multiple places), but those can be overlooked.

 INSAG-7 The Chernobyl Accident: Updating of INSAG-1, IAEA, 1992

 Anatoly Dyatlov, Why INSAG has still got it wrong, NEI, 1995

 Adam Higginbotham, "Midnight in Chernobyl: The Untold Story of the World's Greatest Nuclear Disaster"

 Richard Cook, How Complex Systems Fail

 Some risks of coordinating only sometimes 2019-05-01T00:00:00+00:00 http://brooker.co.za/blog/2019/05/01/emergent
Some risks of coordinating only sometimes

Sometimes-coordinating systems have dangerous emergent behaviors

A classic cloud architecture is built of small clusters of nodes (typically one to nine1), with coordination used inside each cluster to provide availability, durability and integrity in the face of node failures. Coordination between clusters is avoided, making it easier to scale the system while meeting tight availability and latency requirements. In reality, however, systems sometimes do need to coordinate between clusters, or clusters need to coordinate with a central controller. Some of these circumstances are operational, such as around adding or removing capacity. Others are triggered by the application, where the need to present a client API which appears consistent requires either the system itself, or a layer above it, to coordinate across otherwise-uncoordinated clusters.

The costs and risks of re-introducing coordination to handle API requests or provide strong client guarantees are well explored in the literature. Unfortunately, other aspects of sometimes-coordinated systems do not get as much attention, and many designs are not robust in cases where coordination is required for large-scale operations. Results like CAP and CALM2 provide clear tools for thinking through when coordination must occur, but offer little help in understanding the dynamic behavior of the system when it does occur.

One example of this problem is reacting to correlated failures. At scale, uncorrelated node failures happen all the time. Designing to handle them is straightforward, as the code and design is continuously validated in production. Large-scale correlated failures also happen, triggered by power and network failures, offered load, software bugs, operator mistakes, and all manner of unlikely events. If systems are designed to coordinate during failure handling, either as a mesh or by falling back to a controller, these correlated failures bring sudden bursts of coordination and traffic. These correlated failures are rare, so the way the system reacts to them is typically untested at the scale at which it is currently operating when they do happen. This increases time-to-recovery, and sometimes requires that drastic action is taken to recover the system. Overloaded controllers, suddenly called upon to operate at thousands of times their usual traffic, are a common cause of long time-to-recovery outages in large-scale cloud systems.

A related issue is the work that each individual cluster needs to perform during recovery or even scale-up. In practice, it is difficult to ensure that real-world systems have both the capacity required to run, and spare capacity for recovery. As soon as a system can't do both kinds of work, it runs the risk of entering a mode where it is too overloaded to scale up. The causes of failure here are both technical (load measurement is difficult, especially in systems with rich APIs), economic (failure headroom is used very seldom, making it an attractive target to be optimized away), and social (people tend to be poor at planning for relatively rare events).

Another risk of sometimes-coordination is changing quality of results. It's well known how difficult it is to program against APIs which offer inconsistent consistency, but this problem goes beyond just API behavior. A common design for distributed workload schedulers and placement systems is to avoid coordination on the scheduling path (which may be latency and performance critical), and instead distribute or discover stale information about the overall state of the system. In steady state, when staleness is approximately constant, the output of these systems is predictable. During failures, however, staleness may increase substantially, leading the system to making worse choices. This may increase churn and stress on capacity, further altering the workload characteristics and pushing the system outside its comfort zone.

The underlying cause of each of these issues is that the worst-case behavior of these systems may diverge significantly from their average-case behavior, and that many of these systems are bistable with a stable state in normal operation, and a stable state at "overloaded". Within AWS, we are starting to settle on some patterns that help constrain the behavior of systems in the worst case. One approach is to design systems that do a constant amount of coordination, independent of the offered workload or environmental factors. This is expensive, with the constant work frequently going to waste, but worth it for resilience. Another emerging approach is designing explicitly for blast radius, strongly limiting the ability of systems to coordinate or communicate beyond some limited radius. We also design for static stability, the ability for systems to continue to operate as best they can when they aren't able to coordinate.

More work is needed in this space, both in understanding how to build systems which strongly avoid congestive collapse during all kinds of failures, and in building tools to characterize and test the behavior of real-world systems. Distributed systems and control theory are natural partners.

Footnotes:

 Cluster sizing is a super interesting topic in it's own right. Nine seems arbitrary here, but isn't: for the most durable consensus systems, because when spread across three datacenters allows one datacenter failure (losing 3) and one host failure while still having a healthy majority. Chain replicated and erasure coded systems will obviously choose differently, as will anything with read replicas, or cost, latency or other constraints.

 See Keeping CALM: When Distributed Consistency is Easy by Hellerstein and Alvaro. It's a great paper, and a very powerful conceptual tool.

 Learning to build distributed systems 2019-04-03T00:00:00+00:00 http://brooker.co.za/blog/2019/04/03/learning
Learning to build distributed systems

A long email reply

A common question I get at work is "how do I learn to build big distributed systems?". I've written replies to that many times. Here's my latest attempt.

Learning how to design and build big distributed systems is hard. I don't mean that the theory is harder than any other field in computer science. I also don't mean that information is hard to come by. There's a wealth of information online, many distributed systems papers are very accessible, and you can't visit a computer science school without tripping over a distributed systems course. What I mean is that learning the practice of building and running big distributed systems requires big systems. Big systems are expensive, and expensive means that the stakes are high. In industry, millions of customers depend on the biggest systems. In research and academia, the risks of failure are different, but no less immediate. Still, despite the challenges, doing and making mistakes is the most effective way to learn.

Learn through the work of others

This is the most obvious answer, but still one worth paying attention to. If you're academically minded, reading lists and lists of best papers can give you a place to start to find interesting and relevant reading material. If you need a gentler introduction, blogs like Adrian Colyer's Morning Paper summarize and explain papers, and can also be a great way to discover important papers. There are a lot of distributed systems books I love, but I haven't found an accessible introduction I particularly like yet.

If you prefer to start with practice, many of the biggest distributed systems shops on the planet publish papers, blogs, and talks describing their work. Even Amazon, which has a reputation for being a bit secretive with our technology, has published papers like the classic Dynamo paper, and a recent papers on the Aurora database, and many more. Talks can be a valuable resource too. Here's Jaso Sorenson describing the design of DynamoDB, me and Holly Mesrobian describing a bit of how Lambda works, and Colm MacCarthaigh talking about some principles for building control planes. There's enough material out there to keep you busy forever. The hard part is knowing when to stop.

Sometimes (as I've written about before) it can be hard to close the gap between theory papers and practice papers. I don't have a good answer to that problem.

Get hands-on

Learning the theory is great, but I find that building systems is the best way to cement knowledge. Implement Paxos, or Raft, or Viewstamped Replication, or whatever you find interesting. Then test it. Fault injection is a great approach for that. Make notes of the mistakes you make (and you will make mistakes, for sure). Docker, EC2 and Fargate make it easier than ever to build test clusters, locally or in the cloud. I like Go as a language for building implementations of things. It's well-suited to writing network services. It compiles fast, and makes executables that are easy to move around.

Go broad

Learning things outside the distributed systems silo is important, too. I learned control theory as an undergrad, and while I've forgotten most of the math I find the way of thinking very useful. Statistics is useful, too. ML. Human factors. Formal methods. Sociology. Whatever. I don't think there's shame in being narrow and deep, but being broader can make it much easier to find creative solutions to problems.

Become an owner

If you're lucky enough to be able to, find yourself a position on a team, at a company, or in a lab that owns something big. I think the Amazon pattern of having the same team build and operate systems is ideal for learning. If you can, carry a pager. Be accountable to your team and your customers that the stuff you build works. Reality cannot be fooled.

Over the years at AWS we've developed some great mechanisms for being accountable. The wheel is one great example, and the COE process (similar to what the rest of the industry calls blameless postmortems) is another. Dan Luu's list of postmortems has a lot of lessons from around the industry. I've always enjoyed these processes, because they expose the weaknesses of systems, and provide a path to fixing them. Sometimes it can feel unforgiving, but the blameless part works well. Some COEs contain as many great distributed systems lessons as the best research papers.

Research has different mechanisms. The goal (over a longer time horizon) is the same: good ideas and systems survive, and bad ideas and systems are fall away. People build on the good ones, with more good ideas and the whole field moves forward. Being an owner is important.

Another tool I like for learning is the what-if COE or premortem. These are COEs for outages that haven't happened yet, but could happen. When building a new system, think about writing your first COE before it happens. What are the weaknesses in your system? How will it break? When replacing an older system with a new one, look at some of the older one's COEs. How would your new system perform in the same circumstances?

It takes time

This all takes time, both in the sense that you need to allocate hours of the day to it, and in the sense that you're not going to learn everything overnight. I've been doing this stuff for 15 years in one way or another, and still feel like I'm scratching the surface. Don't feel bad about others knowing things you don't. It's an opportunity, not a threat.
 Control Planes vs Data Planes 2019-03-17T00:00:00+00:00 http://brooker.co.za/blog/2019/03/17/control
Control Planes vs Data Planes

Are there multiple things here?

If you want to build a successful distributed system, one of the most important things to get right is the block diagram: what are the components, what does each of them own, and how do they communicate to other components. It's such a basic design step that many of us don't think about how important it is, and how difficult and expensive it can be to make changes to the overall architecture once the system is in production. Getting the block diagram right helps with the design of database schemas and APIs, helps reason through the availability and cost of running the system, and even helps form the right org chart to build the design.

One very common pattern when doing these design exercises is to separate components into a control plane and a data plane, recognizing the differences in requirements between these two roles.

No true monoliths

The microservices and SOA design approaches tend to push towards more blocks, with each block performing a smaller number of functions. The monolith approach is the other end of the spectrum, where the diagram consists of a single block. Arguments about these two approaches can be endless, but ultimately not important. It's worth noting, though, that there are almost no true monoliths. Some kinds of concerns are almost always separated out. Here's a partial list:

Storage. Most modern applications separate business logic from storage and caching, and talk through APIs to their storage.

Load Balancing. Distributed applications need some way for clients to distribute their load across multiple instances.

Failure tolerance. Highly available systems need to be able to handle the failure of hardware and software without affecting users.

Scaling. Systems which need to handle variable load may add and remove resources over time.

Deployments. Any system needs to change over time.

Even in the most monolithic application, these are separate components of the system, and need to be built into the design. What's notable here is that these concerns can be broken into two clean categories: data plane and control plane. Along with the monolithic application itself, storage and load balancing are data plane concerns: they are required to be up for any request to succeed, and scale O(N) with the number of requests the system handles. On the other hand, failure tolerance, scaling and deployments are control plane concerns: they scale differently (either with a small multiple of N, with the rate of change of N, or with the rate of change of the software) and can break for some period of time before customers notice.

Two roles: control plane and data plane

Every distributed system has components that fall roughly into these two roles: data plane components that sit on the request path, and control plane components which help that data plane do its work. Sometimes, the control plane components aren't components at all, and rather people and processes, but the pattern is the same. With this pattern worked out, the block diagram of the system starts to look something like this:

My colleague Colm MacCárthaigh likes to think of control planes from a control theory approach, separating the system (the data plane) from the controller (the control plane). That's a very informative approach, and you can hear him talk about it here:

I tend to take a different approach, looking at the scaling and operational properties of systems. As in the example above, data plane components are the ones that scale with every request1, and need to be up for every request. Control plane components don't need to be up for every request, and instead only need to be up when there is work to do. Similarly, they scale in different ways. Some control plane components, such as those that monitor fleets of hosts, scale with O(N/M), which N is the number of requests and M is the requests per host. Other control plane components, such as those that handle scaling the fleet up and down, scale with O(dN/dt). Finally, control plane components that perform work like deployments scale with code change velocity.

Finding the right separation between control and data planes is, in my experience, one of the most important things in a distributed systems design.

Another view: compartmentalizing complexity

In their classic paper on Chain Replication, van Renesse and Schneider write about how chain replicated systems handle server failure:

In response to detecting the failure of a server that is part of a chain (and, by the fail-stop assumption, all such failures are detected), the chain is reconfigured to eliminate the failed server. For this purpose, we employ a service, called the master

Fair enough. Chain replication can't handle these kinds of failures without adding significant complexity to the protocol. So what do we expect of the master?

In what follows, we assume the master is a single process that never fails.

Oh. Never fails, huh? They then go on to say that they approach this by replicating the master on multiple hosts using Paxos. If they have a Paxos implementation available, then why do they just not use that and not bother with this Chain Replication thing at all? The paper doesn't say2, but I have my own opinion: it's interesting to separate them because Chain Replication offers a different set of performance, throughput, and code complexity trade offs than Paxos3. It is possible to build a single code base (and protocol) which handles both concerns, but at the cost of coupling these two different concerns. Instead, by making the master a separate component, the chain replicated data plane implementation can focus on the things it needs to do (scale, performance, optimizing for every byte). The control plane, which only needs to handle the occasional failure, can focus on what it needs to do (extreme availability, locality, etc). Each of these different requirements adds complexity, and separating them out allows a system to compartmentalize its complexity, and reduce coupling by offering clear APIs and contract between components.

Breaking down the binary

Say you build awesome data plane based on chain replication, and an awesome control plane (master) for that data plane. At first, because of its lower scale, you can operate the control plane manually. Over time, as your system becomes successful, you'll start to have too many instances of the control plane to manage by hand, so you build a control plane for that control plane to automate the management. This is the first way the control/data binary breaks down: at some point control planes need their own control planes. Your controller is somebody else's system under control.

One other way the binary breaks down is with specialization. The master in the chain replicated system handles fault tolerance, but may not handle scaling, or sharding of chains, or interacting with customers to provision chains. In real systems there are frequently multiple control planes which control different aspects of the behavior of a system. Each of these control planes have their own differing requirements, requiring different tools and different expertise. Control planes are not homogeneous.

These two problems highlight that the idea of control planes and data planes may be too reductive to be a core design principle. Instead, it's a useful tool for helping identify opportunities to reduce and compartmentalize complexity by introducing good APIs and contracts, to ensure components have a clear set of responsibilities and ownership, and to use the right tools for solving different kinds of problems. Separating the control and data planes should be a heuristic tool for good system design, not a goal of system design.

Footnotes:

 Or potentially with every request. Things like caches complicate this a bit.

 It does compare Chain Replication to other solutions, but doesn't specifically talk about the benefits of seperation. Murat Demirbas pointed out that Chain Replication's ability to serve linearizable reads from the tail is important. He also pointed me at the Object Storage on CRAQ paper, which talks about how to serve reads from intermediate nodes. Thanks, Murat!

 For one definition of Paxos. Lamport's Vertical Paxos paper sees chain replication as a flavor of Paxos, and more recent work by Heidi Howard et al on Flexible Paxos makes the line even less clear.

 Telling Stories About Little's Law 2018-06-20T00:00:00+00:00 http://brooker.co.za/blog/2018/06/20/littles-law
Telling Stories About Little's Law

Building Up Intuition with Narrative

Little's Law is widely used as a tool for understanding the behavior of distributed systems. The law says that the mean concurrency in the system (𝐿) is equal to the mean rate at which requests arrive (λ) multiplied by the mean time that each request spends in the system (𝑊):

𝐿 = λ𝑊

As I've written about before, Little's law is useful because it gives us a clear way to reason about the capacity of a system, which is often difficult to observe directly, based on quantities like arrival rate (requests per second) and latency which are easier to measure directly. Concurrency is a useful measure of capacity in real systems, because it directly measures consumption of resources like threads, memory, connections, file handles and anything else that's numerically limited. It also provides an indirect way to think about contention: if the concurrency in a system is high, then it's likely that contention is also high.

I like Little's Law as a mathematical tool, but also as a narrative tool. It provides a powerful way to frame stories about system behavior.

Feedback

The way Little's Law is written, each of the terms are long-term averages, and λ and 𝑊 are independent. In the real world, distributed systems don't tend to actually behave this nicely.

Request time (𝑊) tends to increase as concurrency (𝐿) increases. Amdahl's Law provides the simplest model of this: each request has some portion of work which is trivially parallelizable, and some portion of work that is forced to be serialized in some way. Amdahl's law is also wildly optimistic: most real-world systems don't see throughput level out under contention, but rather see throughput drop as contention rises beyond some limit. The universal scalability law captures one model of this behavior. The fundamental reason for this is that contention itself has a cost.

Even in the naive, beautiful, Amdahl world, latency increases as load increases because throughput starts to approach some maximum. In the USL world, this increase can be dramatically non-linear. In both cases 𝑊 is a function of 𝐿.

Arrival rate (λ) also depends on request time (𝑊), and typically in a non-linear way. There are three ways to see this relationship:

Arrival rate drops as request time increases (λ ∝ 1/𝑊). In this model there is a finite number of clients and each has its own finite concurrency (or, in the simplest world is calling serially in a loop). As each call goes up, clients keep their concurrency fixed, so the arrival rate drops.

Arrival rate does not depend on latency. If clients don't change their behavior based on how long requests take, or on requests failing, then there's no relationship. The widely-used Poisson process client model behaves this way.

Arrival rate increases as request time increases (λ ∝ 𝑊). One cause of this is timeout and retry: if a client sees a request exceed some maximum time (so 𝑊>𝜏) they may retry. If that timeout 𝜏 is shorter than their typical inter-call time, this will increase the per-client rate. Other kinds of stateful client behavior can also kick in here. For example, clients may interpret long latencies as errors that don't only need to be retried, but can trigger entire call chains to be retried.

The combination of these effects tends to be that the dynamic behavior of distributed systems has scary cliffs. Systems have plateaus where they behave well where 𝑊, 𝐿 and λ are either close-to-independent or inversely proportional, and cliffs where direct proportionality kicks in and they spiral down to failure. Throttling, admission control, back pressure, backoff and other mechanisms can play a big role in avoiding these cliffs, but they still exist.

Arrival Processes and Spiky Behavior

The mean, like all descriptive statistics, doesn't tell the whole story about data. The mean is very convenient in the mathematics of Little's law, but tends to hide effects caused by high-percentile behavior. Little's law's use of long-term means also tends to obscure the fact that real-world statistical processes are frequently non-stationary: they include trends, cycles, spikes and seasonality which are not well-modeled as a single stationary time series. Non-stationary behavior can affect 𝑊, but is most noticeable in the arrival rate λ.

There are many causes for changes in λ. Seasonality is a big one: the big gift-giving holidays, big sporting events, and other large correlated events can significantly increase arrival rate during some period of time. Human clients tend to exhibit significant daily, weekly, and yearly cycles. People like to sleep. For many systems, though, the biggest cause of spikes is the combination of human biases and computer precision: cron jobs. When humans pick a time for a task to be done (backup once a day, ping once a minute), they don't tend to pick a uniformly random time. Instead, they cluster the work around the boundaries of months, days, hours, minutes and seconds. This leads to significant spikes of traffic, and pushes the distribution of arrival time away from the Poisson process ideal1.

Depending on how you define long term mean, these cyclic changes in λ can either show up in the distribution of λ as high percentiles, or show up in λ being non-stationary. Depending on the data and the size of the spikes it's still possible to get useful results out of Little's law, but they will be less precise and potentially more misleading.

Telling Stories

Somewhat inspired by Little's law, we can build up a difference equation that captures more of real-world behavior:

Wn+1 = 𝑊(Ln, λn, t)

λn+1 = λ(Ln, Wn, t)

Ln+1 = λn+1 𝑊n+1

I find that this is a powerful mental model, even if it's lacking some precision and is hard to use for clean closed-form results. Breaking the behavior of the system down into time steps provides a way to tell a story about the way the system behaves in the next time step, and how the long-term behavior of the system emerges. It's also useful for building simple simulations of the dynamics of systems.

Telling stories about our systems, for all its potential imprecision, is a powerful way to build and communicate intuition.

The system was ticking along nicely, then just after midnight a spike of requests from arrived from a flash sale. This caused latency to increase because of increased lock contention on the database, which in turn caused 10% of client calls to time-out and be retried. A bug in backoff in our client meant that this increased call rate to 10x the normal for this time of day, further increasing contention. And so on...

Each step in the story evolves by understanding the relationship between latency, concurrency and arrival rate. The start of the story is almost always some triggering event that increases latency or arrival rate, and the end is some action or change that breaks the cycle. Each step in the story offers an opportunity to identify something to make the system more robust. Can we reduce the increase in 𝑊 when λ increases? Can we reduce the increase in λ when 𝑊 exceeds a certain bound? Can we break the cycle without manual action?

The typical resiliency tools, like backoff, backpressure and throttling, are all answers to these types of questions, but are far from the full set of answers. Telling the stories allows us to look for more answers.

Footnotes

 Network engineers have long known that the Poisson model is less bursty than many real systems. An Empirical Workload Model for Driving Wide-Area TCP/IP Network Simulations and Wide Area Traffic: The Failure of Poisson Modeling are classics in that genre. I'm not aware of good research on this problem in microservice or SoA architectures, but I'm sure there are some interesting results to be found there.

 Availability and availability 2018-02-25T00:00:00+00:00 http://brooker.co.za/blog/2018/02/25/availability-liveness
Availability and availability

Translating math into engineering.

It's well known that the term Availability in the CAP theorem (as formally defined by Gilbert and Lynch) means something different from the term availability that's commonly used by the designers, builders and operators of distributed systems. Gilbert and Lynch define availability for the CAP theorem as:

every request received by a non-failing node in the system must result in a response.

That's cool, and useful for the mathematical analysis that's needed to prove the CAP theorem. Most builders and users of distributed systems, on the other hand, define availability as the percentage of requests that their clients see as successful, or something close to that. The terms, like 'clients' and 'successful' and 'see', are pretty fuzzy. Not much good for analysis, but more useful for capturing what people care about.

This isn't a new observation. You can find a whole lot of writing about it online. Some of that writing is pretty great. What I don't see addressed as often is how to translate one into the other, using the CAP (or PACELC or whatever) reasoning about Availability to help us think about availability. In reality, are Available systems more available than Consistent systems?

This post isn't a complete answer to that question, but does include some of the things worth thinking about in that space.

Harvest and Yield

Before I dive into this topic, it's worth talking about Harvest and Yield, from a paper by Fox and Brewer. The paper itself has some flaws (as I've blogged about before), but the underlying concept is very useful. The core is about graceful degradation, and how it's useful for systems to return partial or stale answers when they aren't able to answer authoritatively.

The paper makes its case well, but whether its conclusions are practically useful depend on what promises you make to your clients. If the direct clients of your service are people, then you're likely to be able to get away with graceful degradation. If your clients are computers, they're likely expecting a complete, authoritative, response. That's mostly because when people program computers they don't think through all of the edge cases introduced by other computers leaving out some information. This isn't a hard-and-fast rule. Sometimes computers can tolerate partial responses, and sometimes humans can't.

In other words, Harvest and Yield is a partial answer, useful when you can use it.

Taking Availability to Clients

How does CAP's big-A availability translate to clients? The most useful simple answer is that if you've decided you want to Consistent system, then clients on the minority side of a network partition get nothing, and clients on the majority side don't have any problems. Once the partition heals (or moves around), those minority clients might be able to make progress again. If you've chosen an Available system, everybody is able to make progress all the time.

The reality is fuzzier than this simple answer.

The first reason is that, in real systems, there isn't typically a binary choice between A and C. Part of the reason for that is that the definition of Consistency in CAP is also different from the common sense one clients probably care about, and it's possible to give some clients meaningfully consistent experiences without losing A. The details of that are for another day1.

Lets assume that you've chosen a common-sense definition of consistency that requires real strong Consistency properties. Then you run into a second problem: many meaningful workloads from clients don't only read or write a single atomic piece of data. Some workloads are nice a clean and translate into a single database transaction on a single database. Some are messier, and require pulling data from many different shards of different databases, or from other services. Over time, many of the nice clean workloads turn into ugly messy workloads.

There's also a third problem. The vast majority of the patterns that are used for building real-world large-scale systems do different amounts of work in the happy case and the failure case. Master election, for example, is a very commonly-used pattern. Paxos implementations typically optimize away one round most of the time. Raft is explicitly modal.

Clients on the majority side of a partition are theoretically able to continue, but only if they are on the same majority side of all the data and services they depend on. They're also likely to be some cost to continuing, requiring the system to detect the problem, and shift from happy mode into failure handling mode. Depending on the design of the system, this can take a significant period of time.

Failure Detection and Remediation

The first step to surviving a network partition (or any other failure), is figuring out what happened. Sometimes, what happened is a nice clean host failure that everybody can agree on. The real world is uglier: host failures may be partial, network failures may show up as latency or congestion rather than failure, and systems could be cycling between up and down.

Whether you've chosen an Available (A) system or a Consistent (C) system, your system needs to be able to identify failures. How quickly you can do that, and how the system behaves in the mean time, is fundamental to availability.

There are many ways to detect failures: timeouts, direct health pings, latency thresholds, error rate thresholds, TCP connection state (a special case of latency threshold), and even hardware magic like physical-layer connection state. None of those are instantaneous, and most will eat some requests while deciding to fail over. If that happens often, availability will be decreased.

Failure remediation is where the distributed systems protocol literature shines. Paxos Made Simple or Viewstamped Replication or Chord or one of hundreds of other papers provide answers to that problem to fit all kinds of different situations. I'm not going to go into that topic, but even if you nail the implementation of failure handling, you've still not solved your client's problem.

When a failure is fixed, who needs to learn about the new location of the data and how quickly they can learn about it? While clients are trying to talk to the old, broken primary or trying to talk to the other side of a network partition, they aren't going to be making progress. Again, whether you've chosen A or C, availability suffers. Available systems do have a bit of an easier time of this than Consistent systems. They might be able to fail over more aggressively. They also don't have to solve the age-old "oops, I just flipped into the side of the partition away from my clients" problem.

Where do failures happen?

Network partitions do happen. From the perspective of the client of a Consistent system, the system is down if they are partitioned away from the majority of the nodes in the system. From the perspective of the client of an Available system, the system is down if they are partitioned away from all the nodes in the system.

Whether that's a useful distinction or not depends on where the clients are relative to the larger system. If the system is in a single datacenter in a single location, and the clients are spread around the global Internet, it's not much more likely that they'll be able to contact less than half of the nodes than none of the nodes. On the other hand, if the clients are in the same datacenter as the system, then the probabilities are going to be different. More generally, if nodes are spread around the network about the same way as clients, A and C are going to be practically different.

Conclusion

In practice, CAP Available doesn't mean 'highly available to clients'. In practice, picking an Available design over a Consistent one means that it's going to be more available to some clients in a fairly limited set of circumstances. That may very well be worth it, but it's in no way a panacea for availability.

Footnotes

 Although, do check out Bailis and Ghodsi for a very readable introduction to the landscape of consistency.

 Balls Into Bins In Distributed Systems 2018-01-01T00:00:00+00:00 http://brooker.co.za/blog/2018/01/01/balls-into-bins
Balls Into Bins In Distributed Systems

Throwing things can be fun.

If you've come across the Balls Into Bins problem, you probably heard about in context of hash tables. When you hash things into a hash table (especially with separate chaining) it's really useful to be able to ask "If I throw 𝑀 balls into 𝑁 bins, what is the distribution of balls in bins?" You can see how this is fundamental to hash tables: the amortized complexity argument for hash tables depends on their being some load factor (i.e. 𝑀/𝑁) for which most bins contain a small number of items. Once this stops being true, lookup and insertion time on hash tables starts to get ugly. So from that perspective it's already clearly an important problem.

Load Balancing and Work Allocation

Hash tables aren't the only place that the Balls Into Bins problem is interesting. It comes up often in distributed systems, too. For one example, think about a load balancer (in this case a distributor of independent requests) sending load to some number of backends. Requests (𝑀) are balls, and the backends are bins (𝑁) and typically there are multiple requests going to each backend (𝑀 > 𝑁). If we know how to solve for the number of balls in each bin, we can understand the limits of random load balancing, or whether we need a stateful load balancing algorithm like least connections. This is an important question to ask, because sharing consistent state limits scalability, and sharing eventually-consistent state can even make load balancing decisions worse. Load balancing is much easier if it can be done statelessly.

A related problem is push-based work allocation. Here, there is some co-ordinator handing out work items to a fleet of workers, and trying to have those workers do approximately equal amounts of work. One way that systems end up with this pattern is if they are using shuffle sharding or consistent hashing to distribute work items (or records). These hashing-based methods can be great for scaling, and so are widely used across all kinds of large-scale systems. Just as with load balancing, its interesting to be able to understand how well requests are distributed.

Traditionally, papers about this problem have been most concerned about the expectation of the maximum number of balls in a bin ("how bad can it get?"), but other statistics like the expectation of the mean and expectation of the median can be interesting when planning and designing for load. It's also interesting to understand the variance of the maximum, and the size of the right tail on the distribution of the maximum. If the maximum can get really high, but will do so infrequently, then load testing can be difficult.

Closed-Form Analysis

Gaston Gonnet's Expected Length of the Longest Probe Sequence in Hash Code Searching, was one of the first papers to tackle analyzing the problem, in context of separate-chaining hash tables2. Michael Mitzenmacher's PhD thesis (the power of two choices in randomized load balancing) simplifies Gonnet's analysis and finds, for the 𝑀=𝑁 case, the maximum number of balls is1 𝝝(log 𝑁/log log 𝑁). That's not a curve you'll come across often, so this is what it looks like:

In other words, it grows, but grows pretty slowly. Most real-world cases are probably going to have 𝑀>𝑁, and many will have 𝑀≫𝑁. To understand those cases, we can turn to one of my favorite papers in this area, Balls Into Bins: A Simple and Tight Analysis by Raab and Steger. They provide a great overview of the problem, a useful survey of the literature, and a table of bounds on the maximum number of balls in any bin, depending on the relationship between 𝑀 and 𝑁. The proofs are interesting, and somewhat enlightening, but not necessary to understand to find the paper useful.

While this kind of analysis is very useful, when I've needed to solve these problems in the past, I haven't tended to use the results directly. Instead, I've used them to sanity check the output of simulations. This is where engineering practice diverges a bit from computer science theory (although it does it in a pretty theoretically rigorous way).

Simulating the Problem

There are a couple of limitations on the usefulness of the closed-form analysis of this problem. One problem is that it's fairly difficult to understand clearly (at least for me), and quite complex to communicate. The bigger problem, though, is that it's quite inflexible: extending the analysis to include cases like balls of different sizes (as requests are in the real world) and balls coming out of bins (requests completing) is difficult, and difficult to code review unless you are lucky enough to work with a team that's very mathematically sophisticated. The good news, though, is that this problem is exceptionally easy to simulate.

When I think about doing these kinds of simulations, I don't generally think about using specialized simulation tools or frameworks (although you could certainly do that). Instead, I generally think about just writing a few tens of lines of Python or R which directly try the thing that I want an answer for many times, and then output data in a form that's easy to plot. Computer simulation is a broad and subtle topic, but this kind of thing (throw balls into bins, count, repeat) avoids many of the subtleties because you can avoid floating point (its just counting) and because you can avoid being too concerned about the exact values.

Knowing the closed-form analysis makes it easy to sanity-check the simulation. According to Gonnet, the 𝑀=𝑁 case should approach log𝑁/loglog𝑁 (1+𝑜(1)), and we can plot that curve (choosing a value of 𝑜(1) to minimize the difference) alongside the simulation results to see if the simulation matches the theory. The results look pretty good.

Gonnet's paper also contains a table of example values, which compare very well to our simulated and modelled numbers. That all increases our confidence that the simulation is telling us sensible things.

You can also extend this basic counting to be closer to real-world load-balancing. Follow a Poisson process (a fancy way of saying "use exponentially distributed random numbers to decide how long to wait") to add random balls into bins over time, and follow your completion time distribution (probably exponential too) to pull them out of the bins. Every so often, sample the size of the biggest bin. Next, output those samples for analysis. If you have real arrival-time data, and completion-time distributions, you can use those to avoid making any statistical assumptions. Which is nice.

When you've got the basic simulation, it's easy to add in things like different-sized requests, or bursts of traffic, or the effects of scaling up and down the backends.

Some Basic Results

For small M and N, the constant factors are a big problem. With 𝑀=𝑁=100, I get an expected maximum of around 4.2. In other words, we can expect the busiest backend to be over 4x busier than the average. That means that you either need to significantly over-scale all your backends, or put up with the problems that come with hotspotting. This problem also gets worse (although very very slowly, going back to the closed-form) with scale.

In the closer-to-reality case with 𝑀=1000 and 𝑁=100, the gap shrinks. The expected maximum comes to as 18.8, compared to a mean (aka 𝑀/𝑁) of 10. That still means that the hottest backend gets 80% more traffic, but the gap is closing. By 𝑀=10000 and 𝑁=100, the gap has closed to 25%, which starts to be close to the realm of acceptable. Up to 𝑀=100,000 and the gap is closed to 8%. In most distributed systems contexts, 8% is probably within the variation in performance due to other factors.

Still, the conclusion of all of this is that random load balancing (and random shuffle-sharding, and random consistent hashing) distributed load rather poorly when 𝑀 is small. Load-sensitive load-balancing, either stateful or stateless with an algorithm like best-of-two is still very much interesting and relevant. The world would be simpler and more convenient if that wasn't the case, but it is.

Footnotes:

 That's a Big Theta, if you're not familiar with it wikipedia has a good explanation of what it means. If you don't feel like reading that, and replace it with a big O in your head, that's close enough in this case.

 That paper also contains some great analysis on the numerical properties of different hash-table probing strategies versus seperate chaining. If you like algorithm analysis, the conclusion section is particularly interesting.

 Is the Mean Really Useless? 2017-12-28T00:00:00+00:00 http://brooker.co.za/blog/2017/12/28/mean
Is the Mean Really Useless?

Don't be too mean to the mean.

"The mean is useless" is a commonly-repeated statement in the systems observation and monitoring world. As people correctly point out, the mean (or average1) tends to hide information about outliers, tends to be optimistic for many metrics, and can even be wildly misleading in presence of large outliers. That doesn't mean that the average is useless, just that you need to be careful of how you interpret it, and what you use it for.

All descriptive statistics are misleading

All descriptive statistics are misleading, and potentially dangerous. The most prosaic reason for that is that they are summaries: by their nature they don't capture the entire reality of the data they are summarizing. There is no way for a single number to capture everything you need to know about a large set of numbers. Anscombe's quartet is the most famous illustration of this problem: four data sets that have very different graphs, but the same mean and variance in 𝑥 and 𝑦, and the same linear trend. Thanks to Albert Cairo and Autodesk, there's an even more fun example: the datasaurus dozen2.

There are other, more subtle, reasons that descriptive statistics are misleading too. One is that statistics in real-world computer systems change with time, and you can get very different results depending on how those changes in time align with when you sample and how long you average for. Point-in-time sampling can lead to completely missing some detail, especially when the sampling time is aligned to wall-clock time with no jitter.

In this example, we've got a machine that runs a periodic job (like a cron job) every minute, and it uses all the CPU on the box for a second. If we sample periodically, aligned to the minute boundary, we'll think the box has 100% CPU usage. Instead, if we sample periodically aligned to any other second, we'll think it completely idle. If, instead, we sample every second and emit a per-minute summary we'll get a mean of 1.7% usage, a median of 0% and a 99th percentile of 100%. None of those really tell us what's going on. Graphing the time series helps in this case, punting the problem to our brain's ability to summarize graphs, but that's hard to do at scale. The darling on the monitoring crowd, histograms, don't really help here either3. That's obviously a fantastically contrived example. Check out this presentation from Azul systems for some real-world ones.

Ok, so descriptive statistics suck. For many operational tasks, medians and percentiles suck less than the mean. But that shouldn't be taken to imply that averages are useless.

Throughput

The throughput of a serial system, how many items of work it can do in a period of time, is one over the mean latency. That changes when the system can do multiple work items at once, either due to pipelining (like CPUs, networks and storage) or due to true parallelism (again, like CPUs, networks, and storage), but mean latency remains the denominator.

Consider a serial system that processes requests in 1ms 99% of the time, and 1s 1% of the time. The mean latency is 10.99ms, and the throughput is 91 requests per second. What the monitoring people are saying when they talk about the mean being bad is that neither of those figures (10.99ms or 91 rps) tells you that 1% of requests are having a really bad time. That's all true. But both of those numbers are still very useful for capacity planning.

The mean throughput number, 91 requests per second in our example, allows us to compare our expected rate of traffic with the capacity of the system. If we're expecting 10 requests per second at peak this holiday season, we're good. If we're expecting 100, then we're in trouble. Once we know we're in capacity trouble we can react by adding a second processor (doubling throughput in theory), or by trying to reduce latency (probably starting with that 1000ms outlier). Just looking at our latency graphs doesn't tell us that.

Contention and Little's Law

Another place the mean is really useful is in context of Little's Law: 𝐋=𝛌𝐖.

the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system

There are a lot of reasons that this law is interesting and useful, but the biggest one for system operators is concurrency and how it relates to scale. In almost all computer systems concurrency is a limited resource. In thread-per-request (and process-per-request) systems the limit is often the OS or language scheduler. In non-blocking, evented, and green-thread systems limits include memory, open connections, the language scheduler, and backend limitations like database connections. In modern serverless systems like AWS Lambda, you can provision concurrency directly.

Like throughput, Little's law gives us a way to reason about the long-term capacity of a system, and how close we are to it. In large-scale distributed systems many of the limited resources can be difficult to measure directly, so these capacity measures are also useful in understanding the load on resources we can't observe.

It's very useful to build an intuition around Little's law, because it provides a handle onto some of the dynamic behaviors of computer systems. In real-world system (often due to contention), latency (𝐖) tends to increase along with concurrency (𝐋), meaning that the actual reaction of 𝐋 to increasing arrival rate (𝛌) can be seriously non-linear. Similarly, timeout-and-retry leads the arrival rate to increase as latency increases, again leading to non-linear effects.

Little's law isn't true of the other descriptive statistics. You can't plug in a percentile of 𝛌 or 𝐖 and expect to get a correct percentile of 𝐋. It only works, except in exceptional circumstances, on the mean.

Request Size and Volume

Mean request size (or packet size, or response size, etc) is another extremely useful mean. It's useful precisely because of the way the mean is skewed by outliers. Remember that the mean is defined as the sum divided by the count: if you multiply it back by the count you can extract the sum. When it comes to storage, or even things like network traffic, the total count is a very useful capacity measure. Percentiles, by their nature, are robust to outliers, but the measure you're actually interested in ("how much storage am I using?") may be driven by outliers.

Conclusion

Graphs, percentiles, medians, maximums, and moments are all extremely useful tools if you're interested in monitoring systems. But I feel that, in their fervor to promote these tools, people have over-stated the case against the mean. In some quarters there even seems to be a religious fervor against the average, and immediate judgments of incompetence against anybody who uses it. That's unfortunate, because the average is a tool that's well-suited to some important tasks. Like all statistics, it needs to be used with care, but don't believe the anti-mean zealots (and, importantly, don't be mean).

Footnotes:

 In this post I use mean and average more-or-less interchangeably, even though that isn't technically correct. You know what I mean.

 The paper on how the datasaurus dozen were made is worth reading.

 Histograms do, obviously, help in other cases, as do other tools like Box plots. Sometimes you have to graph and summarize data in multiple ways before finding the one that answers the question you need to answer. John Tukey's Exploratory Data Analysis is the classic book in that field.

 Why Must Systems Be Operated? 2016-01-03T00:00:00+00:00 http://brooker.co.za/blog/2016/01/03/correlation
Why Must Systems Be Operated?

Latent Failures and the Safety Margin of Systems

Mirrored RAID1 is a classic way of increasing storage durability. It's also a classic example of a system that's robust against independent failures, but fragile against dependent failure. Patterson et al's 1988 paper, which popularized mirroring, even covered the problem:

As mentioned above we make the same assumptions that disk manufacturers make -- that the failures are exponential and independent. (An earthquake or power surge is a situation where an array of disks might not fail independently.)

A 2-way striped RAID can be in three possible states: a state with no failures, a state with one failure, or a state with two failures. The system moves between the first and second states, and the second and third states, when a failure happens. It can return from the second state to the first by repair. In the third state, data is lost, and returning becomes an exercise in disaster recovery (like restoring a backup). The classic Markov model looks like this, with the failure rate λ and repair rate μ:

This model clearly displays its naive thinking: it assumes that the failure rate of 2 disks is double the failure rate of a single disk2. All experienced system operators know that's not true in practice. A second disk failure seems more likely to happen soon after a first. This happens for three reasons.

Failures with the same cause. These failures, like Patterson's earthquakes and power surges, affect both drives at the same time. A roof falling in on a server can move its RAID from state 1 to state 3 pretty quickly. Operator mistakes are also a common (and maybe dominant) source of these kinds of failures.

Failures triggered by the first failure. When the first drive fails, it triggers a failure of the second drive. In a RAID, the second drive is going to be put under high load as the system attempts to get back to two good copies. This extra load increases the probability of the second drive failing.

Latent failures. These cases start with the system believing (and the system operator believing) that the system is in stage one. When a failure occurs, it very quickly learns that the second good copy isn't so good3.

The third case, latent failures, may be the most interesting to system designers. They are a great example of the fact that systems4 often don't know how far they are from failure. In the simple RAID case, a storage system with a latent failure believes that it's in the first state, but actually is in the second state. This problem isn't, by any means, isolated to RAID.

Another good example of the same problem is a system with a load balancer and some webservers behind it. The load balancer runs health checks on the servers, and only sends load to the servers that it believes are healthy. This system, like mirrored RAID, is susceptible to having outages caused by failures with the same cause (flood, earthquake, etc), failures triggered by the first failure (overload), and latent failures. The last two are vastly more common than the first: the servers fail one-by-one over time, and the system stays up until it either dies of overload, or the last server fails.

In both the load-balancer and RAID cases, a black box monitoring of the system is not sufficient. Black box monitoring, including external monitors, canaries, and so on, only tell the system which side of an externally visible failure boundary a system is on. Many kinds of systems, including nearly every kind that includes some redundancy, can move towards this boundary through multiple failures without crossing it. Black-box monitoring misses these internal state transitions. Catching them can significantly improve the actual, real-world, durability and availability of a system.

Presented that way, it seems obvious. However, I think there's something worth paying real attention to hear: complex systems, the kind we tend to build when we want to build failure-tolerant systems, have a property that simple systems don't. Simple systems, like a teacup, are either working or they aren't. There is no reason to invest in maintenance (beyond the occasional cleaning) until a failure happens. Complex systems are different. They need to be constantly maintained to allow them to achieve their optimum safety characteristics.

This requires deep understanding of the behavior of the system, and involves complexities that are often missed in planning and management activities. If planning for, and allocating resources to, maintenance activities is done without this knowledge (or, worse, only considering external failure rates) then its bound to under-allocate resources to the real problems.

That doesn't mean that all maintenance must, or should, be done by humans. It's possible, and necessary at scale, to automate many of the tasks needed to keep systems far from the failure boundary. You've just got to realize that your automation is now part of the system, and the same conclusions apply.

Footnotes:

 Also known as RAID 1. Despite nearly a decade working on computer storage, my brain refuses to store the bit of which of RAID 0 and RAID 1 is mirroring, and which is striping.

 And a whole lot more. Hafner and Rao is a good place to start for a more complete picture of RAID reliability.

 In storage systems the most common cause of these kinds of issues are latent sector errors. Understanding latent sector errors and how to protect against them is a good place to start with the theory, and An Analysis of Latent Sector Errors in Disk Drives present some (possibly dated) data on their frequency.

 Here, the system includes its operators, both human and automated.

 Heuristic Traps for Systems Operators 2015-11-05T00:00:00+00:00 http://brooker.co.za/blog/2015/11/05/heuristics
Heuristic Traps for Systems Operators

What can we learn from avalanche safety?

Powder magazine's new feature The Human Factor 2.0 is a fantastic read. It's a good disaster story, like the New York Times' Snow Fall: The Avalanche At Tunnel Creek, but looks deeply at a very interesting topic: the way that we make risk decisions. I think there are interesting lessons there for operators and designers of computer systems.

"That's the brutal thing," Donovan said. "It's hard to get experience without exposing yourself to risk."

The consequences of making bad decisions in back-country skiing can be life and death. As designers, builders and operators of systems of computers our bad decisions are generally less dramatic. But they are real. Data loss, customer disappointment, and business failure have all come as the results of making poor risk decisions. One way to mitigate those risks is experience, and it's product: intuition. Unfortunately, as David Page's article reminds us, intuition isn't always the route to safety.

The difficulty, he explained, especially when it comes to continuing education for veteran mountain guides and other professionals, is breaking through a culture of expertise that is based on savoir-faire - in other words, on some deep combination of knowledge and instinct derived from experience - especially if that experience may happen to include years of imperfect decisions and sheer luck. "When we talk about human behavior, people feel a bit attacked in their certainty, in their habits"

The problem with intuition is exactly that it is not the product of conscious thought. Intuition is Daniel Kahneman's System 1: effortless, implicit, and based on heuristics rather than reason. It's well documented that these heuristics serve us very well in many situations, especially when speed of movement is important above all else, but they don't lead to us making good decisions in the long term.

Ian McCammon's Evidence of heuristic traps in recreational avalanche accidents is great evidence of this effect in practice. He presents four heuristics that appear to correlate with snow sports accidents:

The familiarity heuristic, or taking increased risks in familiar places or situations.

The social proof heuristic, or taking increased risks because others are doing it.

The commitment heuristic, or taking increased risks because we want to appear consistent with our words, keep our promises, or feel committed to the situation. Here, we're stepped in so far.

The scarcity heuristic, or taking increased risks to take advantage of limited resource or opportunities.

McCammon presents evidence that the social proof, commitment and scarcity heuristics do correlate with avalanche deaths. Even more interesting is the effect of experience and training. The familiarity and social proof heuristics correlate most strongly in those with advanced training in avalanche safety. The strength of the familiarity heuristic's effect is remarkable: advanced training appears to lead to clearly better decisions in unfamiliar situations, but equal or worse quality decisions in familiar situations.

This all applies to the decisions that systems operators make every day. In systems operations, much like in avalanche safety, there is a strong familiarity heuristic. In my experience, operators don't tend to reflect on the safety of operations they are familiar with as much as unfamiliar operations. This is logical, of course, because if we stopped to think through every action we'd be immobile. Still, it's critical to reevaluate the safety of familiar operations periodically, especially if conditions change.

First, most accidents happen on slopes that are familiar to the victims. While it's likely that people tend to recreate more often on slopes they are familiar with, the high percentage of accidents on familiar slopes suggests that familiarity alone does not correspond to a substantially lower incidence of triggering an avalanche.

The social proof heuristic (and its buddy, appeal to authority) are also common to systems operators. Things that multiple people are doing are seen as safer, despite evidence to the contrary. Like the familiarity heuristic, this one makes some sense on the surface. Successful completion of tasks by others is evidence of their safety. What is irrational is overweighting this evidence.

All of this suggests that the social proof heuristic may have some marginal value in reducing risk, but in view of the large number of accidents that occur when social proof cues are present it cannot be considered in any way reliable.

Finally, the commitment heuristic is our noble wish to be true to our word, to keep our promises and to get things done before its dark out. Committing to get work done is a very important social force - it's what operators are paid for, after all - but can lead to poor risk decisions. This is where I see very interesting overlaps with Jens Rasmussen's model of risk management. The commitment heuristic aligns well with what Rasmussen describes as the "gradient towards least effort* in systems operations.

There is great value in looking at the way that people in unrelated fields makes risk decisions and exercise heuristics, because it allows us to use our system 2 (in Kahneman's terminology) to train our system 1, and recognize where it might be leading us astray.
 Is there a CAP theorem for Durability? 2015-09-26T00:00:00+00:00 http://brooker.co.za/blog/2015/09/26/cap-durability
Is there a CAP theorem for Durability?

Expanding the taxonomy of distributed systems.

The CAP theorem considers only two of the axes of tradeoffs in distributed systems design. There are many others, including operability, security, latency, integrity, efficiency, and durability. I was recently talking over a beer or two with a colleague about whether there is a CAP theorem for durability (DAP theorem?). These are my thoughts.

What is durability?

To have a meaningful conversation, we need to talk about what durability is. Its typically given a few meanings:

Persistence of information to stable storage, to tolerate loss of in-memory (volatile) state. This is the D in ACID.

Loss of the data stored in a database. This is typically measured using population statistics. Annualized failure rate (AFR), and Mean Time to Data Loss (MTTDL) are typical, easy to understand, (but flawed1) metrics.

Loss of recently committed transactions or recently-written data.

On single-node systems, these topics are deeply connected. Persistence to stable storage is required to keep data around across crashes. RAID and backups2 are widely used to protect against permanent loss of the single system. Traditionally, non-zero RPO is tolerated on node failure.

Distributed systems can be different. Instead of having a single gold-plated node with its own great durability properties, distributed databases spread the risk out over multiple machines. That unlinks the topics of persistence to stable storage and loss of data, where systems can be tolerant to some number of node reboots without any stable storage.

For the rest of this post I'll define durability as "the ability to tolerate t node failures without losing data". It's a flawed but hopefully useful definition.

What has this all got to do with CAP?

The limits on consistency are well-known. CAP is one boundary in one system model and set of definitions, another (possibly more useful) one is from the all-time classic Consensus in the Presence of Partial Synchrony:

For fail-stop or omission faults we show that t-resilient consensus is possible iff N ≥ 2t + 1

What that means is that you can build systems that keep on going3 even if t things fail, as long as at least t + 1 things don't fail. It also means you can keep going in the majority side of a network partition, if one exists. In the Gilbert and Lynch total availability sense, that means the system is not available4. In the common sense, the system is still available for everybody on the majority side of the partition.

There's a similar definition possible for durability: "For fail-stop or omission faults, t-resilient durability is possible iff N ≥ t + 1".

The next step in developing the DAP theorem is to define failed. We quickly descend into rule-lawyering.

Alternative 1: Nodes that we can't talk to count as failed. If we're in a system of N = t + 1 nodes, and we can't talk to k other nodes, we can accept writes. That's because, in this state, we've already got k failures, so we only need to tolerate another t - k. That's not a very helpful definition.

Alternative 2: Nodes that we can't talk to don't count as failed. If we're in a system of N = t + 1 nodes, we can only accept writes if we can talk to another t nodes.

In alternative 1, you can stay common-sense available on both sides of a partition. In alternative 2, any partition causes unavailability in both senses. Neither is a very useful definition, and our DAP theorem doesn't seem useful at all.

Towards a useful rule

Abadi's PACELC could be a better fit for durability. Let's revisit Abadi's definition:

 if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?

Replacing C with our definition of D (the ability to tolerate t node failures without losing data), and defining A as the common-sense version of availability (at least some clients are able to make writes), we get PADELD.

 if there is a partition (P), how does the system trade off availability and durability (A and D); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and durability (D)?

That actually does seem to be helpful, in the sense that it could be used to have a real conversation about real systems. In the happy E case, the tradeoff between latency and durability could be between synchronous and asynchronous replication, or it could be between different write quorum sizes. Asynchronous replication reduces latency because fewer steps are required, or particularly expensive steps (like cross-WAN replication) are skipped. Smaller write quorums (for example, writing to 2 of 3 replicas) also reduces latency, especially outlier latency, because writes can be acked while replication is still proceeding to slower replicas. In both cases, a failure is unlikely to lead to complete data loss, but rather some non-zero RPO, where recent writes are more likely to be lost than colder data.

In the partition P case, the tradeoff is between availability and durability. The concerns here are the same as in the E case, and the implementation flavors will be very similar. The partition case is meaningfully distinct, because systems may either change behavior based on failure detection (choosing to lower durability during partitions), or may best-effort replicate but give up after some latency target has been breached.

PD/ED is a pure synchronous replication pattern, where writes are rejected if they can't be offered full durability.

PA/ED could be a system with either modal or latency-target based behavior that generally chooses durability, but may fall back to availability if that can't be achieved.

PA/EL is a pure asynchronous or quorum replication system, which offers a non-zero RPO for t failures at all times.

PD/EL appears to be meaningless.

PADELD may actually be a useful taxonomy of durability behaviors. Durability, at least if we only consider RPO and t-resiliency, is also a less subtle topic than consistency, so it may even be a more useful tool than PACELC in its own right.

Footnotes:

 Greenan et al's Mean time to meaningless does a good job of explaining why these metrics aren't ideal descriptions of true storage system behavior. They propose a different metric, NoMDL, which captures some of the missing subtlety but may be significantly more difficult to understand.

 Although backups are a kind of distributed replica.

 By keep on going I mean keep on doing the consensus thing.

 The total availability definition from Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services is "For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response." A more common sense definition is something like "For a distributed system to be continuously available, some requests received by the system must result in a response within some goal latency". Gilbert and Lynch's definition leads to a more beautiful CAP theorem, but probably a less helpful one.

 CALISDO: Threat Modeling for Distributed Designs 2015-06-20T00:00:00+00:00 http://brooker.co.za/blog/2015/06/20/calisto
CALISDO: Threat Modeling for Distributed Designs

Some steps towards a mnemonic threat model for distributed systems.

Threat modeling from the security field, and business impact analysis from the continuity management field, are powerful and influential ways of structured thinking about particular kinds of problems. The power of threat modeling comes from its structure. By imposing a structure on the thought process, we reduce the number of things that we miss, and make the information more analyzable and accessible. Two popular classic tools for structuring threat modeling are STRIDE and DREAD, both originally from Microsoft. While, on the surface, the mnemonics appear cheesy (what is this, the high school science fair?), in practice they are easy to remember, easy to use, and relatively difficult to misunderstand.

Can we apply the same kind of structured thinking to analyzing the trade offs in distributed systems we design?

CALISDO is my first attempt at a mnemonic for doing STRIDE-style modeling of distributed systems designs.

Consistency How do clients experience the consistency of data in the system?

Availability How do clients experience the availability of the system for operations?

Latency How long does it take for operations to complete? If the system is eventually consistent, how long does it take for data to be visible?

Integrity Under what circumstances could data be corrupted?

Scalability How does the system scale under load?

Durability Under what circumstances could data be lost?

Operational Costs What does it take to operate the system? How much will that cost?

For Consistency, the focus is on client-visible guarantees, in the sense typically used by distributed systems (i.e. more closely related to A and I than C of ACID). Key questions:

When is data visible to clients?

How are concurrent updates handled?

Are operations atomic from the client's perspective?

Can the effects of rolled-back or aborted transactions be seen by other clients?

For Availability, the focus is on how clients experience the ability to interact with the system. This obviously includes classic CAP- and PACELC-style trade offs, but practical concerns are likely to be as important in real systems. Issues such as redundancy, failover, load balancing, infrastructure diversity and hardware quality can all have a significant influence on availability.

Latency focuses on how much time clients have to wait for operations to complete. Within datacenters, and local areas like AWS regions, compute and storage performance typically dominate. For systems spread around large areas of the world, such as websites and CDNs, networking and locality concerns may dominate. Latency analysis should consider both the happy case when everything is working, and degradation behavior under conditions such as failed dependencies and network packet loss. Issues such as data buffering, caching and pre-computation are also important to latency.

Data Integrity is critical to the client experience of distributed systems. Analysis in this area should include both end-to-end properties (such as checksums, error-correcting codes and authenticated encryption modes) and local properties (such as the BER and UBER of storage devices and channels). Key questions should cover how often corruption is expected to happen, how it is detected, and how its existence is communicated to clients. Integrity analysis should also recognized that some types of data (typically indexes and metadata) can have high leverage, effectively turning small amounts of corruption into wide-scale issues. Extra attention should be payed to integrity of this data.

Scalability looks at how the system's behavior changes as load increases. Attention should be paid to two parts of the scaling curve: the rise in goodput in response to load offered up to saturation, and the drop in goodput with increased load beyond saturation. Scalability should consider scale-up (larger hardware), scale-out (spreading load across components) and load allocation (how load is distributed across components). In nearly all real systems, scalability is limited by either bottlenecks in the architecture, or by hot-spotting caused by uneven distribution of load.

Durability deals with data loss. Many distributed systems are stateless, or only handle soft-state that may be lost without major cost. Falling into one of these two categories should be seen as a goal. Systems should only store durable state if they have no other sensible choice. Durability requires attention to the failure rates of individual storage components (hard drives, SSDs, etc) and redundancy used to handle these failures (replication, RAID, etc). Attention should be paid to the blast radius of failures, and potential causes of correlated failure (such as sharing an enclosure). Recognition of the role of latent failures on durability is very important.

Operational Cost covers both the human cost of operations, and the hardware and services cost of operating the system. On human operations, particular attention should be given to single points of failure, where a human operator needs to take action to prevent or end an outage. Human costs also include deployment, updates and upgrades and root-cause investigations. Hardware costs and services costs dominate the overall cost of operating large systems, but human costs often dominate for smaller systems. System designers must be aware of decisions that trade one operational cost for another.

All of these categories are inter-related. The theoretical tradeoffs between availability and latency are well known, but in practice also involve scalability and durability. Similarly, latency and scalability are often in tension: architectural decisions taken to improve scalability can often add latency. Operational costs are typically in tension with all the other categories. There are also some areas where different categories pull together. For example, good design decisions for durability are often similar to good decisions for availability and integrity.

It's also worth noting that CALISDO doesn't include many critical security properties. Analysis of the security properties of a system is also needed, and may interact with decisions around integrity, scalability and operational cost.

CALISDO isn't an exhaustive list of design concerns for distributed systems, but it seems like a good start at not forgetting everything obvious. Taking each aspect of a system design - along with the end-to-end system - and breaking it down into these categories, makes it harder to miss obvious deficiencies, mistakes, and oversights.
 Sodium Carbonate, and Ramenized Pasta 2015-05-24T00:00:00+00:00 http://brooker.co.za/blog/2015/05/24/sodium-carbonate
Sodium Carbonate, and Ramenized Pasta

Doing chemistry with baking soda, cabbage and an oven.

Ramenizing things is super popular right now. The idea seems to have originated from the Ideas In Food crew, and is obviously adapted from the practice of making Ramen in Japan and similar alkaline noodles in China. In those recipes, the secret is incorporating an alkaline ingredient (such as kansui into the dough when making noodles). This leads to a tender and springy noodle, without egg or other proteins. Ramenizing is an attempt to cheat, to introduce the ramen texture into western pasta, rice, and other foods.

Most people online seem to be doing their ramenizing with Sodium Bicarbonate, the least interesting of all bases. It's the Fred Rogers of bases: always friendly, always useful, and you don't mind having it around your home. Baking soda's mild-manneredness is good for safety, but not so good for actually being an effective base. What else could we use?

First, there's Lye. Lye has a long tradition as a kitchen ingredient, most notably for making pretzels. Lye is scary. You don't want to mess with Lye. Then there's slaked lime, or calcium hydroxide. It's also popular in the kitchen, both as an alkali and as a source of calcium for firming up pickles. Slaked lime's biggest claim to fame is as the motive power behind Nixtamalization, the magical process that both softens the corn husk and staves off malnutrition. Having slaked lime around the house is a bit less scary than lye, but still not common.

Finally, there's sodium carbonate. This is baking soda's big brother, a powerful alkali with a long history as a food ingredient. Sodium carbonate grabbed the attention of the online food world back in 2010, when Harold McGee wrote about making it at home. Now, I'm not somebody to doubt Mr McGee. On Food and Cooking is one of my favorite books, and an endless source of fascinating information about food. It's also a useful source of information to share with the kind of person who needs some encouragement to go home after a dinner party.

Making sodium carbonate at home is super simple. I took 11g (about 2 teaspoons) of baking soda, spread it out on a wide glass dish, and baked it in the oven at 150 Celsius (300 f) for about an hour. That yielded about 7g of a fine, white powder. The problem with fine, white powder is it could have been anything. Most likely, it could still have been sodium bicarbonate.

The first test is to see if the masses work out. The reaction I'm going for is:

2 NaHCO3 → Na2CO3 + H2O + CO2

mass-wise, that's 168 parts of sodium bicarbonate to 106 parts of sodium carbonate, and 62 parts of things that will evaporate away. Assuming I started with pure sodium bicarbonate, I should have ended up with 6.94g of sodium carbonate. Close enough.

The best test would be to test the pH of the ramenizing solution I made from the salt. Unfortunately, I don't own any kind of pH measuring device. I had to turn to every kid's favorite food-grade non-toxic indicator: red cabbage water. Making red cabbage water is super easy: start with that red cabbage that's been lying in your fridge since the 90s, chop it up fine, fill a cup with it, top up with water, and microwave until warm. Depending on the age of your cabbage, the resulting smell is either fairly pleasant, or disastrous. Either way, ignore it. The smell's not important. It's all about color.

I made two solutions, both 1% sodium xcarbonate and 0.5% salt. Then, I dropped a quarter teaspoon of each into separate glasses of cabbage water. A control glass got a ml of StarSan, which turned the cabbage stunning pink. The bicarbonate glass stayed stubbornly purple. The sodium carbonate glass went a beautiful baby blue. Success!

The next step was to soak pasta in the two solutions. After two hours, the dried pasta had become pliant and stretchy while remaining firm in both solutions. One of the things people look for in alkali noodles is a yellow color. The carbonate pasta was much yellower, having taken on the deep yellow hue of egg pasta. The bicarbonate pasta remained wan.

Soapiness is probably not desirable in a pasta dish, so I washed both down a few times before boiling for three minutes in plenty of salted water. Both samples were firm, with a bit of chewiness but none of the stick-to-your-teethiness of under cooked pasta. Of the two I preferred the carbonate pasta, a little springier and stretchier, with no signs of being soft. My test subject preferred the bicarbonate pasta, citing less chew. On looks, the yellowness of the carbonate sample won out over the pallid bicarbonate one.

The final bowl, when combined with a meat sauce and some fresh basil (thanks Aerogarden, for my unending basil glut), was excellent. The texture of the ramenized pasta is different from both fresh and dried pastas. It's springier and chewier, which I enjoyed. The end product would probably be more at home with a broth than a chunky meat sauce, but it was still good.

An experiment I'll repeat.
 The Zero, One, Infinity Disease 2015-04-11T00:00:00+00:00 http://brooker.co.za/blog/2015/04/11/zero-one
The Zero, One, Infinity Disease

Numbers are important.

"The only reasonable numbers are zero, one and infinity." (Bruce MacLennan)

Rules and heuristics are important. Within our own heads, they are mental shortcuts we use to save ourselves from needing to reason everything out from first principles. Between us, they are devices that we can use to communicate ideas and share complex concepts. Rules of thumb are named patterns of thinking, pointers to complex discussions that can be used in place of talking things through from the beginning every time. They have huge power. Every so often, we should go through our rules and heuristics and throw out the ones that hurt more than they help.

I have a candidate: the zero-one-infinity rule. In spirit, zero-one-infinity is valuable. It counsels against arbitrary limits, and points out that arbitrary limits are a strong hint that system or piece of code was poorly considered.

The value is lost when the word arbitrary is forgotten.

Numerical instincts are a critical part of the engineer's toolkit. Having the ability to understand the scale and size of a problem, to estimate quickly, and think in terms of upper and lower bounds is exceptionally useful for both science and engineering. This includes the ability to look at a number, or graph, or formula, and quickly decide whether it looks about right or definitely wrong. Many of the best engineers and scientists (most famously Enrico Fermi) have numerical intuition as a strength, or even as a superpower. When it's used well, intuition is irreplaceable. It tells us where to measure, where to calculate, and when to calculate or measure a second time. It's the pure distillation of hard experience into numbers.

Numerical intuition is closely related to another very useful tool: statistical intuition. Statistical intuition is a feeling about how often things happen, what the distribution of things looks like, and how likely it is that the unlikely will turn out to be true. Statistical intuition is often hard won, and can be very easily fooled. Humans, as a species, aren't very good at intuitively understanding statistical concepts. Still, the best engineers and scientists keep practicing. They can guess the general shape of distributions, and build general effects (like the laws of large and small numbers) into their everyday thinking.

Statistical and numerical intuition are most useful when they work over a large range of scales. Experts make a mental shift from linear to exponential estimation as numbers get to big or too small, from multiplying to adding, and from dividing to subtracting. They discard the mantissa, and use only the exponent.

These intuitive strengths give designers something of a superpower. They become good at finding solutions that don't make sense at one or zero, and would never work at infinity, but are perfectly suited to their actual range of uses. They recognize where systems are far from their physical limits, which can be an opportunity to push for lower costs or more performance. They can estimate how close bottlenecks are, and where optimization will really matter.

Zero-one-infinity is often taken to counsel against numerical instincts.

Beyond instinct and intuition, absolute numbers are critical to computing. Absolute values, not arbitrary values but real ones, rule the physical world around us. Real limits of storage, bandwidth and latency dominate every field of computing. Real customer requirements, of numbers of entries and request rates, and request patterns, rule over the businesses we build with computers. Computing lives in a world of numbers.

Zero-one-infinity is often taken as counsel against numbers.

This is dangerous in two ways. First, it limits our ambitions of solving real-world problems. The ghost of infinity haunts us. There are very relevant, real problem domains where solving problems like the traveling salesman, program termination or exact cover are very practical. Not even domains where we can accept approximate solutions, but domains where we can compute exact solutions. When we talk about infinity, we run the risk of forgetting that there's huge value in solving problems at finite scales.

The second problem is more subtle. The success of zero-one-infinity and friends, perhaps exacerbated by our habit of educating all computing people as computer scientists, makes it unfashionable, uncool or unacceptable to talk about real limitations. None of the physical systems we build can scale to infinity on any axis, but it's hard to shake the feeling that we should be embarrassed about that. Instead of finding and documenting the limits of our systems, we pretend they don't exist. Perhaps if we don't talk about physical limits, we can keep pretending we don't have any.

That's the core danger of zero-one-infinity. The most important questions about the scaling of systems are "what are the limits?", "how do I know when I'm close to the limits?", "what happens when I hit the limits?". The core question about each number should be "where did this number come from?", not "why not infinity?". Of course it can't be infinity. It's never going to be infinity. Let's stop pretending it can be, and have a real conversation about numbers.

 Notes:

apy pointed out SQLite's limits page, which makes a similar point.

 Historical Context

Bruce MacLennan, the originator of the rule, was kind enough to get in contact with me about this post. He said:

Of course, the Zero-One-Infinity Principle was intended as a design principle for programming languages, and similar things, in order to keep them cognitively manageable. I formulated it in the early 70s, when I was working on programming language design and annoyed by all the arbitrary numbers that appeared in some of the languages of the day. I certainly have no argument against estimates, limits, or numbers in general! As you said, the problem is with arbitrary numbers.

I don't think I used it in print before I wrote my 1983 PL book. Dick Hamming encouraged me to organize it around principles (a la Kernigan & Plauger and Strunk & White), and the Zero-One-Infinity Principle was one of the first. (FWIW, the name "Zero-One-Infinity Principle" was inspired by George Gamow's book, "One, Two, Three… Infinity," which I read in grade school.)

 How Amazon Web Services Uses Formal Methods 2015-03-29T00:00:00+00:00 http://brooker.co.za/blog/2015/03/29/formal
How Amazon Web Services Uses Formal Methods

Now in CACM.

How Amazon Web Services Uses Formal Methods is in this month's Communications of the ACM. This version isn't changed much from the versions that have been online for a few months, but it's great to see it get some more attention.

In the same issue of CACM is Leslie Lamport's Who Builds a House without Drawing Blueprints?. Fans of his writing won't find anything new in there, but it's a perspective and opinion that I love to see gain more traction.

We think in order to understand what we are doing. If we understand something, we can explain it clearly in writing. If we have not explained it in writing, then we do not know if we really understand it.

And the conclusion:

Thinking does not guarantee that you will not make mistakes. But not thinking guarantees that you will.

It's a very good take on the subject. As our experiences at Amazon have shown, specification can be an extremely powerful tool in the system designer's and programmer's toolbox. It's even more useful as a team member, where the ability to communicate particularly tough ideas formally and concisely really helps collaboration.

Other good formal methods reading this week:

A post by Mark Callaghan about using Spin for MySQL development. I haven't spent as much time with Spin (or Promela) as I would like, but it's very interesting.

Adrian Colyer wrote a good mini-series this week on SPL, one looking at deep bugs in distributed systems and the other at the background of SPL. He finished up with Lineage-Driven Fault Injection. All three posts, and the papers behind them, are good reading.

Not really from this week, or this decade, or century, but still worth it - Lamport's article brought me back to What Good is Temporal Logic?, one of my favorite papers from him. It's extremely interesting to see how his thinking, and chosen framing, has evolved in the last 32 years.

 Jitter: Making Things Better With Randomness 2015-03-21T00:00:00+00:00 http://brooker.co.za/blog/2015/03/21/backoff
Jitter: Making Things Better With Randomness

Jitter is a good thing.

Two weeks ago, I wrote an article titled Exponential Backoff and Jitter for the AWS Architecture blog. It looks at OCC in particular, but the lessons are applicable to all distributed systems. The bottom line is that exponential backoff is good, but not sufficient to prevent both wasted time and wasted effort.

Communication in distributed systems isn't the only place that adding randomness comes in handy. It's a remarkably wide-spread idea, that's found use across many areas of engineering. The basic pattern across all these fields is the same: randomness is a way to prevent systematically doing the wrong thing when you don't have enough information to do the right thing.

One classic distributed systems example is in the paper The Synchronization of Periodic Routing Messages (thanks tptacek). Sally Floyd1 and Van Jacobson2 simulate synchronization emerging in previously unsynchronized systems communicating over a network. This leads to short-lived spikes in contention, and other correlated effects on the network. Their solution is to add randomness, which breaks the loop that creates synchronization. While the exact set of protocols and technologies they look at is very 1990s, the lessons are timeless.

Closely related to these uses of jitter is dither, or adding noise to prevent artifacts when quantizing. Dither is most visible in images, where it can make a huge difference in quality3:

Technically, dither is a way to remove correlation between quantization error and the signal being quantized. That sounds complex, but the underlying concept is extremely simple. Imagine a simple system where we're rounding a vector of reals to the nearest integer. If those reals are nicely distributed, it works well, but sometimes it works very poorly. If we start with

[ 1.4, 1.4, 1.3, 1.4, 1.2, 1.4, 1.1, 1.0, 1.4 ]

it rounds to

[ 1, 1, 1, 1, 1, 1, 1, 1, 1 ]

leaving the error

[ 0.4, 0.4, 0.3, 0.4, 0.2, 0.4, 0.1, 0.0, 0.4 ]

There are two problem here. We've introduced a bias, because all the errors are positive. The error also looks a whole lot like the signal, and there's clearly information in the signal that's left in the error. The solution is to add some noise, the simplest case being uniform noise of half a quantization level (in our case, between -0.5 and 0.5).

[ 1.52, 1.09, 1.34, 1.04, 1.31, 1.83, 0.93, 1.49, 1.67 ]

After rounding, we're left with the error

[ -0.6, 0.4, 0.3, 0.4, 0.2, -0.6, 0.1, 0.0, -0.6 ]

Which has much less bias (-0.6 versus +2.6), and the remaining noise doesn't look like the underlying signal. That's a good thing if you care about spectral artifacts.

One point of talking about jitter and dither together is to point out the similarities. In both cases, we're looking to spread out our error. In the case of jitter it's error that we have because we don't have complete knowledge of our distributed system. In the case of dither it's error we're introducing to have the opportunity to throw out some information. The other point is to invite thought about the advanced techniques of dither (such as error diffusion and noise shaping) and whether they have useful analogs in distributed systems.

Footnotes:

 Apparently "the eighth most highly cited researcher in all of computer science", which is impressive.

 Every time I hear Van Jacobson's name, I wonder what his first name is.

 Images from Wapcaplet on wikimedia commons.

 Electoral Trouble in Sybilania 2015-03-03T00:00:00+00:00 http://brooker.co.za/blog/2015/03/03/sybil
Electoral Trouble in Sybilania

An Small Town Struggles To Achieve a Fair Vote.

Sybilania1 is a small town on the banks of the Orange river, near where where the river turns North toward the Augrabies falls. The main street runs sleepily from the exclusive retirement communities on the river to the grounds of the Northern Cape Rugby Club, champions eight years in a row. On the way, it passes some knitting shops, the church, the grocer, Piet's print shop, and the cavernous town hall. Like every small town, there is no greater event in Sybilania's calendar than the local elections. Everybody wants to be, or at least know, the mayor.

The recall of Mayor Piet had rocked the town. Not so much the recall itself - nobody had liked him anyway - but the reason. Electoral fraud! It was a crime against politics, a crime against morals, and a crime against the very ideals of democracy. Bridge games, golf courses and changing rooms were all filled with talk of the next election. Sybilania's political scene was dominated by three parties: the Rugby party, populated by the town's fit and athletic; the River party, populated by the wealthy retirees who lived on spacious estates near the water; and the Bridge party, dominated by the town's regional-champion card enthusiasts. The three parties didn't agree on much, but they did agree that there would be no ballot stuffing ever again.

You see, that summer the town had voted by mail for the first time. Piet, playboy owner of Piet's print shop, had won in a landslide. The town had been surprised, both by Piet's victory, and the record turnout of three times the town's estimated population. An electoral commission was formed, and tasked with finding a fair way to run elections. They had their work cut out for them. The local branch of the Home Affairs had closed in the '30s, and nearly nobody had ID.

The first commission-guided election was held at the high school. The school's fence had been collapsing for years, and the election was a perfect time to form a work party. Everybody in town reported to the school early one morning, dug holes, and raised posts. The person who dug each hole was allowed to carve the name of a candidate onto each post. A strong and athletic young lady from the rugby club took the mayor's office that year, in a landslide. The other parties demanded that the electoral commission tear down the proof-of-work2 system. They left the fence standing.

The next election happened in a small room at the office of the town surveyor. The town had been divided into a fine grid, the title for the land each grid segment was on was consulted, and its owner was called to ask for their vote. The process ran well into the night, and most of the next day. By mid-afternoon, the mayor from the River party was confirmed. While they knew better than to demand another recall election, the community demanded a replacement for proof-of-stake.

The most recent election was run on the rugby club's main field, right between the posts (which, incidentally, hold the Guinness record for tallest posts in the Southern Hemisphere). Everybody in town arrived wearing a mask (to make sure the vote was secret), and arranged themselves in a wide circle around the field. In turn, each citizen shouted out the name of a candidate, followed by the tally they heard from the previous voter, updated with their vote. As the vote went around the ring, everybody could hear that the tally was fairly kept, and not cheating occurred. The crowd fixed a few mistakes over the course of the afternoon, but left happy that the election was free and fair. The Bridge party won comfortably. A few dissenters still complain about seeing the buses4 of bridge clubs from neighbouring towns in the car park that day, but nothing has ever been proven.

 Footnotes

 The Sybil Attack by John R. Douceur is a very readable paper, almost definately more readable than this fiction. I recommend it.

 Ralph Merkle proposed the use of puzzles for proof-of-work, because it's hard to make computers dig holes.

 You could probably call the weaker people in the community strength-challenged imposters.

 New personalities for Sybil can come from either a printing press or a bridge-club bus.

 Does Bitcoin Solve Byzantine Consensus? 2015-02-28T00:00:00+00:00 http://brooker.co.za/blog/2015/02/28/bitcoin
Does Bitcoin Solve Byzantine Consensus?

An Interesting New Publication on Bitcoin and Consensus.

The Bitcoin community is a fascinating mixture of political idealists, technology enthusiasts, entrepreneurs, investors and others. One group that's increasingly prominent is distributed systems researchers, attracted to some of the interesting problems around Bitcoin and the blockchain. There's plenty of interesting work to come, but some valuable research has already been done. Much of this work focuses on the theoretical core of bitcoin, and shows real progress towards answering concerns about bitcoin's safety and liveness bounds.

In The Bitcoin Backbone Protocol: Analysis and Applications, Garay, Kiayias and Leonardos write about the core of Bitcoin, which they call the backbone. The argument for the correctness of the core of bitcoin from Satoshi's original paper is far from fulfilling:

The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it. If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains.

Garay et. al. attack this core argument directly, and analyze the exact safety and liveness properties of the protocol. The contribution that's going to launch a million online arguments is that bitcoin does not solve the Byzantine agreement problem1:

This is because in case the adversary finds a solution first, then every honest player will extend the adversary's solution and switch to the adversarial input hence abandoning the original input.

and

Nakamoto's protocol does not quite solve BA since it does not satisfy Validity with overwhelming probability.

Their argument hinges on the validity property of Byzantine agreement (or, rather, strong validity 2), and showing that the chosen value may not be one of the inputs to an honest player. In their definition of Byzantine agreement, agreements are only valid if they pick the input of one of the honest players. That doesn't appear to be true of the bitcoin protocol as implemented.

Reducing the practical importance of this result, they also prove a chain quality property. This property puts an upper bound on how often a dishonest player's entry will be added to the chain 3. That's obviously critically important for liveness, and preventing denial-of-service against honest players.

I find this kind of research on Bitcoin very interesting. The community has very strong opinions on the safety and liveness of bitcoin. Until recently, there was little evidence to support these opinions. Proving bitcoin's distributed systems properties is very useful, even though there are still many interesting questions around topics like scalability and economic incentives.

Footnotes

 See Easy Impossibility Proofs for Distributed Consensus Problems for very approachable definitions of the problem, and obviously The Byzantine Generals Problem for the classic definition.

 They cite Neiger Distributed Consensus Revisited, who provides a definition of strong validity (stronger than Fischer, Lynch and Merritt's) and a nice justification for why that's desirable.

 Obviously related to well known selfish mining attacks.

 A Quiet Defense of Patterns 2015-01-25T00:00:00+00:00 http://brooker.co.za/blog/2015/01/25/patterns
A Quiet Defense of Patterns

Twenty years late to the party.

I find myself coming back to Patterns of Software every few years. I think about it often, mostly when I am doing code reviews. One great part is the front matter: a short debate between the author and Christopher Alexander, first author of the much-celebrated A Pattern Language.

The elements of this language are entities called patterns. Each pattern describes a problem which occurs over and over in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice. - A Pattern Language, Alexander et al

In some programming circles, Alexander's book is treated with religious reverence. A kind of Tao Te Ching of oblique anecdotes. Concrete enough to to sound solid, but not enough to be actionable. A source of in-jokes and unhelpful advice. It's also a source of conflict for this same group, because it was an inspiration for something widely reviled: the Gang of Four book.

No design patterns are necessary. In any language. - Jan Hudec

When Design Patterns first came out, back in the mid-90s, it captivated me. My access to technical books was limited, and I didn't have a copy of the book itself, but for a short time I was obsessed with the debate about it. It incited anger, it incited self-righteousness, it incited smugness about missing language features. For each of these loud critics, it seemed to have an equal and opposite supporter. From the community's reaction, I couldn't wait to read Design Patterns. Judging by the controversy, I felt like it must be a deeply important book, with something profound to say about software and those who build it.

As for literary criticism in general: I have long felt that any reviewer who expresses rage and loathing for a novel or a play or a poem is preposterous. He or she is like a person who has put on full armor and attacked a hot fudge sundae or a banana split - Kurt Vonnegut

In my mind, Erich Gamma was a Martin Luther figure. He had written a book that was creating a whole new church, ripping open old wounds and providing new courage to both sides. Imagine my disappointment when I finally got my hands on a copy. Instead of Luther's protest, I found a taxonomy written by stamp collectors.

My overall bias is that technology, science, engineering, and company organization are all secondary to the people and human concerns in the endeavor. Companies, ideas, processes, and approaches ultimately fail when humanity is forgotten, ignored, or placed second. Alexander knew this, but his followers in the software pattern language community do not. Computer scientists and developers don't seem to know it, either. - Richard P Gabriel

Gabriel is right about how many of us have missed the point of Alexander's work. We've seen it as an exercise in taxonomy, or phylogeny, and missed the fact that it's primarily a human, rather than technical, endeavour. We should go looking for that aspect of it again, because the human side of our field is broken. We could use all the help we can get. We've also missed the range of scale of Alexander's work, concerned with patterns from the deeply technical to broad ideas with scope across entire societies. To live up to Alexander's vision in our own field we would need to be doing something much deeper than the Gang of Four did. Design Patterns isn't software's A Pattern Language.

The more we can feel all the connections in the language, the more rich and subtle are the things we say at the most ordinary times.

Design Patterns isn't software's A Pattern Language. It doesn't have to be. The concept is much more useful.

The most obvious way that it's useful is in enabling high-bandwidth conversations by building shared context. Two people with a common set of patterns find it easier to communicate - even if the goal is to reject certain patterns - than those without one. Another advantage, and common area of criticism, is in education. Teaching common patterns makes people more effective communicators, and naming and classifying patterns makes them easier to teach.

A third advantage, perhaps less obvious, is that writing down our shared context lowers the barrier to entry. High bandwidth conversations are needed for efficient teamwork. Effective teams build, and use, a shared context. This is healthy for the team, but can make it difficult to break in. Context can become an impenetrable shield that makes it more difficult to bring others into the group. Whether we intend it or not, this can make groups appear exclusive or exclusionary.

Functional languages are extremely expressive. In a functional language one does not need design patterns because the language is likely so high level, you end up programming in concepts that eliminate design patterns all together. - Slava Akhmechet

Describing and naming patterns is a powerful way to build context, but is not exhaustive. There is no risk of getting to the point where we have described all patterns, and reduced all communication to references to patterns. Context can't replace communication. At the same time, a list of common patterns isn't a monotonically growing thing. Patterns are frequently split, combined, superseded, replaced, destroyed or forgotten.

Patterns themselves are also dependent on context. Some apply well to object-orientated programming, some to functional programming, some to running design meetings, some to mentoring and some to building large-scale systems. This isn't a weakness of the idea of patterns, but a strength. They are sensitive to scale, too. Some patterns of success at one scale, or in one context, may be patterns of failure at another scale, or in another context. Claims that a particular list of patterns is complete, either in support or criticism, are likely wrong.

16 of 23 patterns have qualitatively simpler implementation in Lisp or Dylan than in C++ for at least some uses of each pattern. - Peter Norvig

While recognizing different scales of patterns is critical, they can't be totally ordered by scale. The debate around patterns-as-flaws in programming languages appears to make this mistake: claiming superiority by demonstrating that some patterns are irrelevant due to their scale. This school of thought then claims that the patterns at their scale and above are not indeed patterns, because they have no use of patterns.

This thinking is flawed in two ways. The glaring flaw is in the restrictive definition of patterns. The more subtle flaw is in not recognizing that they have patterns of their own at similar scales to the ones that were rejected. Abstraction is extremely powerful, but operating at higher levels of abstraction doesn't appear to imply higher productivity or reduced needs for patterns as a medium for sharing context.

Design patterns are a form of complexity. As with all complexity, I'd rather see developers focus on simpler solutions before going straight to a complex recipe of design patterns. - Jeff Atwood

Shared context and communication is important, but so is programmer productivity. As we well know, productivity comes from more than the ability to type fast. More than any other factor, productivity comes from solving the right problems. Sometimes that means using solutions that exist in libraries or the platform. More often that means re-using solutions we've found before, or ones we've learned from others. Being productive requires two things: a rich mental library, and the skills to access that library.

A rich mental library can only be built by experience. Experience isn't best accumulated with, or measured with, time. Instead, it's built by solving problems and reading and understanding the solutions of others.

As important as the size of the library is the skills to access it. The first step is matching the current problem to the library, or pattern matching. The second step is taking past solutions and adapting them to the exact context. This is seldom a mental (or physical) copy-and-paste exercise. The third part of using this mental library of patterns is taste. Taste means knowing when not to use a pattern. It means carefully adapting patterns to the context of the problem.

Thinking doesn't guarantee that we won't make mistakes. But not thinking guarantees that we will. - Leslie Lamport

I love programming. I've fallen in love with the craft of programming. I see similar love in the criticism of design patterns (and formal methods, but that's another topic). That love of craft is great, and important.

When it comes to building working software in the long term, the emotional pursuit of craft is not as important as the human pursuit of teamwork, or the intellectual pursuit of correctness. Patterns is one of the most powerful ideas we have. The critics may be right that it devalues the craft, but we would all do well to remember that the craft of software is a means, not an end.
 Make Your Program Slower With Threads 2014-12-06T00:00:00+00:00 http://brooker.co.za/blog/2014/12/06/random
Make Your Program Slower With Threads

How much do context switches matter?

Years ago, while taking a numerical methods course, I wrote some code to calculate the expected number of shared birthdays in a group. The code is very simple: each attempt constructs a vector of N birthdays, then counts the duplicates. The outer loop runs millions of attempts, and calculates the mean number of shared birthdays across all the samples. It's little more than a tight loop around a pseudo-random number generator.

I was also learning about threading at the time, and decided that I could speed up my program by running it on the lab's shiny dual-core machine. I knew that communicating between threads was expensive, so I had each of my threads calculate their attempts in parallel, and merge the results right at the end. I was expecting a great speedup. Much to my disappointment, though, the multi-threaded version was slower. Much, much, slower.

Much like the birthday paradox runs counter to our intuition about statistics, the behavior of bad multi-threaded programs runs counter to our intuition about computer performance. We're used to computers being much faster than they used to be, and single-threaded efficiency mattering less than it used to in most cases. Counter to that intuition, the gap between good and bad multithreaded programs has gotten worse over time.

To illustrate just how bad it can be, I replicated my program from back then. It's not much more than a multi-threaded tight loop around random(3). It's nice and quick single-threaded: running 10 million attempts in under 7 seconds. Going up to two threads makes it a bit faster, down to less than 6 seconds. When we hit three threads (on my four core Haswell E3-1240), it all goes horribly wrong:

To figure out what's wrong, we can turn to Linux's excellent perf tool. Running the 1-thread and 4-thread versions with perf stat make it obvious that something's going on. For 1 thread:

 3,788,352 L1-dcache-load-misses #0.03% of all L1-dcache hits 43,399,424,441 instructions #1.46 insns per cycle 734 context-switches

and for four threads:

 4,110,904,396 L1-dcache-load-misses #6.88% of all L1-dcache hits 248,853,610,160 instructions # 0.51 insns per cycle 15,993,647 context-switches

Two things are going wrong here. One is that we're seeing a more L1 cache misses with more threads, but the bigger issue is that we're seeing a whole lot more context switches. The effect of both of these is visible in the much lower instructions per cycle of the second version. There's no nice constant for the cost of a context switch, but a good modern estimate is around 3μs. Multiplying 3μs by 16 million context switches gives 48 seconds, which is a good hint that we're headed in the right direction. So, what's causing the context switches?

Back to perf, this time running perf record on the processes, followed by perf report. First, the top few rows for the single-threaded version:

# Overhead Command Shared Object Symbol # ........ ........ .............. ........................ 62.01% birthday libc-2.19.so [.] msort_with_tmp.part.0 11.40% birthday libc-2.19.so [.] __memcpy_sse2 10.19% birthday birthday [.] simulate

We're spending 62% of the time sorting the array, which is used to find the duplicates. That's about what I would have guessed. What about the version with four threads?

# Overhead Command Shared Object Symbol # ........ ........ ............. ............ 46.80% birthday [kernel.kallsyms] [k] _raw_spin_lock 8.86% birthday libc-2.19.so [.] __random 3.42% birthday libc-2.19.so [.] __lll_lock_wait_private 3.23% birthday [kernel.kallsyms] [k] try_to_wake_up 2.95% birthday libc-2.19.so [.] __random_r 2.79% birthday libc-2.19.so [.] msort_with_tmp.part.0 2.10% birthday [kernel.kallsyms] [k] futex_wake 1.46% birthday [kernel.kallsyms] [k] system_call 1.35% birthday [kernel.kallsyms] [k] get_futex_value_locked 1.15% birthday [kernel.kallsyms] [k] futex_wait_setup 1.14% birthday [kernel.kallsyms] [k] futex_wait

Well, that's suspicious. There aren't any locks in my code, but there are a whole lot of references to locks in the trace. raw_spin_lock is obviously a candidate, and it's suspicious to see so many futex-related calls. Something's taking locks, and the fact that random is near the top of the list makes it a likely candidate. Before we dive in there, though, let's confirm that we're doing a lot of syscalls:

sudo perf stat -e 'syscalls:sys_e*' ./birthday

Which spits out a long list of system calls, most (like mmap) with just a handful of hits. There are two huge outliers:

46,889,267 syscalls:sys_enter_futex 46,889,267 syscalls:sys_exit_futex

That confirms it, something's taking a lot of futexes. Knowing whether it's random or not requires a dive into the glibc source, which nearly instantly reveals something suspicious:

 /* POSIX.1c requires that there is mutual exclusion for the `rand' and `srand' functions to prevent concurrent calls from modifying common data. */

And, just a little bit further down:

 __libc_lock_lock (lock); (void) __random_r (&unsafe_state, &retval); __libc_lock_unlock (lock);

Getting rid of the locks means getting rid of one of two things: shared state, or the necessity to prevent concurrent modification to that state. It seems like the former is easier: reasoning about a data-race-safe PRNG is tricky. There are a many good ways to get rid of shared state in the PRNG. Linux has one particularly convenient way: the C library exposes a reentrant random number generator called random_r (which is used by random, as you can see from the snippet above). Dropping random_r in place of random has an amazing effect:

As expected, the context switches are way down and instructions per cycle is nicely improved:

 4,166,540 L1-dcache-load-misses # 0.04% of all L1-dcache hits 40,201,461,769 instructions # 1.43 insns per cycle 572 context-switches

I recognize that spinning on a tight loop on random is a contrived example, but it's not too far away from reality. Many programs that multi-thread for performance end up with library or system calls inside relatively tight loops. Our intuition about these things tends to follow Amdahl's law. At worst, it's tempting to think, these things count as a non-parallel portion of code and lower the maximum achievable parallel speedup. In the real world, though, that's not the case. Multi-threaded programs can, and very often do, run much more slowly than the equivalent single-threaded program.

It's just another thing that makes writing multi-threaded code difficult.
 Two Farmers and Common Knowledge 2014-11-30T00:00:00+00:00 http://brooker.co.za/blog/2014/11/30/two-farmers
Two Farmers and Common Knowledge

A legislative solution to a technical problem.

When their beloved father passed away, Jan and Marie inherited his famous wine estate. Jan and his family were given the historic homestead and half the grape harvesting equipment. Marie's family were given the other half, and a graceful home with stunning views down a craggy valley in the Bottelary Hills. As a final practical joke, the old man put strange condition into his will: one small vineyard was split between them, and they could only keep their farms if they met once a year on the same morning with all their inherited equipment to harvest the grapes together. The will insisted that they meet together at the vineyard, at a time when the grapes were perfectly ripe.

The first few years went well. When either decided that the next day would be right for the harvest, they would send a farm worker on his bicycle to tell the other. Farm workers are highly reliable, and they harvested simultaneously for many years. Then, one year around Christmas, a Karaoke joint opened the the village between the two homes. It's a poorly kept secret that farmers and farm workers love Karaoke, and the temptation to drop in to croon along with Sinatra often turned out to be too strong for the passing bicycling farmer worker. The workers loved karaoke so much, they could sing essentially forever.

In early July of the next year, Jan and Marie met to make a plan for that year's harvest. Their farm's remote locations meant that the telephone was out of the question, and SMS and email were yet to be discovered. They needed some way to make their cycling workers reliable again, and that meant finding a technical solution to the problem.

"Ok," said Jan. "All you need to do is send another message back when you get my message. When I get that message, I know you got my message."

"Don't be dumb Jan. What if that one doesn't arrive?"

"Oh. Then you need to send a message back saying you got that message"

"Ja. Then you know that I know that you know about the harvest, and I know that you know."

"But if that one doesn't come, then you don't know that I know that you know that I know."

"One more message, and I know you know that I know, and you know that I know that you know that I know. Right?"

Some hours, and most of a bottle of pot-stilled brandy, later Jan and Marie were still arguing.

"Then one more guy, and you know I know you know I know you know I know you know I know..." Marie counted off the "you knows" and "I knows", and Jan kept the tally with bottle corks. As the cork pile grew, the pair realized the approach wasn't going to work, and talk shifted to discouraging Karaoke in the community. After making a plan to ask for it to be mentioned in that Sunday's sermon, and drafting a list of reasons it wasn't moral, Marie realized it was in vain.

"Any chance, Jan. Any small chance and it's all for niks. The messenger doesn't have to get lost, it's enough for one of us not to be sure. Besides, nobody listens to the dominee."

The two farmers continued to struggle with the problem for days, without any result. Eventually, on a visit to the local library, they came across a paper from 1979 by Yemini and Cohen. In it, they found their worst fears confirmed: they were going to lose the farm. As long as there is any probability that a messenger gets lost, no algorithm can guarantee they meet on the same morning to harvest. It got worse. In a 1984 paper by Halpern and Moses they found that even if all the messengers did eventually arrive, they still couldn't agree, unless the amount of Karaoke they sung was bounded. They felt like all hope was lost.

Just as they were ready to leave the library in desperation, Jan read something that made his heart jump:

On the other hand, if messages are guaranteed to be delivered within ε units of time, then ε-coordinated attack can be accomplished.

"Hey Marie! Did you see that paper by Fagin? We need to read that Halpern and Moses one again!"

"Moses?"

"Probably not the same Moses."

Jan and Marie made a copy of the paper, and headed home. Putting the Halpern and Moses paper next to their father's will, they discovered something amazing. The will didn't say they have to meet at the field at exactly the same time! It just had to be the same morning. If they could set the maximum amount of Karaoke a messenger could sing to ε, they could meet at the fields within ε of each other. As long as ε is less than a morning, they could keep the farm. Being a well-funded land owner, Marie's run for local government was as quick as her career was short. She stayed long enough to propose only one law. To this day, it's illegal to sing karaoke for more than ε seconds in that small dorp in that valley in the Bottelary Hills.
 Exactly-Once Delivery May Not Be What You Want 2014-11-15T00:00:00+00:00 http://brooker.co.za/blog/2014/11/15/exactly-once
Exactly-Once Delivery May Not Be What You Want

It's hard to get, but that's OK, because you don't want it.

Last week, there was a good discussion on lobste.rs about why exactly-once messaging is not possible. The discussion was kicked off with a link to a paper from Patel et al titled Towards In-Order and Exactly-Once Delivery using Hierarchical Distributed Message Queues, which claims to contribute:

... a highly scalable distributed queue service using hierarchical architecture that supports exactly once delivery, message order, large message size, and message resilience.

I haven't evaluated the author's other claims in detail, but the claim of exactly once delivery caught my eye.

There is no chance of getting two get requests for the same message. When a HTTP message request comes in, a message is sent through HTTP response and the message is deleted at the same time.

While I'm not fully satisfied about their at the same time, they don't seem to be claiming to break any fundamental laws here. What I do feel is fundamental, though, is that this definition of exactly once delivery isn't the one that most systems builders would find useful. The effect that most people are interested in is actually exactly-once processing: a message having a particularly side-effect exactly once per message.

I like to think about this in terms of redundancy. Fault-tolerant distributed systems deal with all kinds of failures, but it's often practically useful to break them into two categories: node failure and message loss. Node failures can be tolerated with redundancy in space, having multiple copies of a piece of data on multiple nodes. Message loss can be tolerated with redundancy in time, sending the same message multiple times if it doesn't seem to have been received. Replicated databases are redundant in space, and TCP is a great example of redundancy in time. Side note: I stole this characterization from the excellent talk titled Outwards From The Middle of the Maze by Peter Alvaro.

Think about a simple system making use of an exactly once queue. There's some producer (which we'll mostly ignore), the queue (which we'll pretend has magic durability and availability properties), and the focus of the discussion: a fleet of consumers. The producer makes tasks asking the consumers to alter the world in some way. We could build this system in a few ways:

The queue passes each task to exactly one consumer exactly once. If the consumer fails the task is lost, and the system does each task at most once.

We could ask the consumer to acknowledge the message once it's been processed. If the consumer fails to do that after some amount of time, the queue will offer it to another consumer. This makes system tolerant to consumer failure, but a consumer just stalling could cause it to pick up the work when it recovers, causing multiple delivery. This system ends up being at least once.

To fix the stall problem, we could put a timeout on the task itself, saying "don't perform this task at all if you can't get it done by five o'clock on Friday". While we can do this in a way that doesn't require the queue and consumer to synchronize their clocks, at least we have to depend on the relative rates of their clocks being bounded.

We could pass the task to multiple consumers, and ask them to co-ordinate amongst themselves which will execute it. That's a reasonable solution from the queue's perspective, but just moves the problem down to the consumer.

And so on. There's always a place to slot in one more turtle. The bad news is that I'm not aware of a nice solution to the general problem for all side effects, and I suspect that no such solution exists. On the bright side, there are some very nice solutions that work really well in practice. The simplest is idempotence. This is a very simple idea: we make the tasks have the same effect no matter how many times they are executed.

Consider Bob, distributed systems enthusiast and pizza restaurateur. When people order from Bob, their orders go into a persistent queue. Bob's workers take a pizza order off the queue, bake it, deliver it, and go back to the queue. Occasionally one of Bob's workers gets bored and leaves early in the middle of a task, in which case Bob gives the order to a different worker. Sometimes, this means that multiple pizzas arrive at the customer's house (though never less than one pizza). Bob doesn't want people to end up with excess pizza, so he does something very smart: gives each order a unique identifier. On arriving, the pizza delivery guy asks the home owner if they had received a pizza with that order ID before. If the home owner says yes, the pizza guy takes the duplicate pie with him. If not, he leaves the pie. Each home owner gets exactly one pie, and everybody is happy.

In Bob's world, pizza baking and delivery is an at least once operation, but pizza delivery into the customer's house happens exactly once thanks to the fact that his deliveries are idempotent. Bob's obviously got a strong incentive to reduce pizza waste. He tries to make sure that at least once is also approximately once, which is easy most of the year, but can be a real challenge when it's stormy out and the big game is on.

I think there are two lessons here for people building distributed systems. One is that end-to-end system semantics matter much more than the semantics of an individual building block, and sometimes what seems like a very desirable semantic for a building block may end up making the end-to-end problem harder. The other is that simple, practical, solutions like unique IDs can make really hard problems much easier, and allow us to build and ship real systems that work in predictable ways.
 Ice Cream and Distributed Systems 2014-10-25T00:00:00+00:00 http://brooker.co.za/blog/2014/10/25/ice-cream
Ice Cream and Distributed Systems

Can we serve a fair amount of ice cream?

When I was a child, I really liked to eat ice cream. It's still pretty great, but back then I was somewhat fanatical about it. My parents knew that the delicious mix of fat and sugar was best served only occasionally, and would carefully limit my intake. I, of course, found a way around the system. First, I'd go to my mother and ask if it was time for ice cream, and she would give me an answer. If she answered in the negative, I'd ask my father the same question. That strategy increased by chances of an affirmative answer, because the decisions that my parents made were not consistent. Occasionally, I'd even eat some served by my mother, and then try my father for a second bowl.

After a while of running this scheme, my parents figured it out. They decided that they needed to give me a consistent answer, and the only way to do that was to talk to each other every time I asked the question. Their coordination approach worked great. It guaranteed a consistent answer, and only made young Marc wait a little longer for his question to be answered.

It all broke down when my parents went to work. Being a child, I could find a good excuse to speak to either parent at any time, but their jobs prevented them from speaking to each other. Once again, I could use the situation to my rich, sweet, and creamy advantage. With my parents unable to communicate, I was able to force an inconsistent decision. Did my parents miss a trick that would have allowed them to make a consistent ice cream serving decision without being able to talk to one another?

Assume that the network consists of at least two nodes. Thus it can be divided into two disjoint, non-empty sets: {G1, G2}. The basic idea of the proof is to assume that all messages between G1 and G2 are lost. Then if a write occurs in G1, and later a read occurs in G2, then the read operation cannot return the results of the earlier write operation.

Assuming that my parents didn't have watches, and had to make the decision based only on the messages they have received and their internal state, Gilbert and Lynch proved that they can't have made a consistent decision in general. That's a general result about writes and reads. Could they do better in this specific case?

Getting crafty with clocks

Around that time, my parent's ice cream policy was that I got one bowl a week. They met before work every day when I hadn't reached my weekly allocation, and decided that for the next eight hours only one of them could hand out an ice cream decision. If it was my mother's day, and I called my father for a decision, he told me that he couldn't give me one. As long as I can could contact my mother, I could get a consistent answer. If I couldn't reach my mother, I was out of luck. The one saving factor, though, was that if mom worked late, dad would notice the eight hours had expired and make a decision.

Soon, being the crafty young man I was, I realized that dad's watch ran slightly faster than mom's. When he got home, I'd go to my dad and ask for a serving of vanilla. He'd look at his watch, see that eight hours had expired, and assume that my mom had lost the authority to make the decision. After checking that the bowl in the freezer was still full, to make sure my mom hadn't decided during the day, he'd allow me to eat. I'd wolf down my frozen treat, and call my mom. Her slower watch told her the eight hours weren't up yet, and she'd give me the go ahead for a second bowl. I'd beaten the system!

[the client's lease time] is shortened by ... the allowance E for clock skew. As a minimum, the correct functioning of leases requires only that clocks have a known bounded drift

If my parents had read Gray and Cheriton, they would have known how to fix their lease protocol. My mom and dad would have had to measure the skew between the rate of their watches, and added some time (E) to the time my dad waited before assuming my mom didn't have the lease anymore.

Putting the results back together

Thanks to a diet fad sweeping the nation, my parents decided that ice cream wasn't as bad as they assumed. Being responsible parents they still wanted to track my consumption to check their hypothesis. During the work day, my mom and dad went back to making inconsistent decisions, and each just kept their own records of how often they said yes. Once they were home together again, they could add up their numbers to get an accurate total.

Tracking flavors was a little bit harder. Every time I called to request a scoop, they would write down which flavor I got permission for. Occasionally I'd go to the freezer and find that flavor was out, and I'd call and ask to reduce my tally. Being a small child with a short memory, I couldn't remember if mom or dad had recorded the yes, so I'd call one at random to record the no. That didn't matter, because they could still total their independent counts at the day's end to get an accurate tally. An accurate tally, that is, until disaster struck.

I'd received permission from mom to eat some strawberry gelato, but found none in the usual place between the ice trays and frozen juice. I called her back to report the failure, but the line dropped before I could say goodbye. Distraught at being rudely disconnected from my mother, I called my dad to report the same thing. When the tally was done at the end of the day, my parents were baffled by the count of negative one. Had we invented anti-gelato?

My parents unfortunately hadn't kept track of developments in conflict-free replicated data types. If they had, they could have solved this problem with an OR set, by tracking additions and removals with unique tags. If they had been armed with that paper, and research on CRDTs new and old, could they have gone back to restricting my intake? The intuition is obvious: if we can count something independently, and we can manage a set independently, can we enforce one bowl per day independently? Unfortunately not. The important difference is that add one and add to set are commutative, while reduce by one if the count is greater than zero isn't.

Getting everybody to agree

Following their frustrating battle with flavor tracking, my parents asked their part-time housekeeper Mary to help with the problem. After losing faith in fad diet books, my parents both dedicated part of their work day to investigating the health properties of ice cream, and frequently changed their opinion. They also wanted to keep careful track of how much I was served, in case the dosage turned out to be important to my health. Mom and Dad agreed with Mary that she could allow me to eat some as long as all of them agreed when I asked. Mary was happy with this, but there was one big problem: she didn't like talking on the phone. Fortunately, she loved to send text messages. Unfortunately, texts were still strangely expensive back then.

Mary, Mom and Dad sat down and tried to figure out how to all agree on the problem with the fewest number of messages. Mary invented a simple scheme: when I asked her if I could have some ice cream, she messaged both my mom and dad and ask for their opinion, while asking that they didn't change their opinion until hearing back from her. If they both agreed, she'd go ahead and let them know she was going to serve dessert. If either said no, she let them know that the bowl would remain empty. The protocol, which they called two-phase commit after the frozen and liquid phases of ice cream, took four messages to complete. Could Mary do better and save some money on text messages?

Any commitment protocol ... requires at least 2(n - 1) messages to commit a transaction in the absence of processor failures.

Luckily for them, my parents didn't waste too much time thinking about the problem. Mary came across a paper from Cynthia Dwork and Dale Skeen which laid out what she needed to know. As long as Mary was sending text messages, there was no way to do better than her protocol.
 Harvest and Yield: Not A Natural Cure for Tradeoff Confusion 2014-10-12T00:00:00+00:00 http://brooker.co.za/blog/2014/10/12/harvest-yield
Harvest and Yield: Not A Natural Cure for Tradeoff Confusion

Comments on a 15 year old paper.

As I wrote about in my post on PACELC, I don't think the CAP theorem is the right way for teachers to present distributed systems tradeoffs. I also don't think it's ideal for working practitioners, despite its wide use. I prefer Abadi's PACELC, but there are legitimate criticisms of that one too. One criticism is that it's poorly formalized, which makes it hard to apply to precise statements. Another is the PC/EL is an awkward edge case. There are more. Fox and Brewer's harvest and yield model, from Harvest, Yield, and Scalable Tolerant Systems, is a widely promoted alternative.

While I like the concepts of harvest and yield, I find it hard to recommend the paper. Both Eric Brewer and Armando Fox have made big contributions to the field, and I like many of their papers. I just don't like this one.

I'll start with what I dislike most about it. From the first page:

Partition-resilience means that the system as whole can survive a partition between data replicas.

CA without P: Databases that provide distributed transactional semantics can only do so in the absence of a network partition separating server peers.

I find these statements awkward, and feel like they support the mistaken belief that CA is a valid option. You certainly can't pick CA where your C is linearizability (as in Gilbert and Lynch's proof) or serializability. If you're allowed to pick CA, either your definition of C is weaker than either of those, your definition of A doesn't require minority partitions to make progress, or you're in denial about network partitions (which do exist). Compare the definition of CP:

CP without A: In the event of a partition, further transactions to an ACID database may be blocked until the partition heals, to avoid the risk of introducing merge conflicts (and thus inconsistency).

Is that saying that CA exists, but just introduces inconsistencies that CP doesn't? Overall, I don't follow Fox and Brewer's thinking about partition tolerance in this paper.

On to the model itself, which concerns itself with:

large applications whose output behavior tolerates graceful degradation

The idea of graceful degradation is that a partial response may be more useful to the client than no response, so you can directly trade off between the completeness of the response and the availability of the system. Many real-world systems can tolerate partial responses, especially if you can provide some bounds on the definition of partial. Using probabilistic data structures like Bloom filters and the count-min sketch is a widely accepted technique for scaling systems, and it makes sense to apply the same ideas to availability.

We assume that clients make queries to servers, in which case there are at least two metrics for correct behavior: yield, which is the probability of completing a request, and harvest, which measures the fraction of the data reflected in the response, i.e. the completeness of the answer to the query.

Yield is the availability metric that most practitioners end up working with, and it's worth noting that its different from CAP's A. The authors don't define it formally, but treat it as a long-term probability of response rather than the probability of a response conditioned on there being a failure. That's a good common-sense definition, and one that fits well with the way that most practitioners think about availability.

In the presence of faults there is typically a tradeoff between providing no answer (reducing yield) and providing an imperfect answer (maintaining yield, but reducing harvest).

That's a very powerful idea, and one worth sharing.

Even when the 100%-harvest answer is useful to the client, it may still be preferable to trade response time for harvest when client-to-server bandwidth is limited, for example, by intelligent degradation to low-bandwidth formats.

Another good idea, and one that has been widely used. As good an ideas as it is, though, the paper is conflating at least three separate ideas: cases of shrinking data to conserve bandwidth, responding with cached data to conserve latency, and responding with a partial response to conserve availability. A more precise definition of harvest would be very useful, as would definitions of different availability, latency and bandwidth tradeoffs.

The actual benefit is the ability to provision each subsystem's state management separately, providing strong consistency or persistent state only for the subsystems that need it, not for the entire application.

That's yet another good idea, as is the concept of orthogonal mechanisms from section 5. Again, the problem is that the idea isn't fully developed, and has some significant edge cases.

I really like the concepts of harvest and yield, and many of the other ideas in this paper. I just find the whole thing hard to recommend as a unit. It feels like a bag full of unmarked tools. A sharp scalpel. A rusty hammer. A glass bottle of FOOF. A nice microscope. There's a lot in there to like, but sticking your hand in and rummaging around may do more harm than good.

In any case, harvest and yield isn't really a CAP replacement. The CAP theorem is one boundary of the space of possible designs, a fence that can't be crossed. Fox and Brewer's ideas are more about the shape of the landscape inside the fence. That's useful knowledge, but it's really in a different category from CAP.
 The Essential Barbara Liskov 2014-09-21T00:00:00+00:00 http://brooker.co.za/blog/2014/09/21/liskov-pub
The Essential Barbara Liskov

Some of my favorite Barbara Liskov publications.

Barbara Liskov is one of the greats of computer science. Over a research career nearing 45 years, she's had a resounding impact on multiple different fields, and received an impressive list of honors and awards, including the 2009 Turing Award. In the same spirit as The Essential Leslie Lamport and The Essential Nancy Lynch, I thought I'd write about some of my favorite Liskov papers. These are just papers I like or found particularly interesting, and I'm likely to have missed some you like.

What does it mean for one type to be a subtype of another? We argue that this is a semantic question having to do with the behavior of the objects of the two types: the objects of the subtype ought to behave the same as those of the supertype as for as anyone or any program using the supertype objects can tell.

Data abstraction and hierarchy, A behavioral notion of subtyping and Behavioral subtyping using invariants and constraints, are why most working programmers would recognize Liskov's name. The Liskov Substitution Principle, widely known as the L in SOLID, is a widely-followed rule about the relationship between the behavior of its supertypes and subtypes.

I'll readily admit that types are an area of computer science that I'm not very familiar with, but I found these papers easy to follow and very applicable. For the working programmers, there's not much material there that isn't covered in the wiki page, but it's worth reading to see how Liskov lays out the arguments for the principle. If you're interested in the history and thinking behind rules, these are great papers to read.

Availability is achieved through replication.

Transaction processing depends on forcing information to backups so that a majority of cohorts know about particular events.

Viewstamped Replication: A New Primary Copy Method to Support Highly Available Distributed Systems deserves to be recognized as one of the most influential papers in distributed systems. Viewstamped replication predates Lamport's Paxos, but solves the same problem in a very similar (though distinct) way. The viewstamped replication paper remains both readable and relevant, although some of the descriptions and formalisms used show the paper's age. If you only have time to read one paper on Viewstamped Replication, the recent Viewstamped Replication Revisited is probably a better bet, because it provides a clearer description of the protocol and the design decisions it makes.

I've written before about viewstamped replication, and why I think it should be more widely recognized for the contributions it made to consensus, and the idea of state machine replication. It would be great to see more knowledge about VR among distributed systems practitioners.

Unlike other multistamp (or vector clock) schemes, our scheme is based on time rather than on logical clocks: each entry in a multistamp contains a timestamp representing the clock time at some server in the system.

Version vectors (or vector clocks or multistamps) are a very widely used scheme for versioning data in distributed systems, but keeping them short in the face of scaling or reconfigurations and scaling is a real challenge. Lazy consistency using loosely synchronized clocks paper presents an one approach, using loosely synchronized physical clocks. An interesting aspect of it is that it breaks from the orthodoxy that using clocks for ordering is bad (which it is, unless you are careful with your safety properties). If you find reading this worthwhile, I'd also recommend Dynamic Version Vector Maintenance and Flexible update propagation for weakly consistent replication.

One reason why Byzantine-fault-tolerant algorithms will be important in the future is that they can allow systems to continue to work correctly even when there are software errors. Not all errors are survivable; our approach cannot mask a software error that occurs at all replicas. However, it can mask errors that occur independently at different replicas, including non-deterministic software errors, which are the most problematic and persistent errors since they are the hardest to detect.

Byzantine faults happen all the time in the real world. Handling them, and making safe progress in distributed systems despite them, is a huge challenge. Just getting the theory right is tricky. Getting to a practical implementation of Byzantine fault tolerance is even harder. That's what makes Practical Byzantine fault tolerance so important. Castro and Liskov describe an practically implementable Byzantine fault tolerant system, that works in a realistic system model. The key contribution here, over precursors like Rampart, is safety in real-world system models, especially removing assumptions about synchronicity.

On a similar topic, Byzantine clients rendered harmless is also worth reading. Many approaches to Byzantine-fault-tolerant replication make both safety and liveness assumptions about the behavior of clients. Strengthening the protocol against client behavior is very important to practical systems.
 The Space Between Theory and Practice in Distributed Systems 2014-08-10T00:00:00+00:00 http://brooker.co.za/blog/2014/08/10/the-space-between
The Space Between Theory and Practice in Distributed Systems

How do we learn synthesis?

Teaching and learning about distributed systems, like any complex topic, requires real thought about what to teach and what to learn. It would be great to have enough time to teach and learn everything, but there's just too much material out there. Even if we did have the time to cover every paper, result, code base, experience report and blog post in the field, we'd still need to chose an order to cover them in. There's a natural order to things to the learned that makes them much easier to learn. That's why I was excited to see Henry Robinson's Distributed systems theory for the distributed systems engineer.

It's a good list of things to learn about, from the practical to the theoretical. I like the way it's broken up into clear sections, and uses examples from many real-world systems from industry. This is a list I'm going to be recommending to people for a while, and going to be working through myself. Unfortunately, Henry's list reflects a greater gap in the overall literature: the gap between theory and practice.

From Dynamo and Cassandra to Chubby and ZooKeeper there's a wealth of content available on the design and implementation of real systems. Some of these papers go into real depth on seemingly small details (like Paxos Made Live) while others concern themselves with high-level architecture. Combined with things like Deutsch's 8 Fallacies and Jeff Hodges Notes on Distributed Systems for Young Bloods there's a lot of practical advice available to learn about the practical side of distributed systems.

On the theoretical side, there's also a wealth of material. Robinson points to the CAP proof and the FLP result, and admits that he's only just scratching the surface. There are thousands of good theoretical results out there, from the usual suspects like Lamport and Lynch to areas like topology and game theory.

I feel like if I went through everything I've read on distributed systems and arranged them on a spectrum from theory to practice the two ends would be really well populated, but the middle would be disturbingly empty. Worse, changing to a graph of citation links would show a low density from theory to practice. I strongly believe that a deep knowledge of theory makes practitioners smarter and better. I believe that a deep knowledge of practice makes researcher's work more relevant. It would be great to see more material in this gap.

Many will point at this stage that it's not a complete gap. I'll admit that there's some great material there, including Paxos Made Live on the theory end of practice and Kenneth Birman's Guide to Reliable Distributed Systems or Butler Lampson's How to Build a Highly Available System Using Consensus on the practice end of theory. There are also blogs like Henry's and Aphyr's which do a good job in that gap. Despite this, I still see some big gaps in material. An example may be the easiest way to illustrate it:

If FLP says consensus is impossible with one faulty process, and faults happen all the time in practice, how are real systems built with consensus?

There are a few ways to answer this question. One starts with pointing out that FLP talks about it being not always possible to solve consensus, rather than never possible. Another way is to point out that the real world is richer than FLP's idealized model, and the problem can be solved with clocks or a random oracle. A third way is to laugh derisively at the asker and point out that the answer is in Paxos Made Simple (feigning surprise What‽ You haven't read Paxos Made Simple‽).

Despite these 'obvious' answers, it's actually a really interesting question. On one side we see a researcher saying that consensus isn't always possible, and on the other we hear practitioners talking about how they built highly-available systems using consensus algorithms. Who is right? Does the researcher have their head too far in the clouds? Is the practitioner so ignorant of theory that they have built a ticking time bomb?

That's the gap I am talking about: material that explains how the practice is synthesized from the theory, and how the theory is based off analysis of the practice. The exercise of synthesis is very seldom straight forward, but we too frequently leave it to the imagination. In this context, I use synthesis to mean the process of gathering ideas from the literature and putting them together into a whole working system. Related processes include analysis of other systems, where we break them down into their consistuent parts and see what makes them work (or not work). These are among the most important processes behind successful engineering, but are written about least.

I would love to see more material focused on exactly this synthesis problem in distributed systems, because I think it would help improve the quality of practice, and strengthen the dialog between practitioners and researchers. That's good for all of us.
 Use of Formal Methods at Amazon Web Services 2014-08-09T00:00:00+00:00 http://brooker.co.za/blog/2014/08/09/formal-methods
Use of Formal Methods at Amazon Web Services

How we're using TLA+ at AWS

Late last year, we published Use of Formal Methods at Amazon Web Services about our experiences with using formal methods at Amazon Web Services (AWS). The focus is on TLA+, and why we think it's a great fit for the kind of work we do.

From the paper:

In order to find subtle bugs in a system design, it is necessary to have a precise description of that design. There are at least two major benefits to writing a precise design; the author is forced to think more clearly, which helps eliminate 'plausible hand-waving', and tools can be applied to check for errors in the design, even while it is being written. In contrast, conventional design documents consist of prose, static diagrams, and perhaps pseudo-code in an adhoc untestable language. Such descriptions are far from precise; they are often ambiguous, or omit critical aspects such as partial failure or the granularity of concurrency (i.e. which constructs are assumed to be atomic). At the other end of the spectrum, the final executable code is unambiguous, but contains an overwhelming amount of detail. We needed to be able to capture the essence of a design in a few hundred lines of precise description.

The full paper is worth reading if you're interested in formal methods.
 CAP and PACELC: Thinking More Clearly About Consistency 2014-07-16T00:00:00+00:00 http://brooker.co.za/blog/2014/07/16/pacelc
CAP and PACELC: Thinking More Clearly About Consistency

CAP is confusing. PACELC is better, but still not ideal.

In some sense, the CAP theorem has been too successful. With its snappy name and apparently easy-to-understand behavior, CAP has become the go-to way of talking about tradeoffs in distributed systems. Despite its apparent simplicity, confusion, misunderstandings, misrepresentations and debates about CAP are widespread. Criticism of CAP is also widespread, both in its use as a teaching tool and as a way of reasoning about tradeoffs. Dan Weinreb, Henry Robinson, and Michael Stonebraker have written good examples of the genre. It would be great to find a tool for teaching, and learning about, these tradeoffs that doesn't have the same shortcomings as CAP.

In this post, my focus is on CAP as a tool for learning and teaching about distributed systems tradeoffs, rather than its use by experienced practitioners. The problems with CAP as a teaching tool, as I see them, are:

The popular belief is that CAP means pick any two. The confusion is about the existence of CA systems, which pretend that partition tolerance is optional, or claim that partitions don't happen. Marketing from database vendors plays into this, too. In reality, you can't sacrifice partition tolerance, because partitions happen in real large-scale systems all the time. There is some evidence that the popularity of this misconception is waning, but it would be premature to announce its death.

The second misconception is that the CAP theorem means you can't be consistent and available during partitions. That's not true, at least in the case of Gilbert and Lynch's version of the theorem. Specifically, the CAP theorem only prevents everybody from being consistent and available, not anybody (some literature calls this always available). It doesn't prevent clients and replicas on the majority side of simple partitions from making progress, and experiencing both consistency and availability. There are other restrictions on this, but they aren't CAP restrictions.

The third misconception is that the consistency in CAP is all or nothing, and that you can't offer any consistency guarantees at all during partitions. In reality, many very useful consistency models can be offered on all sides of a partition. Implementation tricks like session stickiness and client-side caching can allow systems to offer useful models like read your writes, monotonic reads and even causal consistency. Bernstein and Das, and Bailis et al have good overviews of some of the possibilities.

The fourth misconception is that eventual consistency is all about CAP, and that everybody would chose strong consistency for every application if it wasn't for the CAP theorem.

Another source of confusion is the different versions of the CAP theorem, from Brewer's original version, to his later writings to Gilbert and Lynch's proof. Some seem to call the former Brewer's Conjecture and the latter the CAP theorem, but this usage is far from universal. Typically, they're both just called CAP or the CAP theorem.

This doesn't mean that the CAP theorem, and Brewer's more general CAP conjecture, isn't useful as a teaching and learning tool. I think its usefulness has been overstated by popularity, and in its popularity a lot of the subtlety has been lost. I find that unfortunate, because it means more confused students, and more confused practitioners. It would be great to replace CAP with something equally snappy, with fewer subtle edges.

Daniel Abadi's Consistency Tradeoffs in Modern Distributed Database System Design proposes an alternative: PACELC. Is that what we need?

A more complete portrayal of the space of potential consistency tradeoffs for DDBSs can be achieved by rewriting CAP as PACELC (pronounced "pass-elk"): if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?

Dan Weinreb suggests making it PACELCA instead, a formulation that I prefer:

The reason the acronym doesn't need to be "PACELCA" is that if there are no partitions, then the system must be available. Adding an "A" to the second part is redundant. But for me (maybe not for you), putting in the redundant "A" in the "E" case helps me. A PA/EL system is always "available", and calling it PA/ELA makes it easier for me to see that availability is always there.

PACELC mostly takes aim at the first and fourth misconceptions I listed: that CA systems exist, and that eventual consistency is all about CAP. First, it doesn't allow you to ignore partition tolerance. Second, it makes it clear that even in the absence of partitions there's a tradeoff between consistency and latency. In the general case, though not all cases, consistency requires a level of coordination which prevents systems from being always available (in the Gilbert and Lynch sense), and increases latency when no partition is present. The matter of latency, which is of great practical importance in real-world systems, isn't captured at all in CAP.

So far so good for PACELC.

The first two categories of PACELC are very clear. PC/EC is the most consistent class of systems, which never give up consistency. PA/EL systems don't try hard to be consistent, and rather take the opportunity to reduce latency and gain availability by reducing coordination. The trickier ground starts with PA/EC. These types of systems give up consistency when there is a partition, and are consistent when there isn't. That's more subtle than it looks. When is there a partition? How long does the network need to be down before there is a partition? Is a single dropped connection or lost packet a partition? That may seem like nit picking, but there's an important line to be drawn between partition and not partition. PACELC doesn't help there.

If PA/EC is tricky, PC/EL is madness. What does it mean to be more consistent during a partition? Daniel Abadi says that's the wrong question:

PNUTS is a PC/EL system. In normal operation, it gives up consistency for latency; however, if a partition occurs, it trades availability for consistency. This is admittedly somewhat confusing: according to PACELC, PNUTS appears to get more consistent upon a network partition. However, PC/EL should not be interpreted in this way. PC does not indicate that the system is fully consistent; rather it indicates that the system does not reduce consistency beyond the baseline consistency level when a network partition occurs—instead, it reduces availability.

That's interesting, but not really helpful, because it introduces a subtle edge to PACELC of the same kind that exists in CAP. All is not lost. I feel that PACELC is a more useful model for beginners in thinking about distributed systems tradeoffs, but it's still not the ideal solution. It would be great if a simple easily-understood replacement existed. Any ideas?
 Two traps in iostat: %util and svctm 2014-07-04T00:00:00+00:00 http://brooker.co.za/blog/2014/07/04/iostat-pct
Two traps in iostat: %util and svctm

These commonly-used fields in iostat shouldn't be commonly-used.

iostat, from the excellent sysstat suite of utilities, is the go-to tool for evaluating IO performance on Linux. It's obvious why that's the case: sysstat is very useful, solid, and widely installed. System administrators can go a lot worse than taking a look at iostat -x. There are some serious caveats lurking in iostat's output, two of which are greatly magnified on newer machines with solid state drives.

To explain what's wrong, let me compare two lines of iostat output:

Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz sdd 0.00 0.00 13823.00 0.00 55292.00 0.00 8.00 avgqu-sz await r_await w_await svctm %util 0.78 0.06 0.06 0.00 0.06 78.40 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz sdd 0.00 0.00 72914.67 0.00 291658.67 0.00 8.00 avgqu-sz await r_await w_await svctm %util 15.27 0.21 0.21 0.00 0.01 100.00

Both of these lines are from the same device (a Samsung 840 EVO SSD), and both are from read-only 4kB random loads. What differs here is the level of parallelism: in the first load the mean queue depth is only 0.78, and in the second it's 15.27. Same pattern, more threads.

The first problem we run into with this output is the svctm field, widely taken to be the average amount of time an operation takes. The iostat man page describes it as:

The average service time (in milliseconds) for I/O requests that were issued to the device.

and goes on to say:

The average service time (svctm field) value is meaningless, as I/O statistics are now calculated at block level, and we don't know when the disk driver starts to process a request.

The reasons the man page states for this field being meaningless are true, as are the warnings in the sysstat code. The calculation behind svctm is fundamentally broken, and doesn't really have a clear meaning. Inside iostat, svctm in an interval is calculated as time the device was doing some work / number of IOs, that is the amount of time we were doing work, divided by the amount of work done. Going back to our two workloads, we can compare their service times:

svctm 0.06 0.01

Taken literally, this means the device was responding in 60µs when under little load, and 10µs when under a lot of load. That seems unlikely, and indeed the load generator fio tells us it's not true. So what's going on?

Magnetic hard drives are serial beings. They have a few tiny heads, ganged together, that move over a spinning platter to a single location where they do some IO. Once the IO is done, and no sooner, they move on. Over the years, they've gathered some shiny capabilities like NCQ and TCQ that make them appear parallel (mostly to allow reordering), but they're still the same old horse-and-carriage sequential devices they've always been. Modern hard drives expose some level of concurrency, but no true parallelism. SSDs, like the Samsung 840 EVO in this test, are different. SSDs can and do perform operations in parallel. In fact, the only way to achieve their peak performance is to offer them parallel work to do.

While SSDs vary in the details of their internal construction, most have the ability to access multiple flash packages (groups of chips) at a time. This is a big deal for SSD performance. Individual flash chips actually don't have great bandwidth, so the ability to group the performance of many chips together is essential. The chips are completely independent, and because the controller doesn't need to block on requests to the chip, the drive is truly doing multiple things at once. Without the single electromechanical head as a bottleneck, even single SSDs can have a fairly large amount of internal parallelism. This diagram from Agarwal, et al shows the high-level architecture:

If Jane does one thing at a time, and doing ten things takes Jane 20 minutes, each thing has taken Jane an average of two minutes. The mean time between asking Jane to do something and Jane completing it is two minutes. Alice, like Jane, can do ten things in twenty minutes, but she works on multiple things in parallel. Looking only at Alice's throughput (the number of things she gets done in a period of time) what can we say about Alice's latency (the amount of time it takes her from start to finish for a task)? Very little. We know its less than 10 minutes. If she's busy the whole time, we know it's 2 or more minutes. That's it.

Let's go back to that iostat output:

Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz sdd 0.00 0.00 13823.00 0.00 55292.00 0.00 8.00 avgqu-sz await r_await w_await svctm %util 0.78 0.06 0.06 0.00 0.06 78.40 Device: rrqm/s wrqm/s r/s w/s rkB/s wkB/s avgrq-sz sdd 0.00 0.00 72914.67 0.00 291658.67 0.00 8.00 avgqu-sz await r_await w_await svctm %util 15.27 0.21 0.21 0.00 0.01 100.00

What's going on with %util, then? The first line is telling us that the drive is 78.4% utilized at 13823 reads per second. The second line is telling us that the drive is 100% utilized at 72914 reads per second. If it takes 14 thousand to fill it to 78.4%, wouldn't we expect it to only be able to do 18 thousand in total? How is it doing 73 thousand?

The problem here is the same - parallelism. When iostat says %util, it means "Percentage of CPU time during which I/O requests were issued to the device". The percentage of the time the drive was doing at least one thing. If it's doing 16 things at the same time, that doesn't change. Once again, this calculation works just fine for magnetic drives (and Jane), which do only one thing at a time. The amount of time they spend doing one thing is a great indication of how busy they really are. SSDs (and RAIDs, and Alice), on the other hand, can do multiple things at once. If you can do multiple things in parallel, the percentage of time you're doing at least one thing isn't a great predictor of your performance potential. The iostat man page does provide a warning:

Device saturation occurs when this value is close to 100% for devices serving requests serially. But for devices serving requests in parallel, such as RAID arrays and modern SSDs, this number does not reflect their performance limits.

As a measure of general IO busyness %util is fairly handy, but as an indication of how much the system is doing compared to what it can do, it's terrible. Iostat's svctm has even fewer redeeming strengths. It's just extremely misleading for most modern storage systems and workloads. Both of these fields are likely to mislead more than inform on modern SSD-based storage systems, and their use should be treated with extreme care.

Hard drive image by Evan-Amos (Own work) (CC-BY-SA-3.0 or GFDL), via Wikimedia Commons
 The Operations Gradient: Improving Safety in Complex Systems 2014-06-29T00:00:00+00:00 http://brooker.co.za/blog/2014/06/29/rasmussen
The Operations Gradient: Improving Safety in Complex Systems

Can we improve the safety of complex systems by listening to operators more?

This week, I watched an excellent lecture by Richard Cook. He goes in some detail about why failures happen, through the lens of Rasmussen's model of system safety. If you build or maintain any kind of complex system, don't miss this lecture.

What is surprising is not that there are so many accidents, it's that there are so few.

The model that takes up most of the lecture is best expressed in Rasmussen's Risk Management in a Dynamic Society: A Modelling Problem, a classic paper that deserves more attention among engineers. The core of the insight of the model from Rasmussen's paper comes from Figure 3:

Rasmussen describes the process of developing systems as an adaptive search within a boundary defined by a set of economic constraints (it's not economically viable to run the system beyond this boundary), engineering effort constraints (there are not enough actors to push the system beyond this boundary), and safety constraints (the system has failed beyond this boundary). The traditional balance between engineering effort and economic return plays out in pushing the operating point of the system away from two of these boundaries. From the paper:

During the adaptive search the actors have ample opportunity to identify an effort gradient and management will normally supply an effective cost gradient.

The combination of optimizing for these two gradients tends to push the operating point towards the safety boundary (or boundary of acceptable performance). A conscious push for safety (or availability, durability and other safety-related properties) forces the operating point away from this boundary. One danger of this is that the position of the safety boundary is not always obvious, and it's also not a single clean line. From the paper:

in systems designed according to a defence-in-depth strategy, the defenses are likely to degenerate systematically through time, when pressure towards cost-effectiveness is dominating.

This is a key point, because defence-in-depth is frequently seen as a very good thing. It's danger in this model is that it turns the safety boundary into a gradient, and significant degeneration in safety can happen before there is any accident. In response to this, we estimate an error margin, we put up an organizational "perceived boundary of acceptable performance", and we put systems in place to monitor that boundary. That's a good idea, but doesn't solve the problem. In Cook's talk he says "repeated experience with successful operations leads us to believe that the margin is too conservative, that we have space in there that we could use". We want to use that space, because that allows us to optimize both for economics (getting further from our economic failure boundary) and engineering effort (getting further from our effort boundary). The response to this is organizational pressure to shrink the margin.

On the other hand, growing the margin, or at least the perceived margin, doesn't necessarily increase safety:

... drivers tend to try to keep their arousal at a desired, constant level and, consequently, go faster if conditions become too undemanding. ... traffic safety is hard to improve beyond a certain limit.

Rasmussen cites Taylor to provide evidence of risk homeostasis in traffic safety. This effect suggests that people (and organizations) will push the limits of safety to a certain perceived level, and increasing perceived safety will encourage risky behavior. While Rasmussen cites some data for this, and it has been suggested by many others, it is hard to reconcile some of these claims with the evidence that real-world traffic safety has been improved significantly since these claims were made. Whether risk compensation behavior exists, and the extent to which is contributes to a risk homeostasis effect, appears to be an area of active research. In skiing, for example, there does not appear to be a significant risk compensation effect with helmet use. Still, this effect may be a significant one, and should be considered before attempting to widen the perceived safety margin of a system.

Another way to move the operating point away from the safety boundary is to shift it in a big discontinuity after accidents occur. Using accidents as a driver away from the safety boundary is difficult for three reasons. The biggest one is that it requires accidents to occur, and that no feedback is provided between accidents. This wait until you crash before turning the corner approach can have very high costs, especially in safety and life critical systems. Another difficulty is the effect of the availability heuristic, our natural tendency to discount evidence that is difficult to recall. The longer it has been since an accident occurred, the smaller the push it provides away from the safety boundary. The third difficulty is that investigating accidents is really hard, and knowing which direction to move the operating point relies on good investigations. Simple it was human error conclusions are unlikely to move the operating point in the right direction.

Is all lost? No, but to make progress we may need to change the way that we think about measuring the safety of our systems. Cook and Nemeth make a distinction between those at the sharp end (operators) and those at the blunt end (management).

Those who are closest to the blunt (management) end are most remote from sharp end operations and are concerned with maintaining the organization, and threats to the organization are minimized by casting adverse events as anomalies.

Instead of treating crossings of the safety boundary as anomalies, we should incorporate more feedback from the sharp end into the process that chooses the system operating point. This sharp-end gradient, mostly supplied by operators of complex systems, can provide a valuable third gradient (along with the gradients towards least effort and towards efficiency). The advantage of this approach is that it is continuous, in that it doesn't rely on big accidents and investigations, and adaptive, it constantly measures the local position of the safety boundary and provides a slope away from it. Getting this right requires constant attention from operators, and requires a conscious decision to include operators in the decision making process.
 Viewstamped Replication: The Less-Famous Consensus Protocol 2014-05-19T00:00:00+00:00 http://brooker.co.za/blog/2014/05/19/vr
Viewstamped Replication: The Less-Famous Consensus Protocol

The first practical consensus protocol may be the least famous.

There's no doubt that Paxos is the most famous distributed consensus protocol. Distributed systems reading lists (such as this one by Dan Creswell and this one by Christopher Meiklejohn) nearly all include at least one paper describing it. That's as it should be. There's no doubt Paxos has been extremely influential in industry, and has formed the basis of many extremely successful systems. Lamport's Paxos Made Simple is very readable, and papers like Google's Paxos Made Live have helped raise the visibility of good Paxos implementation techniques.

Raft, on the other hand, is the most fashionable distributed consensus protocol. It seems like everybody's implementing it right now. I don't know if it's as understandable as it claims to be, but it's definitely in vogue. While I'm not a big fan of technology fads, I find it difficult to be upset about this one. Anything that encourages people to use well-proven distributed algorithms instead of crafting their own is good in my book.

By comparison to Paxos and Raft, one distributed consensus protocol seems frequently overlooked: Oki and Liskov's Viewstamped Replication. Introduced in May 1988 in Brian Oki's PhD thesis, Viewstamped Replication predates the first publication of Paxos by about a year. If you're looking for intrigue you may be disappointed: both Lamport and Liskov claim the inventions were independent. First, from Viewstamped Replication Revisited:

VR was originally developed in the 1980s, at about the same time as Paxos, but without knowledge of that work.

and from Keith Marzullo's comments in the 1998 reprinting of The Part-Time Parliament:

 The author was also apparently unaware that the view management protocol by Oki and Liskov seems to be equivalent to the Paxon protocol.

In many ways, the Paxos protocol as described in The Part-Time Parliament and the Viewstamped Replication protocol are surprisingly different. Paxos' Synod protocol is the basic building block of consensus, and is used more-or-less directly for data replication. On the other hand, in VR, normal requests are merely stamped with a view number on their way through the primary, and are sent to all the replicas in parallel. The similarities start to become apparent when looking at how that view number is chosen: VR's view change protocol. In fact, the view change protocol describe in Section 4.2 of Viewstamped Replication Revisited bears a striking resemblance to the Paxos Synod protocol, especially when compared to the description in Section 2.2 of Paxos Made Simple.

It's easy to believe that these two protocols are, in fact, the same. That doesn't appear to be the case. A new paper by van Renesse et. al., titled Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab, looks at Paxos and VR through the lenses of refinement and abstraction, and finds they are not exactly equivalent due to design decisions in the way they refine a model the paper calls Multi-Consensus. One of the key differences is active (Paxos) vs. passive (VR) replication:

 Passive vs. Active Replication: In active replication, at least f + 1 replicas each must execute operations. In passive replication, only the sequencer executes operations, but it has to propagate state updates to the backups.

I don't have an answer for why Paxos is so much more famous than Viewstamped Replication. The first publication of viewstamped replication was more readable, though less entertaining, than the first publication of Paxos. Implemented out of the paper, VR likely has better performance properties than Paxos, for similar implementation effort and complexity. Barbara Liskov is more widely known among programmers and computer scientists than Leslie Lamport, thanks to the Liskov substitution principle. I can't think of a good explanation at all.

Whatever the cause, both Viewstamped Replication and Viewstamped Replication Revisited are well worth including on your distributed systems reading list.
 The Essential Nancy Lynch 2014-05-10T00:00:00+00:00 http://brooker.co.za/blog/2014/05/10/lynch-pub
The Essential Nancy Lynch

Some of my favorite Nancy Lynch publications.

While reading distributed systems papers, one of the names that comes up most often is Nancy Lynch's. From a standard textbook for university distributed systems courses (Distributed Algorithms), to some of the earliest successful results on consensus, to the proof of the CAP theorem, Lynch's name is everywhere. In the same spirit as The Essential Leslie Lamport, I thought I'd write about some of my favorite Nancy Lynch papers. The criteria are the same as last time: I like these papers for some reason. I'd probably make a different list if I wrote this post again next week.

What good are impossibility results, anyway? They don't seem very useful at first, since they don't allow computers to do anything they couldn't previously.

A Hundred Impossibility Proofs for Distributed Computing is a great read. It covers a huge amount of ground across most of the distributed systems field as it stood in 1989, and presents an overwhelming number of results. The focus is on impossibility results and bounds (as the title suggests), but the paper frequently wanders off this path.

This paper is worth reading on it's own, but it's also a really great way to discover distributed systems papers you haven't seen before. With 103 references, there's plenty to keep you busy if you're looking for papers and books to read. Despite covering some deep results quite formally, the paper remains readable even without deep expertise in some of the areas it covers. A Hundred Impossibility Proofs is also a great piece of history, a snapshot of the distributed systems world 25 years ago.

Why this is worth reading: It presents a huge number of results in a very compact and readable package. You won't get bored reading this paper.

However the read request does not begin until after the write request ... has completed. This therefore contradicts the atomicity property, proving that no such algorithm exists.

The algorithm that doesn't exist is one that implements a writeable data object guaranteeing both consistency and availability in all executions in an asynchronous system. In other words, one that solves one definition of Brewer's CAP theorem. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. is important to the practice of distributed systems today, because it's held up as a proof of the CAP theorem (which it is), and provides some definitions under which conditions the CAP theorem is true. The paper spends about half its length looking at ways to circumvent the CAP theorem in partially synchronous networks.

Why this is worth reading: It both proves the CAP theorem, and debunks many of the common statements of it. The proof itself is simple and succinct, and provides real insight into why CAP is true.

It is easy to see that all correct processors make decisions

Consensus in the Presence of Partial Synchrony is one of three solutions to the consensus problem from the late 1980s. The others, Oki and Liskov's Viewstamped Replication and Lamport's Paxos, are arguably more general and perhaps more interesting solutions, but this one is still very influential. The algorithms in Consensus in the Presence of Partial Synchrony are interesting because they break the problem up differently from both Oki and Liskov and Lamport, and provide real insight into the structure of the consensus problem. The algorithms appear to be more complex and more cumbersome than either VR or Paxos, mostly because of the way they execute ballots in rounds. Still, this is very interesting stuff.

Why this is worth reading: This is more a piece of history than the others papers in this list, but it's still worth reading because it provides a view of a common problem from a different angle.

we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. ... the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement. Thus, this important problem has no robust solution without further assumptions about the computing environment or still greater restrictions on the kind of failures to be tolerated!

There are fairly few results in computer science that are seen as so influential that they have a widely recognized initialism. The FLP result, named after Fischer, Lynch and Paterson, is one such results. It may be even more notable because it's an impossibility result: instead of describing how to do something, FLP simply states that it can't be done.

In Impossibility of distributed consensus with one faulty process, FLP describe how no asynchronous protocol exists that can always reach consensus, even in the case of a single process failure, no matter how many participants there are. It's easy to see why this result is so influential. Still, as famous as FLP is, it seems to be less widely known (and much less widely misinterpreted) than CAP.

The thing that stands out for me in this paper is the beauty and simplicity of the proof. I found Lemma 2 and Lemma 3 in the paper both surprising and enlightening. The proof in the paper is worth reading, but may be easiest to approach once you already understand it. Henry Robinson's A Brief Tour of FLP Impossibility is a great place to start.

Why this is worth reading: It's both an important result and a beautiful proof.

at each round, until termination is reached, each process sends its latest value to all processes (including itself). On receipt of a collection V of values, the process computes a certain function f(V) as its next value.

Reaching approximate agreement in the presence of faults is one of my favorite distributed systems papers. I like it because it contains some incredibly simple, beautiful and yet non-obvious algorithms. I also like it because it take a different look at a common problem. It looks at the FLP result and says "OK, if I can't get exact agreement, how close can I get?". It turns out that you can get arbitrarily close to agreement with guaranteed termination. In some ways, this is the flip side of Ben-Or's consensus with probability 1 results.

This is worth reading because it'll change the way you think about agreement in distributed systems.
 Failure Detectors, and Non-Blocking Atomic Commit 2014-04-14T00:00:00+00:00 http://brooker.co.za/blog/2014/04/14/failure-detectors
Failure Detectors, and Non-Blocking Atomic Commit

Non-blocking atomic commit is harder than uniform consensus. Why would that be?

Many of the most interesting results in distributed systems have come from looking at problems known to be impossible under one set of constraints, and finding how little those constraints can be relaxed before the problem becomes possible. One great example is how adding a random Oracle to the asynchronous system model used by FLP makes consensus possible. That result is very interesting, but not as practically important as the idea of failure detectors.

The theoretical importance of detecting failures in the asynchronous model dates back to work in the 1980s from Dolev, Dwork and Stockmeyer and Dwork, Lynch and Stockmeyer. The latter of these papers is very interesting, because it describes what can be argued is the first practical consensus algorithm before the publication of Viewstamped Replication and Paxos. More on that another time. A great, detailed, description and characterization of failure detectors can be found in Unreliable Failure Detectors for Reliable Distributed Systems by Chandra and Toueg. They also introduced the concept of unreliable failure detectors:

In this paper, we propose an alternative approach to circumvent such impossibility results, and to broaden the applicability of the asynchronous model of computation. Since impossibility results for asynchronous systems stem from the inherent difficulty of determining whether a process has actually crashed or is only "very slow," we propose to augment the asynchronous model of computation with a model of an external failure detection mechanism that can make mistakes. In particular, we model the concept of unreliable failure detectors for systems with crash failures.

The failure detectors that Chandra and Toueg describe are distributed, rather than global, failure detectors. Each process uses local state to keep a list of other processes that it suspects have failed, and adds and removes processes from this list based on communication with other processes. A local failure detector like that can make two kinds of mistakes: putting processes that haven't failed onto the list, and not putting processes that have failed onto the list. Remember, that like in all real distributed systems, there is no central oracle that can tell a node whether its list is correct. These two kinds of mistakes lead to the definition of two properties. From Chandra and Toueg:

completeness requires that a failure detector eventually suspects every process that actually crashes, while accuracy restricts the mistakes that a failure detector can make.⋄

Let's start with the best combination of these properties, a failure detector where every correct process eventually permanently suspects every crashed process of failing (strong completeness), and never suspects a non-crashed process (strong accuracy). This failure detector, P, can be seen as the ideal asynchronous failure detector. It doesn't make mistakes, and it does the best it can at detection while remaining asynchronous. At the other end of the scale is ◇W. With this failure detector, every crashed process is eventually permanently suspected by some crashed process, and eventually some correct process is not suspected by any correct process. ◇W, unlike P, can make lots and lots of mistakes, for arbitrarily long amounts of time.

Before going further, it's worth introducing one piece of notation. Even informal writing about failure detectors tends to make heavy use of the ◇ operator from temporal logic. Don't be put off by the notation, ◇F simply means F is eventually true. There is some state in the future where F is true. To better understand that, let's compare the failure detectors ◇W and W. Both of these meet the weak completeness condition:

Weak Completeness. Eventually every process that crashes is permanently suspected by some correct process.

W meets the weak accuracy condition:

Weak Accuracy. Some correct process is never suspected.

While ◇W only meets the strictly weaker eventual weak accuracy condition.

Eventual Weak Accuracy. There is a time after which some correct process is never suspected by any correct process.

Comparing those two makes the difference more obvious. ◇W is allowed to make mistakes early on (before a time) what W isn't allowed to make.

The existence of these classes of failure detectors allows meaningful comparisons to be made about the difficulty of different distributed problems, much like complexity classes allow us to compare the difficulty of computational problems. For example, it is known that consensus can be solved using ◇W if only a minority of processes fail. The problem known as non-blocking atomic commit (NB-AC), on the other hand, cannot be solved with ◇W if there is a single failure. In a very meaningful sense, NB-AC is harder than consensus. When I first learned about that result, I found it surprising: my assumption had been that uniform consensus was equivalent to the hardest problems in distributed systems.

First, let's define the NB-AC and consensus problems. They have a lot in common, both being non-blocking agreement problems. Both consensus and NB-AC attempt to get a multiple processes to agree on a single value without blocking in the presence of failures. Two-phase commit is, like NB-AC and consensus, an agreement protocol, but it is a blocking one. The presence of a single failure will cause 2PC to block forever.

Guerraoui defines consensus with three conditions:

Agreement: No two correct participants decide different values

Uniform-Validity: If a participant decides v, then v must have been proposed by some participant

Termination: Every correct process eventually decides

Uniform consensus expands the agreement condition to a stronger one, called uniform agreement:

Uniform-Agreement: No two participants (correct or not) decide different values.

Consensus is, therefore, about deciding. NB-AC, on the other hand, is about accepting or voting on whether to commit a transaction. Guerraoui defines it with four conditions:

Uniform-Agreement: No two participants AC-decide different values.

Uniform-Validity: If a participant AC-decides commit, then all participants voted ''yes''.

Termination: Every correct process eventually AC-decides

NonTriviality: If all participants vote yes, and there is no failure, then every correct participant eventually AC-decides commit.

Notice how similar this appears to be to the uniform consensus problem. Guerraoui describes how it is the last one of these conditions, NonTriviality, which has the effect of requiring that a solution to NB-AC has precise knowledge about failures. To meet the Termination condition, eventually each process needs to commit or abort. Eventual strong accuracy doesn't provide the knowledge required to make that decision, because it admits a time t where a process is simply delayed but it's vote is ignored (violating the uniform validity or NonTriviality conditions depending on the vote). Weak accuracy doesn't provide the right knowledge either, because it allows an incorrect abort (and hence violation of NonTriviality) based on incomplete knowledge of the failed set.

If you only have unreliable failure detectors, uniform consensus is no harder than consensus, though reliable failure detectors (like P) make consensus easier than uniform consensus. Therefore, the addition of the uniform agreement requirement doesn't explain why consensus can be solved with ◇W and NB-AC can't. Instead, it's that seemingly harmless NonTriviality condition that makes NB-AC harder. That's a great example of how intuition is often a poor guide in distributed systems problems: seemingly similar problems, with very similar definitions, may end up with completely different difficulties.
 The Essential Leslie Lamport 2014-03-30T00:00:00+00:00 http://brooker.co.za/blog/2014/03/30/lamport-pub
The Essential Leslie Lamport

Some of my favourite Leslie Lamport publications.

After it was announced that Leslie Lamport had won the 2013 A.M. Turing award, the link to his list of publications found popularity on most of the tech-related sites I visit. It's an excellent page, with a long (and growing) list of Lamport's publications, and witty comments by the author on each one. The whole list is worth a read, but can feel overwhelming, so I thought I'd try distill it down it some papers that I feel are really worth reading, if you read nothing else on that page. The criteria are: I like these papers for some reason. I'd probably make a different list if I wrote this post again next week.

The algorithm is quite simple. It is based upon one commonly used in bakeries, in which a customer receives a number upon entering the store. The holder of the lowest number is the next one served.

In A New Solution of Dijkstra's Concurrent Programming Problem Lamport describes the mutual exclusion problem formally posed by Dijkstra, and presents a solution to it. The bakery algorithm is remarkable. Unlike the earlier solutions, which depended on shared memory locations with fairly restrictive behaviors, the bakery algorithm works without any underlying mutual exclusion. Lamport's invention, or discovery, of this algorithm seems to kicked off a cascade of other solutions. Szymanski's, which seems to have been the first to offer both strong fairness and use of a fixed number of shared variables of a bounded size, is particularly interesting.

Why this is worth reading: The bakery algorithm, while not very relevant to today's concurrent software due to changes in memory models, is very simple, very beautiful, and solves a complex problem in an innovative way. It's simply a beautiful piece of computer science.

In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation "happened before" is therefore only a partial ordering of the events in the system. We have found that problems often arise because people are not fully aware of this fact and its implications.

Being able to totally order the events can be very useful in implementing a distributed system. In fact, the reason for implementing a correct system of logical clocks is to obtain such a total ordering.

Time, Clocks and the Ordering of Events in a Distributed System is Lamport's most widely cited paper by a large margin. Google Scholar claims over 8000 citations, CiteSeer finds 2335. His next most cited paper, The Byzantine Generals Problem, has fewer than a quarter of as many citations. Citeseer's view of co-citations of this paper is interesting. The top two are Fischer, Lynch and Paterson's Impossibility of Distributed Consensus with One Faulty Process which contains the famous FLP impossibility result, and Lamport's own The Byzantine Generals problem. Browsing through the papers that cite both of these, it's disturbingly easy to find cases where they are included more for name recognition than any real relevance to the subject at hand.

Why this is worth reading: Aside from the sad realities of citation practices, this is legitimately a fascinating, important and highly influential paper. The paper points to The Maintenance of Duplicate Databases as the first published description of logical clocks in distributed systems, and both extends and clarifies the idea. Time, Clocks... presents a way to extract a deterministic total ordering (note, not the total ordering) from a partial ordering of events. It also introduces the idea of replicated state machines, which Lamport later expanded on in The Implementation of Reliable Distributed Multiprocess Systems. It deserves to be recognized for both of these contributions, and is well worth reading because it presents the foundation of these ideas in a way that's easy to understand. Don't be ashamed if you skip over the proof in the Appendix, but it's worth your time if you'd like to get a deeper understanding of why logical clocks work.

We cannot ensure that the states of all processes and channels will be recorded at the same instant because there is no global clock; however, we require that the recorded process and channel states form a "meaningful" global system state.

The algorithm described in Distributed Snapshots: Determining Global States of a Distributed System, written by Lamport with K. Mani Chandy, does something that is apparently impossible: it creates a consistent global snapshot of a distributed system without requiring global synchronization. It does this by ensuring that a snapshot is taken of the local state of each process in the system, along with every message in flight to that process at the time that local snapshot was taken. The wikipedia page has a nice summary of how it works.

Why this is worth reading: the algorithm presented in this paper, like many great algorithms, does something that seems really difficult in a way that, in retrospect, appears to be simple or even trivial. The paper also does a nice job of explaining the system model, and breaking down each step of the algorithm in clear terms. It's worth reading because it's a fascinating piece of computer science, and because of the way it presents its ideas.

Designing a concurrent program is a difficult task; no formalism can make it easy.

when designing a concurrent program, we cannot restrict our attention to what is true before and after its execution; we must also consider what happens during its execution.

Lamport has written a great deal on temporal logic, including the deservedly heavily-cited The Temporal Logic of Actions, but none of his other papers on the subject are (in my opinion) as well written as the earlier What Good Is Temporal Logic? This paper came fairly early on in the development of TLA, and isn't a complete picture of the idea, but what is there is presented in a way that is both precise and compelling. The paper compares the approach to Milner's work on the Calculus of Communicating Systems, explains the philosophy of temporal logic, explores the value of specifications, and presents the idea of refinement mappings. One point of interest is the conclusion about the expense of mechanical verification, something that has been substantially improved since 1983 more by hardware power than by theory.

Why this is worth reading: it is excellent scientific writing, and covers a lot of ground in not much text.

as commerce flourished, priests began wandering in and out of the Chamber while the Synod was in progress

The Part-Time Parliament is important because of what it contains, and when it was published. It describes, it a fun but impractical way, the Paxos algorithm for distributed consensus. Originally submitted in 1989 (or 1990, depending on who you believe), it came at around the same time as Oki and Liskov's work on viewstamped replication and is one of the earliest solutions for a problem of both practical and theoretical importance. Paxos Made Simple, Cheap Paxos, Fast Paxos and Vertical Paxos and Primary-Backup Replication all contain more easily understandable descriptions of various variants of Paxos.

Why this is worth reading: it's fun, has a great sense of humor, and no sense of self-importance to go with its real importance.

Don't read this if: you're trying to understand or implement Paxos.
 Snark, Chord, and Trust in Algorithms 2014-03-08T00:00:00+00:00 http://brooker.co.za/blog/2014/03/08/model-checking
Snark, Chord, and Trust in Algorithms

Good journals, well-known authors and informal proofs are not sufficient.

Mars Code, in February's CACM, is a very interesting look from the outside at some of the software engineering practices that helped make the Mars Science Laboratory mission successful. The authors cover a lot of ground in the article, from code reviews to coding standards to model extraction and model checking. While writing about model checking, they tell the story of Snark, a non-blocking deque algorithm.

The Snark paper looks great. The algorithm is presented clearly, including both clear text descriptions and blocks of C-like pseudocode. It's published in a well-respected journal, LNCS. It dedicates four and a half of its fifteen pages to a well-structured and clearly written sketch proof of the correctness of the algorithm, with clear diagrams explaining some of the tricky cases. It's got Guy Steele on the author list. It's from Sun. As far as my is this paper likely to be trustworthy? heuristics go, this one doesn't raise many suspicions.

Unfortunately, Snark is broken. Not subtly broken on an obscure liveness measure, but fundamentally broken in that it's unsafe. In DCAS is not a Silver Bullet for Nonblocking Algorithm Design, Doherty et al lay out two bugs in the Snark algorithm. It's worth noting, though, that et al in this case includes most of the authors of the original paper. The paper explains the bugs well, and it's interesting how subtly 30 lines of code can be broken. It's well worth reading, especially if you are interested in non-blocking algorithms. Later, Leslie Lamport used the same bugs as a test of the PlusCal language. In Checking a Multithreaded Algorithm with +CAL he explains how he model checked the original and fixed Snark algorithms using TLC.

Snark is not an isolated example either. Another great example is Chord. The hits are similar: top authors, top journal, good institution, and a detailed sketch proof. In Chord's case, it's also widely implemented and well respected. It even won the 2011 SIGCOMM Test of Time Paper Award. Like Snark, Chord appears to be subtly broken. Pamela Zave, in Using Lightweight Modeling To Understand Chord, found a number of places where either Chord is broken, or the version presented in the paper (and proven in the proofs!) isn't safe. More details can be found in the slides for a talk titled How to make Chord Correct.

The purpose of pointing out these examples isn't self-superiority or even schadenfreude, but to demonstrate that the heuristics we use when deciding whether to trust a published algorithm don't always work. Even talented teams of really smart people get this stuff wrong all the time. Not only are multi-threaded and distributed algorithms tricky to reason about, but techniques for proving their correctness are also complex and often not approachable. Most practitioners lack the training to verify the correctness of the proofs that do exist. Often, it's even quite challenging to write down the requirements sufficiently clearly, though techniques like Refinement Mappings can often help.

Modeling, specification and model checking play an important role. Lamport demonstrated issues in Snark using TLA+, Doherty et al used Spin, and Zave used Alloy. Each of these tools has areas of strength, but each allows computer-aided checking of specifications or models. Lamport puts it this way:

a hand proof is no substitute for model checking. As the two-sided queue example shows, it is easy to make a mistake in an informal proof.

Tools like TLA+ have a big advantages for practitioners: they tend to be much more approachable than proof techniques, allow exploration of algorithm variants without starting from scratch, and allow easy exploration of the effect of a model on the correctness of a specification.The also look like code, and the tools frequently look and behave like the editors and compilers most are familiar with. If you can pick up Haskell or Scheme, and have a passing familiarity with basic set theory, you can learn TLA+, PlusCal or Spin. As another benefit, formal specifications of algorithms like Raft and Cheap Paxos are often (though not always) more complete and precise than either the text or pseudocode descriptions given in papers. Theses specifications allow automated model checking, and provide evidence that such model checking has been done. A specification provides some evidence that the author has thought through all the edge cases of an implementation, at least within the boundaries of the model.

Of course, model checking isn't a panacea. It's just as easy to make mistakes in either the specification or invariants as it is in a proof. Lamport explains some other limitations of model checking:

Model checking is no substitute for proof. Most algorithms can be checked only on instances of an algorithm that are too small to give us complete confidence in their correctness. Moreover, a model checker does not explain why the algorithm works.

Traditional software engineering practices, such as unit tests, are another promising approach. Approaches for testing distributed and multi-threaded algorithm implementations, with good coverage of ordering and failure cases, are still in their infancy, but there is a lot of very encouraging progress. More broadly, and more in industry than academia, we need a cultural shift. A developer who developed their own block cipher and dismissed concerns with it's easy to reason that it is secure would get laughed at by the security community. Somebody who proposed a new sorting algorithm and refused to demonstrate that it actually sorts things would be the target of derision. People who propose their own distributed algorithms, both in the research press and in practice, are too frequently allowed to get away with trust me and it's obvious as demonstrations of correctness. I'm not accusing the authors of the Snark or Chord papers of this, but it is very common. Depending on what you are doing, that's not good enough. You don't need to read much more than the comments on Lamport's Why We Should Build Software Like We Build Houses to see evidence of a strong anti-design and anti-specification bent in software engineering practitioners. While these formal techniques and methods aren't needed for much of the work programmers do, there are many types of systems for which they are extremely helpful (and should more often be required).

If you're looking for a distributed algorithm, and your business, your life or your reputation are on the line, don't accept I copied it from a paper. Don't accept it's obviously right. Don't accept correctness based on reputation. Think twice before trusting only an informal proof.
 Distributed Consensus: Beating Impossibility with Probability One 2014-01-12T00:00:00+00:00 http://brooker.co.za/blog/2014/01/12/ben-or
Distributed Consensus: Beating Impossibility with Probability One

Distributed systems models are critical to understanding impossibility results

Reading Nancy Lynch's 1989 paper A Hundred Impossibility Proofs for Distributed Computing was the first time I came to a real understanding of the value of impossibility proofs. Before reading it, I was aware of many of the famous impossibility proofs, including Brewer's CAP Theorem, FLP impossibility and the lower bounds of number of rounds needed for consensus, but I'd always held existence proofs to be somehow more important. My attitude was along these lines:

What good are impossibility results, anyway? They don't seem very useful at first, since they don't allow computers to do anything they couldn't previously.

Following that question (in Section 3.5 of A Hundred Impossibility Proofs), Lynch goes on to justify the importance of impossibility proofs. The whole case is worth reading, but the one that resonates with me most strongly as a practitioner is:

... the effect of the impossibility result might be to make a systems developer clarify his/her claims about what the system accomplishes.

Nearly 25 years have passed since the publication of this paper, and that remains something of a hopeful dream. Despite the efforts of Lynch, Lamport, Aphyr, Daniel Abadi and many others, there's still a long way to go in having distributed systems developers clearly state the guarantees their systems are making.

Another effect of impossibility proofs, and the clear definition of the models in which they exist, has been research into how little it is possible to change the model to get around the impossibility result. Easily my personal favorite result in this area is another paper from the 1980s, Michael Ben-Or's Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols from 1983 (sadly, I can't seem to find an open-access version of that paper), and a similar result by Rabin in the same year. Ben-Or looked at the FLP impossibility result, and discovered an algorithm which can achieve consensus with probability one in a slightly modified system model.

The first two sections of the paper lay out the problem to be solved, describe the properties of the solution and present the system model. The system model is the standard asynchronous message passing one, with the additional ability of each process to make non-deterministic decisions. This includes the key difference between the problem Ben-Or is solving, and the problem FLP proves is impossible. At each step (i.e. after receiving a message), a process can make a decision based on its internal state, the message state, and some probabilistic state. FLP's processes can't do the last of these: the decisions they make must be deterministic based only on their internal state, and the message state. This is a great illustration of the importance of models in distributed systems proofs. A slight variation of the model turns the problem from an impossible one, to one that is both possible and not particularly complex.

The other key point from section 2, which the correctness of the whole algorithm depends on, is this one:

If for all P, x_p = v, then the decision must be v.

In the paper's language, x_p is the original binary input made by process P. This is different from the majority wins model which is frequently used when informally talking about consensus. The algorithm is correct if it chooses 1, as long as at least one of the original processes originally proposed 1. In a system with five processes, if four propose 0 and one proposes 1, then 1 is still a correct solution. If all five propose 0, only 0 is the correct solution. This definition of correctness becomes critical when we look at the algorithm itself.

The algorithm proceeds in rounds, with four steps per round. In the first step of each round, each process broadcasts it's x_p, along with the round number. It then waits until it receives N - t of these first-step messages, where N is the number of processes, and t is the number of faulty processes (more on t later). The second step then depends on the set of messages received.

If more than N/2 messages have the same v, then the process broadcasts a message the paper calls a D-message, basically just a message indicating that the process has seen a majority of the same value. Obviously if there have been no failures, this happens on the first round (because it's binary consensus, and there's always a majority). Similarly, in the trivial case, where all x_p were the same, all processes will send D-messages. On the other hand, if a process has seen a split vote, it sends a message indicating that it's still unsure.

In the third step, each process waits for N-t of the step 2 messages, and counts how many of those were D-messages. If it gets only one D-message it sets x_p to the v in that message for future rounds. If a process gets more than t D-messages, we're done and can decide on v. In this case, all the D-messages will have the same v, because it's not possible in step 2 for more than one v to be in more than N/2 messages. At this point, the algorithm may be feeling oddly similar to Paxos' Synod protocol. Finally, if no D-messages were received, the process does something interesting - it randomly selects a new v with probability 0.5.

This is where things start to get interesting for the correctness criterion. If a process gets to this random selection part of step 3 in the first round, it must be true that x_p didn't have the same value for all P. If that isn't the case, all the processes could chose a different v, and break the correctness of the protocol. For this protocol to be true, it must decide in a single round in the trivial case, and not allow random re-selection. This protocol does two things, random re-selection and non-triviality, which are not obviously compatible at first glance.

The number of rounds used by this algorithm, and it's Byzantine fault tolerant counterpart, is surprisingly low. For many executions, consensus can be reached on the first round, and the number of rounds increases as slowly as you would expect the number of randomly selected ties to increase. Here's the number of rounds needed for each of 100k runs of the N=5 t=1 case based on a simulation of the algorithm:

I find this paper particularly interesting for a few reasons. The first reason is that it demonstrates how sensitive the FLP result is to the problem statement and model in which it is proven. As distributed systems practitioners who use academic research and formal models to inform our designs (as we should), we need to be careful to not over- or understate what various results actually mean. It's possible, and actually extremely common, to read the CAP and FLP results to mean something like distributed consensus is impossible, when they actually mean exactly this problem is impossible in exactly this system model. These results should only be extended to other problems and other models with care.

The second reason is that it's a very creative solution to a tricky problem. Backed into a corner by FLP, Ben-Or found a very creative solution that still solves a useful problem in a meaningful system model. For practitioners like me, that's the dream. I want to solve real problems in real systems, and I really admire solutions like this. The third reason is that it's a great reminder, when faced with a claim that a system is solving an apparently impossible problem, that we should ask exactly what problem is being solved, and in exactly what system model. It would be easy to package up Ben-Or's result in a press release titled New Algorithm Proves FLP Wrong, but that would be missing the point entirely.
 Restricted Transactional Memory on Haswell 2013-12-16T00:00:00+00:00 http://brooker.co.za/blog/2013/12/16/intel-rtm
Restricted Transactional Memory on Haswell

Exploring the performance of Intel's RTM

In my last post, I looked at the performance of HLE on Intel's Haswell processor, and found that while it offered a nice speedup in some cases, it can cost performance in others. Still, Intel's TSX is an extremely exciting technology. In this post, I look at the other half of TSX, which Intel calls Restricted Transactional Memory.

If you've never heard of transactional memory before, it's worth reading up. As usual, the Wikipedia article isn't a bad place to start. Some languages, like Clojure, offer software transactional memory out of the box. When it fits, STM can be an extremely nice way to write concurrent programs. The programming model can be simpler, and some classes of bugs (correctness, mostly, rather than liveness) are easier to avoid.

Unlike all the great STM libraries, the current interfaces available to RTM, at least in the form of compiler builtins, don't offer much in the way of a simpler programming model. They do, however, offer us a great way to taste some of the performance benefits that Intel promises for RTM. First, let's take a look at what Intel says about RTM. Starting with the Intel® 64 and IA-32 Architectures Optimization Reference Manual:

Intel® Transactional Synchronization Extensions (Intel TSX) aim to improve the performance of lock-protected critical sections while maintaining the lock-based programming model

OK, so a simpler programming model isn't really Intel's aim here. I'm still pretty sure that there are great opportunities for TM libraries, some of which are already starting to appear, like xsync. Some more from the manual:

Intel TSX allows the processor to determine dynamically whether threads need to serialize through lock-protected critical sections, and to perform serialization only when required. This lets hardware expose and exploit concurrency hidden in an application due to dynamically unnecessary synchronization through a technique known as lock elision.

That's the high-level view. When the CPU detects that the lock isn't held, it tries to run without it. If that all goes horribly wrong, because another core tried to do the same thing, the processor undoes its misdeeds and tries again with the lock. It's clever stuff, and with inter-core synchronization becoming more and more of a bottleneck in multicore systems, it's not surprising Intel's investing in it.

Let's take a look at how RTM performs. For today's test, I wrote a simple separately-chained hash table, and inserted random longs into it until it reached 1000% occupancy. I also made insertions a little artificially slow by doing tail, rather than head, insertions when chaining. For synchronization, I followed Example 12-3 in the manual, which shows a pattern for the use of RTM. For the fallback lock, I used the simple spinlock from Example 12-4 (without HLE, because you can't use both together on Haswell). In unoptimized assembly, the lock function ended up looking like this:

 movq %rdi, -8(%rbp) movl $-1, %eax xbegin .L10 .L10: cmpl $-1, %eax jne .L12 movq -8(%rbp), %rax movl (%rax), %eax testl %eax, %eax jne .L13 jmp .L9 .L13: xabort $255 .L12: movq -8(%rbp), %rax movq %rax, %rdi call orig_spinlock

 .L9: leave ret

There you can see the two of the three new operations that make up RTM. Interestingly, the <tt>xbegin</tt> operation can jump (hence the label argument), but the patterns in the manual when used with the builtins in GCC don't use that functionality. Next, we see that we test the lock, and if it's free we return right away. Finally, if somebody else has taken the lock, we <tt>xabort</tt> to end our transaction and fall back on the lock path (in this case by calling orig_spinlock, which is my spinlock implementation). The unlock side tests the lock again to differentiate between the elided path and the locked path, and calls <tt>xend</tt> on the elided path. Nothing very complex at all code-wise.

First, let's look at the results of doing a million inserts into a 100k bucket hash table by number of threads. I ran each test 100 times, and inter-test variance was very low (less than 5%). The RTM implementation is in red, and the straight spinlock-based one (with no HLE) is in blue:

The RTM version is repeatably very marginally slower with a single thread (about 0.2% on average), but otherwise faster across the board. The spinlock implementation succumbs to increasing contention costs and is slower than single-threaded, while RTM is faster until 4 threads. The really impressive performance here is at 2 threads, where the HLE version is much, much faster. It shows true parallel speedup on this task, which is impressive considering it's nearly entirely dominated by lock contention. Comparing performance directly:

RTM is nicely quicker across the board, and runs in only 63% of the time with two threads. It's a really great little performance gain, with very little programmer effort.

What happens if we throw HLE into the mix on this program? I added an HLE version of the code (following Example 12-4) to the two I already had. This was the result:

That's extremely interesting. The HLE implementation is a solid 18% slower than baseline on the single-threaded version, then shows a massive performance advantage until 8 threads. It doesn't improve total parallel speedup beyond three threads, but does very effectively prevent slowdown.

I started looking at this hoping to find some good answers, and it just left me with more questions. Clearly, HLE and RTM have great potential to improve multi-threaded performance on contended data structures, but it's not clear-cut when they should be used. So far, my experiments have shown RTM is better across the board than nothing, while HLE can be even better than that at a potential cost with one thread.

I suspect it's going to take a while for compiler and library writers to untangle all of this. We're not going to be seeing the full performance benefits of these features any time soon.

I'll release the source for these tests as soon as I can.
 Hardware Lock Elision on Haswell 2013-12-14T00:00:00+00:00 http://brooker.co.za/blog/2013/12/14/intel-hle
Hardware Lock Elision on Haswell

Exploring the performance of Intel's HLE

A couple of months ago, I bought myself a new home PC, upgrading from my old Core2 Q6600 to a shiny new Haswell-based Xeon E3-1240v3. Honestly, I don't use my home PC that much, so the biggest draw for upgrading was trying out some of the features in Haswell, and getting loads of ECC RAM to support another project.

The biggest thing I was excited about with Haswell is Intel's new TSX, a step towards true hardware transactional memory on commodity processors. Transactional memory is a very exciting idea, and seeing better support for it in hardware is really great. TSX provides two broad sets of functionality: restricted transactional memory (RTM), and hardware lock elision (HLE). HLE can be seen as a subset of RTM, offering backward compatibility with pre-Haswell processors. I started my investigations by looking at HLE.

Intel describes Haswell's HLE like this:

If multiple threads execute critical sections protected by the same lock but they do not perform any conflicting operations on eachother's data, then the threads can execute concurrently and without serialization. Even though the software uses lock acquisition operations on a common lock, the hardware is allowed to recognize this, elide the lock, and execute the critical sections on the two threads without requiring any communication through the lock if such communication was dynamically unnecessary.

Based on this description, I was expecting HLE to work best on low-contention locks, possibly significantly increasing performance. Intel's backward-compatible HLE is based on two new instruction prefixes (rather than new instructions): XACQUIRE (F2) and XRELEASE (F3). You basically put the XACQUIRE prefix on the instruction that starts your critical section, and XRELEASE on the instruction that ends it. There are a bunch of good ways to implement locks on x86, but most commonly the start instruction will be an xcgh or cmpxchg, and the end will be one of those, or just a mov.

Luckily, to try this out I didn't need to write any assembly, because GCC 4.8 supports HLE through atomic builtins, thanks to the work of Andi Kleen. Taking advantage of HLE is as simple as passing an additional <tt>ATOMIC_HLE_ACQUIRE</tt> flag to <tt>atomic_exchange_n</tt> in your lock implementation, and <tt>ATOMIC_HLE_RELEASE</tt> to your unlock. GCC then emits the prefixes on the lock instructions.

Implementing a spinlock with <tt>atomic_exchange_n</tt> the difference in the emitted assembly is very simple:

- xchgl (%rdi), %eax + xacquire xchgl (%rdi), %eax

To test all of this out, I implemented a multithreaded count-sort of 100MB of random integers into 10000 buckets in C. The count buckets were protected by striped spinlocks, with some number of buckets sharing a single spinlock. Each thread looped over its unique data, and for each item took the spinlock, increased the bucket count and released the spinlock. Obviously a very short critical section, and probably better implemented without locks (directly with an atomic cmpxchg, for example), but I'm only starting out here.

I then ran two versions of the program for various thread counts and lock counts: a version with the HLE prefixes and a version without them and measured the difference in performance:

Here's a cut through the number of locks, for 3 threads (blue) and 10 threads (red). With 3 threads, HLE is faster across the board, and with 10 threads, HLE is a wash with more locks and a big loss with fewer. Both win big with a single lock:

The results are actually very interesting. For this (admittedly extremely lock-intensive) program, the version with HLE takes nearly twice as long as the one without when run with a single thread. However, when run with one lock and 10 threads, a massive amount of contention, the HLE version more than 6 times faster. That's pretty amazing.

If we peek under the hood a bit, we should be able to see what's going on inside the processor to make this big performance differences. As always with low-level CPU performance stuff, perf stat is a great place to start. First, let's look at a case where HLE is much faster, with 3 threads and 10 locks. The HLE version is more than 2x faster in this case.

The first step of perf stat for the two versions shows this for the HLE version: 1,333,417,638 instructions # 0.20 insns per cycle and this for the non-HLE version: 1,333,549,171 instructions # 0.09 insns per cycle

The number of executed instructions is nearly the same, as expected, but instructions per cycle is very different. Obviously, the CPU is doing something other than running instructions, and that something is most likely waiting for memory. Looking at some of the cache counters makes this more obvious. First, the version with HLE:

 27,804,277 LLC-stores 25,302,175 LLC-loads 412,030,786 L1-dcache-loads 65,940,443 L1-dcache-load-misses

and the version without:

 67,958,384 LLC-stores 32,624,733 LLC-loads 400,883,047 L1-dcache-loads 89,777,892 L1-dcache-load-misses

Look at the big difference between LLC-stores (writes to Last Level Cache, L3 in our case) explains a big part of the issue here. The difference between L1-dcache-load-misses is also significant. The non-HLE version is making a lot more trips to memory. HLE is clearly doing its job. In the single-lock case, with HLE's 6x performance improvement, the difference in LLC-stores is huge (6x, actually).

So what about the single thread case? Why does HLE make that slower? I don't understand enough about Intel's architecture to make a good guess, but the 2x slower HLE-enabled version is doing about 2x the LLC-stores. I suspect this is an implementation issue with HLE in TSX, and I hope it's an artifact of this benchmark rather than a general performance issue with TSX. More testing, especially more testing with significant critical sections, should tell.

I'll release the source for these tests as soon as I can. I'm hoping to find some time to play with RTM over the holidays, too.
 Beyond iostat: Storage performance analysis with blktrace 2013-07-14T00:00:00+00:00 http://brooker.co.za/blog/2013/07/14/io-performance
Beyond iostat: Storage performance analysis with blktrace

An under appreciated set of IO analysis tools.

If you've spent much time at all investigating IO performance on Linux, you're no doubt already familiar with iostat from the venerable sysstat package. iostat is the go-to tool for Linux storage performance monitoring with good reason: it's available nearly everywhere, it works on the vast majority of Linux machines, and it's relatively easy to use and understand. Some of what it measures can be subtle, and the exact definitions of its measurements can be confusing, and even contentious, but it's still a great start.

Sometimes, though, you need to go into more detail than iostat can provide. The aggregate view from iostat is simple, but makes it difficult to tell which processes are doing which IOs. Averaging over a period of time can hide subtle performance issues and the real causes of may IO-related problems. To get around these issues, you'll want to go deeper. If you have the guts for it, a recent kernel, and a good understanding of IO performance issues, you'll want to reach for blktrace and friends. The blktrace toolkit provides an extremely powerful way to look at the exact IO performance of a Linux machine, at a wide range of levels of detail, and is vastly more capable than the simple iostat.

For a start, let's look at the performance of a random read workload to a magnetic drive, with 16k IOs. The manufacturer's spec sheet says this drive should be delivering about 120 IOs per second on a completely random load. iostat -x has this to say about the drive:

Device: rrqm/s wrqm/s r/s w/s rsec/s wsec/s avgrq-sz sdb 0.00 0.00 124.67 0.00 3989.33 0.00 32.00 avgqu-sz await svctm %util 1.00 8.01 8.02 100.00

As expected, we're doing about 125 random IOs per second, each at 16k (32.00 512 byte sectors), at a mean service time of around 8ms. That's pretty much exactly what we would expect from a 7200 RPM magnetic drive. Nothing to see there, then. Next up, is a drive I'm a little bit suspicious about. The demanding IO application I've been running on it has been sluggish, but other than that I have no real evidence that it's bad. SMART checks out, for as little as that's worth. iostat -x indicates that things are a little slow, but not off the charts:

Device: rrqm/s wrqm/s r/s w/s rsec/s wsec/s avgrq-sz sdf 0.00 0.00 41.33 50.67 1322.67 1621.33 32.00 avgqu-sz await svctm %util 1.00 10.90 10.86 99.87

Time to turn to blktrace and see what we can find out. The first step to using blktrace is to capture an IO trace for a period of time. Here, I've chosen 30 seconds:

blktrace -w 30 -d /dev/sdf -o sdf

The blktrace command writes down, in a group of files starting with sdf, a trace of all the IOs being performed to that disk. The trace is stored in a binary format, which obviously doesn't make for convenient reading. The tool for that job is blkparse, a simple interface for analyzing the IO traces dumped by blktrace. They are packaged together, so you'll have blkparse if you have blktrace. When given a blktrace file, blkparse outputs a stream of events like these:

8,32 0 19190 28.774795629 2039 D R 94229760 + 32 [fio] 8,32 0 19191 29.927624071 0 C R 94229760 + 32 [0]

At this point I'll have to come clean and admit that the "demanding IO application" is actually the IO benchmark tool, fio, but that doesn't change the results. What you are looking at, in each of those events, is a fixed-field format like this:

major,minor cpu sequence timestamp pid action rwbs offset + size [process_name]

This is nothing more than a stream of events - "this thing happened at this time". The first one means "At 28.774 seconds, a read (R) was issued to the driver (D)". The second one means "At 29.92 seconds, a read (R) was completed (C)". This is just two example events among many. blktrace writes down a large number of event types, so you'll end up with multiple events for each IO. Events include when the IO is queued (Q), merges (M), plugging (P) and unplugging (U) and others. Let's look at a second example, a single traced direct read from this device:

dd if=/dev/sdf bs=1k of=/dev/null count=1 iflag=direct

That should be simple, right? It turns out that the Linux block IO layer is actually doing a bunch of work here:

8,32 3 1 0.000000000 2208 Q R 0 + 2 [dd] 8,32 3 2 0.000002113 2208 G R 0 + 2 [dd] 8,32 3 3 0.000002891 2208 P N [dd] 8,32 3 4 0.000004193 2208 I R 0 + 2 [dd] 8,32 3 5 0.000004802 2208 U N [dd] 1 8,32 3 6 0.000005487 2208 D R 0 + 2 [dd] 8,32 0 1 0.000744872 0 C R 0 + 2 [0]

Here, the IO is queued (Q), a request struct is allocated (G), the queue is plugged (P), the IO is scheduled (I), the queue is unplugged (U), the IO is dispatched to the device (D), and the IO is completed (C). All of that took only 744us, which makes me suspect that it was served out of cache by the device. That's a really simple example. Once merging and read ahead behaviors come into play, the traces can be difficult to understand. There's still a really big gap between having this IO trace, and being able to say something about the performance of the drive. If you're anything like me, you're considering the possibilities of writing a tool to parse these traces and come up with aggregate statistics about the whole trace. Luckily, one has already been written: btt.

Passing our trace through btt gives us a whole lot of output, but the really interesting stuff (in this case) is in the first section. In fact, two lines tell us a huge amount about this disk:

 ALL MIN AVG MAX N --------------- ------------- ------------- ------------- ----------- D2C 0.000580332 0.010877224 1.152828442 2744 Q2C 0.000584308 0.010880923 1.152832326 2744

Here, Q2C is the total IO time (time from being queued to being completed, just like in the example above), and D2C is the IO time spent in the device. The values are in seconds, and N is the number of IOs observed. As was obvious from the iostat output, the queue time isn't very high, so most of what is going on with performance is the device (D2C) time. Here, that's shown by the relatively small difference between the D2C and Q2C lines. The minimum IO time, 584us, is very short. Those IOs must be served from cache somewhere. The mean time, 10.8ms, is slightly high for what we would expect from this drive (it's sibling averaged just over 8ms), but isn't crazy. The maximum, at 1.15s, clearly shows that there's something amiss about this drive. Our healthy drive's maximum D2C over the same test was only 160ms.

If you want even more IO latency detail, btt is capable of exporting nearly all the statistics it calculates in raw form. For example, the -l flag outputs all the samples of D2C latencies. Combined with the plotting capabilities of R or matplotlib, you can quickly make graphs of the finest details of a system's IO performance. Two lines of R gave me this IO latency histogram:

Another useful capability of btt is extracting the offsets of IOs (with the -B flag). The offsets can then be plotted, showing an amazing amount of detail about the current IO workload. In this example, I did an apt-get update then apt-get install libssl1.0.0 on my aging Ubuntu desktop. The whole thing took about 90s, and issued about 7100 IO operations. Here's what the IO pattern looked like:

That's an incredible set of capabilities. Creating a plot of the IO latency histogram of a running system is tremendously powerful, as is graphing access patterns over time. It's also just scratching the surface of the uses of the blktrace family. Other capabilities include counting seeks (though that's getting less interesting as SSDs take over the world), understanding merge behavior, and analyzing the overhead of various parts of the Linux IO subsystem. This is a set of tools that should be more widely known and used.
 Some Patterns of Engineering Design Meetings 2013-05-25T00:00:00+00:00 http://brooker.co.za/blog/2013/05/25/patterns-of-design
Some Patterns of Engineering Design Meetings

On discussing designs.

I spend a lot of time in engineering design discussions and meetings, talking about how we are going to introduce new features, solve problems, and increase capacity. For me, a good design meeting is the highlight of any day - sharing ideas, comparing options and considering alternatives can be extremely rewarding. Good design meetings, unfortunately, aren't the rule. Frequently, meetings don't go anywhere. Earlier in my career, I thought that there is a direct correlation between the complexity of the problem to be solved and the productivity of the design meetings. It felt natural that solving harder problems would be more difficult.

Recently, though, I've been thinking about some of the things that go right and wrong in design meetings, and have come to the conclusion that there is very little correlation between problem complexity and meeting productivity. Instead, the problem typically seems to be that we are starting in the wrong place. To explain what I mean, let me start with the simplest design process in a single-person isolated world.

Identify the current state of the system, where you are.

Identify the goal state of the system, where you are going.

Decide how you are going to get from the current state of the system to the goal state, how do you get there.

Naively, it appears as though group design meeting should focus on step three (how do we get there?). The group considers a variety of different paths from where we are to where we are going, compares their merits, and chooses one of the alternatives. The focus is always on the design, which is what most engineers find most interesting.

Unfortunately, it is this naive belief - the belief that design discussions should focus on design - that derails most design discussions. The most common manifestation of this problem is when different stakeholders enter a design meeting with different goals in mind. Imagine trying to discuss driving directions with somebody who before agreeing on where you are going. "No", you'll say, "we have to turn left on 5th Avenue". "Absolutely not! Right on 5th!". "Left!". "Right!".

There are three forms of this problem that I have observed. One is the simple disagreement, where participants don't have the same goals in mind. All participants have concrete goals, but they aren't the same. The second form is when one or more of the participants haven't really thought about where they want to go. The destination isn't concrete in their head, so they can't meaningfully contribute to the discussion about the route. The third is a mismatch of models. In this case, the participants may agree on the goal, but don't agree on how they see the goal. I want to spend time outdoors, and my colleague wants to play a game of skill. We'd both be happy with a round of golf, but often we can't see that because we don't realize that we are looking at the problem from different angles.

Agreeing on goals can always take some time, but it's almost always time well invested. It's much more wasteful of time when you start discussion the design before you agree on goals. In that case, it becomes very unlikely that the discussion will find consensus, and even less likely that the consensus will have any real value. I've found that starting with goals and requirements is critical to a successful design meeting. This isn't an argument for being inflexible - goals should be allowed to evolve if the discussion of the solution shows them to be incorrect or inadequate - but an argument for explicit consensus.

The other end of the design arrow is just as important to agree on. Before meaningfully discuss directions not only do you need to agree on where you are going, but you need to agree on where you are now. At first glance, it appears obvious that everybody should agree on where we are now. The current state of the world appears to be a simple and concrete thing.

Unfortunately that's not the case. At best, everybody brings a different perspective on the current state of the world to the discussion. Different experience, different levels of exposure to various pieces, and different job roles all contribute to different perspectives. Beyond this, however, is a deeper problem with common understanding. Every system designed by humans is designed to fit not into the real world, but to fit into a mental model of the real world. We don't have the capability to include all possible factors into a design, so we build a simplified mental model to fit the design into. Models necessarily differ between people. The most common forms of differences in mental model are disagreements about model fidelity, how important a factor needs to be before being included in the model, and factor importance, how important any given factor is.

I don't believe that it is possible, or even desirable, to completely match the models of different participants in design meetings. On the other hand, it is critical to spend some time understanding the differences between these models. They will always differ in detail, but need to be the same general shape for productive discussion.

So far, I've mostly written about these patterns of disagreement in context of meeting productivity. The much more serious issue is the issue of meeting outcomes. When we discuss design without agreeing on the current and goal states of the system, we run a high risk of making very bad design decisions. The outcome of a good design meeting is often a compromise, mixing various aspects of each proposal or idea into a coherent whole.

The outcome of a bad design meeting is a false compromise, where various aspects of each proposal are mixed to make a design that doesn't match any model of the current world, and doesn't achieve anybodies goals. This is the most common cause of bad design I have seen in my career: mismatched goals and mismatched models leading to a non-solution. The best way, in my opinion, to avoid this mistake is to make the steps of finding consensus on where we are and where we are going explicit and upfront, and not being ashamed to loop back to them during the discussion of how are we going to get there?.

 Exploring TLA+ with two-phase commit 2013-01-20T00:00:00+00:00 http://brooker.co.za/blog/2013/01/20/two-phase
Exploring TLA+ with two-phase commit

Using testable pseudocode to test a distributed algorithm

There are very few distributed algorithms more widely known by working programmers than the two-phase commit atomic commit protocol. It's a great algorithm to use for teaching purposes: two-phase commit is both extremely simple to write down, and has significant caveats. Some of these shortcomings are obvious, and easily noticed by most students, and some are much more subtle. At a high level, two-phase commit is an atomic commit protocol: it ensures that changes across multiple database systems are either applied to all the systems or to none of them. Assuming a serial stream of transactions, two-phase commit ensures atomicity - the transaction is either fully applied or not applied at all.

A single coordinator (let's call her Alice) runs a group of fried chicken restaurants, and wants each restaurant manager (the literature calls them cohorts, let's them Bob and Chuck) to paint their green restaurant blue. Alice really cares that her customers get a consistent fried chicken experience, so wants to make sure that all the managers do the work or none of them to do it. If Alice simply asked Bob to do the work, then asked Chuck, she'd be in trouble. If Bob went ahead and did the work, then Chuck couldn't (say he didn't have enough paint), Alice would need to ask Bob undo his work. If Bob was then out of green paint, Alice would be stuck with inconsistent restaurant colors. In Alice's world, that's a catastrophe.

Instead, Alice uses two-phase commit. First, she calls Bob and Chuck and asks them to check if they can repaint today. When both acknowledge they can, Alice calls them and asks them to go ahead. For this to work, she doesn't have to get both of them on the same conference call. She just needs to call them one after the other. Alice also needs to be sure that Bob and Chuck won't lie to her about being able to do the work, and that Bob and Chuck will keep answering their phones. If Bob leaves work early after he's acknowledged that he can do the work, but before he does it, Chuck will be left with the cans open and ladders up, and Alice won't be sure if Bob did the painting or not. She doesn't know what to tell Chuck.

Even for such a simple protocol, two-phase commit has some subtle downsides and the distributed nature of the algorithm makes it exceptionally hard to reason about in prose. We could make little dolls of Alice, Bob and Chuck and act out every possible scenario, but that would take a really long time. Even if we managed to do that (and not screw up), we'd need to start the whole exercise again if Alice opened a third chicken frying location. What if we could have a computer do that checking for us? What if we could write down the protocol clearly and precisely, then write down everything we need to make sure is true, then have a computer run through every possible scenario and tell us if it works. That would be good, right?

Leslie Lamport's TLA+ tools allow us to do exactly that - write pseudocode implementations of complex algorithms, and ask the computer to exhaustively check them. Going through every possible path in a code base is a painstaking and time consuming process without any creativity required - the exact kind of problem that computers excel at. Let's see how we can use TLA+ to ask the computer to solve Alice's problem. I've used the PlusCal algorithm language here, because I find it much easier to write and understand than raw TLA+. First, let's define some things about the world:

variables managers = { "bob", "chuck", "dave" }; restaurant_stage = [ i \in managers |-> "start" ];

Here, we're telling PlusCal that there are three managers (Bob, Chuck and Dave), and creating an array of states (one per restaurant) with the initial state of each set to "start". Next, we need to define how each manager behaves:

process (Restaurant \in managers) { c: await restaurant_stage[self] = "propose";

Each manager waits for a call from Alice, proposing that they repaint their restaurant. They'll be happy to wait for ever in this stage, patiently staring at the phone while their employees cut, spice, fry and sell chicken after chicken.

 either { restaurant_stage[self] := "accept"; } or { restaurant_stage[self] := "refuse"; };

In the next stage, the managers are allowed to do one of two things - either accept the work that's been given to them, or refuse to do the work. Using either tells PlusCal that we can go down either of these paths non-deterministically.

 c1: await (restaurant_stage[self] = "commit") \/ (restaurant_stage[self] = "abort");

They then wait for the next call from Alice, giving them the go ahead to paint, or telling them to put away the ladders.

 if (restaurant_stage[self] = "commit") { restaurant_stage[self] := "committed"; } else { restaurant_stage[self] := "aborted"; } }

Finally, they act on Alice's orders - either painting or aborting. Next, we have to specify how Alice behaves. To simplify that code substantially, we can use PlusCal's handy macro feature:

macro SetAll(state, k) { while (k # {}) { with (p \in k) { restaurant_stage[p] := state; k := k \ {p}; }; }; }

This macro loops over every restaurant (in non-deterministic order), and sends them a message. Let's use it to define Alice's behavior:

process (Controller = "alice") variable k, aborted = FALSE; { n: k := managers; n2: SetAll("propose", k);

First up, create the process and define the local variables. Then, send a message to each manager proposing the change.

 k := managers; n3: while (k # {}) { with (p \in k) { await (restaurant_stage[p] = "accept") \/ (restaurant_stage[p] = "refuse"); if (restaurant_stage[p] = "refuse") { aborted := TRUE; }; k := k \ {p}; }; };

Wait for each manager to return the call (checking in non-deterministic order), and write down whether anybody wants to abort the operation.

 k := managers; if (aborted = TRUE) { n6: SetAll("abort", k); } else { n4: SetAll("commit", k); }

If all the managers were happy to continue, then tell everybody to continue. That's the end of the specification of Alice's behavior, and the end of our PlusCal program. Writing down the program like this is valuable already. The precision of the PlusCal language, and the way it ignores many of the other challenges that would complicate real code, forces you to think clearly and completely about the behavior of each player. Programmers are all aware that fuzzy thinking doesn't last long when you have to translate it to code, and this is even more true of PlusCal. Just the act of writing the program this way is valuable. In terms of value, though, we're only just getting started.

TLA+ includes a model checker called TLC. In short, it runs through every possible path of the code and checks some invariants at each stage. Remember all of those non-deterministic steps in the code? When it hits those, it takes all possible paths. To make TLC useful, we need to tell it what it should check, both invariants (things that are true in every state) and properties (things that must become true). The simplest check is one at PlusCal generates itself:

Termination == <>(\A self \in ProcSet: pc[self] = "Done")

In the TLA+ languages, this means "for all self in the set of processes (alice, bob, chuck and dave), check that the program counter eventually reaches Done". The Done state is a magic state that means the code has fallen off the end of our process. This is a valuable thing to check, because it makes sure that all the process run the entire algorithm. Next, we define an invariant:

StateOK == /\ (\A i \in managers: restaurant_stage[i] \in {"start", "propose", "accept", "commit", "abort", "committed", "aborted", "refuse"})

This simply makes sure that restaurant_stage, the variable we have used to simulate the telephone, never goes off into a state we don't know about. Then, we want to check if all the restaurants either get painted or don't:

Committed == /\ \/ <>(\A i \in managers: restaurant_stage[i] = "committed") \/ <>(\A i \in managers: restaurant_stage[i] = "aborted")

Running the code through the handy TLC model checker will check that all of these things are true. Even for this little program, TLC found 718 states the program can be in, 296 of them unique. If Alice opened another two restaurants, these numbers would increase to 21488 states, and 5480 unique states. Long before the time Alice runs a multinational chicken empire, we'd have no chance of enumerating all these states by hand - let alone doing it correctly. To further illustrate the value of TLA+, let's introduce a subtle bug into the system, one that allows Alice to ignore a refuse message from Bob (in the real world, this could be a poorly handled timeout). Replace this line:

if (restaurant_stage[p] = "refuse") {

with this one:

if ((restaurant_stage[p] = "refuse") /\ (p # "bob")) {

That change lets Alice ignore the 'refuse' message from Bob. Running the model checker TLC again reveals something odd. The protocol still works when it shouldn't. We need to tell TLC to check one other invariant: that everybody aborts when somebody asks to. There are several ways to do this, including adding an explicit invariant. Another way to do this is to use the assert functionality in PlusCal. We can track whether each restaurant asked for an abort like this:

or { restaurant_stage[self] := "refuse"; refused := TRUE; };

Then assert that when we are asked to commit:

if (restaurant_stage[self] = "commit") { assert(refused = FALSE); restaurant_stage[self] := "committed";

Running TLC again reveals that the program is broken and that reverting Alice's behavior to always care about Bob's opinion fixes the issue. This reveals the most enlightening thing I've found about playing with TLA+. It's extremely easy to write a TLA+ specification and a set of invariants that work. What's much harder is coming up with a set of invariants that cover all the cases we actually care about, and making sure that modifications to the specification break those invariants. This is a great lesson about writing unit tests too - you have to be very honest to avoid studying to the test if you write the code and write the tests.

In a larger sense, it would be really cool to have a tool that does for TLA+ what Jester does for Java: make random modifications to the specification and show cases where the invariants are not violated. This would be very interesting for building quality invariants, but also for automated exploration of the space of algorithms which meet a given set of invariants.
 C++11's atomic and volatile, under the hood on x86 2013-01-06T00:00:00+00:00 http://brooker.co.za/blog/2013/01/06/volatile
C++11's atomic and volatile, under the hood on x86

How do C++11's atomic and volatile work?

In my previous post Java's Atomic and volatile, under the hood on x86 I look at Atomic and volatile in Java, and how they affect the generated assembly. In this post, I'm looking at std::atomic and volatile in C++.

Like in Java, it's well known that std::atomic and volatile have different meanings in C++, but it's still interesting to take a look at how that translates to what actually gets run. Let's start with a very simple program:

for (int i = 0; i < 500000000; i++) { x += 0x3; }

Then define x in one of three ways:

long x; volatile long x; std::atomic_long x;

Before digging directly into the assembly, we can compare the run-time of the three programs (on a Core2 Q6600 compiled with gcc4.6 -O2):

long took 0.0018s

volatile took 1.9s

atomic_long took 8.5s

It's clear from the difference in run times that these three programs do produce significantly different code. The step up from long to volatile long is 100x, and another 4x up to atomic_long. Starting the with assembly for the long version, we can see why it's so fast:

addq $1500000000, %rsi

Oh gcc, you're sneaky. The compiler has completely discarded the loop, and calculated the result into a constant. Without the guarantees of atomic or volatile, it's free to make optimizations like this. Next, the volatile version:

 movl $500000000, %eax .L2: movq x(%rip), %rdx addq $3, %rdx subl $1, %eax movq %rdx, x(%rip) jne .L2

The inclusion of volatile has forced the compiler to not only run the loop, but also load and store the variable from memory on every run (the two <tt>movq</tt> instructions). The overhead of this is clearly significant, but it's hard to seperate the effects of the two. Moving the load and store out of the loop breaks the volatile guarantee, but keeps the loop:

 movl $500000000, %eax movq x(%rip), %rdx .L2: addq $3, %rdx subl $1, %eax jne .L2 movq %rdx, x(%rip)

That version takes about 0.3s to run, so the it's clear that memory access time still dominates the run time of the program. It's also somewhat interesting the gcc has chosen to load, modify and store instead of doing the add directly to memory. We can modify the original volatile version to do that:

 movl $500000000, %eax .L2: addq $3, x(%rip) subl $1, %eax jne .L2

That's much less code, but it's no faster. In fact, taking the average of a very large number of runs shows that it's about 1% slower on my hardware. perf stat tells the story for the unmodified load-modify-store code:

3,006,477,937 cycles 2,504,227,487 instructions # 0.83 insns per cycle

and for the modified code:

3,035,431,555 cycles 1,504,575,146 instructions # 0.50 insns per cycle

The modified code saves two fifths of the instructions, but drops the instructions per cycle by slightly more. After that diversion, on to the atomic_long version of our original program:

 movl $500000000, %eax .L2: lock addq $3, x(%rip) subl $1, %eax jne .L2

GCC is generating smarter code than java does with volatile, but uses a similar basic approach. It uses the lock prefixed instruction to generate a write barrier. In this case, gcc uses the same instruction to do the addition, which makes the code much simpler (and much faster on some machines). The performance impact of that lock prefix, compared to the nearly identical code above without it, is quite clear. perf stat says:

13,522,633,468 cycles 1,513,530,642 instructions # 0.11 insns per cycle

That's 0.11 instructions per cycle compared to 0.5 for the non-locked version above. Comparing these two pieces of code makes the difference of intention between atomic and volatile quite clear. Even ignoring memory ordering issues, the volatile code can lead to the incorrect answer with concurrent access. Take another look at that code:

 movl $500000000, %eax .L2: movq x(%rip), %rdx addq $3, %rdx subl $1, %eax movq %rdx, x(%rip) jne .L2

If another writer wrote to the location of x between the first and second <tt>movq</tt> instructions, their updates would be completely lost. Clearly, volatile doesn't imply atomic. The picture gets even worse on a multi-processor machine, where the lack of any barriers means that the results are highly unlikely to be correct. Those of us who move between C++ and Java need to be very clear about the difference in meaning between C++ volatile and Java volatile. It's really unfortunate that the designers of Java didn't chose a different keyword.
 Java's Atomic and volatile, under the hood on x86 2012-11-13T00:00:00+00:00 http://brooker.co.za/blog/2012/11/13/increment
Java's Atomic and volatile, under the hood on x86

How exactly do AtomicInteger and volatile do their magic in Java?

It's well known that volatile in Java doesn't mean the same thing as atomic. As Jeremy Manson says:

If you do an increment of a volatile integer, you are actually performing three separate operations: 1) Read the integer to a local. 2) Increment the local 3) Write the integer back out to the volatile field.

On the other hand, the Java memory model is known to offer looser guarantees than some real hardware implementations. Most modern desktops (and most current servers) are powered by x86-family processors, which have fairly predictable memory behavior, especially compared to some other processor families. Despite these stronger guarantees, volatile int doesn't behave like AtomicInteger, even on x86 and even for a very simple operation like counting.

Why not?

To understand what is going on under the hood, let's start with a very simple piece of code, which does only three things:

Launches M threads

Loops a large number of times (N) in each thread, incrementing a shared variable.

Joins the threads.

The three threads are running in parallel, and sharing the value of the variable. For it to end up with the right value at the end (M*N), two things need to be true. First, changes made by one threads must be immediately visible to the other threads. Second, changes made to the variable must be atomic - each threads must perform the load, increment and save as one effective operation. Visibility is not enough, because it allows something like this to happen:

Thread 1 loads 5

Thread 1 increments its private copy to 6.

Thread 2 stores 6

Thread 1 stores 6

Even if changes are immediately visible, increments done by done by one thread can be lost by others. To see the effects of this, we can start with a version of the program with a non-volatile shared variable, which offers neither visibility nor atomicity. On my system, based on a four-core Intel Core2 Q6600 CPU, with 3 threads each counting to 5 million the result is:

Final value 7147559, expected 15000000, time 0.05ms

That worked rather poorly, but was nice and quick. Adding volatile adds visibility, but not atomicity. With the same parameters:

Final value 5191650, expected 15000000, time 2286ms

In this particular sample, it's actually worse, and much much slower. It's worth noting that both of these return some seemingly random value between 5 million and 15 million, mostly clustered near to 5 million. Obviously AtomicInteger, which guarantees both atomicity and visibility, will solve the problem:

Final value 15000000, expected 15000000, time 3041ms

The Atomic version is correct. It's also slower, but not by a huge margin. Clearly these three versions are leading to very different CPU behavior, so let's turn to -XX:+PrintAssembly to see if we can figure out what's going on. First, the increment code from the non-volatile version:

add $0x10,%ecx

Notice how the increment has turned into an add of 16. The compiler has optimized away a lot of the looping, and is doing 1/16 of as many passes through the actual loop as we specified. I'm somewhat surprised that it even does that amount of work. On to the volatile version. Here, we can see the three separate steps:

mov 0xc(%r10),%r8d ; Load inc %r8d ; Increment mov %r8d,0xc(%r10) ; Store lock addl $0x0,(%rsp) ; StoreLoad Barrier

I wrote about the StoreLoad barrier in my previous post on Java's volatile. It's exact semantics can be subtle, but the quick version is that it does two things: makes every store before the lock addl visible to other processors, and ensures that every load after the lock addl gets at least the version visible at the time it is executed. In this case, volatile gives visibility, in that each of the processors immediately gets the version from the other processors after each increment. What it doesn't give is atomicity. Any stores that happen on other processes between the load and the store are lost, as in the example above. AtomicInteger fixes this problem by seeking the processor's help to be truly atomic.

mov 0xc(%r11),%eax ; Load mov %eax,%r8d inc %r8d ; Increment lock cmpxchg %r8d,0xc(%r11) ; Compare and exchange

To understand how this works, we need to understand what cmpxchg does. The Intel Software Developer's Manual describes it as:

Compares the value in the EAX register with the destination operand. If the two values are equal, the source operand is loaded into the destination operand. Otherwise, the destination operand is loaded into the EAX register.

So, we're loading the value, incrementing it, then only writing it into memory if nobody else has overwritten it with a different value since we loaded the value. Obviously, the operation needs to be retried if the store to memory fails. Indeed, the Java does just that. I'll spare you the verbose assembly version, and present that Java version from OpenJDK:

public final int incrementAndGet() { for (;;) { int current = get(); int next = current + 1; if (compareAndSet(current, next)) return next; } }

The compareAndSet function is a native implementation from Unsafe.java. Counting the instructions from the disassemblies would suggest that the Atomic version should be, at most, 100 times slower than the non-Atomic non-Volatile version. So why is it tens of thousands of times slower? The best evidence comes from modifying the programs so the threads don't contend - simply running one, then the other. Removing the contention doesn't do anything to the non-Atomic non-volatile version: it still runs in about 0.05ms. The performance difference when contention is removed from the volatile and Atomic versions is rather startling. The volatile version drops from 2286ms to 0.1ms, and the Atomic version drops from 3041ms to 0.15ms. In both cases, the serial version is around twenty thousand times faster. In trivial examples like this, it's clear that Amdahl's Law, which assumes that paralellizing a program doesn't make it slower, is highly over-optimistic. This is parallel slowdown in action.

To understand what's making this amazing 10-thousand-fold difference in program runtime, we can turn to Linux performance counters, and run the JVM under the perf stat program. Here are some highlights of the report for the two versions, with the no-contention (fast) version first:

 806,970,762 instructions # 0.52 insns per cycle 165,637,507 branches # 57.996 M/sec 2,293,172 branch-misses # 1.38% of all branches 195,282,430 L1-dcache-loads # 68.375 M/sec 4,348,143 L1-dcache-load-misses # 2.23% of all L1-dcache hits 1,978,387 LLC-loads # 0.693 M/sec 110,472 LLC-load-misses # 5.58% of all LL-cache hits 0.713189740 seconds time elapsed

Then the slow version, with contention:

 1,066,079,264 instructions # 0.08 insns per cycle 227,089,065 branches # 17.347 M/sec 10,659,632 branch-misses # 4.69% of all branches 408,262,745 L1-dcache-loads # 31.187 M/sec 24,905,458 L1-dcache-load-misses # 6.10% of all L1-dcache hits 21,168,959 LLC-loads # 1.617 M/sec 12,133,097 LLC-load-misses # 57.32% of all LL-cache hits 3.271893871 seconds time elapsed

We must be careful interpreting these results, because they are polluted with data not related to our program under test, like the JVM startup sequence. Still, the differences are quite obvious. Our first smoking gun is instructions per cycle (the first line) - this measures how many CPU instructions were executed per clock cycle. This is the amount of time the CPU could actually do work without being blocked on other things, like loading data from RAM. Higher is obviously better. The fast no-contention version gets a respectable 0.52 instructions per cycle. The slow version scores a terrible 0.08 - indicating 92% of cycles were wasted. Moving down the report indicates why this is the case, with the last line being the most damning. We went from 110 thousand LLC (last-level cache) misses in the fast version, to over 12 million in the slow version. The slow version is spending most of its time waiting for data from RAM.

Why does contention cause an otherwise identical program to behave so differently? The answer lies in the way that the CPUs in my multi-core system are forced to keep their caches in sync to meet the requirement of visibility. The short version is that each core keeps track of which cache lines (chunks of memory in cache) are shared with other CPUs, and puts in extra effort to tell other CPUs about writes it makes to those lines. If you want to the long version, Ulrich Drepper explains it very well in section 3 of his excellent What Every Programmer Should Know About Memory. I highly recommend reading it.

The most important lesson here is how critical profiling is to writing high-performing parallel programs. Sometimes our intuition (more parallel equals faster) can be dangerously incorrect. The second lesson is the importance of minimizing contention and communication between cores.
 Are volatile reads really free? 2012-09-10T00:00:00+00:00 http://brooker.co.za/blog/2012/09/10/volatile
Are volatile reads really free?

Some claim that reads from volatile variables are free in Java on x86. Is that claim true?

There is a somewhat common belief among Java programmers that reads from volatile variables are free. Are volatile variable 'reads' as fast as normal reads? from StackOverflow is a perfect example, because it's the top result I get from Google for most related searches. The top answer says:

On an x86, there is no additional overhead associated with volatile reads.

and goes on to say:

JSR-133 classifies four barriers "LoadLoad, LoadStore, StoreLoad, and StoreStore". Depending on the architecture, some of these barriers correspond to a "no-op", meaning no action is taken, others require a fence. There is no implicit cost associated with the Load itself, though one may be incurred if a fence is in place. In the case of the x86, only a StoreLoad barrier results in a fence.

Reading Doug Lea's The JSR-133 Cookbook for Compiler Writers gives the same impression. It says:

Issue a StoreStore barrier before each volatile store.

and

Issue a StoreLoad barrier after each volatile store. Note that you could instead issue one before each volatile load, but this would be slower for typical programs using volatiles in which reads greatly outnumber writes. Alternatively, if available, you can implement volatile store as an atomic instruction (for example XCHG on x86) and omit the barrier. This may be more efficient if atomic instructions are cheaper than StoreLoad barriers.

and

Issue LoadLoad and LoadStore barriers after each volatile load.

Doug lists the StoreStore, LoadLoad and LoadStore barriers as noops on x86. It makes some sense to read this as a validation of the idea that volatile reads are free. No extra instructions are issued for the reads, and instructions are what makes computers take time, so no more time is taken. Right?

The first step to answering that question is seeing if the Java JRE 1.6 actually behaves like Doug says it should. Possibly the easiest way to do this is to add the -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly options to the Java command line, and see the assembly that's being generated by the JIT. I wrote a very small toy program which accessed a volatile variable in a loop (to force the JIT to kick in).

Here's the code it generated for both volatile and non-volatile reads:

nop ;*synchronization entry mov 0x10(%rsi),%rax ;*getfield x

And for volatile writes:

xchg %ax,%ax movq $0xab,0x10(%rbx) lock addl $0x0,(%rsp) ;*putfield x

The JVM is behaving exactly like it should according the to the spec, with one minor difference. It's using lock addl $0x0,(%rsp) as the StoreLoad barrier. The gory details can be found in chapter 8 of volume 3A of Intel's IA-32 developer manual, but the short version is:

Locked operations are atomic with respect to all other memory operations and all externally visible events. [...] Locked instructions can be used to synchronize data written by one processor and read by another processor.

While addl $0x0,(%rsp) does nothing, lock addl $0x0,(%rsp) behaves like the StoreLoad barrier that Doug Lea talks about. The minor difference from Lea's description is the xchg %ax,%ax before the store. xchg does have some memory ordering influence, but I'm not sure of the role it plays here - it seems to me like this would be correct without it, so there must be something I am missing.

Anyway, it looks like what the JVM is doing in this case follows Doug Lea's recommendations. We can expect volatile reads to be free, right?

To test the theory, I wrote a program which does the following:

Launches 3 reader threads, which try to do 500 million reads from a shared variable and stores to a local variable

Launches 1 writer thread, which increments the shared variable 500 million times

Synchronizes their start times, and times them to completion

I ran it on my quad-core machine (Intel Q6600), and did three runs. Once, with a non-volatile shared variable, once with a volatile shared variable and once with a volatile shared variable and no writer thread. The graph below summarizes the results.

In this experiment, volatile writes are nearly 100x more expensive than normal writes. That corresponds well with the volatile writes are expensive mental model. What's most notable, though, is that volatile reads when there is a writer are about 25x more expensive than non-volatile reads. The included error bars show one standard deviation both sides of the mean run time, and clearly show that the speed of volatile read access also varies widely. If the code's the same, then what's going on?

What we are seeing is the effect of the processor trying to keep its contract with the lock instruction, and make sure that the data written by the writer is visible to the readers. Memory access and cache coherency are some of the most expensive things that modern processors do, and it's not easy to predict their performance impact from the assembly code. On the single-threaded single-core x86 processors of the past it was hard enough to read an assembly dump and predict performance. On modern multicore systems, it's extraordinarily difficult.

The third set of results tells another interesting story about volatile reads, one that's closer to the meaning of volatile in C. To illustrate the difference, I wrote a much simpler program which reads a variable, increments it, and writes it back to another variable. Without volatile, the compiler generates code like this:

 nop ;*getfield isum add %r10,%r11 add %r10,%r11 ... 12 more adds ... add %r10,%r11 mov %r11,0x10(%rbx) ;*putfield isum

The loop is unrolled, and the variables simply stored in registers. With volatile, the code looks like this:

test %r11d,%r11d je 0x00007f89bd05e7b4 ;*synchronization entry mov 0x18(%r11),%r10 ;*getfield x add %r10,%r9 ;*ladd mov %r9,0x10(%rbx) ;*putfield isum mov 0xc(%rbx),%r11d ;*getfield this$0

I've only included one piece of the unrolled loop here. The compiler wrapped five sections like this in the larger outer loop, reducing the loop overhead somewhat. It does a whole lot more work per step that the non-volatile version (the details are unimportant), and isn't nearly as aggressive about unrolling (I assume because it's making a heuristic decision based on code size).

It appears as though reads to volatile variables are not free in Java on x86, or at least on the tested setup. It's true that the difference isn't so huge (especially for the read-only case) that it'll make a difference in any but the more performance sensitive case, but that's a different statement from free.

EDIT: It's worth noting that I am not criticizing Doug Lea's The JSR-133 Cookbook for Compiler Writers. He doesn't say that volatile reads are free, and doesn't even suggest it. That's just something that many people seem to have inferred from his writing.
 Highly contended and fair locking in Java 2012-09-10T00:00:00+00:00 http://brooker.co.za/blog/2012/09/10/locking
Highly contended and fair locking in Java

How do explicit locks compare to volatile access?

In my last post on Java's volatile, I showed how (in one set of experiments) Java volatile variable reads don't come for free. The cost of accessing a highly-contended volatile variable in one micro-benchmark came out at about 100x the cost of accessing a non-volatile variable. How does that compare to locking?

In the last post, I presented the results of a program which:

Launches 3 reader threads, which do 500 million reads from a shared variable and stores to a local variable

Launches 1 writer thread, which increments the shared variable 500 million times

Synchronizes their start times, and times them to completion

For this post, I modified it to make the variable non-volatile, and add explicit locking using a ReentrantLock. Performance dropped substantially bad. The graph below is an update of the graph from the last post, including the locking version.

For reads, the locking version of this test is about 33x more expensive than the volatile version (and over 3000x more than the incorrect unsynchronized version). Writes are about 15x more expensive. To put this in perspective, it's still only 545 nanoseconds per lock operation, so individual operations are not really expensive in absolute terms.

The other effect of locking vs. volatile is starvation of threads. The documentation for ReentrantLock says:

The constructor for this class accepts an optional fairness parameter. When set true, under contention, locks favor granting access to the longest-waiting thread. Otherwise this lock does not guarantee any particular access order. Programs using fair locks accessed by many threads may display lower overall throughput (i.e., are slower; often much slower) than those using the default setting, but have smaller variances in times to obtain locks and guarantee lack of starvation.

In my tests, I had fairness disabled and saw significant thread starvation. In about one run in five, the program actually runs in a totally serial order - each thread running to completion before any of the other threads run. I have seen thread starvation issues in real-world code too, but never to this extent. Fair locking fixed this problem, but increased the per-lock time to 32µs (from 0.5µs for the non-fair version). That's an increase of about 60x, for a total of approximately 200x more expensive than a volatile access.

Fair locks in the version of Java I was using are based on the AbstractQueuedSynchronizer. It uses a type of lock queue modified from Craig, Landin, Hagersten locks, which provide a FIFO queue of waiters on a lock without needing to depend on another lower-level locking primitive. It's truly fascinating stuff, and well worth reading.

Given the very high costs of fair locks under contention, it's probably best to avoid them in those situations. There are situations where they work well and are very necessary. From Doug Lea:

Even though they may perform poorly under high contention when protecting briefly-held code bodies, fair locks work well, for example, when they protect relatively long code bodies and/or with relatively long inter-lock intervals

It's probably best to avoid writing high-contention code unless absolutely necessary. Where it is necessary, however, volatile should be tested against locking, because it's likely to be much faster. Fair locking shouldn't be used in performance sensitive code unless its guarantees are really needed. You'll likely want to do your own testing, and not assume your application will behave like my test.
 Expect Less, Get More? 2012-09-02T00:00:00+00:00 http://brooker.co.za/blog/2012/09/02/expect-less
Expect Less, Get More?

On what newly hired engineers think they need to do.

Hiring good software engineers is really difficult. It's hard to find good people, hard to filter good hires from bad hires, and possibly even harder to decide what 'good' really means. When we find a good hire, we want to make sure they can reach their potential as quickly as possible. Most good software managers and leaders realize that even excellent people may take some time to really contribute. They have a lot to learn, and must be given the time to learn, however eager we are to get them contributing to our projects.

I recently came across a pair of papers from Andrew Begel at Microsoft Research, and Beth Simon at UCSD. In Novice Software Developers, All Over Again and Struggles of New College Graduates in their First Software Development Job, they present the results from a study where they followed eight new Microsoft hires for a total of 85 hours.

All of the material in these studies is very interesting, but the section I found most relevant to my interests is the list of Misconceptions Which Hinder. The universal misconceptions they list all seem to match my own experiences early in my career, and seem to align well with what I see colleagues struggling with. Perhaps the most poignant of these is the first one:

1. I must do everything myself so that I look good to my manager. This misconception is particularly dangerous, especially in large, complex development environments. [...] the perceived need to "perform" and not "reveal deficiencies" makes for much wasted time. It also seems to contribute to poor communication and a longer acclimatization. Communication suffered both by waiting too long to seek help and by trying to cover up issues that the [engineer] perhaps felt he "should know."

The fact that this was universally felt is especially interesting given the diverse educational backgrounds of the study subjects:

Subjects W, X, Y and Z had BS degrees, V had an MS, and U, R, and T had PhDs, all in computer science or software engineering. 2 were educated in the US, 2 in China, 1 in Mexico, 1 in Pakistan, 1 in Kuwait, and 1 in Australia. All 3 PhDs were earned in US universities.

Starting in industry after completing my PhD, I felt the same pressure that these candidates report. I felt like I had been hired for ''what I knew'', and by admitting that I didn't know something, I'd make my manager and mentor reconsider the decision to hire me. Until reading Begel and Simon's study, I hadn't really thought that this was a widely spread feeling amongst people early in their careers. Thinking about this now, I realized two things. First, this pressure came to from me, and not from the outside. What feedback I received on my performance was almost uniformly positive. Second, it's clear that I wasn't hired for my intimate knowledge of the proprietary systems I was working on.

While Begel and Simon's study is a small one, it is good evidence that this is a widespread problem amongst newly hired engineers. As mentors and managers, we need to make requirements more clear to new hires. It's not surprising that somebody who has been around for only a few months doesn't have a complete knowledge of our system, and we should clearly communicate that we don't expect them to. As software designers, we can also mitigate this problem by making sure our systems are loosely coupled and interfaces well defined - the amount of knowledge that a newbie needs to make effective changes to our software is a useful metric for good design.

After reading these papers, I found the same research covered in the excellent book Making Software: What Really Works, and Why We Believe It. It's well worth picking up if you have any interest in what we know about the process of making software.
 Latency lags bandwidth 2012-02-11T00:00:00+00:00 http://brooker.co.za/blog/2012/02/11/latency-lags-bandwidth
Latency lags bandwidth

On the growing gap between capacity, bandwidth and latency.

One of the key engineering challenges for most high-performance storage systems is minimizing the number of disk seeks that are required to access stored data. Sometimes of this requires smart techniques like reordering, but the majority of the win comes from caching - storing as much data as you can in memory, or at least away from slow disk platters. Database systems do the same, as do modern operating systems - they constantly cache reads and buffer writes in memory in an attempt to hide disk latency. The classic rule of thumb is that it's worth caching pages in memory which are likely to be accessed again within five minutes. This five minute rule has proven to be amazingly constant over several decades and many orders of magnitude of computer speed, capacity and development.

Another way of stating the same thing is that page sizes have stayed approximately constant, disk access latencies have stayed approximately constant, and the ratio between the cost of a byte of RAM and a byte of disk have stayed approximately constant. We spend an ever increasing amount of our cheap RAM on hiding the crappy latency of our cheap storage.

Caching has been very successful. So successful, in fact, that it has effectively hidden from all but the biggest applications the ever-growing split between capacity, bandwidth and latency in our storage systems.

From Latency Lags Bandwidth, a 2003 paper by David Patterson:

For every decade that Patterson measured for the paper, disks got on average 50 times bigger, 12 times faster at doing bulk transfers, and only 2.4 times faster at seeking. That paper came out in 2003, but there isn't much indication that the picture has changed substantially since then. The other way of looking at that is even more disturbing: the time to read a complete disk with random IO is increasing by a factor of 22 every decade or 36% a year.

The problem with the success of caching at hiding latency is that the cliff is getting steeper: the ratio between the speed of a cache hit and a cache miss is changing. Many applications nominally use disk, but may not be able to afford cache misses at all.

There are two solutions to this: simply give up on disks for online data (RAM is the new disk), or expend bandwidth to reduce apparent latency. Both of these options are already widely seen in production systems. MongoDB, Redis and VoltDB are good examples of the first and BDB-JE is a good example of the second. Neither of these approaches is ideal, however. Storing data in RAM requires very careful attention to durability, while bandwidth intensive methods have to deal with the very real and widening gap between capacity and bandwidth and the tradeoff between write and read speeds.

This sets the stage for the explosive rise of SSDs, hybrid disks and hybrid storage systems, which is very exciting. Unfortunately, they only change the constants and not the fundamental arithmetic. Latency is going to keep lagging, and our data is going to keep getting further away.
 The properties of crash-only software 2012-01-22T00:00:00+00:00 http://brooker.co.za/blog/2012/01/22/crash-only
The properties of crash-only software

My thoughts about a classic paper

Crash-only software by Candea and Fox is a very interesting paper which is well worth your time if you spend any time designing software or services. Re-reading it today, I noticed how useful the section headers of section 3 Properties of Crash-Only Software appear outside the context of the paper.

The properties the authors list are:

All important non-volatile state is managed by dedicated state stores

Components have externally enforced boundaries

All interactions between components have a timeout

All resources are leased, rather than permanently allocated

Requests are entirely self-describing

Regardless of what you think of the value of crash-only software, it is difficult to argue with this list of properties. Even outside of the context of the paper, each of these makes sense to me as a good design practice. The way I understand them is like this:

All important non-volatile state is managed by dedicated state stores. Either you care about your state or you don't. If you do, store it somewhere safe where it won't get lost and can be recovered quickly in event of failure. If you don't, and your data is either purely volatile or a cache, then be explicit in your design that you don't care about it. Don't half-care about data. Store data explicitly and not implicitly.

Components have externally enforced boundaries. Keep logically separate components as separate as possible, ensuring that they don't interact except via a well-defined API. Try to limit implicit side channels.

All interactions between components have a timeout. Not only that, but consider the possibility that what you are trying to do will never succeed. All individual calls should have a timeout, and all attempts to retry should be limited. Waiting forever is not a substitute for knowing how to handle failure.

All resources are leased, rather than permanently allocated. If you own something, don't give it away to somebody else if you still value it. You can lend it to them for as long as they can justify it's use. If you no longer care about something, you can give it away. If something still has value to your business, then keep it.

Requests are entirely self-describing. Don't keep implicit context in protocols and interactions. To me, self-describing doesn't imply 'has no schema' or 'doesn't correspond to a well defined API'. It means that requests should contain all the context that is needed to complete them, and if that is not possible keep the state in a dedicated state store. The API should also be explicit about idempotency and the safety of retries.
 The power of two random choices 2012-01-17T00:00:00+00:00 http://brooker.co.za/blog/2012/01/17/two-random
The power of two random choices

Using less information to make better decisions.

In many large-scale web services, multiple layers of stateless and stateful services are seperated by load balancers. Load balancing can be done with dedicated hardware, with dedicated software load balancers, using DNS trickery or through a load-balancing mechanism in the client. In large systems, the resources and constraints at each layer can vary widely. Some layers are stateless, and easily scale horizontally to many machines. Other layers may be more constrained, either due to the need to access state or contention for some other shared resource.

Centralized load balancing solutions can distribute load over a fleet of machines very well. They track the amount of load they are sending to each machine (usually based on a simple measurement like connection count). Because they are centralized, load balancers typically don't need to worry about load sent from other sources. They have complete control over the distribution of load.

Despite this advantage, dediced load balancers are often undesirable. They add cost, latency, complexity, and may introduce a single point of failure. Handing the task of load balancing to each upstream client is also possible, but introduces the challenge of fairly balancing the load from multiple places. In large systems with large numbers of clients and fairly homogeneous calls, a purely random system like DNS round robin can work very well. In smaller systems, systems where each downstream service can only handle a small number or concurrent requests, and systems where requests are heterogeneous it's often desirable to load balance better than random.

Perfect distributed load balancing could be done, at least in the happy case, by distributing information about system load across all the clients. The overhead of constantly sharing the exact load information between different sources can be high, so it's tempting to have each source work off a cached copy. This data can periodically be refreshed from downstream, or from other clients.

It turns out that's not a great idea.

In The Power of Two Random Choices: A Survey of Techniques and Results, Mitzenmacher et. al. survey some research very relevant to this problem. The entire survey is good reading, but one of the most interesting results is about the effects of delayed data (like the cached load results mentioned above) on load balancing. The results are fairly logical in retrospect, but probably don't match most engineers' first expectations.

Using stale data for load balancing leads to a herd behavior, where requests will herd toward a previously quiet host for much longer than it takes to make that host very busy indeed. The next refresh of the cached load data will put the server high up the load list, and it will become quiet again. Then busy again as the next herd sees that it's quiet. Busy. Quiet. Busy. Quiet. And so on.

One possible solution would be to give up on load balancing entirely, and just pick a host at random. Depending on the load factor, that can be a good approach. With many typical loads, though, picking a random host degrades latency and reduces throughput by wasting resources on servers which end up unlucky and quiet.

The approach taken by the studies surveyed by Mitzenmacher is to try two hosts, and pick the one with the least load. This can be done directly (by querying the hosts) but also works surprisingly well on cached load data.

To illustrate how well this works, I ran a simulation of a very simplistic system. Every second one request arrives at a system with 10 servers. Every 8 seconds the oldest request (if any) is removed from the queue on the servers. Load balancing is done with a cached copy of the server queue lengths, updated every N seconds. I considered four approaches: chose a random server, chose the best server, best of two random choices and best of three random choices.

As you can expect, the pick the best approach worked best when perfect undelayed information was available. In the same case, the random pick approach worked poorly, leading to the worst queue times of any of the approaches. As the age of the data increases, the pick the best approach becomes worse and worse because of herding and soon overtakes the random approach as the worst one.

Best of 3 starts in second place, and puts in a good performance. It gains first place, only to cede it to best of 2 as the delay increases. Clearly, the behavior for best of k will approach the behavior of best as k approaches the number of servers. Best of 2 remains the strong leader all the way to the end of this simulation. Given these parameters it would start losing to the random approach around a refresh interval of 70. It is the clear leader for intervals over the range from 10 to 70, which is an impressive performance for such a simple approach.

Best of 2 is good because it combines the best of both worlds: it uses real information about load to pick a host (unlike random), but rejects herd behavior much more strongly than the other two approaches.

Take a look at The Power of Two Random Choices for a much stronger mathematical argument, and some more surprising places this algorithm works really well.
 The benefits of having data 2012-01-10T00:00:00+00:00 http://brooker.co.za/blog/2012/01/10/drive-failure
The benefits of having data

Two ways to look at drive failures and temperature.

Almost all recent articles and papers I have read on hard drive failure rates refer to either Failure Trends in a Large Disk Drive Population from Google, or Estimating Drive Reliability in Desktop Computers and Consumer Electronics Systems from Seagate. Despite both sounding and looking authoritative, these papers come to some wildly different conclusions, and couldn't be more different in their approach.

How does temperature affect drive failure rate? The Seagate paper says an increase from 25C to 30C increases it by 27%. The Google paper suggests a decrease of around 10%. How can the two most widely used studies differ by so much? It's really because these papers use completely different approaches: the Google study uses simple analysis, while the Seagate paper uses powerful and sophisticated models, accelerated aging, and complex statistical tools. Despite sounding less authoritative, the Google paper is much better.

The Seagate paper doesn't actually present the results of testing drives at different temperatures. Instead, all the drives were tested using a standard accelerated aging approach, in an oven heated to 42C. Another standard accelerated aging technique, the Arrhenius Model, was used to estimate the effect of temperature on failure rates. The Seagate paper goes on to use Weibull modeling, and a fairly sophisticated Bayesian approach to estimating the Weibull parameters. The underlying, and unmentioned, assumption is that the failure rate of drives is proportional to the reaction rate constant, or the speed that an unlimited chemical reaction would proceed at a given temperature. No attempt is made to justify this choice, other than appealing to standard textbooks describing the approach.

The Google paper, on the other hand, doesn't use any statistical concepts that would be unfamiliar to an undergraduate engineering student. Instead, they use the failure data from over a hundred thousand disk drives collected over nearly a year of constant measurement.

The difference between these paper's conclusions on a rather fundamental question - how does temperature affect drive failure? - is a great example of how there is no substitute for data. Statistical tools and small-sample laboratory testing are certainly useful, and should not be ignored, but their conclusions are a poor approximation of the real thing.

The Seagate paper is, sadly, an excellent example of why so many engineers (in our industry, and outside of it) are suspicious of statistical approaches. The paper not only stretches a little data into big conclusions, but does it while sounding authoritative. It uses complex statistical jargon not to explain, but to shield. How dare you question my conclusions? You haven't seen a Weibull model since college, and probably don't even know what Eta looks like!