LJ Archive

Simple Access Berkeley DB Using STLdb4

Ben Martin

Issue #154, February 2007

STLdb4 makes C++ programming with the Berkeley DB simpler and more effective.

The Berkeley DB library provides a solid implementation of both the B-Tree and Hash file structures. The implementation includes support for transactions, concurrent access of database files from multiple processes, and secondary indexing as well as logging and recovery.

In this article, I use the term database to refer to a B-Tree or Hash maintained by Berkeley DB. These databases allow rapid key to value look-ups.

The standard distribution of Berkeley DB comes with both a C and C++ API. Unfortunately, the standard Berkeley DB C++ API is a very thin wrapper neglecting modern C++ designs, such as smart pointers, standard C++ I/O streams, iterators, default arguments, operator overloading and so on. As a concrete example of the lack of reference counted smart pointers, the Berkeley DB API for Db::get(), shown in Listing 1, includes two Dbt pointers and the ownership of the memory for these is not immediately obvious.

The STLdb4 Project was created to make using the Berkeley DB from C++ easier. The STLdb4 API aims to make simple database interaction trivial while still keeping more advanced usage simple. A Berkeley DB object behaves similarly to an STL collection allowing look-ups and the setting of elements using an overloaded array operator. A full example program is shown in Listing 2. After execution, the file named with argv[1] will contain a Berkeley DB B-Tree file containing the foo-bar data pair.

The main class is the Database and the reference counted smart pointer for this class is called fh_database. This trend is used throughout STLdb4 where the smart pointer for Foo is called fh_foo. Databases can be opened either as in Listing 2 directly in the constructor or using the empty constructor and the open() or create() methods later. The main difference between open and create is that create requires a database type (for example B-Tree or Hash) and will create a new database at the given path if none exists already.

In the example in Listing 2, I don't have to close the database explicitly, because the smart pointer to the Database object will handle that for me.

Standard STL collection methods, such as empty(), size(), insert(), erase(), count(), begin(), end(), find(), upper_bound() and lower_bound(), all exist in the Database class. There are also partial versions of the latter three methods. The partial versions allow the looking up of entries with part of a key in B-Tree files. A bidirectional iterator object is returned by many of the above methods.

When storing large values in the database, using the standard I/O streams can be more efficient than using the get() method or overloaded array operator. This is because the standard I/O streams use partial read and write operations on the underlying Berkeley DB file. A standard I/O stream is obtained using the getIStream() and getIOStream() methods of the Database class.

The example in Listing 3 shows the standard C++ I/O stream interface for STLdb4. The housekeeping of performing partial I/O to the Berkeley DB file is handled by STLdb4. Accessing large chunks of data through this API maintains a low memory consumption. The API shows one of the used getIOStream() calls as having a ferris_ios first parameter. As the libferrisstreams library that STLdb4 uses offers generic I/O stream support, the ferris_ios is a backward-compatible extension of the std::ios bitfield. The extension allows specifying such things as memory mapped backing and sequential stream access to be nominated for use where supported. The output from running this example is shown in Listing 4.

Storing Objects

One major difference between the Database class and an STL collection like std::map<> is that the key and value are not parameterized in Database. The main reason for this is that the items in a Database object are usually not in RAM but are read from disk on demand. Also, in order not to limit the functionality offered by Berkeley DB, the Database class has to support storing arbitrary data and not a heterogeneous collection of objects.

The illusion of stored objects can be created using implicit constructors and type conversion thin object wrappers. Shown in Listing 5, the Person class stores some information about people. The implicit constructor takes a DatabaseMutableValueRef, which is the class returned by the array operator in Database. A Person object is implicitly convertible to an std::string to enable it to be serialized to disk. As the main function shows, this thin wrapper makes it appear that the Database is storing Person objects.

Secondary Indexing

Sometimes the information that you are storing has multiple keys by which you would like to be able to find a given item quickly. For example, if you are storing contact information, you want to able to look up people based on either their name or e-mail address.

You could achieve the above by storing each person's information manually, using the name as the key and maintaining a second database from e-mail address to name. To find a person by e-mail address, you would use the e-mail-keyed database to find the name and then the name database to find the actual information. Maintaining indexes manually like this is highly error-prone, and moreover, the secondary indexes in Berkeley DB can do this housework for you automatically.

The above example can be implemented by having the primary key-value data stored with the person's name as the key and a secondary index on the e-mail address(es). This setup is shown in Figure 1. I refer to the database with the name-to-person data mapping as the main database and the e-mail look-up database as the secondary index.

Figure 1. A Secondary Index for Quick Look-Up by E-Mail Address

The main concern when using secondary indexing with STLdb4 is how to extract the secondary key from your data. There are some template functions in STLdb4 to help you with this. The getOffsetSecIdx() template takes an offset as its template argument and will return all the data from that offset to the end of an item as the secondary key. The getOffsetLengthSecIdx() is similar, but it allows you to specify both the offset and length of the secondary key data. Finally, the getOffsetNullTerminatedSecIdx() takes an offset and a string skip count to allow you to extract the nth null-terminated string after a given offset. For example, if you have five (32-bit) integer values followed by four null-terminated strings as your persistent format, you could use an offset of 20 and a skip of two to extract the third null-terminated string as your secondary index key.

