Concurrent Design as a Matter of Cause

I've written earlier about designing for concurrency in the small.
But even the best and most flawless bricks can be put together in far more meaningless ways than meaningful ways.
In the following, I'll consider concurrent design on a larger scale, and introduce a tool which may be useful to ensure soundness in a design.

What is concurrent design about? (Performance aside — we'll focus on soundness for the moment.) What is the basic units for reasoning about concurrent, possibly distributed systems?
Mutexes, messages, transactions — these are among the building blocks. But the connecting mortar is causality chains. When a database client, for instance, submits data to a database server, it can rely on the data to be persisted only if there is a causality chain leading from the moment the client receives the "success"-response, back to when the database sent it, and further back to when the database server's hard drive physically wrote the last block of the transaction.
If there is no causality chain, then no timing assumptions can be made. Which is why, in a given concurrent design, it is prudent to ensure that the necessary causality chains are present.

Example: the "update take-over" pitfall

This is a concurrency design pitfall which I learned about a few years ago. I'd forgotten all about its non-obviousness, until it came up recently in a design discussion. This incident suggested to me that the problem might be sufficiently non-trivial for there to be a lesson to pass on. And I will do that — describe the problem, the naïve-but-wrong solution, and some correct solutions — but do so a bit more elaborately than I originally planned, because the focus will not be on the solutions themselves, but rather on the process: a method to arrive at them.

The scenario: A client (C) must keep track of some object's state. It does so by subscribing to changes (updates). However, there are two update sources, and it is desirable to change over from on (A) to the other (B) from some point on. That is, before the take-over, A provides all updates; after the take-over, B provides all the updates.
A common variation of the pattern is that A is providing snapshots of the object's state through an synchronous request-response protocol, rather than providing updates through a subscribe-publish mechanism.
For simplicity, this variation is the scenario I'll be focusing on in the following; it is depicted as UML to the right.

The naïve solution: Simply set up the subscription to B before getting the snapshot from A.

The threat: An update is missed because it "falls into the crack" caused by the take-over — it is processed by A too late to be part of the snapshot, but is processed by B too soon, before the subscription is set up.
The core of the issue is that when there are two independent message paths, we cannot assume anything about their relative timing; even though they have a common source, events in one path may overtake events in the other path. 

Analysis:
What does it take to get this setup to work as expected?

Any update must reach the client, either through A (the snapshot) or B (the following updates).

Or, from a causality view:

There must be a causality chain ruling out "update is processe by A after the snapshot is made, but is processed by B before the subscription is set up".

A causality chain is a series of causality links, which are defined as follows:

Causality rules

1. There is a causality link from X to Y if X happens before Y and they both happen in the same thread.
2. There is a causality link from a message is sent to its reception.
3. Two message receptions may be causally linked if the transport layer guarantees that one is delivered before the other.
   For instance, TCP guarantees that message within the same connection are delivered in order, i.e. that if X is sent before Y (and in the same direction), then X is delivered/received before Y.
   Similarly, in Erlang, message delivery order is guaranteed for any sender/receiver pair.
   

---

Exercise/Kata: I think this problem makes a rather nice kata in concurrent design.
If you'd like to try it yourself, do so before reading on.
How many different solutions do you see?

---

Enter the loop

Here is the trick: Causality loops are impossible. You can't enter a causality loop; they correspond to paradoxes. (Proof by paradox is an ancient technique. also known as proof by contradiction.)
Thus, one way to attack the problem is to reformulate the requirement as follows:

If update is processed by A after the snapshot is made, and the same update is processed by B before the subscription is set up, then there is a causality loop.
The loop in question is absent, however, if either of the two sub-conditions are absent.

The situation can be represented graphically:

This is quite a bit simpler than the UML diagram above. But actually it captures the essence of the problem.
And it is useful, because it leads to a further refinement of the problem statement: How can we introduce a loop which is absent if we reverse either of the two arrows?
We will, however, also need the context in order to translate our findings back into concrete solutions. The context looks like this:

Getting solutions through loops

That question is not too hard: simply add A2→B1 and B2→A1, to get a four-edge loop which disappears if any edge is reversed or removed.

Translating backwards, what does this mean in terms of the original problem?

Solution 1: The client subscribes synchronously to B before getting the snapshot from A. The event origin publishes updates synchronously to A before it sends them to B.
Now, the first part of that solution is reasonable, but the second part is often not directly achievable — the event origin may just have a generic publish-subscribe scheme, and be oblivious to the difference between the nature of A and B.
But there is another interpretation of the A2→B1 edge.
It can be realized by linking A2 or anything "downstream" (causally later) from A2 to B1 or anything "upstream" (causally earlier) from B1.
By using a direct A2→B1 link, we obtain:

Solution 2: The client subscribes synchronously to B before getting the snapshot from A. When A has processed an update, it sends it on to B (which gets the updates by this route, rather than directly from the event source).

Likewise, the A2→B1 edge can be realized by a direct link.  This results in another two solutions:

Solution 3: The client does not contact A directly in order to get a snapshot.  Instead, the 'subscribe' operation provided by B both subscribes and obtains a snapshot from A.

Solution 4: Like in #2, updates are sent only to A, which sends them on to B; like in #3, the client contacts only B, which both registers a subscription and requests a snapshot for the client from A.

Merging nodes

Revisiting Solution 2, we find that, depending on the situation, this solution may render B somewhat moot. It may make sense to eliminate it altogether, which is yet another interpretation: A2 occurs in the same thread as B1, and B2 occurs in the same thread as A1.
In terms of causality graphs, this is a correct solution because merging A1 with B2 and B1 with A2 results in a two-edge loop:

Solution 5: The snapshot provider also plays the role of update publisher. This combined service provides a "get snapshot and subscribe for updates" operation.

In general, merging existing nodes may provide additional ways to obtain causality loops.

Solutions involving conditional edges

We now have usable solutions, but our options haven't been exhausted yet.
There are other ways of causing loops in the graph — but in order to ensure that the loop is only present when it should be, we will need to introduce conditional edges — which are only actually there in certain circumstances.

For instance, consider the loop caused by adding the edge A2→A1. In order to ensure that this loop is absent if the B1→B2 edge is reversed, we will need to put a condition on the new edge saying "only if the update at A2 has already happened at B before the subscription at B2." This means that information from the subscription operation is required to evaluate the condition, so we'll need a B2→A2 edge as well:

Also, we will need the updates to be identifiable in some way, by timestamp, serial number or similar; let's assume serial numbers.

Just as Solutions 1 and 2 differed in how the A2→B1 edge was implemented — whether it was present as a link directly from A to B or from A to the event source to B ­— so there are at least two solutions corresponding to this graph, because an A2→A1 can be realized both directly and as A2→C1 (because C1 is upstreams of A1).
The A2→C1 edge involves the client:

Solution 6: Subscribing to B is a synchronous operation, which returns the ID of the last known update (which is the last update not published as result of the subscription). The "get snapshot" operation provided by A returns both the snapshot and the ID of the last update included in the snapshot. The client first performs the subscription, then requests snapshots repeatedly, until the snapshot includes the last update not published.

In the direct variant, the A2→A1 edge is kept within A; if sending snapshot is expensive, this is probably better:

Solution 7: Subscribing to B is a synchronous operation, which returns the ID of the last known update. The "get snapshot" operation  takes an update ID and checks it against the last known (by A) update. Sending the snapshot is delayed until the update in question has been processed by A.

---

So much for that causality loop; moving on, we consider the loop caused by adding a B2→B1 edge. It also needs to be conditional, with the same condition; this time, we need to add an A1→B2 edge to have the information required to evaluate the condition:

In domain terms: "If the update is not in the image when subscribing, then reprocess the update."
This seems to imply memory:

Solution 8: The update provider B caches a suitable amount of the most recent updates. The "get snapshot" operation returns both the snapshot and the ID of the last update included therein. The subscription operation takes an update ID, and results in all updates since that one to be sent to the client — whether they have already been processed before the subscription took place (in which case the update is taken from the cache), or arrive at B at a later point. The client first gets a snapshot synchronously, then subscribes with the ID thus obtained.

There are more (of course there are)

The set of solutions found so far is obviously not complete; for instance, none of the solutions we've considered have involved reinventing even a quarter of Common Lisp (or Erlang).
Further meaningful solutions exist; for instance, one that lets the snapshot provider send updates until the real update provider has taken over (which resembles a hybrid between #5 and #7); or one in which the snapshot provider tries to include a given update ID (as in #7) but times out if this takes too long, in which case the client may repeat the snapshot operation (as in #6). Or one in which the "get snapshot" operation is replaced with a "get snapshot if update u is included" (also a hybrid between #6 and #7).

Conclusion

We have looked at a concurrent design problem in the view of causality chains, and attacked it using the concept of causality loops (and with the help of causality graphs). Using a fairly simple technique, we have generated a number of solutions — quite different solutions, as it turns out, but all correct and realistic, and with different trade-offs.
Causality loops as a design tool appears to be a useful way both to find correct solutions and to explore and outline the design space for concurrent design problems.

Acknowledgement

I would like to thank Kresten Krab Thorup, who unknowingly became the cause of this posting, and indirectly of many of the ideas in it.

On concurrency issues

Concurrency issues — race conditions and the like — are the worst category of bugs. These are the bugs that cannot well be proven absent by unit tests; these are the kind of bugs that hide away, biding their time until the most inopportune moment, then rearing their ugly, non-deterministic head on your production system when it is at its busiest. And even then, they can continue to exist unlocated for quite a while, despite many hours being put into tracking them down. Elusive, hardly reproducible, yet ultimately expensive; I've seen it happen more than once.

What follows is some thoughts on the basis of the typical issues.

Your basic multi-threading bug
As any course on multi-threaded programming will tell you, when multiple threads of execution are to run concurrently, care needs to be taken or there will be a risk of data corruption and/or unintended results.

More specifially, the threat (a "race condition" or "data race") is present when:

1. one thread modifies the state of an object
2. at the same time as
3. another thread accesses the object.

That is: it takes a coincidence, a conjunction of three conditions.
Let's analyze it...:

Analysis

Another way of stating the above is obtained by reversing the statement:
We can avoid concurrency issues by always making sure that any object either

1. is never modified; or
2. is never accessed by two threads simultaneously (or stronger: never written to while accessed otherwise); or
3. can only ever be accessed by one thread.

Such objects are known as, respectively,

1. Immutable objects.
2. Objects with state protected by a mutex (synchronization lock; monitor)

and the one used less often:

3. Single-thread objects — or even stronger: objects of linear type.

The first two options are well-known; personally, I'm increasingly coming to consider the strong third option — objects with enforced linear lifecycle — to be rather overlooked, language design space-wise.

"Concurrency-ready" metric
One possible metric for how well a programming language is designed to express complex concurrent systems is, then, how easy it is to enforce that all objects fall into one of the three categories.

Languages and concurrency

Let's apply this view to a few programming languages. The two languages I've used most recently are Java and Erlang:

Erlang

In Erlang, there are the following kinds of objects: terms, message queues, process dictionaries and other process metadata, ETS tables, ports (files and drivers).

• Terms are immutable values. They may contains handles of other kinds of objects, but the handles themselves are also immutable.
• Certain objects — private ETS tables, and to some extent ports — are single-thread objects.
• The rest — message queues, public ETS tables, process metadata etc. — are mutex-protected.

Single-thread objects are enforced not to be used by other threads than the owning one.
In Erlang, low-level data races only occur if there's a bug in the Erlang run-time system, or if you write your own driver and include one.

Java

In Java, you could argue both that there are fewer kinds of object — just one, really, the class-file defined kind — and that there is a much wider range of object kinds.There are certainly thousands of classes, defined by one well-defined scheme, which includes just a few mechanisms relevant to concurrency.
But the problem here is the number of classes — because it is at the class level that it is ensured that the corresponding objects will be thread-safe. A well-designed and -implemented class may be thread-safe, in that it is either immutable or uses appropriate inter-thread synchronization (and encapsulation) to ensure thread-safety. A less well-written class may rely implicitly on details of the context in which it is used, and really be single-thread-use only, or multi-thread usable only in certain unstated conditions.

Java is one of the few languages actually designed for portable multi-threaded programs; in particular, it has explicitly stated semantics wrt. multi-threaded execution. However, as the above comparison is one indication of, it has its shortcomings. For a language to claim good concurrency support, it should provide mechanisms for good, usable guarantees to be derived from local context (e.g. "we know that this-and-this property always holds, because these few lines here ensure that it does").
I've expounded earlier on the importance of supporting local reasoning. As it happens, Java did also then get some criticism (sorry, Java, but you're the modern main-stream language I happen to know the best...).

A Java exercise

Imagine that you have in front of you the source code of a Java class.
A quick inspection reveals that all methods are declared "synchronized".
What kinds of thread-safety issues might the class yet have? Try to list at least three ways in which the class may be non-thread-safe.

I'll present my list at the end of this article.

Does it matter?

But building security against these issues into a language is not exactly trivial, you might argue. Is stricter language rules, additional compiler analysis, and/or costly run-time support just for preventing concurrency issues not just overkill?
Sure, the trend is towards increasing parallellism and so on, but we have done quite fine without such extra measures so far, haven't we?
And bondage-and-discipline languages have been out of fashion for a while. Dynamically typed languages are as popular as ever!

The difference is this:

You can easily live and work with the relative uncertainties of dynamic typing — but then, you can unit test and get some confidence that the types match. If something is broken, or breaks later, then there's a good chance it'll be caught.
For many concurrency issues, unit tests are not likely to catch any errors. Furthermore, the necessary invariants aren't local — they are often widely dispersed in the code. To convince yourself that the code is correct, you more or less need to keep it all in your head at once. That, combined with missing language support for documenting and/or enforcing vital non-local invariants, means that they will perhaps not be communicated to whoever makes the next change in the code, who will therefore not have the full picture necessary to keep things correct.

Rather than being caught at the next full test suite run, or at least quite soon after the rubber hits the road, here's what happens to a race-condition bug:

• The program may appear to work most of the time.
  
• The issue will tend to manifest itself at the most inopportune moment: Not during development or testing (unless explicit and considerable effort is taken to stress-test against such issues), but in production, when your servers are at their busiest, or on the desktop of your busiest client.
• Often, what clues you have amount to little besides "There almost certainly is an issue, it presumably is a software bug, the issue is probably in our code — and it occurs seldomly, so it's likely to be a concurrency issue of some kind."
• Replicating the issue may be difficult; under the exact same circumstances, the program may run just fine.
  Indeed, if the problem does manifest itself during development, it'll appear to have gone at the next run.
  The issue may even be technically impossible to reproduce on some machine architectures, because it requires multiple physical processors of the right kinds to manifest itself (and your servers or other production environment is less likely than the development machines to be thus bug-resistant).
• Eliminating a tricky concurrency bug can be a drawn-out experience in all phases — detecting it, reproducing it, tracking down its root cause, verifying that it has gone — all steps tend to be markedly more difficult than for deterministic bugs.
• With any kind of bug, tracking it down once is one thing; there may be even be a feeling of gratification once you've done it. Tracking the same bug down twice is another matter — it is deeply frustrating to realize that there's a reason for your feeling of déja-vu. This is one of the reasons for regression testing: bug hunting may be stimulating in its own way, but it'd better lead to a different bug each time.
  This goes doubly (well, even more than that) for the elusive non-deterministic bugs.
  Sadly, because of their nature it is at best difficult, and often near impossible, to write regression tests for these kinds of issues.
  

Conclusion

Languages differ in concurrency support. Nothing new about that, of course, but I think it likely that many developers using one of the  mainstream languages which have a relatively good level of support in that area may not know that there are alternatives which are significantly more concurrency-ready.
In the beginning of this text, the prerequisites for a race condition were broken down and three kinds of conditions for avoiding race condition were derived; based on this I suggested a qualitative metric for a language's level of support for concurrent programming. I hope to have demonstrated that it may be a useful way of looking at both languages and concrete programs or program designs.

In the absence of a programming language providing strong, local guarantees with respect to thread-safety, as a developer you need to be alert whenever there's a chance that two threads may be executing your code concurrently. The best way of doing this is probably through discipline — for instance, by clearly constructing each class so that it falls into one of the above categories: Immutable, thread-safe through synchronization, or single-thread use only — and then using them strictly according to this. That is one way of trying to restore local reasoning.

Do you write programs involving multiple threads? If so, are you familiar with which consistency guarantees your platform actually provides (e.g, the Java Memory Model)?
Do you regularly stress-test your program on a system with multiple physical processors? I hope you do.
Dealing with concurrent programs in general requires good global, combinatorial-temporal reasoning abilities. Probably not your best-developed cognitive mode... :-)
The solution? Keep things as simple as possible. Find rules that work, and follow them. Encapsulate the issues, so that you can deal with just one question at a time. If possible, let the rules be checked mechanically.

