<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Ok, taking this further. After some discussion with Jason, there actually is a better concurrent linking algorithm we can use that is simpler and more efficient (no spin locks or auxillary nodes), but a bit more delicate with node states. THis is what is used in the linking in JDK6's ConcurrentSkipListMap, but I've quite heavily modified it for our purposes. Not implemented this as yet, but here are the ideas for you guys to tear apart. Looking forward to your feedback. :-)<div><br></div><div><div>Concurrent ordered data container (for FIFO, LRU containers)</div><div>--------------------------------------------------------------------------------</div><div><br></div><div>The main constraints on this container are that it should provide constant time operations for get(), contains(), put() and remove() operations, and the iterator should be ordered and offer constant time traversal.</div><div><br></div><div>This implementation is based on threadsafe linked lists used in ConcurrentSkipListMap (CSLM) in Sun's JDK 6. In addition, the implementation uses a lockable Segment array (as in CHM) except that in the HashEntries, keys are always Object and values are LinkedEntries (LEs). LEs always have a reference to an InternalCacheEntry, as well as volatile next and prev pointers.</div><div><br></div><div>Also, unlike CSLM Nodes, LEs are doubly linked since to update the link on the predecessor, we need a reference to it (as LEs are located via a hash lookup rather than traversal). This alters the logic of insertions and removals somewhat.</div><div><br></div><div>Removal</div><div>-------</div><div>1. Lock segment containing key</div><div>2. Locate LinkedEntry using a hash lookup</div><div>3. If this is null, or its value is null, return null. </div><div>4. CAS LE.value to null. If this fails, ignore and return. Someone else is probably removing it.</div><div>5. Unlink. If unlinking fails, ignore and continue; will be marked and removed later.</div><div>6. Release segment lock</div><div><br></div><div>Unlink</div><div>------</div><div>1. Create Marker LE (MLE)</div><div>2. MLE.next = LE.next</div><div>3. CAS LE.next to MLE (expecting MLE.next)</div><div>4. CAS LE.prev.next to MLE.next (expecting LE)</div><div>5. On failure to CAS, ignore</div><div><br></div><div>Insertion </div><div>---------</div><div><br></div><div>1. Lock segment containing key</div><div>2. Create new LE, populate with value, insert into hash table</div><div>3. Insert link</div><div>4. Release segment lock</div><div><br></div><div>Insert link</div><div>-----------</div><div>1. LE.next = HEAD</div><div>2. LE.prev = HEAD.prev</div><div>3. CAS HEAD.prev = LE (if HEAD.prev == LE.prev)</div><div>4. If the CAS fails, start again at step 4</div><div>5. LE.prev.next = LE (if LE.prev.next = HEAD)</div><div><br></div><div><br></div><div>Update (E.g., for LRU visit or update)</div><div>------</div><div>1. Lock segment containing key (only if update)</div><div>2. if LE == null || LE.value == null return</div><div>3. if update, update value. No need for a CAS here since we have a segment lock</div><div>4. CAS LE.prev.next = LE.next (expecting LE, ignore failure)</div><div>5. CAS LE.next.prev = LE.prev (expecting LE, ignore failure)</div><div>6. insert LE</div><div>7. Release segment lock (if update)</div><div><br></div><div>Get</div><div>---</div><div>1. Retrieve LE</div><div>2. if (LE.value==null) unlink LE, return null.</div><div><br></div><div><div>On 2 Apr 2009, at 10:00, Manik Surtani wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 2 Apr 2009, at 09:10, Mircea Markus wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>Manik Surtani wrote:<br><blockquote type="cite">Hello all.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">I have finished my work with the eviction code in Infinispan, here is a summary of what has happened.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">From a user perspective (including API and configuration) as well as a design overview, please have a look at <br></blockquote><blockquote type="cite"><a href="http://www.jboss.org/community/docs/DOC-13449">http://www.jboss.org/community/docs/DOC-13449</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">From an implementation perspective, have a look at the srcs of FIFODataContainer and LRUDataContainer. These two classes are where everything happens. The javadocs should explain the details, but in a nutshell you can expect constant time operations for all puts, gets, removes, iterations. :-) <br></blockquote><blockquote type="cite">Feedback on the impls would be handy. :-)<br></blockquote>I like to concept - it's nice and clear for users to grasp. Also took a look at implementation, nice and complex, so I'd rather have you and a white board to understand it completely :) .<br>Some notes though: EvictionException is never used, same for SpinLock.rl field.</div></blockquote><div><br></div><div>Good point, EvictionException was a carry-over from JBC which can go away.</div><div><br></div><div>SpinLock.rl was something I used for debugging/tracking race conditions - it should go away now as well.</div><br><blockquote type="cite"><div>And a question:<br>with this impl, we're doing locking twice for cache operations: on LockInterceptor and on DataContainer itself. Why is this necessary? I think this is needed so that eviction thread and user threads not to conflict( am I right?).</div></blockquote><div><br></div><div>Well, the locking is done on a different level. The LockingInterceptor locks a key. So keep in mind that 2 threads may lock 2 separate keys concurrently, but these may map to the same hash bucket in the data container. In which case, since the DC uses a CHM, this would mean that the same stripe is locked preventing concurrent reorganisation of the stripe.</div><div><br></div><blockquote type="cite"><div>Isn't it possible to use the same locking (i.e. LockManager) for both these threads?</div></blockquote><div><br></div><div>Possible, but again not ideal, for example if you have TX 1 which writes to key K1. The way this currently works, here is what happens:</div><div><br></div><div>1. Acquire lock for key K1 in the lock manager</div><div>2. Write to K1</div><div>3. Sleep?</div><div>4. Commit:</div><div>5. Write changes to DC. This will lock the stripe in the CHM for the duration of this step only.</div><div>6. Release lock acquired in 1</div><div><br></div><div>Now if you have a concurrent write to K2, which *happens* to be in the same stripe as K1 in the CHM, this second thread will *not* block for TX 1 since TX 1 only locks the CHM stripe for a short duration (step 5 above). </div><div><br></div><div>Now if we used the same locks thoughout (e.g., step 1 *is* the lock stripe in the CHM) then you have far less concurrency.</div><div><br></div><div>Of course, the above premise only holds true if you have enough shared locks for the lock manager such that K1 and K2 do not map to the same lock, even if they are in the same stripe in the CHM. Also holds true if lock striping is disabled and you have a lock per key.</div><div><br></div><blockquote type="cite"><div>(also, why are we using ConcurrentHashMaps in default container - isn't access to data guarded by the lock interceptor?</div></blockquote><div><br></div><div>See above. :-)</div><div><br></div><div>Cheers</div><div>Manik</div><div><br></div><div>--</div></div><div apple-content-edited="true"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-infinispantal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-infinispantal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>Manik Surtani</div><div>Lead, JBoss Cache</div><div><a href="http://www.jbosscache.org">http://www.jbosscache.org</a><br><a href="mailto:manik@jboss.org" target="_blank">manik@jboss.org</a></div><div><br></div></div></span><br class="Apple-interchange-newline"></div></span><br class="Apple-interchange-newline"> </div><br></div>_______________________________________________<br>infinispan-dev mailing list<br><a href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>https://lists.jboss.org/mailman/listinfo/infinispan-dev<br></blockquote></div><br><div apple-content-edited="true"> <span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-infinispantal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-infinispantal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>--</div><div>Manik Surtani</div><div>Lead, JBoss Cache</div><div><a href="http://www.jbosscache.org">http://www.jbosscache.org</a><br><a href="mailto:manik@jboss.org" target="_blank">manik@jboss.org</a></div><div><br></div></div></span><br class="Apple-interchange-newline"></div></span><br class="Apple-interchange-newline"> </div><br></div></body></html>