c o d i n g f r o g s

croaking about programming, programming languages, software engineering, and the business of software

Versioning Containers and Iterators

Uh, this is a programming post.  Just so you know.

The Problem

Okay, so let's start this discussion with a simple linked list that contains the ingredients for Bill Cosby's Chocolate Cake for Breakfast:

Fig. 1 - Linked list of ingredients for Chocolate Cake for Breakfast

Normally we'd use a linked list in programming when we know we may have to arbitrarily insert items later on.  For example, I just realized that this cake does not contain chocolate, so I should be able to insert that into the list by shuffling a little bit:

Fig. 2 - Chocolate Cake for Breakfast, with Chocolate Added

This seems like a much tastier recipe.  But there can be a slight problem with this.

Suppose the linked list is serving as a model for your recipe view.  You have a UI that accessess the model and then displays the results in some sort of view that you can see on your laptop in the kitchen.  Suppose further that you decide to go even crazier and not just stop with adding chocolate, but you are also going to add sugar and frosting.  INSANE!

This is not a problem yet.  Likely your UI offers the ability to add new ingredients through the UI, so you just add them and the model gets updated, and when your view refreshes you see the new list:

Fig. 3 - Chocolate Cake for Breakfast - Dessert Style!

That sounds like a great chocolate cake.  But now suppose Mr. Cosby is on stage in Winnemucca doing his Chocolate Cake for Breakfast routine, and for some reason that nobody can understand the teleprompter that reminds him of the routine is using your data model to render the view - right at the exact moment in time that you are changing the recipe.

Uh-oh.

I've run into this problem a number of times in my software development career, where I have a data structure that is being accessed by more than one user at the same time.  In our case, we have one read-only accessor and one read/write accessor.  At first glance it doesn't seem like this should be a problem.  But unfortunately, even though the reader isn't making changes to the model, the reader still depends on the model having a constant state.

There's a couple of fairly simple ways to address this problem.

First, we can make a copy of the model for each user.  We can have a resource that provides a copy when a user requests the copy.  Then that user can do whatever they want with the model - read or write.  When they are done, they can either discard their copy, or turn it back to the resource for the changes to be merged into the whole.

This might work for some implementations.  In our trivial example here it would probably be just fine.  But if I have a data structure with two million 50-byte records, this isn't such a great idea.  It isn't just that I don't want to make a copy of a 100 Mbyte (okay, 95 for you technicality folk) data structure - I don't want to double my memory usage from 100 Mbytes to 200 Mbytes (or 95 to 190, sheesh).  So making a copy won't always work.

Another option is to lock the structure.  Using some sort of a mutual exclusion primitive I can lock the data structure so that only one user can access it at a time.  I can't just hold the lock per-access, though - I have to maintain sessions and locks for the entire session.  In other words, I have to make sure that nobody can change the recipe at all throughout the duration of Mr. Cosby's act.  This high level of granularity in the locking of the data structure makes it hard to use.  And it is particularly frustrating for read-only users who are thinking, "Why can't I access the structure?  All I want to know is what is in it!"

Versioning

One way I've successfully solved this problem in production code is to use a versioned container and versioned iterators for that container.  I used these at Volera, for example, for some reason that doesn't matter now, because Volera is DEAD.  Anyway, here's how they work:

Versioned Containers act pretty much like regular containers - vectors, lists, hashtables, etc.  The difference is that each link from one element in the container to the next has an associated version number on the link.  Any given element can have a number of "next" links - even a singly linked list, like in our example.  Each link would have a different version number.  The container itself also has a version number, which corresponds to the highest numbered link in the container.

Versioned Iterators go along with the versioned container.  When you request an iterator from a container, it gives the iterator a version number which corresponds to the current version number of the container at the time of request.  The user requesting the iterator can also request a different version number.

Here's what our data structure might look like if it were versioned:

Fig. 4 - Chocolate Cake for Breakfast with Versioned Containers and Iterators

This ends up working out pretty cool.  Mr. Cosby can request a versioned iterator of the view when his show begins that displays the model as it is when his show starts.  Let's say that his iterator is version 1.  That iterator traverses the list by only following links where the version number is less than or equal to the version number on the iterator.  So it first goes to "eggs", then follows link 1 to "milk", then follows link 1 to "wheat", then ends.  It can be doing this at the same time that another user is changing the data structure, first by inserting "chocolate," which creates the version 2 link from "milk" to "chocolate" and the version 2 link from "chocolate" to "wheat," and later by inserting "sugar" and "frosting" as version 3.  A version two iterator on the structure would start with "eggs" then follow the version 1 link (remember - less than or equal to the iterator version) to "milk."  But then it would follow the version 2 link instead of the version 1 link, so now it goes to "chocolate" instead of going directly to "wheat."

The same goes for the version 3 iterator, which gives us everything in the data structure.

There's a couple of issues you have to deal with when you implement a structure like this.  First off, you need some sort of a scheme to go through the structure and prune it of old traversal versions.  If I remember correctly, a scheme that will work to do this is to have the container itself remember how many users are accessing it and what versions they are at.  When one iterator goes away, the iterator should report this back to the container.  The container then looks to see if that iterator is the lowest-version-number iterator that it knew about.  If it is, the container can go through and prune all of the links that are versioned at that number and below, as well as nodes in the structure that are only included in the structure by links at that version and below.  So there's a little bit of housekeeping that has to go on, but the container should be able to do this after iterators go away.

In other words, once Mr. Cosby's show ends, the data structure that previously looked like Fig. 4 should end up looking more like Fig. 3.

