Struttura dati per la selezione di gruppi di macchine

Question

Ho questo vecchio sistema batch. Lo scheduler memorizza tutti i nodi computazionali in un unico grande array. Ora va bene per la maggior parte, perché la maggior parte delle query può essere risolta filtrando per i nodi che soddisfano la query.

Il problema che ho ora è che oltre a alcune proprietà di base (numero di cpus, memoria, sistema operativo), ci sono anche queste strane proprietà di raggruppamento (città, infiniband, rete zero).

Ora il problema con questi è che quando un utente richiede nodi con infiniband non posso dargli solo dei nodi, ma devo dargli dei nodi collegati a uno switch infiniband, così i nodi possono effettivamente comunicare usando infiniband.

Questo è ancora OK, quando l'utente richiede una sola di tali proprietà (posso solo partizionare l'array per ciascuna delle proprietà e quindi provare a selezionare i nodi in ogni partizione separatamente).

Il problema si presenta con la combinazione di più di tali proprietà, poiché in tal caso dovrei generare tutte le combinazioni di sottoinsiemi (partizioni dell'array principale).

La cosa buona è che la maggior parte delle proprietà si trova in una sottosistema o in una relazione di equivalenza (ha senso per le macchine su un interruttore infiniband essere in una città). Ma questo purtroppo non è assolutamente vero.

Esiste una buona struttura dati per archiviare questo tipo di elemento semi-gerarchico per lo più ad albero?

EDIT: esempio

node1 : city=city1, infiniband=switch03, networkfs=server01 
node2 : city=city1, infiniband=switch03, networkfs=server01 
node3 : city=city1, infiniband=switch03 
node4 : city=city1, infiniband=switch03 
node5 : city=city2, infiniband=switch03, networkfs=server02 
node6 : city=city2, infiniband=switch03, networkfs=server02 
node7 : city=city2, infiniband=switch04, networkfs=server02 
node8 : city=city2, infiniband=switch04, networkfs=server02 

utenti richiedono:

2x node with infiniband and networkfs 

L'uscita desiderato sarebbe: (node1, node2) o (node5,node6) o (node7,node8).

In una buona situazione questo esempio non si verificherebbe, ma in alcuni casi abbiamo effettivamente queste strane connessioni tra siti. Se i nodi in city2 si troverebbero tutti su infiniband switch04, sarebbe facile. Purtroppo ora devo generare gruppi di nodi, che hanno lo stesso switch infiniband e lo stesso filesystem di rete.

In realtà il problema è molto più complicato, dal momento che gli utenti non richiedono interi nodi e le proprietà sono molte.

Modifica: aggiunto l'output desiderato per la query.

Answer 1

Supponendo di avere proprietà di raggruppamento p e n macchine, una soluzione basata su bucket è la più semplice da configurare e fornisce accesso O (2 ^p e middot; log (n)) e aggiornamenti.

• Si crea un secchio-heap per ogni gruppo di proprietà (così si avrebbe un secchio-heap per "InfiniBand", un secchio-heap per "networkfs" e un secchio-heap per "InfiniBand × networkfs") — questo significa 2 ^p bucket-heaps.
• Ogni heap del bucket contiene un bucket per ogni combinazione di valori (quindi il bucket "infiniband" conterrà un bucket per il tasto "switch04" e uno per il tasto "switch03") — ciò significa un totale al massimo n & middot; 2 ^p I bucket si suddividono in tutti gli heap del bucket.
• Ogni bucket è un elenco di server (eventualmente suddiviso in disponibile e non disponibile). Il bucket-heap è un heap standard (vedere std::make_heap) in cui il valore di ciascun bucket è il numero di server disponibili in quel bucket.
• Ogni server memorizza i riferimenti a tutti i bucket che lo contengono.
• Quando si cercano i server che corrispondono a un determinato gruppo di proprietà, si cerca nel bucket corrispondente per quel gruppo di proprietà e si scende nell'heap alla ricerca di un bucket sufficientemente grande da contenere il numero di server richiesti. Questo richiede O (log (p) e middot; log (n)).
• Quando i server sono contrassegnati come disponibili o non disponibili, è necessario aggiornare tutti i bucket contenenti tali server e quindi aggiornare gli heap del bucket che contengono tali bucket. Questa è un'operazione O (2 ^p & middot; log (n)).

Se vi trovate a dover troppo molte proprietà (e il 2 ^p cresce fuori controllo), l'algoritmo permette di alcuni secchio-mucchi da costruire on-demand da altri secchio-cumuli: se l'utente richiede "infiniband × networkfs" ma è disponibile solo un heap di bucket per "infiniband" o "networkfs", è possibile trasformare ciascun bucket nell'heap di bucket "infiniband" in un heap di bucket in modo autonomo (utilizzare un algoritmo pigro quindi non devi elaborare tutti i bucket se il primo funziona) e utilizzare un algoritmo lazy-merging per trovare un bucket appropriato. È quindi possibile utilizzare una cache LRU per decidere quali gruppi di proprietà sono archiviati e quali sono creati su richiesta.

Answer 2

La mia ipotesi è che non ci sarà un algoritmo "facile, efficiente" e la struttura dei dati per risolvere questo problema, perché quello che stai facendo è simile a risolvere un insieme di equazioni simultanee. Supponiamo che ci siano 10 categorie (come city, infiniband e network) in totale e l'utente specifica i valori richiesti per 3 di essi. L'utente chiede 5 nodi, diciamo. Il compito è quindi quello di inferire i valori per le restanti 7 categorie, in modo che esistano almeno 5 record che abbiano tutti e 10 i campi di categoria uguali a questi valori (il 3 specificato e il 7 dedotto). Potrebbero esserci più soluzioni.

Tuttavia, purché non ci siano troppe categorie diverse e non troppe possibilità distinte all'interno di ciascuna categoria, è possibile eseguire una semplice ricerca ricorsiva di forza bruta per trovare possibili soluzioni, in cui ad ogni livello di ricorsione si considera un particolare categoria e "prova" ogni possibilità per esso. Supponiamo che l'utente chiede k record, e può scegliere di stipulare un qualsiasi numero di richieste via required_city, required_infiniband, ecc .:

either(x, y) := if defined(x) then [x] else y 

For each city c in either(required_city, [city1, city2]): 
    For each infiniband i in either(required_infiniband, [switch03, switch04]): 
    For each networkfs nfs in either(required_nfs, [undefined, server01, server02]): 
     Do at least k records of type [c, i, nfs] exist? If so, return them. 

La funzione either() è solo un modo di limitare la ricerca al sottospazio contenente punti che il l'utente ha dato dei vincoli per.

In base a questo, è necessario un modo per cercare rapidamente il numero di punti (righe) per qualsiasi combinazione data [c, i, nfs] - gli hash nidificati funzioneranno correttamente per questo.

Answer 3

Passaggio 1: creare un indice per ciascuna proprietà. Per esempio. per ogni coppia di proprietà + valore, creare un elenco ordinato di nodi con quella proprietà.Metti ciascuna di queste liste in un array associativo di qualche tipo: è qualcosa come e stl map, una per ogni proprietà, indicizzata dai valori. In modo tale che quando hai finito hai una funzione a tempo quasi costante che può restituirti un elenco di nodi che corrispondono a una singola coppia di valore + valore. L'elenco è semplicemente ordinato per numero di nodo.

Passaggio 2: Data una query, per ogni coppia di proprietà + valore richiesta, recuperare l'elenco di nodi.

Passaggio 3: iniziare con l'elenco più breve, chiamarlo elenco 0, confrontarlo con ciascuno degli altri elenchi a sua volta rimuovendo gli elementi dall'elenco 0 che non si trovano negli altri elenchi.

Ora dovresti avere solo i nodi che hanno tutte le proprietà richieste.

L'altra opzione sarebbe quella di utilizzare un database, è già impostato per supportare query come questa. Può essere fatto tutto in memoria con qualcosa come BerkeleyDB con le estensioni SQL.

Answer 4

Se l'elenco di ogni criterio indicato nella query è valido (o se l'elenco è pre-ordinato in base a ciascun criterio relativo), funziona molto bene.

