Assignment 2: Transaction Management Mechanisms in the Pager Layer

Introduction

In this assignment, you will explore the implementation of the Pager Layer, a critical component of the CapybaraDB database system. The Pager Layer is responsible for managing the paging of data in and out of storage, ensuring efficient memory usage, data integrity, and transaction handling.  The Pager Layer:

● Handles read and write transactions,

● Maintains an in-memory cache of database pages, and

● Enforces ACID properties to guarantee data consistency.

Through this assignment, you will deepen your understanding of how CapybaraDB implements transaction management. You will also get hands-on experience with cache management and journaling mechanisms. The concepts of journaling and cache replacement strategies that you will implement are essential for any database system managing transactions and fault recovery.

Task 1: Implement the Journaling Mechanism

In Capybara DBMS, we execute each SQL statement in one transaction. There are two types of transactions:

● read transactions

● write transactions 

In a database connection, we cannot have two concurrent write transactions, but it is possible to have one write transaction and multiple read transactions.

Journaling and ACID Properties

ACID is a crucial set of properties that guarantee reliable transaction processing. It's an acronym that stands for:

● Atomicity: This ensures that a transaction is treated as a single, indivisible unit of work. Either all operations within the transaction are completed successfully, or none of them are. If any part of the transaction fails, the entire transaction is rolled back, leaving the database in its original state. Think of it as an "all or nothing" principle.  

● Consistency: This property ensures that a transaction brings the database from one valid state to another. It maintains the integrity of the database by adhering to predefined rules and constraints. This prevents data corruption and ensures that the database remains in a correct state after each transaction.

● Isolation: This deals with concurrent transactions. It ensures that multiple transactions can occur simultaneously without interfering with each other. Each transaction is isolated from others as if it were the only transaction running. This prevents issues like "dirty reads" or "lost updates."

● Durability: This guarantees that once a transaction is committed, its changes are permanent and will survive even system failures, such as power outages or crashes. The changes are stored persistently, ensuring that data is not lost.

CapybaraDB relies on multiple strategies, including Journaling to achieve ACID transactions . Journaling is a technique used to ensure data integrity, consistency, and recovery in the event of a failure. It involves recording changes to the database in a log (or journal) before they are committed to the actual database files. For example,

● Transaction Journaling to track changes for recovery.

● Checkpoint Journaling to manage long-running transactions and system recovery.

Your primary task in this assignment is to implement the core logic of a journaling mechanism within a Transaction Manager. This involves completing the functionality of the Pager class, specifically the methods responsible for managing write transactions and ensuring data durability.

TODOs

The codebase contains several "TODO" comments to guide you. These markers indicate the locations where you need to insert the implementation logic. Pay close attention to these "TODOs" as they directly correspond to the following key functions:

● Pager::SqlitePagerBegin()

○ This method is responsible for initiating a write transaction. The "TODO" within this function will require you to implement the necessary steps to start the journaling process. This may include managing a journal file, and recording the initial state of the database before any changes are made.

● Pager::SqlitePagerWrite()

○ This method prepares a specific page for writing. The "TODO" within this function will require you to implement the logic that writes the page into the journal. This is critical for rollback functionality.

● Pager::SqlitePagerCommit()

○ This method commits the transaction changes to disk. The "TODO" within this function will require you to implement the logic that finalizes the transaction.

● Pager::SqlitePagerRollback()

○ This method reverts changes made during a transaction. The "TODO" within this function will require you to implement the logic that restores the database to its state before the transaction begins. This includes reading the original page data from the journal and writing it back to the database.

By completing these "TODOs", you will effectively implement a journaling mechanism that provides ACID (Atomicity, Consistency, Isolation, Durability) properties for your Transaction Manager.

Key Areas to Analyze

1. Transaction Lifecycle:

● Your implementation should correctly handle the write transaction lifecycle, including begin, write, commit, and rollback operations.

● Tests will validate:

○ Changes are committed to disk only after a successful commit.

○ Rollback operations restore the database to its pre-transaction state without persisting intermediate changes.

2. File Management:

● Journal files must be created, updated, and managed appropriately during a transaction's lifecycle.

● Tests will evaluate:

○ Proper creation and usage of journal files during write operations.

○ Reverting changes when a rollback is triggered, ensuring the journal restores the database correctly.

○ Cleanup or invalidation of journal files upon a successful commit to maintain consistency.

3. Concurrency Handling:

● Tests will simulate concurrent access to ensure proper handling of read and write transactions.

● Key checks include:

○ Write locks prevent multiple concurrent write transactions.

○ Read transactions can proceed concurrently without conflict.

○ Mechanisms effectively handle deadlocks, race conditions, and maintain consistency in multithreaded scenarios.

4. Resilience and Recovery:

● Your implementation will be tested for its ability to handle unexpected interruptions, such as crashes or power failures, that lead to corruption on the database.

Task 2: Implement the LRU Cache Algorithm

Once a page is loaded from the disk into the memory, CapybaraDB manages these pages in its cache. The purpose of caching is to keep as many pages in the memory as possible and to reduce the number of disk accesses since disk IO can be slow and is usually the bottleneck of performance.

When the cache is full, CapybaraDB needs to decide which page to evict to make room for new pages. There are two eviction strategies and policies supported by CapybaraDB: FIRST_NON_DIRTY and  Least Recently Used (LRU). You will need to complete the logic related to the LRU policy.

// define the eviction policy

enum class EvictionPolicy {

  FIRST_NON_DIRTY,

  LRU

};

Least Recently Used Policy (LRU)

Under LRU policy, when the cache is full, CapybaraDB should evict the page that has been least recently accessed. A page access can be through a get, a lookup, or a write operation.

To achieve the LRU behavior, CapybaraDB’s pager layer maintains a doubly-linked list (lru_list_) and a hashmap (lru_map_); they are members of the Pager class (pager.h). You need to use these two data structures to achieve LRU behavior.

TODOs

The majority of your implementation will be done in pager_cache.cc. The existing code in the Pager layer will give you a general understanding on caching mechanisms. The codebase contains several "TODO" comments to guide your implementation. These "TODOs" highlight the specific logic you must implement for effective page cache management:

● Pager::updateLRU()

○ This function is crucial for maintaining the LRU behavior. The "TODO" within this function will require you to implement the logic that updates a page's usage information whenever it's accessed. This typically involves moving the page "most recently used" to the front of a linked list or similar data structure.

● evictPage()

○ This function removes pages from the cache when it reaches its capacity. The "TODO" within this function will require you to implement the logic that identifies the least recently used page and removes it from the cache.

● SqlitePagerPrivateCacheLookup()

○ This is a private method that searches the page cache for a specific page. The "TODO" within this function will require you to implement the logic that checks if a page exists within the cache and returns it in case its found.

By correctly implementing these "TODOs," you'll create a functional LRU page cache policy.

Objectives and Requirements

1. Task 0: Understand the Pager Layer(existing code):

○ Grasp the functions and structure of the Pager Layer within CapybaraDB.

○ Review the provided code structure and focus on the interaction between Page Cache, Pager Operations, Transaction Manager, and Journal Manager.

2. Task 1: Implement the Journaling Mechanism:

○ Focus on implementing journaling functionality for transactions. This includes creating, writing to, and restoring from journal files to maintain ACID properties during database operations.

3. Task 2: Implement the LRU Cache Algorithm

○ Implement the LRU (Least Recently Used) algorithm to manage page evictions in memory.