Return-Path: X-Original-To: apmail-ignite-issues-archive@minotaur.apache.org Delivered-To: apmail-ignite-issues-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 54C6D182EA for ; Fri, 13 Nov 2015 12:11:11 +0000 (UTC) Received: (qmail 4570 invoked by uid 500); 13 Nov 2015 12:11:11 -0000 Delivered-To: apmail-ignite-issues-archive@ignite.apache.org Received: (qmail 4517 invoked by uid 500); 13 Nov 2015 12:11:11 -0000 Mailing-List: contact issues-help@ignite.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@ignite.apache.org Delivered-To: mailing list issues@ignite.apache.org Received: (qmail 4497 invoked by uid 99); 13 Nov 2015 12:11:11 -0000 Received: from arcas.apache.org (HELO arcas) (140.211.11.28) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 13 Nov 2015 12:11:11 +0000 Received: from arcas.apache.org (localhost [127.0.0.1]) by arcas (Postfix) with ESMTP id EF39D2C1F57 for ; Fri, 13 Nov 2015 12:11:10 +0000 (UTC) Date: Fri, 13 Nov 2015 12:11:10 +0000 (UTC) From: "Amir Akhmedov (JIRA)" To: issues@ignite.apache.org Message-ID: In-Reply-To: References: Subject: [jira] [Assigned] (IGNITE-640) Implement IgniteMultimap data structures MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-JIRA-FingerPrint: 30527f35849b9dde25b450d4833f0394 [ https://issues.apache.org/jira/browse/IGNITE-640?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Amir Akhmedov reassigned IGNITE-640: ------------------------------------ Assignee: Amir Akhmedov > 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. > Collection 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. > Collection 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. > Collection get(K); > // Gets all values for a collection of keys. > Map> getAll(Collection); > 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)