[jboss-jira] [JBoss JIRA] Commented: (JBCACHE-971) Eviction policy based on adaptive replacement

[Paul Cowan (JIRA)]

    [ http://jira.jboss.com/jira/browse/JBCACHE-971?page=comments#action_12394445 ] 
            
Paul Cowan commented on JBCACHE-971:
------------------------------------

Hi all,

I have produced an AdaptiveReplacementPolicy implementation as part of a process of determining which eviciton policy best suits our needs, based on a real-life access data set. The code is rather horrible and would need a lot of cleanup to be able to be made available to the world at large (I'm tossing up whether I should contribute it to jboss or whether it should be a separate standalone open-sourced algorithm implementation with an Adapter to implement it as a jboss algorithm) but it seems to work well. On our dataset, it results in an ~10% decrease in cache misses compared to LFU. 

However, there's a more fundamental issue than code quality which prevents me from even attaching the very rough first-draft patch here -- the ARC algorithm is patented by IBM and hence there's a whole legal can-of-worms involved with doing so (I assume). There are a few patents which cover this area; US patent #6,996,676 is probably the main one I can find. This is the reason Postgres switched from ARC to 2Q (which is, as I understand it, patent-free) as a caching algorithm in version 8.0.2.

I am lodging a request with IBM to find out what's involved in obtaining a license to use this algorithm via their contact form at https://www.ibm.com/ibm/licensing/contact/patents.shtml -- I understand that they have a program to grant licenses to open source projects for certain patents -- and I will advise of their response. 

(The fact that this requires permission from IBM is one reason for possibly making this a non-jboss implementation, with a jboss 'bridge' -- then I might only need to obtain permission from IBM once and people who don't use jboss could still use that open-sourced implementation for other purposes. Fingers crossed they're interested)

In the meantime I also intend to look at implementing 2Q for JBoss Cache.

> Eviction policy based on adaptive replacement
> ---------------------------------------------
>
>                 Key: JBCACHE-971
>                 URL: http://jira.jboss.com/jira/browse/JBCACHE-971
>             Project: JBoss Cache
>          Issue Type: Feature Request
>      Security Level: Public(Everyone can see) 
>          Components: Eviction
>            Reporter: Manik Surtani
>         Assigned To: Mircea Markus
>             Fix For: 3.0.0
>
>   Original Estimate: 2 days
>  Remaining Estimate: 2 days
>
> Quote from Mircea Markus:
> There is an eviction policy algorithm more efficient than LRU (which I found quite popular) - Adaptive Replacement Policy. The basic idea is to not rely only on the time of last access to the node, but also on the number of time(frequency) a given node was accessed. Here it is a nice description of how it works: http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache. 

-- 
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators: http://jira.jboss.com/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira