This is an automated email from the ASF dual-hosted git repository.
alexey pushed a commit to branch branch-1.18.x
in repository https://gitbox.apache.org/repos/asf/kudu.git
The following commit(s) were added to refs/heads/branch-1.18.x by this push:
new 412e32eff KUDU-613: Remove use of vectors under lock
412e32eff is described below
commit 412e32eff93484db692667f8ba08df642b3f5586
Author: Mahesh Reddy <[email protected]>
AuthorDate: Fri Dec 6 18:10:33 2024 -0500
KUDU-613: Remove use of vectors under lock
Currently, the implementation of the SLRU cache returns
a vector of temporarily evicted entries to be reinserted
later. There are performance concerns with this approach
as it allocates and deallocates memory under the lock.
This patch refactors the code to not use a vector to deal
with the temporarily evicted entries.
Change-Id: I8f6a019c7c033c6c3dfef59b0f037e78f8264e68
Reviewed-on: http://gerrit.cloudera.org:8080/22181
Tested-by: Alexey Serbin <[email protected]>
Reviewed-by: Alexey Serbin <[email protected]>
(cherry picked from commit 33fd5e482b4854d23247af903c4263afc9931e59)
Reviewed-on: http://gerrit.cloudera.org:8080/22195
---
src/kudu/util/slru_cache.cc | 73 +++++++++++++++++++--------------------------
src/kudu/util/slru_cache.h | 28 ++++++++---------
2 files changed, 44 insertions(+), 57 deletions(-)
diff --git a/src/kudu/util/slru_cache.cc b/src/kudu/util/slru_cache.cc
index d6184453c..751d95404 100644
--- a/src/kudu/util/slru_cache.cc
+++ b/src/kudu/util/slru_cache.cc
@@ -45,7 +45,6 @@
DECLARE_bool(cache_force_single_shard);
DECLARE_double(cache_memtracker_approximation_ratio);
-using std::vector;
using Handle = kudu::Cache::Handle;
using EvictionCallback = kudu::Cache::EvictionCallback;
@@ -237,8 +236,8 @@ void SLRUCacheShard<segment>::Release(Handle* handle) {
}
}
-template<Segment segment>
-void SLRUCacheShard<segment>::RemoveEntriesPastCapacity() {
+template<>
+void SLRUCacheShard<Segment::kProbationary>::RemoveEntriesPastCapacity() {
while (usage_ > capacity_ && rl_.next != &rl_) {
SLRUHandle* old = rl_.next;
RL_Remove(old);
@@ -249,19 +248,6 @@ void SLRUCacheShard<segment>::RemoveEntriesPastCapacity() {
}
}
-template<Segment segment>
-void
SLRUCacheShard<segment>::SoftRemoveEntriesPastCapacity(vector<SLRUHandle*>*
evicted_entries) {
- while (usage_ > capacity_ && rl_.next != &rl_) {
- SLRUHandle* old = rl_.next;
- RL_Remove(old);
- table_.Remove(old->key(), old->hash);
- if (PREDICT_TRUE(metrics_)) {
- UpdateMetricsEviction(old->charge);
- }
- evicted_entries->emplace_back(old);
- }
-}
-
template<>
Handle* SLRUCacheShard<Segment::kProbationary>::Insert(SLRUHandle* handle,
EvictionCallback*
eviction_callback) {
@@ -292,8 +278,7 @@ Handle*
SLRUCacheShard<Segment::kProbationary>::Insert(SLRUHandle* handle,
}
template<>
-vector<SLRUHandle*>
SLRUCacheShard<Segment::kProtected>::InsertAndReturnEvicted(
- SLRUHandle* handle) {
+void SLRUCacheShard<Segment::kProtected>::UpgradeInsert(SLRUHandle* handle) {
handle->in_protected_segment.store(true, std::memory_order_relaxed);
if (PREDICT_TRUE(metrics_)) {
metrics_->upgrades->Increment();
@@ -307,16 +292,11 @@ vector<SLRUHandle*>
SLRUCacheShard<Segment::kProtected>::InsertAndReturnEvicted(
// No entries should exist with same key in protected segment when upgrading.
SLRUHandle* old_entry = table_.Insert(handle);
DCHECK(old_entry == nullptr);
-
- vector<SLRUHandle*> evicted_entries;
- SoftRemoveEntriesPastCapacity(&evicted_entries);
- return evicted_entries;
}
template<>
-Handle* SLRUCacheShard<Segment::kProtected>::ProtectedInsert(SLRUHandle*
handle,
- EvictionCallback*
eviction_callback,
-
vector<SLRUHandle*>* evictions) {
+Handle* SLRUCacheShard<Segment::kProtected>::UpdateInsert(SLRUHandle* handle,
+ EvictionCallback*
eviction_callback) {
handle->eviction_callback = eviction_callback;
// Two refs for the handle: one from SLRUCacheShard, one for the returned
handle.
// Even though this function is for updates in the protected segment, it's
treated similarly
@@ -341,7 +321,6 @@ Handle*
SLRUCacheShard<Segment::kProtected>::ProtectedInsert(SLRUHandle* handle,
FreeEntry(old_entry);
}
- SoftRemoveEntriesPastCapacity(evictions);
return reinterpret_cast<Handle*>(handle);
}
@@ -374,8 +353,8 @@ void SLRUCacheShard<segment>::Erase(const Slice& key,
uint32_t hash) {
}
}
-template<Segment segment>
-void SLRUCacheShard<segment>::SoftErase(const Slice& key, uint32_t hash) {
+template<>
+void SLRUCacheShard<Segment::kProbationary>::SoftErase(const Slice& key,
uint32_t hash) {
SLRUHandle* e = table_.Remove(key, hash);
if (e != nullptr) {
RL_Remove(e);
@@ -414,14 +393,10 @@ Handle* SLRUCacheShardPair::Insert(SLRUHandle* handle,
if (!ProtectedContains(handle->key(), handle->hash)) {
return probationary_shard_.Insert(handle, eviction_callback);
}
+ auto* inserted = protected_shard_.UpdateInsert(handle, eviction_callback);
// If newly inserted entry has greater charge than previous one,
// possible that entries can be evicted if at capacity.
- vector<SLRUHandle*> evictions;
- auto* inserted = protected_shard_.ProtectedInsert(handle, eviction_callback,
&evictions);
- for (auto it = evictions.begin(); it != evictions.end(); ++it) {
- SLRUHandle* evicted_entry = *it;
- probationary_shard_.ReInsert(evicted_entry);
- }
+ DowngradeEntries();
return inserted;
}
@@ -465,17 +440,13 @@ Handle* SLRUCacheShardPair::Lookup(const Slice& key,
uint32_t hash, bool caching
return probationary_handle;
}
- // Upgrade from the probationary segment.
- // Erase entry from the probationary segment then add entry to the protected
segment.
+ // Upgrade entry from the probationary segment by erasing it from the
+ // probationary segment then adding entry to the protected segment.
+ // Downgrade any entries in the protected segment if past capacity.
probationary_shard_.SoftErase(key, hash);
- vector<SLRUHandle*> evictions =
protected_shard_.InsertAndReturnEvicted(val_handle);
+ protected_shard_.UpgradeInsert(val_handle);
+ DowngradeEntries();
- // Go through all evicted entries from the protected segment and insert them
into
- // the probationary segment. Insert the LRU entries from the protected
segment first.
- for (auto it = evictions.begin(); it != evictions.end(); ++it) {
- SLRUHandle* evicted_entry = *it;
- probationary_shard_.ReInsert(evicted_entry);
- }
return probationary_handle;
}
@@ -504,6 +475,22 @@ bool SLRUCacheShardPair::ProtectedContains(const Slice&
key, uint32_t hash) {
return protected_shard_.Contains(key, hash);
}
+void SLRUCacheShardPair::DowngradeEntries() {
+ // Removes LRU entries of the protected shard while its usage exceeds its
capacity
+ // and reinserts them into the probationary shard.
+ while (protected_shard_.usage_ > protected_shard_.capacity_ &&
+ protected_shard_.rl_.next != &protected_shard_.rl_) {
+ SLRUHandle* lru_entry = protected_shard_.rl_.next;
+ protected_shard_.RL_Remove(lru_entry);
+ protected_shard_.table_.Remove(lru_entry->key(), lru_entry->hash);
+ if (PREDICT_TRUE(protected_shard_.metrics_)) {
+ protected_shard_.UpdateMetricsEviction(lru_entry->charge);
+ }
+ DCHECK(lru_entry);
+ probationary_shard_.ReInsert(lru_entry);
+ }
+}
+
ShardedSLRUCache::ShardedSLRUCache(size_t probationary_capacity, size_t
protected_capacity,
const std::string& id, const uint32_t
lookups)
: shard_bits_(DetermineShardBits()) {
diff --git a/src/kudu/util/slru_cache.h b/src/kudu/util/slru_cache.h
index 3aca5e0fb..6d8613868 100644
--- a/src/kudu/util/slru_cache.h
+++ b/src/kudu/util/slru_cache.h
@@ -115,16 +115,14 @@ class SLRUCacheShard {
void SetMetrics(SLRUCacheMetrics* metrics) { metrics_ = metrics; }
- // Inserts handle into shard and removes any entries if past capacity.
+ // Inserts handle into the probationary shard and removes any entries if
past capacity.
+ // Returns the inserted handle.
Handle* Insert(SLRUHandle* handle, EvictionCallback* eviction_callback);
- // Same as Insert but also returns any evicted entries.
- // Used when upgrading entry to protected segment.
- std::vector<SLRUHandle*> InsertAndReturnEvicted(SLRUHandle* handle);
- // Same as InsertAndReturnEvicted but it returns the inserted handle too.
- // Used for update case in protected segment.
- Handle* ProtectedInsert(SLRUHandle* handle,
- EvictionCallback* eviction_callback,
- std::vector<SLRUHandle*>* evictions);
+ // Inserts handle into the protected shard when upgrading entry from the
probationary segment.
+ void UpgradeInsert(SLRUHandle* handle);
+ // Inserts handle into the protected shard when updating entry in protected
segment.
+ // Returns the inserted handle.
+ Handle* UpdateInsert(SLRUHandle* handle, EvictionCallback*
eviction_callback);
// Like SLRUCache::Lookup, but with an extra "hash" parameter.
Handle* Lookup(const Slice& key, uint32_t hash, bool caching);
// Reduces the entry's ref by one, frees the entry if no refs are remaining.
@@ -136,8 +134,7 @@ class SLRUCacheShard {
void SoftErase(const Slice& key, uint32_t hash);
// Returns true if shard contains entry, false if not.
bool Contains(const Slice& key, uint32_t hash);
- // Like Insert but sets refs to 1 and no possibility for update case.
- // Used when evicted entries from protected segment are being added to
probationary segment.
+ // Inserts handle into the probationary shard when downgrading entry from
the protected segment.
void ReInsert(SLRUHandle* handle);
// Update the high-level metrics for a lookup operation.
void UpdateMetricsLookup(bool was_hit, bool caching);
@@ -145,6 +142,7 @@ class SLRUCacheShard {
void UpdateSegmentMetricsLookup(bool was_hit, bool caching);
private:
+ friend class SLRUCacheShardPair;
void RL_Remove(SLRUHandle* e);
void RL_Append(SLRUHandle* e);
// Update the recency list after a lookup operation.
@@ -156,10 +154,8 @@ class SLRUCacheShard {
void FreeEntry(SLRUHandle* e);
// Updates eviction related metrics.
void UpdateMetricsEviction(size_t charge);
- // Removes any entries past capacity.
+ // Removes any entries past capacity of the probationary shard.
void RemoveEntriesPastCapacity();
- // Adds any entries past capacity to a vector to be processed later.
- void SoftRemoveEntriesPastCapacity(std::vector<SLRUHandle*>*
evicted_entries);
// Update the memtracker's consumption by the given amount.
//
@@ -223,6 +219,10 @@ class SLRUCacheShardPair {
bool ProtectedContains(const Slice& key, uint32_t hash);
private:
+ // Remove any entries past capacity in the protected shard and insert them
into the probationary
+ // shard. As a result of inserting them into the probationary shard, the LRU
entries of the
+ // probationary shard will be evicted if the probationary shard's usage
exceeds its capacity.
+ void DowngradeEntries();
SLRUCacheShard<Segment::kProbationary> probationary_shard_;
SLRUCacheShard<Segment::kProtected> protected_shard_;
