page_evictioner_selector.hpp

Go to the documentation of this file.

#ifndef __PAGE_EVICTIONER_SELECTOR_HPP
#define __PAGE_EVICTIONER_SELECTOR_HPP

#include <mutex>

#include <atomic>

#include "cds/container/fcqueue.h"
#include "cds/container/fcstack.h"
#include "MPMCQueue/MPMCQueue.h"
#include <vector>

#include "hashtable_deque.hpp"

#include "buffer_pool.hpp"

namespace zero::buffer_pool {

    class PageEvictionerSelector {
    protected:
        explicit PageEvictionerSelector(const BufferPool* bufferPool) :
                _maxBufferpoolIndex(bufferPool->getBlockCount() - 1) {};

    public:
        virtual ~PageEvictionerSelector() {};

        virtual bf_idx select() noexcept = 0;

        virtual void updateOnPageHit(bf_idx idx) noexcept = 0;

        virtual void updateOnPageUnfix(bf_idx idx) noexcept = 0;

        virtual void updateOnPageMiss(bf_idx idx, PageID pid) noexcept = 0;

        virtual void updateOnPageFixed(bf_idx idx) noexcept = 0;

        virtual void updateOnPageDirty(bf_idx idx) noexcept = 0;

        virtual void updateOnPageBlocked(bf_idx idx) noexcept = 0;

        virtual void updateOnPageSwizzled(bf_idx idx) noexcept = 0;

        virtual void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept = 0;

        virtual void updateOnPointerSwizzling(bf_idx idx) noexcept = 0;

        virtual void releaseInternalLatches() noexcept = 0;

    protected:
        bf_idx _maxBufferpoolIndex;
    };

