滑动窗口计数java实现

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

 

概念上可以参考TCP的滑窗算法，可以看一下这篇文章（http://go12345.iteye.com/blog/1744728）。在实现上，滑动窗口算法需要循环队列和线程安全保障。

 

下面的实现有几个点

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]

total = 2250 head = 0 >> [2250]

total = 2201 head = 0 >> [2201]

total = 2299 head = 0 >> [2299]

total = 2223 head = 0 >> [2223]

total = 2190 head = 0 >> [2190]

total = 2306 head = 0 >> [2306]

total = 2290 head = 0 >> [2290, 0, 0, 0, 0, 0, 0, 0, 0]

total = 4474 head = 1 >> [2290, 2184, 0, 0, 0, 0, 0, 0, 0]

total = 6632 head = 2 >> [2290, 2184, 2158, 0, 0, 0, 0, 0, 0]

total = 8744 head = 3 >> [2290, 2184, 2158, 2112, 0, 0, 0, 0, 0]

total = 11008 head = 4 >> [2290, 2184, 2158, 2112, 2264, 0, 0, 0, 0]

total = 13277 head = 5 >> [2290, 2184, 2158, 2112, 2264, 2269, 0, 0, 0]

total = 15446 head = 6 >> [2290, 2184, 2158, 2112, 2264, 2269, 2169, 0, 0]

total = 17617 head = 7 >> [2290, 2184, 2158, 2112, 2264, 2269, 2169, 2171, 0]

total = 19749 head = 8 >> [2290, 2184, 2158, 2112, 2264, 2269, 2169, 2171, 2132]

total = 19608 head = 0 >> [2149, 2184, 2158, 2112, 2264, 2269, 2169, 2171, 2132]

total = 2256 head = 0 >> [2256, 0, 0, 0]

total = 4624 head = 1 >> [2256, 2368, 0, 0]

total = 6811 head = 2 >> [2256, 2368, 2187, 0]

total = 8973 head = 3 >> [2256, 2368, 2187, 2162]

total = 8934 head = 0 >> [2217, 2368, 2187, 2162]

total = 8798 head = 1 >> [2217, 2232, 2187, 2162]

total = 8912 head = 2 >> [2217, 2232, 2301, 2162]

total = 8940 head = 3 >> [2217, 2232, 2301, 2190]

total = 8987 head = 0 >> [2264, 2232, 2301, 2190]

total = 9049 head = 1 >> [2264, 2294, 2301, 2190]

total = 2220 head = 0 >> [2220, 0, 0, 0, 0, 0, 0]

total = 4477 head = 1 >> [2220, 2257, 0, 0, 0, 0, 0]

total = 6718 head = 2 >> [2220, 2257, 2241, 0, 0, 0, 0]

total = 8939 head = 3 >> [2220, 2257, 2241, 2221, 0, 0, 0]

total = 11174 head = 4 >> [2220, 2257, 2241, 2221, 2235, 0, 0]

total = 13420 head = 5 >> [2220, 2257, 2241, 2221, 2235, 2246, 0]

total = 15673 head = 6 >> [2220, 2257, 2241, 2221, 2235, 2246, 2253]

total = 15779 head = 0 >> [2326, 2257, 2241, 2221, 2235, 2246, 2253]

total = 15796 head = 1 >> [2326, 2274, 2241, 2221, 2235, 2246, 2253]

total = 15802 head = 2 >> [2326, 2274, 2247, 2221, 2235, 2246, 2253]

 

 

评论

2 楼 huangyunbin 2018-05-04  

swc.advance();   这个什么时候被调用是最核心的实现。
你这个居然是在测试代码中直接调。。。。
应该是切换到下一秒的时候自动调用的。这块地方的并发处理才是最关键的

1 楼 u012352249 2016-05-20  

怎么支持多个窗口啊？