---

Answer to Java exercise
Some ways in which a Java class may be unsafe even though all methods are declared "synchronized":

1. A field is public, and either
1. Non-final (and non-volatile) or
2. Referring to a non-thread-safe object.
   
2. The superclass is non-thread-safe, and the current class does not or can not override the causes.
3. An instance method modifies the value of a a static variable without proper synchronization.
4. An instance method reads the value of a a static variable which is also modified by a static method, without proper synchronization.
   
5. A method exposes a reference to a non-thread-safe object referred to directly or indirectly by the current object.
   
   1. By returning such a reference.
   2. By passing such a reference to some method which stores the reference somewhere accessible to another thread.
      
   3. By starting a new thread and giving it such a reference.
      
   (I.e., a non-thread-safe object becomes shared.)
   
6. A field (which may be private) refers to a non-thread-safe object which may be shared because
1. It originated as (or was extracted from) a parameter to a constructor
2. It originated as (or was extracted from) a parameter to a method
3. It was returned from a call
   
(I.e., a non-thread-safe object is already unexpectedly shared.)
7. An inner class accesses an instance variable of the surrounding class, but fails to synchronize on the right this.
8. An instance method locks on another object which may be of the same class (this may result in a deadlock)
   
   1. Implicitly, by calling a (synchronized) method on the other object
   2. Explicitly, using "synchronized"
   (A plausible example of this is a synchronized equals() method.)
   
