[erlang-questions] e2qc, a 2Q NIF cache

[Alex Wilson]

Hi all,

I've put together an Erlang NIF library implementing the 2Q cache management algorithm (http://www.inf.fu-berlin.de/lehre/WS10/DBS-Tech/Reader/2QBufferManagement.pdf) with a focus on having a very simple-to-use API. I thought I might share it on this list in case anybody is interested and/or wants to make it break and tell me how they did it. :) The code is up on github under a BSD license.

2Q is a refinement of the classic LRU (Least-Recently-Used) cache management algorithm that achieves better hit rates with many common workloads -- especially those that benefit from rejection of sequential scans. In the worst case, it generally performs no worse than plain LRU and still retains much of its simplicity.

Lookups in e2qc are done through a hash table (uthash, with Paul Hseih's hash function), and the cache structure is held in a pair of doubly-linked lists (see the paper for more info about the 2Q structure). Cache hits with e2qc can be zero-copy if using binaries for key and value (key is used as-is, the value in a resource binary). Also, updates to the cache lists and structure are asynchronous, deferred to a background thread -- all the updates get batched up together with the next eviction operation to minimise the time spent with locks held and avoid blocking the VM, rather than mutating the cache lists during a get or put operation.

Its main claim to fame though is that using it is super simple:

some_function(Input) ->
    do_slow_thing(Input).

becomes

some_function(Input) ->
    e2qc:cache(slow_thing, Input, fun() ->
        do_slow_thing(Input)
    end).

and ta-da! your results are cached. No need to start a process for it or pass a handle around, no need to even provide any settings or configuration -- you can just add it wherever in your code. More details are in the README on github:

	https://github.com/arekinath/e2qc

Thanks for your time!