src/repl/heap/store_heap_replacement.cc

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