Concurrent::Hash does not lock on method #each

[shevkoplyas]

Abstract:

Playing with Concurrent::Hash here. I hoped it would block (by using the locks against the object itself) one of two concurrent callers so they will iterate the hash in a one-at-a-time manner.

CASE 1 of 2: Two threads reading the same Concurrent::Hash
When 2 threads reading hash by using iteration method #each it does not lock as expected. Instead in the middle of 1st thread reading through half of hash 2nd thread kicks in and starts reading hash over as if no any locking happening under the hood.
(see code snippet to reproduce below)

CASE 2 of 2: One thread slowly reading other thread writing from/to same Concurrent::Hash
When one thread artificially sleeps fraction of a second inside #each block the 2nd thread tries to modify the same Concurrent::Hash and fails with exception "can't add a new key into hash during iteration (RuntimeError)". Basically showing exact same behaviour as Ruby's standard Hash
(see code snippet to reproduce below)

OS: Ubuntu 14.04.5 LTS, Trusty Tahr

ruby version:
ruby 2.2.5p319 (2016-04-26 revision 54774) [x86_64-linux-gnu]

concurrent version:
concurrent-ruby-1.0.2

concurrent-ruby-ext installed: no
concurrent-ruby-edge used: no

 gem list
 *** LOCAL GEMS ***
 
 bigdecimal (1.2.6)
 bundler (1.13.6)
 concurrent-ruby (1.0.2)
 connection_pool (2.2.0)
 daemons (1.2.4)
 dogapi (1.23.0)
 dogstatsd-ruby (2.0.0)
 eventmachine (1.2.0.1)
 ffi (1.9.14)
 io-console (0.4.3)
 json (1.8.1)
 listen (3.1.5)
 macaddr (1.7.1)
 multi_json (1.12.1)
 net-http-persistent (3.0.0)
 posix_mq (2.3.0)
 psych (2.0.8)
 rack (1.6.4)
 rack-protection (1.5.3)
 rake (10.4.2)
 rb-fsevent (0.9.8)
 rb-inotify (0.9.7)
 rdoc (4.2.0)
 ruby-kafka (0.3.15)
 ruby_dep (1.5.0)
 sinatra (1.4.7)
 sinatra-advanced-routes (0.5.3)
 statsd-ruby (1.3.0)
 sys-cpu (0.7.2)
 sys-filesystem (1.1.7)
 sys-proctable (1.1.3 universal-linux)
 systemu (2.6.5)
 thin (1.7.0)
 thread_safe (0.3.5)
 tilt (2.0.5)
 uuid (2.3.8)

CASE 1 of 2: Two threads reading the same Concurrent::Hash code example:

 #!/usr/bin/env ruby
 
 require 'concurrent'
 
 $h = Concurrent::Hash.new({})
 
 def hash_reader(delim)
     loop{
         count = 0
         $h.each{
             count += 1
             if count != $h.size
                 print delim
             else
                 puts delim.upcase
             end
         }
     }
 end
 
 # fill hash with N=50 items
 hash_size = 50
 hash_size.times{|i|
     $h[i] = i
 }
 
 t1 = Thread.new(){
     hash_reader("o")
 }
 
 t2 = Thread.new(){
     hash_reader("i")
 }
 
 t1.join  # will never happen, but for completeness
 t2.join

output (you can see not all lines are complete with capitalized letter at the end):

oooooooooooooooooooooooooooooooooooooooooooooooooO
oooooooooooooooooooooooooooooooooooooooooooooooooO
oooooooooooooooooooooooooooooooooooooooooooooooooO
oooooooooooooooooooooooooooooooooooooooooooooooooO
ooooooooooooooooooooooooooooiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiioooooooooooooooooooooO
oooooooooooooooooooooooooooooooooooooooooooooooooO
oooooooooooooooooooooooooooooiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiI
iiiiiiiiiooooooooooooooooooooO
oooooooooooooooooooooooooooooooooooooooooooooooooO
oooooooooooooooooooooooooooooooooooooooooooooooooO

CASE 2 of 2: One thread slowly reading other thread writing from/to same Concurrent::Hash code example:

 #!/usr/bin/env ruby
 
 require 'concurrent'
 
 $h = Concurrent::Hash.new({})
 
 def hash_reader(delim)
     loop{
         count = 0
         $h.each{
             count += 1
             if count != $h.size
                 print delim
             else
                 puts delim.upcase
             end
             sleep 0.1  # lets make reader slow
         }
     }
 end
 
 def hash_writer()
     loop{
         begin
             epoch_ms = (Time.now.to_f * 1000).round
             $h[epoch_ms] = epoch_ms
         rescue Object => boom
             $stderr.puts "Exception: #{boom} (#{boom.class})"
             $stderr.puts "Exception message: #{boom.message}"
         end
         sleep 1
     }
 end
 
 # fill hash with N=50 items
 hash_size = 50
 hash_size.times{|i|
     $h[i] = i
 }
 
 t1 = Thread.new(){
     hash_reader("o")
 }
 
 t2 = Thread.new(){
     hash_writer()
 }
 
 t1.join
 t2.join

