A Wrinkle in (Deconstructed) Time

Or, “Hey, you blogged again! It’s about time!”

In “Are We There Yet? A Deconstruction of Object Oriented Time,”[slides] [interview] Clojure creator Rich Hickey looks beyond concurrency support in popular programming languages to see what’s on the horizon. He asserts that wrapping our objects in locks – the popular solution – is an attempt to treat concurrent objects as if they were accessed by a single thread. Hickey describes the problems with this approach in two slides:

We don’t make decisions about things in the world by taking turns rubbing our brains on them.

Nor do we get to stop the world when we want to look around.

Instead of this awkward locking model, he suggests a versioned approach to representing object instances. He also presents some programming constructs to be used in his versioned model.

Below, I present his idea of a pure function to update the view of objects to a new state. I also introduce a problem that this doesn’t handle, the expiration problem, that language designers should either address or state they don’t handle.

Background

In Java and C++ (and many other languages), it’s very easy to write concurrent code that causes inconsistent results across multiple reads. So easy, in fact, that it’s the default for everything! You’d have to do external locking or go to heroic lengths to avoid doing it. It happens regardless of the thread safety of the underlying class!

Let’s look at an example: Assume that some Evil Crime Syndicate is trying to kill me. Even worse, they have cracked all government mainframes and always possess my contact information. Like all Evil Crime Syndicates, they have a gigantic code base written in Java that runs the whole operation. To save themselves some personnel costs, they wrote an automated assassin dispatching system.

Let’s look at a scenario where the assassin acts on an inconsistent kill order:

Assassin code

  class Assassin
  {
    void killPerson(Person person)
    {
      String personAddress = person.getAddress();
 
      // --- INTERMEDIATE ACTION BY ANOTHER THREAD ---
      // I enter the Witness Protection Program, and my
      // name and address are changed.
 
      String personName = person.getName();
 
      // Some private method
      actOnKillOrder(personName, personAddress);
    }
  }

Application code

Person nextTarget = TargetFactory.makeTarget("Jake");
 
// Not shown: logging, passing the target info to a central
// database, etc
 
currentAssassin.killPerson(nextTarget);

If I officially enter the Witness Protection Program while killPerson() performs sequential reads, the assassin will look for a new name at an old address. In the best case, he’ll get some puzzled looks when he asks around for a new identity at the old location.

We’ll call the worst case deadlock

A second chance for the Evil Crime Syndicate

Could language features help the Evil Crime Syndicate kill me? Hickey proposes that instead of looking at objects as a single mutable data point, we treat objects as a succession of states. Each view perceives an immutable state at some point in time, and references it until it is updated. If the view needs to know the current state of the object, then it can call a function that returns the object’s newest state. If the object is constantly being updated by other views, you won’t see any of these changes until you call this function and get the new version of the object.

This is a version control system for objects. You query the object once and do stuff with the data that you get back. When you want to pull the current updates for the new object, just call the system’s update command and get a new version! The system handles all of the reads and writes behind the scene, just like a real database. Interesting aside, databases and version control systems concurrent systems that Joe Coder already uses on a massive scale with minimal concurrency problems.

To imagine this feature in Java, let’s call our pure function Update(). It takes the current view of a Java object and returns the newest value of the object. Yes, I know that adding a function to Java completely breaks the consistency of Java’s all-object model, but you’ll notice that I have no control over the language features added to Java. This continues to be a good decision made by Sun Microsystems.

It turns out that Update() makes it easy to show that the assassin always acts on consistent data!

Assassin code

  class Assassin
  {
    void killPerson(Person person)
    {
      String personAddress = person.GetAddress();
 
      // If my data is updated here, this view's
      // view of 'person' doesn't change. All reads
      // are consistent!
 
      String personName = person.GetName();
      actOnKillOrder(personName, personAddress);
    }
  }

Application code

Person nextTarget = TargetFactory.makeTarget("That Jake guy");
 
