Folks, please disregard my previous email. I confused the range search task when (the search boundaries are defined in a query) with the K largest elements problem described by Vladimir.
Personally, I don't think there is a practical need for partitioned sorted sets. Even if you store thousands of scores in a sorted set it will fit and perform nicely on a single node. If a read rate is high, then you can keep a full copy of the set on 2, 3, etc. nodes and load balance reads among the replicas. It should not be challenging to support such a data structure in Ignite. Rough idea: - You store a sorted set by a unique key in our system cache (or whenever we keep other data structures). - Configure a number of full replicas for the set across the cluster (if you want to load balance reads). - Updates: it might be too expensive to use Java SortedSet as the actual data structure on the nodes due to frequent serialization<->deserialization on updates. We can think of our version. - Reads: we need to figure out how to load balance reads across replicas. A naive approach can use some round-robin algorithm on the client-side. For instance, imagine we introduced IgniteSortedSet API and the client calls IgniteSortedSet.range(start, end) method. Internally, IgniteSortedSet implementation can maintain a variable that keeps an id of a server node whose turn is to serve the next request; the variable gets updated in the round-robin fashion. Btw, Redis SortedSet is not scalable or partitioned, and that's not a big deal: https://stackoverflow.com/questions/6948492/will-rediss-sorted-sets-scale - Denis On Fri, Sep 4, 2020 at 2:36 PM Valentin Kulichenko < valentin.kuliche...@gmail.com> wrote: > Hi Vladimir, > > As far as I know, Redis' SortedSet is not shared. Is this correct? Is it > even possible to support similar functionality for a partitioned dataset? > > -Val > > On Fri, Sep 4, 2020 at 8:58 AM Denis Magda <dma...@apache.org> wrote: > > > Hi Vladimir, > > > > Usually, LSM-storage engines serve the range searches the best (Cassandra > > is one of the examples). The SortedSet of Redis is one of the typical > > components you can find in LSM-engines. > > > > Presently, Ignite neither supports an LSM store nor a SortedSet data > > structure. However, the range searches with Ignite still have O(log(n)) > > complexity, it just takes more steps for the B-tree to collect all the > > records of a range. > > > > - > > Denis > > > > > > On Fri, Sep 4, 2020 at 3:26 AM Vladimir Pligin <vova199...@yandex.ru> > > wrote: > > > > > Hi Igniters, > > > > > > It seems that it's not possible to implement effective leader-board > with > > > the > > > current Ignite indexes. > > > Leader-board stores a score and an id of a player of some game. Score > is > > > indexed. One of the possible requests to that data structure is to get > > some > > > range of scores based on their rank (it's effectively a number of a > > row). I > > > suppose it's required for pagination. For example Redis has an index > > > (https://redis.io/topics/data-types#sorted-sets) that can be scanned > > > (https://redis.io/commands/zrange) to a particular line with O(log(n)) > > > complexity. As far as I know it's node-local. Correct me if I'm wrong > but > > > in > > > Ignite we scan an index until we find a row corresponding to a > > limit/offset > > > clause. It looks like a linear complexity. I suppose it could be > possible > > > to > > > implement it for REPLICATED caches and local queries. But it's really > > > difficult for me to estimate the efforts. By the way it would be useful > > for > > > analytical tools, most of them paginate. So what do you think is it > > > possible > > > to make that happen in Ignite and do we need it at all? Ignite 3.0 > maybe? > > > > > > > > > > > > -- > > > Sent from: http://apache-ignite-developers.2346864.n4.nabble.com/ > > > > > >
