使用文件缓存（MRU）克服进程限制

下载 catch_es.zip - 6.45 KB

引言

当访问大量数据时，进程经常因内存超过2.9G字节而异常退出。通常有两种方法可以解决这个问题。

1. 使用数据库系统（例如BDB）来保存数据。当需要使用某个数据时，进程从数据库读取该数据，进行操作，然后写回数据库。
2. 使用文件来保存数据。当需要使用某个数据时，进程从文件中读取该数据，进行操作，然后写回文件。

这两种方法都会因为频繁操作文件系统而降低进程的性能。本文提出了一种将缓存的MRU算法应用于进程内频繁访问数据的保存，并将不常访问的数据保存到进程外的文件系统中的方法。该方法的主要优点是性能高，并且可以打破进程的内存限制。

背景

该算法非常简单。它维护一个哈希表和一个双向链表来在进程内存中保存频繁访问的数据，最新的访问数据会将最不活跃的数据推出进程内存。被推出的数据将被保存在文件中。进程数据结构如下：

为了能够快速地在双向链表的键和哈希表的键之间进行映射，程序将双向链表中的键替换为哈希表迭代器的指针。
过程如下：

A: 插入数据

1. 如果哈希表的大小没有超过设定值，哈希表将增加一行。同时，数据块将分配一个未使用的内存空间，并将新键调整到双向链表的头部。
2. 如果哈希表的大小超过了设定值，程序将获取双向链表尾部的键，将该键的数据写入文件，然后将腾出的内存空间分配给新数据。之后，程序会将双向链表的尾部调整到其头部。

B: 删除数据

1. 如果被删除数据的键在哈希表中，程序会将IsReleased设置为true，并删除文件中对应的项。
2. 如果被删除数据的键不在哈希表中，程序将删除文件中对应的项。

C: 访问数据

1. 如果被访问数据的键在哈希表中，程序将获取该数据在数据块中的索引，并将该键调整到双向链表的头部。最后，程序将返回数据块中数据的指针。
2. 如果被访问数据的键不在哈希表中，程序将获取双向链表的最后一个键，将最后一个键的数据写入文件。完成这些步骤后，将有一个腾空的内存空间供将来使用。然后，程序从文件中读取所需数据并将其放入腾空的内存空间。最后，程序调整双向链表，将尾部变为头部，并返回存放所需数据的内存空间的指针。

从上面的描述可以看出，使用文件中数据的偏移量作为数据键是一种简单的方法。换句话说，无论数据是否在进程的内存中，每个数据在文件中都将拥有自己的空间。

由于程序需要高性能，并且文件可能就是计算机的内存，因此控制文件大小和减少文件访问次数是设计文件结构的主要因素。为了减少文件访问次数，我建议程序在从缓存获取或放入数据时只进行一次文件访问操作。在源代码中，只有获取数据可能会导致文件的读写操作。为了控制文件大小，程序采用了先“重新分配”已使用的空闲数据空间，后分配新的文件数据空间的规则。为了遵守该规则，文件结构如下：

浅灰色部分代表文件中空闲的数据空间，绿色部分代表正在使用的数据空间。每个空闲的数据空间使用4个字节来记录文件中下一个空闲数据空间的偏移量。程序只知道文件中第一个空闲数据空间的偏移量，因此可以先重新分配所有空闲数据空间。

程序局限性

1. 缓存中的数据必须大于4字节。
2. 数据必须是相同大小。
3. 文件大小限制约为4G。
4. 非线程安全。

环境

Windows, Linux
gcc, vc

Using the Code

1. 带频率调整地获取数据

CFileManager_EqualSize tempFileManager_ES; //Declare the class
//Set the file name and the data size
tempFileManager_ES.createAFile("/var/tempdatafile", sizeof(int));
tempFileManager.setblocksize(10000); //Set the cache size
int aintpos = tempFileManager.malloc(0); //allocate a data resource
int **intptr;
tempFileManager.read(aintpos, 0, (void**)intptr); //get the data
**inteptr = 10; //operate the data
tempFileManager.deleteMe(); //release the resource.

1. 不带频率调整地获取数据

CFileManager_EqualSize tempFileManager_ES; //Declare the class
//Set the file name and the data size
tempFileManager_ES.createAFile("/var/tempdatafile", sizeof(int));
tempFileManager.setblocksize(10000); //Set the cache size
int aintpos = tempFileManager.malloc(0); //allocate a data resource
int **intptr;
tempFileManager.read_nsort(aintpos, 0, (void**)intptr); //get the data
**inteptr = 10; //operate the data
//Write the data back to cache. Because read_snort may get data from file 
//without putting it into cache, program //must write data back.
tempFileManager.write(aintpos, 0, intptr) 
tempFileManager.deleteMe(); //release the resource. 

Using the Code

适用于中文