[jira] [Commented] (IMPALA-10127) LIRS enforcement of tombstone limit has pathological performance scenarios

["ASF subversion and git services (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/IMPALA-10127?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17214431#comment-17214431 ] 

ASF subversion and git services commented on IMPALA-10127:
----------------------------------------------------------

Commit 7b42e9a4391f8177ed6674f68efa7df5f526cd25 in impala's branch refs/heads/master from Joe McDonnell
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=7b42e9a ]

IMPALA-10127: Fix performance for enforcement of lirs_tombstone_multiple

When enforcing lirs_tombstone_multiple for the LIRS cache,
currently it needs to walk backwards through the recency
list to find the oldest tombstone entry to remove it.
This traversal can involve passing a large number of
non-tombstone entries. In pathological cases, it is
O(N) where N is the number of entries in the cache.

This modifies the LIRS implementation to use a combined
unprotected and tombstone list. The first half of the
list is unprotected entries. The second half is tombstone
entries. The tombstone portion of the list allows the
enforcement for the lirs_tombstone_multiple to be O(1)
when finding the oldest tombstone entry.

The unprotected half of the list operates as it did
before, except that the combined list requires maintaining
a pointer to the front of the unprotected list (i.e. the
boundary between the unprotected portion and the tombstone
portion).

Using a combined list means that evicting an unprotected
entry to become a tombstone entry is only updating a
pointer. This is a common operation, so it keeps the
overhead of the tombstone list low.

Performance:
For all existing performance test cases in cache-bench,
lookups/sec are within 2% of the current implementation of LIRS.

This adds a new pathological case to cache-bench where
the cache hit rate is 0.2%. This causes extensive use
of the lirs_tombstone_multiple. This case sees a 2000x
improvement, going from 1.3K lookups/sec to 2.96M lookups/sec.

Testing:
 - lirs-cache-test passes (debug and release)
 - This also adds the DATA_CACHE_EVICTION_POLICY environment
   variable to run-all-tests.sh to allow easy testing with LIRS.
 - Ran a core job with 500MB cache using LIRS

Change-Id: I25b697f57c7daacccf8791a5a7b31878a6f7f1d2
Reviewed-on: http://gerrit.cloudera.org:8080/16597
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
>
> 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