9. A constructor leaks this to some place where it can be accessed by another thread, and the object has at least one (final) variable which is accessed without synchronization.
   (This is because the special rule for final fields, which allows them to be accessed without synchronization, only applies after the constructor has completed.)
10. A method exposes a reference to a thread-safe object referred to directly or indirectly by the current object, and that thread-safe object allows mutation (of itself or of a contained object) in a way that the current class is not prepared for.

This list is quite likely not complete; it is not the result of a systematic analysis of the matter.

Testing distributed-store algorithms

This is a follow-up to my post on a datastructure for storing collections in Riak.
While I have been planning this follow-up, Kresten Krab Thorup has actually gone ahead and implemented the algorithm (on GitHub; see src/riak_column.erl) — which suites me nicely, as I haven't written a single line of implementation and am not really past the thinking stage yet :-)
To wit:

Shortly after writing the post, I discovered a couple of issues or finer points, both of which have to do with the fact that different rows in Riak live independent lives —  they are independently versioned, and no cross-row guarantees are given — specifically, nothing can be concluded from the read order: if one client A updates row X, then row Y, then another client B may see the Y update and later see the old version of row X.

(If Riak is set up with appropriate consistency settings, such that the majority of the replicas of an object are written synchronously, then you do have indirectly some sort of guarantee. Below a certain threshold of machine and/or network problems, that is.
But even so, nothing can be concluded from the read order if there several clusters set up with cluster-to-cluster replication: changes on different keys in one cluster arrive at the other clusters in arbitrary order.)

