如何在C++中实现缓存？

Question

假设我有一个非常大的 std::map< unsigned int, Foo > FooDB，它在内存中保存了 Foo 对象，可通过其 ID 检索。现在可能会有比可用内存更多的 Foo 对象。因此，我想要以下结构：

- 从 FooDB 中检索 ID 为 x 的 Foo 对象。 - 如果对象 x 在 FooDB 中，则返回它。 - 如果不在，从硬盘加载它，并尝试将其存储在 FooDB 中以供进一步查询。 - 如果有足够的内存可用：将其添加到 FooDB 中。 - 如果没有足够的内存：通过删除未使用的对象（最旧的查询时间戳）来释放一些空间。

我想为 FooDB 保留一些内存，但我无法确定其中可以存储多少个 Foo 对象，因为它们的大小不同。

有什么方法可以实现这个问题？

编辑：

我的基本问题是：如何确定 std::map 在内存中的大小？当然，包括其中存储的所有堆对象。如何知道已经达到了 没有足够的内存 部分？

- Ben

---

有些公司专门从事这项业务，年收入高达数十亿美元，所以这是一个相当重要的话题。 - Mysticial

最简单的情况下，您的算法可以直接从伪代码转换为代码。所以只需继续进行即可。但对于更复杂的解决方案，Mysticial是一个不错的选择。您可能需要一个数据库引擎。 - Sam

具体来说，谷歌的NoSQL和键值存储。其中一些使用内存映射进行实现（如果有足够的内存，它们可以完全在内存中运行）。 - sehe

性能标准是什么？有多少项？难道你不能只使用sqlite或<插入任何合理的基于磁盘的数据库>并让操作系统处理磁盘/内存缓存吗？如果它变得太慢，可以在其上添加一个LRU缓存，例如http://code.google.com/p/lru-cache-cpp/。 - user172783

@Mystical：我不需要复杂的预测来确定哪些对象应该被删除。一个非常简单的方法就可以做到这一点。数据库是一个选择，我只是想知道是否有一个简单的DIY解决方案。 - Ben

无法获取非平凡变量的实际内存使用情况，但可以猜测。在 Foo 中添加一个方法来猜测其内存使用情况。不必担心多或少一个字节。找出最大的块并尝试正确地获取它们，并添加一些偏移量以覆盖较小的部分和开销。 - rtlgrmpf

Answer 1

据我所知，除了使用sizeof()外，没有其他方法可以询问对象的大小。您说sizeof()不起作用是因为Foo对象没有固定大小。在这种情况下，如果您可以修改Foo，那么也许您的Foo类可以在内部跟踪其内存占用。如果您无法修改Foo，则可能编写一个外部函数来推断内存占用量。

从根本上讲，语言/编译器/运行时很难知道动态大小对象的大小，因为它不知道哪些分配属于对象。一个简单的解决方案是递归地总结它的成员指向的所有内容，但对于指向它不“拥有”的对象的指针，这种方法将失败。另一个简单的解决方案是跟踪构造函数开始和返回之间进行的所有分配，但对于在调用构造函数后进行分配的任何内容，此方法将失败。

您可能只想使用Foo的数量作为缓存限制，而不是内存大小。除非您非常了解整个系统的内存可用性和使用情况，否则基于内存大小的限制也是任意的。如果您非常了解整个系统的内存使用情况，您可以仅使用整体内存可用性来确定何时释放缓存中的对象。

- Tom Panning

---

我可以跟踪Foo对象的大小。但是例如在std::map中，还有一个开销，因为它必须在某个地方存储树结构以用于索引。使用sizeof()或跟踪我的对象大小就不会有这种情况。 - Ben

@Ben 如果你担心树结构的大小，那么要么Foo对象非常小，要么你需要一个非常精确的测量。如果Foo对象很小，那么限制Foo对象的数量就可以了。否则，如果你需要一个非常精确的测量，我很想知道为什么。 - Tom Panning

这取决于你所谓的“小”。Foo的大小在10到300KB之间。我意识到我的进程消耗的内存比我预期的要高。我不知道它去了哪里，我只是用索引开销来解释它，就像每个数据库一样。而且我不想冒出现内存不足异常的风险，仅此而已。 - Ben

Answer 2

这很简单。

只需按年龄顺序在一个排序的链表中放置每个内存中的Foo实例引用到FooDB中。

当首次将新项加载到内存中时，将其添加到列表前面。

当读取/修改项时，将其从列表中间移动到列表前面。

当需要删除旧项以腾出空间时，请从列表后部弹出它。

例如：

typedef shared_ptr<Foo> PFoo;

class Foo
{
    ...
    list<PFoo>::iterator age;
};

typedef map< unsigned int, PFoo > FooDB;
FooDB foodb; 

list<PFoo> ages;

void LoadFoo(PFoo foo)
{
    ages.push_front(foo);
}

void ReadFoo(PFoo foo)
{
    ...
    ages.erase(foo->age);
    ages.push_front(foo);
}

void MakeSpace()
{
    PFoo foo = ages.back();
    ages.pop_back();
    DeleteFoo(foo);
}

- Andrew Tomazos

---

是的，这是容易的部分，我处理时间戳。但是我怎么知道我的地图是否已满？ - Ben

是的，但是 Foo 的大小不固定。因此我不知道它们实际使用了多少内存。 - Ben

那么你无法在运行时测试一个 Foo 实例使用了多少空间吗？ - Andrew Tomazos

我想知道FooDB有多大，如果它达到了6GB，我想释放一些空间。MemoryPool类听起来不错。我猜我可以为池分配6GB并在满时进行检查？ - Ben

@Ben：你已经知道这个项目是否因为它是FooDB映射的成员而被缓存在内存中了。我假设这就是FooDB的目的。(此外，你应该使用unordered_map来代替FooDB，因为这将给你O(1)的性能，而不是O(logN))。如果这不是FooDB的目的，那么创建一个单独的unordered_set<int>，用于跟踪加载到内存中的元素的ID，并在加载和关闭项目时更新它。排序列表用于跟踪项目的年龄。 - Andrew Tomazos