Wireless Networking & Berkeley DB

WNG currently runs on AIX, IBM's UNIX implementation. Motorola plans to port WNG to Solaris and Linux, and possibly to NT or Windows 2000. An important factor in the selection of platform (hardware and OS) is fault tolerance, including the ability to do a hot-swap of redundant components such as disk drives and CPU boards. Both AIX and upcoming releases of Linux have this capability.

WNG originally kept its configuration information in a set of flat files. Each task would read this information at startup and create its own ad hoc internal database. At shutdown, each task would write any updated information back to the configuration files. When a system crash occurred, live data was lost. Also, the lack of synchronization between the different copies of what was essentially the same data was an ongoing problem. System startup and shutdown was very slow, usually about 10 minutes for each.

Since our uptime goal is 99.999 percent (or about five minutes of downtime per year), this was clearly unacceptable. Consequently, we decided to find a robust third-party database that recovered fast from system crashes. One of our formal system tests is to subject the WNG system to a full-rated load, then pull the power cord. To work in this system, the database package we chose had to be able to successfully recover after the power was restored and the machine rebooted.

Since the system has to be running 100 percent of the time, it cannot be taken down to perform any tuning, reorganizing, or reoptimizing of the database; for that matter, performing any of these functions is completely impractical since there is no operator to perform these or any other offline database maintenance. Therefore, we required that online database backups be done while the system was running.

The data to be stored in the database is 25 MB in size: 2 MB for the main data and 23 MB for the IP datagram header compression context storage. The main access key is always the permanent hardware ID of the mobile radio. The one secondary key is the current IP address associated with the mobile radio. This address usually changes at the beginning of a work shift (for instance, once every eight hours). Complex queries are unnecessary; thus, Motorola did not consider a SQL database beneficial for this application.

What we wanted was a database with a conceptually simple operation and a simple programming interface that would be easy to learn by the programming staff. Also, the database had to fit into the existing architecture (both design and code) of the WNG system. Things such as adding embedded SQL, or handling retries for deadlock resolution (for locking and transactions), to the existing application-level code was out of the question.

Choosing a Database

With this in mind, we performed an exhaustive search to find the appropriate database for the WNG. Several commercial databases were immediately discarded from the beginning due to their cost.