This leads to at least the following issues:

1. Firstly, when splitting a row into two, I included this step: "Write an empty row back under the original auxiliary row key".
   In fact, doing that would be wrong. Even writing some tombstone dummy value in the old row would be a bad idea; instead, one should simply mark the row as obsolete while keeping the old data. This is necessary because a client accessing the collection later on may see from the master row that the old row has been split, but not see the new rows. Or it may see the old row, but not the change in the main row. In the former case, it is necessary that at least the values in the old row be available (or the collection would suddenly have shrunk); in the latter case, it would not be apparent that the values in the old row are obsolete.
   
   
2. Secondly, after modifying an auxiliary row, the main row should be updated — even nothing in it has changed. This may sound silly, but is the easiest way to ensure that, in the event of a concurrent row split, the auxiliary row in question is taken into account at a subsequent merge (indeed, that the merge is triggered at all).
   
   
3. And even that is not enough if there are more than one cluster: At the time of the read repair of the main row, the update for the auxiliary row may not have arrived - and it may therefore be lost silently. It appears that some kind of versioning of the auxiliary rows is necessary; with such versioning, we can tell when repairing the main row that we're missing an update on the pre-split auxiliary row, and that the reference to it should therefore be kept in the main row, so that it can be repaired later when all information is available.

Ah, the perils and challenges of incomplete information.

