Transactional Programming

Database techniques applied to C++ programming.


November 06, 2007
URL:http://www.drdobbs.com/cpp/transactional-programming/202802978

Calum, who holds a Ph.D. in Computer Science from the University of Cambridge, is a senior software engineer at Sophos Plc. He can be contacted at [email protected].


When programs encounter exceptions, they must not leave data in an inconsistent state. It would be no good for a function to half-complete because that could leave the data in an unexpected state and lead to bugs later in the program. But this is exactly what can happen when exceptions are thrown halfway through a function.

For example, the problem with this function:


std::vector<std::string> list1, list2;
void f(const std::string &s)
{
 list1.push_back(s);
 list2.push_back(s);
}

is that the second push_back() might fail and throw std::bad_alloc. This would leave the program in an inconsistent state because list1 and list2 are different. While desktop computers rarely deny a memory request, std::bad_alloc should be anticipated on portable devices or servers.

In an ideal world, functions should either completely succeed or fail without side effects. This all-or-nothing behavior is referred to as "atomic" because it will never leave the program in a halfway state.

A way of describing the effects of exceptions on functions is with Abrahams guarantees [1]:

Although the nothrow guarantee sounds ideal, it is often impossible to arrange for a function to never throw an exception, especially when memory allocation takes place, which could throw std::bad_alloc at an inopportune moment. Many standard library containers rely on memory allocation and could, therefore, throw. The basic guarantee is often not good enough, since leaving a program in a safe but indeterminate state is not terribly useful. It is much better to live with exceptions, and let them propagate out to the caller in a safe and predictable way.

But error recovery is not straightforward in C++. When an exception is thrown, all of the side effects prior to the exception must be undone. In real code this is not often done, or it is added as an afterthought. Even when exceptions are considered up front, analyzing them and recovering from them is difficult and error prone. Exceptional paths are generally the least tested part of software—it is impractical to unit-test every exceptional path caused by std::bad_alloc.

While the best solution is to try to redesign the data structures, this isn't always possible. Consequently, you might try to catch the second exception and undo the push_back() on list1:


void f(const std::string &s)
{
 list1.push_back(s);
 try
 {
  list2.push_back(s);
 }
 catch(...)
 {
  list1.pop_back();
  throw;
 }
}

This code is safe because the Standard guarantees that pop_back() will not throw an exception. Unfortunately, it is also ugly. In more complex situations, wrapping individual operations in a try-catch is hard work and makes the code difficult to read.

Scope-guards [2] offer an alternative. A scope-guard is a utility class that performs some important clean-up in its destructor, as in:

void f(const std::string &s)
{
  list1.push_back(s);
  ScopeGuard guard = MakeObjGuard(
   list1, &std::vector<std::string>::pop_back);
  list2.push_back(s);
  guard.Dismiss();
}

guard calls list1.pop_back() in its destructor, unless guard.Dismiss() is called. So the scope-guard automatically undoes list1.push_back() if list2.push_back() fails. This is an improvement because there is no need to write out the exception handler.

Unfortunately, while you can safely undo a push_back(), you cannot safely undo a deletion or a push_front() because an exception could be thrown while trying to clean up after the first exception. For example:


void g()
{
  list.pop_back();
  h(list);
}

You could not write:

void g()
{
 std::string saved_back = 
    list.back();
 list.pop_back();
 try
 {
  h(list);
 }
 catch(...)
 {
  list.push_back(saved_back);
                  // Can throw
  throw;
 }
}

because list.push_back() could itself fail, breaking our guarantee of atomic behavior.

This shows that only certain operations can be undone on the standard containers. Atomic behavior is only possible to guarantee when a function has no side effects prior to an exception being thrown, or the availability of a guaranteed undo function that can be called in a scope-guard or an exception handler.

