Мера пропускной способности

Question

Я должен реализовать алгоритм ограничения, чтобы избежать ограничения пропускной способности, налагаемого службой, с которой я взаимодействую.

Предел указывается как "N запросов за 1 день", где N порядка 10^6.

У меня есть распределенная система клиентов, взаимодействующих с сервисом, поэтому они должны разделять измерения.

Точное решение должно включать запись всех событий, а затем вычисление предела "когда" происходит событие вызова службы: конечно, этот подход слишком дорог, и поэтому я ищу приблизительное решение.

Первый, который я разработал, подразумевает дискретизацию обнаружения событий: например, поддержание максимум 24 счетчиков и запись количества запросов, произошедших в течение часа.

Приемлемый.

Но я чувствую, что более элегантным, хотя и ведомым разными "силами", является отклонение подхода от континуума.

Допустим, записывая последние N событий, я мог легко вывести "текущую" пропускную способность. Конечно, этот алгоритм страдает из-за отсутствия учета прошлых событий, произошедших часами ранее. Я мог бы улучшить с помощью алгоритма старения, но... и вот мой вопрос:

Вопрос: "Существует элегантное приблизительное решение проблемы оценки пропускной способности услуги в течение длительного периода при высокой частоте событий?"

Answer 1

Согласно моим комментариям, вы должны использовать монитор и каждые 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;
    }
}
}