Storage Manager

The Storage Manager handles low-level file I/O operations, including reading, writing, and dynamically extending database files. It ensures data persistence and provides the interface for page operations.

1. Core Functions:
   • Load Page (Read): Reads a page from the database file.
   • Flush Page (Write): Writes in-memory page changes back to the disk to ensure data persistence.
   • Extend File: Dynamically extends the database file by adding new pages.
   • Constructor/Destructor: Handles initialization and cleanup.
2. Implementation Highlights:

   • Initialization:

     • Opens the database file in read/write mode.

     • If the file doesn’t exist, creates a new file.

     • Calculates the total number of pages (num_pages) based on file size.

       StorageManager::StorageManager() {
           // Attempt to open the database file in read/write mode
           fileStream.open(database_filename, std::ios::in | std::ios::out);
       
           // If the file doesn't exist, create a new empty file
           if (!fileStream) {
               fileStream.clear(); // Reset the stream state
               fileStream.open(database_filename, std::ios::out); // Create a new file
               fileStream.close(); // Close the newly created file
           }
       
           // Reopen the file in read/write mode for further operations
           fileStream.open(database_filename, std::ios::in | std::ios::out);
       
           // Calculate the total number of pages in the file
           fileStream.seekg(0, std::ios::end); // Move to the end of the file
           num_pages = fileStream.tellg() / PAGE_SIZE; // File size divided by page size
       }
       

   • Dynamic File Extension:

     • Adds new pages as needed, ensuring scalability.

     void StorageManager::extend() {
         // Create a new empty page using SlottedPage
         auto empty_slotted_page = std::make_unique<SlottedPage>();
         
         // Move the file pointer to the end of the database file
         fileStream.seekp(0, std::ios::end);
         
         // Write the empty page data to the end of the file
         fileStream.write(empty_slotted_page->page_data.get(), PAGE_SIZE);
         
         // Ensure the changes are immediately saved to disk
         fileStream.flush();
         
         // Increment the total number of pages in the database
         num_pages += 1;
     }
     

   • Data Persistence:

     • The flush operation secures in-memory changes by writing them back to the disk, safeguarding against data loss.

     void StorageManager::flush(uint16_t page_id) {
         // Calculate the offset of the page in the database file
         size_t page_offset = page_id * PAGE_SIZE;
     
         // Move the file pointer to the calculated offset
         fileStream.seekp(page_offset, std::ios::beg);
     
         // Write the page's data from memory to the file
         fileStream.write(pages[page_id]->page_data.get(), PAGE_SIZE);
     
         // Ensure the changes are saved to disk immediately
         fileStream.flush();
     }
     

   • Data Loading:

     • Reads specified pages from the database file and loads them into memory.

     std::unique_ptr<SlottedPage> StorageManager::load(uint16_t page_id) {
         // Move the file pointer to the start of the requested page
         fileStream.seekg(page_id * PAGE_SIZE, std::ios::beg);
     
         // Create a new SlottedPage object
         auto page = std::make_unique<SlottedPage>();
     
         // Read the content of the file into the page's data buffer
         if (fileStream.read(page->page_data.get(), PAGE_SIZE)) {
             // Page read successfully
         } else {
             // Handle read error and terminate
             std::cerr << "Error: Unable to read data from the file.\\n";
             exit(-1);
         }
     
         // Return the loaded page
         return page;
     }
     

Buffer Manager

The Buffer Manager acts as a caching layer between the database file and the application, leveraging DRAM to store frequently accessed pages for faster performance. It interacts with the Storage Manager for page I/O operations and implements a Least Recently Used (LRU) caching policy to manage memory efficiently.

DRAM vs SSD

1. Core Components of Buffer Manager

   • PageID: Utilized for page identification
   • LRU List: Maintains the order of page usage.
   • Page Map: Maps Page IDs to their positions in the LRU list for quick lookups.

2. Functionality:

   • Fetching Pages:

     • Retrieves a page from memory if available; otherwise, loads it from disk via the Storage Manager.
     • Updates the page's position in the LRU list using the touch method.

     std::unique_ptr<SlottedPage> &BufferManager::getPage(int page_id) {
         auto it = pageMap.find(page_id);
         if (it == pageMap.end()) {
             auto page = storage_manager.load(page_id);
             // Add page to cache
         }
         touch(pageMap[page_id]);
         return lruList.begin()->second;
     }
     

   • Touching Pages:

     • Updates a page's position in the LRU list to reflect its recent access.

   • Eviction:

     • Removes the least recently used page from the cache and writes any changes back to disk before eviction.

3. LRU Policy:

   • Pages are evicted based on usage recency, ensuring frequently accessed (hot) pages remain in memory.

     

   void touch(PageList::iterator it) {
       lruList.splice(lruList.begin(), lruList, it);
   }
   
   void evict() {
       auto last = --lruList.end();
       int evictedPageId = last->first;
       storage_manager.flush(evictedPageId, last->second);
       pageMap.erase(evictedPageId);
       lruList.pop_back();
   }
   

Buffer Pool Flooding and TwoQ Policy

Sequential scans can overwhelm the buffer pool with less important pages (cold pages), evicting hot pages prematurely. The TwoQ Policy mitigates this by maintaining two separate queues:

Sequential Scan: When a database reads every table page while processing a query

// Sequential scan across the sales_data table
// Assumption: No index on sale_date column
SELECT *
FROM sales_data
WHERE sale_date BETWEEN ‘2040-01-01’ AND ‘2040-01-31’;

1. FIFO Queue: Holds read-once (cold) pages.
2. LRU Queue: Retains frequently accessed (hot) pages.

• Page Transition Logic:

  • Pages enter the FIFO Queue initially.
  • On subsequent access, they are promoted to the LRU Queue.
  • Frequently accessed pages are retained in memory, while cold pages are eventually evicted.

  void touch(PageID page_id) {
      if (pageMap.find(page_id) != pageMap.end()) {
          auto it = pageMap[page_id];
          // Promote to LRU or adjust position
          // Evict if necessary
      }
  }