Erlang LRU Cache

Question

How to implement a LRU Cache with Erlang?

LRU Cache Wiki

Top starred Github project was fogfish/cache, but Segmented table was not quite fit for my data.

barrel-db/erlang-lru was using a List. after testing, it would be slow if there were too much data.

I guess the problem was here.

move_front(List, Key) -> [Key | lists:delete(Key, List)].

With Java, a better implementation was using a hashmap and a linkedlist like this

I tried to do a linkedlist, and then realized that Linkedlist was not good idea for Erlang, like this thread.

the question is how to do a LRU cache with Erlang?

Answer 1

I've implemented LRU cache using pseudo-time approach (full implementation is available here https://github.com/poroh/erl_lru)

I have two data structure:

1. Unordered map for lookup: #{key() => {order(), value()}}
2. Ordered map for item ordering: gb_tree(order(), key())

Where order() is pseudo-time:

• It is incremented each time when new element is added or any element is updated
• Each element that belongs to LRU has its own update time

Operations:

All operations has O(log(N)) complexity because of using gb_tree.

Add element (Key, Value):

• Increment time (result is T)
• Put Key => {T, Value} to unordered map
• Put {T, Key} to ordered map
• Check overflow

Update element (Key):

• Find element in unordered map Key => {T0, Value}
• Increment time (result is T)
• Remove element Key from unordered map
• Remove element T0 from ordered map
• Add element (Key, Value) as above

Check overflow:

• If number of elements in cache is more than possible maximum
  • take smallest (gb_tree:take_smallest) element in ordered map (T, Key)
  • remove element T from ordered map
  • remove element Key from unordered

Answer 2

The first implementation of THE CACHE was based on ETS with two indexes. One ets table is hold TTL -> Key relation, another ets table is Key -> Object. You can see the implementation at

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

The maintenance of two index was not efficient thus segmented cache outperform original implementation. I would not recommend to implement per-object TTL using Erlang data structures unless you can model your data within actors and accepts overhead. There is an implementation to address it. It is uses process per object concept:

https://github.com/fogfish/pts

Otherwise, you need to implement NIF