Dealing with exceptions is complicated and sometimes messy, and requires different approaches in different circumstances. Some good examples of the subtleties of exception handling are given by Herb Sutter both in Exceptional C++: 47 Engineering Puzzles, Programming Problems and Solutions (Addison-Wesley, 2000); and More Exceptional C++ (Addison-Wesley, 2002).

Transactions

Databases approach errors in a completely different way. Instead of making error recovery explicit, databases make error recovery implicit through the use of transactions; see An Introduction to Database Systems by C.J. Date (Addison-Wesley, 1991).

In this Transact-SQL example, the transaction begins with BEGIN TRAN T1 and ends with COMMIT TRAN T1:


BEGIN TRAN T1
UPDATE table1 ...
UPDATE table2 ...
SELECT * from table1
UPDATE table3 ...
COMMIT TRAN T1

Transactions are units of work that either completely succeed, or can be rolled back completely. If an error such as a disk full, a key violation, or user error occurs during the transaction, it simply rolls back (undoes) all of the operations to the beginning of the transaction. This is safe and robust because the data is guaranteed to be left in its initial consistent state. While recovering from exceptions is difficult in C++, it is extremely easy in databases with transactions.

The Atomic Library (calumgrant.net/atomic) I present here implements transactions in C++, based on database transactions. Here is the same example using a transaction:


atomic::vector<std::string>    list1, list2;
void f(const std::string &s)
{
 atomic::transaction tr;
 list1.push_back(s);
 list2.push_back(s);
 tr.commit();
}

The transaction tr defines the scope of the transaction, namely the entire function f(). list1 and list2 are of type atomic::vector, which is a special container that interacts with atomic::transaction. If f() exits without calling tr.commit(), then all of the changes in f() are undone.

The Atomic C++ Library for transactional programming provides a range of containers that can be rolled back to any point in their past by transactions.

Transactional containers are designed in such a way that deletions can be safely undone without the possibility of failure when the container is rolled back, even if it involves inserting data back into the data structure.

Nesting Transactions

The ability to roll back a single function is okay, but what about functions that need to call other functions? For instance:


void f()
{
 g();
 h();
}

If h() throws an exception, how do you roll back g(), if g() could do something such as detonate a bomb? The answer is that you can't. But if g() and h() only use transactional operations, then they can be rolled back by a transaction in f(); for example:

void f()
{
 atomic::transaction t1;
 ...
 g();
 ...
 h();
 ..
 t1.commit();
}
g()
{
 atomic::transaction t2;
 ...
 t2.commit();
} 
h()
{
 atomic::transaction t3;
 ...
 t3.commit();
}

g() is atomic because of the transaction t2. h() is atomic because of the transaction t3. And f() is atomic because the transaction t1 can roll back anything in f(), g(), or h(). Even when t2.commit() has been called in g(), t2 can still be rolled back.

Transactions can be nested to any depth. Transaction objects must always be nested, which is guaranteed by the C++ scoping rules.

Transactional Containers

The Atomic Library has a variety of containers that can be used in transactions:

In general, these containers behave exactly as their std equivalents, but they can be rolled back by atomic::transaction. For example:


atomic::set<Item> pending;
atomic::list<Item> processed;
void process()
{
  atomic::transaction tr;
  while(!pending.empty())
  {
    Item &i = pending.front();
    i.process();
  processed.push_back(i);
    pending.pop_front();
  }
  tr.commit();
}


When the function encounters an exception in process(), the entire function is rolled back as if no items had been moved from pending to processed.

All functions on atomic containers are guaranteed to be strongly exception safe, unlike the C++ Standard Library.

Transactional Values

Any C++ class can be made transactional. The atomic::value class template holds a single value that can be rolled back to any previous value.


atomic::value<std::string> name =
     "bill";
{
  atomic::transaction t1;
 name = "tom";
  assert(*name == "tom");
 {
  atomic::transaction t2;
    name = "fred";
  assert(*name == "fred");
  t2.commit();
 }
  assert(*name == "fred"); 
    // Committed by t2
}
assert(*name == "bill");
    // Rolled back by t1

