src/repl/heap/store_heap_replacement.cc

   1
   2 /*
   3  * $Id$
   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 #include "Store.h"
  48 #include "MemObject.h"
  49 #include "SquidTime.h"
  50
  51 #if HAVE_MATH_H
  52 #include <math.h>
  53 #endif
  54
  55 /*
  56  * Key generation function to implement the LFU-DA policy (Least
  57  * Frequently Used with Dynamic Aging).  Similar to classical LFU
  58  * but with aging to handle turnover of the popular document set.
  59  * Maximizes byte hit rate by keeping more currently popular objects
  60  * in cache regardless of size.  Achieves lower hit rate than GDS
  61  * because there are more large objects in cache (so less room for
  62  * smaller popular objects).
  63  *
  64  * This version implements a tie-breaker based upon recency
  65  * (e->lastref): for objects that have the same reference count
  66  * the most recent object wins (gets a higher key value).
  67  *
  68  * Note: this does not properly handle when the aging factor
  69  * gets so huge that the added value is outside of the
  70  * precision of double. However, Squid has to stay up
  71  * for quite a extended period of time (number of requests)
  72  * for this to become a problem. (estimation is 10^8 cache
  73  * turnarounds)
  74  */
  75 heap_key
  76 HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
  77 {
  78     StoreEntry *e = (StoreEntry *)entry;
  79     heap_key key;
  80     double tie;
  81
  82     if (e->lastref <= 0)
  83         tie = 0.0;
  84     else if (squid_curtime <= e->lastref)
  85         tie = 0.0;
  86     else
  87         tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0);
  88
  89     key = heap_age + (double) e->refcount - tie;
  90
  91     debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: " << e->getMD5Text() <<
  92            " refcnt=" << e->refcount << " lastref=" << e->lastref <<
  93            " heap_age=" << heap_age << " tie=" << tie << " -> " << key);
  94
  95     if (e->mem_obj && e->mem_obj->url)
  96         debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: url=" << e->mem_obj->url);
  97
  98     return (double) key;
  99 }
 100
 101 /*
 102  * Key generation function to implement the GDS-Frequency policy.
 103  * Similar to Greedy Dual-Size Hits policy, but adds aging of
 104  * documents to prevent pollution.  Maximizes object hit rate by
 105  * keeping more small, popular objects in cache.  Achieves lower
 106  * byte hit rate than LFUDA because there are fewer large objects
 107  * in cache.
 108  *
 109  * This version implements a tie-breaker based upon recency
 110  * (e->lastref): for objects that have the same reference count
 111  * the most recent object wins (gets a higher key value).
 112  *
 113  * Note: this does not properly handle when the aging factor
 114  * gets so huge that the added value is outside of the
 115  * precision of double. However, Squid has to stay up
 116  * for quite a extended period of time (number of requests)
 117  * for this to become a problem. (estimation is 10^8 cache
 118  * turnarounds)
 119  */
 120 heap_key
 121 HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
 122 {
 123     StoreEntry *e = (StoreEntry *)entry;
 124     heap_key key;
 125     double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0;
 126     double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0;
 127     key = heap_age + ((double) e->refcount / size) - tie;
 128     debugs(81, 3, "HeapKeyGen_StoreEntry_GDSF: " << e->getMD5Text() <<
 129            " size=" << size << " refcnt=" << e->refcount << " lastref=" <<
 130            e->lastref << " heap_age=" << heap_age << " tie=" << tie <<
 131            " -> " << key);
 132
 133     if (e->mem_obj && e->mem_obj->url)
 134         debugs(81, 3, "HeapKeyGen_StoreEntry_GDSF: url=" << e->mem_obj->url);
 135
 136     return key;
 137 }
 138
 139 /*
 140  * Key generation function to implement the LRU policy.  Normally
 141  * one would not do this with a heap -- use the linked list instead.
 142  * For testing and performance characterization it was useful.
 143  * Don't use it unless you are trying to compare performance among
 144  * heap-based replacement policies...
 145  */
 146 heap_key
 147 HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
 148 {
 149     StoreEntry *e = (StoreEntry *)entry;
 150     debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: " <<
 151            e->getMD5Text() << " heap_age=" << heap_age <<
 152            " lastref=" << (double) e->lastref  );
 153
 154     if (e->mem_obj && e->mem_obj->url)
 155         debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: url=" << e->mem_obj->url);
 156
 157     return (heap_key) e->lastref;
 158 }