基础实现思路和难度总结

使用VM虚拟机搭建ubuntu 的linux系统环境,安装cmake,git,g++等等关键依赖。

数据类认识

对于table来说,有TablePage,TableScan,Table,Record,RecordHeader

  • TablePage:是对数据底层进行操作的中间者,在读入Page数据后,对数据的位置进行解析,作为底层数据的管理者,可以操作和读取或修改指定的例如lower upper指针,下一页指针等数据。进行的修改会直接改到数据页上。
  • Table:TablePage的上层,类似于用于提供给用户,更加简练的功能函数。
  • Record:记录,也就是插入的数据条,由记录头和记录数据本身组成,也是对底面数据的管理者。
  • RecordHeader:精化版Record,只读取头文件部分,有的时候只要头文件数据。
  • BufferPool:管理内存池,用于申请页内存和清理内存等等。
  • Page:页类,存储页的数据,存储页的状态(是否是脏页),可以交给TablePage在Page上进行修改。

记录插入查找lab/10

table/table.cpp

插入记录功能InsertRecord

原理理解:

插入记录功能实际上就是往页当中放入数据,如果页有剩余空间,就把记录插入这个页,如果没有剩余空间,就去看下一个页是否有,如果都没有,就去向内存池需求一个页面。

函数实现:

可以通过参数和类里面的成员变量从BufferPool中读取到第一个页面。

由于页面Page是单纯的底层数据,因此利用TablePage,可以获取到下一个Page的指针,TablePage也允许支持了获取剩余空间大小,对于参数Record,也可以获取大小,就可以判断是否有足够的空间。

先对起始页面进行判断是否有足够空间或者是否没有页。

类链表地遍历所有页面,如果有空间,则插入。

如果没有空间,创建新页面,同时要设置指针更新。

Rid Table::InsertRecord(std::shared_ptr<Record> record, xid_t xid, cid_t cid, bool write_log) {
  if (record->GetSize() > MAX_RECORD_SIZE) {
    throw DbException("Record size too large: " + std::to_string(record->GetSize()));
  }
  // LAB 1 DONE
  pageid_t curPageID = first_page_id_;
  bool hasInserted = false;
  std::shared_ptr<TablePage> curPageHandle;

  slotid_t resSlotID = 0;
  pageid_t resPageID = 0;

  if(first_page_id_ == NULL_PAGE_ID){
    std::shared_ptr<Page> newPgae = buffer_pool_.NewPage(db_oid_, oid_, 0);
    first_page_id_ = 0;
    curPageHandle = std::make_shared<TablePage>(newPgae);
    curPageHandle->Init();
    curPageHandle->SetNextPageId(NULL_PAGE_ID);
    hasInserted = true;

    resSlotID = curPageHandle->InsertRecord(record, xid, cid);
    resPageID = 0;
  }

  while(not hasInserted){
    std::shared_ptr<Page> page = buffer_pool_.GetPage(db_oid_, oid_, curPageID);
    curPageHandle = std::make_shared<TablePage>(page);
    if(curPageHandle->GetFreeSpaceSize() > record->GetSize()){
      hasInserted = true;
      resSlotID = curPageHandle->InsertRecord(record, xid, cid);
      resPageID = curPageID;
      break;
    }
    if(curPageHandle->GetNextPageId() == NULL_PAGE_ID){
      break;
    }else{
      curPageID = curPageHandle->GetNextPageId();
    }
  }
  
  if(not hasInserted){
    pageid_t newPageID = curPageID + 1;
    curPageHandle->SetNextPageId(newPageID);
    std::shared_ptr<Page> newPage = buffer_pool_.NewPage(db_oid_, oid_, newPageID);

    curPageHandle = std::make_shared<TablePage>(newPage);
    curPageHandle->Init();
    curPageHandle->SetNextPageId(NULL_PAGE_ID);
    
    hasInserted = true;
    resSlotID = curPageHandle->InsertRecord(record, xid, cid);
    resPageID = newPageID;
  }

  return {resPageID, resSlotID};
}

