File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\hudson\util\ConsistentHash.java.html

1 /*
2 * The MIT License
3 *
4 * Copyright (c) 2004-2009, Sun Microsystems, Inc.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to deal
8 * in the Software without restriction, including without limitation the rights
9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
22 * THE SOFTWARE.
23 */
24 package hudson.util;
25
26 import com.trilead.ssh2.crypto.digest.MD5;
27
28 import java.util.Arrays;
29 import java.util.HashMap;
30 import java.util.Map;
31 import java.util.Collection;
32 import java.util.Iterator;
33 import java.util.NoSuchElementException;
34
35 import hudson.util.Iterators.DuplicateFilterIterator;
36
37 /**
38 * Consistent hash.
39 *
40 * <p>
41 * This implementation is concurrency safe; additions and removals are serialized, but look up
42 * can be performed concurrently even when modifications is in progress.
43 *
44 * <p>
45 * Since typical hash functions we use in {@link Object#hashCode()} isn't random enough to
46 * evenly populate the 2^32 ring space, we only ask the user to give us
47 * <a href="http://en.wikipedia.org/wiki/Injective_function">an injective function</a> to a string,
48 * and then we use MD5 to create random enough distribution.
49 *
50 * <p>
51 * This consistent hash implementaiton is consistent both to the addition/removal of Ts, as well
52 * as increase/decrease of the replicas.
53 *
54 * <p>
55 * See http://en.wikipedia.org/wiki/Consistent_hashing for references, and
56 * http://weblogs.java.net/blog/tomwhite/archive/2007/11/consistent_hash.html is probably a reasonable depiction.
57 * If we trust his experiments, creating 100 replicas will reduce the stddev to 10% of the mean for 10 nodes.
58 *
59 * @author Kohsuke Kawaguchi
60 * @since 1.302
61 */
62 public class ConsistentHash<T> {
63 /**
64 * All the items in the hash, to their replication factors.
65 */
66 private final Map<T,Point[]> items = new HashMap<T,Point[]>();
67
68 private final int defaultReplication;
69 private final Hash<T> hash;
70
71 /**
72 * Used for remembering the computed MD5 hash, since it's bit expensive to do it all over again.
73 */
74 private static final class Point implements Comparable<Point> {
75 final int hash;
76 final Object item;
77
78 private Point(int hash, Object item) {
79 this.hash = hash;
80 this.item = item;
81 }
82
83 public int compareTo(Point that) {
84 if(this.hash<that.hash) return -1;
85 if(this.hash==that.hash) return 0;
86 return 1;
87 }
88 }
89
90 /**
91 * Table that gets atomically replaced for concurrency safe operation.
92 */
93 private volatile Table table;
94
95 /**
96 * Immutable consistent hash table.
97 */
98 private final class Table {
99 private final int[] hash;
100 private final Object[] owner; // really T[]
101
102 private Table() {
103 // merge all points from all nodes and sort them into a single array
104 Point[] allPoints = new Point[countAllPoints()];
105 int p=0;
106 for (Point[] v : items.values()) {
107 System.arraycopy(v,0,allPoints,p,v.length);
108 p+=v.length;
109 }
110 Arrays.sort(allPoints);
111
112 hash = new int[allPoints.length];
113 owner = new Object[allPoints.length];
114
115 for (int i=0; i<allPoints.length; i++) {
116 Point pt = allPoints[i];
117 hash[i]=pt.hash;
118 owner[i]=pt.item;
119 }
120 }
121
122 T lookup(int queryPoint) {
123 int i = index(queryPoint);
124 if(i<0) return null;
125 return (T)owner[i];
126 }
127
128 /**
129 * Returns a consistent stream of nodes starting the given query point.
130 *
131 * <p>
132 * This is a permutation of all the nodes, where nodes with more replicas
133 * are more likely to show up early on.
134 */
135 Iterator<T> list(int queryPoint) {
136 final int start = index(queryPoint);
137 return new DuplicateFilterIterator<T>(new Iterator<T>() {
138 int pos=0;
139 public boolean hasNext() {
140 return pos<owner.length;
141 }
142
143 public T next() {
144 if(!hasNext()) throw new NoSuchElementException();
145 return (T)owner[(start+(pos++))%owner.length];
146 }
147
148 public void remove() {
149 throw new UnsupportedOperationException();
150 }
151 });
152 }
153
154 private int index(int queryPoint) {
155 int idx = Arrays.binarySearch(hash, queryPoint);
156 if(idx<0) {
157 idx = -idx-1; // idx is now 'insertion point'
158 if(hash.length==0) return -1;
159 idx %= hash.length; // make it a circle
160 }
161 return idx;
162 }
163 }
164
165 /**
166 * Hashes an object to some value.
167 *
168 * <p>
169 * By default, {@link ConsistentHash} uses {@link Object#toString()} on 'T' to
170 * obtain the hash, but that behavior can be changed by providing
171 * a {@link Hash} implementation.
172 *
173 * <p>
174 * This hash function need not produce a very uniform distribution, as the
175 * output is rehashed with MD5. But it does need to make sure it doesn't
176 * produce the same value for two different 'T's (and that's why this returns
177 * String, not the usual int.)
178 */
179 public interface Hash<T> {
180 /**
181 * @param t
182 * The object to be hashed. Never null.
183 * @return
184 * The hash value.
185 */
186 String hash(T t);
187 }
188
189 private static final Hash DEFAULT_HASH = new Hash() {
190 public String hash(Object o) {
191 return o.toString();
192 }
193 };
194
195 public ConsistentHash() {
196 this(DEFAULT_HASH);
197 }
198
199 public ConsistentHash(int defaultReplication) {
200 this(DEFAULT_HASH,defaultReplication);
201 }
202
203 public ConsistentHash(Hash<T> hash) {
204 this(hash,100);
205 }
206
207 public ConsistentHash(Hash<T> hash, int defaultReplication) {
208 this.hash = hash;
209 this.defaultReplication = defaultReplication;
210 this.table = new Table(); // initial empty table
211 }
212
213 public int countAllPoints() {
214 int r=0;
215 for (Point[] v : items.values())
216 r+=v.length;
217 return r;
218 }
219
220 /**
221 * Adds a new node with the default number of replica.
222 */
223 public void add(T node) {
224 add(node,defaultReplication);
225 }
226
227 /**
228 * Calls {@link #add(Object)} with all the arguments.
229 */
230 public void addAll(T... nodes) {
231 for (T node : nodes)
232 add(node);
233 }
234
235 /**
236 * Calls {@link #add(Object)} with all the arguments.
237 */
238 public void addAll(Collection<? extends T> nodes) {
239 for (T node : nodes)
240 add(node);
241 }
242
243 /**
244 * Removes the node entirely. This is the same as {@code add(node,0)}
245 */
246 public void remove(T node) {
247 add(node,0);
248 }
249
250 /**
251 * Adds a new node with the given number of replica.
252 *
253 * <p>
254 * This is the only function that manipulates {@link #items}.
255 */
256 public synchronized void add(T node, int replica) {
257 if(replica==0) {
258 items.remove(node);
259 } else {
260 Point[] points = new Point[replica];
261 String seed = hash.hash(node);
262 for (int i=0; i<replica; i++)
263 points[i] = new Point(md5(seed+':'+i),node);
264 items.put(node,points);
265 }
266 table = new Table();
267 }
268
269 /**
270 * Compresses a string into an integer with MD5.
271 */
272 private int md5(String s) {
273 MD5 md5 = new MD5();
274 md5.update(s.getBytes());
275 byte[] digest = new byte[16];
276 md5.digest(digest);
277
278 // 16 bytes -> 4 bytes
279 for (int i=0; i<4; i++)
280 digest[i] ^= digest[i+4]+digest[i+8]+digest[i+12];
281 return (b2i(digest[0])<< 24)|(b2i(digest[1])<<16)|(b2i(digest[2])<< 8)|b2i(digest[3]);
282 }
283
284 /**
285 * unsigned byte->int.
286 */
287 private int b2i(byte b) {
288 return ((int)b)&0xFF;
289 }
290
291 /**
292 * Looks up a consistent hash with the given data point.
293 *
294 * <p>
295 * The whole point of this class is that if the same query point is given,
296 * it's likely to return the same result even when other nodes are added/removed,
297 * or the # of replicas for the given node is changed.
298 *
299 * @return
300 * null if the consistent hash is empty. Otherwise always non-null.
301 */
302 public T lookup(int queryPoint) {
303 return table.lookup(queryPoint);
304 }
305
306 /**
307 * Takes a string, hash it with MD5, then calls {@link #lookup(int)}.
308 */
309 public T lookup(String queryPoint) {
310 return lookup(md5(queryPoint));
311 }
312
313 /**
314 * Creates a permutation of all the nodes for the given data point.
315 *
316 * <p>
317 * The returned pemutation is consistent, in the sense that small change
318 * to the consitent hash (like addition/removal/change of replicas) only
319 * creates a small change in the permutation.
320 *
321 * <p>
322 * Nodes with more replicas are more likely to show up early in the list
323 */
324 public Iterable<T> list(final int queryPoint) {
325 return new Iterable<T>() {
326 public Iterator<T> iterator() {
327 return table.list(queryPoint);
328 }
329 };
330 }
331
332 /**
333 * Takes a string, hash it with MD5, then calls {@link #list(int)}.
334 */
335 public Iterable<T> list(String queryPoint) {
336 return list(md5(queryPoint));
337 }
338 }
339