`
yunchow
  • 浏览: 323649 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

滑动窗口计数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]

 

 

1
2
分享到:
评论
2 楼 huangyunbin 2018-05-04  
swc.advance();   这个什么时候被调用是最核心的实现。
你这个居然是在测试代码中直接调。。。。
应该是切换到下一秒的时候自动调用的。这块地方的并发处理才是最关键的
1 楼 u012352249 2016-05-20  
怎么支持多个窗口啊?

相关推荐

    dam-滑动窗口demo

    滑动窗口的概念不仅限于C语言,也可以应用于其他编程语言,如Java、Python等。在大数据处理框架如Apache Flink和Spark中,滑动窗口也被广泛用于实时流处理任务,以满足实时分析和决策的需求。 总的来说,滑动窗口是...

    基于Redis限流(固定窗口、滑动窗口、漏桶、令牌桶).rar

    这里我们主要探讨的是如何利用Redis实现四种不同的限流策略:固定窗口、滑动窗口、漏桶和令牌桶。这些算法广泛应用于分布式系统、微服务架构以及API管理等领域。 首先,我们来看Redis,它是一个开源的、高性能的...

    Java实现的最大匹配法统计词频

    本篇文章将深入探讨如何使用Java实现最大匹配法来统计词频,并基于提供的Eclipse工程进行详细解析。 最大匹配法分为前向最大匹配和后向最大匹配。前向最大匹配是从文本的起始位置开始,尝试匹配尽可能长的词语;...

    java-基于redis限流系统

    Redis提供了丰富的数据结构,如字符串、哈希表、列表、集合以及有序集合,这些都可以用来实现不同的限流算法,如滑动窗口算法、漏桶算法和令牌桶算法。 1. **滑动窗口算法**:它基于时间窗口对请求进行计数,超过...

    apriori算法及常见java算法

    前者可能是实现Apriori算法的Java源代码,后者可能是包含交易数据的数据文件,用于运行算法并测试结果。通过阅读和分析这些文件,我们可以深入了解Apriori算法的具体实现和数据格式,同时也可以加深对Java编程的理解...

    timehash:一种用于创建用户可配置的,可变精度的时间滑动窗口的算法。 对大量数据中的时间值进行装箱很有用

    在实现上,`timehash`通常使用哈希函数来将时间戳转化为整数,这个整数代表了时间值在滑动窗口中的位置。哈希函数的选择应确保在分布式环境中的一致性,以确保不同节点对相同时间值的处理结果相同。哈希函数还需要...

    java连连看游戏源代码

    Java连连看游戏源代码是一个基于Java编程语言实现的桌面游戏,它通过图形用户界面(GUI)为玩家提供了一个直观的游戏体验。在这个项目中,开发者利用Java的Swing库或者JavaFX来构建游戏界面,实现图像的展示、点击...

    小游戏Java课程设计报告书.pdf

    在Java Swing中,窗口布局通常使用边界布局(BorderLayout)、卡片布局(CardLayout)、网格布局(GridLayout)等。 从文档内容来看,游戏设计报告书详细描述了游戏的实现过程,包括游戏设计思路、编程实现、界面...

    【java面试系列】服务的限流.pdf

    **优点**:相比固定窗口算法,滑动窗口算法更加平滑地处理了请求的瞬时高峰,避免了固定窗口算法可能出现的瞬间过载问题。 **缺点**:实现相对复杂,需要维护更多的数据结构。 **示例代码**: ```java public class...

    Redis+lua+AOP实现简单的限流

    固定窗口限流会在特定时间间隔内限制请求的数量,而滑动窗口限流则会连续划分多个小的时间窗口,每个窗口都有独立的请求配额。在此案例中,我们可能采用的是滑动窗口限流,因为这种方式可以更精确地控制瞬时流量。 ...

    java-game-of-life-源码.rar

    为了优化性能,可以使用滑动窗口或者邻接矩阵来计算。 对于Java实现,多线程可以用来并行处理网格的不同部分,提高效率。例如,使用ExecutorService和Callable接口,将计算任务分发给多个工作线程。这样可以充分...

    限流代码脚本

    2. 滑动窗口限流:相对于固定窗口,滑动窗口将时间周期分成多个小窗口,并对每个小窗口内的请求进行计数。这种方式可以更好地平滑请求,减少突刺现象,但实现起来相对复杂。 3. 令牌桶算法:系统会按照一定的速率向...

    Java网络开发--TCP协议

    Java网络开发中,TCP协议是基础且至关重要的部分。TCP(传输控制协议)是一种面向连接的...同时,了解TCP的特性如滑动窗口、拥塞控制和流量控制等,可以帮助开发者更好地解决网络延迟、数据丢失等问题,优化应用性能。

    关于Java面试题小集锦

    滑动窗口通常用于统计特定时间内元素的聚合信息,如最大值、最小值或计数。 10. **InnoDB 和 MyISAM的区别** InnoDB支持事务和行级锁,适合并发场景;MyISAM不支持事务,但读取速度较快,适用于读多写少的场景。 ...

    java经典面试题

    20. **Java 多态的实现原理**: - 通过方法覆盖(重写)和方法重载来实现。 - 在运行时根据对象的实际类型来确定调用哪个方法。 21. **实现多线程的两种方法**: - 继承 `Thread` 类。 - 实现 `Runnable` 接口...

    jishuqi.zip_计数器

    - 滑动窗口计数:在分析实时流量或限制请求频率时,可能需要在特定时间窗口内计算事件次数,这需要一种能够随着时间窗口移动而自动清理过期计数的方法。 在“jishuqi”这个文件中,我们可以期待找到一个基础的...

    RLE.rar_RLE_RLE的java编码_RLE编码_rle 算法_rle压缩

    - **更高效的扫描机制**:优化数据扫描过程,例如使用双指针或滑动窗口来快速检测重复元素。 - **自定义编码格式**:可能使用特定的编码格式来表示重复信息,以节省更多空间。 - **错误检测与恢复**:添加校验码或...

    统计最近N分钟的热门商品TOP data.zip

    滑动窗口每隔N分钟开始一个新的窗口,并且每个窗口的大小也是N分钟,这样可以确保每个窗口内的数据都是最近N分钟的。例如,`timeWindow(Time.minutes(N))`。 4. **聚合操作(Aggregation)**:在每个时间窗口内,...

    实时计算知多少?

    在实现滑动窗口计数时,通常会用到分布式流处理框架,如Apache Storm。Storm提供了处理实时数据流的能力,并允许开发者定义拓扑结构来处理数据。在上述代码片段中,`setup-ticks!`函数用于设置时间间隔(`tick-time-...

    精选java网络编程面试题

    - 流量控制:利用滑动窗口机制来防止发送方的数据发送速率超过接收方的处理能力。 - 拥塞控制:在网络拥堵时减少数据包的发送速率,以避免网络拥塞进一步恶化。 - **UDP(User Datagram Protocol,用户数据报协议...

Global site tag (gtag.js) - Google Analytics