Re: multithreaded cache?

Discussion in 'Java' started by Silvio Bierman, May 15, 2012.

  1. On 05/15/2012 11:14 AM, bugbear 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



    The simplest approach is to wrap your cached values in an object and
    make all cache access go through two stages.

    Stage one is to lookup the wrapper in the cache, possibly inserting a
    new (empty) wrapper if not present.

    Stage two is to get a lock on the wrapper to get the actual cache value.
    If that is not present (or perhaps stale) then the thread owing the lock
    on the wrapper can recompute the value.

    If you cache values that are slow to compute this is usually the way to go.
    Silvio Bierman, May 15, 2012
    #1
    1. Advertising

  2. Silvio Bierman

    Roedy Green Guest

    On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman <>
    wrote, quoted or indirectly quoted someone who said :

    >The simplest approach is to wrap your cached values in an object and
    >make all cache access go through two stages.


    Where did you learn this?
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    Programmers love to create simplified replacements for HTML.
    They forget that the simplest language is the one you
    already know. They also forget that their simple little
    markup language will bit by bit become even more convoluted
    and complicated than HTML because of the unplanned way it grows.
    ..
    Roedy Green, May 15, 2012
    #2
    1. Advertising

  3. Silvio Bierman

    Daniel Pitts Guest

    On 5/15/12 3:57 PM, Roedy Green wrote:
    > On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    > wrote, quoted or indirectly quoted someone who said :
    >
    >> The simplest approach is to wrap your cached values in an object and
    >> make all cache access go through two stages.

    >
    > Where did you learn this?

    I think he meant "an easy efficient approach", rather than "the simplest".

    The simplest of course is a global lock for the cache.
    Daniel Pitts, May 16, 2012
    #3
  4. On 05/16/2012 12:57 AM, Roedy Green wrote:
    > On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    > wrote, quoted or indirectly quoted someone who said :
    >
    >> The simplest approach is to wrap your cached values in an object and
    >> make all cache access go through two stages.

    >
    > Where did you learn this?


    Why do you ask? Do you disagree?

    It is something I came up with the first time I encountered the same
    situation, probably many years ago.
    It is obvious you need to decouple key lookups/insertions, which are
    inherently cache-global, from value insertions/updates, which could be
    considered key-local.

    Eric and Daniel responded with more specific solutions that both match
    my general pattern.
    Silvio Bierman, May 16, 2012
    #4
  5. On 05/16/2012 01:13 AM, Daniel Pitts wrote:
    > On 5/15/12 3:57 PM, Roedy Green wrote:
    >> On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    >> wrote, quoted or indirectly quoted someone who said :
    >>
    >>> The simplest approach is to wrap your cached values in an object and
    >>> make all cache access go through two stages.

    >>
    >> Where did you learn this?

    > I think he meant "an easy efficient approach", rather than "the simplest".
    >
    > The simplest of course is a global lock for the cache.


    Yep, with "simplest" I meant the simplest way to get around the
    mentioned disadvantage of a global lock.
    Silvio Bierman, May 16, 2012
    #5
  6. Silvio Bierman

    Eric Sosman Guest

    On 5/15/2012 7:19 PM, Silvio Bierman wrote:
    > On 05/16/2012 12:57 AM, Roedy Green wrote:
    >> On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    >> wrote, quoted or indirectly quoted someone who said :
    >>
    >>> The simplest approach is to wrap your cached values in an object and
    >>> make all cache access go through two stages.

    >>
    >> Where did you learn this?

    >
    > Why do you ask? Do you disagree?
    >
    > It is something I came up with the first time I encountered the same
    > situation, probably many years ago.
    > It is obvious you need to decouple key lookups/insertions, which are
    > inherently cache-global, from value insertions/updates, which could be
    > considered key-local.
    >
    > Eric and Daniel responded with more specific solutions that both match
    > my general pattern.


    Three independent votes for one pattern: What we have here is a

    M A N D A T E !!!

    --
    Eric Sosman
    d
    Eric Sosman, May 16, 2012
    #6
  7. On 12-05-15 09:26 PM, Eric Sosman wrote:
    > On 5/15/2012 7:19 PM, Silvio Bierman wrote:
    >> On 05/16/2012 12:57 AM, Roedy Green wrote:
    >>> On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    >>> wrote, quoted or indirectly quoted someone who said :
    >>>
    >>>> The simplest approach is to wrap your cached values in an object and
    >>>> make all cache access go through two stages.
    >>>
    >>> Where did you learn this?

    >>
    >> Why do you ask? Do you disagree?
    >>
    >> It is something I came up with the first time I encountered the same
    >> situation, probably many years ago.
    >> It is obvious you need to decouple key lookups/insertions, which are
    >> inherently cache-global, from value insertions/updates, which could be
    >> considered key-local.
    >>
    >> Eric and Daniel responded with more specific solutions that both match
    >> my general pattern.

    >
    > Three independent votes for one pattern: What we have here is a
    >
    > M A N D A T E !!!
    >

    Dunno about that, but I did go out and buy a lottery ticket...

    AHS
    --
    Never interrupt your enemy when he is making a mistake.
    --Napoleon
    Arved Sandstrom, May 16, 2012
    #7
  8. On 05/16/2012 02:26 AM, Eric Sosman wrote:
    > On 5/15/2012 7:19 PM, Silvio Bierman wrote:
    >> On 05/16/2012 12:57 AM, Roedy Green wrote:
    >>> On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    >>> wrote, quoted or indirectly quoted someone who said :
    >>>
    >>>> The simplest approach is to wrap your cached values in an object and
    >>>> make all cache access go through two stages.
    >>>
    >>> Where did you learn this?

    >>
    >> Why do you ask? Do you disagree?
    >>
    >> It is something I came up with the first time I encountered the same
    >> situation, probably many years ago.
    >> It is obvious you need to decouple key lookups/insertions, which are
    >> inherently cache-global, from value insertions/updates, which could be
    >> considered key-local.
    >>
    >> Eric and Daniel responded with more specific solutions that both match
    >> my general pattern.

    >
    > Three independent votes for one pattern: What we have here is a
    >
    > M A N D A T E !!!
    >


    Let's hope this is inspires the Greeks...
    Silvio Bierman, May 16, 2012
    #8
  9. Silvio Bierman

    Roedy Green Guest

    On Wed, 16 May 2012 01:19:07 +0200, Silvio Bierman <>
    wrote, quoted or indirectly quoted someone who said :

    >
    >Why do you ask? Do you disagree?


    No. I thought there were two possibilities. There is a some great
    book you read or website that I should reference in the Java glossary,
    or that you figured this out by exhaustive experiment, in which case I
    should consider worship.
    --
    Roedy Green Canadian Mind Products
    http://mindprod.com
    Plants" with "leaves" no more efficient than today’s solar cells
    could out-compete real plants, crowding the biosphere with an
    inedible foliage. Tough omnivorous "bacteria" could out-compete
    real bacteria: They could spread like blowing pollen, replicate
    swiftly, and reduce the biosphere to dust in a matter of days.
    Dangerous replicators could easily be too tough, small, and
    rapidly spreading to stop -- at least if we make no preparation.
    We have trouble enough controlling viruses and fruit flies.
    ~ Eric Drexler (born: 1955-04-25 age: 57)
    Engines of Creation: The Coming Era of Nanotechnology.
    ..
    Roedy Green, May 17, 2012
    #9
  10. On 05/17/2012 07:03 AM, Roedy Green wrote:
    > On Wed, 16 May 2012 01:19:07 +0200, Silvio Bierman<>
    > wrote, quoted or indirectly quoted someone who said :
    >
    >>
    >> Why do you ask? Do you disagree?

    >
    > No. I thought there were two possibilities. There is a some great
    > book you read or website that I should reference in the Java glossary,
    > or that you figured this out by exhaustive experiment, in which case I
    > should consider worship.


    Actually, exhaustive experiment would be a huge overstatement. It was
    the second thing that came up after I immediately discarded the first
    impulse of a global lock.

    Some people would call that premature optimization...
    Silvio Bierman, May 21, 2012
    #10
  11. "Silvio Bierman" <> wrote in message
    news:4fb35691$0$6944$4all.nl...
    > On 05/16/2012 02:26 AM, Eric Sosman wrote:
    >> On 5/15/2012 7:19 PM, Silvio Bierman wrote:
    >>> On 05/16/2012 12:57 AM, Roedy Green wrote:
    >>>> On Tue, 15 May 2012 11:41:06 +0200, Silvio Bierman<>
    >>>> wrote, quoted or indirectly quoted someone who said :
    >>>>
    >>>>> The simplest approach is to wrap your cached values in an object and
    >>>>> make all cache access go through two stages.
    >>>>
    >>>> Where did you learn this?
    >>>
    >>> Why do you ask? Do you disagree?
    >>>
    >>> It is something I came up with the first time I encountered the same
    >>> situation, probably many years ago.
    >>> It is obvious you need to decouple key lookups/insertions, which are
    >>> inherently cache-global, from value insertions/updates, which could be
    >>> considered key-local.
    >>>
    >>> Eric and Daniel responded with more specific solutions that both match
    >>> my general pattern.

    >>
    >> Three independent votes for one pattern: What we have here is a
    >>
    >> M A N D A T E !!!
    >>

    >
    > Let's hope this is inspires the Greeks...


    They've been dating men for millenia.
    Mike Schilling, May 26, 2012
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jeff Nokes

    Cache::Cache Stale Segments

    Jeff Nokes, Sep 30, 2003, in forum: Perl
    Replies:
    0
    Views:
    570
    Jeff Nokes
    Sep 30, 2003
  2. DesignerX

    Page.Cache vs HttpContext.Current.Cache

    DesignerX, Jan 20, 2004, in forum: ASP .Net
    Replies:
    5
    Views:
    8,242
    vMike
    Jan 20, 2004
  3. Eric Sosman

    Re: multithreaded cache?

    Eric Sosman, May 15, 2012, in forum: Java
    Replies:
    0
    Views:
    466
    Eric Sosman
    May 15, 2012
  4. Robert Klemme

    Re: multithreaded cache?

    Robert Klemme, May 17, 2012, in forum: Java
    Replies:
    20
    Views:
    666
    Robert Klemme
    May 25, 2012
  5. Kevin McMurtrie

    Re: multithreaded cache?

    Kevin McMurtrie, May 25, 2012, in forum: Java
    Replies:
    3
    Views:
    320
    Robert Klemme
    Jun 2, 2012
Loading...

Share This Page