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

95.77

/common/src/main/java/io/github/hyshmily/hotkey/util/window/RollingWindow.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.util.window;

import static io.github.hyshmily.hotkey.util.TimeSource.currentTimeMillis;

import io.github.hyshmily.hotkey.Internal;
import java.util.concurrent.atomic.AtomicLongArray;

/**
 * A fixed-size time-based sliding window backed by an {@link AtomicLongArray}
 * circular buffer.
 *
 * <p>The window is divided into {@code windowSize} equally-sized buckets spanning
 * {@code windowDurationMs} milliseconds. Each bucket represents a time slice and
 * holds a cumulative value. On every access ({@link #add(long)}, {@link #sum()},
 * etc.), expired buckets are detected and zeroed before the operation proceeds
 * via the internal {@link #tick()} method.
 *
 * <p>{@link AtomicLongArray} provides lock-free atomic access to individual
 * buckets, and {@code tick()} uses a private lock only when buckets actually
 * need rotation (once per bucket duration).  For the common case (no bucket
 * boundary crossed) there is zero lock contention.  This design targets the
 * HotKey reporter and SRE limiter use cases where call rates are in the
 * hundreds to low thousands per second.
 *
 * <p>Tick races are self-correcting: if two threads rotate simultaneously,
 * some buckets may be zeroed twice (harmless) or a value may land in a
 * bucket that is about to be zeroed (lost increment, acceptable for
 * rate-limiter approximations).  The next tick will converge.
 *
 * @see io.github.hyshmily.hotkey.util.ratelimit.SreRateLimiter
 */
@Internal
public final class RollingWindow {

  private final AtomicLongArray buckets;
  private final int windowSize;
  private final long bucketDurationMs;

  private volatile long windowStart;
  private volatile int currentBucket;

  /** Private lock for tick() — only acquired when bucket rotation is actually needed. */
  private final Object tickLock = new Object();

  /**
   * Creates a sliding window with the given number of buckets spanning the given duration.
   *
   * <p>Each bucket covers {@code windowDurationMs / windowSize} milliseconds.
   * The window clock starts at construction time. All buckets are initially zero.
   *
   * @param windowSize       number of buckets that form one full window; must be positive
   * @param windowDurationMs total duration of the sliding window in milliseconds; must be
   *                         positive and evenly divisible by {@code windowSize} for
   *                         precise bucket boundaries
   */
  public RollingWindow(int windowSize, long windowDurationMs) {
    this.windowSize = windowSize;
    this.bucketDurationMs = windowDurationMs / windowSize;
    this.buckets = new AtomicLongArray(windowSize);
    this.windowStart = currentTimeMillis();
  }

  /**
   * Add {@code value} to the current (most recent) bucket.
   *
   * <p>Bucket drift is corrected via {@link #tick()} before the addition,
   * ensuring that the value lands in the correct time-aligned bucket even
   * if no other operation has occurred for an extended period.
   *
   * @param value the value to add to the current bucket (may be negative, though
   *              typical usage patterns use non-negative counts)
   */
  public void add(long value) {
    tick();
    buckets.addAndGet(currentBucket, value);
  }

  /**
   * Sum of all buckets in the window.
   *
   * <p>Expired buckets are zeroed via {@link #tick()} before summing, so the
   * returned value reflects only the data from the current window. This is an
   * O(windowSize) operation.
   *
   * @return the sum across all buckets (may be 0 if all buckets are zero)
   */
  public long sum() {
    tick();
    long s = 0;
    for (int i = 0; i < windowSize; i++) {
      s += buckets.get(i);
    }
    return s;
  }

  /**
   * Maximum value across all buckets in the window.
   *
   * <p>Expired buckets are zeroed via {@link #tick()} before computing.
   * O(windowSize) operation.
   *
   * @return the maximum value across all buckets, or 0 if all buckets are zero
   */
  public long max() {
    tick();
    long m = 0;
    for (int i = 0; i < windowSize; i++) {
      long v = buckets.get(i);
      if (v > m) {
        m = v;
      }
    }
    return m;
  }

  /**
   * Minimum non-zero value across all buckets in the window.
   *
   * <p>Expired buckets are zeroed via {@link #tick()} before computing.
   * Useful for detecting the minimum "background" rate when most buckets
   * have positive values. O(windowSize) operation.
   *
   * @return the minimum positive value across all buckets, or {@link Long#MAX_VALUE}
   *         if every bucket is zero
   */
  public long minNonZero() {
    tick();
    long m = Long.MAX_VALUE;
    for (int i = 0; i < windowSize; i++) {
      long v = buckets.get(i);
      if (v > 0 && v < m) {
        m = v;
      }
    }
    return m;
  }

