store_heap_replacement.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 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"
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 */
48HeapKeyGen_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 */
93HeapKeyGen_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 */
119HeapKeyGen_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:205
MemObject * mem_obj
Definition: Store.h:221
time_t lastref
Definition: Store.h:225
uint64_t swap_file_sz
Definition: Store.h:230
uint16_t refcount
Definition: Store.h:231
#define debugs(SECTION, LEVEL, CONTENT)
Definition: Stream.h:193
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