Peter Bailis :: Highly Available, Seldom Consistent

There’s an interesting related challenge (design theme/meme?) regarding how to design systems that behave sanely in the worst case but take advantage of the gap between average-case and worst-case conditions (when it exists). I used to hang out with computer architects, and there’s some cool work on this topic in their community (e.g., “Better than Worst-Case design”). One of my favorite papers is called DIVA and employs a dirt-simple, in-order co-processor to verify the computations of a less reliable primary processor, which employs all sorts of microarchitectural bells and whistles to speed up the primary computation. DIVA only “pays” for errors (worst-case, due to, say, noise, process variation, bugs in the processor design) when they occur (and are subsequently caught by the checker, which is much easier to verify and build correctly). (Fun fact, from Footnote 1: “This [single-author paper] was performed while the author was (un)employed as an independent consultant in late May and June of 1999.”) Some of my favorite algorithms (selfishly, e.g., RAMP) have this flavor, where we’re only penalized when a bad thing occurs (in the case of RAMP-Fast, readers only pay—using a second RTT with servers to repair missing values—when there is actually a race). ↩

Lest I come off as grumpy: I am actually very excited about this possibility, but it’s a challenging chicken-and-egg problem. Which comes first: better hardware, or applications that could make use of the hardware if the hardware existed? I think we can go either way, but I’ll note that (in the latter scenario), there are troves of brilliant ideas in the distributed computing and database literature that are lying in wait for better hardware. As one of my favorite examples, Barbara Liskov’s PODC 1991 keynote on “Practical Uses of Synchronized Clocks in Distributed Systems” has a bunch of great ideas (and associated papers). Now that Barbara’s former student has managed to convince Google to add atomic clocks to their datacenters, these algorithms can be efficiently implemented at scale. I think academics have a serious role to play in this conversation, and this type of co-design is on my research agenda. But there’s probably lower-hanging fruit for practitioners today. ↩

Three scenarios where this kind of analysis has useful implications:

a.) Whenever someone claims their coordinated (e.g., serializable) system achieves unilateral performance or availability with a coordination-free design, we know they’re either misguided, are not exercising an interesting workload, and/or are simply being misleading. In these cases, we know that, regardless of how the system is implemented, because they’re choosing to implement a fundamentally “hard” problem (e.g., serializability, atomic commitment, or maybe just a consensus register) that requires coordination to prevent some “bad” execution, there’s going to be a cost associated. This is effectively the converse of our thesis: if you have to pay in the worst case, you (may) have to pay in the average case. Moreover (and perhaps most importantly), we don’t have to point fingers and argue about someone’s code or implementation—in many cases, there is literally no way to implement a better system, and we can prove that there’s no use in trying to do so. (Of course, there’s plenty of fun [and money] in building fast databases, but the point is that we can separate out what’s fundamentally new—which also happens to be a key criterion for good research—and what’s simply built better.)

b.) “Scale out” versus “scale up” systems design is a hot topic—should we build (often more sophisticated) single-node systems or build simpler systems that are geared toward horizontal scalability? These two are often opposed, and proponents of each strategy will argue that the other is misguided for some particular workload or system implementation. Yet, couched in the terms of worst-case systems design, advances in single-node performance simply serve to increase the capacity of each node within a cluster. Making each node in a coordination-free system two times faster via “scale up” techniques makes the whole cluster two times faster. If the conversation is typically “scale out” versus “scale up,” if we’re coordination-free, we get to choose “scale out” while “scaling up.” This may seem obvious, but consider the fact that speeding up single-node performance does not always, for example, improve the throughput of distributed transaction processing if (ha!) you are bottlenecked on the network.

c.) As hardware changes, the constants associated with communication costs may change—thus affecting the relative benefit of our worst-case designs—but the fundamental gains likely won’t. For example, for decades we’ve been running shared-everything architectures on single-node servers. However, there’s mounting evidence that a shared-nothing approach is desirable in a multi- and (especially) many-core setting. Andy Pavlo and friends recently did a study of OLTP scalability to 1000 cores (in simulation, with some folks at MIT). They found that—regardless of implementation—serializability tanks in performance (due to a variety of factors, depending on the algorithm, but—I’d argue—ultimately due to the fundamental costs of providing serializability). In the distributed setting, today’s datacenter networks make serializable transaction performance an easy target to beat—yet, even as network performance improves and performance bottlenecks lessen in severity, we’ll still see benefits. (An argument I like to make is that, despite DRAM accesses being ridiculously fast—at least relative to remote memory accesses or RPCs—we still spend a lot of time devising cache-friendly algorithms—albeit not for every application, but for many that matter.) ↩