For testing purposes, we created a small prototype that did some typical WNG system database operations; for example, look-up by hardware address, look-up by IP address, read/modify/write data records, and modify IP address (the secondary key). What we discovered was that Berkeley DB, an embedded database engine distributed by Sleepycat Software (http://www.sleepycat.com/), was 20 times faster than the others. This speed difference was attributed to Berkeley DB's unusual combination of disk-resident and embedded database models. It has the operational speed of a main-memory database, the startup and shutdown speed of a disk-resident database, and does not have the overhead of client/server inter-process communication.

Other aspects of Berkeley DB that we liked included that it is open source, and can be downloaded free of charge from the Sleepycat web site. (Sleepycat makes its money by licensing Berkeley DB to proprietary vendors and selling support and services.) Furthermore, you can easily embed Berkeley DB in any application that requires high-performance concurrent data storage and retrieval. Designed to be system independent (it runs most UNIX or UNIX-like systems, Embedix, QNX, VxWorks, and Windows 95/98/NT/2000), Berkeley DB has programmable interfaces for C, C++, Java, Perl, Python, and Tcl, which give a "dbm-style" record management for ease of use. Data is stored as key/value pairs; the keys can then be used to locate required items. Berkeley DB transactions pass the acid test of databases by fulfilling the requirements of being atomic, consistent, isolatable, and durable.

Other features of the Berkeley DB that Motorola considered essential in making it our choice for the WNG include:

• Low overhead concurrent access.
• Performance close to that of a straight main-memory database, with the flexibility of a disk-resident database.

• The ability to perform "live" backups while the system is running.

• Good performance can be maintained without tuning.

• The presence of the database is invisible to the WNG end user.

Database administration, maintenance, and tuning are unnecessary. The few special tasks that are required (backups and crash recovery, for instance) can be easily handled via UNIX scripts.

Nevertheless, Berkeley DB also presented some problems:

• User documentation for Version 2.7.7 was not as good then as it is now; the current Version 3.3 is a big improvement. At that time, critical details were either implied or left out completely. Fortunately, this is no longer an issue.
• Failure to get training from the vendor. Training would have filled in for the documentation shortcomings.

• Secondary keys were not available so we had to implement this option, but found it an easy task. In subsequent versions of WNG, we decided adding it ourselves had been for the best. The number of IP addresses per mobile radio was expanded from 1 to 16, and a general-purpose secondary key feature would most likely have had a greater impact on performance than Motorola's specialized, tailored implementation.

• Some bugs were found during stress testing, but having the source code made it fairly easy to fix them. Even if we had not had the software, this would not have been a big problem since all reported bugs were fixed by Sleepycat Software in a timely manner.

• All programs must be shut down to recover from a single program crashing.

• No built-in method to detect a program crash is available.

• No built-in method to discover all programs with a database open is available.

The last three items are actually trade-off factors since Berkeley DB is linked with each application and runs in the same address space as the application. A client/server model would not have these problems, but would have slower performance.

Incorporating Berkeley DB Into WNG

We chose to use a mid-level API for the database, which would handle all necessary details and call low-level Berkeley DB routines. Cursors, locking, transactions, and the like are all handled internally within the API and are invisible to the application-level code. Application-level programs call specialized API routines (open_mobile_database, close_mobile_database, get_mobile_by_ipaddr for readonly/update, update_ipaddr_secondary_key). Listing One is an example of database API code in WNG — a function that deletes a mobile record and any secondary key records for the IP address of that mobile radio (the macro SSZ(str, mbr) returns the byte offset of member mbr in the struct 'str').

The API uses an explicit high-level lock (very coarse grained) to minimize lock contention for updates that are known to be safe. A record that is updated in place (that is, without changing its size) will not cause any changes in the underlying internal btree structures of the database, so these can safely be done without using transactions (with the attendant overhead).

We also added a callback routine for errors reported by Berkeley DB, and code to hide multiple secondary keys in the same database, by prefixing the target key with a type field. Doing this was only necessary because we were using Version 2.7.7. With Berkeley DB 3.x, this can be done directly by creating multiple subdatabases in the same physical database file.

Another thing we had to add was code to handle restart (abort/retry) of transactions when they deadlocked, because the application programs were not designed to do this.

WNG has two categories of databases — one that includes databases that have small records of 100 to 200 bytes (such as the mobile radio and the user), and another that contains the IP header compression context DB that has much larger records of 2400 bytes. This created problems in the memory pool (the database cache) because the context records kicked out pages of the other DBs.

Also, due to the nature of the access patterns, we wanted to be able to tune the memory pools independently and set the main pool for a high hit rate (everything fits in 2 MB). A lower hit rate on the context database is acceptable, so another 5 MB was dedicated to the context pool, even though the database occupied 50 MB. In this case, access patterns still gave an acceptably high hit rate. Also, the context page size was set to a rather large 16 KB for efficiency, with a low 4 KB for the main pool. Using a single pool with large pages would negatively impact the locking performance of databases in the main pool, since the granularity of locks is at the page level.

One problem that we encountered on implementation was some AIX nastiness that involves a nonstandard implementation of shared memory regions mapped by the system routine mmap: The OS gratuitously writes dirty pages to disk using the syncd function, resulting in tremendous overhead. The technical support people at Sleepycat helped us identify and solve this problem. The solution was to change the Berkeley DB operation from mmap, which is useful only for a single process, to shmem (shared memory), which is more efficient for multiprocessing. Fortunately, the Berkeley DB can use either method for sharing memory between processes.

Berkeley DB Recovery

If, during normal operation, one of the processes using the database terminates unexpectedly, the other processes need to close their own connections to the database so that recovery can run. Since Berkeley DB runs directly in the address space of the embedding application, it is possible for an application to die holding locks that can't otherwise be released. Processes may terminate abnormally for a number of reasons; for example, because the system loses power.

Motorola uses a separate process, called db_demon, to watch for problems and to recover when necessary. db_demon is the first process to start under WNG. It performs recovery at startup and is responsible for taking database checkpoints, cleaning up obsolete transaction log files, and monitoring all the other WNG processes.

Every time a WNG process opens a database, it writes a file to the filesystem that includes its process name (the process ID, under UNIX) and the name of the database on which it is working. The db_demon process runs continually and checks at regular intervals for any such files. Whenever it finds one, it checks the process to be sure that it is still running. On UNIX, this is easy to do by calling kill(0) with the process ID. If the system call reports an error, then the process has terminated.

If a process has terminated, then db_demon notifies all the other processes and they must shut down. Once they have done so, db_demon runs Berkeley DB's recovery service to be sure that the database contents are correct and that no lingering shared state survives from the failed process. db_demon creates a semaphore file, named "recovery_in_progress," to signal to all other processes that they are not permitted to open databases yet. All the WNG processes check for this filename before opening a database, and wait until it disappears if they find it.

At normal system shutdown, all processes close their databases and WNG checkpoints the database. Actually, for performance reasons, it writes two checkpoints. This guarantees that the database state is correct on disk, and the recovery process at startup will run quickly.

Conclusion

The Berkeley DB served Motorola's purposes well in the WNG. It was easily implemented with few problems. Some problems that did occur were a direct result of lack of documentation, a shortcoming that has since been corrected. The Berkeley DB has proven itself to be a robust and stable database for a wireless network.

DDJ

Listing One

/************** The layout for secondary keys ****************/
/* secondary key = ipaddr */
struct mob_ip_sec_key {
   unsigned long mis_sec_type;  /* The secondary type & flag. */
   unsigned long mis_ipaddr;    /* The ipaddr */
};
int mb_delete_mobile(int dcb_han, unsigned long lli)
{
   static char fn[] = "mb_delete_mobile";
   int st;
   int st1;
   DB_TXN *tid = NULL;          /* The transaction control block */
   int rtt = 0;                 /* Transaction retry count */
   struct mob_ip_sec_key msk;   /* The secondary key buffer */
   DBT mi_data_dbt = {0};       /* The data descriptor for mr_ipaddr.     */
   DBT ipkey_dbt = {0};         /* The key descriptor for the ip sec key. */
   DBT key_dbt = {0};           /* Key for the LLI */
   DBC *csr_mob = NULL;         /* cursor for the mobile (LLI) record.    */
   unsigned long mobs_ipaddr;   /* The ipaddr of the mobile (lli) */

   LOCK_SET(DB_LOCK_WRITE);     /* Set the high-level lock. */
   if (0) {                     /* Abort and retry */
      retry:;                   /* Repeat the aborted transaction */
      if (++rtt < 10 || (rtt % 100) == 1)
    printf("retry/txn_abort %d.\n", rtt);
      csr_mob->c_close(csr_mob);
      txn_abort(tid);
   }
   /* Begin a transaction block.  Either all or none of the updates 
    * will be written to the database. */
   st = txn_begin(dcb.dc_dbenv, NULL, &tid, 0);
   if (st != 0) {
      (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st); /* user's error func */
      errno = st;
      dprintf("%s: txn_begin error st: %d", dcb.dc_progname, st);
      LOCK_RELEASE();
      return (-2);
   }
   /* Acquire a cursor for the mobile record. */
   st = dcb.dc_dbp->cursor(dcb.dc_dbp, tid, &csr_mob, 0);
   if (st != 0) {   /* NZ means some kind of error */
      (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st);
      dprintf("cursor_open: %d\n", st);
      txn_abort(tid);
      LOCK_RELEASE();
      errno = st;
      return(-1);
   }
   /* Read the secondary key value(s), and delete the secondary key(s). */
   msk.mis_sec_type = SK_IPADDR_MAGIC;
   key_dbt.data = &lli; /* Set up the key descriptor */
   key_dbt.size = sizeof(lli);
   ipkey_dbt.data = &msk;   /* Set up the ip secondary key descriptor */
   ipkey_dbt.size = sizeof(msk);
   /* Set up the data descriptor, to only access (read/write) the
    * ipaddr field of the mobile's (LLI) record.  */
   mi_data_dbt.doff = SSZ(struct mob_keys, mr_ipaddr);
  mi_data_dbt.ulen = mi_data_dbt.dlen = sizeof(mobs_ipaddr);
   mi_data_dbt.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
   mi_data_dbt.data = &mobs_ipaddr;
   st = csr_mob->c_get(csr_mob, &key_dbt, &mi_data_dbt, DB_SET | DB_RMW);
   dprintf("mb_delete_mob: c_get rtn: %d\n", st);
   if (st == DB_LOCK_DEADLOCK)
      goto retry;
   if (st != 0) {       /* NZ means some kind of error */
      if (st != DB_NOTFOUND)
     (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st);
      dprintf("mb_delete_mob: getcurrent: %d\n", st);
      st1 = csr_mob->c_close(csr_mob);  /* Discard the cursor. */
      txn_abort(tid);
      LOCK_RELEASE();
      errno = st;
      return ((st == DB_NOTFOUND) ? 0 : -2);
   }
   dprintf("mb_delete_mob: del_key: %08x\n", *(unsigned long *)key_dbt.data);
   dprintf("mb_delete_mob: has current ipaddr: %x\n", mobs_ipaddr);

   st = csr_mob->c_del(csr_mob, 0);
   dprintf("mb_delete_mob: c_del rtn: %d\n", st);
   if (st == DB_LOCK_DEADLOCK)
      goto retry;
   if (st != 0)     /* NZ means some kind of error */
      (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st);

   /*** Delete the ipaddr_sec_key record ***/
   if (mobs_ipaddr != 0) {
      msk.mis_ipaddr = mobs_ipaddr;
      st1 = dcb.dc_dbp->del(dcb.dc_dbp, tid, &ipkey_dbt, 0);
      dprintf("mb_delete_mob: del old sec key. st: %d\n", st);
      if (st == DB_LOCK_DEADLOCK)
     goto retry;
      if (st1 != 0)
     (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st1);
   }
   st1 = csr_mob->c_close(csr_mob); /* Discard the cursor. */
   txn_commit(tid, 0);
   if (st1 != 0)
      (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st);
   LOCK_RELEASE();
   if (st == 0)
      return (1);
   (*dcb.dc_db_err_rtn)(fn, dcb.dc_filename, st);
   if (st > 0)
      return (-st);
   return (st);
}

Back to Article