You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@ignite.apache.org by Mikhail Cherkasov <mc...@gridgain.com> on 2017/06/23 18:25:40 UTC
GridCacheAdapter#size() has O(n) complexity
Hi all,
GridCacheAdapter#size() has O(n) complexity and this can lead for delays
during metric collection( https://issues.apache.org/jira/browse/IGNITE-5521
).
It validates all elements in near cache while count them, so it takes O(n),
but java doc requires:
"Gets the number of all entries cached on this node. This method will
return the count of all cache entries and has O(1) complexity on base
IgniteInternalCache. It is essentially the size of cache key set and is
semantically identical to {Cache.keySet().size().
NOTE: this operation is not distributed and returns only the number of
entries cached on this node."
I see two solutions for this:
1. add special method for metrics that will have relaxed accuracy, but with
O(1) complexity
I implemented this solution there:
https://github.com/gridgain/apache-ignite/commit/a68dd81090884d07bd737cbbf48e5f64e9cd27ec
2. or completely remove entries validation for size method.
What is better solution? Thoughts?
--
Thanks,
Mikhail.
Re: GridCacheAdapter#size() has O(n) complexity
Posted by Dmitriy Setrakyan <ds...@apache.org>.
On Mon, Jun 26, 2017 at 2:31 AM, Yakov Zhdanov <yz...@apache.org> wrote:
> Guys, I see little inconsistency. Imagine user does 1000 puts with near
> cache enabled. Then user does some gets() and size() returns 1000 + N, more
> gets() and size() is 1000 + M. This is a bit weird. Can we have nearSize()
> on public API? Any thoughts here?
>
Completely agree. Cache size should not include near size. Near size should
be a separate count. The size, on the other hand, should always return the
actual size of the cache on the server side.
>
> As far as the original issue I would not bother with validity check on
> getting size and just return raw map size.
>
Agree.
>
> --Yakov
>
Re: GridCacheAdapter#size() has O(n) complexity
Posted by Yakov Zhdanov <yz...@apache.org>.
Guys, I see little inconsistency. Imagine user does 1000 puts with near
cache enabled. Then user does some gets() and size() returns 1000 + N, more
gets() and size() is 1000 + M. This is a bit weird. Can we have nearSize()
on public API? Any thoughts here?
As far as the original issue I would not bother with validity check on
getting size and just return raw map size.
--Yakov
Re: GridCacheAdapter#size() has O(n) complexity
Posted by Dmitriy Setrakyan <ds...@apache.org>.
Hm... why not just return the key count? Can we really have nulls in the
near cache?
On Fri, Jun 23, 2017 at 8:25 PM, Mikhail Cherkasov <mc...@gridgain.com>
wrote:
> Hi all,
>
> GridCacheAdapter#size() has O(n) complexity and this can lead for delays
> during metric collection( https://issues.apache.org/
> jira/browse/IGNITE-5521
> ).
> It validates all elements in near cache while count them, so it takes O(n),
> but java doc requires:
>
> "Gets the number of all entries cached on this node. This method will
> return the count of all cache entries and has O(1) complexity on base
> IgniteInternalCache. It is essentially the size of cache key set and is
> semantically identical to {Cache.keySet().size().
> NOTE: this operation is not distributed and returns only the number of
> entries cached on this node."
>
>
> I see two solutions for this:
>
> 1. add special method for metrics that will have relaxed accuracy, but with
> O(1) complexity
> I implemented this solution there:
> https://github.com/gridgain/apache-ignite/commit/
> a68dd81090884d07bd737cbbf48e5f64e9cd27ec
>
> 2. or completely remove entries validation for size method.
>
> What is better solution? Thoughts?
>
> --
> Thanks,
> Mikhail.
>