As an alternative to the suggestions above, you could also consider using a DBM file solution. Specifically the Berkeley DB from SleepyCat. It operates in the key/value system you already use and scales well.

There is a CPAN module here so YMMV (look at the tests).