Assuming the use of the Person class from Listing 5, the code in Listing 6 creates and uses a secondary index on the e-mail address for your Person objects. Because the disk format starts with our string data, when creating the extraction function with getOffsetNullTerminatedSecIdx(), I use an offset of zero and skip one null-terminated string (the name) to extract the e-mail address null-terminated string.

I then perform a partial look-up using the secondary index. The equal_range_partial() method finds both the lower and upper bound for partial key material. In this case, I find any e-mail addresses that begin with al. The output from the program is shown in Listing 7. Note that the first element of the iterator is the key from the secondary index, and the second element is the data from the main database. The key from the main database for this look-up is available through getPrimaryKey() on the iterator object.

Transactions

Transactions are supported either by passing an explicit transaction object to each method or by setting the implicit transaction on Database objects. The latter style can be very convenient in cases when the overloaded array operator is used, which does not allow a transaction object to be passed in (only one argument can be passed to the array operator).

When explicitly passing a transaction object to the database for each method call, the Transaction class has the commit() and abort() methods either to ensure the data is stored safely on disk or the whole transaction is fully reverted. When the last reference to a transaction object goes out of scope, it will call commit() in its destructor if it was not already committed or aborted.

If you are operating on only one database, you can largely avoid the Transaction class and use the start() method of the Database class to begin an implicit transaction. When using an implicit transaction, the commit() and abort() methods of the Database class perform the transaction finalization actions.

The simplest method of using transactions is shown in Listing 8. Things of note in the example include the use of a database environment, which in this case will include initialization of the Berkeley DB transaction subsystem. A transaction object must be passed to the Database object when it is created. In the Database constructor, I pass a new Transaction that will be handed in as an fh_trans smart pointer, which will clean up the Transaction object for me after the Database object is constructed. When executed, the Initial value and Final value lines will print the same information to cerr.

The same transaction can be used with multiple databases by holding onto the transaction object smart pointer and associating it with each database. This is shown in Listing 9. The second part of the example uses setImplicitTransaction() to associate the databases with the current transaction.

The default action of a Transaction object can be changed to calling abort() by setting setDefaultDestructionIsAbort(true) on the transaction object. This is very handy for use with a Resource Acquisition Is Initialization (RAII) programming style to revert a transaction automatically if any exception occurs in a code block. This RAII style is shown in Listing 10. The code block marked starting at the comment (AA) sets the default destruction action for a transaction to call abort() and then modifies the database with this transaction. An exception is explicitly thrown that will cause the Transaction object to be destroyed (its last reference being the one held by tr on the stack). This will call abort() for the transaction, and we will eventually print the old “bar” value at the end of the example.

The Database::iterator class uses Berkeley DB cursors in its implementation, so the transaction we pass to Database::find() will be used for any operations performed on the database iterator. For example, if getIOStream() was called on diter, STLdb4 would be performing partial I/O using the transaction tr on the Berkeley DB file behind the API.

This use of RAII is very handy for code that wants to make changes to the database in one go, but that might throw an exception along the way.

The setImplicitTransaction() call should be avoided when performing RAII, because it will have the Database keep a smart pointer to the Transaction that will prolong the call to abort() if an exception is thrown.

Database Environments

Database environments are convenient for configuring a group of Berkeley databases that will be used together. Using database environments together with the Concurrent Data Store mode with multiple database files allows you to have multiple applications all reading and writing to the database files, and Berkeley DB takes care of locking to make sure that the files don't become corrupt.

The default database environment in STLdb4 is effectively a null environment. New database environments are created using the Environment class. The static Environment::setDefault() method can be used in applications using a single database environment to avoid having to pass the database environment object to the Database constructor.

The code shown in Listing 11 uses a database environment to protect two database files from simultaneous update by multiple running processes. First, a new database environment is created and set to use the Concurrent Data Store mode. This database environment is set to be the default STLdb4 environment. The first Database object is created using the default database environment; the second Database object is created by specifying the database environment explicitly and opening the database file as a separate call.

Other Things of Interest

The ordering of elements in the database can be changed with Database::set_bt_compare() using either a function pointer or a Loki functor object. For details on Loki functors, refer to the Modern C++ Design book (see the on-line Resources). As the comparison function is a relatively low-level operation, no implicit conversions happen for this, and you must compare two Dbt values. A collection of functions for numeric comparison, such as getInt32Compare() and string comparison with and without case sensitivity using getCISCompare(), are available in STLdb4. The ordering of a comparison functor can be reversed by passing it to makeReverseCompare() to create a new functor. These operations must be performed before the database is open, so you have to use the open() or create() calls and the non-opening Database constructor as shown in Listing 12.

Increasing the default Berkeley DB cache size using Database::set_cachesize() can improve read-only database performance significantly.

Future Directions

A template subclass of Database taking parameters similar to std::map<> would be nice. There would need to be some extra work to allow both the key and value to be (de)serialized on demand perhaps by assuming that both can be Boost serialized.

Resources for this article: /article/9512.

Ben Martin has been working on filesystems for more than ten years. He is currently working toward a PhD at the University of Wollongong, Australia, combining Semantic Filesystems with Formal Concept Analysis to improve human-filesystem interaction.

LJ Archive