Erlang LRU缓存

Question

如何使用Erlang实现LRU Cache？ LRU Cache Wiki 最受欢迎的Github项目是fogfish/cache，但分段表不太适合我的数据。 barrel-db/erlang-lru使用了List。经过测试，如果数据量太大，速度会变慢。

我想问题可能出在这里。 move_front(List, Key) -> [Key | lists:delete(Key, List)]. 使用Java，更好的实现方法是使用hashmap和linkedlist像这样。

我曾尝试使用链表，但后来意识到在Erlang中不适合使用链表，就像这个帖子所说的那样。

问题是如何使用Erlang实现LRU缓存？

- user3644708

---

我认为Erlang对于做低级缓存来说太高级了，而且目前在核心功能中Erlang有一些类似的特性（比如ETS http://erlang.org/doc/man/ets.html），所以在使用外部项目之前，你是否测试过这些功能之一？ - Mathieu Kerjouan

@MathieuK，谢谢你的评论。是的，我试过了。关键问题是LRU（最近最少使用）算法。我尝试使用表格来保存访问时间，但是每次读取/更新时，我需要更新（删除然后插入）表格。我想知道是否有更好的方法可以解决这个问题？ - user3644708

我没有一个对你问题的确定答案。如果你想在Erlang中实现高效的LRU缓存，我猜最好的方法之一是使用连接到 ports 或者 NIF 的外部代码。C编程不是我的最爱领域，但如果你需要一些实现C代码用于Erlang的例子，可以查看beam源代码。 - Mathieu Kerjouan

Answer 1

THE CACHE的第一次实现基于ETS，有两个索引。一个ETS表保存了TTL -> Key关系，另一个ETS表保存了Key -> Object关系。您可以在以下网址查看实现：

https://github.com/fogfish/cache/commit/8cc50bffb4178ad9ad716703507c3290e1f94821

维护两个索引效率不高，因此分段缓存优于原始实现。我不建议使用Erlang数据结构来实现每个对象的TTL，除非您可以在actor中建模您的数据并接受开销。有一种实现方法可以解决这个问题，它使用每个对象的进程概念：

https://github.com/fogfish/pts

否则，您需要实现NIF。

- fogfish

Answer 2

我使用伪时间方法实现了LRU缓存（完整实现可在此处找到https://github.com/poroh/erl_lru）

我有两个数据结构：

1. 用于查找的无序映射：#{key() => {order(), value()}}
2. 用于项目排序的有序映射：gb_tree(order(), key())

其中order()是伪时间：

• 每次添加新元素或更新任何元素时，它都会递增
• 属于LRU的每个元素都有自己的更新时间

操作：

由于使用了gb_tree，所有操作的复杂度均为O(log(N))。

添加元素（Key，Value）：

• 增加时间（结果为T）
• 将Key => {T，Value}放入无序映射中
• 将{T，Key}放入有序映射中
• 检查溢出

更新元素（Key）：

• 在无序映射中查找元素 Key => {T0, Value}
• 增加时间 (结果为 T)
• 从无序映射中删除元素 Key
• 从有序映射中删除元素 T0
• 按上述方式添加元素 (Key, Value)

检查溢出:

• 如果缓存中的元素数量超过可能的最大值
  • 取有序映射中最小的元素 (gb_tree:take_smallest) (T, Key)
  • 从有序映射中删除元素 T
  • 从无序映射中删除元素 Key

- Dmitry Poroh