Proj2 BufferPool

CS61B

BufferPool

BufferPool manages the reading and writing of pages into memory from disk and store up to numPages pages, so I added member variables maxPageNum and HashMap<PageId, Page> pageMap.

/**
 * BufferPool manages the reading and writing of pages into memory from
 * disk. Access methods call into it to retrieve pages, and it fetches
 * pages from the appropriate location.
 * 
public class BufferPool {
    /** Bytes per page, including header. */
    public static final int PAGE_SIZE = 4096;
    /** Default number of pages passed to the constructor. This is used by
     other classes. BufferPool should use the numPages argument to the
     constructor instead. */
    public static final int DEFAULT_PAGES = 50;
    public int maxPageNum;
    public HashMap<PageId,Page> pageMap;
    /**
     * Creates a BufferPool that caches up to numPages pages.
     *
     * @param numPages maximum number of pages in this buffer pool.
     */
    public BufferPool(int numPages) {
        // some code goes here
        this.maxPageNum = numPages;
        this.pageMap = new HashMap<>();
    }

Then, I wrote getPage() method. Retrieve the specified page with the associated permissions. The retrieved page should be looked up in the buffer pool. If it is present, it should be returned. If it is not present, it should be added to the buffer pool and returned. If there is insufficient space in the buffer pool, an page should be evicted and the new page should be added in its place.

public Page getPage(TransactionId tid, PageId pid, Permissions perm)
            throws TransactionAbortedException, DbException {
        // some code goes here
        if(pageMap.containsKey(pid)){
            return pageMap.get(pid);
        }else{
            //use PageId to get TableId, then use TableId to get DbFile,
            //then readPage from DbFile, now you have the Page and PageId
            //so that you can put it to the BufferPool pageMap, then return;
            DbFile dbfile = Database.getCatalog().getDbFile(pid.getTableId());
            Page newpage = dbfile.readPage(pid);
            if( pageMap.size() >= maxPageNum){
                Random random = new Random();
                int i = random.nextInt(maxPageNum);
                int j = 0;
                for(PageId pid1 : pageMap.keySet()){
                    if( i == j){
                        pageMap.remove(random);
                        pageMap.put(pid, newpage);
                    }
                    j++;
                }
            }else {
                pageMap.put(pid, newpage);
            }
            return pageMap.get(pid);
        }
    }

Here, I used containsKey() for the first time. It is a method for HashMap data structure to check whether it contains a certain key, pretty straighforward.

Also, I used util.Random for the first time. This class it used to generate random number, here's a basic intro for how to use it.

Random基本用法

Random类提供了更为丰富的随机方法，它的方法不是静态方法，使用Random，先要创建一个Random实例，看个例子：

Random rnd = new Random();
System.out.println(rnd.nextInt());
System.out.println(rnd.nextInt(100));

我的电脑上的一次运行，输出为：

-1516612608
23
nextInt()产生一个随机的int，可能为正数，也可能为负数，nextInt(100)产生一个随机int，范围是0到100，包括0不包括100。
计算机程序的思维逻辑 (34) - 随机

Then, I used forEach loop which I rarely use and here's a fairly straightforward example:

public Page getPage(TransactionId tid, PageId pid, Permissions perm)
            throws TransactionAbortedException, DbException {
        // some code goes here
        if(pageMap.containsKey(pid)){
            return pageMap.get(pid);
        }else{
            //use PageId to get TableId, then use TableId to get DbFile,
            //then readPage from DbFile, now you have the Page and PageId
            //so that you can put it to the BufferPool pageMap, then return;
            DbFile dbfile = Database.getCatalog().getDbFile(pid.getTableId());
            Page newpage = dbfile.readPage(pid);
            if( pageMap.size() >= maxPageNum){
                Random random = new Random();
                int i = random.nextInt(maxPageNum);
                int j = 0;
                for(PageId pid1 : pageMap.keySet()){
                    if( i == j){
                        pageMap.remove(random);
                        pageMap.put(pid, newpage);
                    }
                    j++;
                }
            }else {
                pageMap.put(pid, newpage);
            }
            return pageMap.get(pid);
        }
    }

In my implementation for getPage(), I got a better understanding of the structure of the database.

储存

Catalog 储存了所有表的信息。每个表的信息包括：name，schema，相应的 DbFile，以及 primary key。

SimpleDB 只支持两种 field(column），Interger 和 fixed length string。

每个表的 schema 用 RowDesc 定义，其储存每个 filed(column) 的 type 和 name。其除了支持用 index (offset) 获得 field 的 type 或 name，用 name 获得 field 的 index，还提供一个静态方法用于 merge 两个 RowDesc 获得一个新的 RowDesc （Join operator 使用）

row 用来储存 field(column)，其除了提供第 i 个 field 的 getter/setter，还提供了所有 field(column) 的 iterator。
row 有一个 record id(rowid) 标志其在磁盘中的位置。

HeapPage 实现了 Page 接口。用一个 PageId 唯一标志，用来储存 rows，其用一个 byte[] header 作为bitmap。
其支持在该 page 上插入/删除 row，标志该 page 为 dirty。还提供了迭代器用来迭代 page 中所有的row。
其支持将 page 实例序列化为 byte[] 和由 byte[] 构建 page 实例。

HeapFile 实现了 DbFile 的接口，其提供唯一的 ID，以及获得文件系统 File，table schema 的 API。
其支持从从磁盘获取数据(byte []), 并构建相应 page 实例。和将 page 序列化到磁盘。

bufferpool 存放了当前所有的 page 实例，如果已满，则会剔除某个page(如果 page 为 dirty，则 flush 到磁盘)。
所有对数据(都是以 page，也就是构建 HeapPage 实例)的访问都要经由 buffer pool （调用 getPage API）

这里必须要理清：
数据是储存在磁盘中的（支持序列化），当需要访问时，都会通过 bufferpool 获得。后者调用相应的 HeapFile 从磁盘中获得数据并生成 HeapPage 实例放入 bufferpool。
当 bufferpool 已满，会 kick out 一个page，如果那个 page 是 dirty 的，会先 flush 到磁盘（通过调用 HeapFile 的 writePage API）。

SimpleDB