Thread-safety and hash tables

I’m storing information in a hashtable. The information is keyed off a string, and the key is volatile — items can be removed, added, replaced, etc., from the hash table. The problem that I’m studying is how to manipulate this information in a thread-safe way without locking the entire hash table all the time and killing performance.

Solution number 1 was to lock the entire hash table during each operation on the data in the hash table. I had code like this:

lock(hashtable) {
  Item item = (Item)hashtable[key];
  item.SetName(“foo”);
  database.Persist(item);
}

The problem with this is that I couldn’t take advantage of SQLServer’s ability to handle several database operations simultaneously. In the presence of lots of threads, my CPU usage in this style never got about 50% or so, indicating that there was lots of contention for the lock that was preventing any parallelism entirely (kind of the point of threads, eh???)

Next attempt was the naive way:

Item item = (Item)hashtable[key];
lock(item) {
  item.SetName(“foo”);
  database.Persist(item);
}

Obviously not thread safe. Between the first and second line, someone can come in and delete or replace the item in the hash table, so I could be dealing with old data, possibly persisting data to the database that is stale and overwriting the new data. This is bad.

Next attempt was to be a little clever and wrap the data in the cache with an object that was longer-lived than an individual cache item. This way the above attempt was OK to do, because I was always guaranteed that the wrapper was the same and I could lock it to prevent changes to its contents. It looked something like this:

ItemWrapper wrapper = (ItemWrapper)hashtable[key];
lock(wrapper) {
  Item item = wrapper.Item;
  item.SetName(“foo”);
  database.Persist(item);
}

Our problem here was that I could never get rid of these wrappers. Once in the hashtable, they had to live there forever. If I did start getting rid of them, I’d get right back into the same place where I was before with the race condition between getting stuff out of the cache and locking it.

What I really wanted was a single method call that I could make on a hashtable that would return me an Item from the hashtable already locked, and locked in a thread-safe way. And I couldn’t lock the hashtable while I was trying to lock the Item, because that would lead to the same performance problems that I had originally. So what was I to do????

Well, I started looking at Optimistic Locking as a way around this. I embedded a version number inside my Item object and started doing various manipulations to that version number in an attempt to satisfy all my requirements. But this is getting very complicated, and I’m still not convinced of my thread safety.

So, my question for you, my loyal reader (all 1 of you :))… Have I missed something? Is there some other, simpler way of approaching this problem that I missed? Any comments and hints appreciated.

— bab

 

Now playing: Dream TheaterHollow Years

