FooTreeCache

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

FooTreeCache

Hanson Char
Hi,

For some reason I need to cache a large but bounded number of of items
in a SortedMap and be able to preload the cache concurrently (ie
without significantly impacting the handling of service requests.)
Actually the closes thing I need is probably ConcurrentSkipListMap in
Java 6, but suffice to say I can't use it yet.  Below is a much
simplified version of such hypothetical cache.

The basic idea is to combine the use of
1) Read/Write Lock;
2) volatile; and
3) AtomicReference

to maximize concurrency.

Can someone spot any significant concurrency issue with it ?

(I know there is ConcurrentHashMap, but let's say for some reason I
need an internal SortedMap and not just Map.)

Many thanks!

Hanson Char

/**
  * A simple concurrent cache that, for some reasons, needs to have a
SortedMap internally.
 */
@ThreadSafe
public class FooTreeCache {
    /** Uses a non-synchronized map for optimal performance both for
read and write. */
    @GuardedBy("rwLock")
    private static volatile SortedMap<String,String> sortedMap = new
TreeMap<String,String>();
    private static final Lock readLock;
    private static final Lock writeLock;
    static {
        ReadWriteLock rwLock = new ReentrantReadWriteLock();
        readLock = rwLock.readLock();
        writeLock = rwLock.writeLock();
    }
    /** Atomic Cache status reference. */
    private static final AtomicReference<Status> status = new
AtomicReference<Status>(Status.INIT);

    private FooTreeCache() {
    }

    /**
     * Cache Status.
     *
     * Valid state transitions:
     * INIT       -> TRANSIENT
     * TRANSIENT  -> PRE_LOADED
     * PRE_LOADED -> TRANSIENT
     * TRANSIENT  -> INIT
     */
    public static enum Status {
        INIT,
        TRANSIENT,
        PRE_LOADED;
    }

    /** Preloads from db. */
    public static void preload() {
        if (!status.compareAndSet(Status.INIT, Status.TRANSIENT))
        {   // already loading or preloaded by another thread.
            return;
        }
        Thread t = new Thread("FooTreeCachePreLoader")
        {
            @Override
            public void run()
            {
                Collection<Map.Entry<String,String>> col = // ...
lenghty IO to load or whatever
                SortedMap<String,String> temp = new TreeMap<String,String>();
                for (Map.Entry<String,String> ccbr : col)
                    temp.put(ccbr.getKey(), ccbr.getValue());
                // Replace the cache with a preloaded one.
                sortedMap = temp;
                status.set(Status.PRE_LOADED);
            }
        };
        t.setDaemon(true);
        t.start();
    }

    public static String get(int key)
    {
        readLock.lock();
        try {
            return sortedMap.get(key);
        } finally {
            readLock.unlock();
        }
    }

    public static void put(String key, String value)
    {
        writeLock.lock();
        try {
            sortedMap.put(key, value);
        } finally {
            writeLock.unlock();
        }
    }

    public static int size() {
        readLock.lock();
        try {
            return sortedMap.size();
        } finally {
            readLock.unlock();
        }
    }

    public static void clear() {
        if (!status.compareAndSet(Status.PRE_LOADED, Status.TRANSIENT))
            if (!status.compareAndSet(Status.INIT, Status.TRANSIENT))
                return;
        SortedMap<String,String> temp = sortedMap;
        // Replace the cache with an empty one.
        sortedMap = new TreeMap<String,String>();
        status.set(Status.INIT);
        // Clear the old one for better garbage collection ?
        temp.clear();
    }
}
// End
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Kasper Nielsen-2
Hanson Char wrote:
> Hi,
>
> For some reason I need to cache a large but bounded number of of items
> in a SortedMap and be able to preload the cache concurrently (ie
> without significantly impacting the handling of service requests.)
> Actually the closes thing I need is probably ConcurrentSkipListMap in
> Java 6, but suffice to say I can't use it yet.

The source is released to the public domain, so why don't use it? I
think ConcurrentSkipListMap will only need minor changes to compile on
5.0. (missing interfaces etc.)

- Kasper
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
Yes, thanks for the pointer.  David Holmes also made the same point.
Will look into replacing the use of the ReadWriteLock+SortedMap with a
ConcurrentSkipListMap.

However, the need for the volatile and AtomicReference in FooTreeCache
will still hold.

Any problem anyone can spot ?

Hanson Char

On 8/25/06, Kasper Nielsen <[hidden email]> wrote:

> Hanson Char wrote:
> > Hi,
> >
> > For some reason I need to cache a large but bounded number of of items
> > in a SortedMap and be able to preload the cache concurrently (ie
> > without significantly impacting the handling of service requests.)
> > Actually the closes thing I need is probably ConcurrentSkipListMap in
> > Java 6, but suffice to say I can't use it yet.
>
> The source is released to the public domain, so why don't use it? I
> think ConcurrentSkipListMap will only need minor changes to compile on
> 5.0. (missing interfaces etc.)
>
> - Kasper
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
When I look at the source code in Java 6, I see something like:

