28637103998

Committed 03 Jul 2026 03:48AM UTC coverage: 90.399% (-0.2%) from 90.63%

Build # 28637103998

Build Type

push

github

Committed by

Hyshmily

Commit Message

fix: add packaging to gitignore, fix flaky jitter test, update docs references

Signed-off-by: Hyshmily <cxm8607@outlook.com>

Coverage Stats

1264 of 1461 branches covered (86.52%)

Branch coverage included in aggregate %.

3604 of 3924 relevant lines covered (91.85%)

4.19 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.74

/common/src/main/java/io/github/hyshmily/hotkey/sharding/ConsistentHashRing.java

/*
 * Copyright 2026 Hyshmily. All Rights Reserved.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package io.github.hyshmily.hotkey.sharding;

import com.google.common.hash.Hashing;
import io.github.hyshmily.hotkey.Internal;
import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.function.Predicate;
import lombok.RequiredArgsConstructor;
import lombok.extern.slf4j.Slf4j;

/**
 * Consistent hash ring backed by a {@link TreeMap}.
 *
 * <p>Each physical node is replicated across the ring with {@code virtualNodeCount}
 * virtual nodes, all mapped to the same physical {@code nodeId}.  The entire ring
 * is rebuilt atomically via {@link #rebuild(Set)} — no partial mutations, safe for
 * lock-free reads on the hot path.
 */
@Internal
@RequiredArgsConstructor
@Slf4j
public class ConsistentHashRing {

  /**
   * Immutable snapshot of the ring at a point in time.
   *
   * @param ring      the virtual-node hash-to-nodeId mapping
   * @param liveNodes the set of live physical node IDs
   */
  private record RingState(NavigableMap<Integer, String> ring, Set<String> liveNodes) {}

  /** Number of virtual copies created per physical node on the ring. */
  private final int virtualNodeCount;
  /** Current immutable ring snapshot; read lock-free, replaced atomically via {@link #rebuild(Set)}. */
  private volatile RingState currentState = new RingState(Collections.emptyNavigableMap(), Collections.emptySet());

  /** Safety limit to prevent infinite-loop when the ring is corrupt or all nodes are dead. */
  private static final int MAX_PROBES = 512;

  /**
   * Atomically replace the ring with one built from the given live nodes.
   * Each node is replicated {@code virtualNodeCount} times on the ring.
   *
   * @param liveNodes the set of physical node IDs to place on the ring;
   *                  must not be {@code null}
   */
  public void rebuild(Set<String> liveNodes) {
    NavigableMap<Integer, String> ring = new TreeMap<>();

    for (String nodeId : liveNodes) {
      for (int i = 0; i < virtualNodeCount; i++) {
        ring.put(hash(nodeId + ":" + i), nodeId);
      }
    }
    currentState = new RingState(Collections.unmodifiableNavigableMap(ring), Set.copyOf(liveNodes));
  }

  /**
   * Return the physical node responsible for the given business key, skipping nodes
   * that fail the liveness predicate.
   *
   * @param key     the business key to route; must not be {@code null}
   * @param isAlive predicate that returns {@code true} if a node is considered alive;
   *                must not be {@code null}
   * @return the physical node ID, or {@code null} if the ring is empty or all nodes are dead
   */
  public String locateNode(String key, Predicate<String> isAlive) {
    NavigableMap<Integer, String> currentRing = currentState.ring;

    if (currentRing.isEmpty()) {
      return null;
    }

    int hashKey = hash(key);
    Map.Entry<Integer, String> entry = currentRing.ceilingEntry(hashKey);
    if (entry == null) {
      entry = currentRing.firstEntry();
    }

    int startHash = entry.getKey();
    int currentHash = startHash;
    int probes = 0;

    do {
      String physicalNode = currentRing.get(currentHash);
      if (physicalNode != null && isAlive.test(physicalNode)) {
        return physicalNode;
      }

      Map.Entry<Integer, String> next = currentRing.higherEntry(currentHash);
      if (next == null) {
        next = currentRing.firstEntry();
      }

      currentHash = next.getKey();

      if (++probes > MAX_PROBES) {
        log.warn(
          "Exhausted {} probes in consistent hash ring for key '{}', all workers appear dead or ring is corrupt. Discarding this key.",
          MAX_PROBES,
          key
        );
        break;
      }
    } while (currentHash != startHash);

    return null;
  }

  /**
   * Return the set of live physical node IDs.
   *
   * @return an unmodifiable set of node IDs (never {@code null})
   */
  public Set<String> getNodes() {
    return currentState.liveNodes;
  }

  /**
   * Return whether the ring contains no virtual nodes (i.e. no live nodes).
   *
   * @return {@code true} if the ring is empty
   */
  public boolean isEmpty() {
    return currentState.ring.isEmpty();
  }

  /**
   * Return the number of live physical nodes in the ring.
   *
   * @return the node count (zero if no live nodes)
   */
  public int nodeCount() {
    return currentState.liveNodes.size();
  }

  /**
   * Compute a 32-bit Murmur3 hash for the given string using Guava's
   * {@code murmur3_32_fixed()} implementation.
   *
   * @param key the string to hash; must not be {@code null}
   * @return the hash value (may be negative)
   */
  private static int hash(String key) {
    return Hashing.murmur3_32_fixed().hashString(key, StandardCharsets.UTF_8).asInt();
  }
}

