Skip to content

本章涉及代码都在 https://github.com/CN-GuoZiyang/MYDB/tree/master/src/main/java/top/guoziyang/mydb/backend/dm/pageIndex、https://github.com/CN-GuoZiyang/MYDB/tree/master/src/main/java/top/guoziyang/mydb/backend/dm/dataItemhttps://github.com/CN-GuoZiyang/MYDB/tree/master/src/main/java/top/guoziyang/mydb/backend/dm 中。

前言

本节将为 DM 层做收尾,介绍一个实现简单的页面索引。并且实现了 DM 层对于上层的抽象:DataItem。

页面索引

页面索引,缓存了每一页的空闲空间。用于在上层模块进行插入操作时,能够快速找到一个合适空间的页面,而无需从磁盘或者缓存中检查每一个页面的信息。

MYDB 用一个比较粗略的算法实现了页面索引,将一页的空间划分成了 40 个区间。在启动时,就会遍历所有的页面信息,获取页面的空闲空间,安排到这 40 个区间中。insert 在请求一个页时,会首先将所需的空间向上取整,映射到某一个区间,随后取出这个区间的任何一页,都可以满足需求。

PageIndex 的实现也很简单,一个 List 类型的数组。

java
public class PageIndex {
    // 将一页划成40个区间
    private static final int INTERVALS_NO = 40;
    private static final int THRESHOLD = PageCache.PAGE_SIZE / INTERVALS_NO;

    private List[] lists;
}

从 PageIndex 中获取页面也很简单,算出区间号,直接取即可:

java
public PageInfo select(int spaceSize) {
    int number = spaceSize / THRESHOLD;
    if(number < INTERVALS_NO) number ++;
    while(number <= INTERVALS_NO) {
        if(lists[number].size() == 0) {
            number ++;
            continue;
        }
        return lists[number].remove(0);
    }
    return null;
}

返回的 PageInfo 中包含页号和空闲空间大小的信息。

可以注意到,被选择的页,会直接从 PageIndex 中移除,这意味着,同一个页面是不允许并发写的。在上层模块使用完这个页面后,需要将其重新插入 PageIndex:

java
public void add(int pgno, int freeSpace) {
    int number = freeSpace / THRESHOLD;
    lists[number].add(new PageInfo(pgno, freeSpace));
}

在 DataManager 被创建时,需要获取所有页面并填充 PageIndex:

java
// 初始化pageIndex
void fillPageIndex() {
    int pageNumber = pc.getPageNumber();
    for(int i = 2; i <= pageNumber; i ++) {
        Page pg = null;
        try {
            pg = pc.getPage(i);
        } catch (Exception e) {
            Panic.panic(e);
        }
        pIndex.add(pg.getPageNumber(), PageX.getFreeSpace(pg));
        pg.release();
    }
}

注意在使用完 Page 后需要及时 release,否则可能会撑爆缓存。

DataItem

DataItem 是 DM 层向上层提供的数据抽象。上层模块通过地址,向 DM 请求到对应的 DataItem,再获取到其中的数据。

DataItem 的实现很简单:

java
public class DataItemImpl implements DataItem {
    private SubArray raw;
    private byte[] oldRaw;
    private DataManagerImpl dm;
    private long uid;
    private Page pg;
}

保存一个 dm 的引用是因为其释放依赖 dm 的释放(dm 同时实现了缓存接口,用于缓存 DataItem),以及修改数据时落日志。

DataItem 中保存的数据,结构如下:

[ValidFlag] [DataSize] [Data]

其中 ValidFlag 占用 1 字节,标识了该 DataItem 是否有效。删除一个 DataItem,只需要简单地将其有效位设置为 0。DataSize 占用 2 字节,标识了后面 Data 的长度。

上层模块在获取到 DataItem 后,可以通过 data() 方法,该方法返回的数组是数据共享的,而不是拷贝实现的,所以使用了 SubArray。

java
@Override
public SubArray data() {
    return new SubArray(raw.raw, raw.start+OF_DATA, raw.end);
}

在上层模块试图对 DataItem 进行修改时,需要遵循一定的流程:在修改之前需要调用 before() 方法,想要撤销修改时,调用 unBefore() 方法,在修改完成后,调用 after() 方法。整个流程,主要是为了保存前相数据,并及时落日志。DM 会保证对 DataItem 的修改是原子性的。

java
@Override
public void before() {
    wLock.lock();
    pg.setDirty(true);
    System.arraycopy(raw.raw, raw.start, oldRaw, 0, oldRaw.length);
}

@Override
public void unBefore() {
    System.arraycopy(oldRaw, 0, raw.raw, raw.start, oldRaw.length);
    wLock.unlock();
}

@Override
public void after(long xid) {
    dm.logDataItem(xid, this);
    wLock.unlock();
}

after() 方法,主要就是调用 dm 中的一个方法,对修改操作落日志,不赘述。

在使用完 DataItem 后,也应当及时调用 release() 方法,释放掉 DataItem 的缓存(由 DM 缓存 DataItem)。

java
@Override
public void release() {
    dm.releaseDataItem(this);
}

DM 的实现

DataManager 是 DM 层直接对外提供方法的类,同时,也实现成 DataItem 对象的缓存。DataItem 存储的 key,是由页号和页内偏移组成的一个 8 字节无符号整数,页号和偏移各占 4 字节。

