src/repl/heap/store_heap_replacement.cc

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