Add some kind of LRU support

Right now there's no mechanism for eviction, that is mandatory for caching services. Adding LRU is not an easy job since it depends on some kind of internal extensions for memory allocations or new data structures.

Ways to handle:

Capped collections - MongoDB citation "fixed-size collections that support high throughput operations that insert and retrieve documents based on insertion order. Capped collections work in a way similar to circular buffers: once a collection fills its allocated space, it makes room for new documents by overwriting the oldest documents in the collection."
Some kind of external LRU implementation with changes on every get - heavy solution (simpler - some mutable fields in tuple and change this field on every access)
per slab-level LRU, 100% chance that deletion will provide you new tuple

Also, compaction of memory is needed (triggered or automatic)

Comment from @txii

I'm trying to test eviction feature of ordinary memcached. For that purpose I created tarantool instance with memcached interface with small amount of memory available (~ 2mb or less) and started this small perl script to constantly set a key and get it back to check if it was written correctly:

use strict;
use warnings;

use Test::More 'no_plan';
use Cache::Memcached::Fast;

my $memd = new Cache::Memcached::Fast({
    servers => [ "host:port" ],
    nowait => 0,
    hash_namespace => 0,
    utf8 => ($^V ge v5.8.1 ? 1 : 0),
});

for my $i (8 .. 100_000) {
    my $ttl = 5*60;
    my $store_key   = "ttladdmanythiskey$i";
    my $store_value = "ttladdmanythisvalue$i";

    is(  $memd->get($store_key), undef,              "Get not existent value for iteration $i"  );
    ok(  $memd->set($store_key, $store_value, $ttl), "Set with ttl ok for iteration $i"         );
    is(  $memd->get($store_key), $store_value,       "Cmp value for iteration $i"               );
}

I expect that set will be OK always, regardless of how much space is already used and whether or not the same key was already set (so set() is always ok). But a get errors for set() on ~ 100th (well, randomly, btw) iteration of the loop.

The same error is repoduced when ->add is used instead of ->set.

Also I used tcpdump to see tarantool responses. Some of them were:

        0x0000:  4500 007a 9464 4000 3a06 d7e7 0aff da85  E..z.d@.:.......
        0x0010:  053d e970 2bcb b6a1 d007 31d2 ba66 9ae9  .=.p+.....1..f..
        0x0020:  8018 7120 6ac1 0000 0101 080a 5d23 a5ab  ..q.j.......]#..
        0x0030:  f039 1d5f 5345 5256 4552 5f45 5252 4f52  .9._SERVER_ERROR
        0x0040:  2046 6169 6c65 6420 746f 2061 6c6c 6f63  .Failed.to.alloc
        0x0050:  6174 6520 3833 2062 7974 6573 2069 6e20  ate.83.bytes.in.
        0x0060:  736c 6162 2061 6c6c 6f63 6174 6f72 2066  slab.allocator.f
        0x0070:  6f72 2074 7570 6c65 0d0a                 or.tuple..

So I think the problem is with memcached's eviction support.

tarantool / memcached

Add some kind of LRU support #42