Cấu trúc dữ liệu để chọn các nhóm máy

Question

Tôi có hệ thống lô cũ này. Bộ lập lịch lưu trữ tất cả các nút tính toán trong một mảng lớn. Bây giờ điều đó là tốt cho hầu hết các phần, bởi vì hầu hết các truy vấn có thể được giải quyết bằng cách lọc cho các nút thỏa mãn truy vấn.

Vấn đề tôi có bây giờ là ngoài một số thuộc tính cơ bản (số cpus, bộ nhớ, hệ điều hành), cũng có những thuộc tính nhóm lạ (thành phố, thông tin, mạng đầu). Bây giờ vấn đề với những điều này là khi người dùng yêu cầu các nút với infiniband tôi không thể chỉ cho anh ta bất kỳ nút nào, nhưng tôi phải cho anh ta các nút được kết nối với một công tắc infiniband, vì vậy các nút có thể thực sự giao tiếp bằng cách sử dụng infiniband.

Điều này vẫn OK, khi người dùng chỉ yêu cầu một thuộc tính như vậy (tôi chỉ có thể phân vùng mảng cho mỗi thuộc tính và sau đó cố gắng chọn các nút trong từng phân đoạn riêng biệt).

Sự cố đi kèm với việc kết hợp nhiều thuộc tính như vậy, vì sau đó tôi sẽ phải tạo tất cả kết hợp các tập con (phân vùng của mảng chính).

Điều tốt là hầu hết các thuộc tính đều nằm trong tập hợp con hoặc tương đương (Nó có ý nghĩa đối với các máy trên một công tắc vô tuyến ở trong một thành phố). Nhưng tiếc là điều này không đúng.

Có một số cấu trúc dữ liệu tốt để lưu trữ loại điều bán phần lớn cây phân cấp này không?

EDIT: Ví dụ

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 

Người dùng yêu cầu:

2x node with infiniband and networkfs 

Kết quả mong muốn sẽ là: (node1, node2) hoặc (node5,node6) hoặc (node7,node8).

Trong tình huống tốt, ví dụ này sẽ không xảy ra, nhưng chúng tôi thực sự có các kết nối chéo trang lạ trong một số trường hợp. Nếu các nút trong city2 sẽ là tất cả trên infiniband switch04, nó sẽ dễ dàng. Thật không may bây giờ tôi phải tạo ra các nhóm của các nút, có cùng một switch infiniband và cùng một hệ thống tập tin mạng.

Trong thực tế, vấn đề phức tạp hơn nhiều, vì người dùng không yêu cầu toàn bộ nút và thuộc tính rất nhiều.

Chỉnh sửa: đã thêm đầu ra mong muốn cho truy vấn.

Answer 1

Giả sử bạn có thuộc tính nhóm p và máy n, giải pháp dựa trên thùng là cách dễ nhất để thiết lập và cung cấp quyền truy cập và cập nhật O (2 ^p & middot; log (n)).

• Bạn tạo một xô-đống cho mỗi nhóm tài sản (do đó bạn sẽ có một cái xô-đống cho "InfiniBand", một cái xô-đống cho "networkfs" và một cái xô-đống cho "InfiniBand × networkfs") — điều này có nghĩa là 2 ^p xô-đống.
• Mỗi nhóm thùng chứa một nhóm cho mọi kết hợp giá trị (do đó, nhóm "infiniband" sẽ chứa một nhóm cho khóa "switch04" và một cho khóa "switch03") — điều này có nghĩa là tổng số tối đa n & middot; 2 ^p các nhóm được chia thành tất cả các nhóm.
• Mỗi nhóm là danh sách máy chủ (có thể được phân đoạn thành có sẵn và không khả dụng). Xô-đống là một đống tiêu chuẩn (xem std::make_heap) trong đó giá trị của mỗi nhóm là số lượng các máy chủ có sẵn trong nhóm đó.
• Mỗi máy chủ lưu trữ các tham chiếu đến tất cả các nhóm chứa nó.
• Khi bạn tìm kiếm máy chủ khớp với một nhóm thuộc tính nhất định, bạn chỉ cần nhìn vào nhóm tương ứng cho nhóm thuộc tính đó và leo xuống heap để tìm một nhóm đủ lớn để chứa số lượng máy chủ được yêu cầu. Điều này có O (log (p) & middot; log (n)).
• Khi máy chủ được đánh dấu là có sẵn hoặc không khả dụng, bạn phải cập nhật tất cả các nhóm chứa các máy chủ đó và sau đó cập nhật nhóm thùng chứa các nhóm đó. Đây là thao tác O (2 ^p & middot; log (n)).

Nếu bạn thấy mình có quá nhiều tài sản (và 2 ^p phát triển ngoài tầm kiểm soát), thuật toán cho phép đối với một số xô-đống sẽ được xây dựng theo yêu cầu từ khác xô-đống: nếu người dùng yêu cầu "infiniband × networkfs" nhưng bạn chỉ có một nhóm thùng có sẵn cho "infiniband" hoặc "networkfs", bạn có thể biến từng nhóm trong nhóm "tự động" thành một nhóm thùng (sử dụng thuật toán lười biếng) do đó bạn không phải xử lý tất cả các nhóm nếu nhóm đầu tiên hoạt động) và sử dụng thuật toán kết hợp heap để tìm một nhóm thích hợp. Sau đó, bạn có thể sử dụng bộ nhớ cache LRU để quyết định nhóm thuộc tính nào được lưu trữ và được tạo theo yêu cầu.

