| /** |
| * Licensed to the Apache Software Foundation (ASF) under one |
| * or more contributor license agreements. See the NOTICE file |
| * distributed with this work for additional information |
| * regarding copyright ownership. The ASF licenses this file |
| * to you under the Apache License, Version 2.0 (the |
| * "License"); you may not use this file except in compliance |
| * with the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, |
| * software distributed under the License is distributed on an |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| * KIND, either express or implied. See the License for the |
| * specific language governing permissions and limitations |
| * under the License. |
| **/ |
| |
| #include "storage/EvictionPolicy.hpp" |
| |
| #include <algorithm> |
| #include <array> |
| #include <atomic> |
| #include <chrono> |
| #include <unordered_map> |
| #include <unordered_set> |
| #include <vector> |
| |
| #include "storage/StorageBlockInfo.hpp" |
| #include "storage/StorageConstants.hpp" |
| #include "threading/Mutex.hpp" |
| #include "threading/SpinMutex.hpp" |
| #include "threading/SpinSharedMutex.hpp" |
| #include "utility/Macros.hpp" |
| |
| #include "glog/logging.h" |
| |
| using std::chrono::duration_cast; |
| using std::chrono::high_resolution_clock; |
| using std::chrono::time_point; |
| using std::chrono::microseconds; |
| |
| namespace quickstep { |
| |
| EvictionPolicy::Status EvictAnyBlockEvictionPolicy::chooseBlockToEvict(block_id* block) { |
| MutexLock lock(mutex_); |
| if (nonreferenced_blocks_.empty()) { |
| return Status::kBlockNotFound; |
| } |
| std::unordered_set<block_id>::const_iterator it = nonreferenced_blocks_.begin(); |
| *block = *it; |
| ref_counts_.erase(*it); |
| nonreferenced_blocks_.erase(it); |
| return Status::kOk; |
| } |
| |
| void EvictAnyBlockEvictionPolicy::blockCreated(const block_id block) { |
| MutexLock lock(mutex_); |
| ref_counts_[block] = 0; |
| nonreferenced_blocks_.insert(block); |
| } |
| |
| void EvictAnyBlockEvictionPolicy::blockEvicted(const block_id block) { |
| MutexLock lock(mutex_); |
| ref_counts_.erase(block); |
| nonreferenced_blocks_.erase(block); |
| } |
| |
| void EvictAnyBlockEvictionPolicy::blockReferenced(const block_id block) { |
| MutexLock lock(mutex_); |
| if (ref_counts_[block]++ == 0) { |
| // Since the ref count was 0, the block might be in nonreferenced_blocks_ |
| nonreferenced_blocks_.erase(block); |
| } |
| } |
| |
| void EvictAnyBlockEvictionPolicy::blockUnreferenced(const block_id block) { |
| MutexLock lock(mutex_); |
| DEBUG_ASSERT(ref_counts_.find(block) != ref_counts_.end()); |
| DEBUG_ASSERT(ref_counts_[block] > 0); |
| if (--ref_counts_[block] == 0) { |
| nonreferenced_blocks_.insert(block); |
| } |
| } |
| |
| unsigned int EvictAnyBlockEvictionPolicy::getRefCount(const block_id block) { |
| MutexLock lock(mutex_); |
| DEBUG_ASSERT(ref_counts_.find(block) != ref_counts_.end()); |
| return ref_counts_[block]; |
| } |
| |
| EvictionPolicy::Status UniformRandomEvictionPolicy::chooseBlockToEvict(block_id* block) { |
| MutexLock lock(mutex_); |
| if (nonreferenced_blocks_.empty()) { |
| return Status::kBlockNotFound; |
| } |
| std::uniform_int_distribution<> rng(0, nonreferenced_blocks_.size() - 1); |
| std::vector<block_id>::iterator block_it = nonreferenced_blocks_.begin() + rng(gen_); |
| *block = *block_it; |
| ref_counts_.erase(*block); |
| nonreferenced_blocks_.erase(block_it); |
| return Status::kOk; |
| } |
| |
| void UniformRandomEvictionPolicy::blockCreated(const block_id block) { |
| MutexLock lock(mutex_); |
| ref_counts_[block] = 0; |
| nonreferenced_blocks_.push_back(block); |
| } |
| |
| void UniformRandomEvictionPolicy::blockEvicted(const block_id block) { |
| MutexLock lock(mutex_); |
| if (ref_counts_.erase(block) != 0) { |
| // The only way a block could be in nonreferenced_blocks_ is if it were |
| // first referenced and then later unreferenced. Thus, we only need to |
| // check nonreferenced_blocks_ if it had an entry in ref_counts_. |
| // Further, if it had an entry in ref_counts_, it must have an entry in |
| // nonreferenced_blocks_, unless it was evicted with a non-zero ref count, |
| // which is an error. |
| std::vector<block_id>::iterator it = std::find(nonreferenced_blocks_.begin(), nonreferenced_blocks_.end(), block); |
| DEBUG_ASSERT(it != nonreferenced_blocks_.end()); |
| nonreferenced_blocks_.erase(it); |
| } |
| } |
| |
| void UniformRandomEvictionPolicy::blockReferenced(const block_id block) { |
| MutexLock lock(mutex_); |
| std::unordered_map<block_id, unsigned int>::iterator it = ref_counts_.find(block); |
| if (it == ref_counts_.end()) { |
| ref_counts_[block] = 1; |
| } else if (++(it->second) == 1) { |
| // If we already had a ref count of 0 for the block, then it must be in nonreferenced_blocks_, since that could |
| // only happen if the block were referenced and then unreferenced back to 0. |
| std::vector<block_id>::iterator it = std::find(nonreferenced_blocks_.begin(), nonreferenced_blocks_.end(), block); |
| DEBUG_ASSERT(it != nonreferenced_blocks_.end()); |
| nonreferenced_blocks_.erase(it); |
| } |
| } |
| |
| void UniformRandomEvictionPolicy::blockUnreferenced(const block_id block) { |
| MutexLock lock(mutex_); |
| DEBUG_ASSERT(ref_counts_.find(block) != ref_counts_.end()); |
| DEBUG_ASSERT(ref_counts_[block] > 0); |
| if (--ref_counts_[block] == 0) { |
| nonreferenced_blocks_.push_back(block); |
| } |
| } |
| |
| unsigned int UniformRandomEvictionPolicy::getRefCount(const block_id block) { |
| MutexLock lock(mutex_); |
| DEBUG_ASSERT(ref_counts_.find(block) != ref_counts_.end()); |
| return ref_counts_[block]; |
| } |
| |
| /** |
| * @brief This class provides the implementation of the LRU-k eviction |
| * policy. It is a template parameterized on K, the number of references to keep |
| * for each block. |
| **/ |
| template<std::size_t K> |
| class LRUKEvictionPolicyImpl : public EvictionPolicy { |
| public: |
| explicit LRUKEvictionPolicyImpl(const microseconds correlated_reference_period); |
| ~LRUKEvictionPolicyImpl() override { } |
| EvictionPolicy::Status chooseBlockToEvict(block_id* block) override; |
| void blockCreated(const block_id block) override; |
| void blockEvicted(const block_id block) override; |
| void blockReferenced(const block_id block) override; |
| void blockUnreferenced(const block_id block) override; |
| void blockDeleted(const block_id block) override; |
| unsigned int getRefCount(const block_id block) override; |
| |
| private: |
| struct BlockInfo { |
| /** |
| * Array of the last K references. ref_list_[0] refers to the most recent |
| * access, ref_list_[1] to the second most recent, and so on. This only |
| * records references that did not take place within the same Correlated |
| * Reference Period. These times are drawn from |
| * std::chrono::high_resolution_clock. |
| **/ |
| std::array<time_point<high_resolution_clock>, K> ref_list_; |
| |
| /** |
| * Time of the last reference regardless of whether it occurred within the |
| * Correlated Reference Period of the previous reference. |
| */ |
| time_point<high_resolution_clock> last_reference_; |
| |
| /** |
| * How many references are outstanding on this block. |
| */ |
| std::atomic<unsigned int> ref_count_; |
| |
| /** |
| * Whether or not this block is currently in memory. |
| */ |
| std::atomic<bool> in_memory_; |
| |
| /** |
| * A mutex protecting ref_list_ and last_reference_. |
| */ |
| mutable SpinSharedMutex<false> time_mutex_; |
| |
| BlockInfo() |
| : ref_count_(0), in_memory_(false) { |
| ref_list_.fill(time_point<high_resolution_clock>::min()); |
| } |
| |
| /** |
| * @brief Increments the reference count for a block, marks the block as |
| * in memory, and records a new reference time. |
| * |
| * @param correlated_reference_period The correlated reference period of |
| * the parent LRU-K eviction policy. |
| * @return True if reference count was zero before this call (meaning the |
| * caller should erase this block from nonreferenced_blocks_). |
| **/ |
| bool blockReferencedHelper(const microseconds correlated_reference_period) { |
| time_point<high_resolution_clock> time = high_resolution_clock::now(); |
| SpinSharedMutexExclusiveLock<false> lock(time_mutex_); |
| if (in_memory_.load()) { |
| // Block was already in buffer pool. |
| if (time - last_reference_ > correlated_reference_period) { |
| addReferenceTime(time, true); |
| } |
| } else { |
| // Block was just brought into the buffer pool, possibly after an |
| // eviction. |
| addReferenceTime(time, false); |
| in_memory_.store(true); |
| } |
| last_reference_ = time; |
| return (ref_count_++ == 0); |
| } |
| |
| private: |
| /** |
| * @brief Adds a new time as the most recent non-correlated reference. Does |
| * not update last_reference_. Also adjusts the previous reference |
| * times by moving them up |
| * @param time The new time to add. |
| **/ |
| inline void addReferenceTime(const time_point<high_resolution_clock> &time, |
| const bool currently_in_memory) { |
| // Move existing reference times back while also adjusting them for the |
| // correlated reference period of this block |
| if (currently_in_memory) { |
| const microseconds corrl_period = duration_cast<microseconds>(last_reference_ - ref_list_[0]); |
| for (int i = ref_list_.size() - 1; i > 0; --i) { |
| ref_list_[i] = ref_list_[i - 1] + corrl_period; |
| } |
| } else { |
| for (int i = ref_list_.size() - 1; i > 0; --i) { |
| ref_list_[i] = ref_list_[i - 1]; |
| } |
| } |
| // Now add the new reference to the front |
| ref_list_[0] = time; |
| } |
| |
| DISALLOW_COPY_AND_ASSIGN(BlockInfo); |
| }; |
| |
| /** |
| * @brief Compares two BlockInfo objects A and B as follows: |
| * (1) If the time since A's last reference is greater than the correlated reference period and B's is not, |
| * A < B |
| * (2) Otherwise, A < B iff A's Kth most recent reference < B's Kth most recent reference. |
| * @return true iff lhs < rhs |
| */ |
| class BlockInfoComparator { |
| public: |
| const time_point<high_resolution_clock> time_; |
| const microseconds correlated_reference_period_; |
| |
| BlockInfoComparator( |
| const time_point<high_resolution_clock> time, |
| const microseconds correlated_reference_period) |
| : time_(time), correlated_reference_period_(correlated_reference_period) { } |
| |
| inline bool operator()(const BlockInfo& lhs, const BlockInfo& rhs) { |
| time_point<high_resolution_clock> lhs_last, rhs_last, lhs_next_last, rhs_next_last; |
| { |
| SpinSharedMutexSharedLock<false> lhs_lock(lhs.time_mutex_); |
| lhs_last = lhs.last_reference_; |
| lhs_next_last = lhs.ref_list_[K - 1]; |
| } |
| { |
| SpinSharedMutexSharedLock<false> rhs_lock(rhs.time_mutex_); |
| rhs_last = rhs.last_reference_; |
| rhs_next_last = rhs.ref_list_[K - 1]; |
| } |
| |
| bool lhs_past_corrl_period = time_ - lhs_last > correlated_reference_period_; |
| bool rhs_past_corrl_period = time_ - rhs_last > correlated_reference_period_; |
| if (lhs_past_corrl_period == rhs_past_corrl_period) { |
| return lhs_next_last < rhs_next_last; |
| } else { |
| return lhs_past_corrl_period; |
| } |
| } |
| }; |
| |
| std::unordered_map<block_id, BlockInfo> blocks_; |
| alignas(kCacheLineBytes) SpinSharedMutex<false> blocks_mutex_; |
| const microseconds correlated_reference_period_; |
| std::unordered_set<block_id> nonreferenced_blocks_; |
| SpinMutex nonreferenced_blocks_mutex_; |
| |
| #ifdef QUICKSTEP_DEBUG |
| /** |
| * @brief Prints the contents of the LRUKEvictionPolicyImpl. Use this |
| * strictly for debugging purposes. |
| * WARNING: This method is not safe as it does not acquire |
| * any mutexes on the internal state variable, so use it |
| * primarily for debugging purposes. |
| * |
| * @param print_map If true, print the eviction map. |
| * @param print_nr_list If true, print the list of non referenced blocks. |
| * |
| */ |
| void printState(const bool print_map, const bool print_nr_list) const { |
| if (print_map) { |
| LOG(INFO) << "Eviction Policy Map (" << blocks_.size() << " entries: "; |
| |
| for (const auto& it : blocks_) { |
| LOG(INFO) << "[" << it.first // print the block number |
| << ", " << it.second.ref_count_ << "] "; // and the ref count |
| } |
| |
| LOG(INFO) << "\n"; |
| } |
| |
| if (print_nr_list) { |
| // Print the non-referenced block list |
| LOG(INFO) << "Non referenced block list is: "; |
| |
| for (const block_id nonref_block : nonreferenced_blocks_) { |
| LOG(INFO) << nonref_block << "; "; |
| } |
| |
| LOG(INFO) << "\n"; |
| } |
| } |
| #endif |
| |
| DISALLOW_COPY_AND_ASSIGN(LRUKEvictionPolicyImpl); |
| }; |
| |
| template<std::size_t K> |
| LRUKEvictionPolicyImpl<K>::LRUKEvictionPolicyImpl( |
| const microseconds correlated_reference_period) |
| : correlated_reference_period_(correlated_reference_period) { } |
| |
| template<std::size_t K> |
| EvictionPolicy::Status LRUKEvictionPolicyImpl<K>::chooseBlockToEvict(block_id* block) { |
| const BlockInfo *smallest_blockinfo = nullptr; |
| BlockInfoComparator cmp(high_resolution_clock::now(), correlated_reference_period_); |
| |
| SpinSharedMutexSharedLock<false> blocks_read_lock(blocks_mutex_); |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| block_id ret; |
| { |
| for (const block_id nonref_block : nonreferenced_blocks_) { |
| const BlockInfo &blockinfo = blocks_[nonref_block]; |
| if (blockinfo.in_memory_.load()) { |
| if ((smallest_blockinfo == nullptr || cmp(blockinfo, *smallest_blockinfo))) { |
| smallest_blockinfo = &blockinfo; |
| ret = nonref_block; |
| } |
| } |
| } |
| } |
| |
| if (smallest_blockinfo == nullptr) { |
| return Status::kBlockNotFound; |
| } else { |
| *block = ret; |
| |
| #ifdef QUICKSTEP_DEBUG |
| if (blocks_[*block].ref_count_ != 0) { |
| LOG(INFO) << "Block " << *block |
| << " has nonzero reference count. Printing state...\n"; |
| printState(true, true); |
| } |
| #endif |
| DEBUG_ASSERT(blocks_[*block].ref_count_ == 0); |
| blocks_[*block].in_memory_.store(false); |
| nonreferenced_blocks_.erase(*block); |
| return Status::kOk; |
| } |
| } |
| |
| template<std::size_t K> |
| void LRUKEvictionPolicyImpl<K>::blockCreated(const block_id block) { |
| SpinSharedMutexExclusiveLock<false> blocks_write_lock(blocks_mutex_); |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| |
| // 'blocks_[block]' will be implicitly default-constructed below. Set |
| // 'in_memory_' to true initially. |
| blocks_[block].in_memory_.store(true); |
| |
| // Block is initially nonreferenced. |
| nonreferenced_blocks_.insert(block); |
| } |
| |
| template<std::size_t K> |
| void LRUKEvictionPolicyImpl<K>::blockEvicted(const block_id block) { |
| SpinSharedMutexSharedLock<false> blocks_read_lock(blocks_mutex_); |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| DEBUG_ASSERT(blocks_[block].ref_count_ == 0); |
| blocks_[block].in_memory_.store(false); |
| nonreferenced_blocks_.erase(block); |
| } |
| |
| template<std::size_t K> |
| void LRUKEvictionPolicyImpl<K>::blockReferenced(const block_id block) { |
| bool block_known = false; |
| { |
| SpinSharedMutexSharedLock<false> read_lock(blocks_mutex_); |
| typename std::unordered_map<block_id, BlockInfo>::iterator it = blocks_.find(block); |
| if (it != blocks_.end()) { |
| block_known = true; |
| |
| // Need to protect the access to "ref_count", so grab the mutex. |
| // Note we need to grab this outside the loop as "blockReferencedHelper" |
| // changes the "ref_count." |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| if (it->second.blockReferencedHelper(correlated_reference_period_)) { |
| nonreferenced_blocks_.erase(block); |
| } |
| } |
| } |
| if (!block_known) { |
| SpinSharedMutexExclusiveLock<false> blocks_write_lock(blocks_mutex_); |
| |
| // As above, need to protect access to ref_count, so grab the mutex. |
| // Note we need to grab this outside the loop as "blockReferencedHelper" |
| // changes the "ref_count." |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| if (blocks_[block].blockReferencedHelper(correlated_reference_period_)) { |
| nonreferenced_blocks_.erase(block); |
| } |
| } |
| } |
| |
| template<std::size_t K> |
| void LRUKEvictionPolicyImpl<K>::blockUnreferenced(const block_id block) { |
| SpinSharedMutexSharedLock<false> read_lock(blocks_mutex_); |
| DEBUG_ASSERT(blocks_.find(block) != blocks_.end()); |
| DEBUG_ASSERT(blocks_[block].ref_count_ > 0); |
| BlockInfo& blockinfo = blocks_[block]; |
| |
| // Need to protect the access to "ref_count", so grab the mutex. |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| if (--blockinfo.ref_count_ == 0) { |
| nonreferenced_blocks_.insert(block); |
| } |
| } |
| |
| template<std::size_t K> |
| void LRUKEvictionPolicyImpl<K>::blockDeleted(const block_id block) { |
| SpinSharedMutexExclusiveLock<false> write_lock(blocks_mutex_); |
| SpinMutexLock nonreferenced_blocks_lock(nonreferenced_blocks_mutex_); |
| blocks_.erase(block); |
| nonreferenced_blocks_.erase(block); |
| } |
| |
| template<std::size_t K> |
| unsigned int LRUKEvictionPolicyImpl<K>::getRefCount(const block_id block) { |
| SpinSharedMutexSharedLock<false> read_lock(blocks_mutex_); |
| DEBUG_ASSERT(blocks_.find(block) != blocks_.end()); |
| return blocks_[block].ref_count_.load(); |
| } |
| |
| EvictionPolicy* LRUKEvictionPolicyFactory::ConstructLRUKEvictionPolicy( |
| const size_t k, |
| const microseconds correlated_reference_period) { |
| switch (k) { |
| case 1: |
| return new LRUKEvictionPolicyImpl<1>( |
| correlated_reference_period); |
| break; |
| case 2: |
| return new LRUKEvictionPolicyImpl<2>( |
| correlated_reference_period); |
| break; |
| case 3: |
| return new LRUKEvictionPolicyImpl<3>( |
| correlated_reference_period); |
| break; |
| default: |
| FATAL_ERROR("LRU-k only supports k = 1, 2, or 3"); |
| } |
| } |
| |
| } // namespace quickstep |