store_heap_replacement.cc
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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  */
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  */
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 
double heap_key
Definition: heap.h:33
heap_key HeapKeyGen_StoreEntry_LFUDA(void *entry, double heap_age)
time_t squid_curtime
Definition: stub_time.cc:17
heap_key HeapKeyGen_StoreEntry_GDSF(void *entry, double heap_age)
uint64_t swap_file_sz
Definition: Store.h:171
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Debug.h:123
const char * storeId() const
Definition: MemObject.cc:54
heap_key HeapKeyGen_StoreEntry_LRU(void *entry, double heap_age)
MemObject * mem_obj
Definition: Store.h:162
uint16_t refcount
Definition: Store.h:172
virtual const char * getMD5Text() const
Definition: store.cc:181
void const cache_key * key
time_t lastref
Definition: Store.h:166
int size
Definition: ModDevPoll.cc:77

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors