store_heap_replacement.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2022 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 "Store.h"
23 #include "store_heap_replacement.h"
24 
25 #include <cmath>
26 
27 /*
28  * Key generation function to implement the LFU-DA policy (Least
29  * Frequently Used with Dynamic Aging). Similar to classical LFU
30  * but with aging to handle turnover of the popular document set.
31  * Maximizes byte hit rate by keeping more currently popular objects
32  * in cache regardless of size. Achieves lower hit rate than GDS
33  * because there are more large objects in cache (so less room for
34  * smaller popular objects).
35  *
36  * This version implements a tie-breaker based upon recency
37  * (e->lastref): for objects that have the same reference count
38  * the most recent object wins (gets a higher key value).
39  *
40  * Note: this does not properly handle when the aging factor
41  * gets so huge that the added value is outside of the
42  * precision of double. However, Squid has to stay up
43  * for quite a extended period of time (number of requests)
44  * for this to become a problem. (estimation is 10^8 cache
45  * turnarounds)
46  */
48 HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
49 {
50  StoreEntry *e = (StoreEntry *)entry;
51  heap_key key;
52  double tie;
53 
54  if (e->lastref <= 0)
55  tie = 0.0;
56  else if (squid_curtime <= e->lastref)
57  tie = 0.0;
58  else
59  tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0);
60 
61  key = heap_age + (double) e->refcount - tie;
62 
63  debugs(81, 3, "HeapKeyGen_StoreEntry_LFUDA: " << e->getMD5Text() <<
64  " refcnt=" << e->refcount << " lastref=" << e->lastref <<
65  " heap_age=" << heap_age << " tie=" << tie << " -> " << key);
66 
67  if (e->mem_obj)
68  debugs(81, 3, "storeId=" << e->mem_obj->storeId());
69 
70  return (double) key;
71 }
72 
73 /*
74  * Key generation function to implement the GDS-Frequency policy.
75  * Similar to Greedy Dual-Size Hits policy, but adds aging of
76  * documents to prevent pollution. Maximizes object hit rate by
77  * keeping more small, popular objects in cache. Achieves lower
78  * byte hit rate than LFUDA because there are fewer large objects
79  * in cache.
80  *
81  * This version implements a tie-breaker based upon recency
82  * (e->lastref): for objects that have the same reference count
83  * the most recent object wins (gets a higher key value).
84  *
85  * Note: this does not properly handle when the aging factor
86  * gets so huge that the added value is outside of the
87  * precision of double. However, Squid has to stay up
88  * for quite a extended period of time (number of requests)
89  * for this to become a problem. (estimation is 10^8 cache
90  * turnarounds)
91  */
93 HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
94 {
95  StoreEntry *e = (StoreEntry *)entry;
96  heap_key key;
97  double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0;
98  double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0;
99  key = heap_age + ((double) e->refcount / size) - tie;
100  debugs(81, 3, "HeapKeyGen_StoreEntry_GDSF: " << e->getMD5Text() <<
101  " size=" << size << " refcnt=" << e->refcount << " lastref=" <<
102  e->lastref << " heap_age=" << heap_age << " tie=" << tie <<
103  " -> " << key);
104 
105  if (e->mem_obj)
106  debugs(81, 3, "storeId=" << e->mem_obj->storeId());
107 
108  return key;
109 }
110 
111 /*
112  * Key generation function to implement the LRU policy. Normally
113  * one would not do this with a heap -- use the linked list instead.
114  * For testing and performance characterization it was useful.
115  * Don't use it unless you are trying to compare performance among
116  * heap-based replacement policies...
117  */
118 heap_key
119 HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
120 {
121  StoreEntry *e = (StoreEntry *)entry;
122  debugs(81, 3, "HeapKeyGen_StoreEntry_LRU: " <<
123  e->getMD5Text() << " heap_age=" << heap_age <<
124  " lastref=" << (double) e->lastref );
125 
126  if (e->mem_obj)
127  debugs(81, 3, "storeId=" << e->mem_obj->storeId());
128 
129  return (heap_key) e->lastref;
130 }
131 
int size
Definition: ModDevPoll.cc:75
time_t squid_curtime
Definition: stub_libtime.cc:20
const char * storeId() const
Definition: MemObject.cc:53
const char * getMD5Text() const
Definition: store.cc:204
MemObject * mem_obj
Definition: Store.h:219
time_t lastref
Definition: Store.h:223
uint64_t swap_file_sz
Definition: Store.h:228
uint16_t refcount
Definition: Store.h:229
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:196
double heap_key
Definition: heap.h:33
heap_key HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
heap_key HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
heap_key HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
void EVH void double
Definition: stub_event.cc:16

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors