|
stldb::trans_map is a concurrent,
transactional implementation of std::map. While the goal of STLdb has been
to keep to the API of std::map as much as possible, some changes were necessary
to allow for a transactional map. Accordingly, the API of the map template
is changed in the following ways:
stldb::trans_map::mutex()
method) which is used by callers for concurrency control.
stldb::Transaction
parameter to indicate the transaction that the change is being made under.
stldb::row_level_lock_contention
exception. However methods are available which will instead block the caller
until the contending transaction is resolved. These variant methods take
a stldb::wait_policy parameter
to allow the caller to control the blocking behavior.
stldb::trans_map::update()
and stldb::trans_map::lock()
have been added to support the transactional handling of modifications. The
use of these methods is required as opposed to the use of the direct use
of a referenced entry as an lvalue.
The rationalization for these changes to the map API is discussed in the remainder
of this section. Aside from these changes, the stldb::trans_map
interface is otherwise identical to the std::map interface, for the sake of
minimizing the learning curve associated with this library.
Concurrency control with stldb::trans_map is via a mutex which is exposed
through the stldb::trans_map::mutex()
method of the map. The type of this mutex is determined by template parameters.
It can be an interprocess_mutex or a interprocess_upgradable_mutex. The map
container supports a degree of concurrency via shared locking. If an interprocess_upgradable_mutex
is used the type of lock acquired can be shared for all operations except
calls to insert().
Applications using the stldb::trans_map must first acquire a lock on the maps mutex and can then call one or more methods of the map while the lock is held. This approach allows the application to decide the granularity of locks at the level of map. A lock might be held for one or several operations. This convention also allows you to choose the type of lock (sharable or exclusive) in cases where the mutex type is an upgradable mutex.
TODO - example of insert, alongside find.
When an application uses a method which inserts, erases, or modifies an entry within the map, the entry in question is locked by that transaction, using an entry-level lock. This is the equivalent of a row-level lock in traditional RDBMS databases. The duration of the entry-level lock is tied to the transaction which creates it. It is held until the transaction is committed or rolled back.
stldb::trans_map implements multi-version concurrency control. This means that the last committed value of any given entry remains in the map, even when there is a pending change or erase of an entry. This in turn allows accessor methods like find(), lower_bond(), and upper_bound() to continue to show the last committed value for any entry, corresponding to iso isolation level 1 (read committed). row-level locks never block these read-only accessor methods.
TODO - example of read isolation.
There are versions of the accessor() methods which take a transaction as a parameter. Such accessor methods (and any iterators returned by them) return results which reflect outstanding changes which have been made as part of that transaction. So for example, iterators can point to newly inserted entries which have not yet been committed. The use of these accessor methods yields results which are consistent from the perspective of the transaction. Methods whch do not take a transaction() always return committed information, and return iterators which show only committed information.
TODO - example of the above.
A normal map permits the modification of entries within the map by using a dereferenced iterator directly as an lvalue. The transactional infrastructure of STLdb needs to know when the application is modifying the entries within the map. Attempting to infer this from the use of operator* or operator-> on iterators is subject to false inferences in which routine non-const access could be incorrectly asmed to be an update. stldb::trans_map makes use of a more explicit technique to avoid that problem.
stdb::map has an update( iterator, V newValue, txn ) method. When called, this method sets the value component of the entry at the iterator to the newValue passed, and does so within the context of the transaction passed. This method establishes an entry-level lock on the entry, if one is not alread in place.
TODO - example of find() followed by update()
One point with regard to updating entries in a map should be kept in mind. With the example above, threads could overwrite each other's values because a shared lock is being used during the scope of the find() and update() methods. Specifically, the following paths of execution, by two different threads on a shared processor, shows the problems that can occur:
Under that sequence, the second thread overwrites the value that had just been committed by the first. To avoid this problem, the application could use an exclusive lock when locking the map, however that can reduce the overall concurrency of the map, and could be a significant problem if a great deal of processing is required between the initial find() of a row and the subsequent update().
As an alternative, stldb::trans_map includes support for a lock( iterator, txn ) method, which can be used to establish a row-level lock on an entry without modifying it in the process. This then allows the application to use the entry without fear that any other transaction could change the values on the entry.
A revised version of the prior example which addresses the overwrite problem would look as follows:
TODO - example of find(), lock(), increment value attribute, and update()
The locking example in the previous section, is almost a complete, ready-to-run example. One detail remains. When a thread attempts to lokc(), update() or erase() an entry which currently has an entry-level lock held by another transaction, a lock contention problem has occurred. This contention can be handled in one of two ways by stldb::trans_map:
stldb::row_level_lock_contention
exception, requiring that it be retried later once the transaction holding
the lock has completed.
STLdb, as with most relational databases, supports both of those options.
Those versions of insert(), erase(), update(), and lock() which do not take
a wait_policy parameter do not block, and will instead throw an stldb::row_level_lock_contention
exception to indicate that the operation cannot be done without blocking.
Alternative versions of insert(), erase(), update(), and lock() exist which take a final 'wait_policy' parameter. The wait_policy argument permits blocking behavior and determines the blocking policy. The wait_policy can, for example, determine a timeout whch applies to the wait.
class wait_policy { void unlock_container(); void relock_container(); template <class row_mutex_t, class condition_t> void wait( boost::interprocess::scoped_lock<row_mutex_t> &mutex, condition_t &condition ); }
The wait_policy is assumed to have a reference to the lock that the application currently has on the container. This allows it to implement the unlock_container() and relock_container() methods. The wait() method is invoked to perform a wait on the condition variable passed. Internally, stldb::trans_map uses an interprocess_condition to implement blocking on entry-level locks. The wait() method must wait on that vairable, but may do so conditionally.
STLdb comes with two pre-implemented wait policies. stldb::wait_indefinitely_policy
blocks until the entry is unlocked. stldb::bounded_wait_policy
will wait for the entry-level lock to be released for a designated maximum
amount of time. If it is not released within that timeframe, a stldb::lock_timeout_exception
is thrown.
TODO - Example find(), lock(), update() with wait policy.
With the blocking variant, it is possible for the lock(), update(), or erase()
method to ultimately fail if the entry which it is waiting on is erased by
the transaction which currently holds the lock. In the event that this should
occur, those methods will throw a stldb::row_deleted_exception
to signal that the entry was erased, and thus can no longer occur.
Iterators acquired from a stldb::trans_map are good so long as the thread using them maintains at least a sharable lock on the trans_map. Once a lock is released, it is possible that other threads might erase the entry that the iterator currently points to.
The stldb::trans_map iterator has a valid()
method which returns true if the iterator is known to point to a valid entry
in the trans_map. If an iterator is used across locks on a trans_map, this
method can be used to confirm that the iterator is still valid. Currently,
this method errors on the side of caution. It will return false if any entries
in the trans_map are erased after the iterator is created.
With the blocking variant of the lock(), update(), and erase() methods, the application's lock on the container is released while the application is waiting, and as such, all iterators which existed prior to the blocking call might then be invalid, and their valid() method should be consulted.