Hello Tim Armstrong, Impala Public Jenkins,
I'd like you to reexamine a change. Please visit
http://gerrit.cloudera.org:8080/16597
to look at the new patch set (#2).
Change subject: IMPALA-10127: Fix performance for enforcement of
lirs_tombstone_multiple
......................................................................
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
---
M be/src/util/cache/cache-bench.cc
M be/src/util/cache/lirs-cache.cc
M bin/run-all-tests.sh
3 files changed, 171 insertions(+), 64 deletions(-)
git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/97/16597/2
--
To view, visit http://gerrit.cloudera.org:8080/16597
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: I25b697f57c7daacccf8791a5a7b31878a6f7f1d2
Gerrit-Change-Number: 16597
Gerrit-PatchSet: 2
Gerrit-Owner: Joe McDonnell <joemcdonn...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins <impala-public-jenk...@cloudera.com>
Gerrit-Reviewer: Joe McDonnell <joemcdonn...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <tarmstr...@cloudera.com>