Managing concurrent subtlety
As the saying goes,

Meddle not in the affairs of concurrent systems for their ways are subtle, and are quick to anger.
-- Tolkie(error: timeout)n

In a domain as subtle as this — with gotchas in the style of the above mentioned issues, how can we ever convince ourselves that a scheme like the one for Riak collections are implemented robustly and correctly?

As always, there are two ways: Formal verification — proving that the program is correct; and thorough testing — gaining confidence by exercising the program.
Both have their advantages and disadvantages.

If I were Dijkstra, I'd develop a formal proof (as he did in quite a few of his blog postings), and probably modify the algorithm appropriately along the way. I, however, am no Dijkstra, do not believe to have the time to develop a formal proof — nor do I have any delusion of being able to write anything worth reading in the process. Luckily, going the other way, through testing, have something going for it as well:

• It is not always clear which guarantees the components we build on actually provide. That mean that, regarding formal proof, the set of axioms may be uncertain.
• The same test can be applied to different implementations of a component.
• The same test can be applied to different versions of a component — i.e. if we modify the code, we can cheaply gain some confidence in the modified version.

For both formal verification and testing goes that the answers you get depend on the questions you ask.
When proving a property, you prove only that property; when you test a concrete call sequence with concrete values, you test with only those values.
Which is of course a good reason to get familiar with property-based testing — which lies somewhere in between the two in that it tests a property on a number of concrete call sequences — typically a few hundred, and typically different instances for each time a test is run.

This can be a nice compromise between formal verification and hand-rolled test cases — provided of course that the properties and the instance generators are chosen well.
As always with testing, paranoia and imagination is key. But you get more value for your paranoia when it's used to power random test case generation.

For the problem in question, and assuming an Erlang implementation like KKT's, property testing can be done with relative ease using a tool like Quviq QuickCheck or Proper. Their support for testing state machines comes in handy; I've not tried using it before, but this seems a good occasion.

How to test randomly
Randomized testing involves abstracting over usage scenarios.
How the abstraction is done determines what will be tested.
Knowledge of the problem domain is the primary guide; paranoia together with perhaps knowledge of implementation details should provide additional input.
What must be considered is:

• What is tested:
  Which API functions to exercise?
  Which invariants to verify?
• How it is tested:
  Test concurrent use to check for thread safety?
  Test with invalid inputs?
  Should certain special circumstances be simulated - e.g., file I/O errors, disk-full conditions, network delays, packet loss?
• With what it is tested:
  Test with abnormal (very long/short/high/low) inputs?
  Key collisions?
  Many values for the same key?
  Keys which are nearly identical?

This is of course where the imagination and paranoia enter the picture.
You can't assume that "since we generate the values randomly over a large domain, we exercise all code paths" — exercising e.g. a dictionary with a million randomly generated keys is of little use if the keys never collide.

How to test distributed collections
OK then, how to test an implementation of the distributed collections scheme?
Using the state machine testing support of Proper, we can maintain a "model" collection aside the subject-under-scrutiny collection (shortened to SUS in the following).

What to test:
This is the easiest part: We will test the usual collection functions: insert, delete, lookup, list keys.
The invariant is that the result is consistent with the same operation performed on the model collection — as defined below.

How to test:
We'll certainly need to test concurrent use. Let's say that there are three simultaneous users of the collection; we know that there are subtleties involving two, and there may be additional ones involving at least three.
The users won't be really simultaneous, though — We will test concurrent use in a way where the concurrency is made explicit. This provides repeatability and insight into why things fail, which is indispensable for this problem domain.
So, instead of having an actual underlying Riak store, we'll mock it up, in such a way that the mock provides just the guarantees we actually expect the real thing to provide.


Model representation
The structure I have in mind is: the mock remembers all versions of all values put into it. This is what the entire simulated multi-cluster store — let's call it the "cloud" — has ever seen.
The mock furthermore has a number of "views" of the store, corresponding to what you would see if you accessed the cloud at different points. It has a number of these; we'll make the assumption that in any of these views, for any given key, the version will only increase with time. I.e. we do not expect the version of any value in any view to evolve backwards. The mock keeps track of the view-to-version mapping for all keys.

