為便于理解先將實(shí)驗(yàn)要求進(jìn)行翻譯坡慌，水平有限，有不妥之處請(qǐng)多指教挚赊。另外聲明在先诡壁，本文僅僅是實(shí)驗(yàn)要求的中文翻譯。
介紹
在本項(xiàng)目中荠割，我們將實(shí)現(xiàn)一個(gè)簡(jiǎn)單的存儲(chǔ)與緩存管理器妹卿。文檔著重于磁盤(pán)和內(nèi)存的管理。討論的內(nèi)容包括：內(nèi)存（buffer）和頁(yè)框（frame）大小蔑鹦，buffer和frame存儲(chǔ)結(jié)構(gòu)夺克，頁(yè)（page）格式，page存儲(chǔ)結(jié)構(gòu)嚎朽，文件（file）結(jié)構(gòu)铺纽，緩存技術(shù)，哈希技術(shù)哟忍，文件存儲(chǔ)結(jié)構(gòu)狡门，以及硬盤(pán)空間的接口函數(shù)，緩沖模塊锅很。
Buffer與Frames
Buffer與Frames大小
Buffer指主存中的空間其馏。CPU只可以訪問(wèn)駐存在主存中的內(nèi)容。Buffer包含一個(gè)frame數(shù)組爆安。當(dāng)一個(gè)page要被訪問(wèn)時(shí)叛复，page先被加載到內(nèi)存的buffer中。大多數(shù)的商業(yè)數(shù)據(jù)庫(kù)管理系統(tǒng)為了避免產(chǎn)生額外的碎片，將frame與page的大小設(shè)置成一樣的褐奥。本項(xiàng)目中也采取類似的策略咖耘，buffer的默認(rèn)值將被設(shè)置成1024.
Buffer 和 Frame存儲(chǔ)結(jié)構(gòu)
Buffer在邏輯上被劃分為frame塊。
一個(gè)frame被描述為如下全局定義的結(jié)構(gòu)抖僵，
#define FRAMESIZE 4096
struct bFrame{
char field[FRAMESIZE];
};
frame存放待加載的page鲤看，而buffer中保存frame數(shù)組。
數(shù)組的結(jié)構(gòu)如下：
#define DEFBUFSIZE 1024
bFrame buf[DEFBUFSIZE]; //or the size that the user defined by the input parameter
上述空間將被分配給buffer耍群，緩沖區(qū)管理器和文件將通過(guò)訪問(wèn)該buffer來(lái)訪問(wèn)所需的頁(yè)面义桂。
Page格式
在本項(xiàng)目中，我們不需要指明page結(jié)構(gòu)的具體細(xì)節(jié)蹈垢。唯一有關(guān)的信息是page_id和page_size慷吊。
File格式
我們推薦使用目錄結(jié)構(gòu)的來(lái)組織數(shù)據(jù)庫(kù)文件。每個(gè)文件有一個(gè)基址頁(yè)保存指向每個(gè)頁(yè)面的指針曹抬。頁(yè)面中的每個(gè)指針都于頁(yè)面中順序存放溉瓶。這種類型文件中的數(shù)據(jù)頁(yè)面（Data pages）不再設(shè)指針，使用記錄表示谤民。為了訪問(wèn)文件中的下一頁(yè)堰酿，必須查閱基址頁(yè)(base page)或目錄。
之所以選擇基于目錄的文件格式张足，是因?yàn)樗m合查找特定的記錄請(qǐng)求頁(yè)触创。目錄的基址文件可以實(shí)現(xiàn)快速訪問(wèn)正確的頁(yè)面，而不必搜索一長(zhǎng)串的頁(yè)面找到正確的一個(gè)为牍。
Buffering技術(shù)
我們采用LRU作為實(shí)驗(yàn)中唯一的一種替換技術(shù)哼绑。LRU總是從一個(gè)buffer page的LRU隊(duì)列中剔除最近最少訪問(wèn)的(least-recently-used)頁(yè)面，緩沖頁(yè)面LRU隊(duì)列按最后一次引用的時(shí)間順序碉咆。它總是在LRU位置上尋找替換頁(yè)(victim page)抖韩。LRU的最大優(yōu)勢(shì)在于：它擁有常數(shù)級(jí)別的時(shí)間復(fù)雜性。進(jìn)一步說(shuō)疫铜，LRU在時(shí)間局部性上表現(xiàn)良好茂浮，比如通常最近訪問(wèn)的頁(yè)面有較高的可能性會(huì)再被訪問(wèn)。
Hashing 技術(shù)
對(duì)buffer中的每個(gè)frame而言壳咕，buffer control block 必須常駐励稳。每個(gè)buffer control block，或者說(shuō)BCB囱井，包含一個(gè)page_id驹尼，一個(gè)frame_id，page_latch庞呕，fix_count新翎，以及dirty_bit程帕。page_ids被用于hash函數(shù)的key值映射到BCB上。兩個(gè)hash表必須常駐內(nèi)存：一個(gè)將page_ids映射到frame_ids以及BCB另一個(gè)將frame_ids 映射到page_ids上地啰。
我們建議采用簡(jiǎn)單的靜態(tài)hash技術(shù)愁拭。在靜態(tài)哈希中，buckets（筐子）的數(shù)目固定亏吝。如果一個(gè)框滿岭埠，剩余的數(shù)據(jù)項(xiàng)使用一個(gè)溢出鏈連接。針對(duì)key值蔚鸥，hash函數(shù)將其映射入一個(gè)筐子惜论。并且在一個(gè)獨(dú)立bucket中可以采用線性搜索。bucket的數(shù)目不會(huì)隨時(shí)間增長(zhǎng)變化止喷。
對(duì)hash表而言馆类，靜態(tài)的hash函數(shù)具有如下相似形式：
H(k) = (page_id)%buffer_size
BCB（Buffer Control Blocks）通常包含page_id, frame_id, latch, count, dirty_bit。
BCB中page_id的hash表具有如下類似形式：BCB hTable[BufferSize]弹谁。
page_id中的frame_id 的hash表具有如下類似形式： int hTable[BufferSize]乾巧。
struct BCB
{ BCB();
int page_id;
int frame_id;
int latch;
int count;
int dirty;
BCB * next;
};
File Storage
我們的項(xiàng)目中，我們只需要在磁盤(pán)上存放一個(gè)物理文件预愤。所有的數(shù)據(jù)庫(kù)數(shù)據(jù)將會(huì)存放在這個(gè)單獨(dú)文件中沟于。該文件將會(huì)駐存在工作目錄中并命名為data.dbf。該文件必須始終能被找到植康，即使是空文件社裆。
Class Design
Data Storage Manager
class DSMgr
{
public:
DSMgr();
int OpenFile(string filename);
int CloseFile();
bFrame ReadPage(int page_id);
int WritePage(int frame_id, bFrame frm);
int Seek(int offset, int pos);
FILE * GetFile();
void IncNumPages();
int GetNumPages();
void SetUse(int index, int use_bit);
int GetUse(int index);
private:
FILE *currFile;
int numPages;
int pages[MAXPAGES];
};
Buffer Manager
class BMgr
{
public:
BMgr();
// Interface functions
int FixPage(int page_id, int prot);
void NewPage FixNewPage();
int UnfixPage(int page_id);
int NumFreeFrames();
// Internal Functions
int SelectVictim();
int Hash(int page_id);
void RemoveBCB(BCB * ptr, int page_id);
void RemoveLRUEle(int frid);
void SetDirty(int frame_id);
void UnsetDirty(int frame_id);
void WriteDirtys();
PrintFrame(int frame_id);
private:
// Hash Table
int ftop[DEFBUFSIZE];
BCB* ptof[DEFBUFSIZE];
};
Buffer Interface Functions
這些接口函數(shù)將會(huì)提供一個(gè)對(duì)文件與訪問(wèn)管理器的接口。為實(shí)現(xiàn)相關(guān)功能向图，我們需要構(gòu)造如下函數(shù)。
FixPage(int page_id, int prot)
函數(shù)原型為FixPage(Page_id, protection)标沪。
該函數(shù)返回一個(gè)frame_id榄攀。
文件與訪問(wèn)管理器將會(huì)傳遞一個(gè)page_id來(lái)調(diào)用相關(guān)page，此處的page_id與記錄中的record_id相對(duì)應(yīng)金句。該函數(shù)查看所需page是否已經(jīng)在buffer中檩赢，若存在返回它對(duì)應(yīng)的frame_id。若該頁(yè)不在內(nèi)存违寞，該函數(shù)選擇一個(gè)victim page贞瞒，并且若有需要加載所需page。
FixNewPage()
該函數(shù)原型為 FixNewPage()趁曼，它返回一個(gè)page_id和frame_id军浆。
當(dāng)產(chǎn)生插入，目錄分割或創(chuàng)建對(duì)象等操作時(shí)挡闰，該函數(shù)被調(diào)用乒融，用來(lái)產(chǎn)生一個(gè)新的page掰盘。
該函數(shù)的返回值是與record_id或元數(shù)據(jù)相對(duì)應(yīng)的page_id。這個(gè)函數(shù)將會(huì)尋找一個(gè)空頁(yè)面赞季，供給文件與訪問(wèn)管理器存放數(shù)據(jù)愧捕。
UnfixPage(int page_id)
該函數(shù)原型為UnfixPage(page_id)，它返回一個(gè)frame_id申钩。該函數(shù)是與FixPage或FixNewPage配合使用次绘。這個(gè)函數(shù)每次將frame上的fix count減一。 當(dāng)數(shù)量為0時(shí)撒遣，對(duì)page的占用就被解除邮偎，若被選中frame可以被移除。page_id可以被轉(zhuǎn)化成frame_id并且它可以被解除占用愉舔。當(dāng)一個(gè)頁(yè)面上的count等于0時(shí)钢猛，該頁(yè)面可以被選為victim page。
NumFreeFrames()
NumFreeFrame查看buffer返回空閑可用的buffer page數(shù)量轩缤。該函數(shù)在使用N-路排序中非常有用命迈。該函數(shù)的原型是 NumFreeFrames()，返回值為一個(gè)整數(shù)火的，范圍為 0 -BUFFERSIZE-1(1023).
SelectVictim()
SelectVictim函數(shù)選擇一個(gè)frame進(jìn)行替換壶愤。當(dāng)一個(gè)被選中的頁(yè)面dirty位被標(biāo)記，需要將選中頁(yè)面寫(xiě)回磁盤(pán)馏鹤。
Hash(int page_id)
Hash函數(shù)使用page_id作為參數(shù)并返回frame id征椒。
RemoveBCB(BCB* ptr, int page_id)
RemoveBCB函數(shù)從隊(duì)列里移除 page_id對(duì)應(yīng)的BCB 。只有在SelectVictim()函數(shù)需要替換一個(gè)frame時(shí)才被調(diào)用湃累。
RemoveLRUEle(int frid)
RemoveLRUEle函數(shù)從隊(duì)列里移除LRU 元素勃救。
SetDirty(int frame_id)
SetDirty為 frame_id設(shè)置dirty位。dirty位用于指示是否需要寫(xiě)回frame治力。一個(gè)frame若被修改過(guò)蒙秒，則需要被寫(xiě)回。這包括目錄頁(yè)和數(shù)據(jù)頁(yè)面宵统。若該位為1需要被寫(xiě)回晕讲，若為0不需要寫(xiě)回。
UnsetDirty(int frame_id)
UnsetDirty函數(shù)將對(duì)應(yīng)frame_id的dirty_bit設(shè)置為0马澈。當(dāng)調(diào)用了setDirty()函數(shù)但瓢省，實(shí)際上該頁(yè)只是臨時(shí)改動(dòng)，不需要被寫(xiě)回痊班，也不想被存儲(chǔ)到磁盤(pán)勤婚，調(diào)用UnsetDirty函數(shù)。
WriteDirtys()
WriteDirtys 在系統(tǒng)結(jié)束前必須被調(diào)用涤伐。函數(shù)的目的是寫(xiě)回buffer中的所有dirty_bit為1的page到磁盤(pán)蛔六。.
PrintFrame(int frame_id)
PrintFrame函數(shù)打印frame內(nèi)容荆永，這里打印frame_id。
Data Storage Interface Functions
現(xiàn)在的數(shù)據(jù)文件會(huì)保持在 DSManager class中国章。文件名為data.dbf具钥。
OpenFile(string filename)
任何一個(gè)文件需要被讀取或?qū)懭耄琌penFile函數(shù)就被調(diào)用液兽。函數(shù)原型為OpenFile(String filename)骂删，若執(zhí)行錯(cuò)誤返回一個(gè)錯(cuò)誤碼。
CloseFile()
當(dāng)一個(gè)文件要被關(guān)閉時(shí)調(diào)用CloseFile函數(shù)四啰。函數(shù)原型為 CloseFile() 宁玫。函數(shù)只能在數(shù)據(jù)庫(kù)發(fā)生變化或一個(gè)程序被關(guān)閉時(shí)被調(diào)用。
ReadPage(int page_id)
在buffer管理器中柑晒，ReadPage函數(shù)被FixPage調(diào)用。函數(shù)原型為ReadPage(page_id, bytes)匙赞，返回值為它讀取的內(nèi)容佛掖。該函數(shù)調(diào)用fseek()和fread()從文件中讀取數(shù)據(jù)。
WritePage(int frame_id, bFrame frm)
當(dāng)一個(gè)page從buffer中取出時(shí)芥被，調(diào)用WritePage函數(shù)。函數(shù)原型為 WritePage(frame_id, frm)返回值為被寫(xiě)入的字節(jié)數(shù)目。該函數(shù)調(diào)用fseek()和 fwrite()向文件中寫(xiě)入數(shù)據(jù)。
Seek(int offset, int pos)
Seek function moves the file pointer.
GetFile()
GetFile function returns the current file.
IncNumPages()
IncNumPages function increments the page counter.
GetNumPages()
GetNumPages function returns the page counter.
SetUse(int page_id, int use_bit)
SetUse在page數(shù)組中查找set位芳室。這個(gè)數(shù)組用于記錄page使用情況的變化。如果這個(gè)page中所有的記錄都被刪除芽死，該頁(yè)面即不再被使用。為了了解一個(gè)頁(yè)面是否被重復(fù)使用過(guò)，該數(shù)組所有的use_bit位都需要被檢查是否被置為0。fixNewPage先檢查數(shù)組的use_bit是否被置為0奴拦。如果找到1瓷产，說(shuō)明page已經(jīng)被重用株旷。否則需要分配一個(gè)新的page晾剖。
GetUse(int page_id)
GetUse函數(shù)返回page_id對(duì)應(yīng)的use_bit
Experiment Setup
我們的項(xiàng)目中，我們需要執(zhí)行一個(gè)trace-driven的實(shí)驗(yàn)來(lái)測(cè)試你的實(shí)現(xiàn)結(jié)果。我們需要根據(jù)Zipf分布確定trace的生成。 trace中共有50000個(gè)page記錄，每條記錄數(shù)字從0-49999浓若。每條 trace 記錄格式如下 “x, ###”，x表示0(read) or 1(write) 而 ### 指示page number. 你需要掃描trace file，打印出所有的內(nèi)存與硬盤(pán)間的I/Os次數(shù)。
buffer初始為空。所有的50000個(gè)頁(yè)面首先需要被保存在磁盤(pán)上敷燎，對(duì)應(yīng)一個(gè)directory-based文件data.dbf饭豹。