table/table_page.cpp

底层插入记录功能InsertRecord

原理理解:

先要了解记录在底层数据上是如何管理的,本架构建立于变长记录的存储,因此,每个数据分成两份,一份是记录位置的,一份是记录数据本身。

记录位置由于是固定长度,所以存储在开头位置,数据本身由于是变长数据,因此放在尾巴,记录位置的数据要记录尾巴里数据的位置。这也被称作为一个槽。完成对页面数据的修改后,不能忘记将页变为脏页。

函数实现:

我们已经知道有lower指针和upper指针了,根据原理,lower指针应当存放槽的数据位置信息,在本架构中有Slot类,有两个数据,offset以及size。

根据数据大小,先更新upper和lower指针,upper加上一个Slot的大小,lower减去一个Record大小长度。

对于数据,使用架构中有的反序列化函数写入Upper指针,再将当前的数据位置和大小信息存入Slot,丢入Slot数组(写入)。

通过Page类标记Page为脏页。

slotid_t TablePage::InsertRecord(std::shared_ptr<Record> record, xid_t xid, cid_t cid) {
  // LAB 1 DONE
  db_size_t recordSize = record->GetSize();
  slotid_t slot_id = GetRecordCount();
  *upper_ -= recordSize;
  *lower_ += sizeof(Slot);

  slots_[slot_id].offset_ = *upper_;
  slots_[slot_id].size_ = recordSize;

  record->SerializeTo(page_data_ + slots_[slot_id].offset_);
  page_->SetDirty();

  return slot_id;
}

获取数据记录功能GetRecord

原理理解:

通过slot_id找到指定数据位置,从对应的数据位置读取Record即可。

函数实现:

从slot数组也就是Page的前面获取offet,创建一个Record共享指针,通过offset读取对应数据。

std::shared_ptr<Record> TablePage::GetRecord(Rid rid, const ColumnList &column_list) {
  // LAB 1 DONE
  std::shared_ptr<Record> result = std::make_shared<Record>();
  result->SetRid(rid);
  db_size_t offset = slots_[rid.slot_id_].offset_;
  result->DeserializeFrom(page_data_ + offset, column_list);

  return result;
}

table/table_scan.cpp

原理理解:

对表内的所有数据进行读取,这是一个类似于迭代器一样的函数,使用一次就会返回一个数据并且更新自己的状态,用于迭代表内的所有记录,迭代完成之后就会返回空指针。所以实际上,也就是从数据表中获取所有页,对页面进行迭代,再对页面的所有记录进行迭代并返回即可。

函数实现:

先获取锁在的Page,使用TablePage读取数据,进行迭代,获取槽的数量,遍历每个页面的每个槽。需要注意的是,如果读取到被删除的数据则需要跳过当前读取下一个。

std::shared_ptr<Record> TableScan::GetNextRecord(xid_t xid, IsolationLevel isolation_level, cid_t cid,
                                                 const std::unordered_set<xid_t> &active_xids) {
  if (rid_.page_id_ == NULL_PAGE_ID) {
    return nullptr;
  }

  oid_t dbOid = table_->GetDbOid();
  oid_t oid = table_->GetOid();
  std::shared_ptr<Page> curPage = buffer_pool_.GetPage(dbOid, oid, rid_.page_id_);
  if (curPage == nullptr) {
    return nullptr;
  }
  
  TablePage pageHandle(curPage);
  db_size_t recordCnt = pageHandle.GetRecordCount();

  while (true) {

    if (rid_.slot_id_ >= recordCnt) {
      rid_.page_id_ = pageHandle.GetNextPageId();
      rid_.slot_id_ = 0;
      if (rid_.page_id_ == NULL_PAGE_ID) {
        return nullptr;
      }
      curPage = buffer_pool_.GetPage(dbOid, oid, rid_.page_id_);
      if (curPage == nullptr) {
        return nullptr;
      }
      pageHandle = TablePage(curPage);
      recordCnt = pageHandle.GetRecordCount();
    }

    std::shared_ptr<Record> result = pageHandle.GetRecord(rid_, table_->GetColumnList());
    if (result->IsDeleted()) {
      rid_.slot_id_++;
      continue;
    }

    rid_.slot_id_++;
    return result;
  }
}