The stored object is const, so that it cannot be accidentally modified in a way that cannot be rolled back by a transaction. Previous values are not destroyed until the end of the transaction, in case they need to be reincarnated.

Transactional Pointers

The Atomic Library provides shared pointers and weak pointers that are similar to the TR1 smart pointers (www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1745.pdf). These pointers keep a counter of the number of pointers to the object. When the count reaches zero, the object can be deleted.

These pointers do not destroy the pointee object until the end of the transaction in case the pointer needs to be rolled back, but the reference count (q.expired(), for example) behaves as if the object is destroyed. For instance:


atomic::shared_ptr<int> 
    p(new int(1));
atomic::weak_ptr<int> q(p);
{
 atomic::transaction tr;
 p.reset(new int(2));
 assert(q.expired());
 assert(*p == 2);
}
assert(*p == 1);  
    // Rolled back by tr
assert(!q.expired()); 
    // Rolled back by tr


If compatibility with std::tr1::shared_ptr is required, then a suitable approach would be atomic::value<std::tr1::shared_ptr<> >.

Implementation

The implementation of the Atomic Library is based around a central stack—a transaction stack—that logs each operation. Whenever an atomic container is modified, it pushes a record of the operation onto the stack.

Each operation is recorded in the struct:


struct Transaction
{
 atomic::container* container;
 object_pointer node;
 enum { insertion, deletion } event;
};

When a transaction is entered, the constructor of atomic::transaction stores the initial size of the transaction stack. When a transaction exits, the destructor of atomic::transaction can roll back all operations (in reverse order) to the initial size of the transaction stack. The transaction::commit() method sets a flag in the transaction telling it not to roll back.

There are just two types of atomic operations—insert and delete. Other operations can be composed of insertions or deletions.

All atomic containers derive from atomic::container:


class container
{
public:
 virtual ~container();
 virtual void destroy(object_pointer)=0;
 virtual void unlink(object_pointer)=0;
 virtual void relink(object_pointer)=0;
};

When an item is inserted into a container, it logs an insertion, a pointer to the container, and a pointer to the inserted object on the transaction stack.

When an item is deleted from a container, it logs a deletion, a pointer to the container, and a pointer to the deleted object on the transaction stack. The object is not destroyed at this point in case it needs to be inserted back into the container.

Rolling Back

Rolling back is performed differently on different containers. But what is extremely important is that rolling back must not fail. Fortunately, this turns out to be possible, even for tree-based containers such as atomic::set, atomic::map, atomic::multiset, and atomic::multimap.

When an insertion is rolled back, the unlink() function is called on the container to remove the item from the data structure, and destroy() is called to delete the object.

When a deletion is rolled back, the relink() function is called on the container to insert the item back into the data structure. The deleted item must contain a hint where the item should be inserted.

Lists

atomic::list is implemented as a doubly linked list of nodes, just like std::list would be implemented. When an item is inserted into the list, the node containing the item is logged on the transaction stack. When an item is deleted, it is removed from the data structure and stored on the transaction stack. To roll back a delete, the left and right pointers point to live nodes, giving the correct place in the list to insert the node.

There is no possibility of an exception being thrown because roll back only requires pointer manipulation, not any memory allocation. To roll back an insertion, the list node is removed and deleted (which will not throw). Figure 1 shows how list operations can be rolled back.

Figure 1: Operations on atomic::list<int>: (a) Initial list; (b) list after push_front(4); (c) list after pop_back(); (d) list after rolling back step (c); (e) the list after rolling back step (b).

Trees

The tree-based containers (atomic::map and the like) are based upon an implementation of red-black trees (a standard technique for balancing trees). When an item is inserted into the data structure, it is logged on the transaction stack. When an item is deleted, it is removed from the data structure and stored on the transaction stack.