/*
 * @(#)ConcurrentSkipListMap.java   1.3 05/11/17
 *
 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

I thought the source code of ConcurrentSkipListMap is in the public
domain.  Does this header comment mean anything ?

Hanson Char

> > The source is released to the public domain, so why don't use it? I
> > think ConcurrentSkipListMap will only need minor changes to compile on
> > 5.0. (missing interfaces etc.)
> >
> > - Kasper
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Joe Bowbeer
On 8/25/06, Hanson Char <[hidden email]> wrote:

> When I look at the source code in Java 6, I see something like:
>
> /*
>  * @(#)ConcurrentSkipListMap.java   1.3 05/11/17
>  *
>  * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
>  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
>  */
>
> I thought the source code of ConcurrentSkipListMap is in the public
> domain.  Does this header comment mean anything ?
>

The source at the link below is in the public domain:

http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

--Joe
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Gregg Wonderly-3
Joe Bowbeer wrote:
> The source at the link below is in the public domain:
>
> http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/
>
> /*
>  * Written by Doug Lea with assistance from members of JCP JSR-166
>  * Expert Group and released to the public domain, as explained at
>  * http://creativecommons.org/licenses/publicdomain
>  */

There are some dependencies to compile that class which seem to be Sun
proprietary labeled.

Gregg Wonderly
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
In reply to this post by Kasper Nielsen-2
Just in case anyone is interested in using ConcurrentSkipListMap
immediately in Java 5 (ie without Java 6), it's available at:

http://beanlib.sourceforge.net/3.2.2/api/net/sf/beanlib/util/concurrent/ConcurrentSkipListMap.html

Hanson

> The source is released to the public domain, so why don't use it? I
> think ConcurrentSkipListMap will only need minor changes to compile on
> 5.0. (missing interfaces etc.)
>
> - Kasper
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Doug Lea
In reply to this post by Gregg Wonderly-3
Gregg Wonderly wrote:
> J
> There are some dependencies to compile that class which seem to be Sun
> proprietary labeled.
>

All the ones you need to actually make ConcurrentSkipList{Map, Set}
minimally compilable can be taken from the jsr166x version of this class.
(Mostly, just local versions of the little AbstractMap utility
classes that should have been in Tiger/Java5 but weren't.)

Sorry that we've put a low priority on meshing the initial jsr166x
versions with the final Java 6 versions. Someone once sent in
a partial reconciliation, but that was before final Java 6 API
was settled. Volunteers would be welcome.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Doug Lea
In reply to this post by Hanson Char
Hanson Char wrote:
> Just in case anyone is interested in using ConcurrentSkipListMap
> immediately in Java 5 (ie without Java 6), it's available at:
>
> http://beanlib.sourceforge.net/3.2.2/api/net/sf/beanlib/util/concurrent/ConcurrentSkipListMap.html
>

Great; thanks!
I should have waited ten more seconds before sending out my
last reply :-)

-Doug

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
In reply to this post by Doug Lea
Just curious.  Why is it that all the classes in jsr166x exist in Java
6 beta, except the ConcurrentLinkedDeque ?

Hanson

On 8/26/06, Doug Lea <[hidden email]> wrote:

> Gregg Wonderly wrote:
> > J
> > There are some dependencies to compile that class which seem to be Sun
> > proprietary labeled.
> >
>
> All the ones you need to actually make ConcurrentSkipList{Map, Set}
> minimally compilable can be taken from the jsr166x version of this class.
> (Mostly, just local versions of the little AbstractMap utility
> classes that should have been in Tiger/Java5 but weren't.)
>
> Sorry that we've put a low priority on meshing the initial jsr166x
> versions with the final Java 6 versions. Someone once sent in
> a partial reconciliation, but that was before final Java 6 API
> was settled. Volunteers would be welcome.
>
> -Doug
> _______________________________________________
> Concurrency-interest mailing list
> [hidden email]
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
It seems java.util.Deque has an extra method than jsr166x.Deque:

    Iterator<E> descendingIterator();

In jsr166x.ConcurrentLinkedDeque, there exists the implementation for the method

    public Iterator<E> iterator();

However, there is no existing implementation for the method
"descendingIterator".

If one were to provide the missing implementation in
jsr166x.ConcurrentLinkedDeque, would it be something like the one
given below ?

Hanson

    public Iterator<E> descendingIterator() {
        return new CLDDescendingIterator();
    }

    final class CLDDescendingIterator implements Iterator<E>
    {
        Node<E> last;
        Node<E> next = trailer.back();

        public boolean hasNext() {
            return next != null;
        }

        public E next() {
            Node<E> l = last = next;
            if (l == null)
                throw new NoSuchElementException();
            next = next.back();
            return l.element;
        }

        public void remove() {
            Node<E> l = last;
            if (l == null)
                throw new IllegalStateException();
            while (!l.delete() && !l.isDeleted())
                ;
        }
    }

On 8/26/06, Hanson Char <[hidden email]> wrote:
> Just curious.  Why is it that all the classes in jsr166x exist in Java
> 6 beta, except the ConcurrentLinkedDeque ?
>
> Hanson
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
Everything classes of jsr166x are now included and "augmented" with
the source from Java 6 beta (with also the missing method addded for
ConcurrentLinkedDeque):

http://beanlib.sourceforge.net/3.2.3/api/net/sf/beanlib/util/concurrent/package-summary.html

Please let me know if I screwed up anything.  Otherwise, I can start
enjoying jsr166x in Java 5 :)

