Flash-DBSim[SuJXCY09]是由中国科学与技术大学知识与数据工程实验室开发的闪存模拟器，它为各种算法性能验证提供了仿真环境，可以模拟闪存技术研究中出现的各种实验环境。该模拟器可以根据上层应用的需要模拟出不同特性的固态盘，如闪存的读写代价不一致和写前擦除等特性。Flash-DBSim使用的程序设计语言为c++，开发工具为visualstudio2008。很多已有的研究（比如缓冲区替换算法CCF-LRU和AD-LRU）都采用了该模拟器进行算法性能的比较。
Flash-DBSim具有如下特点：
闪存存储系统包括两个关键组件，即闪存技术设备模块MTD和闪存转换层FTL。MTD(MemoryTechnologyDriver)提供了对闪存的读、写和擦除操作的函数，它直接控制物理闪存芯片。FTL（FlashTranslationLayer）是架构在MTD层之上的，用来实现地址翻译、空间分配和垃圾回收等操作，从而把一个闪存设备模拟成一个块设备，使得文件系统和用户应用可以像访问磁盘一样访问闪存设备。
图[Flash-DBsim-two-ways]显示了实现一个闪存存储系统的两种不同方式。第一种方式是，MTD和FTL被封装在闪存设备（比如固态盘）中，如图[Flash-DBsim-two-ways](a)所示。第二种方式是，MTD和FTL在闪存设备上面的软件系统中实现，如图[Flash-DBsim-two-ways](b)所示。Flash-DBSim采用了第一种实现方式，即封装在一个闪存设备中，只不过在Flash-DBSim中，这个闪存设备并非真实的设备，而是一个虚拟的设备。
图[Flash-DBsim-two-ways]闪存存储系统的两种实现方式
图[Flash-DBsim-architecture]给出了Flash-DBSim的体系架构，包括以下几个组件：
公共访问接口：该组件是开放给所有用户的，它对用户隐藏了所有底层细节。
图[Flash-DBsim-architecture]Flash-DBSim的体系架构
Flash-DBSim官方网站提供了两个不同版本的Flash-DBSim下载内容：
Flash-DBSim使用的程序设计语言为c++，开发工具为visualstudio2008，因此，读者对压缩文件flash-dbsim-source-1.6.zip进行解压后，可以得到名为“flash-dbsim-source-1.6”的文件夹，该文件夹下面包含一个解决方案文件和两个工程文件夹：
这部分内容首先简单介绍FlashDBSimDll_Sample工程中各个文件的作用，然后介绍如何设置模拟器的参数，接下来给出了一个实例来演示如何测试LRU算法的性能，最后，简单介绍如何测试自己的缓冲区替换算法性能。
从Flash-DBSim官方网站下载得到原始压缩文件“flash-dbsim-source-1.6.zip”以后，解压缩得到名为“flash-dbsim-source-1.6”的文件夹，该文件夹下面包含一个解决方案文件FlashDBSimDll.sln和两个工程文件夹。
在FlashDBSimDll_Sample工程下面，包含4个头文件、3个C++源文件和2个测试数据集文件：
打开工程FlashDBSimDll_Sample下的main.cpp文件，可以直接运行程序。下面介绍各个文件的作用：
Flash-DBSim是一种高效的、可重用和可配置的闪存存储系统仿真平台，可以根据上层应用的需要模拟出不同的特性的固态盘，从而可以方便地为上层应用提供仿真测试环境。Flash-DBSim闪存模拟器通常可以采用下面表[Flash-DBSim-parameters]中的典型参数配置：
表[Flash-DBSim-parameters].NAND闪存的特性参数
Flash-DBSim中的闪存基本参数设置是在FlashDBSimDll_Sample工程下面的main.cpp文件中完成的，相应的代码如下：
vfdInfo.pageCountPerBlock=64;//设置每个块中包含的页的数量
vfdInfo.pageSize.size1=2048;//设置页的数据区域的大小
vfdInfo.pageSize.size2=0;//设置页的带外数据区域的大小
vfdInfo.eraseLimitation=100000;//设置闪存的每个块的擦除次数上限
vfdInfo.readTime.randomTime=25;//设置随机读操作延迟为25微秒
vfdInfo.readTime.serialTime=0;//设置顺序读操作延迟为0微秒
vfdInfo.programTime=200;//设置写操作延迟为200微秒
vfdInfo.eraseTime=1500;//设置擦除操作延迟为1500微秒
这些闪存特性参数可以根据具体的实验要求而有所不同，可以在main.cpp文件中进行修改。需要指出的是，如果实验中需要修改缓冲区的大小，可以在BufferAlgorithm.h文件中修改变量DEFBUFSIZE的值，该值默认为1536，即缓冲区可以容纳1536个页，每个页大小为2048字节，因此，缓冲区大小为3MB。。
FlashDBSimDll_Sample工程提供了一个测试LRU(LeastRecentlyUsed)算法性能实验的例子。为了更好地设计实现自己的缓冲区替换算法，读者应该首先了解LRU算法性能测试的基本步骤、所使用的数据结构和算法成员函数。
在FlashDBSimDll_Sample工程中，通过main.cpp来调用各种缓冲区替换算法，测试任何缓冲区替换算法（包括LRU算法和自己设计的算法）的性能时，都需要严格遵循以下5个步骤：
在Flash-DBSim自带的实例工程FlashDBSimDll_Sample中，包含一个头文件LRU.h，这个头文件里定义了两个结构体LRUBCB和LRUElement，以及一个数组ftop，它们都是为LRU算法服务的。如图[Flash-DBSim-LRU]所示，LRU算法使用的数据结构包含了一个LRU链表、一个哈希表(ptop)和一个数组(ftop)，具体作用如下：
当需要读取一个逻辑页时，需要判断该页是否在缓冲区中，方法很简单，只需要根据页号page_id得到哈希值，然后在哈希表ptop找到对应的哈希桶，每个哈希桶都存储了一个链表，如果该链表中不存在与page_id对应的元素，则说明该页不在缓冲区中。如果链表中存在一个与page_id对应的元素，则读取出该元素的frame_id属性的值，到相应的缓冲区单元中读取数据页。
当需要把一个页号为page_id的逻辑页写入缓冲区的帧号为frame_id的某个帧时，首先，修改数组内容，把数组元素ftop[frame_id]的内容设置为page_id，然后，需要根据页号page_id得到哈希值，在哈希表ptop找到对应的哈希桶，每个哈希桶都存储了一个链表，为page_id和frame_id创建一个新的元素加入到链表中。
当需要把一个逻辑页驱逐出缓冲区时，只需要根据页号page_id得到哈希值，然后在哈希表ptop找到对应的哈希桶，每个哈希桶都存储了一个链表，在链表中找到与page_id对应的元素，读取frame_id的值，然后，把内存中帧号为frame_id的缓冲区单元的内容清空。
图[Flash-DBSim-LRU]Flash-DBSim中LRU算法使用的数据结构
下面分别介绍LRU算法的成员函数及其作用。
Public成员函数：
Public:LRU()//构造函数，初始化数据
~LRU()//析构函数，释放资源
voidInit()//初始化，在LRU算法性能测试的基本步骤的第2步与第3步之间调用
intFixPage(intpage_id)//安插一个数据页
NewPageFixNewPage(LBAlba)//安插一个新的数据页
intUnFixPage(intpage_id)//基本不会用到
voidReadFrame(intframe_id,char*buffer)//读一帧数据，用不到
voidWriteFrame(intframe_id,constchar*buffer)//写一帧数据，用不到
intWriteDirty(void)//将内存中的脏页写回闪存
doubleHitRatio(void)//返回命中率
voidRWInfo()//返回读写统计信息
intIsLBAValid(LBAlba)//判断LBA是否有效
intLBAToPID(LBAlba)//通过LBA获取PID
Private成员函数：
inthash(intpage_id)//哈希函数
LRUBCB*PageToLRUBCB(intpage_id)//通过page_id获取块数据
voidRemoveLRUBCB(LRUBCB*pb)//移除块数据
voidInsertLRUEle(intframe_id)//在链表中插入元素
voidRemoveLRUEle(intframe_id)//移除链表元素
voidAdjustLRUList(intframe_id)//调整链表元素（缓冲区命中以后调整命中页在链表中的位置）
voidSetDirty(intframe_id)//设置frame_id的脏标识
intSelectVictim()//选择替换页，缓存替换算法的核心函数
voidRegistEntry(LBAlba,PIDpage_id)//注册一页，用不到
Private成员变量：
intftop[DEFBUFSIZE]//数组
LRUBC*ptop[DEFBUFSIZE]//哈希表
bFramebuf[DEFBUFSIZE]//存放帧数据，用不到
Map
LRUElement*lru//链表的表尾指针
LRUElement*mru//链表的表头指针
inthit//命中次数
inttotal//读写操作的次数
intflashreadcount//物理读操作次数
intflashwritecount//物理写操作次数
假设读者需要开展实验测试自己的缓冲区替换算法的性能，建议首先阅读FlashDBSimDll_Sample工程下面的main.cpp、LRU.h和LRU.cpp文件，理解程序运行过程，从而更好地了解Flash-DBSim的使用方法以及如何在main.cpp中调用自己设计实现的其他缓冲区替换算法。在实现自己的缓冲区替换算法时，建议直接在LRU算法基础之上进行修改，这样可以避免引入未知错误。建议深刻理解LRU算法实例的运行细节，这样才能更好地设计实现自己的算法，知道哪些成员函数需要修改，哪些成员函数不需要修改。在实现自己的算法中，可以拷贝LRU算法的代码，修改关键的几个成员函数。这里需要注意的是，由于大部分成员函数不需要修改，如果读者需要实现多个不同的缓冲区替换算法，建议将那些不需要修改的成员函数移到基类BMgr中去。
利用闪存模拟器提供的仿真环境进行实验具有一定的局限性，因此，对于某些闪存研究实验，需要在真实的数据库和闪存设备环境下进行，因此，这里将介绍如何修改PostgreSQL开源数据库的源代码，从而实现真实环境下的性能测试。
在使用PostgreSQL开展实验之前，读者可能会思考一些问题，因此，这里以问答的形式帮助读者对实验的开展有一个整体的认识。
答1：是的，在postgresql-7.3.40/src/backend/storage/buffer目录下修改缓冲区替换算法，修改完成以后还和以前一样安装即可。
问2：要实现多个缓冲区替换算法，是否需要多次安装、卸载PostgreSQL？
答2：是的，一个系统中只有一个PostgreSQL数据库，如果要比较多个缓冲区替换算法的性能，则需要在每次实现一个算法的时候，都分别安装PostgreSQL，获取测试数据，然后卸载PostgreSQL，然后，再去实现下一个算法。
问3：如何将数据存储到固态盘？
问4：实验的输入数据是什么？从哪里来？
答4:开展实验时，不需要我们自己获取输入数据，有一个名为BenchmarkSQL的测试工具，会自动帮我们创建表，创建索引，添加数据。
问6：如何设置缓冲区大小？
答6：在PostgreSQL的源码中，有一个名为NBuffer的变量，默认值是1000，表示有几个缓冲区(数据页)，修改缓冲区大小，只需要修改这个变量的值即可。
问7：如何统计写操作次数和命中率？
使用PostgreSQL开展缓冲区替换算法，包括以下4个大的步骤：
第1步：下载PostgreSQL，修改PostgreSQL自带的缓冲区替换算法（LRU算法）的源代码，实现自己的缓冲区替换算法；
第2步：用源码安装的方式把PostgreSQL数据库安装到固态盘；
第3步：安装BenchmarkSQL；
第4步：使用BenchmarkSQL进行性能测试，获取测试结果
以上每一步都可以分为很多小步，其中，第1步最复杂，需要读者首先阅读PostgreSQL源码，在此基础上实现自己的缓冲区替换算法。
接下来的内容，将介绍以下几个方面的细节：
PostgreSQL需要在Linux环境下运行，可以采用虚拟机软件VMware，在其中安装ubuntu系统。
在Linux下安装PostgreSQL，需要遵循Linux下安装源码文件的三个步骤：
（1）./configure
（2）Make
（3）Makeinstall
通过上述三个步骤，就可以把PostgreSQL安装到prefix指定的目录下。
实际上，读者也可以根据PostgreSQL的安装说明文件来指导自己的安装过程。在刚才解压缩得到的postgresql-7.4.30目录下，有一个安装说明文件INSTALL，这里对该说明文件中的几行关键代码做简要解释，具体如下：
./configure#配置
gmake#make
su#切换到root用户
gmakeinstall#安装，以上几步是linux下安装软件的典型方式
adduserpostgres#添加一个用户，添加完用户以后需要通过passwdpostgres来修改该用户的密码
mkdir/usr/local/pgsql/data#新建一个目录，以后数据库的所有数据和操作都在该目录下
chownpostgres/usr/local/pgsql/data#更改目录的所有者为postgres
/usr/local/pgsql/bin/initdb-D/usr/local/pgsql/data#初始化工作区
/usr/local/pgsql/bin/postmaster-D/usr/local/pgsql/data>logfile2>&1&
/usr/local/pgsql/bin/createdbtest#启动服务，并新建一个名为test的数据库
/usr/local/pgsql/bin/psqltest#启动数据库
下面介绍如何将PostgreSQL安装到固态盘，以及如何配置PostgreSQL，使得BenchmarkSQL能够顺利完成对PostgreSQL的性能测试。
把PostgreSQL安装到固态盘，可以执行以下三个步骤：
make
sudomakeinstall
执行完上面3条语句以后，数据库就安装完成了，但是，还有很多工作要做。
其次，在替换完成以后，需要初始化工作区：
mkdir/usr/local/pgsql/data
chownuserName/usr/local/pgsql/data
再次，在初始化工作区以后，需要修改配置文件。进入存储空间所在文件夹(/usr/local/pgsql/data)，打开postgresql.conf文件，将#tcpip_socket=false的“#”删除，并把false改为true，另外，需要将#port=5432的“#”删除。
上面步骤完成以后，配置工作就完成了，下面只需要启动数据库服务，然后新建数据库就可以了。
#启动服务
/usr/local/pgsql/bin/pg_ctl-D/usr/local/pgsql/data-llogfilestart
#创建一个名为test的数据库
/usr/local/pgsql/bin/createdbtest
到这里为止，我们的数据库就创建完成了，下面就可以使用BenchmarkSQL来测试性能。
BenchmarkSQL是一款采用TPC-C的、开源的数据库测试工具，几乎不用修改就能测试当前主流数据库的性能。这里介绍BenchmarkSQL的下载、安装和使用方法。
首先，需要修改“BenchmarkSQL-2.3.2/run/”目录下面的postgres.properties文件，设置正确的数据库名和密码。如果之前已经创建了一个名为test的数据库，那么，这里只需要给出相应的账户和密码就可以了，具体配置如下：
driver=org.postgresql.Driver
conn=jdbc:postgresql://localhost:5432/test
user=lalor
password=123456
然后，在“BenchmarkSQL-2.3.2/run/”目录下运行如下命令：
./runSQL.shpostgres.propertiessqlTableCreates
上面的命令用于创建我们进行TPC-C测试所需的数据库表。
./loadData.shpostgres.propertiesnumWarehouses10
上面的命令用于加载我们进行TPC-C测试所需的数据，numWarehouses后的数字可以自行设置。
./runSQL.shpostgres.propertiessqlIndexCreates
上面的命令用于创建我们进行TPC-C测试所需的索引。
./runBenchmark.shpostgres.properties
使用BenchmarkSQL可以帮我们生成测试结果数据，从而了解数据库的性能，但是，如果要获取底层的详细信息，如缓冲区命中率、物理读操作次数和物理写操作次数等，则还需要查看PostgreSQL源代码，通过修改源代码来获取这些信息。具体方法如下：
vimPostgreSQL-7.4.30/src/backend/libpq/pqcomm.c
注册回调函数具体过程包含以下三个步骤：
第2步：定义回调函数
第3步：在合适的地方(pg_init)注册回调函数
voidpq_init(void){PqSendPointer=PqRecvPointer=PqRecvLength=0;PqCommBusy=false;DoingCopyOut=false;on_proc_exit(printBufferUsageInfo,0);//新增加的回调函数注册语句on_proc_exit(pq_close,0);}
通过前面内容的描述，我们已经了解了在PostgreSQL下测试缓冲区替换算法LRU的性能的基本过程。在实际研究工作中，我们需要测试其他多个缓冲区替换算法的性能，从而进行性能比较，但是，一个系统中只能有一个PostgreSQL数据库，在测试完LRU算法的性能以后，我们只能删除PostgreSQL数据库，再吧PostgreSQL数据库中的缓冲区替换算法修改成其他算法，再次进行安装测试。
删除PostgreSQL数据库包括以下4个步骤：
第1步：关闭数据库服务
/usr/local/pgsql/bin/pg_ctl-D/usr/local/pgsql/data-llogfilestop
第2步：删除数据库
/usr/local/pgsql/bin/dropdbtest
第3步：卸载PostgreSQL
sudomakeuninstall
sudomakeclean
第4步：删除目录
sudorm-rf/usr/local/pgsql
下面首先介绍修改PostgreSQL的预备知识，然后介绍修改PostgreSQL缓冲区替换算法的基本步骤，最后给出一个实例，介绍如何修改PostgreSQL实现缓冲区替换算法CFLRU。
图[PostgreSQL-LRU]PostgreSQL中的LRU算法所使用的数据结构
图[PostgreSQL-LRU]显示了PostgreSQL中的LRU算法所使用的“LRU链表”，不过需要注意的是，这个LRU链表并不是真正的链表，而是用数组来实现的，数组名为BufferDescriptors，数组中有NBuffer+1个“描述子”，所谓“描述子”就是一个结构体（BufferDesc）类型的变量，用于表示LRU链表的一个元素，结构体（BufferDesc）类型定义位于头文件buf_internals.h中。如果我们实现的算法中需要增加新的属性，就在该结构体中添加。数组BufferDescriptors中，前NBuffer个元素用来表示空闲缓冲区（数据页），最后一个元素是“哨兵”，设置这个元素是为了方便操作，有一个指针变量SharedFreeList会一直指向“哨兵”位置，当满足SharedFreeList->freeNext==Free_List_Descriptor的时候，就说明缓冲区中的所有数据页都在被使用。有了SharedFreeList，我们就可以很快地从LRU链表中选择LRU位置的数据页作为驱逐页，并将新的数据页插入到LRU链表的MRU位置。
在PostgreSQL中，有了上面的数据结构，实现LRU算法只用到了两个函数：
修改PostgreSQL的缓冲区替换算法主要包括两个步骤：
第1步：修改描述子，增加新属性。若新算法为缓冲区赋予了新的属性，则需要修改PostgreSQL缓冲区描述子的数据结构，在其中定义新的参数，以描述缓冲区的新属性。
第2步：增加新的数据结构和操作。LRU算法要求缓冲池是一个LRU链表，若新算法要求缓冲池是另一种数据结构，就需要对缓冲区管理部分进行相应的修改。首先，需要修改缓冲区描述子的数据结构，增加新的数据结构，满足缓冲池的构建要求；然后，需要修改缓冲池的初始化操作，在初始化时构建新结构的缓冲池；最后，通过修改原有的缓冲池维护操作，或者替换和增加新的维护操作，保证缓冲池的数据结构始终满足新算法的要求。
CFLRU算法[ParkJKKL06]采用了“双区域”机制，把LRU链表划分成两个区域，即工作区域和干净优先区域，两个区域可以采用各种成熟的替换算法（比如LRU）。CFLRU算法不需要增加新属性，只需要判断干净页优先区域(Clean-FirstRegion)中是否有干净页，如果有干净页，就替换干净页，如果没有干净页，就替换LRU位置的数据页。在CFLRU算法中，我们只需要增加一个变量nWindowSize表示干净页优先区域的大小，然后修改GetFreeBuffer()函数即可。
（1）PostgreSQL自带的LRU算法中的GetFreeBuffer()函数
/*
*/
BufferDesc*
GetFreeBuffer(void)
{
BufferDesc*buf;
if(Free_List_Descriptor==SharedFreeList->freeNext)
/*queueisempty.Allbuffersinthebufferpoolarepinned.*/
ereport(ERROR,
(errcode(ERRCODE_INSUFFICIENT_RESOURCES),
returnNULL;
}
buf=&(BufferDescriptors[SharedFreeList->freeNext]);
/*removefromfreelistqueue*/
BufferDescriptors[buf->freeNext].freePrev=buf->freePrev;
BufferDescriptors[buf->freePrev].freeNext=buf->freeNext;
buf->freeNext=buf->freePrev=INVALID_DESCRIPTOR;
buf->flags&=~(BM_FREE);
returnbuf;
（2）采用CFLRU算法时修改以后的GetFreeBuffer()函数
intn=0;
/*selectareplacepageinclean-firstregion*/
while(n /*Isbufferdirty*/ if(buf->flags&BM_DIRTY||buf->cntxDirty) buf=&(BufferDescriptors[buf->freeNext]); /*nomorebuffer*/ if(buf==SharedFreeList) buf=NULL; break; else {/*selectthispageasreplacepage*/ n++; *1.buf==NULL说明缓冲区中总共也没有nWindowSize个freebuffer *2.n>=nWindowSize说明缓冲区中干净页优先区域中，全都是脏页