Answer 2

Tôi đoán là sẽ không có thuật toán và cấu trúc dữ liệu "dễ dàng, hiệu quả" để giải quyết vấn đề này, bởi vì những gì bạn đang làm tương tự như giải quyết một tập hợp các phương trình đồng thời. Giả sử có 10 danh mục (như số city, infiniband và network) và người dùng chỉ định các giá trị bắt buộc cho 3 danh mục. Người dùng yêu cầu 5 nút, giả sử. Nhiệm vụ của bạn sau đó là suy ra các giá trị cho 7 danh mục còn lại, sao cho ít nhất 5 bản ghi tồn tại có tất cả 10 trường danh mục tương đương với các giá trị này (3 chỉ định và 7 được suy ra). Có thể có nhiều giải pháp.Tuy nhiên, với điều kiện không có quá nhiều danh mục khác nhau và không có quá nhiều khả năng khác nhau trong mỗi danh mục, bạn có thể thực hiện tìm kiếm đệ quy lực đơn giản để tìm các giải pháp khả thi, ở mỗi cấp độ đệ quy mà bạn xem xét một cách cụ thể loại và "thử" từng khả năng cho nó. Giả sử người dùng yêu cầu k hồ sơ, và có thể chọn để quy định bất kỳ số lượng yêu cầu qua required_city, required_infiniband, v.v .:

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. 

Chức năng either() chỉ là một cách để hạn chế tìm kiếm để không gian con chứa chỉ rằng người dùng đã đưa ra các ràng buộc cho.

Dựa trên điều này, bạn sẽ cần một cách để nhanh chóng tra cứu số điểm (hàng) cho bất kỳ kết hợp [c, i, nfs] nhất định - hashtables lồng nhau sẽ hoạt động tốt cho việc này.

Answer 3

Bước 1: Tạo chỉ mục cho từng thuộc tính. Ví dụ. cho mỗi cặp thuộc tính + giá trị, tạo danh sách các nút được sắp xếp với thuộc tính đó.Đặt mỗi danh sách như vậy vào một mảng kết hợp của một số loại - Đó là một cái gì đó giống như và bản đồ stl, một cho mỗi thuộc tính, được lập chỉ mục bởi các giá trị. Như vậy khi bạn đã hoàn thành, bạn có một hàm thời gian gần không đổi có thể trả lại cho bạn danh sách các nút khớp với một cặp giá trị + thuộc tính duy nhất. Danh sách chỉ đơn giản là sắp xếp theo số nút.

Bước 2: Cho một truy vấn, cho mỗi cặp thuộc tính + giá trị bắt buộc, hãy truy xuất danh sách các nút.

Bước 3: Bắt đầu với danh sách ngắn nhất, gọi danh sách 0, so sánh nó với từng danh sách khác để loại bỏ các phần tử khỏi danh sách 0 không nằm trong danh sách khác.

Bây giờ bạn sẽ chỉ có các nút có tất cả các thuộc tính được yêu cầu.

Tùy chọn khác của bạn sẽ là sử dụng cơ sở dữ liệu, nó đã được thiết lập để hỗ trợ các truy vấn như thế này. Nó có thể được thực hiện tất cả trong bộ nhớ với một cái gì đó giống như BerkeleyDB với các phần mở rộng SQL.

Answer 4

Nếu sắp xếp danh sách theo mọi tiêu chí được đề cập trong truy vấn là khả thi (hoặc có danh sách được sắp xếp trước theo từng tiêu chí tương đối), điều này hoạt động rất tốt.

Bởi "tiêu chí tương đối", tôi có nghĩa là tiêu chí không có dạng "x phải là 5", không đáng kể để lọc, nhưng tiêu chí của biểu mẫu "x phải giống nhau cho từng mục trong tập hợp kết quả" . Nếu cũng có tiêu chí của biểu mẫu "x phải là 5", thì hãy lọc theo các tiêu chí đầu tiên, sau đó thực hiện như sau.

Tùy thuộc vào việc sử dụng sắp xếp ổn định trên nhiều cột để tìm nhanh nhóm phù hợp (không thử kết hợp).

Độ phức tạp là số lượng nút * số lượng tiêu chí trong truy vấn (cho chính thuật toán) + số lượng nút * nhật ký (số lượng nút) * số tiêu chí (sắp xếp, nếu không sắp xếp trước). Vì vậy, nút * Đăng nhập (Nút) * Tiêu chí.

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

tôi sẽ làm một cái gì đó như thế này (rõ ràng thay vì chuỗi bạn nên lập bản đồ họ int, và sử dụng int như mã)

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

Để lấp đầy cây với mẫu của bạn

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

Giờ đây, bạn có thể dễ dàng có được tất cả các kết hợp bạn muốn, ví dụ: truy vấn của bạn sẽ giống như sau:

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

Và ví dụ chỉ City02 trên switch03 với networfs không có sản phẩm nào

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