src/repl/heap/store_heap_replacement.cc

   1
   2 /*
   3  * $Id: store_heap_replacement.cc,v 1.2 2000/11/03 16:38:46 wessels Exp $
   4  *
   5  * DEBUG: section 20    Storage Manager Heap-based replacement
   6  * AUTHOR: John Dilley
   7  *
   8  * SQUID Internet Object Cache  http://squid.nlanr.net/Squid/
   9  * ----------------------------------------------------------
  10  *
  11  *  Squid is the result of efforts by numerous individuals from the
  12  *  Internet community.  Development is led by Duane Wessels of the
  13  *  National Laboratory for Applied Network Research and funded by the
  14  *  National Science Foundation.  Squid is Copyrighted (C) 1998 by
  15  *  the Regents of the University of California.  Please see the
  16  *  COPYRIGHT file for full details.  Squid incorporates software
  17  *  developed and/or copyrighted by other sources.  Please see the
  18  *  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
  47 /*
  48  * Key generation function to implement the LFU-DA policy (Least
  49  * Frequently Used with Dynamic Aging).  Similar to classical LFU
  50  * but with aging to handle turnover of the popular document set.
  51  * Maximizes byte hit rate by keeping more currently popular objects
  52  * in cache regardless of size.  Achieves lower hit rate than GDS
  53  * because there are more large objects in cache (so less room for
  54  * smaller popular objects).
  55  *
  56  * This version implements a tie-breaker based upon recency
  57  * (e->lastref): for objects that have the same reference count
  58  * the most recent object wins (gets a higher key value).
  59  *
  60  * Note: this does not properly handle when the aging factor
  61  * gets so huge that the added value is outside of the
  62  * precision of double. However, Squid has to stay up
  63  * for quite a extended period of time (number of requests)
  64  * for this to become a problem. (estimation is 10^8 cache
  65  * turnarounds)
  66  */
  67 heap_key HeapKeyGen_StoreEntry_LFUDA(void *entry, double age)
  68 {
  69     StoreEntry *e = entry;
  70     heap_key key;
  71     double tie;
  72     if (e->lastref <= 0)
  73         tie = 0.0;
  74     else if (squid_curtime <= e->lastref)
  75         tie = 0.0;
  76     else
  77         tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0);
  78     key = age + (double) e->refcount - tie;
  79     debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: %s refcnt=%ld lastref=%ld age=%f tie=%f -> %f\n",
  80             storeKeyText(e->hash.key), e->refcount, e->lastref, age, tie, key);
  81     if (e->mem_obj && e->mem_obj->url)
  82         debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: url=%s\n",
  83             e->mem_obj->url);
  84     return (double)key;
  85 }
  86
  87
  88 /*
  89  * Key generation function to implement the GDS-Frequency policy.
  90  * Similar to Greedy Dual-Size Hits policy, but adds aging of
  91  * documents to prevent pollution.  Maximizes object hit rate by
  92  * keeping more small, popular objects in cache.  Achieves lower
  93  * byte hit rate than LFUDA because there are fewer large objects
  94  * in cache.
  95  *
  96  * This version implements a tie-breaker based upon recency
  97  * (e->lastref): for objects that have the same reference count
  98  * the most recent object wins (gets a higher key value).
  99  *
 100  * Note: this does not properly handle when the aging factor
 101  * gets so huge that the added value is outside of the
 102  * precision of double. However, Squid has to stay up
 103  * for quite a extended period of time (number of requests)
 104  * for this to become a problem. (estimation is 10^8 cache
 105  * turnarounds)
 106  */
 107 heap_key HeapKeyGen_StoreEntry_GDSF(void *entry, double age)
 108 {
 109     StoreEntry *e = entry;
 110     heap_key key;
 111     double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0;
 112     double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0;
 113     key = age + ((double) e->refcount / size) - tie;
 114     debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: %s size=%f refcnt=%ld lastref=%ld age=%f tie=%f -> %f\n",
 115             storeKeyText(e->hash.key), size, e->refcount, e->lastref, age, tie, key);
 116     if (e->mem_obj && e->mem_obj->url)
 117         debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: url=%s\n",
 118             e->mem_obj->url);
 119     return key;
 120 }
 121
 122 /*
 123  * Key generation function to implement the LRU policy.  Normally
 124  * one would not do this with a heap -- use the linked list instead.
 125  * For testing and performance characterization it was useful.
 126  * Don't use it unless you are trying to compare performance among
 127  * heap-based replacement policies...
 128  */
 129 heap_key HeapKeyGen_StoreEntry_LRU(void *entry, double age)
 130 {
 131     StoreEntry *e = entry;
 132     debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: %s age=%f lastref=%f\n",
 133             storeKeyText(e->hash.key), age, (double)e->lastref);
 134     if (e->mem_obj && e->mem_obj->url)
 135         debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: url=%s\n",
 136             e->mem_obj->url);
 137     return (heap_key) e->lastref;
 138 }