为便于理解先将实验要求进行翻译，水平有限，有不妥之处请多指教。另外声明在先，本文仅仅是实验要求的中文翻译。
介绍
在本项目中，我们将实现一个简单的存储与缓存管理器。文档着重于磁盘和内存的管理。讨论的内容包括：内存（buffer）和页框（frame）大小，buffer和frame存储结构，页（page）格式，page存储结构，文件（file）结构，缓存技术，哈希技术，文件存储结构，以及硬盘空间的接口函数，缓冲模块。
Buffer与Frames
Buffer与Frames大小
Buffer指主存中的空间。CPU只可以访问驻存在主存中的内容。Buffer包含一个frame数组。当一个page要被访问时，page先被加载到内存的buffer中。大多数的商业数据库管理系统为了避免产生额外的碎片，将frame与page的大小设置成一样的。本项目中也采取类似的策略，buffer的默认值将被设置成1024.
Buffer 和 Frame存储结构
Buffer在逻辑上被划分为frame块。
一个frame被描述为如下全局定义的结构，
#define FRAMESIZE 4096
struct bFrame{
char field[FRAMESIZE];
};
frame存放待加载的page，而buffer中保存frame数组。
数组的结构如下：
#define DEFBUFSIZE 1024
bFrame buf[DEFBUFSIZE]; //or the size that the user defined by the input parameter
上述空间将被分配给buffer，缓冲区管理器和文件将通过访问该buffer来访问所需的页面。
Page格式
在本项目中，我们不需要指明page结构的具体细节。唯一有关的信息是page_id和page_size。
File格式
我们推荐使用目录结构的来组织数据库文件。每个文件有一个基址页保存指向每个页面的指针。页面中的每个指针都于页面中顺序存放。这种类型文件中的数据页面（Data pages）不再设指针，使用记录表示。为了访问文件中的下一页，必须查阅基址页(base page)或目录。
之所以选择基于目录的文件格式，是因为它适合查找特定的记录请求页。目录的基址文件可以实现快速访问正确的页面，而不必搜索一长串的页面找到正确的一个。
Buffering技术
我们采用LRU作为实验中唯一的一种替换技术。LRU总是从一个buffer page的LRU队列中剔除最近最少访问的(least-recently-used)页面，缓冲页面LRU队列按最后一次引用的时间顺序。它总是在LRU位置上寻找替换页(victim page)。LRU的最大优势在于：它拥有常数级别的时间复杂性。进一步说，LRU在时间局部性上表现良好，比如通常最近访问的页面有较高的可能性会再被访问。
Hashing 技术
对buffer中的每个frame而言，buffer control block 必须常驻。每个buffer control block，或者说BCB，包含一个page_id，一个frame_id，page_latch，fix_count，以及dirty_bit。page_ids被用于hash函数的key值映射到BCB上。两个hash表必须常驻内存：一个将page_ids映射到frame_ids以及BCB另一个将frame_ids 映射到page_ids上。
我们建议采用简单的静态hash技术。在静态哈希中，buckets（筐子）的数目固定。如果一个框满，剩余的数据项使用一个溢出链连接。针对key值，hash函数将其映射入一个筐子。并且在一个独立bucket中可以采用线性搜索。bucket的数目不会随时间增长变化。
对hash表而言，静态的hash函数具有如下相似形式：
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
我们的项目中，我们只需要在磁盘上存放一个物理文件。所有的数据库数据将会存放在这个单独文件中。该文件将会驻存在工作目录中并命名为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
这些接口函数将会提供一个对文件与访问管理器的接口。为实现相关功能，我们需要构造如下函数。
FixPage(int page_id, int prot)
函数原型为FixPage(Page_id, protection)。
该函数返回一个frame_id。
文件与访问管理器将会传递一个page_id来调用相关page，此处的page_id与记录中的record_id相对应。该函数查看所需page是否已经在buffer中，若存在返回它对应的frame_id。若该页不在内存，该函数选择一个victim page，并且若有需要加载所需page。
FixNewPage()
该函数原型为 FixNewPage()，它返回一个page_id和frame_id。
当产生插入，目录分割或创建对象等操作时，该函数被调用，用来产生一个新的page。
该函数的返回值是与record_id或元数据相对应的page_id。这个函数将会寻找一个空页面，供给文件与访问管理器存放数据。
UnfixPage(int page_id)
该函数原型为UnfixPage(page_id)，它返回一个frame_id。该函数是与FixPage或FixNewPage配合使用。这个函数每次将frame上的fix count减一。 当数量为0时，对page的占用就被解除，若被选中frame可以被移除。page_id可以被转化成frame_id并且它可以被解除占用。当一个页面上的count等于0时，该页面可以被选为victim page。
NumFreeFrames()
NumFreeFrame查看buffer返回空闲可用的buffer page数量。该函数在使用N-路排序中非常有用。该函数的原型是 NumFreeFrames()，返回值为一个整数，范围为 0 -BUFFERSIZE-1(1023).
SelectVictim()
SelectVictim函数选择一个frame进行替换。当一个被选中的页面dirty位被标记，需要将选中页面写回磁盘。
Hash(int page_id)
Hash函数使用page_id作为参数并返回frame id。
RemoveBCB(BCB* ptr, int page_id)
RemoveBCB函数从队列里移除 page_id对应的BCB 。只有在SelectVictim()函数需要替换一个frame时才被调用。
RemoveLRUEle(int frid)
RemoveLRUEle函数从队列里移除LRU 元素。
SetDirty(int frame_id)
SetDirty为 frame_id设置dirty位。dirty位用于指示是否需要写回frame。一个frame若被修改过，则需要被写回。这包括目录页和数据页面。若该位为1需要被写回，若为0不需要写回。
UnsetDirty(int frame_id)
UnsetDirty函数将对应frame_id的dirty_bit设置为0。当调用了setDirty()函数但，实际上该页只是临时改动，不需要被写回，也不想被存储到磁盘，调用UnsetDirty函数。
WriteDirtys()
WriteDirtys 在系统结束前必须被调用。函数的目的是写回buffer中的所有dirty_bit为1的page到磁盘。.
PrintFrame(int frame_id)
PrintFrame函数打印frame内容，这里打印frame_id。
Data Storage Interface Functions
现在的数据文件会保持在 DSManager class中。文件名为data.dbf。
OpenFile(string filename)
任何一个文件需要被读取或写入，OpenFile函数就被调用。函数原型为OpenFile(String filename)，若执行错误返回一个错误码。
CloseFile()
当一个文件要被关闭时调用CloseFile函数。函数原型为 CloseFile() 。函数只能在数据库发生变化或一个程序被关闭时被调用。
ReadPage(int page_id)
在buffer管理器中，ReadPage函数被FixPage调用。函数原型为ReadPage(page_id, bytes)，返回值为它读取的内容。该函数调用fseek()和fread()从文件中读取数据。
WritePage(int frame_id, bFrame frm)
当一个page从buffer中取出时，调用WritePage函数。函数原型为 WritePage(frame_id, frm)返回值为被写入的字节数目。该函数调用fseek()和 fwrite()向文件中写入数据。
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数组中查找set位。这个数组用于记录page使用情况的变化。如果这个page中所有的记录都被删除，该页面即不再被使用。为了了解一个页面是否被重复使用过，该数组所有的use_bit位都需要被检查是否被置为0。fixNewPage先检查数组的use_bit是否被置为0。如果找到1，说明page已经被重用。否则需要分配一个新的page。
GetUse(int page_id)
GetUse函数返回page_id对应的use_bit
Experiment Setup
我们的项目中，我们需要执行一个trace-driven的实验来测试你的实现结果。我们需要根据Zipf分布确定trace的生成。 trace中共有50000个page记录，每条记录数字从0-49999。每条 trace 记录格式如下 “x, ###”，x表示0(read) or 1(write) 而 ### 指示page number. 你需要扫描trace file，打印出所有的内存与硬盘间的I/Os次数。
buffer初始为空。所有的50000个页面首先需要被保存在磁盘上，对应一个directory-based文件data.dbf。
