]>
Commit | Line | Data |
---|---|---|
6a566b9c | 1 | |
2 | /* | |
f0debecb | 3 | * $Id: store_heap_replacement.cc,v 1.4 2001/01/02 00:11:55 wessels Exp $ |
6a566b9c | 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 | */ | |
f0debecb | 67 | heap_key |
be1ed2a4 | 68 | HeapKeyGen_StoreEntry_LFUDA(void *entry, double age) |
6a566b9c | 69 | { |
70 | StoreEntry *e = entry; | |
71 | heap_key key; | |
72 | double tie; | |
73 | if (e->lastref <= 0) | |
74 | tie = 0.0; | |
75 | else if (squid_curtime <= e->lastref) | |
76 | tie = 0.0; | |
77 | else | |
78 | tie = 1.0 - exp((double) (e->lastref - squid_curtime) / 86400.0); | |
79 | key = age + (double) e->refcount - tie; | |
80 | debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: %s refcnt=%ld lastref=%ld age=%f tie=%f -> %f\n", | |
be1ed2a4 | 81 | storeKeyText(e->hash.key), e->refcount, e->lastref, age, tie, key); |
6a566b9c | 82 | if (e->mem_obj && e->mem_obj->url) |
83 | debug(81, 3) ("HeapKeyGen_StoreEntry_LFUDA: url=%s\n", | |
84 | e->mem_obj->url); | |
be1ed2a4 | 85 | return (double) key; |
6a566b9c | 86 | } |
87 | ||
88 | ||
89 | /* | |
90 | * Key generation function to implement the GDS-Frequency policy. | |
91 | * Similar to Greedy Dual-Size Hits policy, but adds aging of | |
92 | * documents to prevent pollution. Maximizes object hit rate by | |
93 | * keeping more small, popular objects in cache. Achieves lower | |
94 | * byte hit rate than LFUDA because there are fewer large objects | |
95 | * in cache. | |
96 | * | |
97 | * This version implements a tie-breaker based upon recency | |
98 | * (e->lastref): for objects that have the same reference count | |
99 | * the most recent object wins (gets a higher key value). | |
100 | * | |
101 | * Note: this does not properly handle when the aging factor | |
102 | * gets so huge that the added value is outside of the | |
103 | * precision of double. However, Squid has to stay up | |
104 | * for quite a extended period of time (number of requests) | |
105 | * for this to become a problem. (estimation is 10^8 cache | |
106 | * turnarounds) | |
107 | */ | |
f0debecb | 108 | heap_key |
be1ed2a4 | 109 | HeapKeyGen_StoreEntry_GDSF(void *entry, double age) |
6a566b9c | 110 | { |
111 | StoreEntry *e = entry; | |
112 | heap_key key; | |
113 | double size = e->swap_file_sz ? (double) e->swap_file_sz : 1.0; | |
114 | double tie = (e->lastref > 1) ? (1.0 / e->lastref) : 1.0; | |
115 | key = age + ((double) e->refcount / size) - tie; | |
116 | debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: %s size=%f refcnt=%ld lastref=%ld age=%f tie=%f -> %f\n", | |
be1ed2a4 | 117 | storeKeyText(e->hash.key), size, e->refcount, e->lastref, age, tie, key); |
6a566b9c | 118 | if (e->mem_obj && e->mem_obj->url) |
119 | debug(81, 3) ("HeapKeyGen_StoreEntry_GDSF: url=%s\n", | |
120 | e->mem_obj->url); | |
121 | return key; | |
122 | } | |
123 | ||
124 | /* | |
125 | * Key generation function to implement the LRU policy. Normally | |
126 | * one would not do this with a heap -- use the linked list instead. | |
127 | * For testing and performance characterization it was useful. | |
128 | * Don't use it unless you are trying to compare performance among | |
129 | * heap-based replacement policies... | |
130 | */ | |
f0debecb | 131 | heap_key |
be1ed2a4 | 132 | HeapKeyGen_StoreEntry_LRU(void *entry, double age) |
6a566b9c | 133 | { |
134 | StoreEntry *e = entry; | |
135 | debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: %s age=%f lastref=%f\n", | |
be1ed2a4 | 136 | storeKeyText(e->hash.key), age, (double) e->lastref); |
6a566b9c | 137 | if (e->mem_obj && e->mem_obj->url) |
138 | debug(81, 3) ("HeapKeyGen_StoreEntry_LRU: url=%s\n", | |
139 | e->mem_obj->url); | |
140 | return (heap_key) e->lastref; | |
141 | } |