Rolling back a deletion is tricky because the object must be inserted in the correct position in the tree. You cannot simply call insert() to insert the node back into the data structure because the comparators might throw, and the nodes might end up in a different order than the original. So the deleted node stores the next node in the data structure. When the deletion is rolled back, the node is reinserted immediately before the next node in the data structure. There are a few cases to consider, but the procedure can be performed reliably. Figure 2 shows how tree operations are rolled back (ignoring tree balancing).

Figure 2: Operations on atomic::set<int>: (a) Initial tree; (b) tree after insert(6); (c) Tree after erase(5); (d) tree after rolling back step (c); this is equivalent to tree (b); (e) tree after rolling back step (b).

With red-back trees, the tree-balancing algorithms must be called after an insertion or a deletion, but these only perform pointer manipulation and will not throw exceptions.

Cleanup

If the program could be rolled back right to the beginning, no memory would ever be freed and eventually the program would run out of memory. So objects marked for deletion must actually be deleted at some point.

This can be done when the outermost transaction has completed. At this point, there is no possibility of roll back. So the entire transaction stack is scanned for deleted objects, which are deleted, and then the transaction stack is resized to 0.

If transactions are kept short, then the transaction stack will be small, and deleted objects will not be hanging around for very long. On the other hand, if the entire program is wrapped in a transaction, then the program will never free any memory!

Concurrent Access

Transactions in different threads should be independent. When one thread throws an exception and rolls back some containers, it should not interfere with another thread that is executing quite happily. This means that concurrent threads cannot share the same transaction stack.

There are basically two solutions to this problem.

The general pattern is as follows:


{
 Lock lock(mutex);  
  // Destructor unlocks
 atomic::transaction tr;
  // Modify container
 tr.commit();
}

Performance

Transactions add around 5-15 percent of CPU time for insertion and deletion. The main overhead is logging each operation on the transaction stack. The extra memory used is proportional to the size of the transaction, not the size of the data. Provided that transactions are short, little extra memory is required. Object deletion is deferred until the end of the transaction.

Table 1 shows some performance comparisons of atomic containers compared to their std equivalents, in nonthrowing circumstances. The program used to generate these numbers is available online (see "Resource Center," page 5) and at calumgrant.net/atomic. These figures measure the same operation performed repeatedly on different types of containers. As you can see from these results, atomic containers do add some overhead, which is to be expected. The only container for which the overhead dominates the performance is for vector<int>, which is so efficient that the operations on the transaction stack are slower than the operations on the vector itself.

Container Operation std:: (ms) atomic:: (ms) atomic/std
list insert 750 937 1.25
delete 297 313 1.05
list insert 3469 3718 1.07
delete 985 937 0.95
vector insert 16 375 23.4
vector insert 3688 4516 1.22
set insert 1172 1484 1.26
delete 375 390 1.04
set insert 5765 5890 1.02
delete 1062 1016 0.96
map insert 2203 2452 1.11
delete 375 390 1.04
map insert 9517 9813 1.03
delete 1375 1391 1.01

Table 1: Measuring the performance of transactions.

Conclusion

The problem with C++ exceptions is that they can occur at many points in a program, and if even a single exception is overlooked, the program is potentially unsafe. Database transactions don't suffer from this problem because atomic behavior is guaranteed by the transaction. By copying the database approach, C++ can also implement transactions. It provides guarantees of atomic behavior, helps in complex error-recovery situations, and allows smaller functions to be composed into larger transactions. Whichever exception strategy is used, it is an important part of the design and needs care, attention, and planning.

References

[1] Abrahams, D. "Exception-Safety in Generic Components," Generic Programming: Proceedings of a Dagstuhl Seminar, M. Jazayeri, R. Loos, and D. Musser, eds. (Springer Verlag, 1999).

[2] Alexandrescu, A., P. Marginean. "Change the Way You Write Exception-Safe Code—Forever." (www.cuj.com/ documents/s=8000/cujcexp1812alexandr/alexandr.htm).

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.