10

私はこの古いバッチシステムを持っています。スケジューラは、すべての計算ノードを 1 つの大きな配列に格納します。ほとんどのクエリは、クエリを満たすノードをフィルタリングすることで解決できるため、これで大部分は問題ありません。

私が今抱えている問題は、いくつかの基本的なプロパティ (CPU、メモリ、OS の数) とは別に、これらの奇妙なグループ化プロパティ (都市、インフィニバンド、ネットワーク スクラッチ) もあるということです。

これらの問題は、ユーザーがインフィニバンドでノードを要求したときに、ノードを与えるだけではなく、1 つのインフィニバンド スイッチに接続されたノードをユーザーに与える必要があるため、ノードは実際にインフィニバンドを使用して通信できることです。

これは、ユーザーがそのようなプロパティを 1 つだけ要求する場合でも問題ありません (プロパティごとに配列をパーティション分割し、各パーティション内のノードを個別に選択することができます)。

このようなプロパティを複数組み合わせると、サブセット (メイン配列のパーティション) のすべての組み合わせを生成する必要があるため、問題が発生します。

良いことは、プロパティのほとんどがサブセットまたは同等の関係にあることです (1 つのインフィニバンド スイッチ上のマシンが 1 つの都市にあることは、ある程度理にかなっています)。しかし、残念ながらこれは厳密には真実ではありません。

この種の半階層的でほとんどツリーのようなものを格納するための適切なデータ構造はありますか?

編集：例

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

ユーザーのリクエスト:

2x node with infiniband and networkfs

望ましい出力は、(node1, node2)または(node5,node6)または(node7,node8)です。

良い状況では、この例は発生しませんが、実際には、これらの奇妙なクロスサイト接続がいくつかのケースで発生します。のノードcity2がすべて infinibandswitch04にある場合、それは簡単です。残念ながら、同じインフィニバンド スイッチと同じネットワーク ファイルシステムを持つノードのグループを生成する必要があります。

実際には、ユーザーがノード全体を要求するわけではなく、プロパティが多数あるため、問題ははるかに複雑です。

編集：クエリに必要な出力を追加しました。

4

5 に答える 5

3

p個のグループ化プロパティとn個のマシンがあるとすると、バケットベースのソリューションはセットアップが最も簡単で、O（2 p・log（n））アクセスと更新を提供します。

  • プロパティのグループごとにバケットヒープを作成します（つまり、「infiniband」のバケットヒープ、「networkfs」のバケットヒープ、「infiniband×networkfs」のバケットヒープがあります）—これは2pを意味します。バケットヒープ。
  • 各バケットヒープには、値のすべての組み合わせに対するバケットが含まれます（したがって、「infiniband」バケットには、キー「switch04」用のバケットとキー「switch03」用のバケットが含まれます）。これは、合計で最大n・2pのバケットが分割されることを意味します。すべてのバケットヒープにわたって。
  • 各バケットはサーバーのリストです（使用可能なものと使用できないものに分割されている可能性があります）。バケットヒープは標準ヒープ（を参照std::make_heap）であり、各バケットの値はそのバケットで使用可能なサーバーの数です。
  • 各サーバーは、それを含むすべてのバケットへの参照を格納します。
  • 特定のプロパティグループに一致するサーバーを探すときは、そのプロパティグループに対応するバケットを調べ、ヒープを降りて、要求されたサーバーの数に対応するのに十分な大きさのバケットを探します。これにはO（log（p）・log（n））が必要です。
  • サーバーが使用可能または使用不可としてマークされている場合は、それらのサーバーを含むすべてのバケットを更新してから、それらのバケットを含むバケットヒープを更新する必要があります。これはO（2 p・log（n））操作です。

プロパティが多すぎる場合（および2 pが制御不能になる場合）、アルゴリズムでは、他のバケットヒープからオンデマンドでいくつかのバケットヒープを構築できます。ユーザーが「infiniband×networkfs」を要求した場合、 「infiniband」または「networkfs」で使用できるバケットヒープのみがあります。「infiniband」バケットヒープ内の各バケットを独自にバケットヒープに変換できます（遅延アルゴリズムを使用するため、処理する必要はありません）。最初のバケットが機能する場合はすべてのバケット）、レイジーヒープマージアルゴリズムを使用して適切なバケットを見つけます。次に、LRUキャッシュを使用して、保存するプロパティグループとオンデマンドで構築するプロパティグループを決定できます。