Per "criterio relativo", intendo i criteri non della forma "x deve essere 5", che sono banali da filtrare, ma i criteri del modulo "x devono essere gli stessi per ogni elemento nel set di risultati" . Se sono presenti anche i criteri del modulo "x deve essere 5", filtrare prima quelli, quindi fare quanto segue.

Si basa sull'utilizzo di un ordinamento stabile su più colonne per trovare rapidamente i gruppi corrispondenti (senza provare le combinazioni).

La complessità è numero di nodi * numero di criteri nella query (per l'algoritmo stesso) + numero di nodi * registro (numero di nodi) * numero di criteri (per l'ordinamento, se non pre-ordinamento). Quindi Nodi * Log (nodi) * Criteri.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace bleh 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<Node> list = new List<Node>(); 

      // create a random input list 
      Random r = new Random(); 
      for (int i = 1; i <= 10000; i++) 
      { 
       Node node = new Node(); 
       for (char c = 'a'; c <= 'z'; c++) node.Properties[c.ToString()] = (r.Next() % 10 + 1).ToString(); 
       list.Add(node); 
      } 

      // if you have any absolute criteria, filter the list first according to it, which is very easy 
      // i am sure you know how to do that 

      // only look at relative criteria after removing nodes which are eliminated by absolute criteria 
      // example 
      List<string> criteria = new List<string> {"c", "h", "r", "x" }; 
      criteria = criteria.OrderBy(x => x).ToList(); 

      // order the list by each relative criteria, using a ***STABLE*** sort 
      foreach (string s in criteria) 
       list = list.OrderBy(x => x.Properties[s]).ToList(); 

      // size of sought group 
      int n = 4; 

      // this is the algorithm 
      int sectionstart = 0; 
      int sectionend = 0; 
      for (int i = 1; i < list.Count; i++) 
      { 
       bool same = true; 
       foreach (string s in criteria) if (list[i].Properties[s] != list[sectionstart].Properties[s]) same = false; 
       if (same == true) sectionend = i; 
       else sectionstart = i; 
       if (sectionend - sectionstart == n - 1) break; 
      } 

      // print the results 
      Console.WriteLine("\r\nResult:"); 
      for (int i = sectionstart; i <= sectionend; i++) 
      { 
       Console.Write("[" + i.ToString() + "]" + "\t"); 
       foreach (string s in criteria) Console.Write(list[i].Properties[s] + "\t"); 
       Console.WriteLine(); 
      } 
      Console.ReadLine(); 
     } 
    } 
} 

