Monday Jan 24, 2011

The C++ Standard Template Library as a BDB Database (part 3)

In the second entry I showed that the Berkeley DB's C++ STL API can substitute in for in-memory data structures like vectors. Now in this final installment we'll see Berkeley DB at work storing object instance data referenced by STL structures.

Berkeley DB's C++ STL API, the dbstl, will automatically store the STL container in an on-disk database, but what about the data referenced by the elements within the STL container? You must choose how to store the values pointed to within the STL data structures so that they too can be reconstituted from the database. This means storing the actual data that the pointers point to, which isn't so hard. Let's get started.

Suppose we have a simple class like a "Car" (as below) that has an "Engine" member (a pointer) referencing an instance of the class "Engine".
<script src=""></script>

class Car {
  size_t length, width, height;
  Engine *engine;
  string model;
  // Member functions follow ...
class Engine {
  size_t horse_power;
  char num_cylinder;
  float displacement;
  // Member functions follow ...
view raw stl-ex-2a.cpp This Gist brought to you by GitHub.


Now we want to store the "owner name" of the Car and we do that using a map container like std::map container, here is the pseudo code:
<script src=""></script>

typedef std::map<const char *, Car> owner_car_map_t;
owner_car_map_t ocmap;
while (has more owner-car pairs to input) {
  // Accept input data for owner name and car, create car.
  Engine *pEngine = new Engine(hp, ncyl, displ);
  Car car(len, width, height, pEngine);
  ocmap[owner.c_str()] = car;
view raw stl-ex-2b.cpp This Gist brought to you by GitHub.


Note how the preceding code stores all information in memory, so it can't be automatically persisted by Berkeley DB. When using dbstl, we can persist it, as follows.
<script src=""></script>

typedef dbstl::db_map<const char *, Car> owner_car_map_t; // (1)
owner_car_map_t ocmap;
while (has more owner-car pairs to input) {
  // Accept input data for owner name and car, create car.
  Engine *pEngine = new Engine(hp, ncyl, displ);
  Car car(len, width, height, pEngine);
  ocmap[owner.c_str()] = car; // (2)
view raw stl-ex-2c.cpp This Gist brought to you by GitHub.


Now the code will store the ower name strings and Car objects into underlying Berkeley DB database as a key/data pair in (2).

In (1), though we are using a "const char*" type as key, they key string characters can be stored into underlying Berkeley DB database. This is possible because we are using a class Car rather than primitive types like int, double, etc, we don't need the ElementHolder template here. If we are storing a char* string pair in the map, we should use this type: dbstl::db_map>.

However, the Engine objects referenced by each "car.engine" member pointer are not yet properly stored into database. At this point only their memory address is stored, which is meaningless for persistence.

This is because by default the Berkeley DB STL API (dbstl) will simply copy the object to be stored using memcpy, (i.e. we are doing a shallow copy of objects) by default. Any pointer members in the object is shallow copied, the objects they refer to are not copied. This is sufficient for classes with no member pointers, i.e. when each of its instance locates on a single continous chunk of memory, but not sufficient to be completely persisted if they have pointer members.

In order to store the Engine object of each car object, we need to do deep copy of such objects, we should register the following callback functions to do so. They cooperate closely together to enable an elegant deep copy of any complex objects.
<script src=""></script>

u_int32_t CarSize(const Car &car) // (3)
  return sizeof(length) * 3 + model.length() + 1 +
    sizeof(*engine); // (4)
void CopyCar(void *dest, const Car&car) // (5)
  // Copy all bytes of the car object into memory chunk M
  // referenced by dest.
  // M is preallocated and just big enough because our CarSize is used
  // to measure the object size. Note the bytes
  // of the Engine object E referenced by car.engine should be copied
  // into this M, rather than the car.engine pointer value,
  // in order to deep copy E.
  char *p = (char *)dest;
  memcpy(p, car.length, sizeof(size_t));
  p += sizeof(size_t);
  memcpy(p, car.width, sizeof(size_t));
  p += sizeof(size_t);
  memcpy(p, car.height, sizeof(size_t));
  p += sizeof(size_t);
  memcpy(p, car.model.c_str(), car.model.length() + 1); // (6)
  p += car.model.length() + 1; // (6)
  memcpy(p, car.engine, sizeof(*car.engine); // (7)
void RestoreCar(Car &car, const void* src) // (8)
  // src references the memory chunk M which contains the bytes of a Car
  // object previously marshalled by CopyCar function, so we know
  // the data structure and composition of M. Thus here we can
  // un-marshal bytes stored in M to assign to each member of car.
  // Since we have data of the Engine member in M, we should create an
  // Engine object E using 'new' operator, and assign to its members
  // using bytes in M, and assign E's pointer to car.engine.
  char *p = src;
  memcpy(car.length, p, sizeof(size_t));
  p += sizeof(size_t);
  memcpy(car.width, p, sizeof(size_t));
  p += sizeof(size_t);
  memcpy(car.height, p, sizeof(size_t));
  p += sizeof(size_t);
  car.model = p; // (9)
  p += car.model.length() + 1; // (9)
  memcpy(car.engine, p, sizeof(*car.engine);
dbstl::DbstlElemTraits<Car> *pCarTraits =
  dbstl::DbstlElemTraits<Car>::instance(); // (10)
pCarTraits->set_size_function(CarSize); // (11)
pCarTraits->set_copy_function(CopyCar); // (12)
pCarTraits->set_restore_function(RestoreCar); // (13)
view raw stl-ex-2d.cpp This Gist brought to you by GitHub.


In (3), this function measures a Car's size in bytes, dbstl uses it to allocate just enough space to store an object's bytes. We should consider space needed for all members we want to store.

In (4) Since we want to deep copy the engine object "E" referenced by "car.engine", we should consider its size too using sizeof(*car.engine) since Engine is a simple class each of whose instance locates on a continuous memory;

And we want to store the model string's trailing '\0' character to unmarshal it easily, so we add 1 to the model.length().

In this function we return a size just big enough so that all bytes can be placed into M with no extra trash bytes left. This depends on what bytes we want to store, i.e. the CopyCar function.

In (5), this function does the marshalling work, see the comments in the function body for more information.

In (6), note how the string is copied --- we only copy its characters, ignoring all other members. And we want to copy the tailing '\0' for easier handling later.

In (7), note we are copying the Engine object rather than the car.engine pointer, in order to completely persist the car object. Since in CarSize we have allowed for the space for the Engine object, we have just enough space here.

In (8), this function does the unmarshalling work, see the comments in the function body for more information.

In (9), we are safe to do so here because we copied the trailing '\0'.

In (10) This is the global singleton for class Car where we register callback functions for dbstl to use internally to store/retrieve Car objects.

(11)(12)(13) We register callback functions like this. This way, we can do deep copy for instances of the Car class. And note that we should do (10), (11), (12), (13) actions before (1).

There are some other features in dbstl that are beyond standard C++ STL classes, which enable you to make use of Berkeley DB's advanced features such as secondary indexes, bulk retrieval (to speed up reading chunks of consecutive data items), transactions, replication, etc. Please refer to the dbstl API documentation and reference manual for details.

The full code for this example can be found here.

There are quite a lot of example code in the download package $(db)/examples_stl and $(db)/test_stl/base demonstrating these advanced features; And in $(db)/test_stl/ms_examples and $(db)/test_stl/stlport there are dbstl standard usage example code. These example code is good resource to start with.

Sunday Jan 23, 2011

The C++ Standard Template Library as a BDB Database (part 2)

In the first entry I touched on some of the features available when using Berkeley DB's C++ STL API. Now it's time to dive into more detail.

Every copy of Berkeley DB comes with this API, there is nothing extra to download or add-on. Simply download the latest version and configure it to build the C++ and STL APIs and you're ready to go.

We've worked to make it very easy to use dbstl if you already have C++ STL programming experience. It is especially easy to map your C++ STL containers existing code to dbstl. In the following sections I will list several pieces of C++ code which uses C++ STL, and show you how to convert them to use dbstl instead.

If you want to use dbstl to manage purely in-memory data structures there is very little conversion is needed from standard STL, but most of the time you will choose Berkeley DB for its persistence, concurrency and transactional recovery features. To use those features you will need to use some of the basic features of dbstl.

I. Basic Features

1. Suppose we have the following code which uses C++ STL std::vector container:
<script src=""></script>

int vector_test(int, char**)
  typedef std::vector<double> dbl_vec_t; // (1)
  dbl_vec_t v1; // Empty vector of doubles. (1)
  // The rest follows ...
view raw stl-ex-1a.cpp This Gist brought to you by GitHub.


This is the code to use dbstl instead, note that only lines 3 and 4 are modified.
<script src=""></script>

int vector_test(int, char**)
  typedef dbstl::db_vector <double, ElementHolder<double> > dbl_vec_t; // (1)
  dbl_vec_t v1; // Empty vector of doubles. (1)
  // The rest follows ...
view raw stl-ex-1b.cpp This Gist brought to you by GitHub.


The reason for the change is:

a. All dbstl classes and global functions are defined inside "dbstl" namespace.

b. For all dbstl container class templates, we must add one more type parameter ElementHolder if T is a primitive data type like int, double, char*, etc; If T is a class type, this type parameter is not needed.

c. Here we used default constructor for v1, in the dbstl case, this means an anonymous in-memory database will be created and used only by the v1 vector. You can only share the v1 vector or its database handle to share the underlying database in current process only.

Alternatively, you can create a database environment and open a database inside it explicitly and use the opened handles to create a container like the following:
<script src=""></script>

int vector_test(int, char**)
  typedef dbstl::db_vector <double, ElementHolder<double> > dbl_vec_t;
  DbEnv *penv = new DbEnv(DB_CXX_NO_EXCEPTIONS); // (2)
    flags | DB_CREATE | DB_INIT_MPOOL | DB_PRIVATE, 0777); // (3)
  pdb = dbstl::open_db(penv, "vector2.db",
    DB_RECNO, DB_CREATE | dboflags, 0); // (4)
  dbstl::register_db_env(penv); // (5)
  dbstl::register_db(pdb); // (6)
  dbl_vec_t v1(penv, pdb); // (7)
  // The rest follows ...
view raw stl-ex-1c.cpp This Gist brought to you by GitHub.


This snippets contains the majority of code you need to add to convert your C++ STL application into a dbstl-enabled application.

In line 3, we must create the DbEnv object using "new" operator, this is also a requirement to create a Db object; In line 4, the "flags" variable can be set to open a transactional environment, a concurrent data store environment, or simply a data store environment. Actually any valid use of Berkeley DB via its C/C++ API can be used here.
Between lines 3 and 4, you can set various flags or callback functions to configure the environment, in the same way you used Berkeley DB C++ API. There is a helper function dbstl::open_env to open an environment in one call, but with less configurations to do.

In line 5, we used a helper function dbstl::open_db to open the database, and optionally set various flags to the database. It helps you to open a database easier, though there are something you can't do with it, for example setting callback functions. So use it if it is sufficient for you, or simply open a database in the same way you use Berkeley DB C++ API.

We need to pay attention that different type of containers have different requirement to its database handles, see dbstl API documentation for details. Here db_vector requires the database to be of DB_RECNO type.

In lines 6 and 7, we must register the created database and environment handles into dbstl in each thread using the handles, see the documentation for the two register functions for details.

In line 8, we pass the database and environment handles to v1, so that v1 is backed by pdb database. Other thread of control can also open the database and access it concurrently, using dbstl, or simply using DB C/C++ API.

2. Apart from the above code to construct a dbstl container, the rest of the code does not need any modification. The following snippet can be appended to the above three snippets to be three complete functions doing basically the same thing:
<script src=""></script>

  for(dbl_vec_t::iterator itr = v1.begin(); itr != v1.end(); ++itr)
    *itr *= 2;
  for (int i = 0; i < v1.size(); i++)
    v1[i] += 3;
  v1.swap(v2); // Swap the vector's contents.
  v2 = v1; // Assign one vector to another.
  assert(v1 == v2);
  std::reverse(v1.begin(), v1.end());
  // More standard features follow ...
  for(dbl_vec_t::reverse_iterator ritr = v1.begin(); ritr != v1.rend(); ++ritr)
    *ritr /= 2;
  v1.insert(v1.begin(), 34);
  assert(v1.front() == 34);
  v2.assign(v1.begin(), v1.end());
  return 0;
view raw stl-ex-1d.cpp This Gist brought to you by GitHub.


Here in line 1, there are some more parameters in v1.begin() to control the behavior of the created iterator in dbstl. Refer to the dbstl API documentation for more information.

In 2, after this call, the new value for this element is stored into database, also true for line 5.

In line 4, you can make the v1.size() call to compute faster but not precisely. This is helpful when the database contains millions of key/data pairs. Like size(), there are some more similar methods in all container classes which have default parameters to work like C++ STL, but can be configured to work better with Berkeley DB in special situations.

In 7 the key/data pairs in v2's backing database is written to v1's backing database, after the data in v1 is truncated. Also true for line 8, where v1's key/data pairs written into v2 after data in v2 is truncated.

In line 10, almost all algorithm functions in C++ STL library can work with dbstl, because dbstl has standard iterators and containers, the default behaviors of dbstl containers and iterators follow C++ STL specifications. The exception to this fact is the "inplace_merge", "find_end" and "stable_sort" in the STL library of GCC compiler, these three functions don't work with dbstl correctly. Apart from them, all C++ STL algorithms are always applicable to dbstl.

Starting at line 14, dbstl containers and iterators have all methods that each corresponding C++ STL containers have, and each with identical default behaviors. So you can use dbstl just the same way you use C++ STL containers/iterators to access Berkeley DB.

In our next post...
Next up we'll dive even deeper into more advanced features of the dbstl API. For now if you'd like to read ahead the code is here.


Information about Berkeley DB products directly from the people who build them.


« June 2016