Kahadb – PageFile

0

Introduction

Kahadb is the file persistence database. ActiveMQ uses it to persist the messages.
It is made up of four main components.

  1. Page File
  2. B-Tree Index
  3. Journal File
  4. Message Database

KahaDb message database mainly depends on Page File, B-Tree index and Journal File components whereas B-Tre index depends only on the Page File. Page File and Journal File are independent from functional perspective.
Kahadb - PageFile

 

In this article we will discuss about the PageFile

Page File

Since the main objective of a file persistence database is to allow read/write objects to/from file, performance plays an important point in the design.

Kahadb uses paging to store and read data from file which means instead of reading a byte at a time, it would read a block of bytes called page thereby minimising I/O operations. The default page size is 4k bytes.

 

Kahadb - PageFile

Overflow

When the object we trying to store exceeds the page size it is called an overflow. Whenever there is an overflow, an additional page is allocated to accommodate the extra bytes. Thus a storage operation may involve one or more pages.

Transaction

In case we want to rollback the operation, the pages used must be freed. This is where the concept of transaction comes.
Page read/update is done within a transaction. Transaction allows us to do multiple update operations in a single unit of work which can be either committed or roll-backed.
We will try to understand the mechanics using an example. Let’s try to store first.

Example

Below example stores “Hello world”.

1. PageFile pf = new PageFile(“testdir”, “myfile”);
2. pf.load();
3. Transaction tx = pf.tx();
4. Page page = tx.allocate();
5. page.set(“Hello world”);
6. tx.store(page, StringMarshaller.INSTANCE, true);
7. tx.commit();
  1. PageFile constructor: we pass-in the directory and file name.
  2. Page File load: creates read and write file handlers .
  3. Creates a transaction to do page read/wite.
  4. Allocates a page
  5. Sets the data object to the allocated page
  6. Store: The data object gets marshalled to bytes. The bytes may exceed the page size. New pages are allocated as and when an overflow is encountered. Each page update is cached within the transaction.
  7. Commits the transaction to the PageFile as a single ‘Unit of Work’. Either all cached page updates associated with the transaction are written to disk or none will. The cached page updates are cleared.

Each of the above step does a lot more than what I have mentioned but we will get to that later.

Question Time

How do we know whether the pages allocated in a transaction belong to same transaction?
Each Transaction is assigned an ID and the pages allocated within a transaction will all get the same transaction ID.

What happens in case of an overflow?
If the object to be stored need more space than the page to which it is been written, a new page is allocated and the previous page is linked to the new page.

 

Kahadb - PageFile

 

 

What is the relation between Transaction and PageFile?

A PageFile can have one or more transactions.
Kahadb - PageFile

 

What happens to the allocated pages when we rollback a transaction?
All the allocated pages within the transaction are freed.

What will be the allocated page ID?
The page ID is a sequential number. The first allocated page would be 0. The next would be 1 and so on. PageFile is responsible to allocate the page. It knows the last page ID so next allocated page will be the next number in sequence.

What is the siginificance of a page ID?
The page ID determines the offset in the file from where the page data begins so page ID helps the file handler to jump to the offset and start reading or writing.
Offset = pageID * page size.

What is a free page list?
If we want to remove the object that a page is holding we free the page. If the object spans more than one page, all the pages involved will be freed. The pages freed will be added to a free page list. Once we commit the transaction, the pages freed within the transaction will be added to the PageFile’s free page list.

Once a page is freed, is it eligible for reuse?
Yes, when a PageFile allocates a page, it will always try to take one from the free list. If there is none, it will allocate a new page.

Does Tansaction object allocate the page?
No, it is the PageFile that allocates the page. Transaction delegates the allocation call to PageFile. A PageFile can have more than one transactions and there can be more than one thread concurrently requesting for new pages which is why it is the responsibility of PageFile to allocate new pages as it knows the last page ID allocated and the freed page list.

How many page updates can a transaction accomodate?

There is a limit to the transaction size and it is configurable.

