src/repl/heap/store_heap_replacement.cc

   1 /*
   2  * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 /* DEBUG: section 20    Storage Manager Heap-based replacement */
  10
  11 /*
  12  * The code in this file is Copyrighted (C) 1999 by Hewlett Packard.
  13  *
  14  *
  15  * For a description of these cache replacement policies see --
  16  *  http://www.hpl.hp.com/techreports/1999/HPL-1999-69.html
  17  */
  18
  19 #include "squid.h"
  20 #include "heap.h"
  21 #include "MemObject.h"
  22 #include "SquidTime.h"
  23 #include "Store.h"
  24 #include "store_heap_replacement.h"
  25
  26 #include <cmath>
  27
  28 /*
  29  * Key generation function to implement the LFU-DA policy (Least
  30  * Frequently Used with Dynamic Aging).  Similar to classical LFU
  31  * but with aging to handle turnover of the popular document set.
  32  * Maximizes byte hit rate by keeping more currently popular objects
  33  * in cache regardless of size.  Achieves lower hit rate than GDS
  34  * because there are more large objects in cache (so less room for
  35  * smaller popular objects).
  36  *
  37  * This version implements a tie-breaker based upon recency
  38  * (e->lastref): for objects that have the same reference count
  39  * the most recent object wins (gets a higher key value).
  40  *
  41  * Note: this does not properly handle when the aging factor
  42  * gets so huge that the added value is outside of the
  43  * precision of double. However, Squid has to stay up
  44  * for quite a extended period of time (number of requests)
  45  * for this to become a problem. (estimation is 10^8 cache
  46  * turnarounds)
  47  */
  48 heap_key
  49 HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
  50 {
  51     StoreEntry *e = (StoreEntry *)entry;
  52     heap_key key;
  53     double tie;
  54
  55     if (e->lastref <= 0)
  56         tie = 0.0;
  57     else if (squid_curtime <= e->lastref)
  58         tie = 0.0;
  59     else
  60         tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0);
  61
  62     key = heap_age + (double) e->refcount - tie;
  63
  64     debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: " << e->getMD5Text() <<
  65            " refcnt=" << e->refcount << " lastref=" << e->lastref <<
  66            " heap_age=" << heap_age << " tie=" << tie << " -> " << key);
  67
  68     if (e->mem_obj)
  69         debugs(81, 3, "storeId=" << e->mem_obj->storeId());
  70
  71     return (double) key;
  72 }
  73
  74 /*
  75  * Key generation function to implement the GDS-Frequency policy.
  76  * Similar to Greedy Dual-Size Hits policy, but adds aging of
  77  * documents to prevent pollution.  Maximizes object hit rate by
  78  * keeping more small, popular objects in cache.  Achieves lower
  79  * byte hit rate than LFUDA because there are fewer large objects
  80  * in cache.
  81  *
  82  * This version implements a tie-breaker based upon recency
  83  * (e->lastref): for objects that have the same reference count
  84  * the most recent object wins (gets a higher key value).
  85  *
  86  * Note: this does not properly handle when the aging factor
  87  * gets so huge that the added value is outside of the
  88  * precision of double. However, Squid has to stay up
  89  * for quite a extended period of time (number of requests)
  90  * for this to become a problem. (estimation is 10^8 cache
  91  * turnarounds)
  92  */
  93 heap_key
  94 HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
  95 {
  96     StoreEntry *e = (StoreEntry *)entry;
  97     heap_key key;
  98     double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0;
  99     double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0;
 100     key = heap_age + ((double) e->refcount / size) - tie;
 101     debugs(81, 3, "HeapKeyGen_StoreEntry_GDSF: " << e->getMD5Text() <<
 102            " size=" << size << " refcnt=" << e->refcount << " lastref=" <<
 103            e->lastref << " heap_age=" << heap_age << " tie=" << tie <<
 104            " -> " << key);
 105
 106     if (e->mem_obj)
 107         debugs(81, 3, "storeId=" << e->mem_obj->storeId());
 108
 109     return key;
 110 }
 111
 112 /*
 113  * Key generation function to implement the LRU policy.  Normally
 114  * one would not do this with a heap -- use the linked list instead.
 115  * For testing and performance characterization it was useful.
 116  * Don't use it unless you are trying to compare performance among
 117  * heap-based replacement policies...
 118  */
 119 heap_key
 120 HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
 121 {
 122     StoreEntry *e = (StoreEntry *)entry;
 123     debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: " <<
 124            e->getMD5Text() << " heap_age=" << heap_age <<
 125            " lastref=" << (double) e->lastref  );
 126
 127     if (e->mem_obj)
 128         debugs(81, 3, "storeId=" << e->mem_obj->storeId());
 129
 130     return (heap_key) e->lastref;
 131 }
 132