Buffer Pool Architecture Overview

The buffer pool manager serves as the storage interface between the database system and physical storage. When the system requests a page using a page_id, the buffer pool manager handles the retrieval process transparently, abstracting away whether the page is fetched from disk or memory.

The core components include:

• Extendible Hash Table: Maps page IDs to frame IDs in the buffer pool
• LRU-K Replacer: Determines which frames to evict when the buffer pool is full
• Buffer Pool Manager Instance: Coordinates between hash table, replacer, and disk manager

Extendible Hash Tablle Implementation

The extendible hash table maintains page_id to frame_id mappings without using built-in hash tables. It consists of a directory and multiple buckets.

Core Components

Directory: Aray of pointers to buckets, used to locate the bucket containing a key's value.

Bucket: Stores key-value pairs with a fixed capacity limit.

The hash table tracks:

• global_depth: Number of bits used to index into the directory
• local_depth (per bucket): Number of bits required to locate the bucket

Insertion Process

// Calculate hash and directory index
size_t hash_val = std::hash<k>()(key);
size_t dir_index = hash_val & ((1 << global_depth_) - 1);

// If bucket is full, perform split operation
while (directory[dir_index]->IsFull()) {
    if (global_depth_ == bucket_local_depth) {
        global_depth_++;
        directory.resize(directory.size() * 2);
        // Copy existing pointers to new positions
    }
    
    // Create new buckets with increased depth
    auto bucket0 = std::make_shared<bucket>(bucket_size_, local_depth + 1);
    auto bucket1 = std::make_shared<bucket>(bucket_size_, local_depth + 1);
    
    // Redistribute entries from full bucket
    for (auto& entry : full_bucket->GetItems()) {
        size_t entry_hash = std::hash<k>()(entry.first);
        if (entry_hash & (1 << local_depth)) {
            bucket1->Insert(entry.first, entry.second);
        } else {
            bucket0->Insert(entry.first, entry.second);
        }
    }
    
    // Update directory pointers
    for (size_t i = 0; i < directory.size(); i++) {
        if (directory[i] == full_bucket) {
            directory[i] = (i & (1 << local_depth)) ? bucket1 : bucket0;
        }
    }
}

// Insert into appropriate bucket
directory[dir_index]->Insert(key, value);
</k></bucket></bucket></k>

Bucket Class Methods

class Bucket {
public:
    bool Find(const K& key, V& value);
    bool Insert(const K& key, const V& value);
    bool Remove(const K& key);
private:
    size_t capacity_;
    int depth_;
    std::list<:pair v="">> entries_;
};
</:pair>

LRU-K Replacement Policy

The LRU-K algorithm tracks access history to determine which frames to evict when bufffer space is exhausted.

Data Structures

struct FrameRecord {
    bool evictable = true;
    int access_count = 0;
    std::list<frame_id_t>::iterator position;
};

std::list<frame_id_t> history_queue_;
std::list<frame_id_t> cache_queue_;
std::unordered_map<frame_id_t framerecord=""> frame_records_;
size_t k_value_;
size_t capacity_;
size_t current_size_;
std::mutex lock_;
</frame_id_t></frame_id_t></frame_id_t></frame_id_t>

Key Operations

Record Access

void RecordAccess(frame_id_t frame_id) {
    std::scoped_lock lock(lock_);
    FrameRecord& record = frame_records_[frame_id];
    record.access_count++;
    
    if (record.access_count == 1) {
        history_queue_.push_front(frame_id);
        record.position = history_queue_.begin();
        current_size_++;
    } else if (record.access_count == k_value_) {
        history_queue_.erase(record.position);
        cache_queue_.push_front(frame_id);
        record.position = cache_queue_.begin();
    } else if (record.access_count > k_value_) {
        cache_queue_.erase(record.position);
        cache_queue_.push_front(frame_id);
        record.position = cache_queue_.begin();
    }
}

Eviction

