C语言中的LRU缓存

Question

我需要在C应用程序（在*nix环境中）中将大量（但可变）的较小文件（1千字节到10兆字节）缓存在内存中。由于我不想耗尽所有内存，我想设置一个硬内存限制（比如说64兆字节），并将文件推入哈希表中，以文件名作为键，并且处理最少使用的条目。我相信我需要的是一个LRU缓存。

实际上，我不想自己动手，所以如果有人知道哪里可以找到可行的库，请指引一下？如果找不到，能否提供一个简单的C语言LRU缓存示例？相关帖子表明需要使用双向链表的哈希表，但我甚至不清楚双向链表如何保持LRU。

顺便说一下：我意识到这几乎就是memcache的功能，但对我来说不是一个选项。我还查看了源代码，希望能够让自己了解LRU缓存，但没有成功。

- lazyconfabulator

---

在某种程度上，这似乎与您的操作系统磁盘缓存具有相同的功能。 - Thanatos

你有多需要这个？如果你只是想减少平均访问延迟，并且正在运行完整的服务操作系统，那么就让操作系统来处理它。自己管理只是一种特殊情况... - dmckee --- ex-moderator kitten

HTTP服务器通常执行相同的功能（提供大量较小文件），它们通常包含自己的缓存，而不是使用操作系统的磁盘缓存。我认为这表明仅依赖操作系统进行缓存并不是最优解决方案。 - lazyconfabulator

Answer 1

相关帖子表明了哈希表中含有双向链表，但我甚至不清楚双向链表如何保持LRU。 我只是猜测，但可能可以像这样做（使用伪C语言因为我比较懒）。以下是基本数据结构：

struct File
{
    // hash key
    string Name;

    // doubly-linked list
    File* Previous;
    File* Next;

    // other file data...
}

struct Cache
{
    HashTable<string, File*> Table // some existing hashtable implementation
    File* First; // most recent
    File* Last;  // least recent
}

以下是如何打开和关闭文件的示例：

File* Open(Cache* cache, string name)
{
    if (look up name in cache->Table succeeds)
    {
        File* found = find it from the hash table lookup
        move it to the front of the list
    }
    else
    {
        File* newFile = open the file and create a new node for it

        insert it at the beginning of the list

        if (the cache is full now)
        {
            remove the last file from the list
            close it
            remove it from the hashtable too
        }
    }
}

散列表可以快速地通过名称找到节点，而链表可以让你按使用顺序维护它们。由于它们指向相同的节点，你可以在它们之间切换。这样，你可以通过名称查找文件，然后在列表中移动它。

但我对这些都可能完全错了。

- munificent

Answer 2

如果你在使用Linux，我认为操作系统可以满足你的需求，特别是如果你利用fadvise系统调用告诉系统你计划下一个使用哪些文件。

- Norman Ramsey

Answer 3

koders.com 找到了一些相关的内容；如果你能接受它的许可条件，最容易适应和重用的一个似乎是来自 FreeType 项目的 this one（需要一些时间去理解它那有点儿“有趣”的预处理器工作）。最坏的情况下，它应该可以展示给你一种在 C 中实现 LRU 缓存的方法。

当然，大多数可重用的 LRU 缓存实现（网络上有很多），使用更方便的语言（Java、C++、C#、Python 等），提供更强大的数据结构和通常更好的内存管理。

- Alex Martelli

Answer 4

看起来你可以用uthash在C语言中构建LRU缓存。

我最喜欢uthash的地方是它只是一个简单的头文件，有很多宏，因此你的额外依赖保持最小。

- user159987

Answer 5

我不知道在C语言中是否有任何通用的Unix环境库，但实现起来应该不难。

对于代码示例，我建议查看任何一个海量（oi）哈希表实现。无论表格使用链接列表还是树结构进行实际处理，通常都会使用某种形式的缓存（例如MRU），因此它可能会给您提供实现的想法。一些简单的垃圾收集器和需要页面替换算法的各种软件也值得一看。

基本上，当访问时标记物品并使引用变老。如果在访问时增加事物的年龄而不是每个访问项的同级，则显然可以节省访问时的循环并将权重推到过期操作上。您需要进行一些轻量级的分析，以找到最近最少使用的足够不太频繁的一般想法。当您达到那个点时，只需相应地更新缓存即可。

- TerryP