[concurrency-interest] Locking a ConcurrentHashSet in a ConcurrentHasHMap

Ben Manes ben_manes at yahoo.com
Wed Aug 6 21:55:46 EDT 2008


If the race was, for example, against volatile data like caches then the entries could be recreated cheaply and the this complexity isn't necessary.  This is easiest way to avoid locking.  :-)

If its not an acceptable loss, then you could use a conditional remove to avoid part of the race condition.
  index.remove(valueName, set, Collections.emptySet())

You would then have a race of updating a set that was just removed. To be optimistic, you could follow the add with a "get" to avoid internal locking, and then lock with an attempted put if the check fails.
  if (set == index.get(valueName) {
    return; // success - set wasn't removed while adding
  } else if (index.putIfAbset(valueName, set) == null)) {
    return; // success - set removed, but added back by us
  } else {
    continue; // failed - set removed, but added back by someone else.  Retry add against new set
  }


----- Original Message ----
From: Mike Bean <bean at alcatel-lucent.com>
To: concurrency-interest at cs.oswego.edu
Sent: Wednesday, August 6, 2008 5:10:21 PM
Subject: [concurrency-interest] Locking a ConcurrentHashSet in a ConcurrentHasHMap

Experts,

I was wondering if anyone had some thoughts on how to avoid a lock to 
allow removal of a ConcurrentHashSet from a ConcurrentHashMap.  Context 
is an index manager with these two calls:

    public void index( Normal name, Value value, Entry entry )
    {
        if ( !m_indexingEnabled )
            return;

        ConcurrentHashMap<String,ConcurrentHashSet<Entry>> index = 
getIndex( name );
        if ( index != null )
        {
            String valueName = value.getAsString();
            while( true )
            {
                ConcurrentHashSet<Entry> set = index.get( valueName );
                if ( set == null )
                {
                    ConcurrentHashSet<Entry> newSet = new 
ConcurrentHashSet<Entry>();
                    newSet.add( entry );
                    if ( index.putIfAbsent( valueName, newSet ) == null )
                    {
                        break;
                    }
                }
                else
                {
                    synchronized ( set )  //!!! make sure we don't add 
entry to set while another thread removes empty set from index
                    {
                        if ( set.size() == 0 )
                        {
                            continue;
                        }
                        set.add( entry );
                        break;
                    }
                }
            }
        }
    }

    public void unindex( Normal name, Value value, Entry entry )
    {
        if ( !m_indexingEnabled )
            return;

        ConcurrentHashMap<String,ConcurrentHashSet<Entry>> index = 
getIndex( name );
        if ( index != null )
        {
            String valueName = value.getAsString();
            ConcurrentHashSet<Entry> set = index.get( valueName );
            if ( set != null )
            {
                synchronized ( set )  //!!! make sure we don't remove 
set from index while another thread adds entry to set
                {
                    set.remove( entry );
                    if ( set.size() == 0 )
                    {
                        index.remove( valueName, set );
                    }
                }
            }
        }
    }

Is there a better way to prevent one thread from updating the set while 
another thread is trying to remove the set from the map than the lock?.

I'm also concerned at the memory cost of a ConcurrentHashSet for a 
single reference to an Entry object but the indexing and unindexing 
entries gets more complex with the map containing an Entry or a 
ConcurrentHashSet of Entries.

Methods not shown from our index manager include queries that never fail 
as the map and set of entries change.

Thanks for all the work in this area,

Mike

-- 
Michael Bean (Mike)
Alcatel-Lucent
AAA Product Group
3461 Robin Ln, Ste 1
Cameron Park, CA 95682
Email: bean at alcatel-lucent.com
Phone: 530 672 7577
Fax: 530 676 3442

_______________________________________________
Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest



      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20080806/035abe31/attachment.html>


More information about the Concurrency-interest mailing list