bool Evict(frame_id_t* frame_id) {
    std::scoped_lock lock(lock_);
    if (current_size_ == 0) return false;
    
    // Try history queue first
    for (auto it = history_queue_.rbegin(); it != history_queue_.rend(); ++it) {
        if (frame_records_[*it].evictable) {
            *frame_id = *it;
            history_queue_.erase(frame_records_[*frame_id].position);
            frame_records_.erase(*frame_id);
            current_size_--;
            return true;
        }
    }
    
    // Then try cache queue
    for (auto it = cache_queue_.rbegin(); it != cache_queue_.rend(); ++it) {
        if (frame_records_[*it].evictable) {
            *frame_id = *it;
            cache_queue_.erase(frame_records_[*frame_id].position);
            frame_records_.erase(*frame_id);
            current_size_--;
            return true;
        }
    }
    
    return false;
}

Buffer Pool Manager Implementation

Core Components

class BufferPoolManagerInstance {
private:
    Page* pages_;
    DiskManager* disk_manager_;
    ExtendibleHashTable<page_id_t frame_id_t="">* page_table_;
    LRUKReplacer* replacer_;
    std::list<frame_id_t> free_frames_;
    std::mutex lock_;
    size_t pool_size_;
};
</frame_id_t></page_id_t>

Frame Allocation Helper

bool GetAvailableFrame(frame_id_t* frame_id) {
    if (!free_frames_.empty()) {
        *frame_id = free_frames_.front();
        free_frames_.pop_front();
        return true;
    }
    
    if (replacer_->Evict(frame_id)) {
        Page& victim_page = pages_[*frame_id];
        if (victim_page.IsDirty()) {
            disk_manager_->WritePage(victim_page.GetPageId(), victim_page.GetData());
            victim_page.is_dirty_ = false;
        }
        page_table_->Remove(victim_page.GetPageId());
        return true;
    }
    
    return false;
}

Page Creation

Page* NewPage(page_id_t* page_id) {
    std::scoped_lock lock(lock_);
    frame_id_t frame_id;
    
    if (GetAvailableFrame(&frame_id)) {
        *page_id = AllocatePage();
        pages_[frame_id].page_id_ = *page_id;
        pages_[frame_id].ResetMemory();
        pages_[frame_id].pin_count_ = 1;
        pages_[frame_id].is_dirty_ = false;
        
        page_table_->Insert(*page_id, frame_id);
        replacer_->RecordAccess(frame_id);
        replacer_->SetEvictable(frame_id, false);
        
        return &pages_[frame_id];
    }
    
    return nullptr;
}

Page Retrieval

Page* FetchPage(page_id_t page_id) {
    std::scoped_lock lock(lock_);
    frame_id_t frame_id;
    
    if (page_table_->Find(page_id, frame_id)) {
        pages_[frame_id].pin_count_++;
        replacer_->RecordAccess(frame_id);
        replacer_->SetEvictable(frame_id, false);
        return &pages_[frame_id];
    }
    
    if (GetAvailableFrame(&frame_id)) {
        pages_[frame_id].page_id_ = page_id;
        disk_manager_->ReadPage(page_id, pages_[frame_id].data_);
        pages_[frame_id].pin_count_ = 1;
        pages_[frame_id].is_dirty_ = false;
        
        page_table_->Insert(page_id, frame_id);
        replacer_->RecordAccess(frame_id);
        replacer_->SetEvictable(frame_id, false);
        
        return &pages_[frame_id];
    }
    
    return nullptr;
}

Page Unpinning

bool UnpinPage(page_id_t page_id, bool is_dirty) {
    std::scoped_lock lock(lock_);
    frame_id_t frame_id;
    
    if (page_table_->Find(page_id, frame_id)) {
        if (pages_[frame_id].GetPinCount() == 0) {
            return false;
        }
        
        pages_[frame_id].pin_count_--;
        if (pages_[frame_id].GetPinCount() == 0) {
            replacer_->SetEvictable(frame_id, true);
        }
        
        if (is_dirty) {
            pages_[frame_id].is_dirty_ = true;
        }
        
        return true;
    }
    
    return false;
}