Hanson

On 8/26/06, Hanson Char <[hidden email]> wrote:

> It seems java.util.Deque has an extra method than jsr166x.Deque:
>
>     Iterator<E> descendingIterator();
>
> In jsr166x.ConcurrentLinkedDeque, there exists the implementation for the method
>
>     public Iterator<E> iterator();
>
> However, there is no existing implementation for the method
> "descendingIterator".
>
> If one were to provide the missing implementation in
> jsr166x.ConcurrentLinkedDeque, would it be something like the one
> given below ?
>
> Hanson
>
>     public Iterator<E> descendingIterator() {
>         return new CLDDescendingIterator();
>     }
>
>     final class CLDDescendingIterator implements Iterator<E>
>     {
>         Node<E> last;
>         Node<E> next = trailer.back();
>
>         public boolean hasNext() {
>             return next != null;
>         }
>
>         public E next() {
>             Node<E> l = last = next;
>             if (l == null)
>                 throw new NoSuchElementException();
>             next = next.back();
>             return l.element;
>         }
>
>         public void remove() {
>             Node<E> l = last;
>             if (l == null)
>                 throw new IllegalStateException();
>             while (!l.delete() && !l.isDeleted())
>                 ;
>         }
>     }
>
> On 8/26/06, Hanson Char <[hidden email]> wrote:
> > Just curious.  Why is it that all the classes in jsr166x exist in Java
> > 6 beta, except the ConcurrentLinkedDeque ?
> >
> > Hanson
>
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
Further updated with the latest sources from Java 6 beta 2 (from beta).

  http://prdownloads.sourceforge.net/beanlib/beanlib-3.2.4.tar.gz?download

Hanson

On 8/26/06, Hanson Char <[hidden email]> wrote:

> Everything classes of jsr166x are now included and "augmented" with
> the source from Java 6 beta (with also the missing method addded for
> ConcurrentLinkedDeque):
>
> http://beanlib.sourceforge.net/3.2.3/api/net/sf/beanlib/util/concurrent/package-summary.html
>
> Please let me know if I screwed up anything.  Otherwise, I can start
> enjoying jsr166x in Java 5 :)
>
> Hanson
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Doug Lea
In reply to this post by Hanson Char
Hanson Char wrote:
> Just curious.  Why is it that all the classes in jsr166x exist in Java
> 6 beta, except the ConcurrentLinkedDeque ?
>

This was a judgement call about its utility. While the current
implementation is OK for some applications, it is not the best
approach for one of the most common parallel applications of
Deques, as work-stealing queues. See for example the FJ
Fork/join framework in dl.util.concurrent, which we plan to
finally revive in much improved form for JDK7 and supply some
nice lightweight and fast loop-parallelization utilities.
So all in all, it seemed better to not commit to having this
class in JDK6.

That's why we put all those disclaimers on the the jsr166x
package. (And will do likewise probably within a few months
for a "jsr166y" package (for lack of a better name, unless
someone suggests something better) with candidate classes
for JDK7.

If I were you, I might not include ConcurrentLinkedQueue in
a JDK6-workalike package for JDK5.

Thanks again for taking this on!

-Doug



_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: FooTreeCache

Hanson Char
ConcurrentLinkedDeque removed in beanlib 3.2.5:

  http://prdownloads.sourceforge.net/beanlib/beanlib-3.2.5.tar.gz?download

Hanson

On 8/27/06, Doug Lea <[hidden email]> wrote:

> Hanson Char wrote:
> > Just curious.  Why is it that all the classes in jsr166x exist in Java
> > 6 beta, except the ConcurrentLinkedDeque ?
> >
>
> This was a judgement call about its utility. While the current
> implementation is OK for some applications, it is not the best
> approach for one of the most common parallel applications of
> Deques, as work-stealing queues. See for example the FJ
> Fork/join framework in dl.util.concurrent, which we plan to
> finally revive in much improved form for JDK7 and supply some
> nice lightweight and fast loop-parallelization utilities.
> So all in all, it seemed better to not commit to having this
> class in JDK6.
>
> That's why we put all those disclaimers on the the jsr166x
> package. (And will do likewise probably within a few months
> for a "jsr166y" package (for lack of a better name, unless
> someone suggests something better) with candidate classes
> for JDK7.
>
> If I were you, I might not include ConcurrentLinkedQueue in
> a JDK6-workalike package for JDK5.
>
> Thanks again for taking this on!
>
> -Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest