I'm working on a project that is attempting to create a cache using JE
as its back-end data store.

What I'm trying to do is limit the number of entries that can exist in
the "cache" to a specified amount. Once the cache grows beyond its
limit, old entries should be evicted in an LRU (approximately LRU is
fine) fashion. So far I've been using the collections API
(specifically a StoredMap).

I'm having trouble in a couple of areas. One problem that I've
encountered is there doesn't seem to be any efficient way to determine
the number of entries in a database without keeping track of it myself.
StoredMap.size() appears to simply iterate over all elements using a
cursor. Knowing the number of entries is, of course, essential to
knowing when to perform evictions.

The second problem is that of managing cache entries in some kind of
ordered list, so old entries can be quickly found and removed once the
cache has grown too large (i.e. beyond a specified threshold).
Ideally, my goal is to create a persistent LinkedHashMap using access
ordering, but I don't have a good way of maintaining a linked list in
the database.

Alternatively, I wouldn't mind taking another approach where evictions
occur once the database size on disk has grown too large. If there is
a good way of determining that size, that would potentially help with
my first problem.

Any suggestions are appreciated.

Patrick

Hello Patrick,

JE does not maintain a record count per database, since that would
significantly reduce concurrency. In JE 3.0.12 and earlier the fastest
way to obtain a count is to traverse the database using
READ_UNCOMMITTED, which is what our Map/Collection.size does. We are
working on ways to get a faster count for future releases.

Can you treat the database as a queue, always appending to one end in a
key sequence and always deleting from the other end? If so, you can
subtract the first and last key values to determine the size.

It is hard to give more advice without knowing what kind of algorithm
you use for removing items from the cache -- are you using aging or
something else?

Mark

Hello Mark,

Thank you for your great advice on how to determine the database size
using sequences. I can understand how it wouldn't be exact, as records
may be updated or removed, thus creating holes in the sequence
elements, but I think it gives a close enough approximation for my
caching module. Your technique also provides great performance.

The module works as a FIFO cache. Elements get a sequence number when
they are inserted or updated, i.e. whenever StoredMap.put is called.
When the cache is determined to be over its size limit, the cache
starts removing entries in the order of their sequence numbers.
Basically, it works exactly like your suggestion in the previous post.
This isn't quite the LRU cache that I originally hoped for, but I
cannot see a way to make the cache LRU without performing a database
write every time an element is retrieved via StoredMap.get. For the
applications that this module will be used in, that seems like more
overhead than it's worth.

Thanks again for all of your help. It's very much appreciated.

Patrick

Mike,

You're welcome. It's great to hear that worked for you.

You're correct that to use an LRU on a large set of records, you would
need to write the records (or write to some database) whenever a record
is accessed.

Good luck with your project!

Mark