Could ConcurrentSkipListMap be used as backing map?

[GoogleCodeExporter]

Hi - 

I was looking into your cache implementation to check if I could use a 
ConcurrentSkipListMap because I need to be able to seek into the cache with 
ceilingKey and floorKey methods.

Keys have two components and would look like:

key.1
key.2
key.4

Searching would look like this 

ceilingKey(key) -> key.1
ceilingKey(key.1) -> key.1
ceilingKey(key.3) -> key.4

floorKey(key.magicendmarker) -> key.4

I would also need to expose tailKeyItertor(fromKey) and headKeyIterator(toKey)

Value access would always be performed via get(key)

This is not really a feature request but an inquiry if you see any problems 
doing that. From my understanding of the code it should work.

Thanks,
Daniel

Original issue reported on code.google.com by Daniel.D...@gmail.com on 15 Jul 2011 at 5:32

[GoogleCodeExporter]

Yep, the decorator makes no assumptions about the backing ConcurrentMap. I did 
borrow ascending/descending terms from NavigatableMap for snapshot views, since 
Cassandra claimed to need both. I think only hot->cold makes sense, so when 
bringing that internal to Google we used "activeEntries" instead (see Guava's 
CacheBuilder). That may cause a little confusion if exposing as NavigatableMap.

You're welcome to fork a copy for your needs. I'd like to understand your 
usages first before I'd commit to offering a version directly. I don't think 
that the changes would be very complicated.

From your example, I think you may want something like the IndexMap. If you had 
the value associated with multiple keys as described, then it could be 
partially evicted / statistical anomalies / coherence mistakes. IndexMap solves 
this problem and you could add a #getIndex(key.x) which keeps the keys in 
sorted order. Since I wrote it a few years ago, you'd have some minor work to 
streamline and remove custom utilities.

It might be valuable if you could start a thread on 
guava-discuss@googlegroups.com with more detail on your use-case. Guava is 
where my work is standardized by the broader community. An IndexMap / 
bounded-CSLM hasn't been a use-case that we've seen internally so its not on 
the roadmap.

Original comment by Ben.Manes@gmail.com on 15 Jul 2011 at 7:59

[GoogleCodeExporter]

I think since I am at an experimental stage right now (this is also for 
cassandra) I'll just create a simple patch with an added ctor which takes the 
backing map as an argument. 
For iteration I can access the backing map directly when I dont want the read 
to be tracked as 'used' access. 
I also need a public afterCompletion() to mark that the client actually 
consumed a value during iteration.

As for the index map: My keys actually map to different values. The values are 
parts (ranges) of cassandra rows (these are like skip list maps too) and the 
second component of the key is the start of the cached row range. So I actually 
want that  cached ranges get evicted if not accessed. But I still want to be 
able to read overlapping ranges when I know that two ranges int the cache are 
consecutive. Thus I need to be able to iterate.

I'll post to the list as suggested when I see that this is actually getting 
somewhere.

Thanks again,
Daniel

Original comment by Daniel.D...@gmail.com on 18 Jul 2011 at 2:14

[GoogleCodeExporter]

Great. Let me know how it goes. I may try switching to Git now that GoogleCode 
supports it, which should make forks easier to manage.

If you run into performance issues, you might want to switch from a SkipList to 
a SkipTree. That should be more efficient w.r.t. hardware caches.
(https://github.com/mspiegel/lockfreeskiptree)

Original comment by Ben.Manes@gmail.com on 18 Jul 2011 at 6:46

[GoogleCodeExporter]

Is this still a desirable feature? Let me know since I'm putting together the 
v1.3 release for resolving a Cassandra feature request.

Original comment by Ben.Manes@gmail.com on 8 May 2012 at 8:15

[GoogleCodeExporter]

Thanks for asking. Well at least not at the moment. Some work has been done in 
that area but the original use case (why I posted the question) is still too 
vague / experimental.

Original comment by Daniel.D...@gmail.com on 14 May 2012 at 10:14

[GoogleCodeExporter]

fyi
I finally switched the repository over to git. It should be much easier to 
maintain a fork on github now.

I'm starting to work on v2 again. If there are more invasive API changes you'd 
like to see that would be a reasonable candidate.

Original comment by Ben.Manes@gmail.com on 31 Oct 2012 at 9:12

[GoogleCodeExporter]

Original comment by Ben.Manes@gmail.com on 15 Dec 2014 at 8:29

• Changed state: WontFix