A few notes from PaPoC 2015

I spent last week in beautiful Bordeaux, France, attending EuroSys 2015 and the affiliated PaPoC workshop. This was my first EuroSys, as well as my first nontrivial trip to France, and I had a tremendously good time. I served on the PaPoC program committee and got to chair a session at the workshop as well.¹

A well-attended PaPoC (photo by Carlos Baquero).

It was a very well-attended workshop – we filled the room and even had to bring in extra chairs! Here are a couple of talks that I particularly liked.

Claret: exploiting commutativity for transaction performance

The first talk of the workshop was “Claret: Using Data Types for Highly Concurrent Distributed Transactions”, presented by Brandon Holt from the University of Washington. (Two of the other authors, Irene Zhang and Dan Ports, were at PaPoC, too, and Brandon also has his own enthusiastic writeup about the workshop.)

Claret is a programming model that tries to exploit commutativity for performance of database operations. The idea is that a data store should also be able to take advantage of what’s known about the commutativity of particular operations on particular types, and leverage that knowledge for transaction performance. For instance, additions to a set (such as the set of all users who have retweeted a particular tweet) commute, so if two such operations (say, two retweets of the same tweet) contend for access to the same record, then there’s no need for one of them to abort. They called this approach “transaction boosting”. Exploiting commutativity is of course an old idea (and CRDTs do the same thing); the interesting thing here is that it’s being applied to transactions.

The other interesting wrinkle is that Claret supports approximate data types that support what they call “bounded inconsistency”. For instance, reads (e.g., showing a tweet’s retweet count) don’t commute with updates (retweeting it), but one user’s retweet shouldn’t fail just because another user is in the middle of requesting the retweet count; rather, we should allow the retweet to go through and allow the first user to see a possibly-stale retweet count, within reason.

One question I was left with was what mechanism the authors are using, or plan to use, for these approximate data types. Is there, or could there be, any relationship to the “Uncertain<T>” work on types for uncertain data by their UW colleague James Bornholt? In fact, it seems like Bornholt and company are already looking into applying Uncertain<T> to Internet of Things programming, also known as…distributed programming. I think there’s an important opportunity for collaboration between people working on approximate computing, low-power and low-energy computing, and eventual consistency, and I expect that in the next several years, we’ll see a lot more work in the intersections of these areas.

Smart replication based on access patterns

A bit later in the workshop, we heard from Annette Bieniusa on her work on “Adaptive Strength Geo-replication Strategy” with Amadeo Ascó.² The idea of adaptive-strength replication is that, in a distributed database, we don’t necessarily want to have to replicate all the data. Rather, each data object’s access pattern over time should determine the number and location of replicas we need. We can associate each replica with a “replication strength” score that is always changing, based on access patterns: local reads and writes to the replica bump up its replication strength, while remote reads and writes decrease it. If nothing happens, the replication strength will also decay over time.

One of the challenges with this approach is just knowing where all the replicas of a given data object are at any given time. Existing approaches to “non-total replication” – that is, storing replicas only on some subset of the nodes where they could be stored – use something like consistent hashing to figure out which nodes to put replicas on, but the number and locations of the replicas are still determined statically. With adaptive-strength replication, the number and locations of the replicas are dynamic, and so we need some kind of directory (which is itself replicated!) that keeps track of how many replicas there are of each object, and where they are.

Annette pointed out that no matter how low an object’s replication strength is, we need to make sure never to remove the last replica of it! (Or, if there’s some guaranteed minimum number of replicas, we need to make sure not to drop below that.) This means that replica removal has to be a strongly consistent operation. Replica addition, on the other hand, doesn’t need to be. (Although, now that I think about it, perhaps the copies of the replica directory don’t actually need to agree on the exact number of replicas; they just need to agree that that number is greater than zero, or greater than the minimum.)

One last cool thing is that their prototype of an adaptive replication system is built using Antidote, the SyncFree project’s shared platform. SyncFree is a joint effort between many institutions and even more people. In my experience, considering how hard it is to just get people at the same university, working in the same lab to collaborate on a codebase, I think it’s impressive how the SyncFree people have managed to work together to build a platform that is general and robust enough to support the many diverse projects that they have in flight. Well done, SyncFree folks!

And much more…

I can’t possibly cover everything that appeared at PaPoC, but the papers (which are really just talk proposals, so they’re quite short) are all available for free download (as is everything that appeared at the main EuroSys conference).

Thanks to the workshop organizers, the rest of the PC, and to everyone who attended PaPoC and made it a success! Let’s do this again sometime.

1. This was my first experience as a session chair, and I’d like to say that it was fun, but it’s really no fun at all to have to cut off people who are having a lively discussion because the next talk is overdue to start. I stand by my observation that Q&A, in the format it’s usually done at these things, is often terrible. ↩

2. With Santiago Castiñeira, Annette also co-authored another interesting PaPoC paper on using CRDTs for intermittently-online applications, which Brandon discusses in his post! ↩