Struktura danych do wyboru grup maszyn

Question

Mam ten stary system wsadowy. Program planujący przechowuje wszystkie węzły obliczeniowe w jednej dużej tablicy. Teraz jest to w porządku, ponieważ większość zapytań można rozwiązać przez filtrowanie dla węzłów, które spełniają zapytanie.

Problemem, który mam teraz, jest to, że oprócz pewnych podstawowych właściwości (liczba procesorów, pamięci, systemu operacyjnego), istnieją również te dziwne właściwości grupowania (miasto, infiniband, zarysowanie sieci).

Teraz problem polega na tym, że gdy użytkownik żąda węzłów z infiniband, nie mogę po prostu dać mu żadnych węzłów, ale muszę dać mu węzły podłączone do jednego przełącznika infiniband, więc węzły mogą rzeczywiście komunikować się za pomocą infiniband.

To wciąż jest OK, gdy użytkownik żąda tylko jednej takiej właściwości (mogę po prostu podzielić tablicę dla każdej właściwości, a następnie spróbować wybrać węzły w każdej partycji oddzielnie).

Problem polega na łączeniu wielu takich właściwości, ponieważ wtedy musiałbym wygenerować całą kombinację podzbiorów (partycji głównej tablicy).

Dobrą rzeczą jest to, że większość właściwości znajduje się w relacji podzestawu lub równoważności (to ma sens, aby maszyny znajdujące się na jednym przełączniku infiniband znajdowały się w jednym mieście). Ale to niestety nie jest ściśle prawdą.

Czy istnieje pewna dobra struktura danych do przechowywania tego rodzaju semi-hierarchicznych, głównie podobnych do drzewa rzeczy?

Edycja: Przykład

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 

Użytkownicy żądają:

2x node with infiniband and networkfs 

pożądany wynik byłby: (node1, node2) lub (node5,node6) lub (node7,node8).

W dobrej sytuacji ten przykład nie miałby miejsca, ale w niektórych przypadkach mamy te dziwne połączenia między lokacjami. Jeśli węzły w city2 będą wszystkie na infiniband switch04, będzie to łatwe. Niestety teraz muszę generować grupy węzłów, które mają ten sam przełącznik infiniband i ten sam sieciowy system plików.

W rzeczywistości problem jest znacznie bardziej skomplikowany, ponieważ użytkownicy nie żądają całych węzłów, a ich właściwości są liczne.

Edytuj: dodano pożądane wyjście dla zapytania.

Answer 1

Zakładając, że mają właściwości i N maszyn p grupowanie, wiadro rozwiązanie oparte jest najłatwiejszy do konfigurowania i zapewnia O (2 ^p & middot; log (n)) dostępu i aktualizacji.

• utworzyć wiadro sterty dla każdej grupy właściwości (tak trzeba wiadrem sterty dla „InfiniBand”, wiadro sterty dla „networkfs” i wiadro sterty dla „InfiniBand × networkfs”) — oznacza to 2 ^p kubełków.
• Każda kupka-wiadro zawiera wiadro dla każdej kombinacji wartości (więc wiadro "infiniband" zawierałoby klucz dla klucza "switch04" i jeden dla klucza "switch03") — oznacza to sumę co najwyżej n & middot; 2 ^p wiadra podzielone na wszystkie wiadra-hałdy.
• Każdy segment jest listą serwerów (prawdopodobnie podzielonych na dostępne i niedostępne). Kupa-wiadro jest standardową stertą (patrz std::make_heap), gdzie wartość każdego zasobnika to liczba dostępnych serwerów w tym zasobniku.
• Każdy serwer przechowuje odwołania do wszystkich zasobników, które go zawierają.
• Szukając serwerów, które pasują do określonej grupy właściwości, wystarczy spojrzeć do odpowiedniego zasobnika dla tej grupy właściwości i zejść do sterty w poszukiwaniu kubełka, który jest wystarczająco duży, aby pomieścić żądaną liczbę serwerów. Zajmuje to O (log (p) i middot; log (n)).
• Gdy serwery są oznaczone jako dostępne lub niedostępne, należy zaktualizować wszystkie zasobniki zawierające te serwery, a następnie zaktualizować kupony zawierające te segmenty. Jest to operacja O (2 ^p & middot; log (n)).

Jeśli znajdziesz się zbyt wielu właściwości (i 2 ^p rośnie spod kontroli), algorytm pozwala na pewne wiadro hałdy być zbudowany na żądanie z drugiej wiadro pryzmach: jeśli użytkownik żąda "infiniband × networkfs" ale masz tylko stertę wiadra dostępną dla "infiniband" lub "networkfs", możesz zamienić każdy kubeł w stos "infiniband" w stos kubełkowy samodzielnie (użyj leniwego algorytmu więc nie musisz przetwarzać wszystkich wiader, jeśli działa pierwszy) i użyć leniwego algorytmu scalania sterty, aby znaleźć odpowiednie wiadro. Następnie można użyć pamięci podręcznej LRU, aby zdecydować, które grupy właściwości są przechowywane i które są budowane na żądanie.

