(This problem may apply to other cache storage solutions as well.)

The expiration purge code iterates and loads the entire database to find expired entries, which is highly inefficient.

protected void purgeInternal() throws CacheLoaderException {
try {
Iterator<Map.Entry<Object, InternalCacheEntry>> i = cacheMap.entrySet().iterator();
while (i.hasNext())

Should maintain a separate time -> key association. BDB-JE has a "StoredSortedMap", so this should be straightforward to use. (See how JDBM handles eviction.)