至此完成lab/10的所有实验测试 PASS

数据删除

table/table.cpp

记录删除功能DeleteRecord

原理理解:

作为删除记录的上层操作,只要根据接口做事即可,也就是先获得Page位置,再根据槽id删除对应数据。

函数实现:

void Table::DeleteRecord(const Rid &rid, xid_t xid, bool write_log) {
  std::shared_ptr<Page> page = buffer_pool_.GetPage(db_oid_, oid_, rid.page_id_);
  TablePage pageHandle(page);
  pageHandle.DeleteRecord(rid.slot_id_, xid);
}

table/table_page.cpp

底层记录删除功能DeleteRecord

原理理解:

从数据的底层角度来考虑,对于数据来说,如果一个数据被删除,并不需要清除他的空间,只需要做一个标记,等待他被其他数据覆写即可。因此实际的删除操作只要去做一个标记就可以了

函数实现:

这个标记处于记录的头数据中,因此使用Header读取,只修改Header中的是否删除标记即可。

void TablePage::DeleteRecord(slotid_t slot_id, xid_t xid) {
  // LAB 1 DONE
  Record header;
  header.DeserializeHeaderFrom(page_data_ + slots_[slot_id].offset_);
  header.SetDeleted(true);
  header.SerializeHeaderTo(page_data_ + slots_[slot_id].offset_);
  page_->SetDirty();
}

至此完成lab/20和lab/30,删除和更新,由于本架构的更新是删除加插入,因此也同步完成。

LRU缓存替换策略

原理理解:

缓存替换发生在缓存的页面过多,当我读取一个没有缓存的页面,就有页面需要被释放掉,根据启发式的贪心,我们可以认为,此时应该释放最少使用的,根据LRU策略,我们使用一个队列来具体化操作行为,如果使用了一个点,这个点如果不在队列中,就把他塞入头部,如果在队列中,那就把它从队列中移动到头部。如果需要释放最不常用的Page,那么恭喜,就在队列的尾巴处。

函数实现:

由以上原理我们可以发现,需要我们对中间的元素进行删除和插入到开头,同时还要对尾巴使用删除。因此我们认为,双向链表可以很好的做到这个事情。同时,我们要记录元素对应的指针位置,不然很难判断这个元素是否在队列内,并且删除的时候需要知道他的位置。我们使用一个哈希表来完成这个任务。

class LRUBufferStrategy : public BufferStrategy {
 public:
	void LRUBufferStrategy::Access(size_t frame_no) {
	  // 缓存页面访问
	  // LAB 1 DONE
	  auto it = cache_map_.find(frame_no);
	  if(it == cache_map_.end()){
	    cache_items_.insert(cache_items_.begin(), frame_no);
	    cache_map_[frame_no] = cache_items_.begin();
	  }else{
	    cache_items_.splice(cache_items_.begin(), cache_items_, it->second);
	  }
	};
	size_t LRUBufferStrategy::Evict() {
	  // 缓存页面淘汰,返回淘汰的页面在 buffer pool 中的下标
	  // LAB 1 DONE
	  size_t res = cache_items_.back();
	  cache_items_.pop_back();
	  return res;
	}
 private:
  std::list<size_t> cache_items_;
  std::unordered_map<size_t, std::list<size_t>::iterator> cache_map_;
};

至此完成lab/50测试

难度和坑的总结

总体实验需要先对框架的类和函数有一定的了解和分析。

在这个角度上,踩了一个坑,没有提前发现TablePage的Iinit初始化函数,在从bufferpool获取到内存后,没有用TablePage进行初始化,导致后面读取了未知数据,在查找实验中频繁出错,折腾了好久才发现。