[jira] [Comment Edited] (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
]
Anton Vinogradov edited comment on IGNITE-640 at 9/7/18 9:10 AM:
-
[~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?
I can come up with solution to rename Set "header" classes to Map and reuse an
existing code as much as possible but I don't see how to combine the
implementation of Set and Map so far. Any thoughts?
was (Author: aakhmedov):
[~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?
I can come up with solution to rename Set "header" classes to Map and reuse an
existing code as much as possible but I don't see how to combine the
implementation of Set and Map so far. Any 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.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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 9/6/18 5:28 PM:
--
[~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?
I can come up with solution to rename Set "header" classes to Map and reuse an
existing code as much as possible but I don't see how to combine the
implementation of Set and Map so far. Any thoughts?
was (Author: aakhmedov):
[~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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 7/9/18 3:11 PM:
-
[~aakhmedov],
1) My idea is to implement multimap *extremely* close to set (just let set to
keep array instead of boolean), avoiding
- code duplication
- extra features like size inside GridCacheMapHeader. All extra features should
be implemented as an additional issue.
Some issues with current design:
- Now I see that multimap0 have the same design as queue0, instead of using
set0.
- compatibleCacheForMultimap is a 99% copy of compatibleCache.
- I see no reason to have special GridCacheMapItemKey it 100% equals to
GridCacheSetItemKey.
...
Overall,
1) I see no reason to use any code from queue. Please let me know in case I'm
wrong.
2) You should use and refactor set implementation to support multimap as well.
Avoid code duplication.
2.1) multimap is just a set with array, so I do not expect a lot of changes
inside GridCacheQueryManager or DataStructuresProcessor.
Refactor set's methods where necessary to support both structures.
2) >>I think it worth to add generic type for key into MapItemKey, without it
code in MultimapImpl looks a little odd.
What odd do you see?
3) I see codstyle issues, some tips:
{noformat}
MutableEntry> entry, Object... arguments) {
int size = 0;
/** newline **/
List list = entry.getValue();
/** newline **/
if (list == null) {
size = 1;
/** newline **/
list = getListInstance();
}
/** newline **/
list.add(value);
/** newline **/
entry.setValue(list);
/** newline **/
return new IgniteBiTuple<>(true, size);
{noformat}
was (Author: avinogradov):
[~aakhmedov],
1) My idea is to implement multimap *extremely* close to set (just let set to
keep array instead of boolean), avoiding
- code duplication
- extra features like size inside GridCacheMapHeader. All extra features should
be implemented as an additional issue.
Some issues with current design:
- Now I see that multimap0 have the same design as queue0, instead of using
set0.
- compatibleCacheForMultimap is a 99% copy of compatibleCache.
- I see no reason to have special GridCacheMapItemKey it 100% equals to
GridCacheSetItemKey.
...
Overall,
1) I see no reason to use any code from queue. Please let me know in case I'm
wrong.
2) You should use and refactor set implementation to support multimap as well.
Avoid code duplication.
2.1) multimap is just a set with array, so I do not expect a lot of changes
inside GridCacheQueryManager or DataStructuresProcessor.
Refactor set's methods where necessary to support both structures.
2) >>I think it worth to add generic type for key into MapItemKey, without it
code in MultimapImpl looks a little odd.
What odd do you see?
3) I see codstyle issues, some tips:
MutableEntry> entry, Object... arguments) {
int size = 0;
/** newline **/
List list = entry.getValue();
/** newline **/
if (list == null) {
size = 1;
/** newline **/
list = getListInstance();
}
/** newline **/
list.add(value);
/** newline **/
entry.setValue(list);
/** newline **/
return new IgniteBiTuple<>(true, size);
> 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.
>
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 7/9/18 3:09 PM:
-
[~aakhmedov],
1) My idea is to implement multimap *extremely* close to set (just let set to
keep array instead of boolean), avoiding
- code duplication
- extra features like size inside GridCacheMapHeader. All extra features should
be implemented as an additional issue.
Some issues with current design:
- Now I see that multimap0 have the same design as queue0, instead of using
set0.
- compatibleCacheForMultimap is a 99% copy of compatibleCache.
- I see no reason to have special GridCacheMapItemKey it 100% equals to
GridCacheSetItemKey.
...
Overall,
1) I see no reason to use any code from queue. Please let me know in case I'm
wrong.
2) You should use and refactor set implementation to support multimap as well.
Avoid code duplication.
2.1) multimap is just a set with array, so I do not expect a lot of changes
inside GridCacheQueryManager or DataStructuresProcessor.
Refactor set's methods where necessary to support both structures.
2) >>I think it worth to add generic type for key into MapItemKey, without it
code in MultimapImpl looks a little odd.
What odd do you see?
3) I see codstyle issues, some tips:
MutableEntry> entry, Object... arguments) {
int size = 0;
/** newline **/
List list = entry.getValue();
/** newline **/
if (list == null) {
size = 1;
/** newline **/
list = getListInstance();
}
/** newline **/
list.add(value);
/** newline **/
entry.setValue(list);
/** newline **/
return new IgniteBiTuple<>(true, size);
was (Author: avinogradov):
[~aakhmedov],
1) My idea is to implement multimap *extremely* close to set (just let set to
keep array instead of boolean), avoiding
- code duplication
- extra features like size inside GridCacheMapHeader. All extra features should
be implemented as an additional issue.
Some issues with current design:
Now I see that multimap0 have the same design as queue0, instead of using set0.
compatibleCacheForMultimap is a 99% copy of compatibleCache.
I see no reason to have special GridCacheMapItemKey it 100% equals to
GridCacheSetItemKey.
...
Overall,
1) I see no reason to use any code from queue. Please let me know in case I'm
wrong.
2) You should use and refactor set implementation to support multimap as well.
Avoid code duplication.
2.1) multimap is just a set with array, so I do not expect a lot of changes
inside GridCacheQueryManager or DataStructuresProcessor.
Refactor set's methods where necessary to support both structures.
2) >>I think it worth to add generic type for key into MapItemKey, without it
code in MultimapImpl looks a little odd.
What odd do you see?
3) I see codstyle issues, some tips:
MutableEntry> entry, Object... arguments) {
int size = 0;
/** newline **/
List list = entry.getValue();
/** newline **/
if (list == null) {
size = 1;
/** newline **/
list = getListInstance();
}
/** newline **/
list.add(value);
/** newline **/
entry.setValue(list);
/** newline **/
return new IgniteBiTuple<>(true, size);
> 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);
>
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 7/9/18 3:08 PM:
-
[~aakhmedov],
1) My idea is to implement multimap *extremely* close to set (just let set to
keep array instead of boolean), avoiding
- code duplication
- extra features like size inside GridCacheMapHeader. All extra features should
be implemented as an additional issue.
Some issues with current design:
Now I see that multimap0 have the same design as queue0, instead of using set0.
compatibleCacheForMultimap is a 99% copy of compatibleCache.
I see no reason to have special GridCacheMapItemKey it 100% equals to
GridCacheSetItemKey.
...
Overall,
1) I see no reason to use any code from queue. Please let me know in case I'm
wrong.
2) You should use and refactor set implementation to support multimap as well.
Avoid code duplication.
2.1) multimap is just a set with array, so I do not expect a lot of changes
inside GridCacheQueryManager or DataStructuresProcessor.
Refactor set's methods where necessary to support both structures.
2) >>I think it worth to add generic type for key into MapItemKey, without it
code in MultimapImpl looks a little odd.
What odd do you see?
3) I see codstyle issues, some tips:
MutableEntry> entry, Object... arguments) {
int size = 0;
/** newline **/
List list = entry.getValue();
/** newline **/
if (list == null) {
size = 1;
/** newline **/
list = getListInstance();
}
/** newline **/
list.add(value);
/** newline **/
entry.setValue(list);
/** newline **/
return new IgniteBiTuple<>(true, size);
was (Author: avinogradov):
[~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.
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 7/6/18 5:11 AM:
--
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.
PR: [https://github.com/apache/ignite/pull/4207]
was (Author: aakhmedov):
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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 5/21/18 12:41 PM:
---
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, which may contain another multimap/queue/set instances.
{{IgniteQueue}} avoids full cache scan by using elements indexing (see
{{IgniteCacheQueueAdapter#itemKey}}), {{IgniteSet}} maintains plain Java sets
(see {{CacheDataStructuresManager#setData}}). May be this behavior should be
documented or discussed.
- 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}
was (Author: xtern):
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.
- 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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 5/21/18 11:13 AM:
---
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.
- 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}
was (Author: xtern):
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
>
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 5/21/18 11:04 AM:
---
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 interested
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) We sould nod use \{{System.out.println("Filter [key: " + k + ", v: " +
v);}}, use logger instead.
9) 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.
was (Author: avinogradov):
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 interested
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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 5/17/18 4:18 PM:
--
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 interested
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.
was (Author: avinogradov):
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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 5/7/18 2:52 PM:
---
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. I
would appreciate if failures would be double-checked.
was (Author: dpavlov):
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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 8/14/16 6:46 PM:
---
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
[jira] [Comment Edited] (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 edited comment on IGNITE-640 at 3/1/16 2:20 PM:
Some thoughts about possible multimap 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}
was (Author: ruskim):
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?
>