DataItem 缓存,getForCache(),只需要从 key 中解析出页号,从 pageCache 中获取到页面,再根据偏移,解析出 DataItem 即可:

java
@Override
protected DataItem getForCache(long uid) throws Exception {
    short offset = (short)(uid & ((1L << 16) - 1));
    uid >>>= 32;
    int pgno = (int)(uid & ((1L << 32) - 1));
    Page pg = pc.getPage(pgno);
    return DataItem.parseDataItem(pg, offset, this);
}

DataItem 缓存释放,需要将 DataItem 写回数据源,由于对文件的读写是以页为单位进行的,只需要将 DataItem 所在的页 release 即可:

java
@Override
protected void releaseForCache(DataItem di) {
    di.page().release();
}

从已有文件创建 DataManager 和从空文件创建 DataManager 的流程稍有不同,除了 PageCache 和 Logger 的创建方式有所不同以外,从空文件创建首先需要对第一页进行初始化,而从已有文件创建,则是需要对第一页进行校验,来判断是否需要执行恢复流程。并重新对第一页生成随机字节。

java
public static DataManager create(String path, long mem, TransactionManager tm) {
    PageCache pc = PageCache.create(path, mem);
    Logger lg = Logger.create(path);
    DataManagerImpl dm = new DataManagerImpl(pc, lg, tm);
    dm.initPageOne();
    return dm;
}

public static DataManager open(String path, long mem, TransactionManager tm) {
    PageCache pc = PageCache.open(path, mem);
    Logger lg = Logger.open(path);
    DataManagerImpl dm = new DataManagerImpl(pc, lg, tm);
    if(!dm.loadCheckPageOne()) {
        Recover.recover(tm, lg, pc);
    }
    dm.fillPageIndex();
    PageOne.setVcOpen(dm.pageOne);
    dm.pc.flushPage(dm.pageOne);
    return dm;
}

其中,初始化第一页,和校验第一页,基本都是调用 PageOne 类中的方法实现的:

java
// 在创建文件时初始化PageOne
void initPageOne() {
    int pgno = pc.newPage(PageOne.InitRaw());
    assert pgno == 1;
    try {
        pageOne = pc.getPage(pgno);
    } catch (Exception e) {
        Panic.panic(e);
    }
    pc.flushPage(pageOne);
}

// 在打开已有文件时时读入PageOne,并验证正确性
boolean loadCheckPageOne() {
    try {
        pageOne = pc.getPage(1);
    } catch (Exception e) {
        Panic.panic(e);
    }
    return PageOne.checkVc(pageOne);
}

DM 层提供了三个功能供上层使用,分别是读、插入和修改。修改是通过读出的 DataItem 实现的,于是 DataManager 只需要提供 read()insert() 方法。

read() 根据 UID 从缓存中获取 DataItem,并校验有效位:

java
@Override
public DataItem read(long uid) throws Exception {
    DataItemImpl di = (DataItemImpl)super.get(uid);
    if(!di.isValid()) {
        di.release();
        return null;
    }
    return di;
}

insert() 方法,在 pageIndex 中获取一个足以存储插入内容的页面的页号,获取页面后,首先需要写入插入日志,接着才可以通过 pageX 插入数据,并返回插入位置的偏移。最后需要将页面信息重新插入 pageIndex。

java
@Override
public long insert(long xid, byte[] data) throws Exception {
    byte[] raw = DataItem.wrapDataItemRaw(data);
    if(raw.length > PageX.MAX_FREE_SPACE) {
        throw Error.DataTooLargeException;
    }

    // 尝试获取可用页
    PageInfo pi = null;
    for(int i = 0; i < 5; i ++) {
        pi = pIndex.select(raw.length);
        if (pi != null) {
            break;
        } else {
            int newPgno = pc.newPage(PageX.initRaw());
            pIndex.add(newPgno, PageX.MAX_FREE_SPACE);
        }
    }
    if(pi == null) {
        throw Error.DatabaseBusyException;
    }

    Page pg = null;
    int freeSpace = 0;
    try {
        pg = pc.getPage(pi.pgno);
        // 首先做日志
        byte[] log = Recover.insertLog(xid, pg, raw);
        logger.log(log);
        // 再执行插入操作
        short offset = PageX.insert(pg, raw);

        pg.release();
        return Types.addressToUid(pi.pgno, offset);

    } finally {
        // 将取出的pg重新插入pIndex
        if(pg != null) {
            pIndex.add(pi.pgno, PageX.getFreeSpace(pg));
        } else {
            pIndex.add(pi.pgno, freeSpace);
        }
    }
}

DataManager 正常关闭时,需要执行缓存和日志的关闭流程,不要忘了设置第一页的字节校验:

java
@Override
public void close() {
    super.close();
    logger.close();

    PageOne.setVcClose(pageOne);
    pageOne.release();
    pc.close();
}

以上,DM 层完结。

今天是 2021 年 12 月 11 日,A-SOUL 一周年直播。祝 A-SOUL 一周年快乐!还会有两周年、三周年、十周年!鸟巢见!!!

我们是,ASOUL!

如有转载或 CV 请标注本站原文地址