lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Yonik Seeley (Commented) (JIRA)" <>
Subject [jira] [Commented] (SOLR-2906) Implement LFU Cache
Date Sat, 19 Nov 2011 00:18:52 GMT


Yonik Seeley commented on SOLR-2906:

bq. I've been trying to find my bug. Looking back at the original LRU implementation, I have
no idea how it's working.

Heh... it is pretty complex, and I did try to add a ton of comments because of that.
The basic idea is that I wanted to avoid an O(n*log( n )) solution of sorting everything and
then discarding the lowest.
In my testing, it seems to work, and we often just need to take a singe O( n ) pass to evict
all the entries we need.

The comment at the top is the most important to understanding how it works:

    // if we want to keep at least 1000 entries, then timestamps of
    // current through current-1000 are guaranteed not to be the oldest (but that does
    // not mean there are 1000 entries in that group... it's acutally anywhere between
    // 1 and 1000).
    // Also, if we want to remove 500 entries, then
    // oldestEntry through oldestEntry+500 are guaranteed to be
    // removed (however many there are there).

But really, it seems like you should disregard all the algorithmic stuff in LRU when implementing
If you think you see a bug in the existing LRU stuff, you're going to have to spell it out
for me a bit more.
> Implement LFU Cache
> -------------------
>                 Key: SOLR-2906
>                 URL:
>             Project: Solr
>          Issue Type: Sub-task
>          Components: search
>    Affects Versions: 3.4
>            Reporter: Shawn Heisey
>            Priority: Minor
>         Attachments:,
> Implement an LFU (Least Frequently Used) cache as the first step towards a full ARC cache

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:!default.jspa
For more information on JIRA, see:


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message