Hi, Re: https://jira.jboss.org/jira/browse/ISPN-116 I can see two ways of providing such feature: 1. Rather than using a queue, using a data structure similar to the one used in the data container so that when a newer value for a key already present in the queue is present, the value can be swapped (map like lookup required on the key so that O(1) is maintained) while maintaining queue-like FIFO operations required to empty it. 2. Based on suggestion coming amin59 in http://www.jboss.org/index.html?module=bb&op=viewtopic&p=4240980#..., make the current queue only store keys and make the draining process query the cache for the latest value. Because from the time the data was put to the cache to the time it's stored, the data could have expired or had been removed all together, such query would need to make sure it doesn't go to the cache loader again. Also, if the data had been removed, how would the Async store know that from cache.get()? The queue would need to record somehow that a key was actually removed. The benefit of the 1st option is that we can take advantage of fast drainTo() like operations when draining it, and also the fact that no contention is added to the cache itself. The downside would be the need for a more complex data structure. The benefit of the 2nd option is the keeping a simple queue, less complex data structure, but requires that each time a key is to be drained, we have to query the cache. This could slow down the draining process. My preference is with 1. but for to use it, I'd need the data container collection to be made more generic. Thoughts? -- Galder Zamarreño Sr. Software Engineer Infinispan, JBoss Cache _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

Galder Zamarreno wrote: > Hi, > > Re: https://jira.jboss.org/jira/browse/ISPN-116 > > I can see two ways of providing such feature: > > 1. Rather than using a queue, using a data structure similar to the > one used in the data container so that when a newer value for a key > already present in the queue is present, the value can be swapped > (map like lookup required on the key so that O(1) is maintained) > while maintaining queue-like FIFO operations required to empty it. Is the FIFO order required? We apply the 'final state' when we do the flush of the structure, I don't think the order of the operation is relevant. If this is the case, our structure might be a Map, with null values for removed keys, as a convention. > > 2. Based on suggestion coming amin59 in http://www.jboss.org/index.html?module=bb&op=viewtopic&p=4240980#... > , make the current queue only store keys and make the draining > process query the cache for the latest value. Because from the time > the data was put to the cache to the time it's stored, the data > could have expired or had been removed all together, such query > would need to make sure it doesn't go to the cache loader again. > Also, if the data had been removed, how would the Async store know > that from cache.get()? The queue would need to record somehow that > a key was actually removed. > > The benefit of the 1st option is that we can take advantage of fast > drainTo() like operations when draining it, and also the fact that > no contention is added to the cache itself. The downside would be > the need for a more complex data structure. > > The benefit of the 2nd option is the keeping a simple queue, less > complex data structure, but requires that each time a key is to be > drained, we have to query the cache. This could slow down the > draining process. draining process being slowed down is not critical, as it is performed async. > > My preference is with 1. but for to use it, I'd need the data > container collection to be made more generic. > > Thoughts? _______________________________________________ infinispan-dev mailing list infinispan-dev(a)lists.jboss.org https://lists.jboss.org/mailman/listinfo/infinispan-dev

Manik Surtani wrote: > * Make the concurrent map volatile > * When iterating, first create a new ConcurrentMap and replace the > old one with the new one so all concurrent threads write to the new > Map > * Iterate over the old map That would lead to race conditions since a concurrent writing thread could write to the "old" map, either by getting a recent yet incorrect read off the volatile, or reading it right before it changes.

On 07/09/2009 11:55 AM, Manik Surtani wrote: > > On 8 Jul 2009, at 19:53, Jason T. Greene wrote: > >> Manik Surtani wrote: >>> * Make the concurrent map volatile >>> * When iterating, first create a new ConcurrentMap and replace the >>> old one with the new one so all concurrent threads write to the >>> new Map >>> * Iterate over the old map >> >> That would lead to race conditions since a concurrent writing thread >> could write to the "old" map, either by getting a recent yet >> incorrect >> read off the volatile, or reading it right before it changes. > > True, since referencing the map and writing to it isn't atomic. > > We could guard access to the map with a read/write lock. Safe, if a > little heavy-handed... map writers would acquire a RL (since we want > concurrent access here) but the async flushing thread would need to > wait > for a WL to swap the map reference, releasing the lock after the map > reference has been swapped. Yeah, I don't think it could be volatile because it only applies to the variable itself, not the contents pointed at. The R/W lock approach looks like a valid one and better than using synchronized blocks. Another thing I had in my mind is whether we need the copy to be a ConcurrentMap, we could probably just use a Immutables.immutableMapCopy().

I looked at the two implementations (ConcurrentHashMap(Map) constructor vs Immutables.immutableMapCopy() which would Object.clone() on the map) but I'm not sure which one would be faster. Since clone() would rely on a native clone() impl, I'd imagine that to be faster.

> -- > Manik Surtani > manik(a)jboss.org > Lead, Infinispan > Lead, JBoss Cache > http://www.infinispan.org > http://www.jbosscache.org > > > > > _______________________________________________ > infinispan-dev mailing list > infinispan-dev(a)lists.jboss.org > https://lists.jboss.org/mailman/listinfo/infinispan-dev -- Galder Zamarreño Sr. Software Engineer Infinispan, JBoss Cache

On 07/07/2009 12:02 PM, Mircea Markus wrote: > Galder Zamarreno wrote: >> </snip> >> >> 1. Rather than using a queue, using a data structure similar to the >> one used in the data container so that when a newer value for a key >> already present in the queue is present, the value can be swapped (map >> like lookup required on the key so that O(1) is maintained) while >> maintaining queue-like FIFO operations required to empty it. > Is the FIFO order required? We apply the 'final state' when we do the > flush of the structure, I don't think the order of the operation is > relevant. > If this is the case, our structure might be a Map, with null values for > removed keys, as a convention. Hmmmm, very good point. In my mind, I was thinking that even in async mode, we should still apply the changes in the order they came but tbh, the moment you do this asynchronously, you lose the confirmation that it actually happens and hence, the order is probably irrelevant.