Heap-based replacement policies

From: Osama Saleh <osaleh@dont-contact.us>
Date: Tue, 13 Jun 2006 06:11:34 -0700

('binary' encoding is not supported, stored as-is) Hello Squid Gurus,

I am implementing a new algorithm for caching *HUGE* multimedia files based
on segmentation and partial caching/eviction. My algorithm is heap-based and
uses a combination of object size, # of bytes sent from this object and
other metrics to decide which object to evict next.

I have the algorithm implemented already but I want to integrate it into
squid. I read on the squid README files and website that GDSF (Greedy Dual
Size Frequency) and LFUA (LFU with Aging) are implemented in squid using a
heap data structure. I went through the technical report from HP:

http://www.hpl.hp.com/techreports/1999/HPL-1999-69.pdf

and they describe how they implemented GDSF and LFU in squid by modifying
dlinkAdd() and dlinkDelete() so that it points to a heap_node rather than a
link_node (LRU node). The problem is, even though I have gone through their
heap implementation (heap.c in lib), I cannot find the implementation for
GDSF, for example. I need to see how they implemented GDSF and trace the
places where they needed to change method calls, add code, ...etc., so I can
implement my new policy. I grep-ed for methods in the heap which add to the
heap's add and remove methods for GDSF or LFU , but never found anything,
even though the squid README files say they are implemented.

Where can I find implementation for heap based policies (what files)? Or if
it is not implemented, what files should be I closely examining to
understand what I have to do?

Thank you very much.
Received on Tue Jun 13 2006 - 08:13:45 MDT