Stage 6 : Buffer Management and Disk Write-back (12 hours)

Learning Objectives

• Implement the commands to rename relations and attributes
• Implement the LRU algorithm to free up space in the buffer by writing back to the disk when the buffer becomes fully occupied

PREREQUISITE READING

• Data Definition Language (DDL) Commands

Introduction

This far, we've covered a lot of the functionality of NITCbase involving reading from the disk. You've implemented a read-only buffer and a cache for the catalog entries. In this stage, we will discuss operations involving writing back to the disk. You will implement the ALTER TABLE RENAME and ALTER TABLE RENAME COLUMN commands which are used to rename a relation and it's attributes respectively.

Block Replacement

In our implementation so far, every time we want to access a block, we load it into a buffer and then do all our read operations from that. Recall that in the Buffer Layer, StaticBuffer allows us to buffer BUFFER_CAPACITY(=32) blocks at any given time. What if we want to read from a new block? We will obviously have to reuse an existing slot to load in our new block.

NITCbase uses the LRU(least recently used) algorithm to decide on the block that will be replaced. Each entry in the buffer has a corresponding timestamp field which keeps track of how long it has been since the disk block buffered in that particular location has been used. When a position needs to be freed up, the disk block with the highest timestamp is chosen and changes, if any, are written back to the disk.

Each entry in the buffer also has a corresponding dirty field which is a boolean value storing if the values in that buffer entry have been updated since they were loaded from the disk block. If the dirty bit is set for an entry, we will write it back to the disk when the entry is replaced in the buffer or at system exit.

Implementation

The ALTER TABLE RENAME and ALTER TABLE RENAME COLUMN commands modify the schema of a relation and are hence handled by the Schema Layer. NITCbase requires that a relation be closed before its schema can be edited. To update a relation name or attribute name, we will need to update the corresponding entries in the relation and/or attribute catalog blocks. These changes will subsequently be written back to the disk from the disk buffer.

A sequence diagram showing the call sequence involved in the implementation of this functionality is shown below.

NOTE: The functions are denoted with circles as follows.
🔵 -> methods that are already in their final state
🟢 -> methods that will attain their final state in this stage
🟠 -> methods that we will modify in this stage, and in subsequent stages

A class diagram showing the methods relevant to this functionality in the Schema Layer, Block Access Layer and Buffer Layer is shown below.

---

Buffer Layer

As shown in the sequence diagram above, the Frontend User Interface will parse the ALTER TABLE RENAME command and call the Frontend::alter_table_rename() function in the Frontend Programming Interface. This call is then transferred along to the Schema Layer. Hence, the implementation of the Frontend::alter_table_rename() function only involves a call to the Schema::renameRel() function. Similarly, the ALTER TABLE RENAME COLUMN command leads to the Frontend::alter_table_rename_column() function which in turn transfers control to Schema::renameAttr().

Frontend/Frontend.cpp

int Frontend::alter_table_rename(char relname_from[ATTR_SIZE], char relname_to[ATTR_SIZE]) {
  return Schema::renameRel(relname_from, relname_to);
}

int Frontend::alter_table_rename_column(char relname[ATTR_SIZE], char attrname_from[ATTR_SIZE],
                                        char attrname_to[ATTR_SIZE]) {
  return Schema::renameAttr(relname, attrname_from, attrname_to);
}

Now, let us implement the functions in the Schema Layer

The Schema::renameRel() and Schema::renameAttr() functions ensure that the relation is closed and the input is for a valid operation. Subsequently, they call the respective Block Access Layer functions BlockAccess::renameRelation() and BlockAccess::renameAttribute().

Schema/Schema.cpp

Implement the following functions looking at their respective design docs

• Schema::renameRel()
• Schema::renameAttr()

The Block Access Layer functions will then call linearSearch() to iterate through the relation and attribute catalog blocks and find the entries corresponding to the required relation. It then uses RecBuffer::getRecord() and RecBuffer::setRecord() to fetch the existing record value, update the name and then write the updated record back into the disk block. (The implementation of the RecBuffer::setRecord() function will be described later in this stage.)

BlockAccess/BlockAccess.cpp

Implement the following functions looking at their respective design docs

• BlockAccess::renameRelation()
• BlockAccess::renameAttribute()

Now, the only functionality we have left to implement is in the Buffer Layer. In the StaticBuffer class, we update the StaticBuffer::getFreeBuffer() function to implement our block replacement algorithm if there are no free slots in the buffer. We also modify the constructor and destructor to work with the changes we discussed and implement StaticBuffer::setDirtyBit().

Buffer/StaticBuffer.cpp

StaticBuffer::StaticBuffer() {

  for (/*bufferIndex = 0 to BUFFER_CAPACITY-1*/) {
    // set metainfo[bufferindex] with the following values
    //   free = true
    //   dirty = false
    //   timestamp = -1
    //   blockNum = -1
  }
}

// write back all modified blocks on system exit
StaticBuffer::~StaticBuffer() {
  /*iterate through all the buffer blocks,
    write back blocks with metainfo as free=false,dirty=true
    using Disk::writeBlock()
    */
}

TASK: Implement the following functions looking at their respective design docs

• StaticBuffer::getFreeBuffer()
• StaticBuffer::setDirtyBit()

In the RecBuffer class, we modify the BlockBuffer::loadBlockAndGetBufferPtr() function to increment the timestamp field for the buffer blocks and call the StaticBuffer::getFreeBuffer() function to allocate a free buffer if required. We also implement the RecBuffer::setRecord() function which is used to update the value of a record at a particular slot in the disk block.

Buffer/BlockBuffer.cpp

Implement the following functions looking at their respective design docs

• BlockBuffer::loadBlockAndGetBufferPtr()
• RecBuffer::setRecord()

And that's it! You should now be able to rename any relation (except RELCAT and ATTRCAT of course) and any attribute of a relation. We have also implemented the basis of writing blocks back to the disk which we will expand upon in later stages.

Exercises

Q1. In the XFS interface, create a relation Books(name STR, author STR, price NUM, bookOwner STR). Then, in your NITCbase, run the following commands.

ALTER TABLE RENAME Books TO LibraryBooks;
ALTER TABLE RENAME LibraryBooks COLUMN bookOwner TO lender;
OPEN TABLE LibraryBooks;
SELECT * FROM LibraryBooks INTO null WHERE price>0;
exit

Ensure that you get the following output.

| name | author | price | lender |
Selected successfully into null

Now, let's confirm whether the changes have been written back to the disk. Open the XFS Interface and verify the output of the schema command.

# schema LibraryBooks
Relation: LibraryBooks
Attribute        Type Index
---------------- ---- -----
name             STR  no
author           STR  no
price            NUM  no
lender           STR  no

Q2. In this exercise, we will test the error conditions of the rename functionality. Run the following commands in your NITCbase and ensure that you get the corresponding output.

alter table rename LibBooks to Books            # Error: Relation does not exist
alter table rename LibraryBooks to Students     # Error: Relation already exists
alter table rename LibraryBooks to RELATIONCAT  # Error: This operation is not permitted
open table LibraryBooks                         # Relation LibraryBooks opened successfully
alter table rename LibraryBooks to LibBooks     # Error: Relation is open