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