Hi Dominic, thanks for spending time to shoot holes in Index!
On Tue, Jan 14, 2014 at 8:27 AM, Dominic Tootell <dominic.toot...@gmail.com>wrote: > Hi there, > > Apologies if this question has been asked elsewhere, and if I'm not > correct in my thought process. > I was looking around for a ConcurrentMultiMap implementation and came > across the one in akka after searching. > > The implementation I'm referencing is the following: > > - > https://github.com/akka/akka/blob/master/akka-actor/src/main/scala/akka/util/Index.scala > > The use case I was looking at is as follows: > > (a) If the existing key (K) was present in the map, the (V) would be put > onto the existing Set of V's associated with the K. > (b) If the K did not exist in the map a new Set with V as the initial > value would be added, to the map associated with K. > > The .put(K,V) would work concurrently with remove(K), such that V, would > either be in the > Set removed by remove(K) (when that method completes); or would be added > to the map as (b), > if remove(K) completed before the put(K,V) did. > > Looking at the source of Index.scala, it looks as thought the above use > case is not satisfied by the implementation. > Such that there could be (forgive me if I'm wrong here), a slight > possibility for the put(K,V) > to neither be added to the map (in an existing or new Set), or be in the > Set removed by remove(K) > (when that method completes). This could be a completely valid for it's > use case it has been developed for. > > For example: > > Say Thread t1 runs in put(K,Vy) up to line 52 (completes it) and returns a > Set such that oldSet is a Set of one V > (i.e. it is running per the use case in the comment "// Parry for two > simultaneous putIfAbsent(id,newSet)") > > Say Thread t1 is ctx switched (unscheduled by the OS) and Thread t2 is > scheduled and calls remove(K), which completes, > and t2 does what it needs on the returned Set (the Vy from t1.put(K,Vy) is > not in the Set processed by t2). > > Thread t1 is once again scheduled and runs. The oldSet is niether null, > or empty. As a result the set is appended > to with Vy, and the method returns. However, the Set Vy was appended to > is > neither in the Map (associated with K) due to t2's remove operation, or > was it in the Set when t2 removed it. > As a result the value, from the put(K,V) goes missing. > Check def remove, it only removes Sets from the Map if they are empty, and if it is empty: https://github.com/akka/akka/blob/master/akka-actor/src/main/scala/akka/util/Index.scala#L124 And if def put sees an empty set, it will retry: https://github.com/akka/akka/blob/master/akka-actor/src/main/scala/akka/util/Index.scala#L55 If you add a sleep after putIfAbsent, can you provoke a bug? Cheers, √ > The documentation > http://doc.akka.io/api/akka/2.2.3/#akka.util.ConcurrentMultiMap > specifies that the Add/remove is serialized over the specified key; which > seems to indicate that > add/remove shouldn't cause a race condition. However, it depends on how > that is in interpreted. > Therefore, I'm unsure if add/remove for the MultiMap implementation were > meant to be synchronized with each other > or not. > > A simple test case of the above can be found here: > https://github.com/tootedom/akka-cmm > > I was just wondering if this Race condition in the remove(K), and > put(K,V); is expected by design > or if perhaps it a valid issue in the implementation, and as a result an > issue for akka itself, for > the LookupClassification trait in > https://github.com/akka/akka/blob/master/akka-actor/src/main/scala/akka/event/EventBus.scala > > Apologies if the above doesn't make sense. > > thanks > /dom > > -- > >>>>>>>>>> Read the docs: http://akka.io/docs/ > >>>>>>>>>> Check the FAQ: http://akka.io/faq/ > >>>>>>>>>> Search the archives: https://groups.google.com/group/akka-user > --- > You received this message because you are subscribed to the Google Groups > "Akka User List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to akka-user+unsubscr...@googlegroups.com. > To post to this group, send email to akka-user@googlegroups.com. > Visit this group at http://groups.google.com/group/akka-user. > For more options, visit https://groups.google.com/groups/opt_out. > -- Cheers, √ *Viktor Klang* *Director of Engineering* Typesafe <http://www.typesafe.com/> Twitter: @viktorklang -- >>>>>>>>>> Read the docs: http://akka.io/docs/ >>>>>>>>>> Check the FAQ: http://akka.io/faq/ >>>>>>>>>> Search the archives: https://groups.google.com/group/akka-user --- You received this message because you are subscribed to the Google Groups "Akka User List" group. To unsubscribe from this group and stop receiving emails from it, send an email to akka-user+unsubscr...@googlegroups.com. To post to this group, send email to akka-user@googlegroups.com. Visit this group at http://groups.google.com/group/akka-user. For more options, visit https://groups.google.com/groups/opt_out.