    template<uint32_t retry_list_check_ppm/* = 1000000*/, uint32_t initial_list_check_ppm/* = 10000*/>
    class PageEvictionerSelectorQuasiFIFOLowContention : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorQuasiFIFOLowContention(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _notExplicitlyEvictedList(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            static thread_local bool currentlyCheckingRetryList;
            static thread_local size_t retriedBufferIndexes;

            bf_idx selected;
            while (true) {
                if (!currentlyCheckingRetryList) {   // This thread checked the front of the _initialList last:
                    if (retriedBufferIndexes < static_cast<bf_idx>(_initialListCheck * _initialList.size())
                        || _retryList.empty()) {       // Check again the front of the _initialList:
                        _initialList.pop(selected);
                        retriedBufferIndexes++;
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    } else {                        // Change to checking entries from the front of the _retryList
                        _retryList.pop(selected);
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            retriedBufferIndexes = 0;
                            currentlyCheckingRetryList = true;
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    }
                } else {                            // This thread checked the front of the _retryList last:
                    if (retriedBufferIndexes < static_cast<bf_idx>(_retryListCheck * _retryList.size())
                        || _initialList.empty()) {     // Check again the front of the _retryList:
                        _retryList.pop(selected);
                        retriedBufferIndexes++;
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    } else {                        // Change to checking entries from the front of the _initialList
                        _initialList.pop(selected);
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            retriedBufferIndexes = 0;
                            currentlyCheckingRetryList = false;
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    }
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {};

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _notExplicitlyEvictedList[idx].test_and_set();
            _initialList.push(idx);
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _notExplicitlyEvictedList[idx].clear();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        cds::container::FCQueue<bf_idx> _initialList;

        cds::container::FCQueue<bf_idx> _retryList;

        std::vector<std::atomic_flag> _notExplicitlyEvictedList;

        static constexpr double _retryListCheck = retry_list_check_ppm * 0.000001;

        static constexpr double _initialListCheck = initial_list_check_ppm * 0.000001;
    };

    template<uint32_t retry_list_check_ppm/* = 1000000*/, uint32_t initial_list_check_ppm/* = 10000*/>
    class PageEvictionerSelectorQuasiFIFOHighContention : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorQuasiFIFOHighContention(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _approximateInitialListLength(0),
                _approximateRetryListLength(0),
                _initialList(bufferPool->getBlockCount()),
                _retryList(bufferPool->getBlockCount()),
                _notExplicitlyEvictedList(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            static thread_local bool currentlyCheckingRetryList;
            static thread_local size_t retriedBufferIndexes;

            bf_idx selected;
            while (true) {
                if (!currentlyCheckingRetryList) {               // This thread checked the front of the _initialList last:
                    if (retriedBufferIndexes < static_cast<bf_idx>(_initialListCheck * _approximateInitialListLength)
                        || _approximateRetryListLength == 0) {
                        if (_initialList.try_pop(selected)) {  // Check again the front of the _initialList
                            _approximateInitialListLength--;
                            retriedBufferIndexes++;
                            if (_notExplicitlyEvictedList[selected].test_and_set()) {
                                return selected;
                            } else {
                                continue;                       // This buffer frame was explicitly evicted
                            }
                        } else {
                            currentlyCheckingRetryList = true;
                            continue;
                        }
                    } else {                                    // Change to checking entries from the front of the _retryList
                        if (_retryList.try_pop(selected)) {
                            _approximateRetryListLength--;
                            retriedBufferIndexes = 0;
                            if (_notExplicitlyEvictedList[selected].test_and_set()) {
                                return selected;
                            } else {
                                continue;                       // This buffer frame was explicitly evicted
                            }
                        } else {
                            currentlyCheckingRetryList = false;
                            continue;
                        }
                    }
                } else {                                        // This thread checked the front of the _retryList last:
                    if (retriedBufferIndexes < static_cast<bf_idx>(_retryListCheck * _approximateRetryListLength)
                        || _approximateInitialListLength == 0) {
                        if (_retryList.try_pop(selected)) {    // Check again the front of the _retryList
                            _approximateRetryListLength--;
                            retriedBufferIndexes++;
                            if (_notExplicitlyEvictedList[selected].test_and_set()) {
                                return selected;
                            } else {
                                continue;                       // This buffer frame was explicitly evicted
                            }
                        } else {
                            currentlyCheckingRetryList = false;
                            continue;
                        }
                    } else {                                    // Change to checking entries from the front of the _initialList
                        if (_initialList.try_pop(selected)) {
                            _approximateInitialListLength--;
                            retriedBufferIndexes = 0;
                            if (_notExplicitlyEvictedList[selected].test_and_set()) {
                                return selected;
                            } else {
                                continue;                       // This buffer frame was explicitly evicted
                            }
                        } else {
                            currentlyCheckingRetryList = true;
                            continue;
                        }
                    }
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {};

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _notExplicitlyEvictedList[idx].test_and_set();
            _initialList.push(idx);
            _approximateInitialListLength++;
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _retryList.push(idx);
            _approximateRetryListLength++;
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _retryList.push(idx);
            _approximateRetryListLength++;
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _retryList.push(idx);
            _approximateRetryListLength++;
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _retryList.push(idx);
            _approximateRetryListLength++;
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _notExplicitlyEvictedList[idx].clear();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        rigtorp::MPMCQueue<bf_idx> _initialList;

        atomic_bf_idx _approximateInitialListLength;

        rigtorp::MPMCQueue<bf_idx> _retryList;

        atomic_bf_idx _approximateRetryListLength;

        std::vector<std::atomic_flag> _notExplicitlyEvictedList;

        static constexpr double _retryListCheck = retry_list_check_ppm * 0.000001;

        static constexpr double _initialListCheck = initial_list_check_ppm * 0.000001;
    };

    template<uint32_t retry_list_check_ppm/* = 1000000*/, uint32_t initial_list_check_ppm/* = 10000*/>
    class PageEvictionerSelectorQuasiFILOLowContention : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorQuasiFILOLowContention(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _notExplicitlyEvictedList(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            static thread_local bool currentlyCheckingRetryList;
            static thread_local size_t retriedBufferIndexes;

            bf_idx selected;
            while (true) {
                if (!currentlyCheckingRetryList) {   // This thread checked the front of the _retryList last:
                    if (retriedBufferIndexes < static_cast<bf_idx>(_initialListCheck * _initialList.size())
                        || _retryList.empty()) {       // Check again the front of the _initialList:
                        _initialList.pop(selected);
                        retriedBufferIndexes++;
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    } else {                        // Change to checking entries from the front of the _retryList
                        _retryList.pop(selected);
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            retriedBufferIndexes = 0;
                            currentlyCheckingRetryList = true;
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted

                        }
                    }
                } else {                            // This thread checked the front of the _initialList last:
                    if (retriedBufferIndexes < static_cast<bf_idx>(_retryListCheck * _retryList.size())
                        || _initialList.empty()) {     // Check again the front of the _retryList:
                        _retryList.pop(selected);
                        retriedBufferIndexes++;
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    } else {                        // Change to checking entries from the front of the _initialList
                        _initialList.pop(selected);
                        if (_notExplicitlyEvictedList[selected].test_and_set()) {
                            retriedBufferIndexes = 0;
                            currentlyCheckingRetryList = false;
                            return selected;
                        } else {
                            continue;               // This buffer frame was explicitly evicted
                        }
                    }
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {};

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _notExplicitlyEvictedList[idx].test_and_set();
            _initialList.push(idx);
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _retryList.push(idx);
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _notExplicitlyEvictedList[idx].clear();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        cds::container::FCStack<bf_idx> _initialList;

        cds::container::FCQueue<bf_idx> _retryList;

        std::vector<std::atomic_flag> _notExplicitlyEvictedList;

        static constexpr double _retryListCheck = retry_list_check_ppm * 0.000001;

        static constexpr double _initialListCheck = initial_list_check_ppm * 0.000001;
    };

    class PageEvictionerSelectorLRU : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorLRU(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _lruList(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            bf_idx selected;
            _lruListLock.lock();
            _lruList.popFromFront(selected);
            return selected;
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            std::lock_guard<std::recursive_mutex> lock(_lruListLock);
            _lruList.remove(idx);
            _lruList.pushToBack(idx);
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {
            std::lock_guard<std::recursive_mutex> lock(_lruListLock);
            _lruList.remove(idx);
            _lruList.pushToBack(idx);
        };

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _lruListLock.lock();
            _lruList.pushToBack(idx);
            _lruListLock.unlock();
            _lruListLock.unlock();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _lruList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _lruList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _lruList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _lruList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _lruListLock.lock();
            try {
                _lruList.remove(idx);
            } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {}
            _lruListLock.unlock();
            _lruListLock.unlock();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {
            _lruListLock.unlock();
        };

    private:
        zero::hashtable_deque::HashtableDeque<bf_idx, 0> _lruList;

        std::recursive_mutex _lruListLock;
    };

    template<bf_idx protected_block_ppm/* = 10000*/>
    class PageEvictionerSelectorSLRU : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorSLRU(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _protectedBlockCount(static_cast<bf_idx>(protected_block_ppm * 0.000001 * bufferPool->getBlockCount())),
                _protectedLRUList(_protectedBlockCount),
                _probationaryLRUList(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            bf_idx selected;
            _lruListLock.lock();
            _probationaryLRUList.popFromFront(selected);
            return selected;
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            std::lock_guard<std::recursive_mutex> lock(_lruListLock);
            try {
                _protectedLRUList.remove(idx);
            } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {
                _probationaryLRUList.remove(idx);
            }
            if (_protectedLRUList.length() >= _protectedBlockCount - 1) {
                bf_idx downgradeIndex;
                _protectedLRUList.popFromFront(downgradeIndex);
                _probationaryLRUList.pushToBack(downgradeIndex);
            }
            _protectedLRUList.pushToBack(idx);
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _lruListLock.lock();
            _probationaryLRUList.pushToBack(idx);
            _lruListLock.unlock();
            _lruListLock.unlock();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            if (_protectedLRUList.length() >= _protectedBlockCount - 1) {
                bf_idx downgradeIndex;
                _protectedLRUList.popFromFront(downgradeIndex);
                _probationaryLRUList.pushToBack(downgradeIndex);
            }
            _protectedLRUList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            if (_protectedLRUList.length() >= _protectedBlockCount - 1) {
                bf_idx downgradeIndex;
                _protectedLRUList.popFromFront(downgradeIndex);
                _probationaryLRUList.pushToBack(downgradeIndex);
            }
            _protectedLRUList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            if (_protectedLRUList.length() >= _protectedBlockCount - 1) {
                bf_idx downgradeIndex;
                _protectedLRUList.popFromFront(downgradeIndex);
                _probationaryLRUList.pushToBack(downgradeIndex);
            }
            _protectedLRUList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            if (_protectedLRUList.length() >= _protectedBlockCount - 1) {
                bf_idx downgradeIndex;
                _protectedLRUList.popFromFront(downgradeIndex);
                _probationaryLRUList.pushToBack(downgradeIndex);
            }
            _protectedLRUList.pushToBack(idx);
            _lruListLock.unlock();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            std::lock_guard<std::recursive_mutex> lock(_lruListLock);
            try {
                _protectedLRUList.remove(idx);
            } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {
                try {
                    _probationaryLRUList.remove(idx);
                } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {}
            }
            _lruListLock.unlock();
            _lruListLock.unlock();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {
            _lruListLock.unlock();
        };

    private:
        zero::hashtable_deque::HashtableDeque<bf_idx, 0> _protectedLRUList;

        zero::hashtable_deque::HashtableDeque<bf_idx, 0> _probationaryLRUList;

        const bf_idx _protectedBlockCount;

        std::recursive_mutex _lruListLock;
    };

    template<size_t k/* = 2*/, bool on_page_unfix/* = false*/>
    class PageEvictionerSelectorLRUK : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorLRUK(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _lruList(k * bufferPool->getBlockCount()),
                _frameReferences(bufferPool->getBlockCount(), 0),
                _leastRecentlyUsedFinite(0) {};

        inline bf_idx select() noexcept final {
            uint64_t selected;                  // Does not remove more tracked references because the page might be not
            _lruListLock.lock();                // evictable right now.
            selected = _popFromFront();
            return static_cast<bf_idx>(selected / k);
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            if constexpr (!on_page_unfix) {
                _lruListLock.lock();
                _remove(static_cast<uint64_t>((_frameReferences[idx] % k) + k * idx));
                _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
                _lruListLock.unlock();
            }
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {
            if constexpr (on_page_unfix) {
                _lruListLock.lock();
                _remove(static_cast<uint64_t>((_frameReferences[idx] % k) + k * idx));
                _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
                _lruListLock.unlock();
            }
        };

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _lruListLock.lock();
            _frameReferences[idx] = 0;
            for (size_t i = 0; i < k; i++) {    // select() does not remove all the tracked references therefore, this is
                try {       // done here to prevent influence of the old reference history on the new page.
                    _remove(static_cast<uint64_t>((i % k) + k * idx));
                } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<uint64_t, 0>& ex) {}
            }
            if (k >= 2) {
                try {
                    _lruList.insertBefore(static_cast<uint64_t>((_frameReferences[idx] % k) + k * idx),
                                          _leastRecentlyUsedFinite);
                } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<uint64_t, 0>& ex) {
                    _lruList.pushToBack(static_cast<uint64_t>((_frameReferences[idx] % k) + k * idx));
                }
            }
            for (size_t i = 2; i < k; i++) {
                uint64_t ref = static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx);
                try {
                    _lruList.insertBefore(static_cast<uint64_t>((_frameReferences[idx] % k) + k * idx),
                                          ref);
                } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<uint64_t, 0>& ex) {
                    _lruList.pushToBack(static_cast<uint64_t>((_frameReferences[idx] % k) + k * idx));
                }
            }
            if (k >= 2) {
                _frameReferences[idx]++;
            }
            _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
            _lruListLock.unlock();
            _lruListLock.unlock();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
            _lruListLock.unlock();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
            _lruListLock.unlock();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
            _lruListLock.unlock();
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _pushToBack(static_cast<uint64_t>((_frameReferences[idx]++ % k) + k * idx));
            _lruListLock.unlock();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _lruListLock.lock();
            _frameReferences[idx] = 0;
            for (size_t i; i < k; i++) {
                try {
                    _remove(static_cast<uint64_t>((i % k) + k * idx));
                } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<uint64_t, 0>& ex) {}
            }
            _lruListLock.unlock();
            _lruListLock.unlock();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {
            _lruListLock.unlock();
        };

    private:
        zero::hashtable_deque::HashtableDeque<uint64_t, 0> _lruList;

        std::vector<size_t> _frameReferences;

        std::recursive_mutex _lruListLock;

        uint64_t _leastRecentlyUsedFinite;

        inline void _pushToBack(uint64_t key) {
            if (_leastRecentlyUsedFinite == 0) {
                _leastRecentlyUsedFinite = key;
            }
            _lruList.pushToBack(key);
        }

        inline uint64_t _popFromFront() {
            uint64_t front = _lruList.getFront();
            _remove(front);
            return front;
        }

        inline void _remove(uint64_t key) {
            if (key == _leastRecentlyUsedFinite) {
                try {
                    _leastRecentlyUsedFinite = _lruList.getAfter(key);
                } catch (const zero::hashtable_deque::HashtableDequeAlreadyAtTheBackException<uint64_t, 0>& ex) {
                    _leastRecentlyUsedFinite = 0;
                }
            }
            _lruList.remove(key);
        }

    };

    template<uint32_t retry_list_check_ppm/* = 1000000*/, uint32_t mru_list_check_ppm/* = 10000*/>
    class PageEvictionerSelectorQuasiMRU : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorQuasiMRU(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _mruList(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            static thread_local bool currentlyCheckingRetryList;
            static thread_local size_t retriedBufferIndexes;

            bf_idx selected;
            if (currentlyCheckingRetryList) {       // This thread checked the front of the _retryList last:
                if (retriedBufferIndexes < static_cast<bf_idx>(retry_list_check_ppm * 0.000001 * _retryList.length())
                    || _mruList.length() == 0) {    // Check again the front of the _retryList:
                    _mruListLock.lock();
                    _retryList.popFromFront(selected);
                    retriedBufferIndexes++;
                    return selected;
                } else {                            // Change to checking entries from the front of the _initialList
                    _mruListLock.lock();
                    _mruList.popFromFront(selected);
                    retriedBufferIndexes = 0;
                    currentlyCheckingRetryList = false;
                    return selected;
                }
            } else {                                // This thread checked the front of the _initialList last:
                if (retriedBufferIndexes < static_cast<bf_idx>(mru_list_check_ppm * 0.000001 * _mruList.length())
                    || _retryList.length() == 0) {  // Check again the front of the _initialList:
                    _mruListLock.lock();
                    _mruList.popFromFront(selected);
                    retriedBufferIndexes++;
                    return selected;
                } else {                            // Change to checking entries from the front of the _retryList
                    _mruListLock.lock();
                    _retryList.popFromFront(selected);
                    retriedBufferIndexes = 0;
                    currentlyCheckingRetryList = true;
                    return selected;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {};

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {
            _mruListLock.lock();
            try {
                _mruList.remove(idx);
            } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {
                _retryList.remove(idx);
            }
            _mruList.pushToFront(idx);
            _mruListLock.unlock();
        };

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _mruListLock.lock();
            _mruList.pushToFront(idx);
            _mruListLock.unlock();
            _mruListLock.unlock();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _mruListLock.lock();
            _retryList.pushToBack(idx);
            _mruListLock.unlock();
            _mruListLock.unlock();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _mruListLock.lock();
            _retryList.pushToBack(idx);
            _mruListLock.unlock();
            _mruListLock.unlock();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _mruListLock.lock();
            _retryList.pushToBack(idx);
            _mruListLock.unlock();
            _mruListLock.unlock();
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _mruListLock.lock();
            _retryList.pushToBack(idx);
            _mruListLock.unlock();
            _mruListLock.unlock();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _mruListLock.lock();
            try {
                _mruList.remove(idx);
            } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {
                try {
                    _retryList.remove(idx);
                } catch (const zero::hashtable_deque::HashtableDequeNotContainedException<bf_idx, 0>& ex) {}
            }
            _mruListLock.unlock();
            _mruListLock.unlock();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {
            _mruListLock.unlock();
        };

    private:
        zero::hashtable_deque::HashtableDeque<bf_idx, 0> _mruList;

        std::recursive_mutex _mruListLock;

        zero::hashtable_deque::HashtableDeque<bf_idx, 0> _retryList;
    };

    template<bf_idx resort_threshold_ppm/* = 750000*/>
    class PageEvictionerSelectorTimestampLRU : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorTimestampLRU(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _timestampsLive(bufferPool->getBlockCount()),
                _lruList0(bufferPool->getBlockCount()),
                _lruList1(bufferPool->getBlockCount()),
                _lastChecked(0),
                _useLRUList0(false),
                _useLRUList1(false) {
            _sortingInProgress.clear(); // _sortingInProgress should be initialized false but sometimes it is true!?
        };

        inline bf_idx select() noexcept final {
            while (true) {
                if (_useLRUList0) {
                    if (_lastChecked > static_cast<bf_idx>(resort_threshold_ppm * 0.000001 * (_maxBufferpoolIndex - 1))
                        && !_sortingInProgress.test_and_set()) {
                        _waitForSorted.lock();
                        sort(_lruList1);
                        _useLRUList1 = true;
                        _lastChecked = 0;
                        _waitForSorted.unlock();
                        _useLRUList0 = false;
                        _sortingInProgress.clear();
                        continue;
                    } else {
                        bf_idx checkThis = ++_lastChecked;
                        if (checkThis > _maxBufferpoolIndex) {
                            _waitForSorted.lock();
                            _waitForSorted.unlock();
                            continue;
                        } else {
                            if (std::get<1>(_lruList0[checkThis])
                                == _timestampsLive[std::get<0>(_lruList0[checkThis])]) {
                                return std::get<0>(_lruList0[checkThis]);
                            } else {
                                continue;
                            }
                        }
                    }
                } else if (_useLRUList1) {
                    if (_lastChecked > static_cast<bf_idx>(resort_threshold_ppm * 0.000001 * (_maxBufferpoolIndex - 1))
                        && !_sortingInProgress.test_and_set()) {
                        _waitForSorted.lock();
                        sort(_lruList0);
                        _useLRUList0 = true;
                        _lastChecked = 0;
                        _waitForSorted.unlock();
                        _useLRUList1 = false;
                        _sortingInProgress.clear();
                        continue;
                    } else {
                        bf_idx checkThis = ++_lastChecked;
                        if (checkThis > _maxBufferpoolIndex) {
                            _waitForSorted.lock();
                            _waitForSorted.unlock();
                            continue;
                        } else {
                            if (std::get<1>(_lruList1[checkThis])
                                == _timestampsLive[std::get<0>(_lruList1[checkThis])]) {
                                return std::get<0>(_lruList1[checkThis]);
                            } else {
                                continue;
                            }
                        }
                    }
                } else if (!_sortingInProgress.test_and_set()) {
                    _waitForSorted.lock();
                    sort(_lruList0);
                    _useLRUList0 = true;
                    _lastChecked = 0;
                    _waitForSorted.unlock();
                    _useLRUList1 = false;
                    _sortingInProgress.clear();
                } else {
                    _waitForSorted.lock();
                    _waitForSorted.unlock();
                    continue;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _timestampsLive[idx]
                    = std::chrono::time_point<std::chrono::steady_clock>::max().time_since_epoch().count();
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _timestampsLive[idx] = std::chrono::steady_clock::duration::max().count();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        std::vector<std::atomic<std::chrono::steady_clock::duration::rep>> _timestampsLive;

        std::vector<std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>> _lruList0;

        std::vector<std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>> _lruList1;

        atomic_bf_idx _lastChecked;

        std::atomic<bool> _useLRUList0;

        std::atomic<bool> _useLRUList1;

        std::atomic_flag _sortingInProgress;

        std::mutex _waitForSorted;

        inline void sort(
                std::vector<std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>>& into) noexcept {
            for (bf_idx index = 0; index < _timestampsLive.size(); index++) {
                into[index] = std::make_tuple(index, _timestampsLive[index].load());
            }

            std::sort(/*std::parallel::par,*/
                    into.begin(),
                    into.end(),
                    [](const std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>& a,
                       const std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>& b) {
                        return std::get<1>(a) < std::get<1>(b);
                    });

            std::cout << "0: "                       << std::get<0>(into[0]) << "; "
                      << _maxBufferpoolIndex << ": " << std::get<0>(into[_maxBufferpoolIndex])
                      << std::endl;
        };
    };

    template<size_t k/* = 2*/, bf_idx resort_threshold_ppm/* = 750000*/, bool on_page_unfix/* = false*/>
    class PageEvictionerSelectorTimestampLRUK : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorTimestampLRUK(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _timestampsLiveOldestTimestamp(bufferPool->getBlockCount()),
                _timestampsLive(bufferPool->getBlockCount()),
                _lruList0(bufferPool->getBlockCount()),
                _lruList1(bufferPool->getBlockCount()),
                _lastChecked(0),
                _useLRUList0(false),
                _useLRUList1(false),
                _infinitePast(0) {
            _sortingInProgress.clear(); // _sortingInProgress should be initialized false but sometimes it is true!?
        };

        inline bf_idx select() noexcept final {
            while (true) {
                if (_useLRUList0) {
                    if (_lastChecked > static_cast<bf_idx>(resort_threshold_ppm * 0.000001 * (_maxBufferpoolIndex - 1))
                        && !_sortingInProgress.test_and_set()) {
                        _waitForSorted.lock();
                        sort(_lruList1);
                        _useLRUList1 = true;
                        _lastChecked = 0;
                        _waitForSorted.unlock();
                        _useLRUList0 = false;
                        _sortingInProgress.clear();
                        continue;
                    } else {
                        bf_idx checkThis = ++_lastChecked;
                        if (checkThis > _maxBufferpoolIndex) {
                            _waitForSorted.lock();
                            _waitForSorted.unlock();
                            continue;
                        } else {
                            if (std::get<1>(_lruList0[checkThis])
                                == _timestampsLive[std::get<0>(_lruList0[checkThis])][
                                        _timestampsLiveOldestTimestamp[std::get<0>(_lruList0[checkThis])] % k]
                             && std::get<0>(_lruList0[checkThis]) != 0) {
                                return std::get<0>(_lruList0[checkThis]);
                            } else {
                                continue;
                            }
                        }
                    }
                } else if (_useLRUList1) {
                    if (_lastChecked > static_cast<bf_idx>(resort_threshold_ppm * 0.000001 * (_maxBufferpoolIndex - 1))
                        && !_sortingInProgress.test_and_set()) {
                        _waitForSorted.lock();
                        sort(_lruList0);
                        _useLRUList0 = true;
                        _lastChecked = 0;
                        _waitForSorted.unlock();
                        _useLRUList1 = false;
                        _sortingInProgress.clear();
                        continue;
                    } else {
                        bf_idx checkThis = ++_lastChecked;
                        if (checkThis > _maxBufferpoolIndex) {
                            _waitForSorted.lock();
                            _waitForSorted.unlock();
                            continue;
                        } else {
                            if (std::get<1>(_lruList1[checkThis])
                                == _timestampsLive[std::get<0>(_lruList1[checkThis])][
                                        _timestampsLiveOldestTimestamp[std::get<0>(_lruList1[checkThis])] % k]
                             && std::get<0>(_lruList1[checkThis]) != 0) {
                                return std::get<0>(_lruList1[checkThis]);
                            } else {
                                continue;
                            }
                        }
                    }
                } else if (!_sortingInProgress.test_and_set()) {
                    _waitForSorted.lock();
                    sort(_lruList0);
                    _useLRUList0 = true;
                    _lastChecked = 0;
                    _waitForSorted.unlock();
                    _useLRUList1 = false;
                    _sortingInProgress.clear();
                    continue;
                } else {
                    _waitForSorted.lock();
                    _waitForSorted.unlock();
                    continue;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            if constexpr (!on_page_unfix) {
                _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k]
                        = std::chrono::steady_clock::now().time_since_epoch().count();
            }
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {
            if constexpr (on_page_unfix) {
                _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k]
                        = std::chrono::steady_clock::now().time_since_epoch().count();
            }
        };

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _timestampsLiveOldestTimestamp[idx] = 0;
            _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k] = std::chrono::steady_clock::now().time_since_epoch().count();
            for (size_t i = 1; i > k; i++) {
                _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k] = _infinitePast++;
            }
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k]
                    = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k]
                    = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            for (size_t i = 0; i < k; i++) {
                _timestampsLive[idx][i]
                        = std::chrono::time_point<std::chrono::steady_clock>::max().time_since_epoch().count();
            }
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _timestampsLive[idx][_timestampsLiveOldestTimestamp[idx]++ % k]
                    = std::chrono::steady_clock::now().time_since_epoch().count();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            for (size_t i = 0; i < k; i++) {
                _timestampsLive[idx][i]
                        = std::chrono::steady_clock::now().time_since_epoch().count();
            }
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        std::vector<size_t> _timestampsLiveOldestTimestamp;

        std::vector<std::array<std::atomic<std::chrono::steady_clock::duration::rep>, k>> _timestampsLive;

        std::vector<std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>> _lruList0;

        std::vector<std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>> _lruList1;

        atomic_bf_idx _lastChecked;

        std::atomic<bool> _useLRUList0;

        std::atomic<bool> _useLRUList1;

        std::atomic_flag _sortingInProgress;

        std::mutex _waitForSorted;

        std::atomic<std::chrono::steady_clock::duration::rep> _infinitePast;

        inline void sort(
                std::vector<std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>>& into) noexcept {
            for (bf_idx index = 0; index < _timestampsLive.size(); index++) {
                into[index] = std::make_tuple(index,
                                              _timestampsLive[index][_timestampsLiveOldestTimestamp[index] % k].load());
            }

            std::sort(/*std::parallel::par,*/
                    into.begin(),
                    into.end(),
                    [](const std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>& a,
                       const std::tuple<bf_idx, std::chrono::steady_clock::duration::rep>& b) {
                        return std::get<1>(a) < std::get<1>(b);
                    });
        };
    };

    class PageEvictionerSelectorLFU : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorLFU(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _frameReferences(bufferPool->getBlockCount()),
                _frameAlreadySelected(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            bf_idx minIndex = 0;
            uint64_t minReferences = std::numeric_limits<uint64_t>::max();

            while (true) {
                for (bf_idx index = 1; index <= _maxBufferpoolIndex; index++) {
                    if (_frameReferences[index] < minReferences) {
                        if (!_frameAlreadySelected[index].test_and_set()) {
                            _frameAlreadySelected[minIndex].clear();
                            minIndex = index;
                            minReferences = _frameReferences[index];
                        }
                    }
                }

                if (_frameReferences[minIndex] != minReferences) {
                    _frameAlreadySelected[minIndex].clear();
                    minReferences = std::numeric_limits<uint64_t>::max();
                    continue;
                } else {
                    return minIndex;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            _frameReferences[idx]++;
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _frameReferences[idx] = 1;
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _frameReferences[idx] = std::numeric_limits<uint64_t>::max() / 2;
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _frameReferences[idx] = std::numeric_limits<uint64_t>::max();
            _frameAlreadySelected[idx].test_and_set();
        }

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        std::vector<std::atomic<uint64_t>> _frameReferences;

        std::vector<std::atomic_flag> _frameAlreadySelected;

    };

    class PageEvictionerSelectorLFUDA : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorLFUDA(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _frameReferences(bufferPool->getBlockCount()),
                _inflationFactor(1),
                _frameAlreadySelected(bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            bf_idx minIndex = 0;
            uint64_t minReferences = std::numeric_limits<uint64_t>::max();

            while (true) {
                for (bf_idx index = 1; index <= _maxBufferpoolIndex; index++) {
                    if (_frameReferences[index] < minReferences) {
                        if (!_frameAlreadySelected[index].test_and_set()) {
                            _frameAlreadySelected[minIndex].clear();
                            minIndex = index;
                            minReferences = _frameReferences[index];
                        }
                    }
                }

                if (_frameReferences[minIndex] != minReferences) {
                    _frameAlreadySelected[minIndex].clear();
                    minReferences = std::numeric_limits<uint64_t>::max();
                    continue;
                } else {
                    _inflationFactor = minReferences;
                    return minIndex;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            _frameReferences[idx]++;
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _frameReferences[idx] = _inflationFactor.load();
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _frameReferences[idx] = std::numeric_limits<uint64_t>::max() / 2;
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _frameReferences[idx] = std::numeric_limits<uint64_t>::max();
            _frameAlreadySelected[idx].test_and_set();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        std::vector<std::atomic<uint64_t>> _frameReferences;

        std::atomic<uint64_t> _inflationFactor;

        std::vector<std::atomic_flag> _frameAlreadySelected;

    };

    class PageEvictionerSelectorLRDV1 : public PageEvictionerSelector {
    public:
        explicit PageEvictionerSelectorLRDV1(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _frameReferences(bufferPool->getBlockCount()),
                _frameFirstReferenced(bufferPool->getBlockCount()),
                _frameAlreadySelected(bufferPool->getBlockCount()),
                _globalReferences(0) {};

        inline bf_idx select() noexcept final {
            bf_idx minLRDIndex = 0;
            uint64_t minLRDReferences;
            double minLRDReferenceDensity = std::numeric_limits<double>::max();

            while (true) {
                for (bf_idx index = 1; index <= _maxBufferpoolIndex; index++) {
                    if ((static_cast<double>(_frameReferences[index])
                         / static_cast<double>(_globalReferences - _frameFirstReferenced[index]))
                        < minLRDReferenceDensity) {
                        if (!_frameAlreadySelected[index].test_and_set()) {
                            _frameAlreadySelected[minLRDIndex].clear();
                            minLRDIndex = index;
                            minLRDReferences = _frameReferences[index];
                            minLRDReferenceDensity = static_cast<double>(_frameReferences[index])
                                                     / static_cast<double>(_globalReferences
                                                                           - _frameFirstReferenced[index]);
                        }
                    }
                }

                if (_frameReferences[minLRDIndex] != minLRDReferences) {
                    _frameAlreadySelected[minLRDIndex].clear();
                    minLRDReferenceDensity = std::numeric_limits<double>::max();
                    continue;
                } else {
                    return minLRDIndex;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            _globalReferences++;
            _frameReferences[idx]++;
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _frameFirstReferenced[idx] = _globalReferences++;
            _frameReferences[idx] = 1;
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _frameReferences[idx] = _globalReferences.load();   // Prevent further tries of eviction!
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _frameFirstReferenced[idx] = 0;
            _frameReferences[idx] = 0;
            _frameAlreadySelected[idx].test_and_set();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        std::vector<std::atomic<uint64_t>> _frameReferences;

        std::vector<std::atomic<uint64_t>> _frameFirstReferenced;

        std::vector<std::atomic_flag> _frameAlreadySelected;

        std::atomic<uint64_t> _globalReferences;
    };

    struct AgingFunction {
        virtual void operator()(std::atomic<uint64_t>& referenceCount) noexcept = 0;
    };

    template<uint64_t subtrahend/* = 10*/>
    struct AgingFunctionSubtraction : public AgingFunction {
        inline void operator()(std::atomic<uint64_t>& referenceCount) noexcept final {
            if (referenceCount > subtrahend) {
                referenceCount -= subtrahend;
            } else {
                referenceCount = 0;
            }
        }
    };

    template<uint64_t factor_ppm/* = 750000*/>
    struct AgingFunctionMultiplication : public AgingFunction {
        inline void operator()(std::atomic<uint64_t>& referenceCount) noexcept final {
            referenceCount = static_cast<uint64_t>(factor_ppm * 0.000001 * referenceCount);
        }
    };

    template<uint64_t aging_frequency/* = 10*/, class aging_function>
    class PageEvictionerSelectorLRDV2 : public PageEvictionerSelector {
        static_assert(std::is_base_of<AgingFunction, aging_function>::value,
                      "'selector_class' is not of type 'AgingFunction'!");

    public:
        explicit PageEvictionerSelectorLRDV2(const BufferPool* bufferPool) :
                PageEvictionerSelector(bufferPool),
                _frameReferences(bufferPool->getBlockCount()),
                _frameFirstReferenced(bufferPool->getBlockCount()),
                _frameAlreadySelected(bufferPool->getBlockCount()),
                _globalReferences(0),
                _agingFrequency(aging_frequency * bufferPool->getBlockCount()) {};

        inline bf_idx select() noexcept final {
            bf_idx minLRDIndex = 0;
            uint64_t minLRDReferences;
            double minLRDReferenceDensity = std::numeric_limits<double>::max();

            while (true) {
                for (bf_idx index = 1; index <= _maxBufferpoolIndex; index++) {
                    if ((static_cast<double>(_frameReferences[index])
                         / static_cast<double>(_globalReferences - _frameFirstReferenced[index]))
                        < minLRDReferenceDensity) {
                        if (!_frameAlreadySelected[index].test_and_set()) {
                            _frameAlreadySelected[minLRDIndex].clear();
                            minLRDIndex = index;
                            minLRDReferences = _frameReferences[index];
                            minLRDReferenceDensity = static_cast<double>(_frameReferences[index])
                                                     / static_cast<double>(_globalReferences
                                                                           - _frameFirstReferenced[index]);
                        }
                    }
                }

                if (_frameReferences[minLRDIndex] != minLRDReferences) {
                    _frameAlreadySelected[minLRDIndex].clear();
                    minLRDReferenceDensity = std::numeric_limits<double>::max();
                    continue;
                } else {
                    return minLRDIndex;
                }
            }
        };

        inline void updateOnPageHit(bf_idx idx) noexcept final {
            _frameReferences[idx]++;
            if (_globalReferences++ % _agingFrequency == 0) {
                std::for_each(/*std::parallel::par, */_frameReferences.begin(), _frameReferences.end(),
                                                      [this](std::atomic<uint64_t>& referenceCount) {
                                                          _agingFunction(referenceCount);
                                                      });
            }
        };

        inline void updateOnPageUnfix(bf_idx idx) noexcept final {};

        inline void updateOnPageMiss(bf_idx idx, PageID pid) noexcept final {
            _frameFirstReferenced[idx] = _globalReferences++;
            if (_frameFirstReferenced[idx] % _agingFrequency == 0) {
                std::for_each(/*std::parallel::par, */_frameReferences.begin(), _frameReferences.end(),
                                                      [this](std::atomic<uint64_t>& referenceCount) {
                                                          _agingFunction(referenceCount);
                                                      });
            }
            _frameReferences[idx] = 1;
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageFixed(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageDirty(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageBlocked(bf_idx idx) noexcept final {
            _frameReferences[idx] = _globalReferences.load();   // Prevent further tries of eviction!
        };

        inline void updateOnPageSwizzled(bf_idx idx) noexcept final {
            _frameReferences[idx]++;    // Prevent infinite loops of non-evictable selects.
            _frameAlreadySelected[idx].clear();
        };

        inline void updateOnPageExplicitlyUnbuffered(bf_idx idx) noexcept final {
            _frameFirstReferenced[idx] = 0;
            _frameReferences[idx] = 0;
            _frameAlreadySelected[idx].test_and_set();
        };

        void updateOnPointerSwizzling(bf_idx idx) noexcept final {};

        inline void releaseInternalLatches() noexcept final {};

    private:
        std::vector<std::atomic<uint64_t>> _frameReferences;

        std::vector<std::atomic<uint64_t>> _frameFirstReferenced;

        std::vector<std::atomic_flag> _frameAlreadySelected;

        std::atomic<uint64_t> _globalReferences;

        uint64_t _agingFrequency;

        aging_function _agingFunction;
    };
} // zero::buffer_pool

#endif // __PAGE_EVICTIONER_SELECTOR_HPP