Aceleración de llamadas a métodos a M peticiones en N segundos

Lo que funcionó fuera de la caja para mí fue Google Guava RateLimiter.

// Allow one request per second
private RateLimiter throttle = RateLimiter.create(1.0);

private void someMethod() {
    throttle.acquire();
    // Do something
}

En términos concretos, debería ser capaz de implementar esto con un DelayQueue. Inicializar la cola con M Delayed instancias con su retardo establecido inicialmente en cero. A medida que las solicitudes al método entran, take un token, que hace que el método se bloquee hasta que se cumpla el requisito de limitación. Cuando se ha tomado un token, add un nuevo token a la cola con un retraso de N.

Lea el algoritmo Token bucket. Básicamente, tienes un cubo con fichas en él. Cada vez que ejecuta el método, toma un token. Si no hay más tokens, bloquearás hasta que consigas uno. Mientras tanto, hay algún actor externo que repone los tokens en un intervalo fijo.

No tengo conocimiento de una biblioteca para hacer esto (o algo similar). Puedes escribir esta lógica en tu código o usar AspectJ para agregar el comportamiento.

Esto depende de la aplicación.

Imagine el caso en el que múltiples hilosquieren que un token realice una acción globalmente limitadacon no se permite ráfaga (es decir, desea limitar 10 acciones por 10 segundos, pero no desea que 10 acciones ocurran en el primer segundo y luego permanezcan 9 segundos detenidos).

El DelayedQueue tiene una desventaja: el orden en el que los tokens de solicitud de subprocesos pueden no ser el orden en el que reciben su solicitud cumplido. Si se bloquean varios hilos esperando un token, no está claro cuál tomará el siguiente token disponible. Incluso podrías tener hilos esperando para siempre, en mi punto de vista.

Una solución es tener un intervalo mínimo de tiempo entre dos acciones consecutivas, y tomar acciones en el mismo orden que se solicitaron.

Aquí está una implementación:

public class LeakyBucket {
    protected float maxRate;
    protected long minTime;
    //holds time of last action (past or future!)
    protected long lastSchedAction = System.currentTimeMillis();

    public LeakyBucket(float maxRate) throws Exception {
        if(maxRate <= 0.0f) {
            throw new Exception("Invalid rate");
        }
        this.maxRate = maxRate;
        this.minTime = (long)(1000.0f / maxRate);
    }

    public void consume() throws InterruptedException {
        long curTime = System.currentTimeMillis();
        long timeLeft;

        //calculate when can we do the action
        synchronized(this) {
            timeLeft = lastSchedAction + minTime - curTime;
            if(timeLeft > 0) {
                lastSchedAction += minTime;
            }
            else {
                lastSchedAction = curTime;
            }
        }

        //If needed, wait for our time
        if(timeLeft <= 0) {
            return;
        }
        else {
            Thread.sleep(timeLeft);
        }
    }
}

Si necesita un limitador de velocidad de ventana deslizante basado en Java que operará en un sistema distribuido, es posible que desee echar un vistazo a https://github.com/mokies/ratelimitj proyecto.

Una configuración respaldada por Redis, para limitar las solicitudes por IP a 50 por minuto se vería así:

import com.lambdaworks.redis.RedisClient;
import es.moki.ratelimitj.core.LimitRule;

RedisClient client = RedisClient.create("redis://localhost");
Set<LimitRule> rules = Collections.singleton(LimitRule.of(1, TimeUnit.MINUTES, 50)); // 50 request per minute, per key
RedisRateLimit requestRateLimiter = new RedisRateLimit(client, rules);

boolean overLimit = requestRateLimiter.overLimit("ip:127.0.0.2");

Véase https://github.com/mokies/ratelimitj/tree/master/ratelimitj-redis para más detalles sobre la configuración de Redis.

Aunque no es lo que pediste, ThreadPoolExecutor, que está diseñado para limitar a M solicitudes simultáneas en lugar de M solicitudes en N segundos, también podría ser útil.

La pregunta original se parece mucho al problema resuelto en esta publicación del blog: Java Multi-Channel Asynchronous Throttler.

Para una tasa de M llamadas en N segundos, el regulador discutido en este blog garantiza que cualquier intervalo de longitud N en la línea de tiempo no contendrá más de M llamadas.