  /**
   * Zero every bucket and reset the window clock to the current time.
   *
   * <p>After calling this method, the window behaves as if newly constructed:
   * all buckets are zero and the time origin is reset. This is useful when
   * the monitored metric resets (e.g. after a configuration change, a new
   * sampling period, or a rate-limit cooldown).
   *
   * <p>O(windowSize) operation.
   */
  public void reset() {
    synchronized (tickLock) {
      for (int i = 0; i < windowSize; i++) {
        buckets.set(i, 0);
      }
      windowStart = currentTimeMillis();
      currentBucket = 0;
    }
  }

  /**
   * Returns the number of buckets in the window.  Thread-safe.
   *
   * @return the number of buckets
   */
  public int size() {
    return windowSize;
  }

  /** Advance the window, zeroing buckets that have elapsed. */
  private void tick() {
    // Fast path (no lock) — 99.9%+ of calls hit this.
    if (currentTimeMillis() - windowStart < bucketDurationMs) {
      return;
    }

    synchronized (tickLock) {
      long now = currentTimeMillis();
      long elapsed = now - windowStart;
      if (elapsed < bucketDurationMs) {
        return; // double-check: another thread already rotated
      }

      int steps = (int) Math.min(elapsed / bucketDurationMs, windowSize);
      for (int i = 0; i < steps; i++) {
        currentBucket = (currentBucket + 1) % windowSize;
        buckets.set(currentBucket, 0);
      }
      windowStart += steps * bucketDurationMs;
    }
  }
}

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.util.window;
17
18	import static io.github.hyshmily.hotkey.util.TimeSource.currentTimeMillis;
19
20	import io.github.hyshmily.hotkey.Internal;
21	import java.util.concurrent.atomic.AtomicLongArray;
22
23	/**
24	* A fixed-size time-based sliding window backed by an {@link AtomicLongArray}
25	* circular buffer.
26	*
27	* <p>The window is divided into {@code windowSize} equally-sized buckets spanning
28	* {@code windowDurationMs} milliseconds. Each bucket represents a time slice and
29	* holds a cumulative value. On every access ({@link #add(long)}, {@link #sum()},
30	* etc.), expired buckets are detected and zeroed before the operation proceeds
31	* via the internal {@link #tick()} method.
32	*
33	* <p>{@link AtomicLongArray} provides lock-free atomic access to individual
34	* buckets, and {@code tick()} uses a private lock only when buckets actually
35	* need rotation (once per bucket duration). For the common case (no bucket
36	* boundary crossed) there is zero lock contention. This design targets the
37	* HotKey reporter and SRE limiter use cases where call rates are in the
38	* hundreds to low thousands per second.
39	*
40	* <p>Tick races are self-correcting: if two threads rotate simultaneously,
41	* some buckets may be zeroed twice (harmless) or a value may land in a
42	* bucket that is about to be zeroed (lost increment, acceptable for
43	* rate-limiter approximations). The next tick will converge.
44	*
45	* @see io.github.hyshmily.hotkey.util.ratelimit.SreRateLimiter
46	*/
47	@Internal
48	public final class RollingWindow {
49
50	private final AtomicLongArray buckets;
51	private final int windowSize;
52	private final long bucketDurationMs;
53
54	private volatile long windowStart;
55	private volatile int currentBucket;
56
57	/** Private lock for tick() — only acquired when bucket rotation is actually needed. */
58	private final Object tickLock = new Object();	5✔
59
60	/**
61	* Creates a sliding window with the given number of buckets spanning the given duration.
62	*
63	* <p>Each bucket covers {@code windowDurationMs / windowSize} milliseconds.
64	* The window clock starts at construction time. All buckets are initially zero.
65	*
66	* @param windowSize number of buckets that form one full window; must be positive
67	* @param windowDurationMs total duration of the sliding window in milliseconds; must be
68	* positive and evenly divisible by {@code windowSize} for
69	* precise bucket boundaries
70	*/
71	public RollingWindow(int windowSize, long windowDurationMs) {	2✔
72	this.windowSize = windowSize;	3✔
73	this.bucketDurationMs = windowDurationMs / windowSize;	6✔
74	this.buckets = new AtomicLongArray(windowSize);	6✔
75	this.windowStart = currentTimeMillis();	3✔
76	}	1✔
77
78	/**
79	* Add {@code value} to the current (most recent) bucket.
80	*
81	* <p>Bucket drift is corrected via {@link #tick()} before the addition,
82	* ensuring that the value lands in the correct time-aligned bucket even
83	* if no other operation has occurred for an extended period.
84	*
85	* @param value the value to add to the current bucket (may be negative, though
86	* typical usage patterns use non-negative counts)
87	*/
88	public void add(long value) {
89	tick();	2✔
90	buckets.addAndGet(currentBucket, value);	7✔
91	}	1✔
92
93	/**
94	* Sum of all buckets in the window.
95	*
96	* <p>Expired buckets are zeroed via {@link #tick()} before summing, so the
97	* returned value reflects only the data from the current window. This is an
98	* O(windowSize) operation.
99	*
100	* @return the sum across all buckets (may be 0 if all buckets are zero)
101	*/
102	public long sum() {
103	tick();	2✔
104	long s = 0;	2✔
105	for (int i = 0; i < windowSize; i++) {	8✔
106	s += buckets.get(i);	7✔
107	}
108	return s;	2✔
109	}
110
111	/**
112	* Maximum value across all buckets in the window.
113	*
114	* <p>Expired buckets are zeroed via {@link #tick()} before computing.
115	* O(windowSize) operation.
116	*
117	* @return the maximum value across all buckets, or 0 if all buckets are zero
118	*/
119	public long max() {
120	tick();	2✔
121	long m = 0;	2✔
122	for (int i = 0; i < windowSize; i++) {	8✔
123	long v = buckets.get(i);	5✔
124	if (v > m) {	4✔
125	m = v;	2✔
126	}
127	}
128	return m;	2✔
129	}
130
131	/**
132	* Minimum non-zero value across all buckets in the window.
133	*
134	* <p>Expired buckets are zeroed via {@link #tick()} before computing.
135	* Useful for detecting the minimum "background" rate when most buckets
136	* have positive values. O(windowSize) operation.
137	*
138	* @return the minimum positive value across all buckets, or {@link Long#MAX_VALUE}
139	* if every bucket is zero
140	*/
141	public long minNonZero() {
142	tick();	2✔
143	long m = Long.MAX_VALUE;	2✔
144	for (int i = 0; i < windowSize; i++) {	8✔
145	long v = buckets.get(i);	5✔
146	if (v > 0 && v < m) {	8!
147	m = v;	2✔
148	}
149	}
150	return m;	2✔
151	}
152
153	/**
154	* Zero every bucket and reset the window clock to the current time.
155	*
156	* <p>After calling this method, the window behaves as if newly constructed:
157	* all buckets are zero and the time origin is reset. This is useful when
158	* the monitored metric resets (e.g. after a configuration change, a new
159	* sampling period, or a rate-limit cooldown).
160	*
161	* <p>O(windowSize) operation.
162	*/
163	public void reset() {
164	synchronized (tickLock) {	5✔
165	for (int i = 0; i < windowSize; i++) {	8✔
166	buckets.set(i, 0);	5✔
167	}
168	windowStart = currentTimeMillis();	3✔
169	currentBucket = 0;	3✔
170	}	3✔
171	}	1✔
172
173	/**
174	* Returns the number of buckets in the window. Thread-safe.
175	*
176	* @return the number of buckets
177	*/
178	public int size() {
179	return windowSize;	3✔
180	}
181
182	/** Advance the window, zeroing buckets that have elapsed. */
183	private void tick() {
184	// Fast path (no lock) — 99.9%+ of calls hit this.
185	if (currentTimeMillis() - windowStart < bucketDurationMs) {	8✔
186	return;	1✔
187	}
188
189	synchronized (tickLock) {	5✔
190	long now = currentTimeMillis();	2✔
191	long elapsed = now - windowStart;	5✔
192	if (elapsed < bucketDurationMs) {	5!
193	return; // double-check: another thread already rotated	×
194	}
195
196	int steps = (int) Math.min(elapsed / bucketDurationMs, windowSize);	10✔
197	for (int i = 0; i < steps; i++) {	7✔
198	currentBucket = (currentBucket + 1) % windowSize;	9✔
199	buckets.set(currentBucket, 0);	6✔
200	}
201	windowStart += steps * bucketDurationMs;	10✔
202	}	3✔
203	}	1✔
204	}

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