Another problem to consider is this:  If the data structure lives for a long time and has lots of accessors, it is possible for the version numbers to overflow.  The overflowing isn't necessarily a problem, though, as long as you keep track of what is really the oldest version in the data structure.  Another way to do this is, as you prune the table, you can take the liberty of reversioning the table if there are no accessors to the table.  Depending on your situation, you may never have a chance to lock the whole structure in order to reversion it, but the first option should be workable.

Lastly, since you have to version the links themselves, you might not be able to directly use standard containers; for example, if you are using C++ you might have to create your own linked list template with a list of versioned next pointers in each node, instead of implementing your versioned list container in terms of the STL list container.  I never tried this so I'm not sure how it would work.  When I did this, I did it using a tree container that was implemented in STL style, with versioning in the pointers and iterators.  It was pretty cool.

Popping Threadsafe Containers

After spending a bit of time last week dealing with thread safety issues and a queue in C++, it only seems appropriate to blog a bit about it.  (Obviously, the information below would also apply to a stack or probably any other container type.)

Suppose you have a very common multiprocessing scenario:  two threads, one of which is producing work to be done, and another which is consuming the work to be done and performing the work.  You can accomplish this in a pretty straightforward fashion with:

• A queue
• Mutexes to prevent concurrent queue access
• A condition variable to tell the consumer when there is work to do

Originally I thought about creating my own container class for this.  Then part of my brain resisted.  "Quiet, engineering part of Matt's brain!" it exclaimed.  "You're just trying to do that because it seems Interesting!"  So I shut down that idea and pushed on trying to use a standard STL queue.  However, after I had to deal with some concurrency issues over and over, I realized that, at least this time, the engineering part of my brain was right.

So I set out to create a threadsafe queue.  The idea was that it would feel a lot like an STL queue, and would implement thread safety under the covers for you - so, for example, a simple call to q.empty() would automatically lock the mutex for you, see if the underlying queue was empty, then unlock and return the result.  So, essentially an STL queue wrapper class with automatic mutex locking, right?  It should be easy!

Well, you'd think so, until you get to an implementation of pop().

To see why this matters, first we should establish what we expect out of a threadsafe queue in C++:

• It should feel like an STL queue.  This means that it should have similar semantics and API if possible, and also, it should be a template.
• You get out what you put in.  Not a handle to what you put in; exactly what you put in is what you get out.
• Thread safety should be handled automatically - the user shouldn't have to deal with thread safety.

An STL queue "pop()" isn't as simple as it sounds.  The concept of "pop" is actually performed like this:

    std::queue q;
    ...
    if (! q.empty()) {
        int v = q.front();
        q.pop();
    }

Popping an empty queue has strange consequences; in fact, on my machine, it segfaults.  You'd think the queue would be resilient to that behavior but it isn't.  Also, you have to get the item off the front in a separate operation from actually removing the item.  This is so you can store anything in the queue - pointers, reference objects, etc. - and obtain the item in the front of the queue and know it will survive long enough for you to do something with it.  You pop() the queue after you are finished with the item.

That's all fine but it makes our threadsafe queue a bit of a problem.  Suppose we decide to follow strictly the STL queue API.  In that case, we'd perform an "if not q.empty(), then q.front() and q.pop()" dance.  We have to assume that each of those three actions is legal on its own though, and we surely can't release the lock after each one.  So that would mean that the user has to obtain a lock on their own, to be used outside of the whole three-step dance, which breaks one of our rules, namely, that the user shouldn't have to deal with thread safety.

Okay, so what if we abandon the need for strict adherence to the STL queue semantics, and instead just implement a pop() method that does everything?  Now we can hide the thread safety management from the user.  But now we have a different problem.  How do we know whether the value we get back from pop() is a legal value?  How do we know whether it came from the queue or whether the queue was empty and there was nothing to pop()?  We need some way to check to see whether the value coming back is valid, i.e., whether there was something in the queue to pop beforehand.

There's a couple of ways to do this, but none I like.

• If the return value were a pointer (or an iterator), we could check for NULL (or end()).  However, we don't necessarily know that.  If the class is a template, and if we always get back what we put in, we can't know whether the return value is a pointer or a value or a reference.  True, we could cast the return value to a pointer type - but then, not only are we not returning what we put in, but we are getting into a rather scary situation where the user is required to massage the data before it can be used properly.  And we lose type safety.
• We could return a std::pair<bool, t> where t is the type used to populate the queue.  Not as scary as the casting solution before, but still with the problem where the user has to massage the data, and the return value isn't strictly what was put in (although it is contained in the pair).
• We could throw an exception if the container is empty, but an empty container isn't exactly an exceptional case and is probably not a good ethical candidate for throwing an exception.
• We could stop using the STL queue and create our own queue with more reasonable semantics.  However, although I'm not necessarily in love with the STL queue, I'm also not convinced I can do it better, at least not convinced enough that I want to spend the time to do something that already exists.
• We could do away with making the wrapper class a template and instead make it implementation-specific.

Since I don't know for sure that I will need my threadsafe queue for anything other than a very specific data type I have in mind right now, I chose the last option.  This is the agile way - I'll meet today's requirements today, and trust that I can refactor the code to meet future requirements when they show up.

So now everything works great, except doing the wait on the condition variable, which normally looks something like this:

    mutex m;
    condvar cv;
    m.lock();
    if (q.empty()) cv.wait(m);
    v = q.pop();

Yeah, here I am, managing thread safety outside of the queue again.  I really should put this into my threadsafe queue also; except I would need a method something like waitThenDo(action) where action is a function pointer or some other callable.  I hate how that makes my code look though.  And at this point, with the waiting done as shown above (roughly), my code is working, so I've stopped caring.

But if you have a great solution to this problem, I'd love to hear it.