// Not shown: passing the target to a central database, etc
 
person = Update(person);
currentAssassin.killPerson(nextTarget);

In this code snippet, the fact that Update() is called before dispatching the assassin ensures that the assassin is acting on a consistent and relatively recent view of me. I mean, I could enter Witness Protection as the assassin travels, or immediately after Update() is called. However, that’s a logistics problem for the assassin, and he won’t get any sympathy from me!

The Expiration Problem

Now the wrinkle! What if we query real-world objects for their state? Let’s say that you have an atomic clock hooked up to your computer via a serial port.

     AtomicTime time = atomicClock.queryTime();

Let’s assume that the delta between the AtomicClock time and the system time is known and constant, which is not usually a reasonable assumption. For the sake of discussion, let’s also assume that Update() can update an AtomicTime to the most recent value pulled from the AtomicClock. How does Update() interact with this real-time object?

Most of the time, it works very well. We can use Update() to ensure that our view of the time is consistent if we read hours, microseconds, and nanoseconds sequentially.

As we use it more, we run into a problem! Let’s assume that we want to display the atomic time to the user. We could just constantly Update() the time returned from the atomic clock, but I’m not a big fan of polling. Why? If we hit unexpected latency or blocking and we poll slower than we expect, we’re going to display times to the user that are no longer accurate. The data changed and nobody told us.

I call this the expiration problem. Sometimes it’s easy to fix — dude, just poll the clock faster. Duh. — and other times it’s not so easy. Just look at the assassin example. Even when we could show the function always worked consistently, the assassin could still be dispatched to an old address looking for an old name. This is obviously bad: the data rotted and the programming language stayed silent. The system knows everything it needs to say, “Hey, by the way, this data isn’t good anymore,” but it doesn’t.

The front office of the Evil Crime Syndicate naturally doesn’t understand the distinction and will totally give my would-be assassin a hard time. “What do you mean you killed the wrong person? Our system always gives a consistent and up-to-date target. Obviously this is your fault. You’re getting a pay cut after you finish this assignment.”

Of course, there are also problems introduced when values are allowed to expire. The data doesn’t always need to expire! An assassin could gather clues from old aliases and residences, for instance. You could want to store a list of AtomicTimes for processing elsewhere.

Any language that uses expiration as an explicit action needs to also allow the programmer to differentiate between the following:

• Hard expiration: Occurs when using a dated value could be expensive or harmful. An exception is thrown if you attempt to use the object after expiration.
• Soft expiration: The programmer wants to know if the value goes bad, but the value is still usable in some views. This could be implemented through either callback handlers or exceptions.
• No expiration:  The default for most data.

Ideally, this would be settable per each view of the data.

Conclusion

Concurrent programming has a lot of inherent wrinkles, and trying to remove all of them out is a very deep rabbit hole. Each solution usually points to another problem. Sometimes they don’t really matter, like showing an atomic clock time for an extra few nanoseconds. Sometimes they could cause expensive mistakes, like sending an assassin to the wrong place for the wrong target.

Rich Hickey’s pure function that returns the future as a function of the present is a great idea, and I’d love to see Hickey implement something like it in Clojure. It may also be possible to implement expiration! I recall that Clojure allows validators to be attached to objects to check for consistency across updates. I don’t see why expiration couldn’t be handled similarly to check for staleness on reads.

I would love to see some other language-level ideas and implementations for aborting a current action if the data fails a staleness check. “Data is guaranteed consistent and up-to-date!” would be a pretty good selling point for a language, even if the utility of having both at the same time is often low.

The expiration problem exists in every language, but if we’re actively trying to ease the pain of concurrent programming, it’s something that needs to be explicitly formalized and addressed. In fact, I’d bet a dollar that there are already 5 different formalizations for this phenomena. Does anyone know if this has been discussed in a more professional or academic publication?

Special thanks to Sarah Braun and Greg Molyneux for reading drafts

Popularity: 5% [?]