于 2012-06-26T13:40:33.660 に答える
0

ステップ1：各プロパティのインデックスを作成します。たとえば、プロパティと値のペアごとに、そのプロパティを持つノードの並べ替えられたリストを作成します。そのような各リストをある種の連想配列に入れます-これは、値でインデックス付けされた、プロパティごとに1つずつのstlマップのようなものです。完了すると、単一のプロパティと値のペアに一致するノードのリストを返すことができるほぼ一定の時間関数が得られます。リストは単にノード番号でソートされています。

ステップ2：クエリを指定して、必要なプロパティと値のペアごとに、ノードのリストを取得します。

ステップ3：最短のリストから始めて、それをリスト0と呼び、それを他の各リストと比較して、他のリストにない要素をリスト0から削除します。

これで、要求されたすべてのプロパティを持つノードだけができました。

他のオプションはデータベースを使用することです。データベースはこのようなクエリをサポートするようにすでに設定されています。これは、SQL拡張機能を備えたBerkeleyDBのようなものを使用して、すべてメモリ内で実行できます。

于 2012-06-26T13:56:29.307 に答える
0

私の推測では、この問題を解決するための「簡単で効率的な」アルゴリズムとデータ構造は存在しないと思います。なぜなら、あなたがしていることは一連の連立方程式を解くことに似ているからです。合計10 個のカテゴリ ( city、 、infinibandなどnetwork) があり、ユーザーがそのうちの 3 つに必要な値を指定するとします。ユーザーが 5 つのノードを要求したとします。次に、残りの 7 つのカテゴリの値を推測し、10 個のカテゴリ フィールドすべてがこれらの値 (指定された 3 つと推測された 7 つ) を持つ少なくとも 5 つのレコードが存在するようにします。複数のソリューションが存在する可能性があります。

それでも、異なるカテゴリが多すぎず、各カテゴリ内に明確な可能性が多すぎない場合は、再帰の各レベルで特定のカテゴリを検討する単純なブルート フォース再帰検索を実行して、可能な解決策を見つけることができます。そのためのあらゆる可能性を試してみてください。ユーザーがレコードを要求し、、 などkを介して任意の数の要件を規定することを選択できるとします。required_cityrequired_infiniband

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.

このeither()関数は、ユーザーが制約を与えた点を含む部分空間に検索を限定する方法にすぎません。

これに基づいて、特定の[c, i, nfs]組み合わせのポイント (行) の数をすばやく検索する方法が必要になります。これには、ネストされたハッシュテーブルがうまく機能します。

于 2012-06-26T13:35:48.707 に答える
-1

クエリに記載されているすべての条件でリストを並べ替えることが実行可能な場合 (または、各相対条件でリストを事前に並べ替える場合)、これは非常にうまく機能します。

「相対基準」とは、「x は 5 でなければならない」という形式ではなく、フィルタリングするのが簡単な基準を意味しますが、「x は結果セット内の各項目で同じでなければならない」という形式の基準です。「x は 5 でなければならない」という形式の基準もある場合は、最初にそれらに対してフィルター処理を行ってから、次の手順を実行します。

複数の列で安定した並べ替えを使用して、一致するグループをすばやく見つけることに依存しています (組み合わせを試す必要はありません)。

複雑さは、ノード数 * クエリ内の条件の数 (アルゴリズム自体の場合) + ノードの数 * ログ (ノードの数) * 条件の数 (事前ソートでない場合はソートの場合) です。つまり、ノード*ログ(ノード)*基準です。

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();
        }
    }
}
于 2012-06-26T14:16:50.800 に答える
-1

私はこのようなことをします（明らかに、文字列の代わりに、それらをintにマップし、intをコードとして使用する必要があります）

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

ツリーをサンプルで埋めるには

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

これで、必要なすべての組み合わせを簡単に取得できます。たとえば、クエリは次のようになります。

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

たとえば、ネットワークが空でない switch03 の City02 のみ

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);
于 2012-06-26T17:03:07.970 に答える