[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17002045#comment-17002045
]
Amir Akhmedov commented on IGNITE-640:
--
[~dmagda], removed my name from assignees.
> 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
>Priority: Major
> Fix For: 2.9
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=17001038#comment-17001038
]
Denis A. Magda commented on IGNITE-640:
---
[~aakhmedov], are you planning to continue with this task? If you don't have
time for it any longer, we would let another contributor pick the task up.
> 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
>Priority: Major
> Fix For: 2.9
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16946867#comment-16946867
]
Maxim Muzafarov commented on IGNITE-640:
Moved to 2.9 due to inactivity. Please, feel free to move it back if you will
be able to complete the ticket by 2.8 code freeze date, December 2, 2019.
> 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
>Priority: Major
> Fix For: 2.9
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16835610#comment-16835610
]
Vishal Patel commented on IGNITE-640:
-
Is this issue still in progress, can I checkout source for this requirement,
and I can fix whatever is left, can anyone provide more details on this.
> 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
>Priority: Major
> Fix For: 2.8
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16626697#comment-16626697
]
Amir Akhmedov commented on IGNITE-640:
--
[~NIzhikov], I don't think it's feasible to include it into 2.7.
> 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
>Priority: Major
> Fix For: 2.8
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16623485#comment-16623485
]
Nikolay Izhikov commented on IGNITE-640:
[~aakhmedov], [~avinogradov] Do we have a chance to resolve this ticket until
the code freeze of 2.7?
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16606873#comment-16606873
]
Anton Vinogradov commented on IGNITE-640:
-
[~aakhmedov]
As discussed privately, let's just remove {{extends AbstractCollection}} at
{{GridCacheSetImpl}}, this should solve the issue.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16606116#comment-16606116
]
Amir Akhmedov commented on IGNITE-640:
--
[~avinogradov],
In this [#comment-16520147] you mentioned to create an **AbsractMap** that
IgniteSet and IgniteMultimap could inherit. But the problem is IgniteSet
already extends AbstractCollection. Do you think it's still an option to have a
common abstract parent class for both Set and Multimap?
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16595159#comment-16595159
]
Amir Akhmedov commented on IGNITE-640:
--
[~avinogradov],
Work in progress, will have something to share by next week
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16538346#comment-16538346
]
Anton Vinogradov commented on IGNITE-640:
-
1) We have to implement one improvement at a time.
In case you want to make size faster, lets do this for set to, but later and
inside another issue.
Pending issues:
IGNITE-7823 - almost ready to be merged (hope, we'll merge it tomorrow)
IGNITE-5553 - should be ready in two weeks.
Anyway, we can fix it after your commit (multimap and set will be fixed
together)
2) Generic type for key into MapItemKey sounds ok in case it will not cause
huge code refactor.
3) I sent you an email with contacts and possible periods.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16538061#comment-16538061
]
Amir Akhmedov commented on IGNITE-640:
--
[~avinogradov],
1) I need size field in {{GridCacheMapHeader}} to make {{size()}} faster
otherwise for the collocated map we have to iterate over all maps to count the
size of target map.
2) I made {{multimap0}} similar to to {{queue0}} because its implementation
more natural and clean than {{set0}}. At the moment of my initial
implementation there was no talk about removal of {{setDataMap}} in
{{IgniteSet}} and I wanted to avoid such design flaw. I think once we start
work on IGNITE-5553 {{set0}} will be much similar to {{multimap0}} and it will
be good time to converge {{set0()}} and {{multimap0()}} into one method e.g.
{{map0()}} and thus avoid a code dupe.
>> compatibleCacheForMultimap is a 99% copy of compatibleCache.
Agree, will fix it soon
>> I see no reason to have special GridCacheMapItemKey it 100% equals to
>>GridCacheSetItemKey.
I do not see two classes, as you suggested I renamed GridCacheSetItemKey to
GridCacheMapItemKey.
>> I see no reason to use any code from queue
In general, all {{queue()}}, {{set()}}, {{multimap()}} are similar in
{{CacheDataStructuresManager}} and {{DataStructuresProcessor}} except
daastructure removal in queue/multimap handled through continuous query and in
set through infamous {{setDataMap}}
>> You should use and refactor set implementation to support multimap as well.
>>Avoid code duplication.
Agree but IMHO first one of the implementations should go first either
IGNITE-640 or IGNITE-5553. Today, multimap and set are two different
implementations.
>> What odd do you see?
e.g. in {{GridCacheMultimapImpl::getAll}} I need to make casting like this
{{(Map>) getAll0(keys)}}
Please let me know your thoughts.
P.S. do you mind to have a chat/call through gitter/Skype to discuss the
details? Sometimes 5 minutes of chat can be more productive than long running
email chains. Please, do not hesitate to directly email me if you mind to have
a chat/call.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16536807#comment-16536807
]
Anton Vinogradov commented on IGNITE-640:
-
[~aakhmedov],
will check in the near future.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16534428#comment-16534428
]
Amir Akhmedov commented on IGNITE-640:
--
Hi [~avinogradov],
I made a changes discussed above, please check them.
I think it worth to add generic type for key into MapItemKey, without it code
in MultimapImpl looks a little odd.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16526192#comment-16526192
]
Anton Vinogradov commented on IGNITE-640:
-
[~aakhmedov]
1) gate.enter() operates on readLock, which means it guarantee that all
operations will be finished before we'll perform some critical operation with
writeLock.
2) Better case is to use structures I listed as is.
I expect no changes at these classes, except names.
Even having that IGNITE-7823 almost ready to be merged I think that we can
rename classes as a part of this issue, this should not cause real problems at
merge.
3) Since we decided how to fix IGNITE-5553 it's a good idea to "merge" Multimap
and Set.
Both will be eventually "fixed" at IGNITE-5553.
So, as far as I understand we agreed that Multimap should be implemented based
on IgniteSet.
Common parts will be extracted to abstract classes and same datastructures will
be used.
Correct?
P.s. In case you see some more optimisation of IgniteSet (except onheap
duplication removal), let's discuss them.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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);
>
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16523955#comment-16523955
]
Amir Akhmedov commented on IGNITE-640:
--
[~avinogradov],
Yes, I followed the ideas from {{IgniteQueue}} since I found its implementation
more clean and natural. {{IgniteSet}}'s implementation really polluted with the
maintenance of {{setDataMap}}
# Regarding the size, in general I followed how it's working today in
IgniteQueue. I understand that at some point of time you will see inconsistent
data between actual map's size and {{size()}} but I think {{gate.enter()}} call
in {{GridCacheMultimapProxy}} should help at least not to see a big deference
in values of actual vs {{size()}}. Or am I wrong on capabilities of
{{gate.enter()}}?
# Right, and I think you are right, I will rename
{{CollocatedMultimapItemKey}} and others to **Map** so we could reuse them
latter when re-implement {{IgniteSet}}. I don't think it's a good idea to make
changes for two tickets in one pull request
# Absolutely agree with you. There was no intention to change {{IgniteSet}}
when I started to work on this ticket that's why I separated the logic into
{{DataStructuresProcessor#getMultimap}} but right now I can extract them out
into a base class so they could be reused in both {{IgniteMultimap}} and
{{IgniteSet}}
Please let me know your thoughts. If you are fine then I'll start working on
changes discussed above.
> 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
>Priority: Major
> Fix For: 2.7
>
>
> 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
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16520147#comment-16520147
]
Anton Vinogradov commented on IGNITE-640:
-
[~aakhmedov],
I checked your solution and found you made multimap similar to IgniteQueue.
Could you please explain reasons to choosing such approach?
Some issues with such approach:
1) multimap.size() is not consistent.
"Add" and "set sise" are two sparated atomic operations, so it's possible to
have 1M keys inside multimap, but see size 1K.
2)You duplicated all IgniteQueue structures
- CollocatedMultimapItemKey
- GridCacheMultimapHeader
- GridCacheMultimapHeaderKey
- GridCacheMultimapItemKey
- MultimapItemKey
3) You added methods almost equals to IgniteSet's methods to "cast" IgniteQueue
to IgniteMultimap.
For example
org.apache.ignite.internal.processors.datastructures.DataStructuresProcessor#getCollection
->
org.apache.ignite.internal.processors.datastructures.DataStructuresProcessor#getMultimap
I'm proposing to refactor this implementation to use IgniteSet as a base
1) size() method can be shared between IgniteSet and IgniteMultimap without
modifications
2) IgniteSet's datastructures
- CollocatedSetItemKey
- SetItemKey
- GridCacheSetHeader
- GridCacheSetHeaderKey
- GridCacheSetItemKey
can be reused without modification. You can rename them to ***Map***.
3) As far as I can see, all you need to do in that case is to implement
GridCacheMultimapImpl based on GridCacheAbstractMapImpl.
GridCacheAbstractMapImpl will contains methods shared between IgniteMultimap
and IgniteSet in that case , eg. size() or clear().
Thoughts?
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16515756#comment-16515756
]
Pavel Pereslegin commented on IGNITE-640:
-
[~aakhmedov], [~avinogradov]
I left comments on
[upsource|https://reviews.ignite.apache.org/ignite/review/IGNT-CR-649] and I
think that you should include multimap in these common data structure tests:
{noformat}
IgniteDataStructureUniqueNameTest
IgnitePersistentStoreDataStructuresTest
IgniteClientDataStructuresAbstractTest
IgniteClientReconnectApiExceptionTest
IgniteClientReconnectCollectionsTest
IgniteAtomicLongChangingTopologySelfTest
{noformat}
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16514979#comment-16514979
]
Amir Akhmedov commented on IGNITE-640:
--
New pull request created [https://github.com/apache/ignite/pull/4207]
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16514973#comment-16514973
]
ASF GitHub Bot commented on IGNITE-640:
---
GitHub user amirakhmedov opened a pull request:
https://github.com/apache/ignite/pull/4207
IGNITE-640: Implement IgniteMultimap data structures
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/amirakhmedov/ignite IGNITE-640-1
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/ignite/pull/4207.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #4207
commit 28164b3795dda4c8833f66aa2aaf632fd45c7925
Author: Amir Akhmedov
Date: 2018-06-17T03:05:35Z
IGNITE-640: Implement IgniteMultimap data structures
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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);
> // Potentially need to properly sort values, based on the key order,
> // if the returning map does not do it automatically.
>
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16501233#comment-16501233
]
Amir Akhmedov commented on IGNITE-640:
--
Hi [~avinogradov],
Thanks for your time to review and comment my changes. Please find below my
comments:
# I think Map and Set look similar at first glance but in general they
implement two different interfaces which has nothing in common. In terms of
Ignite we can build similar infrastructure on CacheDataStructuresManager and
DataStructuresProcessor levels but I doubt we can come up with generic easy
maintainable design for both of them.
# Agree. I could say the methods queue0 and multimap0 in
CacheDataStructuresManager are identical and would be nice to merge them into
one but I can't make my mind how to do this cause despite having the similar
flow those methods operate with different object types, arguments, predicates
etc. If you have an idea how to converge them would be happy to listen to it.
# Fixed.
# Fixed in most places. Will look more carefully in next days.
# Fixed.
# Sorry, I'm not following. Can you please put more details how
GridCacheMultimapApiSelfAbstractTest could be shortened?
# Fixed.
# Fixed.
# I tried my best and did something wrong, now my PR looks ugly :) I don't
know can it be reverted back or not.
Please let me know if you have any other inquiries or concerns.
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16480732#comment-16480732
]
Pavel Pereslegin commented on IGNITE-640:
-
Hi [~aakhmedov], [~avinogradov].
In GridCacheMultimapImpl I noticed some things that you should pay attention to.
- Iterator of collocated multimap can be slow because it performs full scan of
shared cache (with another multimap instances). May be this should be described
in docs.
- Close operation of non-collocated multimap does not waits for the result of
cache destroy operation (may be it's ok).
- Also I noticed a few calls
{code:java}cctx.kernalContext().cache().internalCache(cctx.name()).get(hdrKey){code}
that can be simplified with
{code:java}cctx.cache().get(hdrKey){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: Amir Akhmedov
>Priority: Major
> Fix For: 2.6
>
>
> 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);
> // 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())
>
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16479283#comment-16479283
]
Anton Vinogradov commented on IGNITE-640:
-
Hi, [~aakhmedov]
I made a brief review, here's some comments:
0) We have an issue IGNITE-7823 which affects your changes.
Added Issue as related.
BTW, current assignee have some issues with implementation, do you intereasted
to fix this too?
1) I see some architecture duplication.
{{Map}} and {{Set}} is the same thing, I think.
So, it will be a good idea to have some common implementation and {{set}} +
{{map}} based on it.
2) Also, I see you made changes similar to {{Queue}} code.
It will be nice to fix this duplication too.
3) I see some codestyle issues.
Main point is that each semantic unit should be separated by new line.
Example:
{code:java}
/** {@inheritDoc} */
@Override public List get(K key, int min, int max) {
try {
List list = cache.get(itemKey(key));
//newline
if (list == null)
return Collections.emptyList();
//newline
return IntStream.rangeClosed(min, max)
.mapToObj(list::get)
.collect(toList());
}
catch (IgniteCheckedException e) {
throw U.convertException(e);
}
}
{code}
4) Currently java8 features allowed only at tests.
That does not mean you should replace all code by java7 code.
My proposal is to discuss this one more time.
previous discussion:
[http://apache-ignite-developers.2346864.n4.nabble.com/Use-of-lambdas-and-other-Java-8-features-td27671.html#a27674]
let's continue it
I agree that
{code:java}
return IntStream.rangeClosed(min, max)
.mapToObj(list::get)
.collect(toList());
{code}
looks better than java7 code, but not sure it has same speed.
5) I see duplication at tests, for example
{{GridCacheLocalAtomicCollocatedMultimapApiSelfTest}} pretty similar to
{{GridCacheLocalAtomicNonCollocatedMultimapApiSelfTest}}.
6) I see duplication at GridCacheMultimapApiSelfAbstractTest, looks like this
test can be shorten.
Here is ans example how to make test smaller:
{{org.apache.ignite.internal.processors.cache.CrossCacheTxRandomOperationsTest#cacheOperation}}
7) I see some lines commented
{code:java}
//multimap1.close();
//multimap2.close();
//multimap3.close();
{code}
final patch should not contain commented lines.
8) I created Upsource review to see you code at IDEA, but Upsource works bad
with merges from master (which you have at branch), so, following request's
goal it to make my review easy ;)
Could you please merge current master to your branch and then squash your
branch with force commit (to gain only one commit with your changes). This will
allow Upsource show same changes as at PR.
You should not make any more merges or squashes after that, this will break
Upsource again. Each subsequent fix should be as a separate commit. Thanks.
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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)
>
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16474001#comment-16474001
]
Dmitriy Pavlov commented on IGNITE-640:
---
Hi [~avinogradov],
I would appreciate if you take a look to this fix.
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16465983#comment-16465983
]
Dmitriy Pavlov commented on IGNITE-640:
---
Hi [~aakhmedov], I've checked tests, there are several suspicious failures
- .NET: IgniteParityTest.TestIgnite[ (fail rate
0,0%)|https://ci.ignite.apache.org/project.html?projectId=IgniteTests24Java8=8364830731500038749=pull%2F3926%2Fhead=testDetails]
- 2 times
- IgniteClientTestSuite: ClientReconnectionSelfTest.testNoFailedReconnection[
(fail rate
0,0%)|https://ci.ignite.apache.org/project.html?projectId=IgniteTests24Java8=-3141249888117413735=pull%2F3926%2Fhead=testDetails]
-IgniteCacheQuerySelfTestSuite3:
CacheContinuousWithTransformerReplicatedSelfTest.testContinuousWithTransformerAndRegularListenerAsync[
(fail rate
0,0%)|https://ci.ignite.apache.org/project.html?projectId=IgniteTests24Java8=4610502389755369639=pull%2F3926%2Fhead=testDetails]
- IgniteBinarySimpleNameMapperBasicTestSuite:
StopNodeOrHaltFailureHandlerTest.testJvmHalted[ (fail rate
0,0%)|https://ci.ignite.apache.org/project.html?projectId=IgniteTests24Java8=2179356000860350976=pull%2F3926%2Fhead=testDetails]
- IgniteCacheTestSuite4:
CacheGetEntryOptimisticReadCommittedSeltTest.testPartitionedTransactional[
(fail rate
0,0%)|https://ci.ignite.apache.org/project.html?projectId=IgniteTests24Java8=3635582098648232308=pull%2F3926%2Fhead=testDetails]
These failures are not defenetely caused by this change, but it may be, so I
would appreciate if failures would be double-checked.
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=16459702#comment-16459702
]
Amir Akhmedov commented on IGNITE-640:
--
Hi All,
Could someone please check my pull request?
PR: [https://github.com/apache/ignite/pull/3926]
TC Run:
[https://ci.ignite.apache.org/viewLog.html?buildId=1255210=buildResultsDiv=IgniteTests24Java8_RunAll]
> 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
>Priority: Major
> Fix For: 2.6
>
>
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15637143#comment-15637143
]
Dmitriy Setrakyan commented on IGNITE-640:
--
I actually cannot think of a reason why I didn't suggest {{ArrayList-based}}
implementation immediately. I agree that indexed access and removals will be
implemented much easier this way.
Unless there are any objections, I would switch to the {{key-to-ArrayList}}
mappings.
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map.
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15623754#comment-15623754
]
Denis Magda commented on IGNITE-640:
The memory footprint will be negligible. However, the second concern about the
removal sounds reasonable to me. [~dsetrakyan], do you see how the design
proposed by you can handle a removal based on key and val efficiently, so that
there is no need to update all the indexes if we remove a value in the middle
of the "list"?
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
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);
> //
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15420877#comment-15420877
]
Amir Akhmedov commented on IGNITE-640:
--
Dmitriy, one interface is used as a base interface. Besides list-based I also
provided interfaces for set-based for constant check, fetch operations and
sortedset-based to keep the keys and values in order
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15420776#comment-15420776
]
Dmitriy Setrakyan commented on IGNITE-640:
--
In my view the list-based multi-map should be enough and efficiently covers all
the use cases. What is the purpose of having 3 different interfaces?
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15420437#comment-15420437
]
Amir Akhmedov commented on IGNITE-640:
--
I'm proposing IgniteMultimap interface to be as Guava has: IgniteMultimap is a
base interface and also there will be 3 derived interfaces: IgniteListMultimap,
IgniteSetMultimap, IgniteSortedSetMultimap. All 3 subinterfaces will have
Atomic and Transactional implementations.
Please review it, any comments and concerns will be highly appreciated.
{code:title=IgniteMultimap.java|borderStyle=solid}
public interface IgniteMultimap extends Closeable {
/**
* Returns collection of values to which the specified key is mapped,
* or empty collection if this multimap contains no mapping for the key.
*
* @param key the key whose associated values are to be returned
* @return the list of values to which the specified key is mapped,
* or empty collection if this multimap contains no mapping for the key.
* @throws ClassCastException if the key is of an inappropriate type for
this multimap
*/
public Collection get(K key);
/**
* Returns the list of values for a collection of keys to which the keys
are mapped.
* Empty collection will be added to resulting list if this multimap
contains no mapping for the key.
* @param keys collection of keys
* @return the list of values for a collection of keys to which the keys
are mapped.
* Empty collection will be added to resulting list if this multimap
contains no mapping for the key.
* @throws ClassCastException if the key is of an inappropriate type for
this multimap
*/
public Map getAll(Collection keys);
/**
* Clears the multimap. Removes all key-value pairs.
*/
public void clear();
/**
* Returns {@code true} if this multimap contains a mapping for the
specified key.
*
* @param key key whose presence in this multimap is to be tested
* @return {@code true} if this multimap contains a mapping for the
specified key
* @throws ClassCastException if the key is of an inappropriate type for
this multimap
*/
public boolean containsKey(K key);
/**
* Returns {@code true} if this multimap contains at least one key-value
pair
* with the value {@code value}.
*
* @param value value whose presence in this multimap is to be tested
* @return {@code true} if this multimap contains at least one key-value
pair
* with the value {@code value}.
* @throws ClassCastException if the key is of an inappropriate type for
this multimap
*/
public boolean containsValue(V value);
/**
* Returns whether the multimap contains the given key-value pair.
*
* @param key key whose presence in this multimap is to be tested
* @param value value whose presence in this multimap is to be tested
*
* @return {@code true} if the multimap contains the key-value pair, {@code
false} otherwise
* @throws ClassCastException if the key is of an inappropriate type for
this multimap
*/
public boolean containsEntry(K key, V value);
/**
* Returns a {@link Collection} view of the mappings contained in this
multimap.
*
* @return a {@link Collection} view of the mappings contained in this
multimap.
*/
public Collection> entries();
/**
* Returns the locally owned set of keys.
*
* @return the locally owned set of keys.
*/
public Set localKeySet();
/**
* Returns a {@link Set} view of the keys contained in this multimap.
*
* @return a {@link Set} view of the keys contained in this multimap.
*/
public Set keySet();
/**
* Associates the specified value with the specified key in this multimap
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return {@code true} if the method increased the size of the multimap, or
* {@code false} if the multimap already contained the key-value pair and
* doesn't allow duplicates
* @throws ClassCastException if the class of the specified key or value
* prevents it from being stored in this multimap
*/
public boolean put(K key, V value);
/**
* Stores a key-value pair in this multimap for each of {@code values}, all
* using the same key, {@code key}. Equivalent to (but expected to be more
* efficient than):{@code
*
* for (V value : values) {
* put(key, value);
* }}
*
* In particular, this is a no-op if {@code values} is empty.
*
* @return {@code true} if the multimap changed
* @throws ClassCastException if the class of the specified key or value
* prevents it from being stored in
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15420426#comment-15420426
]
Amir Akhmedov commented on IGNITE-640:
--
Discussion thread:
http://apache-ignite-developers.2346864.n4.nabble.com/IGNITE-640-IgniteMultimap-interface-draft-version-td10659.html
> 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);
> // 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}
> h2. Evictions
> Evictions in the {{IgniteMultiMap}} should have 2 levels: maximum number of
> keys, and maximum number of values for a key. The maximum number of keys
> should be controlled by Ignite standard eviction policy. The maximum number
> of values for a key should be controlled by the implementation of the
> multi-map. Either eviction parameter should be configurable.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15175427#comment-15175427
]
Yakov Zhdanov commented on IGNITE-640:
--
Hi Konstantin!
Very good start!
I have reviewed
https://github.com/apache/ignite/compare/master...ruskim:ignite-640?expand=1
and here are my comments.
1. I don't think we need busy lock in the map. I don't see in in IgniteSet or
IgniteQueue either. Can you please point me to the usages in data structures?
2. IgniteMultimap interface should be documented and contain "public" modifiers
for members. Please take a look at IgniteQueue, for instance, and be consistent.
3. I don't like ArrayLists as values. They will often have 1-2-3 elements. I
would use exact size arrays. This way we avoid unnecessary memory overhead. Or
investigate use single-linked list structure. Maybe we should provide an
ability to choose the backing structure. I.e. if map is not supposed to change
very often then arrays seems to be perfect.
4. Using "key" provided by user as map key is not correct. You can end up with
the situation when several multimaps can backed by the same cache. This way you
require keys to be unique across all maps. Please see GridCacheQueueItemKey or
GridCacheSetItemKey
5. Can I ask you to fully design multimap interface and then send notice to dev
list so others can review?
6. I would also think of providing support for comparable values.
Yakov
> 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: Konstantin Margorin
>
> 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}
>
[jira] [Commented] (IGNITE-640) Implement IgniteMultimap data structures
[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel=15173717#comment-15173717
]
Konstantin Margorin commented on IGNITE-640:
Some thoughts possible multimap about implementation.
According to above suggestion we shell use cache with specially constructed key:
{code}
class MultiKey {
@CacheAffinityMapped
private K key;
int index;
}
{code}
Method {{put(K key, V value)}} should created MultiKey for a new value. We
should know new index value for MultiKey construction in the {{put}} method.
The simplest implementation will use another {{Cache indexCache}} to
keep count of items with key K.
So, pseudo-code for put will look like
{code}
put(K key, V value)
{
try (Transaction tx = Ignition.ignite().transactions().txStart()) {
newIndex = indexCache.get(key) + 1;
indexCache.put(key, newIndex);
multikeyCache.put(new MultiKey(key, newIndex), value);
tx.commit()
}
}
{code}
The problem here is that we use:
- {{transaction}}
- one {{get}}
- two {{put}}
cache operations for one Multikey {{put}} operation. It looks like big overhead.
Dmitriy suggested another way:
{quote}
An alternative way would be to store Key to List, i. e. to store Lists
directly in cache. Then we can use EntryProcessor to add/remove elements to the
list. The only problem here is that we will not be able to update the existing
lists, but rather clone the lists, so we can add/remove elements to it, but I
still think it will be cheaper than using transactions.
{quote}
> 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: Konstantin Margorin
>
> 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<>();
