28503055923

Committed 01 Jul 2026 08:06AM UTC coverage: 90.445% (-0.4%) from 90.887%

Build # 28503055923

Build Type

push

github

Committed by

Hyshmily

Commit Message

perf : promote throughput performance

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

Coverage Stats

1248 of 1441 branches covered (86.61%)

Branch coverage included in aggregate %.

123 of 139 new or added lines in 10 files covered. (88.49%)

2 existing lines in 2 files now uncovered.

3532 of 3844 relevant lines covered (91.88%)

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

Hyshmily / hotkey / 28503055923

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