5 thoughts to “Thread-safety and hash tables”

  1. I keep thinking that the solution to your problem is to place some kind of "future" object in the hash table, to represent the data that is being persisted to the database, or the data that is being fetched from the database. Once this object exists, you can drop the lock on the HashTable, and take out a lock on the individual "future" instance.

    Like this…

    (untested, and not necessarily written in any computer language known to man πŸ˜‰

    void Save(key, item) {

    Persister persister = null;

    lock(hashtable) {

    if (hashtable.exists(key))

    persister = hashtable[key];

    persister.setData(item);

    else {

    persister = new Persister(key, item);

    hashtable.add(key, persister);

    }

    } // unlock hash map here.

    lock(persister) {

    persister.doPersist();

    }

    }

    So, you only lock the hash table while putting in an object that represents the fetching or saving of the data, then you unlock the hash table. Then you lock the proxy object and do the fetching or persisting of the data. The long lock that is taken to fetch or save the data will affect only threads that touch that particular data instance. And this is good.

    OK, so you’re worried about these extraneous objects "staying around" too long.

    Solutions:

    #1. Don’t worry about it.

    #2. Once the data is loaded, lock the hash map to put the actual data there in place of the proxy. (Then garbage collection will toss out the unused proxies.)

  2. http://site.voila.fr/ku19826/nvmingxing.htm ???????

    http://site.voila.fr/ku19826/xinfeng.htm ?????

    http://site.voila.fr/ku19826/shunv.htm ????

    http://site.voila.fr/ku19826/nvxingxb.htm ????????

    http://site.voila.fr/ku19826/qiantai.htm ????????

    http://site.voila.fr/ku19826/gglldd.htm ????

    http://site.voila.fr/ku19826/touming.htm ?????

    http://site.voila.fr/ku19826/qingsdy.htm ????

    http://site.voila.fr/ku19826/sanjipian.htm ???

    http://site.voila.fr/ku19826/jiqxisho.htm ????

    http://site.voila.fr/ku19826/jiqingying.htm ????

    http://site.voila.fr/ku19826/xingzhan.htm ????

    http://site.voila.fr/ku19826/xintu.htm ????

    http://site.voila.fr/ku19826/xingd.htm ????

    http://site.voila.fr/ku19826/ct.htm ????

    http://site.voila.fr/ku19826/cx.htm ????

    http://site.voila.fr/ku19826/crz.htm ????

    http://site.voila.fr/ku19826/cdy.htm ????

    http://site.voila.fr/ku19826/st.htm ????

    http://site.voila.fr/ku19826/sqs.htm ????

    http://site.voila.fr/ku19826/szz.htm ????

    http://site.voila.fr/ku19826/syyy.htm ????

    http://site.voila.fr/ku19826/huangtt.htm ????

    http://site.voila.fr/ku19826/hhhz.htm ????

    http://site.voila.fr/ku19826/hhdd.htm ????

    http://site.voila.fr/ku19826/hhyy.htm ????

    http://www.liberalforum.org/blog/?u=nxiong ????????

    http://www.liberalforum.org/blog/?u=tttmmm ?????

    http://www.liberalforum.org/blog/?u=sssnnn ????

    http://www.liberalforum.org/blog/?u=qqqjjj ????????

    http://www.liberalforum.org/blog/?u=ngyngy ???????

    http://www.liberalforum.org/blog/?u=gugu8 ????

    http://www.liberalforum.org/blog/?u=xxxyyy ????

    http://www.liberalforum.org/blog/?u=cccyyy ????

    http://www.liberalforum.org/blog/?u=hhhyyy ????

    http://www.liberalforum.org/blog/?u=jjjyyy ????

    http://www.liberalforum.org/blog/?u=hhhzzz ????

    http://www.liberalforum.org/blog/?u=jjjzzz ????

    http://www.liberalforum.org/blog/?u=sssyyy ????

    http://www.liberalforum.org/blog/?u=hhhsss ????

    http://www.liberalforum.org/blog/?u=ssszzz ????

    http://www.liberalforum.org/blog/?u=ssssss ????

    http://www.liberalforum.org/blog/?u=xxxsss ????

    http://www.liberalforum.org/blog/?u=ccczzz ????

    http://www.liberalforum.org/blog/?u=cccsss ????

    http://www.liberalforum.org/blog/?u=xxxzzz ????

    http://www.liberalforum.org/blog/?u=sssjjj ???

    http://www.greatestjournal.com/users/ccblog/311.html ???

    http://www.greatestjournal.com/users/ccblog/570.html ????

    http://www.greatestjournal.com/users/ccblog/993.html ????

    http://www.greatestjournal.com/users/ccblog/1221.html ????

    http://www.greatestjournal.com/users/ccblog/1522.html ????

    http://www.greatestjournal.com/users/ccblog/1642.html ????

    http://www.greatestjournal.com/users/ccblog/1940.html ????

    http://www.greatestjournal.com/users/ccblog/2124.html“>http://www.greatestjournal.com/users/ccblog/2124.html ????

    http://www.greatestjournal.com/users/ccblog/2124.html“>http://www.greatestjournal.com/users/ccblog/2124.html ????

    http://www.greatestjournal.com/users/ccblog/2796.html ????

    http://www.greatestjournal.com/users/ccblog/3062.html ????

    http://www.greatestjournal.com/users/ccblog/3229.html ????

    http://www.greatestjournal.com/users/ccblog/3577.html ?????

    http://www.greatestjournal.com/users/ccblog/3658.html ??? ????

    http://www.greatestjournal.com/users/ccblog/3907.html ????

    http://www.greatestjournal.com/users/ccblog/4174.html ????????

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.