Avantage de l'algorithme de débit de cellules génériques sur l'algorithme de seau en fuite

Question

Je recherche un algorithme pour limiter les demandes entrantes à un serveur HTTP REST. Je suis passé par le "seau Leaky" & "Generic Cell Rate Algorithm: Schedulling virtuel"

Selon ma compréhension Leaky Bucket présente les limites suivantes: -

1. Si la file d'attente/seau est vide et la La requête arrive avant l'horloge (lorsque nous sommes en train de traiter une requête) alors la requête doit attendre le temps jusqu'à ce que l'horloge corresponde.
2. paquets de longueur variable dans le domaine du réseau

Je suis passé par cette blog qui implémente "Cell Rate générique algorithme: Schedulling virtuel".

peut me expliquer certains les éléments suivants: -

1. Comment fonctionne GCRA résout la limitation de Leaky Bucket comme mentionné dans # 1?
2. Dans mon cas d'utilisation, si je mets l'horloge à l'état bas (peut être vérifié toutes les nanosecondes), le problème avec Leaky Bucket ne devrait-il pas être atténué?

Answer 1

L'algorithme de compartiment de fuite a deux variantes, meter et queue. Le mètre est plus pertinent ici, alors concentrons-nous là-dessus.

L'idée est qu'un godet se voit attribuer un taux d'égouttage (soit uniforme dans les compartiments, soit basé sur un niveau). Un travail qui arrive a un certain "volume" associé. Il peut soit entrer dans le seau ou non. Si ce n'est pas le cas, il est rejeté. Si cela correspond, il est transmis pour traitement (au moins dans la version du compteur).

Qui est responsable de l'égouttage du seau? Le blog que vous avez mentionné prétend que cela est généralement fait par un processus de fond, qui circule autour des seaux et les égoutte. Il mentionne l'inconvénient que si le taux auquel il peut traiter les seaux est faible (avec le cas extrême de sa déconnexion), un travail peut être rejeté non pas parce qu'il n'y a pas assez de volume vide appartenant au seau, mais parce que le dégouttement processus ne l'a pas mis à jour. C'est fondamentalement votre point 1; Je ne vois pas le problème avec votre point 2 (bien que vous ayez pu lire une description de l'un des zillions de versions de bucket leaky qui est contraint à des volumes uniformes, mais rien d'inhérent à l'algorithme ne l'exige).

C'est là qu'intervient GCRA. Si vous y réfléchissez, un processus d'égouttage distinct n'est pas vraiment nécessaire. Si vous effectuez le suivi, dans un compartiment, de l'état actuel et d'un travail, vous pouvez calculer la prochaine fois qu'il y aura suffisamment de volume vide pour une taille de travail future donnée. Ainsi, quand un travail arrive, il vérifie juste s'il est venu avant ou après cette heure. S'il est venu avant, il est rejeté. S'il vient après, il est laissé passer, et les temps-jusqu'à-prochains-travaux sont mis à jour.

En ce qui concerne vos questions (qui sont liés):

1. Depuis avec GCRA vous ne comptez pas sur un processus distinct pour les gouttes, vous ne rencontrerez pas un problème où il est mort ou juste couldn » Tais-toi.Cela conduit au point suivant: en particulier,

2. Si vous exécutez un processus séparé avec une fréquence très élevée, alors, tant que le processus d'égouttage se maintient, tout va bien. Avec une fréquence élevée, cependant, il y a une chance que le processus d'égouttage ne continue pas.

---

Notez qu'il n'y a pas de repas gratuits, cependant. Quelle que soit la puissance de traitement que vous avez, quelqu'un doit vérifier le volume vide et mettre à jour les gouttes. YMMV. Pour certains paramètres et implémentations, il est facile d'imaginer où un processus d'égouttage séparé (en supposant que quelqu'un a bien conçu le système et qu'il ne se déconnecte pas) donne un système avec une latence globale inférieure, un débit supérieur ou les deux. D'autres paramètres et implémentations peuvent avoir le contraire.