Answer 5

vorrei fare qualcosa di simile (ovviamente invece di stringhe si dovrebbe mappare loro di int, e utilizzare int di come codici)

struct structNode 
{ 
    std::set<std::string> sMachines; 
    std::map<std::string, int> mCodeToIndex;  
    std::vector<structNode> vChilds;   
}; 

void Fill(std::string strIdMachine, int iIndex, structNode* pNode, std::vector<std::string> &vCodes) 
{ 
    if(iIndex < vCodes.size()) 
    {   
     // Add "Empty" if Needed 
     if(pNode->vChilds.size() == 0) 
     { 
      pNode->mCodeToIndex.insert(pNode->mCodeToIndex.begin(), make_pair("empty", 0)); 
      pNode->vChilds.push_back(structNode()); 
     } 

     // Add for "Empty" 
     pNode->vChilds[0].sMachines.insert(strIdMachine); 
     Fill(strIdMachine, (iIndex + 1), &pNode->vChilds[0], vCodes); 

     if(vCodes[iIndex] == "empty") 
      return; 


     // Add for "Any"   
     std::map<std::string, int>::iterator mIte = pNode->mCodeToIndex.find("any"); 
     if(mIte == pNode->mCodeToIndex.end()) 
     { 
      mIte = pNode->mCodeToIndex.insert(pNode->mCodeToIndex.begin(), make_pair("any", pNode->vChilds.size())); 
      pNode->vChilds.push_back(structNode());  
     } 

     pNode->vChilds[mIte->second].sMachines.insert(strIdMachine); 
     Fill(strIdMachine, (iIndex + 1), &pNode->vChilds[mIte->second], vCodes); 


     // Add for "Segment" 
     mIte = pNode->mCodeToIndex.find(vCodes[iIndex]); 
     if(mIte == pNode->mCodeToIndex.end()) 
     { 
      mIte = pNode->mCodeToIndex.insert(pNode->mCodeToIndex.begin(), make_pair(vCodes[iIndex], pNode->vChilds.size())); 
      pNode->vChilds.push_back(structNode());     
     } 

     pNode->vChilds[mIte->second].sMachines.insert(strIdMachine); 
     Fill(strIdMachine, (iIndex + 1), &pNode->vChilds[mIte->second], vCodes); 

    } 
} 

