src/repl/heap/store_heap_replacement.cc

   1
   2 /*
   3  * $Id: store_heap_replacement.cc,v 1.6 2001/02/07 18:56:56 hno Exp $
   4  *
   5  * DEBUG: section 20    Storage Manager Heap-based replacement
   6  * AUTHOR: John Dilley
   7  *
   8  * SQUID Web Proxy Cache          http://www.squid-cache.org/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from
  12  *  the Internet community; see the CONTRIBUTORS file for full
  13  *  details.   Many organizations have provided support for Squid's
  14  *  development; see the SPONSORS file for full details.  Squid is
  15  *  Copyrighted (C) 2001 by the Regents of the University of
  16  *  California; see the COPYRIGHT file for full details.  Squid
  17  *  incorporates software developed and/or copyrighted by other
  18  *  sources; see the CREDITS file for full details.
  19  *
  20  *  This program is free software; you can redistribute it and/or modify
  21  *  it under the terms of the GNU General Public License as published by
  22  *  the Free Software Foundation; either version 2 of the License, or
  23  *  (at your option) any later version.
  24  *
  25  *  This program is distributed in the hope that it will be useful,
  26  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28  *  GNU General Public License for more details.
  29  *
  30  *  You should have received a copy of the GNU General Public License
  31  *  along with this program; if not, write to the Free Software
  32  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA.
  33  *
  34  */
  35
  36 /*
  37  * The code in this file is Copyrighted (C) 1999 by Hewlett Packard.
  38  *
  39  *
  40  * For a description of these cache replacement policies see --
  41  *  http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
  42  */
  43
  44 #include "squid.h"
  45 #include "heap.h"
  46 #include "store_heap_replacement.h"
  47
  48 /*
  49  * Key generation function to implement the LFU-DA policy (Least
  50  * Frequently Used with Dynamic Aging).  Similar to classical LFU
  51  * but with aging to handle turnover of the popular document set.
  52  * Maximizes byte hit rate by keeping more currently popular objects
  53  * in cache regardless of size.  Achieves lower hit rate than GDS
  54  * because there are more large objects in cache (so less room for
  55  * smaller popular objects).
  56  *
  57  * This version implements a tie-breaker based upon recency
  58  * (e->lastref): for objects that have the same reference count
  59  * the most recent object wins (gets a higher key value).
  60  *
  61  * Note: this does not properly handle when the aging factor
  62  * gets so huge that the added value is outside of the
  63  * precision of double. However, Squid has to stay up
  64  * for quite a extended period of time (number of requests)
  65  * for this to become a problem. (estimation is 10^8 cache
  66  * turnarounds)
  67  */
  68 heap_key
  69 HeapKeyGen_StoreEntry_LFUDA(void *entry, double age)
  70 {
  71     StoreEntry *e = entry;
  72     heap_key key;
  73     double tie;
  74     if (e->lastref <= 0)
  75         tie = 0.0;
  76     else if (squid_curtime <= e->lastref)
  77         tie = 0.0;
  78     else
  79         tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0);
  80     key = age + (double) e->refcount - tie;
  81     debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: %s refcnt=%ld lastref=%ld age=%f tie=%f -> %f\n",
  82         storeKeyText(e->hash.key), e->refcount, e->lastref, age, tie, key);
  83     if (e->mem_obj && e->mem_obj->url)
  84         debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: url=%s\n",
  85             e->mem_obj->url);
  86     return (double) key;
  87 }
  88
  89
  90 /*
  91  * Key generation function to implement the GDS-Frequency policy.
  92  * Similar to Greedy Dual-Size Hits policy, but adds aging of
  93  * documents to prevent pollution.  Maximizes object hit rate by
  94  * keeping more small, popular objects in cache.  Achieves lower
  95  * byte hit rate than LFUDA because there are fewer large objects
  96  * in cache.
  97  *
  98  * This version implements a tie-breaker based upon recency
  99  * (e->lastref): for objects that have the same reference count
 100  * the most recent object wins (gets a higher key value).
 101  *
 102  * Note: this does not properly handle when the aging factor
 103  * gets so huge that the added value is outside of the
 104  * precision of double. However, Squid has to stay up
 105  * for quite a extended period of time (number of requests)
 106  * for this to become a problem. (estimation is 10^8 cache
 107  * turnarounds)
 108  */
 109 heap_key
 110 HeapKeyGen_StoreEntry_GDSF(void *entry, double age)
 111 {
 112     StoreEntry *e = entry;
 113     heap_key key;
 114     double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0;
 115     double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0;
 116     key = age + ((double) e->refcount / size) - tie;
 117     debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: %s size=%f refcnt=%ld lastref=%ld age=%f tie=%f -> %f\n",
 118         storeKeyText(e->hash.key), size, e->refcount, e->lastref, age, tie, key);
 119     if (e->mem_obj && e->mem_obj->url)
 120         debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: url=%s\n",
 121             e->mem_obj->url);
 122     return key;
 123 }
 124
 125 /*
 126  * Key generation function to implement the LRU policy.  Normally
 127  * one would not do this with a heap -- use the linked list instead.
 128  * For testing and performance characterization it was useful.
 129  * Don't use it unless you are trying to compare performance among
 130  * heap-based replacement policies...
 131  */
 132 heap_key
 133 HeapKeyGen_StoreEntry_LRU(void *entry, double age)
 134 {
 135     StoreEntry *e = entry;
 136     debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: %s age=%f lastref=%f\n",
 137         storeKeyText(e->hash.key), age, (double) e->lastref);
 138     if (e->mem_obj && e->mem_obj->url)
 139         debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: url=%s\n",
 140             e->mem_obj->url);
 141     return (heap_key) e->lastref;
 142 }