algorithme évolutif pour détecter des données périmées

Question

Voici le problème:

« Agents » installés sur de nombreux serveurs différents envoyer des signaux « rythme cardiaque » à un serveur central toutes les 5 secondes. Comment puis-je trouver activement ceux qui ont manqué leur rythme cardiaque pendant plus de 10 secondes et déclencher une alerte?

Le problème est simple si vous ne pensez pas à l'évolutivité. Dans la forme la plus simple, vous pouvez enregistrer l'horodatage des dernières pulsations reçues de chaque agent dans une table de base de données et exécuter une requête régulière pour trouver celles qui sont antérieures au seuil.

Cette solution n'est cependant pas évolutive pour des millions d'agents. Je recherche des algorithmes ou des technologies qui me permettent de le faire. Je suis à la recherche d'algorithmes ou de technologies qui me permettront d'atteindre ce but.

Answer 1

1. Utiliser une carte: AgentID -> LastHearbeatTime
2. utilisation 11 ensembles (en supposant une résolution de 1 seconde est suffisante), chacun détient Ids des agents rapporté dans une fenêtre de 1 seconde.

Chaque fois que signaler un agent d'un hearthbeat: 1. Trouvez sur la carte 2. supprimer de l'ensemble pertinent 3. Mise à jour dans la carte 4. Ajouter à l'ensemble pertinent

Définition d'un fil: Une fois par seconde, l'ensemble le plus ancien expire. Ça devrait être vide. Si ce n'est pas le cas, il contient les ID des agents qui n'ont pas signalé. Une fois qu'un ensemble expire, vous pouvez le réutiliser (tableau cyclique d'ensembles). Je crois qu'il peut être mis en œuvre sans verrous (peut-être vous aurez besoin de 12 jeux).

Answer 2

MongoDB est idéal pour ce type d'utilisation. Bien qu'il ne s'agisse pas exactement d'un algorithme, il convient à la technologie fondamentale nécessaire pour créer ce service. Nous l'utilisons ici chez CopperEgg pour que notre produit RevealCloud fasse exactement ce que vous dites - nous envoyons une alerte lorsque le système est parti pour un peu de temps - l'échantillonnage toutes les 5 secondes. J'aimerais en savoir plus sur vos pensées et votre cas d'utilisation. Pouvez-vous fournir plus de détails?

Answer 3

Sans connaître le langage et la plate-forme, il est quelque peu difficile de vous conseiller sur une implémentation détaillée, mais mon conseil est assez similaire à celui de Lior Kogan. À mon avis, cependant, il vous suffit de deux ensembles et aucune carte est impliqué:

que vous avez deux variables représentant des ensembles, A et B.

Chaque battement de coeur supprime l'identifiant de l'agent de jeu A. Chaque 5 secondes, un thread différent déclenche une alerte pour chaque identifiant d'agent dans B, puis définit B = A, et crée un ensemble avec tous les identifiants d'agent et définit A comme égal (si le nombre d'ID d'agent est vraiment grand, vous pouvez préparer le nouveau jeu entre un chèque et l'autre et seulement dormir pour le temps restant). Le verrouillage ne serait nécessaire que lors de la modification des variables pointant sur chaque ensemble, à condition que vous utilisiez une collection de jeux sans verrou. Les performances dépendront largement de la complexité algorithmique de cette implémentation, et si vous descendez de cette façon, vous devriez privilégier celui avec les meilleures performances (pas nécessairement le meilleur big-O, par exemple si la latence wost-case vous importe) pour les suppressions .En remarque, si la mémoire n'est pas un problème ou si les échecs sont relativement peu nombreux, quand vous vérifiez si vous avez besoin d'élever des alertes et faites-le, vous pouvez le faire sur un thread et obtenir des gains de performance potentiellement intéressants (encore une fois, la plate-forme et le runtime importent, car dans erlang ce serait un jeu d'enfant, mais dans Windows, le coût de création d'un nouveau thread peut dépasser les performances si les échecs sont rares) au détriment de l'ancien jeu B en mémoire.