滑动窗口计数java实现

- 日理万妓 2022-11-27 03:11 110阅读 0赞

滑动窗口计数有很多使用场景，比如说限流防止系统雪崩。相比计数实现，滑动窗口实现会更加平滑，能自动消除毛刺。

概念上可以参考TCP的滑窗算法，可以看一下这篇文章（[关于两种限流模式][Link 1]）。在实现上，滑动窗口算法需要循环队列和线程安全保障。

下面的实现有几点：

> 1.   支持滑窗大小运行时动态调整
> 2.  基于 java8 编译器
> 3.  DEMO实现只支持一个窗口对象，如果要支持多个，需要修改 SlotBaseCounter 类

package slidingwindow;  
      
    import java.util.Arrays;  
    import java.util.concurrent.atomic.AtomicInteger;  
      
    /** 
     * Created by admin on 2016/02/20. 
     */  
    public class SlotBaseCounter {  
        private int slotSize;  
        private AtomicInteger[] slotCounter;  
      
        public SlotBaseCounter(int slotSize) {  
            slotSize = slotSize < 1 ? 1 : slotSize;  
            this.slotSize = slotSize;  
            this.slotCounter = new AtomicInteger[slotSize];  
            for (int i = 0; i < this.slotSize; i++) {  
                slotCounter[i] = new AtomicInteger(0);  
            }  
        }  
      
        public void increaseSlot(int slotSize) {  
            slotCounter[slotSize].incrementAndGet();  
        }  
      
        public void wipeSlot(int slotSize) {  
            slotCounter[slotSize].set(0);  
        }  
      
        public int totalCount() {  
            return Arrays.stream(slotCounter).mapToInt(slotCounter -> slotCounter.get()).sum();  
        }  
      
        @Override  
        public String toString() {  
            return Arrays.toString(slotCounter);  
        }  
    }

package slidingwindow;  
      
    /** 
     * Created by admin on 2016/02/20. 
     */  
    public class SlidingWindowCounter {  
        private volatile SlotBaseCounter slotBaseCounter;  
        private volatile int windowSize;  
        private volatile int head;  
      
        public SlidingWindowCounter(int windowSize) {  
            resizeWindow(windowSize);  
        }  
      
        public synchronized void resizeWindow(int windowSize) {  
            this.windowSize = windowSize;  
            this.slotBaseCounter = new SlotBaseCounter(windowSize);  
            this.head = 0;  
        }  
      
        public void increase() {  
            slotBaseCounter.increaseSlot(head);  
        }  
      
        public int totalAndAdvance() {  
            int total = totalCount();  
            advance();  
            return total;  
        }  
      
        public void advance() {  
            int tail = (head + 1) % windowSize;  
            slotBaseCounter.wipeSlot(tail);  
            head = tail;  
        }  
      
        public int totalCount() {  
            return slotBaseCounter.totalCount();  
        }  
      
        @Override  
        public String toString() {  
            return "total = " + totalCount() + " head = " + head + " >> " + slotBaseCounter;  
        }  
    }

package slidingwindow;  
      
    import java.util.concurrent.TimeUnit;  
      
    /** 
     * Created by admin on 2016/02/20. 
     */  
    public class Loops {  
      
        public static void dieLoop(Runnable runnable) {  
            while (true) {  
                run(runnable);  
            }  
        }  
      
        public static void rateLoop(Runnable runnable, int mills) {  
            while (true) {  
                try {  
                    TimeUnit.MILLISECONDS.sleep(mills);  
                } catch (InterruptedException e) {  
      
                }  
                run(runnable);  
            }  
        }  
      
        public static void fixLoop(Runnable runnable, int loop) {  
            for (int i = 0; i < loop; i++) {  
                run(runnable);  
            }  
        }  
      
        private static void run(Runnable runnable) {  
            try {  
                runnable.run();  
            } catch (Exception e) {  
                e.printStackTrace();  
            }  
        }  
    }

package slidingwindow;  
      
    import org.junit.Test;  
      
    import java.io.IOException;  
    import java.util.Random;  
    import java.util.Scanner;  
    import java.util.concurrent.ExecutorService;  
    import java.util.concurrent.Executors;  
    import java.util.concurrent.ScheduledExecutorService;  
    import java.util.concurrent.TimeUnit;  
      
    /** 
     * Created by admin on 2016/02/20. 
     */  
    public class SlidingWindowCounterTest {  
      
        private ExecutorService es = Executors.newCachedThreadPool();  
        private ScheduledExecutorService ses = Executors.newSingleThreadScheduledExecutor();  
      
        @Test  
        public void testNWindow() throws IOException {  
            SlidingWindowCounter swc = new SlidingWindowCounter(3);  
            ses.scheduleAtFixedRate(() -> {  
                Loops.fixLoop(swc::increase, new Random().nextInt(10));  
            }, 10, 2, TimeUnit.MILLISECONDS);  
            ses.scheduleAtFixedRate(() -> {  
                System.out.println(swc);  
                swc.advance();  
            }, 1, 1, TimeUnit.SECONDS);  
            ses.scheduleAtFixedRate(() -> {  
                swc.resizeWindow(new Random().nextInt(10));  
            }, 1, 10, TimeUnit.SECONDS);  
            System.in.read();  
        }  
      
      
        @Test  
        public void test1Window() {  
            SlidingWindowCounter swc = new SlidingWindowCounter(1);  
            System.out.println(swc);  
            swc.increase();  
            swc.increase();  
            System.out.println(swc);  
            swc.advance();  
            System.out.println(swc);  
            swc.increase();  
            swc.increase();  
            System.out.println(swc);  
        }  
      
        @Test  
        public void test3Window() {  
            SlidingWindowCounter swc = new SlidingWindowCounter(3);  
            System.out.println(swc);  
            swc.increase();  
            System.out.println(swc);  
            swc.advance();  
            System.out.println(swc);  
            swc.increase();  
            swc.increase();  
            System.out.println(swc);  
            swc.advance();  
            System.out.println(swc);  
            swc.increase();  
            swc.increase();  
            swc.increase();  
            System.out.println(swc);  
            swc.advance();  
            System.out.println(swc);  
            swc.increase();  
            swc.increase();  
            swc.increase();  
            swc.increase();  
            System.out.println(swc);  
            swc.advance();  
            System.out.println(swc);  
        }  
    }

**部分测试结果输出：**

total = 2245 head = 0 >> [2245, 0, 0, 0, 0, 0]
    total = 4561 head = 1 >> [2245, 2316, 0, 0, 0, 0]
    total = 6840 head = 2 >> [2245, 2316, 2279, 0, 0, 0]
    total = 8994 head = 3 >> [2245, 2316, 2279, 2154, 0, 0]
    total = 11219 head = 4 >> [2245, 2316, 2279, 2154, 2225, 0]
    total = 13508 head = 5 >> [2245, 2316, 2279, 2154, 2225, 2289]
    total = 13602 head = 0 >> [2339, 2316, 2279, 2154, 2225, 2289]
    total = 13465 head = 1 >> [2339, 2179, 2279, 2154, 2225, 2289]
    total = 13474 head = 2 >> [2339, 2179, 2288, 2154, 2225, 2289]
    total = 13551 head = 3 >> [2339, 2179, 2288, 2231, 2225, 2289]
    total = 2192 head = 0 >> [2192]
    total = 2207 head = 0 >> [2207]
    total = 2291 head = 0 >> [2291]
    total = 2257 head = 0 >> [2257]
    ......

[Link 1]: http://go12345.iteye.com/blog/1744728