He implementado un algoritmo de limitación simple.Pruebe este enlace, http://krishnaprasadas.blogspot.in/2012/05/throttling-algorithm.html

Un resumen sobre el Algoritmo,

Este algoritmo utiliza la capacidad de Java Delayed Queue. Cree un objeto delayed con el retraso esperado (aquí 1000/M para el milisegundo TimeUnit). Coloque el mismo objeto en la cola retrasada que nos proporcionará la ventana de movimiento. Luego, antes de cada method call take el objeto forma la cola, take es una llamada de bloqueo que regresará solo después del retraso especificado, y después de la llamada al método no olvide poner el objeto en la cola con el tiempo actualizado(aquí milisegundos actuales).

Aquí también podemos tener múltiples objetos retrasados con diferente retraso. Este enfoque también proporcionará un alto rendimiento.

Necesito asegurarme de que mi método es ejecutado no más de M veces en a ventana corredera de N segundos.

Recientemente escribí una entrada de blog sobre cómo hacer esto en .NET. Es posible que pueda crear algo similar en Java.

Mejor Limitación de velocidad en. NET

Intente usar este enfoque simple:

public class SimpleThrottler {

private static final int T = 1; // min
private static final int N = 345;

private Lock lock = new ReentrantLock();
private Condition newFrame = lock.newCondition();
private volatile boolean currentFrame = true;

public SimpleThrottler() {
    handleForGate();
}

/**
 * Payload
 */
private void job() {
    try {
        Thread.sleep(Math.abs(ThreadLocalRandom.current().nextLong(12, 98)));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.err.print(" J. ");
}

public void doJob() throws InterruptedException {
    lock.lock();
    try {

        while (true) {

            int count = 0;

            while (count < N && currentFrame) {
                job();
                count++;
            }

            newFrame.await();
            currentFrame = true;
        }

    } finally {
        lock.unlock();
    }
}

public void handleForGate() {
    Thread handler = new Thread(() -> {
        while (true) {
            try {
                Thread.sleep(1 * 900);
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                currentFrame = false;

                lock.lock();
                try {
                    newFrame.signal();
                } finally {
                    lock.unlock();
                }
            }
        }
    });
    handler.start();
}

}

Apache Camel también soporta viene con Throttler mecanismo de la siguiente manera:

from("seda:a").throttle(100).asyncDelayed().to("seda:b");

Puede usar redis para esto cuando se necesita bloqueo en el sistema distribuido. Segundo algoritmo en https://redis.io/commands/incr

Esta es una actualización del código LeakyBucket anterior. Esto funciona para más de 1000 solicitudes por segundo.

import lombok.SneakyThrows;
import java.util.concurrent.TimeUnit;

class LeakyBucket {
  private long minTimeNano; // sec / billion
  private long sched = System.nanoTime();

  /**
   * Create a rate limiter using the leakybucket alg.
   * @param perSec the number of requests per second
   */
  public LeakyBucket(double perSec) {
    if (perSec <= 0.0) {
      throw new RuntimeException("Invalid rate " + perSec);
    }
    this.minTimeNano = (long) (1_000_000_000.0 / perSec);
  }

  @SneakyThrows public void consume() {
    long curr = System.nanoTime();
    long timeLeft;

    synchronized (this) {
      timeLeft = sched - curr + minTimeNano;
      sched += minTimeNano;
    }
    if (timeLeft <= minTimeNano) {
      return;
    }
    TimeUnit.NANOSECONDS.sleep(timeLeft);
  }
}

Y la prueba unitaria para arriba:

import com.google.common.base.Stopwatch;
import org.junit.Ignore;
import org.junit.Test;

import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

public class LeakyBucketTest {
  @Test @Ignore public void t() {
    double numberPerSec = 10000;
    LeakyBucket b = new LeakyBucket(numberPerSec);
    Stopwatch w = Stopwatch.createStarted();
    IntStream.range(0, (int) (numberPerSec * 5)).parallel().forEach(
        x -> b.consume());
    System.out.printf("%,d ms%n", w.elapsed(TimeUnit.MILLISECONDS));
  }
}

Echa un vistazo a [TimerTask1 clase. O el ScheduledExecutor.