Re: multithreaded cache?

In article <zsWdnVufD87Egy_SnZ2dnUVZ7oednZ2d@xxxxxxxxxxxxxxxx>,
bugbear <bugbear@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

I'm using various Apache Commons Maps as a
multithread cache, protected using
ReentrantReadWriteLock, so that getting() uses a read lock,
and putting() uses a write lock.

But I've got an issue; in the
case of a cache miss (protected by a read lock),
the required value is acquired using the "underlying function"
that the cache is over; this value is then put() into
the cache (protected by a write lock)

This is all perfectly thread safe, and gives
correct results.

However, if the underlying function is slow
and/or resource hungry (consider cacheing
a ray traced image!) many threads can
end up calling the real function (second
and subsequent threads to the first get a miss
during the first threads call to the underlying function).

"obviously..." what I want is for only
the thread that FIRST has a cache miss
calls the underlying function, whilst other
threads (for the same key) wait.

This seems "obvious" enough that I'm guessing
there's a standard solution.

Googling led me to several "heavy" libraries;

This appears more a locking/cacheing issue
than a Java issue, although my implementation
is in Java.

Can anyone (please) point me at a
canonical solution/implementation?

BugBear

Ha, this is an interview question that I use.

What you need is row level locking for the cache load.

Step 1)
Use synchronized operations to map your key to a value; creating an
uninitialized value in the map if needed. Use whatever tech you want.
A synchronized block on a HashMap is simplest and performs the fastest
on 1 or 2 core systems. A ConcurrentHashMap sometimes performs better
with 4+ core systems.

Step 2)
Synchronize on the value. Initialize it if needed.


Step 1 blocks all cache access for only for a very short moment to make
sure that a key always has a value. Step 2 blocks access independently
for each cache value to make sure that it is loaded. It will perform
well for continuous use by several CPU cores. Google has some high
concurrency Maps that aren't too bad either.

In the 16 core range you'll find that any kind of exclusive lock causes
stalls where threads suspend while holding locks, causing a backlog that
reinforces itself. A concurrency expert can fix that using complex
Compare-And-Swap designs. In the 32+ core range you'll sometimes find
that harmless race conditions are better than multiple threads
frequently writing to the same memory page.
--
I will not see posts from Google because I must filter them as spam
.

Relevant Pages

  • Re: Problem with BDC "View Profile" link
    ... but it seems to "short circuit" while it is reading the BDC cache. ... 71qj High Acquired Read lock on LobSystemInstance cache ... 71qj High Acquired Read lock on MethodInstance cache ... 71qj High Acquired Read lock on TypeDescriptor cache ...
    (microsoft.public.sharepoint.portalserver.development)
  • Re: multithreaded cache?
    ... ReentrantReadWriteLock, so that gettinguses a read lock, ... case of a cache miss, ... if the underlying function is slow ... if (cachedFuture!= null) { ...
    (comp.lang.java.programmer)
  • Re: Fenceless atomic RMW
    ... let's assume that the cache line is already in cache in E state ... cache lock or address lock (or even a bus lock for ... So, the question is, how do you do the load part of the atomic RMWS? ... draining the store buffer so that the RMW is sequentially consistentg ...
    (comp.arch)
  • Re: How to free a locked object?
    ... timeout occurred while waiting to lock object xxx' ... Upon checking the v$session_wait, i found "latch: cache ... 'DR','Distributed Recovery', ... 'NA','Library Cache Pin', ...
    (comp.databases.oracle.server)
  • Re: ASP requests and locking
    ... Typically you would cache immutable content. ... There is no need to lock ... How many properties will you reading per request and will they ... Anthony Jones - MVP ASP/ASP.NET ...
    (microsoft.public.dotnet.framework.aspnet)