One thing that can happen, then, beside operations on collections, is that value versions find their way from one view to another. Also, version merging can happen in transit — the versions being merged are not necessarily the latest value in any view, but may be any versions that have ever existed in the cloud.
For simplicity, let's say that this is modelled with views also — if we allow enough views, this won't reduce the generality.

The model thus consists, not just of a simple collection, but of an abstract model of the storage cloud.
Beside the externally visible events — the calls to the collection API — there are internal events: a given version of a given key finds its way to one view to another. Both kind of events go into the randomly generated test scenario specification.

The test
It was originally my intention to end with putting all of this together in a Proper-based Erlang unit test — it would then be a good occasion for me to get experience with the state-machine modelling support (link: state machine part is  from p.26).
However, it appears that I have a latency-vs.-completeness tradeoff to make, so I'd better stop here, publish what I have, and hope to return to the subject soon, hopefully with some concrete code. (While this posting has been under way, naturally other topics have come up which I'd like to write about; the order in which further postings arrive here is undetermined...)

Multi-version collections in Riak

The setting:
We have a distributed, transaction-less key-value store with multi-version awareness (vector clocks as version numbers, basically). More specifically, we have Riak.

This provides us with the ability to store and retrieve blobs by key — and to do decent conflict resolution, up to a point.

That is a great building block, but there are some shortcomings which means that we need to build on.

First, the stored values have (as far as Riak is concerned) no structure.
This means that if we store rows as values, and need to update only a part of a row, we still need to fetch and store the entire row.
There are both potential bandwidth and versioning issues with this: you may have to move more data than strictly needed, and the elements of the row are (at the outset) not individually versioned, which makes conflict resolution difficult.
For the latter problem, a solution has already been devised in the form of Vector Maps.

Second, there is no concept of "collections".
This leaves you with two possibilities when you need to store a collection in Riak: storing the entire collection under one Riak key, or storing it under several Riak keys.
(I'll henceforth use the term "row" for a value stored under one Riak key, both to avoid confusion with the keys of the individual element and because that's the term that has become stuck in my head.)

Storing all of a collection in one row has the above-mentioned drawbacks: it's a waste of resources (bandwidth, CPU, disk I/O) much of the time, and you lose much of the advantages of automatic version conflict resolution because only the version of the entire value is taken into consideration.