////////////////////////////////////////////////////////////////////// 
// Get 
// 
// NULL on empty group 
////////////////////////////////////////////////////////////////////// 
set<std::string>* Get(structNode* pNode, int iIndex, vector<std::string> vCodes, int iMinValue) 
{  
    if(iIndex < vCodes.size()) 
    {  
     std::map<std::string, int>::iterator mIte = pNode->mCodeToIndex.find(vCodes[iIndex]);  
     if(mIte != pNode->mCodeToIndex.end()) 
     { 
      if(pNode->vChilds[mIte->second].sMachines.size() < iMinValue) 
       return NULL; 
      else 
       return Get(&pNode->vChilds[mIte->second], (iIndex + 1), vCodes, iMinValue); 
     } 
     else 
      return NULL;   
    } 

    return &pNode->sMachines; 
} 

Per riempire l'albero con il campione

structNode stRoot; 

    const char* dummy[] = { "city1", "switch03", "server01" }; 
    const char* dummy2[] = { "city1", "switch03", "empty" }; 
    const char* dummy3[] = { "city2", "switch03", "server02" }; 
    const char* dummy4[] = { "city2", "switch04", "server02" }; 

    // Fill the tree with the sample  
    Fill("node1", 0, &stRoot, vector<std::string>(dummy, dummy + 3)); 
    Fill("node2", 0, &stRoot, vector<std::string>(dummy, dummy + 3)); 
    Fill("node3", 0, &stRoot, vector<std::string>(dummy2, dummy2 + 3)); 
    Fill("node4", 0, &stRoot, vector<std::string>(dummy2, dummy2 + 3)); 
    Fill("node5", 0, &stRoot, vector<std::string>(dummy3, dummy3 + 3)); 
    Fill("node6", 0, &stRoot, vector<std::string>(dummy3, dummy3 + 3)); 
    Fill("node7", 0, &stRoot, vector<std::string>(dummy4, dummy4 + 3)); 
    Fill("node8", 0, &stRoot, vector<std::string>(dummy4, dummy4 + 3)); 

Ora è possibile ottenere facilmente tutte le combinazioni che si desidera, ad esempio la query potrebbe essere qualcosa del tipo:

vector<std::string> vCodes; 
    vCodes.push_back("empty"); // Discard first property (cities) 
    vCodes.push_back("any"); // Any value for infiniband 
    vCodes.push_back("any"); // Any value for networkfs (except empty) 

    set<std::string>* pMachines = Get(&stRoot, 0, vCodes, 2); 

E per esempio, solo il City02 switch03 con networfs non vuote

vector<std::string> vCodes; 
    vCodes.push_back("city2"); // Only city2 
    vCodes.push_back("switch03"); // Only switch03 
    vCodes.push_back("any"); // Any value for networkfs (except empy) 

    set<std::string>* pMachines = Get(&stRoot, 0, vCodes, 2);