![[Jenkins]](/grizzly/static/26056217/images/svgs/logo.svg){kind=logo}
Package: ConsistentHashStore
ConsistentHashStore
| name | instruction | branch | complexity | line | method | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ConsistentHashStore() |
|
|
|
|
|
||||||||||||||||||||
| add(Object) |
|
|
|
|
|
||||||||||||||||||||
| addOrRemove(Object, boolean) |
|
|
|
|
|
||||||||||||||||||||
| calculateHash(ByteBuffer) |
|
|
|
|
|
||||||||||||||||||||
| calculateHash(byte[]) |
|
|
|
|
|
||||||||||||||||||||
| clear() |
|
|
|
|
|
||||||||||||||||||||
| get(ByteBuffer) |
|
|
|
|
|
||||||||||||||||||||
| get(String) |
|
|
|
|
|
||||||||||||||||||||
| get(byte[]) |
|
|
|
|
|
||||||||||||||||||||
| getMessageDigest() |
|
|
|
|
|
||||||||||||||||||||
| hasValue(Object) |
|
|
|
|
|
||||||||||||||||||||
| remove(Object) |
|
|
|
|
|
||||||||||||||||||||
| static {...} |
|
|
|
|
|
||||||||||||||||||||
Coverage
1: /*
2: * Copyright (c) 2012, 2017 Oracle and/or its affiliates. All rights reserved.
3: *
4: * This program and the accompanying materials are made available under the
5: * terms of the Eclipse Public License v. 2.0, which is available at
6: * http://www.eclipse.org/legal/epl-2.0.
7: *
8: * This Source Code may also be made available under the following Secondary
9: * Licenses when the conditions for such availability set forth in the
10: * Eclipse Public License v. 2.0 are satisfied: GNU General Public License,
11: * version 2 with the GNU Classpath Exception, which is available at
12: * https://www.gnu.org/software/classpath/license.html.
13: *
14: * SPDX-License-Identifier: EPL-2.0 OR GPL-2.0 WITH Classpath-exception-2.0
15: */
16:
17: package org.glassfish.grizzly.memcached;
18:
19: import org.glassfish.grizzly.Grizzly;
20:
21: import java.nio.ByteBuffer;
22: import java.security.MessageDigest;
23: import java.security.NoSuchAlgorithmException;
24: import java.util.Collections;
25: import java.util.Set;
26: import java.util.concurrent.ConcurrentHashMap;
27: import java.util.concurrent.ConcurrentSkipListMap;
28: import java.util.logging.Level;
29: import java.util.logging.Logger;
30: import java.util.zip.CRC32;
31:
32: /**
33: * The implementation class of the Consistent Hashing algorithms
34: * <p>
35: * Given keys and values will be hashed by MD5 and stored in sorted map.
36: * If MD5 is not supported, CRC32 will be used.
37: * Values(such as server list) can be added and removed dynamically.
38: * <p>
39: * This store supports keys of String, byte array and ByteBuffer type
40: * <p>
41: * Ketama's logic applied partially.
42: * <p>
43: * This class should be thread-safe.
44: * <p>
45: * Example of use:
46: * See org.glassfish.grizzly.memcached.ConsistentHashStoreTest's test codes
47: *
48: * @author Bongjae Chang
49: */
50: public class ConsistentHashStore<T> {
51:
52: private static final Logger logger = Grizzly.logger(ConsistentHashStore.class);
53:
54: private static final ThreadLocal<MessageDigest> md5ThreadLocal = new ThreadLocal<MessageDigest>();
55: private volatile static boolean md5NotSupported;
56:
57: private static final int REPLICA_NUMBER = 160;
58:
59: private final ConcurrentSkipListMap<Long, T> buckets = new ConcurrentSkipListMap<Long, T>();
60: private final Set<T> values = Collections.newSetFromMap(new ConcurrentHashMap<T, Boolean>());
61:
62: /**
63: * Add the value such as a server name
64: *
65: * @param value value to be added
66: */
67: public void add(final T value) {
68: addOrRemove(value, true);
69: values.add(value);
70: }
71:
72: /**
73: * Remove the value which already added by {@link #add}
74: *
75: * @param value value to be removed in this store
76: */
77: public void remove(final T value) {
78: addOrRemove(value, false);
79: values.remove(value);
80: }
81:
82: /**
83: * Check if this store has {@code value}
84: *
85: * @param value value to be checked
86: * @return true if this store already contains {@code value}
87: */
88: public boolean hasValue(final T value) {
89:• return value != null && values.contains(value);
90: }
91:
92: /**
93: * Clear all values and keys
94: */
95: public void clear() {
96: buckets.clear();
97: values.clear();
98: }
99:
100: private void addOrRemove(final T value, boolean add) {
101:• if (value == null) {
102: return;
103: }
104: final MessageDigest md5 = getMessageDigest();
105:• if (md5 == null) {
106:• for (int i = 0; i < REPLICA_NUMBER; i++) {
107: final StringBuilder stringBuilder = new StringBuilder(64);
108: stringBuilder.append(value).append('-').append(i);
109: CRC32 crc32 = new CRC32();
110: crc32.update(stringBuilder.toString().getBytes());
111: long hashKey = crc32.getValue() >> 16 & 0x7fff;
112:• if (add) {
113: buckets.putIfAbsent(hashKey, value);
114:• if (logger.isLoggable(Level.FINE)) {
115: logger.log(Level.FINE, "added {0} to the bucket successfully. key={1}", new Object[]{value, hashKey});
116: }
117: } else {
118: buckets.remove(hashKey);
119:• if (logger.isLoggable(Level.FINE)) {
120: logger.log(Level.FINE, "removed {0} to the bucket successfully. key={1}", new Object[]{value, hashKey});
121: }
122: }
123: }
124: } else {
125:• for (int i = 0; i < REPLICA_NUMBER / 4; i++) {
126: final StringBuilder stringBuilder = new StringBuilder(64);
127: stringBuilder.append(value).append('-').append(i);
128: byte[] digest = md5.digest(stringBuilder.toString().getBytes());
129:• for (int j = 0; j < 4; j++) {
130: long hashKey = ((long) (digest[3 + j * 4] & 0xFF) << 24)
131: | ((long) (digest[2 + j * 4] & 0xFF) << 16)
132: | ((long) (digest[1 + j * 4] & 0xFF) << 8)
133: | ((long) (digest[j * 4] & 0xFF));
134:• if (add) {
135: buckets.putIfAbsent(hashKey, value);
136:• if (logger.isLoggable(Level.FINE)) {
137: logger.log(Level.FINE, "added {0} to the bucket successfully. key={1}", new Object[]{value, hashKey});
138: }
139: } else {
140: buckets.remove(hashKey);
141:• if (logger.isLoggable(Level.FINE)) {
142: logger.log(Level.FINE, "removed {0} to the bucket successfully. key={1}", new Object[]{value, hashKey});
143: }
144: }
145: }
146: }
147: }
148: }
149:
150: /**
151: * Get the value corresponding to the given key
152: *
153: * @param key String key
154: * @return the selected value corresponding to the {@code key}
155: */
156: public T get(final String key) {
157:• if (key == null) {
158: return null;
159: }
160: return get(key.getBytes());
161: }
162:
163: /**
164: * Get the value corresponding to the given key
165: *
166: * @param key byte array key
167: * @return the selected value corresponding to the {@code key}
168: */
169: public T get(final byte[] key) {
170:• if (key == null) {
171: return null;
172: }
173:• if (buckets.size() == 0) {
174: return null;
175: }
176:• if (buckets.size() == 1) {
177: return buckets.firstEntry().getValue();
178: }
179: // ceilingKey returns the least key greater than or equal to the given key,
180: // or null if no such key.
181: Long hashKey = buckets.ceilingKey(calculateHash(key));
182: // if none found, it must be at the end, return the lowest in the tree
183: // (we go over the end the continuum to the first entry)
184:• if (hashKey == null) {
185: hashKey = buckets.firstKey();
186: }
187: return buckets.get(hashKey);
188: }
189:
190: /**
191: * Get the value corresponding to the given key
192: *
193: * @param key {@link ByteBuffer} key
194: * @return the selected value corresponding to the {@code key}
195: */
196: public T get(final ByteBuffer key) {
197:• if (key == null) {
198: return null;
199: }
200:• if (buckets.size() == 0) {
201: return null;
202: }
203:• if (buckets.size() == 1) {
204: return buckets.firstEntry().getValue();
205: }
206: // ceilingKey returns the least key greater than or equal to the given key,
207: // or null if no such key.
208: Long hashKey = buckets.ceilingKey(calculateHash(key));
209: // if none found, it must be at the end, return the lowest in the tree
210: // (we go over the end the continuum to the first entry)
211:• if (hashKey == null) {
212: hashKey = buckets.firstKey();
213: }
214: return buckets.get(hashKey);
215: }
216:
217: private long calculateHash(final byte[] key) {
218:• if (key == null) {
219: return 0;
220: }
221: final long hash;
222: final MessageDigest md5 = getMessageDigest();
223:• if (md5 == null) {
224: CRC32 crc32 = new CRC32();
225: crc32.update(key);
226: hash = crc32.getValue() >> 16 & 0x7fff;
227: } else {
228: md5.reset();
229: final byte[] digest = md5.digest(key);
230: hash = ((long) (digest[3] & 0xFF) << 24) | ((long) (digest[2] & 0xFF) << 16) | ((long) (digest[1] & 0xFF) << 8) | (long) (digest[0] & 0xFF);
231: }
232: return hash;
233: }
234:
235: private long calculateHash(final ByteBuffer key) {
236:• if (key == null) {
237: return 0;
238: }
239: final long hash;
240: final MessageDigest md5 = getMessageDigest();
241:• if (md5 == null) {
242:• if (key.hasArray()) {
243: CRC32 crc32 = new CRC32();
244: byte[] b = key.array();
245: int ofs = key.arrayOffset();
246: int pos = key.position();
247: int lim = key.limit();
248: crc32.update(b, ofs + pos, lim - pos);
249: key.position(lim);
250: hash = crc32.getValue() >> 16 & 0x7fff;
251: } else {
252: hash = key.hashCode();
253: }
254: } else {
255: md5.reset();
256: md5.update(key);
257: final byte[] digest = md5.digest();
258: hash = ((long) (digest[3] & 0xFF) << 24) | ((long) (digest[2] & 0xFF) << 16) | ((long) (digest[1] & 0xFF) << 8) | (long) (digest[0] & 0xFF);
259: }
260: key.flip();
261: return hash;
262: }
263:
264: private static MessageDigest getMessageDigest() {
265:• if (md5NotSupported) {
266: return null;
267: }
268: MessageDigest md5 = md5ThreadLocal.get();
269:• if (md5 == null) {
270: try {
271: md5 = MessageDigest.getInstance("MD5");
272: md5ThreadLocal.set(md5);
273: } catch (NoSuchAlgorithmException nsae) {
274: md5NotSupported = true;
275:• if (logger.isLoggable(Level.WARNING)) {
276: logger.log(Level.WARNING, "failed to get the md5", nsae);
277: }
278: }
279: }
280: return md5;
281: }
282: }