[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15560441#comment-15560441
]
Amir Akhmedov commented on IGNITE-640:
--
I had a question about implementation details of this ticket.
In details it's said "The most natural way to implement such map, would be to
store every value under a separate key in an Ignite cache"
1. How about memory footprint in this approach? We need to create a separate
cache key for every value in multimap rather backing all the value for key
under some data structure?
2. Retrieving the data by index for key will be much difficult in case of value
removal e.g.
{{multimap.put(key, "one");
multimap.put(key, "two");
multimap.put(key, "three");
multimap.remove(key, "two");}}
In this case value "three" will have index 1 by Multimap API but internally
(Ignite side) it has index 2 and need to take extra steps to handle such cases
which hurt performance
For me, backing structure for values in ArrayList will be optimal way to go.
Please, advise?
> Implement IgniteMultimap data structures
>
>
> Key: IGNITE-640
> URL: https://issues.apache.org/jira/browse/IGNITE-640
> Project: Ignite
> Issue Type: Sub-task
> Components: data structures
>Reporter: Dmitriy Setrakyan
>Assignee: Amir Akhmedov
>
> We need to add {{IgniteMultimap}} data structure in addition to other data
> structures provided by Ignite. {{IgniteMultiMap}} should have similar API to
> {{java.util.Map}} class in JDK, but support the semantics of multiple values
> per key, similar to [Guava
> Multimap|http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimap.html].
>
> However, unlike in Guava, our multi-map should work with Lists, not
> Collections. Lists should make it possible to support the following methods:
> {code}
> // Gets value at a certain index for a key.
> V get(K, index);
> // Gets all values for a collection of keys at a certain index.
> Map getAll(Collection, index);
> // Gets values for specified indexes for a key.
> List get(K, Iterable indexes);
> // Gets all values for a collection of keys at specified indexes.
> Map getAll(Collection, Iterable indexes);
> // Gets values for specified range of indexes, between min and max.
> List get(K, int min, int max);
> // Gets all values for a collection of keys for a specified index range,
> between min and max.
> Map getAll(Collection, int min, int max);
> // Gets all values for a specific key.
> List get(K);
> // Gets all values for a collection of keys.
> Map getAll(Collection);
> // Iterate through all elements with a certain index.
> Iterator> iterate(int idx);
> // Do we need this?
> Collection get(K, IgniteBiPredicate)
> {code}
> Multimap should also support colocated and non-colocated modes, similar to
> [IgniteQueue|https://github.com/apache/incubator-ignite/blob/master/modules/core/src/main/java/org/apache/ignite/IgniteQueue.java]
> and its implementation,
> [GridAtomicCacheQueueImpl|https://github.com/apache/incubator-ignite/blob/master/modules/core/src/main/java/org/apache/ignite/internal/processors/datastructures/GridAtomicCacheQueueImpl.java].
> h2. Design Details
> The most natural way to implement such map, would be to store every value
> under a separate key in an Ignite cache. For example, let's say that we have
> a key {{K}} with multiple values: {{V0, V1, V2, ...}}. Then the cache should
> end up with the following values {{K0, V0}}, {{K1, V1}}, {{K2, V2}}, etc.
> This means that we need to wrap user key into our own, internal key, which
> will also have {{index}} field.
> Also note that we need to collocate all the values for the same key on the
> same node, which means that we need to define user key K as the affinity key,
> like so:
> {code}
> class MultiKey {
> @CacheAffinityMapped
> private K key;
> int index;
> }
> {code}
> Look ups of values at specific indexes becomes very simple. Just attach a
> specific index to a key and do a cache lookup. Look ups for all values for a
> key should work as following:
> {code}
> MultiKey key;
> V v = null;
> int index = 0;
> List res = new LinkedList<>();
> do {
> v = cache.get(MultiKey(K, index));
> if (v != null)
> res.add(v);
> index++;
> }
> while (v != null);
> return res;
> {code}
> We could also use batching for performance reason. In this case the batch
> size should be configurable.
> {code}
> int index = 0;
> List res = new LinkedList<>();
> while (true) {
> List batch = new ArrayList<>(batchSize);
> // Populate batch.
> for (; index < batchSize; index++)
> batch.add(new MultiKey(K, index % batchSize);
> Map batchRes = cache.getAll(batch);
> //
