0

我必须实现一个限制算法，以避免达到我正在与之交互的服务所施加的吞吐量限制。

限制指定为«N requests over 1 day»，其中 N 的数量级为 10^6。

我有一个客户端与服务交互的分布式系统，因此他们应该共享度量。

一个确切的解决方案应该涉及记录所有事件，而不是计算调用服务事件发生的“时间”限制：当然，这种方法太昂贵了，所以我正在寻找一个近似的解决方案。

我设计的第一个意味着对事件的检测进行离散化：例如，最多维护 24 个计数器并记录一小时内发生的请求数。

可以接受。

但我觉得一个更优雅的，即使是由不同的“力量”领导，是拒绝接近连续体的方法。

假设记录最后 N 个事件，我可以轻松推断出“当前”吞吐量。当然，这个算法会因为错过了几个小时前发生的过去事件而受到影响。我可以使用老化算法进行改进，但是……下面是我的问题：

问：«有一个优雅的近似解决方案来估计长时间和高事件率的服务吞吐量的问题？»

4

1 回答 1

0

根据我的评论，您应该使用监视器并让它每 15 分钟对值进行一次采样，以合理猜测请求的数量。

我在这里嘲笑了一些东西，但还没有测试过，应该给你一个首发。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Timer;
import java.util.TimerTask;

public class TestCounter {

private final Monitor monitor;

private TestCounter() {
    monitor = new Monitor();
}

/** The thing you are limiting */
public void myService() {
    if (monitor.isThresholdExceeded()) {
        //Return error
    } else {
        monitor.incremenetCounter();
        //do stuff
    }
}

public static void main(String[] args) {
    TestCounter t = new TestCounter();
    for (int i = 0; i < 100000; i++) {
        t.myService();
    }

    for (int i = 0; i < 100000; i++) {
        t.myService();
    }
}

private class Monitor {
    private final Queue<Integer> queue = new LinkedList<Integer>();

    private int counter = 1;

    /** Number of 15 minute periods in a day. */
    private final int numberOfSamples = 76;

    private final int threshold = 1000000;

    private boolean thresholdExceeded;

    public Monitor() {
        //Schedule a sample every 15 minutes.
        Timer t = new Timer();
        t.scheduleAtFixedRate(new TimerTask() {
            @Override
            public void run() {
                sampleCounter();
            }
        }, 0l, 900000 /** ms in 15 minutes */
        );
    }

    /** Could synchroinise */
    void incremenetCounter() {
        counter++;
    }

    /** Could synchroinise */
    void sampleCounter() {
        int tempCount = counter;
        counter = 0;
        queue.add(tempCount);

        if (queue.size() > numberOfSamples) {
            queue.poll();
        }

        int totalCount = 0;
        for (Integer value : queue) {
            totalCount += value;
        }
        if (totalCount > threshold) {
            thresholdExceeded = true;
        } else {
            thresholdExceeded = false;
        }
    }

    public boolean isThresholdExceeded() {
        return thresholdExceeded;
    }
}
}
于 2013-03-28T14:08:30.847 回答