]>
Commit | Line | Data |
---|---|---|
f740a279 | 1 | |
afd88fbe | 2 | /* |
528b2c61 | 3 | * $Id: carp.cc,v 1.22 2003/01/23 00:37:17 robertc Exp $ |
afd88fbe | 4 | * |
67f46679 | 5 | * DEBUG: section 39 Cache Array Routing Protocol |
b3995439 | 6 | * AUTHOR: Henrik Nordstrom |
7 | * BASED ON: carp.c by Eric Stern and draft-vinod-carp-v1-03.txt | |
afd88fbe | 8 | * |
2b6662ba | 9 | * SQUID Web Proxy Cache http://www.squid-cache.org/ |
e25c139f | 10 | * ---------------------------------------------------------- |
11 | * | |
2b6662ba | 12 | * Squid is the result of efforts by numerous individuals from |
13 | * the Internet community; see the CONTRIBUTORS file for full | |
14 | * details. Many organizations have provided support for Squid's | |
15 | * development; see the SPONSORS file for full details. Squid is | |
16 | * Copyrighted (C) 2001 by the Regents of the University of | |
17 | * California; see the COPYRIGHT file for full details. Squid | |
18 | * incorporates software developed and/or copyrighted by other | |
19 | * sources; see the CREDITS file for full details. | |
e25c139f | 20 | * |
afd88fbe | 21 | * This program is free software; you can redistribute it and/or modify |
22 | * it under the terms of the GNU General Public License as published by | |
23 | * the Free Software Foundation; either version 2 of the License, or | |
24 | * (at your option) any later version. | |
e25c139f | 25 | * |
afd88fbe | 26 | * This program is distributed in the hope that it will be useful, |
27 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
28 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
29 | * GNU General Public License for more details. | |
e25c139f | 30 | * |
afd88fbe | 31 | * You should have received a copy of the GNU General Public License |
32 | * along with this program; if not, write to the Free Software | |
cbdec147 | 33 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. |
e25c139f | 34 | * |
0cdcddb9 | 35 | */ |
afd88fbe | 36 | |
37 | #include "squid.h" | |
e6ccf245 | 38 | #include "Store.h" |
afd88fbe | 39 | |
40 | #if USE_CARP | |
41 | ||
b3995439 | 42 | #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) |
43 | ||
44 | static int n_carp_peers = 0; | |
45 | static peer **carp_peers = NULL; | |
8ee9b49f | 46 | static OBJH carpCachemgr; |
47 | ||
b3995439 | 48 | static int |
49 | peerSortWeight(const void *a, const void *b) | |
50 | { | |
ff83713b | 51 | const peer *const *p1 = (const peer *const *)a; |
52 | const peer *const *p2 = (const peer *const *)b; | |
b3995439 | 53 | return (*p1)->weight - (*p2)->weight; |
54 | } | |
55 | ||
afd88fbe | 56 | void |
57 | carpInit(void) | |
58 | { | |
b3995439 | 59 | int W = 0; |
60 | int K; | |
afd88fbe | 61 | int k; |
b3995439 | 62 | double P_last, X_last, Xn; |
afd88fbe | 63 | peer *p; |
b3995439 | 64 | peer **P; |
65 | char *t; | |
66 | /* Clean up */ | |
67 | for (k = 0; k < n_carp_peers; k++) { | |
fa80a8ef | 68 | cbdataReferenceDone(carp_peers[k]); |
b3995439 | 69 | } |
70 | safe_free(carp_peers); | |
71 | n_carp_peers = 0; | |
72 | /* find out which peers we have */ | |
afd88fbe | 73 | for (p = Config.peers; p; p = p->next) { |
b3995439 | 74 | if (!p->options.carp) |
75 | continue; | |
76 | assert(p->type == PEER_PARENT); | |
77 | if (p->weight == 0) | |
78 | continue; | |
79 | n_carp_peers++; | |
80 | W += p->weight; | |
afd88fbe | 81 | } |
b3995439 | 82 | if (n_carp_peers == 0) |
afd88fbe | 83 | return; |
ff83713b | 84 | carp_peers = (peer **)xcalloc(n_carp_peers, sizeof(*carp_peers)); |
b3995439 | 85 | /* Build a list of the found peers and calculate hashes and load factors */ |
86 | for (P = carp_peers, p = Config.peers; p; p = p->next) { | |
87 | if (!p->options.carp) | |
88 | continue; | |
89 | if (p->weight == 0) | |
90 | continue; | |
91 | /* calculate this peers hash */ | |
92 | p->carp.hash = 0; | |
93 | for (t = p->host; *t != 0; t++) | |
94 | p->carp.hash += ROTATE_LEFT(p->carp.hash, 19) + (unsigned int) *t; | |
95 | p->carp.hash += p->carp.hash * 0x62531965; | |
96 | p->carp.hash = ROTATE_LEFT(p->carp.hash, 21); | |
97 | /* and load factor */ | |
98 | p->carp.load_factor = ((double) p->weight) / (double) W; | |
99 | if (floor(p->carp.load_factor * 1000.0) == 0.0) | |
100 | p->carp.load_factor = 0.0; | |
101 | /* add it to our list of peers */ | |
fa80a8ef | 102 | *P++ = cbdataReference(p); |
67766c17 | 103 | } |
b3995439 | 104 | /* Sort our list on weight */ |
105 | qsort(carp_peers, n_carp_peers, sizeof(*carp_peers), peerSortWeight); | |
106 | /* Calculate the load factor multipliers X_k | |
107 | * | |
108 | * X_1 = pow ((K*p_1), (1/K)) | |
109 | * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) | |
110 | * X_k += pow ((X_{k-1}, {K-k+1}) | |
111 | * X_k = pow (X_k, {1/(K-k+1)}) | |
112 | * simplified to have X_1 part of the loop | |
afd88fbe | 113 | */ |
b3995439 | 114 | K = n_carp_peers; |
115 | P_last = 0.0; /* Empty P_0 */ | |
116 | Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ | |
117 | X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ | |
118 | for (k = 1; k <= K; k++) { | |
119 | double Kk1 = (double) (K - k + 1); | |
120 | p = carp_peers[k - 1]; | |
121 | p->carp.load_multiplier = (Kk1 * (p->carp.load_factor - P_last)) / Xn; | |
122 | p->carp.load_multiplier += pow(X_last, Kk1); | |
123 | p->carp.load_multiplier = pow(p->carp.load_multiplier, 1.0 / Kk1); | |
67766c17 | 124 | Xn *= p->carp.load_multiplier; |
125 | X_last = p->carp.load_multiplier; | |
67766c17 | 126 | P_last = p->carp.load_factor; |
afd88fbe | 127 | } |
8ee9b49f | 128 | cachemgrRegister("carp", "CARP information", carpCachemgr, 0, 1); |
afd88fbe | 129 | } |
130 | ||
131 | peer * | |
132 | carpSelectParent(request_t * request) | |
133 | { | |
b3995439 | 134 | int k; |
afd88fbe | 135 | const char *c; |
136 | peer *p = NULL; | |
137 | peer *tp; | |
b3995439 | 138 | unsigned int user_hash = 0; |
139 | unsigned int combined_hash; | |
140 | double score; | |
141 | double high_score = 0; | |
ecefb559 | 142 | const char *key = NULL; |
b3995439 | 143 | |
144 | if (n_carp_peers == 0) | |
145 | return NULL; | |
146 | ||
358a75e0 | 147 | key = urlCanonical(request); |
b3995439 | 148 | |
149 | /* calculate hash key */ | |
150 | debug(39, 2) ("carpSelectParent: Calculating hash for %s\n", key); | |
151 | for (c = key; *c != 0; c++) | |
152 | user_hash += ROTATE_LEFT(user_hash, 19) + *c; | |
afd88fbe | 153 | /* select peer */ |
b3995439 | 154 | for (k = 0; k < n_carp_peers; k++) { |
155 | tp = carp_peers[k]; | |
156 | combined_hash = (user_hash ^ tp->carp.hash); | |
afd88fbe | 157 | combined_hash += combined_hash * 0x62531965; |
d20b1cd0 | 158 | combined_hash = ROTATE_LEFT(combined_hash, 21); |
b3995439 | 159 | score = combined_hash * tp->carp.load_multiplier; |
160 | debug(39, 3) ("carpSelectParent: %s combined_hash %u score %.0f\n", | |
161 | tp->host, combined_hash, score); | |
162 | if ((score > high_score) && peerHTTPOkay(tp, request)) { | |
afd88fbe | 163 | p = tp; |
b3995439 | 164 | high_score = score; |
afd88fbe | 165 | } |
166 | } | |
167 | if (p) | |
b3995439 | 168 | debug(39, 2) ("carpSelectParent: selected %s\n", p->host); |
afd88fbe | 169 | return p; |
170 | } | |
8ee9b49f | 171 | |
172 | static void | |
173 | carpCachemgr(StoreEntry * sentry) | |
174 | { | |
175 | peer *p; | |
176 | int sumfetches = 0; | |
177 | storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", | |
178 | "Hostname", | |
179 | "Hash", | |
180 | "Multiplier", | |
181 | "Factor", | |
182 | "Actual"); | |
183 | for (p = Config.peers; p; p = p->next) | |
184 | sumfetches += p->stats.fetches; | |
185 | for (p = Config.peers; p; p = p->next) { | |
186 | storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", | |
187 | p->host, p->carp.hash, | |
188 | p->carp.load_multiplier, | |
189 | p->carp.load_factor, | |
190 | sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); | |
191 | } | |
8ee9b49f | 192 | } |
193 | ||
afd88fbe | 194 | #endif |