Answer 2

Domyślam się, że nie będzie "łatwego, wydajnego" algorytmu i struktury danych, aby rozwiązać ten problem, ponieważ to, co robisz, jest podobne do , rozwiązując zestaw równoczesnych równań. Załóżmy, że w sumie jest 10 kategorii (na przykład city, infiniband i network), a użytkownik podaje wymagane wartości dla 3 z nich. Użytkownik prosi o 5 węzłów, powiedzmy. Twoim zadaniem jest wtedy wyprowadzić wartości dla pozostałych 7 kategorii, tak aby istniało co najmniej 5 rekordów, które mają wszystkie 10 pól kategorii równe tym wartościom (3 określone i 7 wnioskowane). Może być wiele rozwiązań.

Nadal, pod warunkiem, że nie ma zbyt wielu różnych kategorii i nie ma zbyt wielu różnych możliwości w obrębie każdej kategorii, można wykonać proste rekursywne wyszukiwanie w poszukiwaniu brutalnych sił, aby znaleźć możliwe rozwiązania, w których na każdym poziomie rekurencji należy rozważyć kategorii i "wypróbuj" każdą możliwość. Załóżmy, że użytkownik prosi o k rekordów, a może zdecydować się określać dowolną liczbę wymagań poprzez required_city, required_infiniband itp .:

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. 

Funkcja either() jest po prostu sposobem na ograniczenie wyszukiwania do podprzestrzeni zawierających wskazuje, że użytkownik dał ograniczenia dla.

W oparciu o to, będziesz potrzebował sposobu na szybkie sprawdzenie liczby punktów (wierszy) dla dowolnej kombinacji [c, i, nfs] - zagnieżdżone hashtables będą działać dobrze.

Answer 3

Krok 1: Utwórz indeks dla każdej właściwości. Na przykład. dla każdej pary właściwości + wartości utwórz posortowaną listę węzłów z tą właściwością.Każdą taką listę umieść w tablicy asocjacyjnej jakiegoś rodzaju - To jest coś takiego i mapa STL, jedna dla każdej właściwości, indeksowana według wartości. Taki, że gdy skończysz, masz prawie stałą funkcję czasu, która może zwrócić ci listę węzłów, które pasują do pojedynczej pary właściwości + wartości. Lista jest po prostu sortowana według numeru węzła.

Krok 2: Przy zapytaniu, dla każdej pary właściwości i wartości, pobierz listę węzłów.

Krok 3: Zaczynając od najkrótszej listy, wywołaj ją na liście 0, porównaj ją z każdą z pozostałych list po kolei usuwając elementy z listy 0, które nie znajdują się na innych listach.

Powinieneś mieć teraz tylko węzły, które mają wszystkie żądane właściwości.

Inną opcją byłoby użycie bazy danych, która jest już skonfigurowana do obsługi takich zapytań. Można to zrobić w pamięci za pomocą czegoś takiego jak BerkeleyDB z rozszerzeniami SQL.

Answer 4

Jeśli sortowanie listy według wszystkich kryteriów wymienionych w kwerendzie jest wykonalne (lub lista jest wstępnie posortowana według kryteriów), działa to bardzo dobrze.

Przez „względnych kryteriów”, to znaczy kryteriów nie w postaci „x musi być 5”, które są trywialne filtrować przed, ale kryterium w postaci „x musi być taka sama dla każdego elementu w zestawie wyników” . Jeśli istnieją również kryteria dotyczące formy "x musi być 5", a następnie filtruj przeciwko tym pierwszym, wykonaj następujące czynności.

Opiera się na użyciu stabilnego sortowania na wielu kolumnach, aby szybko znaleźć pasujące grupy (bez wypróbowywania kombinacji).

Złożoność to liczba węzłów * liczba kryteriów w zapytaniu (dla samego algorytmu) + liczba węzłów * log (liczba węzłów) * liczba kryteriów (dla sortowania, jeśli nie wstępnego sortowania). Węzły * Log (węzły) * Kryteria.

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

chciałbym zrobić coś takiego (oczywiście zamiast łańcuchów należy mapować je na int i użyć int jako kody)

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; 
} 

Aby wypełnić drzewa z próbki

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)); 

Teraz możesz łatwo uzyskać wszystkie kombinacje, które chcesz, na przykład zapytanie: coś takiego:

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); 

i przykładowo tylko City02 na switch03 z networfs nie pustych

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);