《高级数据库系统》课程实验.docx

高级数据库系统课程实验Storage and Buffer Manager实验报告指导教师:金培权姓 名:赵杭天学 号： SC电子邮件： 实验日期： 2019年1月1日C:UsersZhao-hangtianOneDrive - M®bu.DC ZZ DC DC DC DC DC DC DC wC ZZ «C Z »C ， «>Z >C «Z «1Z «Z «1Z* Storage and Buffer Manager by ZHT *人 « 1 « « 1 » 人 s I w ala « I « sis ala « 1 * ala via ala ala al* a la w 1 « a 1 » a I * a Is a I * al* a 1 « « 1 > via ml* I > via al* « 1 a * 1 » ala « 1 « a 1 » via « I » ala « 1 * * 1 a « 1 * « 1 « -Y- - y - | | -丫- - j - J _ - - J | | | - J - - - -丫 J J - J _ - j - I J - J - | _ y - | | - - J J - J J | WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：1024BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request：50000010:331004Hits：169565Hit ratio：33.912998%trace consuining time： 5. 855000 seconds请按任意键继续.进程内存(MB) 14邮专用汴14控制台输出信息包含缓冲区大小Buffer frame size、总请求量Request、IO 总发起量10、总命中数Hits、命中率Hit ratio、完成trace总消耗时间trace consuming timeo另外，本实验还通过Visual Studio的诊断工具记录了程序的内 存占用情况。可以看出，本实验编写程序没有出现明显的内存泄漏。下面将更改BUFFSIZE并分别进行测试，最后汇总于表格1中，并结果进行 分析。设置BUFFSIZE=2048进行测试，结果如下图：C:UsersZhao-hangtianOneDrive - M®buffer.-* Storage and Buffer Manager by ZHT *一- «la «I> - 1- -A- -1-A* «A« -A- -A- «A-A» »A» «A» »A» A- -A-«A«-*-A-»A» »A- »A«» 一<-|» - J - - J - - J - - | - T - |- - J - - J - y - - T - j |- - J - -j - - | - - J J - | - - J - - J - - J - - | - T - | J - J - - I - - J - - J -WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：2048BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request：50000010:291581Hits：209569Hit ratio：41. 913799%trace consuming time： 5.301000 seconds请按任意键继续进程内存(MB) 19快照专用字节19设置BUFFSIZE=3072进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - M®buffer.* Storage and Buffer Manager by ZHT * 1 1 o « 1 ml 0 1 1 m 1 1 1 » I 0 - 1 « I - 1 « 1 0 1 0 1 1 I 1 - 1 « 1 1 0 1 - I « 1 1 m 1 0 1 1 o « 1 1 « 1 1 « 1 0 1 « 1 1 m 1 1 - 1 « 1 -( - - - - | J - - - - | - -T I J - - | - -T | - - - - » - | J - | - - J | - - - |1 - - J - | - J | - - - T - - | -WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：3072BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request：50000010:266188Hits：235584Hit ratio：47. 116798%trace consuming time： 5.030000 seconds请按任意键继续.设置BUFFSIZE=4096进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - M®b. 1 1 « 1 X «1 1 X 1 X 1 o 1 X 1 1 1 1 0 1 1 1 » 1 1 1 1 1 «1 1 «X 人人 人 人. 人 人人 人 .人 1 人.- - > j - - - - - - - - - - j - - - - - - - - - - - 1 - - - - - - - - - - - - - - j - - - - - - - - - - - - - - - - - - - - - - j - - -,-* Storage and Buffer Manager by ZHT *«»CWELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：4096BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request:50000010:246942Hits：255440Hit ratio：51.088001%trace consuming time ： 4. 666000 seconds请按任意键继续.设置BUFFSIZE=8192进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - M®buffer.«1 «1 «1 «1 1 «1入.人 .人 -一， 人.人 .人 一， 人 .人一，人人.人人人. .人人入.人 一，入人人人人A- - J * - j j - - j - - j - j J - - J - - j - - j « j J - - J - J - j - - - j - J - - - j - j - j - - j * Storage and Buffer Manager by ZHT *WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：8192BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request:50000010:196319Hits：308746Hit ratio：61. 749199%trace consuming time： 4. 038000 seconds请按任意键继续./进程内存(MB) 46飕专用广 46设置BUFFSIZE=16384进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - M®buffe.- 1 - 1 - 1 - 1 1 - 1 o 1 » 1 1 I 1 « 1 1 0 1 » 1 1 1 1 « 1 - I 0 1 - 1 - 1 1 - 1 » - 1 - 1 » 0 1 1 0 1 1 - 1 » - 1 - 1 » 1 1 1 1 1 - 1 1 -I - - | -| - - J | - I - - | - - J - - J - - J - | - - I - - | - - J - | - 'J - - | - - | I - - j J | - 1 J - - | - J | - »T - J J | -* Storage and Buffer Manager by ZHT *d|c d|cd|c d|cd|c d|c d|c d|c d|c zfcWELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：16384BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request：50000010:141795Hits：369294Hit ratio：73.858803%trace consuming time： 3. 224000 seconds请按任意键继续.进程内存(MB)82姆专用片设置BUFFSIZE=32768进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - M®bu. X* Storage and Buffer Manager by ZHT *人 ala « 1 m 1 w 1 1 1 0 i 1 1 1 1 1 1 1 W 1 X 1 « 1 » 1 » 1 w 1 w 1 1 i I 1 m 1 1 1 i 1 1 0 1 1 w 1 I 1 1 w 1 1 - T J -|- |- 1 T - - - - -T | - - - - J - - J - - - - J - J - - J - - | - - J - » |- J - - | J - J | - - J - - |- | - - Y - - | -| J -|- J | - - J -| -WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：32768BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request：50000010:93589Hits：432375Hit ratio：86. 474998%trace consuming time： 2. 304000 seconds请按任意键继续.,进程内存(MB)快照 专用字节154 -e1540 J0设置BUFFSIZE=65536进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - mail.ustc.edu. X* Storage and Buffer Manager by ZHT *-1 - 1 1 1 1 ， .人 1 - ， 1 1 A - 1 - 1 1 1 1 - 1 1 1 1 1 1 1 - 1 1 - 1 1 1 1 - 1 1 1 1 1 1 1 1 1 1 1 (-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-(-| -(-(-(-(-(-(-(-(-(-(-(-(-WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：65536BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request：50000010:86906Hits：452977Hit ratio：90.595398%trace consuming time ： 1.910000 seconds请按任意键继续.0/进程内存(MB)297，触专用汴 297设置BUFFSIZE =131072进行测试，结果如下图:C:UsersZhao-hangtianOneDrive - . 1 1 « 1 人 « 1 1 人 « 1 » 1 « 人 人 人 人 1 A 1 人 人 « 1« 1 人 人 I 1 I «1 I 人 1« 1 w w 1 人 工I I J - J - - I I , I I J - - I - - J I " I - I I I - I - J I I I I I I - - I - I I 丁 I I I J I - I - I I I I Storage and Buffer Manager by ZHT *1 » ««L mmo«a a o oaamo*L ao(* aL *1 , , 丫 J , , , , j j - , , , , , 丫 , , 丫 J , 丫- J WELCOME!Open data, dbf successfully!Open data-5w-50w-zipf. txt successfully!Buffer frame size：131072BUFFER 10 PERFORMANCE TESTING!BUFFER 10 TEST OK!Request:50000010:86906Hits：452977Hit ratio：90.595398%trace consuming time： 1.882000 seconds需按任意键继续./进程内存(MB)5800快照专用字节580为直观对比，将上述数据整理于下表中：表 1 不同 BUFFSIZE 的 buffer 性能表现(Requset=500,000)BUFFSIZE10HitsHit ratiotime/smemory/MB102433100416956533.91%5.85514204829158120956941.91%5.30119307226618823558447.12%5.0323409624694225544051.09%4.66628819219631930874661.75%4.038461638414175936929473.86%3.22482327689358943237586.48%2.304154655368690645297790.60%1.9102971310728690645297790.60%1.8825803、分析与结论：1、观察BUFFSIZE与10、Hits的关系可以看出，随着缓存页面总数 BUFFSIZE的增大，缺页现象逐渐减少，发生磁盘10的数量稳定减少、命中数 Hits稳定增加，IO、Hits两者变化趋势（方向、斜率）是几乎是相反的。2、随着BUFFSIZE的增大，IO数量将下降到一个稳定值，命中数、命中 率页上升到了一个稳定值，即BUFFSIZE继续增大将不会继改善IO性能（命 中率）。造成这点的原因分析如下：首先，是缓存区的大小已经超过了数据库本身，在将数据库完全读入内 存之后、释放LRUCache将脏数据写回磁盘之前，程序将不会因trace产生任何 磁盘10操作；如前所述，这是因为初始化的缓存器是不含任何缓存页的，每个磁盘页 第一次读入缓存必将产生一次IO;除此之外，在程序即将退出，释放 LRUCache时，必须将脏数据写回磁盘，这也必然产生磁盘10操作。这决定了 10总数绝不可能降至0。3、从图表中我们可以发现一个有趣的现象，即IO总数下降停留在了 86906o固定的86906次磁盘IO是由trace中所有的磁盘号（trace的page_id从 0到49,999,共发起500,000次请求，但是这500,000次请求并未涵盖page_id 从0到49,999的所有page）的第一次读写请求，与写请求之后脏数据写回磁盘 所产生的。设trace中出现过的所有的不同的读请求page_id数为R、trace中出 现过的所有的不同的写请求pagjid数为W,则有R + 2xW = 869064、从命中Hits最终停留在452977次，我们也可以看出，足够大 LRUCache将数据库全部读入缓存后，所有请求全部在内存中实现命中。可以 推出trace请求的不同的page_id数P = 50 = 47023,即trace共出现了 47023个 不同的page_id。5、进一步地，由R + W = 47023和R+2xW = 86906,我们可以推出：trace中出现的不同的读请求page_id数R = 7140trace中出现的不同的写请求page_id数W = 398836、观察10和Hits的值可以发现，在所有的情况下，10和Hit的总数都是 超过trace发起的请求数500,000的。原因是：当LRUCache进行1次缺页写操作时，必然带来。次Hit和2次10, 一次 是缺页置换，另一次是脏数据写回磁盘；LRUCache进行1次缺页读操作时， 必然带来0次Hit和1次IOo此外，LRUCache在对同一 page_id进行n次不 缺页的读操作时，产生n次Hit和。次IO； LRUCache在对同一 page_id进行n 不缺页的写操作时，产生n-1次Hit和1次IO。综合来看，每1次的读写请求会产生三者情况：1次10和0次Hit、0次 10和1次Hit、2次10和0次Hit,所以10和Hit的总数必然会超过trace发起 的请求数。7、观察BUFFSIZE、memory、time三者的关系，可以看出随着BUFFSIZE 的增大，内存占用memory快速上升，而执行trace的时间time逐渐减少。这本 质上是采取了 “空间换时间”策略。可以看出，分配更大的BUFFSIZE, time 会逐渐减少，但减少的速度逐渐放缓，这也符合了 “边际效用递减法则”。六、总结本次实验从金老师布置的第二周便开始着手准备，参考实验描述文档 Storage and Buffer Manager Lab Description和上课讲义，结合自己的想法， 回忆着数据结构、数据库和算法方面的知识，在两个星期里用C+一步步的实 现，但半期之后课业逐渐繁重，最近才开始撰写报告。期间也向助教老师进行 过请教，在此感谢助教老师和金老师提供的指导。本次实验最具挑战性的地方应该是如何把握数据结构的组织，必须清晰地 认识buffer管理器的功能、原理和定位，以及灵活运用哈希表和双向链表数据 结构，熟悉利用C+STL可以起到事半功倍的效果。通过这次实验，我对于数据库buffer管理器的工作原理有了更深的认识。 本实验使用C+实现，期间使用了大量的指针操作、流操作、STLO本次实 验，使我对C+指针有了更深刻的认识、动手实践了二进制字节流磁盘保存与 在内存中还原其数据结构的操作、动手实现了 “哈希+双向链表”这一经典数据 结构、了解熟悉了 unordered_maps stack、vector等C+标准模板，收获颇丰。六、源码本实验源码（sin工程包，release编译）附在ftp服务器提交的压缩包中;亦可1.16号后访问获取；一、实验背景为了了解数据库buffer管理器的工作原理，对数据库底层结构有更进一步 的了解，我们将实现一个简单的存储和缓存管理器。该实验涉及存储和缓存管 理器的缓存技术、散列技术、文件存储结构、磁盘空间和缓存模块的接口等功 能。二、实验环境硬件平台：OMEN HP Laptop 15-dc 16.0GB RAM开发环境：操作系统：Windows 10 Pro 64bit开发语言：C+ 14集成开发环境：Visual Studio 2017, 三、实验内容1、实现基于对磁盘进行字节流操作的数据库读写函数；2、实现基于哈希+双向链表的缓存管理器器设计；（主要）3、使用trace文件验证系统；4、更改缓存器大小buffersize对比分析实验结果；三、设计思路与实现概要1、实现基于对磁盘进行字节流操作的数据库读写函数为了更好地使用trace文件验证系统，首先建立一个真实的数据库，这就需 要首先实现对数据库文件进行读写的函数。根据实验文档所描述的，建立的数据库名称设为，若不存在则新建，存在 则覆盖。参考上课讲义与教材，设计的记录类型如下：指向模式的指针长度 时间戳长度 时间戳nameaddressgenderbirthdate300304316char char char char01244每条记录长度为316字节，每个磁盘页大小（pagesize）设定为4KB, 4096-316 = 12304,每个磁盘页（这里也称磁盘块）可放入12条记录，在磁盘页首部设计块号（4byte）、块时间戳（4byte）、块偏移量表（索 引，24byte）,磁盘页尾部填充272个字节。正好实现316 * 12 + 8 + 12 * 2 + 272 = 4096B = 4KB对齐。文件操作基于C+标准库fstream实现，主要部分如下:for （int j = 0; j num_blocks; j+）/写入num blocks个块，数据记录方法：固定格式定长记录/写入块首部 block_num = j;int writeCnt = fwrite (&block_numz sizeof (block_num), 1, fstream_w); / 数据块号 writeCnt = fwrite (&btimestampz sizeof (btimestamp) r lz fstream_w); / 时间戳 writeCnt = fwrite (&offsetz sizeof (offset), 1, fstream_w); / 块内偏移表 /写入记录一char * p_schema = NULL;unsigned int timestamp = j; unsigned int length = 316;namePtr32; adrressPtr256; genderPtr4;birthdayPtr12;for (int i = 0； i < FRAMESIZE / RECORDSIZE； i+) / 2048/316=12writeCnt = fwrite(&fstream_wz sizeof(fstream_w)z 1, fstream_w);writeCnt = fwrite(&lengthr sizeof(length), 1, fstream_w);writeCnt = fwrite(&timestampz sizeof(timestamp)z 1, fstream_w);writeCnt = fwrite(&namePtrr sizeof(namePtr), 1, fstream w);writeCnt = fwrite(sadrressPtr, sizeof(adrressPtr), 1, fstream w);writeCnt = fwrite(&genderPtrz sizeof(genderPtr), 1, fstream w);writeCnt = fwrite(&birthdayPtrz sizeof(birthdayPtr), 1, fstream w); ;:char null 272; /填充字节使得4KB对齐writeCnt = fwrite(&nullz sizeof(null)r lz fstream w);)图1.1数据库文件建立函数根据trace文件要求，设置num_blocks=50000,即向磁盘连续写入50000 个页，使用目录式堆文件组织，建立索引。根据块号返回值确定数据库的正确性：void NoIndexQuery(int find_block_num) ；/查询指定块的块号FILE * fstream_r;:fstream_r = fopen(ndata.dbfn r nrbn);unsigned int blocknum = 0;cout « nquery target: “ « find_block_num « endl;int offset = find_b1ock_nurn * FRAMESIZE;fseek(fstream_r, offset, SEEK_SET);int readCnt = fread(&blocknumz sizeof(blocknum)r lr fstream_r); cout « " query result: " « blocknum « endl;fclose(fstream_r); 一图L2数据库文件访问测试数据库只需建立一次，得到数据库文件后可以将CreateBlockWRTest (int num_blocks)函数的调用注释掉，并备份测试数据库。2、缓存管理器器设计2.1 确定缓存区的结构根据业界标准，缓存页的大小(framesize) 一般等于磁盘页大小(pagesize),两者均设为4KB。由上小节讨论，磁盘(disk)数据库文件有 50000个磁盘页(page),缓存区(buffer)中应存在多个缓存页(frame),缓 存区中frame的数量用BUFFSIZE定义，初始设定为1024。在后面的实验中可 以看到随缓存区大小(BUFFSIZE)的增大带来的变化。2.2 缓存控制块设计(Buffer Control Blocks, BCB)一般地，1个BCB维护着1个磁盘页在缓存(内存)中的信息，包括磁盘 页号page_id、此块号对应的缓存页号frame_id、reference位、用户占用计数 count、时间戳time、脏位dirty, BCB结构体如图2.2。在主流的实现方式中， BCB作为数组或者链表的结点，组成便于管理的数据结构，提供快速的查找、 更新、置换等功能。struct BCBint page_idf frame_idA refr count, time, dirty;BCB * _prev;BCB * _next;BCB() : next(NULL), prev(NULL) BCB(int page_idf int frame_id) : page_id(page_id)r frame_id(frame_id)r :count(0)z time(0)z dirty(0) BCB(); ：/黜沐节点void disconnect () | . |：/ next方向插入节点void Insert (BCB * node) . )；图2.2 BCB结构设计2.3 使用哈希表+双向链表实现LRUCache在大多数场景下，page数远大于BUFFSIZE,所以缓存器必须有一个调度 机制，用以实现内存中缓存页frame的置换、淘汰，这里使用了 LRU (Least Recent Used)算法。关于LRU的实现主要有3种方式：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插 入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的 时间戳置为。并插入到数组中。每次访问数组中的数据项的时候，将被访问的 数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。这 种实现思路比较简单，但缺点也很明显：需要不停地维护数据项的访问时间 戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n)。利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头 部；每次缓存命中(即数据被访问)，则将数据移到链表头部；那么当链表满 的时候，就将链表尾部的数据丢弃。这种方法效率相对第一种稍高，但链表在 定位数据的时候时间复杂度为O(n)。基于哈希表和双向链表。当需要插入新的数据项的时候(哈希查询)， 如果新数据项在链表中存在(命中)，则把该节点移到链表头部，如果不存 在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删 除(哈希删除)即可。这样一来在链表尾部的节点就是最近最久未访问的数据 项。基本所有操作可以实现时间复杂度0(1)。本实验基于C+ 14 STL容器，使用方法3实现LRUCache：std:list,相当于双向链表。spliceQ, push_front(), pop_back()的复杂度为O(l)ostd:unordered_map,相当于哈希表。find。，insert。，erase()的复杂度为0(1) oHASH TABLELINKED LIST图2.3哈希表+双向链表实现LRU CacheLRUCache类具有哈希表+双向链表数据结构。向BCB添加前向（prev）、后向（next）指针以及断开（disconnect）、插 入（insert）函数，使其组成双向链表。磁盘页号 page_id 作为哈希表的 key, frame_id, ref, count, time, dirty 作为哈 希表的valueo其中最主要的value是缓存页号frame_ido可以以时间复杂度 0实现page_id到framejd的映射以及LRU置换。LRUCache的private成员主要包含：（如图2.4）STL容器如哈希表hashmap>栈frame_ids；DiskSpaceManager类实例化对象，用于实现对磁盘文件的读写；整型数组f2P