BerkeleyDB (http://www.sleepycat.com) is well suited to such an application. Unfortunately the perl module is really light on documentation. I'll provide a very quick example here but you'll really want to read the documentation on the database web site. Since the perl module is based on the C API you'll want to read the C API documentation and then just where it uses some C code, pretend it's perl code.

The one caveat is that I never use the tie interface. All it does is call the object oriented interface anyway so I save a method call and just use the database as it's designed to be used. I have an example of object oriented (though not using the CDB features) BerkeleyDB up at http://www.greentechnologist.org/tiger/unpack.pl and http://www.greentechnologist.org/tiger/graph.pl. The CDB features just "happen" if you enable them.

 use strict;
 use warnings;
 use BerkeleyDB;

 my $env = get_environment();
 
 my $db = BerkeleyDB::Btree->new (
     -Filename => 'my_file.db',
     -Flags    => DB_CREATE,
     -Env      => $env
 ) or die
 "Couldn't open database at my_file.db: $BerkeleyDB::Error";
 
 # the database now supports concurrant access. You'd
 # just open it in each thread and use it. See
 # http://www.sleepycat.com/docs/ref/cam/intro.html
 # for info on the concurrant system.

 # You can also do nested transactions and logging. See
 # http://www.sleepycat.com/docs/ref/transapp/intro.html
 # and continue next otherwise just read the docs from the
 # table of contents.

 sub get_environment {
     BerkeleyDB::Env->new (
         -Flags => DB_CREATE     |
                   DB_INIT_MPOOL |
                   DB_INIT_CDB
     ) or die
     "Couldn't initialize BerkeleyDB environment: $BerkeleyDB::Error";
 }
[download]

Update I should add that the SleepyCat documentation explicitly notes that BerkeleyDB's concurrant access modes work correctly across threads. I posted a code example for multi process access - your multi-threaded example should read similarly though there's no real reason you should need threading given your specified requirements.

Update I didn't know the perl module BerkeleyDB wasn't thread safe. The underlying library is. So if you're to follow my suggestion then probably you want multiple processes.

Fun Fun Fun in the Fluffy Chair