Storing the collection in different rows also has its drawbacks, though — most significantly, you lose data locality. To fetch a collection of 100 elements, spread over 100 different keys, 100 separate disk locations may have to be accessed. (Unless perhaps you're so clever that you can trick the hashing function, that is...)

A side note:
Riak has a "link" concept which enable you to link objects associated with different keys together; sadly, it has both the locality issue (which can't be helped) and the versioning issue (which is a pity, this being Riak).
For instance, consider an object which in version [] has one link, "foo"; in version [{a,1}] the foo link is deleted; and in version [{b,1}] another link, "bar", is added. Based on versions [{a,1}] and [{b,1}], with link sets Ø and {foo,bar}, respectively, you can't conclude anything about which links should be present in a merge. (Even if the version [] was accessible to Riak, it would be disregarded entirely.)
So, if you want to take advantage of Riak's multiversioning support, you'd better stay clear of links. Or else use them in a disciplined manner — i.e., only adding, never changing or deleting them.

The concerns
Summing up so far, we have these concerns when storing collections:

1. The ability to store an arbitrary amount of elements (obviously).
2. Data locality. — This concern alone would have all elements in one row.
3. Manageable row size. — This concern alone would have one element in each row.
4. Efficient element lookup.
   (In the following, the elements are assumed to be associated with some kind of key.)
5. Easy conflict resolution.
   (E.g., when creating a new row, expect that another Riak node might also decide to create a row at the same time, based on the same decisions; this may influence the way you choose keys. Also, don't move data from one row to another too much.)

(A non-concern, luckily, is hard limits e.g. on row size. The present problem has many features in common with the issue of how to structure database storage, but while DBs have to respect the size of a disk block, we have more freedom. A good thing, too — dealing with concurrency is quite enough.)

The conflict between concerns (2) and (3) is obvious.
One straightforward compromise between the two is "add elements to a row until it reaches a certain size (say, N elements), then create a new row for the next N elements, and so on", but this conflicts with concern (4).

Hash tables
So, we need a growable, block-based collection, in which elements can be looked up efficiently; what are our options?
A hash table as it is usually implemented — using hash value modulo bucket count to get the bucket number — is not so good a choice in light of (5); global redistribution of the data is a thing to be avoided.

Taking inspiration from database systems, however, we might consider the hash table variants used there, secondary-storage hash tables (link?).
These work by using a bitwise prefix of the hash value as the bucket indicator.

The scheme I have in mind differs from both of the variants described in my book on database systems, but the basic idea is the same — after all, the main concern of touching as few block as possible at each access is the same.
I'll sketch my scheme below.

Collection representation using secondary-storage hash table
First, a bit of basics and assumptions:
I'll assume that we have a Riak bucket to our disposal for collection storage; that each collection is associated with an alphanumeric key in that collection.

Each element is versioned individually, for reasons mentioned earlier:

VersionedElement :: {ElementKey, [{VClock, Data}]}

(I'll be using Erlang type specifications.)

After a version merge, multiple versions of the element may be present, with pairwise independent versions (i.e. none of them "happens before" any of the other); this is why there is a list of versioned values rather than a single value.

As mentioned, we use a prefix of the hash values for indexing the auxiliary rows.
The two approaches for extensible secondary-storage hash tables which are described in my database book ("Database Systems: The Complete Book", by Garcia-Molina, Ullman and Widom; interesting reading) are:

• "Extensible hash table" — in which a hash table's current structure is described by the number i of bits of suffix used for selecting the hash bucket. Drawback: the table extension from i to 2i has to be done all at once.
  
• "Linear hash table" — which employs an incremental growing approach, and in which the structure is described by (i,k) where i is as above and k is the current number of buckets, 2^i-1 < k <= 2ⁱ . If a suffix is below k, it's used as the bucket number; if it is k or larger, then the suffix of length i-1 is used (i.e., clear the MSB of the original suffix). When k is increased, the elements in preexisting bucket j are redistributed between j and k — where j is k with the MSB cleared.
  Quite elegant, really.

In our case, the concerns and constraints are similar but different; for one thing, we can get away with using less compact and simple data structures. More specifically, instead of a couple of numbers we're going to have a list of buckets:

RowPointer :: {BitCount :: integer(), BitSuffix :: integer()}

This allows us to split exactly the hash buckets that need splitting, rather than having to rely on a predetermined splitting order.
(This structuring turns out to be similar to the one wikipedia calls extendible hashing, except for the representation of the bit suffix table)
Consider a collection stored under Key. The collection's main row looks like this:

Key → MainRow

where

MainRow :: {[VersionedElement], [RowPointer]}

and VersionedElement and RowPointer are described above.

For locality, we allow a limited number of elements to be stored directly in the main row. This is an optimization, of course, which ensures that for small collections, one row access is needed rather than two; it can be easily omitted but I see no harm in it.

The RowPointer set must be internally consistent: For each possible bit pattern, there should be at most one RowPointer matching that pattern.

For auxiliary rows, we use the key format

AuxKey = Key#BitCount,BitSuffix

(where '#' is a character guaranteed never to be present in Key. Alternatively, use Key# as key for the main row.)
The auxiliary rows contain just elements:

AuxKey → [VersionedElement]

Consistency and conflict resolution
Let us define criteria for a reliable collection storing scheme, to guide the further design:

• Firstly, we can determine the key set for a given collection (subject to which revision versions are visible to us).
•  Secondly, given a collection and a key, we can determine the last version(s) of the associated value.

Part of the first criterion is that deleted elements stay deleted even when other versions of the collection is "versionally visible" where an older version of the element is present.
Part of the second criterion is, strictly speaking, that if a version is visible in which an elements was deleted, then that element is either not present at all in the key set, or the concluded "last version(s)" include a 'deleted' value — i.e., it will not be forgotten that it was once deleted.

Version-Merging Algorithm
When merging two versions of the collection, we have for each row a number of versions of that row available. In Riak we can't tell across rows which versions belong together.

An outline of a merge algorithm is as follows:

• First, determine the set of keys.
• Next, for each key,
• Determine the most recent version(s).

Determining the most recent versions of each element is a known and solved problem; the interesting part is therefore finding all of the relevant versions.

First attempt:

• Take the union of the RowPointers set from all versions of the main row.
• For each of these rows, take all element versions.

This doesn't take deletions into account, however.
To handle deletions, I see two options:

1: The tombstone approach. We represent deleted elements by explicit tombstone values (just as it is done in vector maps and, I believe, in Riak itself).

It would be nicer to have deleted elements be removed from the system altogether. Is this possible, within the constraints we've set up?

Consider a merge operation of two independent versions "D" and "P" of a row; a given element "X" is present in "P", but absent in "D". Assume further that the element modification version is later than the last common version ("LVC"). How do we know whether the "X" was present in "LVC", then deleted in "D" and modified in "P" (in which case we must include both options, present and deleted, in the merge result: [X_P, tombstone]), or if it was created since the LCV (in which case it must be present, not deleted, in the merge result: [X_P])?

           LCV
          / \
delete(X)/   \update(X)
        /     \
       D       P
 (X absent)  (X → X_P)

This question leads to:

2: The extra versioning approach. For each element, include both the version of the last modification and the version of its creation. Furthermore, include for each row the version of the last modification to the row (these versions must be comparable to the versions of the individual elements, by the way).

With this extra information, we can distinguish: If the row timestamp of "D" is later than the creation date, then it was deleted (result=[X_P, tombstone]); if not, then X was created since (result=[X_P]).

Interestingly, the two approaches (1) and (2) are not equivalent, but yield different results in certain cases.
Consider for instance the following history:

                V0
               /:
              / :
create(Y) - A1  V1 - create(X)
               /|
              / |
delete(X) - A2  V2 - delete(X)
               /:
              / :
create(Y) - A3  V3 - create(X)
               /|
              / |
delete(X) - A4  V4 - update(X)

and assume that the input versions available to the merge operation is V4 and one of {A2, A3}.
Then using the tombstone approach, A2 and A3 contains a tombstone value for X, and we must include it in the merge result.
Using the extra versioning approach, on the other hand, we can conclude that the X present in V4 is created at a point not "versionally visible" to either A2 or A3, and thus exists without question after the merger.

(If merging (V4 and A1) or (V4 and A4), the two approaches yield the same result.)

Anyway, I hope to have convinced you that we can resolve conflicts reliably.
Having gotten that out of the way, let's turn to how the data structure is actually manipulated.

Collection Manipulation Algorithms
In the insertion and deletion algorithm, the possibility of write conflicts has been ignored. This is intentional; Riak lets you detect the write conflict, and it can then be repaired — instantly or later, as read repair — using the principles described above.
Note that the organization of the data means that repairs caused by write conflicts are local, i.e. only a few rows need to be repaired, not the entire collection.

Lookup algorithm:
Given a collection key, and an element key, look up the key in the collection. Answer with the versioned element or "not found".
 - Fetch the main row of the collection: {Elements, RowPointers}.
- Is the element among Elements?
  - If yes: There's your answer.
  - If no: Is there a RowPointer matching the key?
    - If no: Conclude "not found".
    - If yes: Fetch the auxiliary row pointed to by RowPointer: Elements2.
      - Is the element in Elements2?
        - If yes: There's your answer.
    - If no: Conclude "not found".

Update algorithm:
Like the lookup algorithm, with the obvious additions. Left as an exercise to the reader.

Insertion algorithm:
Given a collection key, an element key and a value, insert the (key,value) pair in the collection.

 - Perform a Update of the key. If the key was found, we are done; if not, continue.
- Fetch the main row of the collection: {Elements, RowPointers}.
- Is there room for another element in Element, without exceeding the size threshold?
  - If yes: insert the versioned element in the main row.
  - If no: Is there a RowPointer matching the key?
    - If yes: fetch the row pointed to by RowPointer, and add the versioned element.
      - Is the size limit exceeded?
        - If no: Write the auxiliary row back.
    - If yes: Split the auxiliary row into two rows with a BitCount increased by one.
          - Write these rows.
      - Update the main row with the new row pointers.
      - Write an empty row back under the original auxiliary row key. (Optional?)
    - If no:
      - Create a RowPointer matching the key and having as small a BitCount as possible.
      - Insert an auxiliary row for that RowPointer, containing just the new element.
      - Update the main row, adding the RowPointer.

Deletion algorithm:
Given a collection key, and an element key, delete the element with that key from the collection (if it is present).
Done like Update with a 'tombstone' value — if the element is present; if it isn't, nothing should be done.

Conclusion
Riak is a good building block for a distributed storage system, but for certain applications you need some appropriate abstractions on top of the raw key-value store. There are for instance good reasons to put some thought into the organization of collections of values, and ensure that conflicting versions can be dealt with appropriately.
I have presented some of the issues involved and attempted to put together a  usable scheme.
At this point, it's all talk and no code, though — not a bad starting point, but I cannot claim much about the resulting scheme except that, given that this text ended up much longer and with many more asides that I originally envisioned, I must have put some thought into it.

(Update: There is now a follow-up. Still more thinking than code, though -- for my part, at least.)

Oh, and by the way, I hope to be able to find the time to explain why I'm writing about Riak, all of a sudden.

Program Composition and Transformation in Unix

A few years ago, I got the feeling that language design could benefit from looking towards Unix and the lessons of the Unix culture.
A definite source of inspiration for this was Eric S. Raymond's The Art of Unix Programming, which among other things analyze what the greatest strengths and most significant design decisions (or rather, design style elements) of Unix are.

One of the qualities I'd most like to carry over from Unix to programming languages has to do with modularity - the ease with which one can combine small components into great things; components which in themselves are simple and easily understood.

Programming Languages and Local Reasoning

Through time, there have been two interesting trends in programming languages: towards better guarantees and later binding.

With "guarantees", I mean facts and invariants which the language rules permit us to conclude from the code. Such as the following - you may or may not recognize them (and the language features which give rise to them):

• "The value in this variable is of this type."
• "The value in this variable can only come from one of these expressions."
• "The value of this object field can not be changed once the object has been constructed."
• "This variable can only be accessed from one thread."
• "This method can not be redefined in subclasses."
• "This process will always be notified when this other process disappears."
• "If this code point is reached, then this other code point will eventually be reached."

The two trends, better guarantees and later binding, correspond to two desirable properties of software: the ability to reason about the behaviour of software, and flexibility.

Introduction

About me:

I have a background in theoretical computer science (Master's degree from University of Aarhus). I currently work as a software developer (developing in Erlang, Scala, and the odd Bash, Perl and C++).

I've been involved - briefly - in many software projects; as bug reporter, coder, translator, or level designer. You could call me a hit-and-run contributor.
The reason: I tend to have too many ideas of my own to explore to hang around any particular project for long. Perhaps not ideal, but that's how it's turned out.

My main interests are programming languages and their implementations. That means primarily compilers, but also interpreters and runtime systems.