What is the best way to deal with collections (lists or sets) in key-value storage?

Question

I wonder what can be an effective way to add/remove items from a really large list when your storage is memcached-like? Maybe there is some distributed storage with Java interface that deals with this problem well?

Someone may recommend Terracotta. I know about it, but that's not exactly what I need. ;)

Answer 1

Hazelcast 1.6 will have distributed implementation MultiMap, where a key can be associated with a set of values.

MultiMap<String, String> multimap = Hazelcast.getMultiMap ("mymultimap");
multimap.put ("1", "a");
multimap.put ("1", "b");
multimap.put ("1", "c");
multimap.put ("2", "x");
multimap.put ("2", "y");

Collection<String> values = multimap.get("1"); //containing a,b,c

Hazelcast is an open source transactional, distributed/partitioned implementation of queue, topic, map, set, list, lock and executor service. It is super easy to work with; just add hazelcast.jar into your classpath and start coding. Almost no configuration is required.

Hazelcast is released under Apache license and enterprise grade support is also available. Code is hosted at Google Code.

Answer 2

Maybe you should also have a look at Scalaris!

Answer 3

You can use a key-value store to model most data structures if you ignore concurrency issues. Your requirements aren't entirely clear, so I'm going to make some assumptions about your use case. Hopefully if they are incorrect you can generalize the approach.

You can trivially create a linked list in the storage by having a known root (let's call it 'node_root') node which points to a value tuple of {data, prev_key, next_key}. The prev_key and next_key elements are key names which should follow the convention 'node_foo' where foo is a UUID (ideally you can generate these sequentially, if not you can use some other type of UUID). This provides ordered access to your data.

Now if you need O(1) removal of a key, you can add a second index on the structure with key 'data' and value 'node_foo' for the right foo. Then you can perform the removal just as you would a linked list in memory. Remove the index node when you're done.

Now, keep in mind that concurrent modification of this list is just as bad as concurrent modification of any shared data structure. If you're using something like BDBs, you can use their (excellent) transaction support to avoid this. For something without transactions or concurrency control, you'll want to provide external locking or serialize accesses to a single thread.