Comment mettre à l'échelle un algorithme/service/système avec plusieurs machines?

Question

J'ai récemment eu quelques entrevues et il est tout à fait normal qu'on me pose des problèmes d'échelle. Par exemple, vous avez une longue liste de mots (dict) et une liste de caractères comme entrées, concevez un algorithme pour trouver le mot le plus court qui contient dans dict tous les caractères de la liste de caractères. Ensuite, l'intervieweur a demandé comment mettre à l'échelle votre algorithme sur plusieurs machines. Un autre exemple est que vous avez conçu un système de contrôle de feux de circulation pour une intersection dans une ville. Comment pouvez-vous mettre à l'échelle ce système de contrôle à toute la ville qui a de nombreuses intersections. Je n'ai toujours aucune idée de ce genre de problèmes "d'échelle", bienvenue vos suggestions et commentaires.

Answer 1

Votre première question est complètement différente de votre deuxième question. En fait, le contrôle des feux de circulation dans les villes est une opération locale. Il y a des boîtes à proximité que vous pouvez régler et un capteur optique sur le dessus de la lumière qui détecte les voitures en attente. Je suppose que si vous avez besoin d'optimiser pour une fonction objective de flux, vous pouvez router des informations vers un processus serveur, puis il peut devenir comment faire évoluer ce processus serveur sur plusieurs machines.

Je ne suis pas un expert en conception d'algorithmes distribués, qui couvre tout un champ de recherche. Mais les questions des entrevues de premier cycle ne sont généralement pas spécialisées. Après tout, ils n'interrogent pas un étudiant diplômé spécialisé dans ces domaines. Prenez votre première question par exemple, c'est assez générique.

Normalement, ces questions impliquent plusieurs structures de données (plusieurs listes et tables de hachage) interagissant (se rejoignant, itérant, etc.) pour résoudre un problème. Une fois que vous avez élaboré une solution de base, la mise à l'échelle consiste essentiellement à copier cette solution sur de nombreuses machines et à les exécuter avec des partitions de l'entrée en même temps. (Bien sûr, dans de nombreux cas, c'est difficile sinon impossible, mais les questions d'entrevue ne seront pas si difficiles)

Autrement dit, vous avez beaucoup de travailleurs identiques qui partagent la charge de travail en entrée et travaillent en même temps, mais ces travailleurs sont des processus dans différentes machines. Cela amène le problème du protocole de communication et de la latence du réseau, etc., mais nous allons les ignorer pour en arriver aux bases. La manière la plus courante de mettre à l'échelle consiste à laisser les travailleurs conserver des copies de structures de données plus petites et à répartir les plus grandes structures de données en charge de travail. Dans votre exemple (première question), la liste des caractères est de petite taille, donc vous donneriez à chaque employé une copie de la liste, et une partie du dictionnaire pour travailler avec la liste. Notez que l'inverse ne fonctionnera pas, parce que chaque travailleur possédant un dictionnaire consommera une grande quantité de mémoire au total, et cela ne vous sauvera rien. Si votre problème s'aggrave, vous aurez peut-être besoin de plus de couches de séparation, ce qui implique également que vous ayez besoin d'un moyen de combiner les sorties des travailleurs prenant l'entrée fractionnée. C'est le concept général et la motivation pour le framework MapReduce et ses dérivés.

Hope it helps ...

Answer 2

Pour la première question, comment rechercher des mots qui contiennent tous les ombles dans la liste char qui peut fonctionner sur le même temps sur la machine différente. (Pas encore le plus court). Je le ferai avec map-reduce comme base. Tout d'abord, ce problème peut en fait s'exécuter sur une machine différente en même temps. C'est parce que pour chaque mot dans la base de données, vous pouvez le vérifier sur une autre machine (pour vérifier un autre mot, vous n'avez pas à attendre le mot précédent ou le mot suivant, vous pouvez littéralement envoyer chaque mot à un autre ordinateur être vérifié).

En utilisant map-reduce, vous pouvez map chaque mot comme value puis de le vérifier s'il contient tous les caractères de la liste de caractères.

Map(Word, keyout, valueout){ 
    //Word comes from dbase, keyout & valueout is input for Reduce 
    if(check if word contain all char){ 
     sharedOutput(Key, Word)//Basically, you send the word to a shared file. 
    //The output shared file, should be managed by the 'said like' hadoop 
    } 
} 

Après cette course Map, vous obtenez toute la Parole que vous voulez à partir de la base de données locate dans le fichier partagé. En ce qui concerne l'étape reduce, vous pouvez réellement utiliser une étape simple pour la réduire en fonction de sa longueur. Et tada, vous obtenez le plus court. En ce qui concerne la deuxième question, le multi threading me vient à l'esprit. C'est en fait un problème qui ne se rapporte pas les uns aux autres. Je veux dire que chaque intersection a sa propre horloge? Donc, pour être capable de gérer des tonnes d'intersection, vous devez utiliser multi threading.

Le terme simple utilisera chaque cœur dans le processeur pour contrôler chaque intersection. Plutôt que d'aller en boucle à travers toute l'intersection par un. Vous pouvez les alocaliser dans chaque cœur afin que le processus soit plus rapide.