[ https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Dmitriy Setrakyan updated IGNITE-640: ------------------------------------- Description: 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 values for specified indexes for a key. Collection<V> get(K, Iterable<Integer> indexes); // Gets values for specified range of indexes, between min and max. Collection<V> get(K, int min, int max); // Gets all values for a specific key. Collection<V> get(K); {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<K> { @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<V> 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<V> res = new LinkedList<>(); while (true) { List<Key> batch = new ArrayList<>(batchSize); // Populate batch. for (; index < batchSize; index++) batch.add(new MultiKey(K, index % batchSize); Map<Key, V> batchRes = cache.getAll(batch); // Potentially need to properly sort values, based on the key order, // if the returning map does not do it automatically. res.addAll(batchRes.values()); if (res.size() < batch.size()) break; } return res; {code} was: 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 values for specified indexes for a key. Collection<V> get(K, Iterable<Integer> indexes); // Gets values for specified range of indexes, between min and max. Collection<V> get(K, int min, int max); // Gets all values for a specific key. Collection<V> get(K); {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<K> { @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<V> 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<V> res = new LinkedList<>(); while (true) { List<Key> batch = new ArrayList<>(batchSize); // Populate batch. for (; index < batchSize; index++) batch.add(new MultiKey(K, index % batchSize); Map<Key, V> batchRes = cache.getAll(batch); // Potentially need to properly sort values, based on the key order, // if the returning map does not do it automatically. res.addAll(batchRes.values()); if (res.size() < batch.size()) break; } return res; {code} > 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: Vladisav Jelisavcic > > 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 values for specified indexes for a key. > Collection<V> get(K, Iterable<Integer> indexes); > // Gets values for specified range of indexes, between min and max. > Collection<V> get(K, int min, int max); > // Gets all values for a specific key. > Collection<V> get(K); > {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<K> { > @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<V> 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<V> res = new LinkedList<>(); > while (true) { > List<Key> batch = new ArrayList<>(batchSize); > // Populate batch. > for (; index < batchSize; index++) > batch.add(new MultiKey(K, index % batchSize); > Map<Key, V> batchRes = cache.getAll(batch); > // Potentially need to properly sort values, based on the key order, > // if the returning map does not do it automatically. > res.addAll(batchRes.values()); > if (res.size() < batch.size()) > break; > } > return res; > {code} -- This message was sent by Atlassian JIRA (v6.3.4#6332)