What happens if the transaction reaches the maximum allowed transaction size?
It will write to a temporary file instead of writing to a cache.

What is the state of a transaction?
It holds the page updates, temporary file, transaction ID, the free pages and allocated pages.

 

Kahadb - PageFile

Example:

We will now use an example to further understand the operations like store, free, commit and rollback.
Our objective would be to store Book object to a file. Book class is a simple bean which contain some basic attributes about the book.

 
    public class Book {
        String author;
        String name;
        Date releaseDate;
        double ver;
    }

    private Book createBook(String name, int count) {
        Book book = new Book();
        book.author = "Ram Satish";
        book.name = name + count + 
                    "Testing kahadb Transaction................................................";
        book.releaseDate = new Date();
        book.ver = 1.22111;
        return book;
    }

Test creates two transactions (concurently). In each transaction, we create three Book objects and store them in a file. Since we use multiple threads, we make the PageFile thread safe by extending PageFile and synchronize the page allocation.

   public class PageFileSync extends PageFile {
        public PageFileSync(File directory, String name) {
            super(directory, name);
        }
        synchronized  Page allocate(int count) throws IOException {
            return super.allocate(count);
        }
    }

Book transaction to store Books:

private class BookTx implements Runnable {
        public void run() {
            tx = pageFile.tx();
            for (int i = 0; i < 3; i++) {
                try {
                    Page page = tx.allocate();
                    pageList.add(page);
                    page.set(createBook(name, i));
                    tx.store(page, bookMarshaller, true);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }
}

BookMarshaller marshalls and un-marshalls the Book object.

private class BookMarshaller implements Marshaller {
        public void writePayload(Book book, DataOutput dataOut) throws IOException {
            dataOut.writeUTF(book.author);
            dataOut.writeUTF(book.name);
            dataOut.writeLong(book.releaseDate.getTime());
            dataOut.writeDouble(book.ver);
        }
        public Book readPayload(DataInput dataIn) throws IOException {
            Book book = new Book();
            book.author = dataIn.readUTF();
            book.name = dataIn.readUTF();
            book.releaseDate = new Date(dataIn.readLong());
            book.ver = dataIn.readDouble();
            return book;
        }
}

First part of the test is about storage. It creates two Book transactions running in separate threads. It then commits the transactions and unloads the page file.

Public void testStore() {
        PageFileSync pf = new PageFileSync(new File("target/test-data"), getName());
        pf.setPageSize(63);
        pf.delete();
        pf.load();
        BookTx bookTx1 = new BookTx(pf, "A");
        BookTx bookTx2 = new BookTx(pf, "B");
        Thread th1 = new Thread(bookTx1);
        Thread th2 = new Thread(bookTx2);
        th1.start();
        th2.start();
        th1.join();
        th2.join();
        bookTx1.commit();
        bookTx2.commit();
        pf.unload();
}

The second part of the test case, re-loads the PageFile, creates a transaction to load the pages. It then asserts that the number of Books objects read is six.

public void testRead {
....
        pf.load();
        Transaction tx = pf.tx();
 ...
        for (Page page : allPages) {
            page = tx.load(page.getPageId(), bookMarshaller());
            books.add(page.get());
        }
        assertEquals(6, books.size());
}

In the last part of the test case, we free one of the pages to remove the Book object. The number of Books objects read should be five.

public void testRemove() {
....
        tx.free(allPages.get(2).getPageId());
        tx.commit();
        books.clear();
        pf.unload();
        pf.load();
        for (Page page : allPages) {
            page = tx.load(page.getPageId(), null);
            if (Page.PAGE_FREE_TYPE == page.getType()) {
                continue;
            } else {
                page = tx.load(page.getPageId(), bookMarshaller());
                books.add(page.get());
            }
        }
        assertEquals(5, books.size());
}

If instead of commit, we rollback then the book count will remain at six. Below is how the state of PageFile looks like:

 

Kahadb - PageFile

 

In my next article, we will discuss about transaction’s page load.

Share.

Leave A Reply