[
https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=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<K, List<V>>) 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<K, V> getAll(Collection<K>, index);
> // Gets values for specified indexes for a key.
> List<V> get(K, Iterable<Integer> indexes);
> // Gets all values for a collection of keys at specified indexes.
> Map<K, Collection<V>> getAll(Collection<K>, Iterable<Integer> indexes);
> // Gets values for specified range of indexes, between min and max.
> List<V> get(K, int min, int max);
> // Gets all values for a collection of keys for a specified index range,
> between min and max.
> Map<K, Collection<V>> getAll(Collection<K>, int min, int max);
> // Gets all values for a specific key.
> List<V> get(K);
> // Gets all values for a collection of keys.
> Map<K, List<V>> getAll(Collection<K>);
> // Iterate through all elements with a certain index.
> Iterator<Map.Entry<K, V>> iterate(int idx);
> // Do we need this?
> Collection<IgniteTuple<Integer V>> get(K, IgniteBiPredicate<Integer, V>)
> {code}
> Multimap should also support colocated and non-colocated modes, similar to
> [IgniteQueue|https://github.com/apache/incubator-ignite/blob/master/modules/core/src/main/java/org/apache/ignite/IgniteQueue.java]
> and its implementation,
> [GridAtomicCacheQueueImpl|https://github.com/apache/incubator-ignite/blob/master/modules/core/src/main/java/org/apache/ignite/internal/processors/datastructures/GridAtomicCacheQueueImpl.java].
> h2. Design Details
> The most natural way to implement such map, would be to store every value
> under a separate key in an Ignite cache. For example, let's say that we have
> a key {{K}} with multiple values: {{V0, V1, V2, ...}}. Then the cache should
> end up with the following values {{K0, V0}}, {{K1, V1}}, {{K2, V2}}, etc.
> This means that we need to wrap user key into our own, internal key, which
> will also have {{index}} field.
> Also note that we need to collocate all the values for the same key on the
> same node, which means that we need to define user key K as the affinity key,
> like so:
> {code}
> class MultiKey<K> {
> @CacheAffinityMapped
> private K key;
> int index;
> }
> {code}
> Look ups of values at specific indexes becomes very simple. Just attach a
> specific index to a key and do a cache lookup. Look ups for all values for a
> key should work as following:
> {code}
> MultiKey key;
> V v = null;
> int index = 0;
> List<V> res = new LinkedList<>();
> do {
> v = cache.get(MultiKey(K, index));
> if (v != null)
> res.add(v);
> index++;
> }
> while (v != null);
> return res;
> {code}
> We could also use batching for performance reason. In this case the batch
> size should be configurable.
> {code}
> int index = 0;
> List<V> res = new LinkedList<>();
> while (true) {
> List<Key> batch = new ArrayList<>(batchSize);
> // Populate batch.
> for (; index < batchSize; index++)
> batch.add(new MultiKey(K, index % batchSize);
> Map<Key, V> batchRes = cache.getAll(batch);
> // Potentially need to properly sort values, based on the key order,
> // if the returning map does not do it automatically.
> res.addAll(batchRes.values());
> if (res.size() < batch.size())
> break;
> }
> return res;
> {code}
> 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)