1	/*
2	* Copyright 2026 Hyshmily. All Rights Reserved.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package io.github.hyshmily.hotkey.sharding;
17
18	import com.google.common.hash.Hashing;
19	import io.github.hyshmily.hotkey.Internal;
20	import java.nio.charset.StandardCharsets;
21	import java.util.*;
22	import java.util.function.Predicate;
23	import lombok.RequiredArgsConstructor;
24	import lombok.extern.slf4j.Slf4j;
25
26	/**
27	* Consistent hash ring backed by a {@link TreeMap}.
28	*
29	* <p>Each physical node is replicated across the ring with {@code virtualNodeCount}
30	* virtual nodes, all mapped to the same physical {@code nodeId}. The entire ring
31	* is rebuilt atomically via {@link #rebuild(Set)} — no partial mutations, safe for
32	* lock-free reads on the hot path.
33	*/
34	@Internal
35	@RequiredArgsConstructor
36	@Slf4j	4✔
37	public class ConsistentHashRing {
38
39	/**
40	* Immutable snapshot of the ring at a point in time.
41	*
42	* @param ring the virtual-node hash-to-nodeId mapping
43	* @param liveNodes the set of live physical node IDs
44	*/
45	private record RingState(NavigableMap<Integer, String> ring, Set<String> liveNodes) {}	9✔
46
47	/** Number of virtual copies created per physical node on the ring. */
48	private final int virtualNodeCount;
49	/** Current immutable ring snapshot; read lock-free, replaced atomically via {@link #rebuild(Set)}. */
50	private volatile RingState currentState = new RingState(Collections.emptyNavigableMap(), Collections.emptySet());
51
52	/** Safety limit to prevent infinite-loop when the ring is corrupt or all nodes are dead. */
53	private static final int MAX_PROBES = 512;
54
55	/**
56	* Atomically replace the ring with one built from the given live nodes.
57	* Each node is replicated {@code virtualNodeCount} times on the ring.
58	*
59	* @param liveNodes the set of physical node IDs to place on the ring;
60	* must not be {@code null}
61	*/
62	public void rebuild(Set<String> liveNodes) {
63	NavigableMap<Integer, String> ring = new TreeMap<>();	4✔
64
65	for (String nodeId : liveNodes) {	10✔
66	for (int i = 0; i < virtualNodeCount; i++) {	8✔
67	ring.put(hash(nodeId + ":" + i), nodeId);	9✔
68	}
69	}	1✔
70	currentState = new RingState(Collections.unmodifiableNavigableMap(ring), Set.copyOf(liveNodes));	9✔
71	}	1✔
72
73	/**
74	* Return the physical node responsible for the given business key, skipping nodes
75	* that fail the liveness predicate.
76	*
77	* @param key the business key to route; must not be {@code null}
78	* @param isAlive predicate that returns {@code true} if a node is considered alive;
79	* must not be {@code null}
80	* @return the physical node ID, or {@code null} if the ring is empty or all nodes are dead
81	*/
82	public String locateNode(String key, Predicate<String> isAlive) {
83	NavigableMap<Integer, String> currentRing = currentState.ring;	4✔
84
85	if (currentRing.isEmpty()) {	3✔
86	return null;	2✔
87	}
88
89	int hashKey = hash(key);	3✔
90	Map.Entry<Integer, String> entry = currentRing.ceilingEntry(hashKey);	5✔
91	if (entry == null) {	2✔
92	entry = currentRing.firstEntry();	3✔
93	}
94
95	int startHash = entry.getKey();	5✔
96	int currentHash = startHash;	2✔
97	int probes = 0;	2✔
98
99	do {
100	String physicalNode = currentRing.get(currentHash);	6✔
101	if (physicalNode != null && isAlive.test(physicalNode)) {	6!
102	return physicalNode;	2✔
103	}
104
105	Map.Entry<Integer, String> next = currentRing.higherEntry(currentHash);	5✔
106	if (next == null) {	2✔
107	next = currentRing.firstEntry();	3✔
108	}
109
110	currentHash = next.getKey();	5✔
111
112	if (++probes > MAX_PROBES) {	4!
113	log.warn(	×
114	"Exhausted {} probes in consistent hash ring for key '{}', all workers appear dead or ring is corrupt. Discarding this key.",
115	MAX_PROBES,	×
116	key
117	);
118	break;	×
119	}
120	} while (currentHash != startHash);	3✔
121
122	return null;	2✔
123	}
124
125	/**
126	* Return the set of live physical node IDs.
127	*
128	* @return an unmodifiable set of node IDs (never {@code null})
129	*/
130	public Set<String> getNodes() {
131	return currentState.liveNodes;	4✔
132	}
133
134	/**
135	* Return whether the ring contains no virtual nodes (i.e. no live nodes).
136	*
137	* @return {@code true} if the ring is empty
138	*/
139	public boolean isEmpty() {
140	return currentState.ring.isEmpty();	5✔
141	}
142
143	/**
144	* Return the number of live physical nodes in the ring.
145	*
146	* @return the node count (zero if no live nodes)
147	*/
148	public int nodeCount() {
149	return currentState.liveNodes.size();	5✔
150	}
151
152	/**
153	* Compute a 32-bit Murmur3 hash for the given string using Guava's
154	* {@code murmur3_32_fixed()} implementation.
155	*
156	* @param key the string to hash; must not be {@code null}
157	* @return the hash value (may be negative)
158	*/
159	private static int hash(String key) {
160	return Hashing.murmur3_32_fixed().hashString(key, StandardCharsets.UTF_8).asInt();	6✔
161	}
162	}

Hyshmily / hotkey / 28637103998

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous