J'ai un environnement qui sert de nombreux appareils répartis sur 3 fuseaux horaires en recevant et en envoyant des données pendant les petites heures de la nuit. La distribution de ces dispositifs a été déterminée pseudo-aléatoire sur la base d'un numéro d'identification et d'un calcul simple à l'aide d'une opération de modulo. Le résultat d'un tel calcul crée un pic artificiel inutile qui consomme plus de ressources que je voudrais pendant certaines heures de la nuit.
Dans le cadre de notre protocole, je peux instruire des périphériques lorsque vous pouvez vous connecter à notre système les nuits ultérieures.
Je cherche un algorithme qui peut généralement distribuer le pic en une ligne de plus niveau (bien généralement plus élevée à la plupart des temps) ou au moins une poussée dans la bonne direction - ce qui signifie quel type de terminologie devrais-je passer mon temps à lire. Je me suis disponible pour moi des numéros d'identification pour les périphériques, l'heure actuelle et le fuseau horaire de l'appareil en tant qu'entrées pour effectuer des calculs. Je peux également effectuer des calculs analytiques avant de créer des piscines à partir de laquelle dessiner des machines à sous, même si je pense que cette approche peut être moins élégante que celle que j'espérise (bien qu'un algorithme d'apprentissage ne soit pas une mauvaise chose ...). < / p>
(finalement et quelque peu moins pertinent, je mettrai en place cet algorithme à l'aide de C #.)
3 Réponses :
Vous dites que vous pouvez dire aux appareils à quelle heure de connexion, donc je ne vois pas pourquoi vous avez besoin de quelque chose de hasard ou de modulable. Lorsque chaque appareil se connecte, choisissez une heure demain, ce qui ne dispose pas de nombreux périphériques qui lui sont attribués et attribuent l'appareil à ce temps. Si les appareils prennent tous environ la même quantité de ressources au service, une algorithme gourmande triviale produira une distribution complètement lisse - attribuer chaque appareil à la même manière que le temps est actuellement le moins encombré. Si le serveur gère d'autres travaux que de simplement ces périphériques, vous souhaiteriez commencer par son profil de charge typique, puis ajoutez la charge de l'appareil à cela. Je n'appellerais pas vraiment ces "calculs analytiques", il suffit de stocker un histogramme de charge attendue contre le temps pour les 24 prochaines 24 heures.
ou avez-vous le problème que l'appareil ne peut pas obéir aux instructions (par exemple, il pourrait être déconnecté à sa durée attribuée, puis connectez-vous chaque fois qu'il est suivant)? Évidemment, si vos utilisateurs dans un fuseau horaire particulier commencent tous les travaux en même temps le matin, ce serait une stratégie problématique.
Le problème avec cela est qu'il a une composante boucle de rétroaction. Si le premier soir, il arrive que 2h du matin est le moins occupé, il allouera des ressources à 2h du matin. Cela fera 2h du matin le plus occupé si le trafic accessoire a été alloué au hasard que la première nuit, elle planifiera donc tout à partir de 2h du matin, ce qui entraînera une utilisation inefficace du temps d'environ 2 heures du matin. À moins qu'une distribution stable du trafic accessoire ne soit réalisable, la répartition uniforme entre les intervalles sera toujours optimale.
Si l'heure actuelle est actuellement la durée la plus occupée (disons, 1,5 million de hits) et 2h du moindre occupé (par exemple, 0,5 million de hits), alors ma suggestion est de demander à 0,5 million de 1 million des 1hitters de frapper à 2 heures du matin à l'avenir. Je ne vois pas comment cela a une boucle de rétroaction: il suffit de garder une gamme de seaux contenant un entier, "Combien de hits sont programmés pour cette heure demain" et remplissez ces seaux uniformément. Il n'y a pas de sur-compensation, à moins que vous n'utilisiez l'algorithme défectueux "Combien de hits sont programmés pour cette heure demain, non compris ceux que j'ai déjà déplacés d'autres fois ". Alors ne fais pas ça.
Prenez simplement le nombre d'appareils et divisez votre intervalle de temps dans N segments égaux et allouez chaque segment à un périphérique, en l'informant de la connexion lorsqu'ils se connectent ensuite.
Cela vous donnera une distribution optimale uniforme dans tous les cas.
normaliser tout temps à GMT, que vous souciez-vous des fuseaux horaires ou des économies de lumière de jour ou quoi que ce soit? Est maintenant peu importe quel fuseau horaire vous êtes.
L'ajout d'une distribution aléatoire peut entraîner une exploration (une distribution aléatoire uniforme n'est qu'un uniforme dans la limite, mais pas nécessairement pour un échantillon particulier), et doit vraiment être utilisé s'il n'y a pas de mécanisme de rétroaction. Puisque vous pouvez contrôler dans une certaine mesure quand ils connectent un composant aléatoire ne sont pas du tout nécessaires et ne sont même pas optimaux à distance.
Si vous êtes préoccupé par la dérive d'horloge à travers les périphériques, considérez même si vous avez ajouté au hasard, cela ne diminuerait aucune manière le hasard de votre dérive d'horloge et ne contribuerait à une allocation encore moins optimale.
Si vous souhaitez assurer une distribution stable de périphériques par région, calculez le rapport entre les périphériques par région et distribuer les allocations de machines à sous de manière appropriée. Par exemple, si vous avez respectivement 50/25/25 par zone temporelle, attribuez des emplacements au premier fuseau horaire, puis les deux emplacements suivants aux zones de temps restants, puis répétez.
Si vous souhaitez éviter les pointes associées à l'utilisation de temps aléatoires, regardez les différentes fonctions de hachage utilisées pour les hachons. Votre lecture pourrait commencer aux articles Wikipedia sur le sujet:
http://fr.wikipedia.org/wiki/hash_function
Fondamentalement, divisez tout ce que vous souhaitez que votre fenêtre de mise à jour soit dans le nombre de godets approprié. Une option peut être 3 heures * 60 minutes * 60 secondes = 10800 godets. Ensuite, utilisez-le comme une taille de hashtable, pour la fonction de hachage choisie. Votre entrée unique pourrait être une carte d'identité du périphérique. N'oubliez pas d'utiliser GMT pour l'heure choisie. Votre langage de programmation a probablement un certain nombre de fonctions de hachage intégrées, mais l'article doit fournir des liens pour vous aider à démarrer si vous souhaitez en implémenter un de zéro.
Cette approche est supérieure à la réponse antérieure des temps d'accès aléatoires, car il a beaucoup de meilleures propriétés de la vie, et garantit que vos modèles d'accès seront approximativement à plat, par rapport à la fonction aléatoire qui est probable. parfois expose des pointes.
Voici quelques informations plus spécifiques sur la mise en œuvre de différentes fonctions:
http://www.partow.net/programming/hashfonctions/index.html < / a>
Je ne trouve pas l'explication du problème complètement clair? Que distribuons-nous? Comment une répartition aléatoire (plus ou moins) peut-elle entraîner une importante pic? Que se passerait-il si la distribution était une simple ronde-robine?
Le pic est créé artificiellement en raison des fuseaux horaires et de l'opération de modulo.