You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "ASF subversion and git services (Jira)" <ji...@apache.org> on 2020/12/16 20:40:00 UTC
[jira] [Commented] (IMPALA-10127) LIRS enforcement of tombstone
limit has pathological performance scenarios
[ https://issues.apache.org/jira/browse/IMPALA-10127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17250627#comment-17250627 ]
ASF subversion and git services commented on IMPALA-10127:
----------------------------------------------------------
Commit ec6070aee012648ef1441ca4fbb11e485693bfdb in impala's branch refs/heads/master from Joe McDonnell
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=ec6070a ]
IMPALA-10391: Fix LIRS edge case for single unprotected entry
When an unprotected entry is not in the recency list, a
lookup will cause it to be moved to be the newest
entry in the unprotected list. The fix for IMPALA-10127
introduced a regression when this happens when there is
exactly on entry in the unprotected list.
The code currently calls RemoveFromUnprotectedList()
followed by AddToUnprotectedList(). This now fails
because it is doing these operations without manipulating
the num_unprotected_ count. RemoveFromUnprotectedList()
clears out unprotected_list_front_, because num_unprotected_
is 1. However, AddToUnprotectedList() does not set it
back, because it only does that if num_unprotected_ is 0,
and the count is not changing.
This skips the remove/add in this case if there is exactly
one unprotected entry in the list.
Testing:
- Added a backend test for this specific case and verfied
that it failed before the fix and passes now
Change-Id: I8d21b619811a1a7baab1a92790f2ffc03e949131
Reviewed-on: http://gerrit.cloudera.org:8080/16857
Reviewed-by: Joe McDonnell <jo...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>
> LIRS enforcement of tombstone limit has pathological performance scenarios
> --------------------------------------------------------------------------
>
> Key: IMPALA-10127
> URL: https://issues.apache.org/jira/browse/IMPALA-10127
> Project: IMPALA
> Issue Type: Bug
> Components: Backend
> Affects Versions: Impala 4.0
> Reporter: Joe McDonnell
> Assignee: Joe McDonnell
> Priority: Blocker
> Fix For: Impala 4.0
>
>
> LIRS maintains metadata for some tombstone entries that have been evicted from the cache (but might be seen again). To limit the memory used for these entries, the lirs_tombstone_multiple limits the total number of tombstone entries. The enforcement walks through the recency list from oldest to newest and removes tombstone entries until it is back underneath the limit. This requires it to go past a certain number of non-tombstone entries before it reaches a tombstone entry. There are pathological cases where this enforcement needs to walk past a very large number of entries before reaching a tombstone entry.
> Suppose that the cache never accesses the same entry more than once. Starting from empty, the first entries representing 95% of the capacity are automatically considered protected. The subsequent accesses are all unprotected. In order to dislodge a protected entry, an entry needs to accessed more than once. If every entry is unique, the protected entries are never touched again and form a contiguous block as the oldest entries on the recency list. Tombstone entries are above them, and unprotected elements are the newest entries on the recency list. It looks like this:
> Oldest
> Protected entries (representing 95% of cache capacity)
> ...
> Tombstone entries
> ...
> Unprotected entries (representing 5% of cache capacity)
> Newest
> To enforce the tombstone limit, it would need to pass all the protected entries to reach a single tombstone entry. I modified cache-bench to add a case with UNIFORM distribution but a 500x ratio of entries to the cache size. This shows pathological performance compared to the 3x ratio:
> {noformat}
> I0831 18:22:06.356406 2605 cache-bench.cc:180] Warming up...
> I0831 18:22:07.357687 2605 cache-bench.cc:183] Running benchmark...
> I0831 18:22:22.358944 2605 cache-bench.cc:191] UNIFORM ratio=3.00x n_unique=786432: 3.48M lookups/sec <---- FINE
> I0831 18:22:22.358958 2605 cache-bench.cc:192] UNIFORM ratio=3.00x n_unique=786432: 33.3% hit rate
> I0831 18:22:22.961802 2605 cache-bench.cc:180] Warming up...
> I0831 18:22:24.010735 2605 cache-bench.cc:183] Running benchmark...
> I0831 18:22:39.026588 2605 cache-bench.cc:191] UNIFORM ratio=500.00x n_unique=131072000: 1.31k lookups/sec <----- OUCH
> I0831 18:22:39.026614 2605 cache-bench.cc:192] UNIFORM ratio=500.00x n_unique=131072000: 0.2% hit rate{noformat}
> We should rework the enforcement of the tombstone limit to avoid walking past all those entries. One option is to keep the tombstone entries on their own list.
> Note that without the tombstone limit, this pathological case would use an unbounded amount of memory (because the tombstone entries would never be reach the bottom of the recency list and get removed).
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org