Cache algorithm implementation "Least frequently used"

data-structures
algorithms
lfu
caching
(Adavidoaiei Dumitru-Cornel) #1

In .NET Framework nu exista un caching care sa implementeze algoritmul least frequently used pentru eliminarea elementelor cel mai putine accesate atunci cand acesta ajunge la dimensiunea maxima.

O posibila solutie pentru implementarea algoritmului least frequently used, se construieste o lista inlantuita(lfuList) a elementelor din cache(CacheNode) ordonata dupa numarul de accesari a fiecarui element(UseCount), de fiecare data cand un element din cache este accesat se incrementeaza numarul de accesari(UseCount) pentru acest element, iar elementul se repozitioneaza in lista inlantuita(lfuList) astfel incat ca elementele din aceasta lista inlantuita sa fie ordonate dupa numarul de accesari, cand adaugam un nou element in cache dar acesta a ajuns la dimensiunea maxima se elimina primul nod din lista inlantuita(lfuList), acesta fiind cel mai putin accesat, de asemenea acesta se sterge si din cache lasand loc noului item.

Urmatorul cache este implementat pentru a fi folosit intr-o aplicatie single thread, pentru o aplicatie multithreading acest cache trebuie adaptat pentru a asigura accesul thread safe concurent la date.

public class LfuCache<TKey, TValue>
{
    private class CacheNode
    {
        public TKey Key { get; set; }
        public TValue Data { get; set; }
        public int UseCount { get; set; }
    }

    private readonly int _size;

    private Dictionary<TKey, LinkedListNode<CacheNode>> _cache = new Dictionary<TKey, LinkedListNode<CacheNode>>();
    private LinkedList<CacheNode> _lfuList = new LinkedList<CacheNode>();

    public LfuCache(int size)
    {
        _size = size;
    }

    public void Add(TKey key, TValue val)
    {
        TValue existing;

        if (!TryGet(key, out existing))
        {
            var node = new CacheNode() { Key = key, Data = val, UseCount = 1 };

            if (_lfuList.Count == _size)
            {
                _cache.Remove(_lfuList.First.Value.Key);
                _lfuList.RemoveFirst();
            }

            var insertionPoint = Nodes.LastOrDefault(n => n.Value.UseCount < 2);

            LinkedListNode<CacheNode> inserted;

            if (insertionPoint == null)
            {
                inserted = _lfuList.AddFirst(node);
            }
            else
            {
                inserted = _lfuList.AddAfter(insertionPoint, node);
            }

            _cache[key] = inserted;
        }
    }

    IEnumerable<LinkedListNode<CacheNode>> Nodes
    {
        get
        {
            var node = _lfuList.First;
            while (node != null)
            {
                yield return node;
                node = node.Next;
            }
        }
    }

    IEnumerable<LinkedListNode<CacheNode>> IterateFrom(LinkedListNode<CacheNode> node)
    {
        while (node != null)
        {
            yield return node;
            node = node.Next;
        }
    }

    public TValue GetOrDefault(TKey key)
    {
        TValue val;
        TryGet(key, out val);
        return val;
    }

    public bool TryGet(TKey key, out TValue val)
    {
        LinkedListNode<CacheNode> data;
        bool success = false;

        if (_cache.TryGetValue(key, out data))
        {
            var cacheNode = data.Value;
            val = cacheNode.Data;
            cacheNode.UseCount++;

            var insertionPoint = IterateFrom(_lfuList.First).Last(n => n.Value.UseCount <= cacheNode.UseCount);

            if (insertionPoint != data)
            {
                _lfuList.Remove(data);
                _lfuList.AddAfter(insertionPoint, data);
            }

            success = true;
        }
        else
        {
            val = default(TValue);
        }

        return success;
    }
}
3 Likes
(Ex. Dakull) #2

@adavidoaiei ar fi interesant si o serie de benchs. comparative?

(Ionuț Botizan) #3

Frecvență = Mărime care arată de câte ori se produce un fenomen într-o unitate de timp.


Algoritmul tău nu folosește nici o unitate de timp la care să raporteze numărul utilizărilor/accesărilor, de aceea nu se poate numi Least Frequently Used ci doar Least Used. După o perioadă mai mare de timp se poate întâmpla ca noduri irelevante să nu fie eliminate din cache în timp ce altele relevante să nu fie păstrate.

Un exemplu băbesc:
În ultima lună (unitate de timp aleasă de mine arbitrar), ai adunat în cache elementele:

Node | Count | Daily
====================
  a  |  120  |  4.0
  b  |   90  |  3.0
  c  |   30  |  1.0
  d  |    9  |  0.3

Însă, în ultimele 3 zile ai avut 2 noduri accesate de 30, respectiv 18 ori

Node | Count | Daily
====================
  x  |   18  |  6.0
  y  |    6  |  2.0

Din cauza faptului că te bazezi numai pe Count, doar nodul d va fi eliminat din cache și numai nodul x va fi adăugat, deși, raportat la unitatea de timp zi, ambele au o frecvență mai mare decât c și d.
În schimb, c este păstrat și cu fiecare zi ce trece, deși frecvența este aceeași, numărul total crește și va deveni tot mai greu de eliminat din cache.

Unitățile pot fi scalate în jos, la nivel de oră/minut sau orice are sens în cazul tău. Rezultatul va fi același.

1 Like
(Adavidoaiei Dumitru-Cornel) #4

@dakull cam asa arata un benchmark:

metoda pe care s-a facut benchmark adauga 100.000 de elemente intr-un cache de size 90.000 si apoi face get la ele, din pacate implementarea veche nu mergea pe 100.000 de elemente, ci doar pe testele cu 1000 si 10.000 asa ca am schimbat implementarea, nu stiu daca e perfecta dar trece testele unitare, in loc de lista inlantuita am folosit un sorted dictionary in care cheia e UseCount iar valoarea e o lista inlantuita cu elementele din cache care au fost accesate de un numar UseCount.

@IonutBotizan exemplul cu impartirea pe zile nu mi se pare relevanta pentru ce am implementat eu cache-ul, durata lui de viata e destul de scurta, il folosesc pentru caching-ul elementelor parsate, spre exemplu in excel ai shared string item care reprezinta celule excel cu formatare care se repeta, ca sa nu le parsez de mai multe ori fac caching la ele.

Ideea din algoritm se gaseste si in definitia standard LFU https://en.wikipedia.org/wiki/Least_frequently_used care nu zice nimic de timp ci doar de Count.

3 Likes
(Ionuț Botizan) #5

În link-ul Wikipedia pe care l-ai dat este expusă aceeași problemă pe care am menționat-o eu (vezi secțiunea Problems).

Cât despre unitatea de timp, cum am zis în mesajul inițial, poți scala în ce direcție vrei, problema e aceeași. Pune milisecunde în loc de zile și vei avea același rezultat.

1 Like
(Adavidoaiei Dumitru-Cornel) #6

Am facut un proiect in care am pus implementarea refactorizata a algoritmului least frequently used cache care are complexitate logaritmica, proiectul mai contine teste unitare si de performanta.

Performance benchmark

1000.000 add/get operations on implemented Least Frequently Used Cache of size 90.000 using elements from a list with 100.000 takes 466ms.

This cache runs faster than MemoryCache from .NET Framework and consumes less memory than this on the same benchmark.

1 Like
(Adavidoaiei Dumitru-Cornel) #7

Am incercat sa scriu o postare pe blog despre implementare Least Frequently Used Cache in .NET cu teste unitare si teste de performanta:

1 Like