case 2 of 2 example output:

oException: can't add a new key into hash during iteration (RuntimeError)
Exception message: can't add a new key into hash during iteration
oooooooooException: can't add a new key into hash during iteration (RuntimeError)
Exception message: can't add a new key into hash during iteration
ooooooooooException: can't add a new key into hash during iteration (RuntimeError)
Exception message: can't add a new key into hash during iteration
ooooooooooException: can't add a new key into hash during iteration (RuntimeError)

I couldn't find example/docs on how to properly use Concurrent::Hash, so please suggest if I'm using it in a wrong way or is it a bug?

thank you in advance,
Dmitry Shevkoplyas

[pitr-ch]

Thanks @shevkoplyas. @thedarkone could you have look?

[jdantonio]

I believe this is expected behavior. I believe this class only promises that each read/write is synchronized. I don't believe it promises atomicity for the entire #each method. We should compare to the Java and Rbx implementations.

[pitr-ch]

yeah, the error is rather unfortunate though, it would be nice if it could handle concurrent iteration and updates.

[shevkoplyas]

Thanks guys for quick reply.
Well, the docs for Concurrent::Hash then should be fixed because currently docs promise to lock on #each call as well:

Overview
A thread-safe subclass of Hash. This version locks against the object itself for every method call, ensuring only one thread can be reading or writing at a time. This includes iteration methods like #each.

I understand it as: Locks for every method, including #each, which means while one thread not finished it's #each call the other will have to wait.

Honestly instead of quick fix in the doc's false promise I'd rather love to see the described behaviour when I don't need to inject manually any locking mechanisms into the Hash class numerous methods of accessing/altering it. That would make Concurrent::Hash brilliant ruby gem and the only one ready-to-use in multrithreaded environment out of the box (as it's name suggests;) !

thanks,
Dmitry Shevkoplyas

ps: what would be your verdict? should we be hopeful?

[jdantonio]

That would make Concurrent::Hash brilliant ruby gem and the only one ready-to-use in multrithreaded environment out of the box

I take issue with this statement. Concurrent Ruby is "ready-to-use in multrithreaded environment" as it exists. Your understanding of "thread safe" is limited and too heavily focussed on your personal use case.

"Thread safe" simply means that one thread cannot write to a memory location while one or more other threads read from or write to that same memory location. Concurrent::Hash makes this guarantee and implements that correctly. What you are asking for is for the gem to synchronize a complex series of actions. That's not an unreasonable request. Many of our abstractions do this. But that isn't thread safety, that's synchronization of a complex series of actions. And it isn't necessarily suitable for the #each method.

Let me give another use case. Let's say that I have an array of 1 million items and I'm running my application on a four-core system using JRuby. If I have 4 threads simultaneously calling #each to iterate over the array and all 4 are only reading from the array, what is the desired behavior? Locking the entire #each method would force 3 of the threads to block while the first finishes. Two would then block while the second performs its iteration. And so on. This would be horribly inefficient. The desired, thread safe behavior is for all 4 threads to have simultaneous access to the array, but for each individual read to be protected. The current implementation does this. There are also cases where writes against that array may be algorithmically acceptable. If the first thread has traversed the first half of the array then it probably doesn't care if the second thread inserts a new element at the head. This, too, is supported by the current implementation.

With the current implementation it is possible for a programmer to manually synchronize the #each method. Therefore, both use cases are supported. If we change the behavior of #each then only one of the two presented use cases is supported. We make life easier in one case but make it impossible in the other. Is that really what's best for the Ruby community as a whole?

In this case we should recognize that Concurrent Ruby provides a suite of tools at varying levels of abstraction. Actor is a very high level of abstraction whereas CountDownLatch is a very low level abstraction. We have different expectations of Actor than CountDownLatch. And that's OK. The question we need to ask with respect to Concurrent::Hash is this: How low/high level is it? Our expectations should be set accordingly.

Personally, I believe that Concurrent::Hash is a fairly low level abstraction and that its current behavior is reasonable and best for its intended use.

[thedarkone]

@shevkoplyas thanks, for bringing this up! I believe you'll be much better served by Concurrent::Map, it is usually the case that if you are after a concurrent Hash-like data structure, Concurrent::Map is what you want 😉. As a general rule, you should only pick Conc::Hash over Conc::Map if your use case requires insertion order guarantees.

---

@pitr-ch, @jdantonio: sigh, KeyError got to us again... we'll probably have to tackle this the same way as in Conc::Map, this is going to slightly spoil our beautiful MRI impl of Conc::Hash 😭.

[pitr-ch]

Thanks @jdantonio for the elaboration, I agree. @shevkoplyas please synchronise externally if you need separate iterations.

I've updated the documentation 6f9d974, @thedarkone would you work on allowing concurrent iteration and writes #599 ?

[pitr-ch]

Remaining issue tracked in #599