Mercury: Supporting Scalable Multi-Attribute Range Queries Ashwin R.Bharambe, Mekesh Agrawal, Srinivasan Seshan Computer Science Department Carnegie Mellon University Mercury • distributed systemにおけるrange queryのた めの効率的検索要求機構 • multi attribute(複数属性)の対応 – wildcardによる検索要求も可能 • load balancingの実現 DHTによるrange queryの限界 • range queryを実装するのに適していない • rangeのハッシュはrange内の値のハッシュに相関 しない – value spaceをbucketsに分け、valueとrangeをマップさせ る – 分割できないもの ex:)file name • load balancing難 – bucketsを細かくとる→一部ノードに負荷 – bucketsを大きくとる→検索オーバヘッド Mercury: Data Model • Data – – – – – float float string string int x-coord y-coord player team score type attribute = 50 = 100 = “John” = “topgunz” = 76 value Mercury: Data Model • Query – – – – float float string int x-coord y-coord player score < > = = 53 34 “J*” “*” type attribute operator value Mercury Routing • attribute hubという同じattributeを担当する ノード同士で論理ネットワークを構築 • 同一hubのノードをリング状に並べ接続す る Mercury Routing • attributeのvalueをある閾値で均等に分ける • リングのそれぞれのノードに領域が連続す るようにvalueを割り当てる • queryはリングを周って、必要とするデータ をvalueの領域を担当するノードから貰う Mercury Routing xの0～80 の範囲を 担当とい う意味 x=100のデータ を担当するノー ドはb, y=200はe multi attributeを満たすた めhub間でルーティング Mercury Routing • 個々のノードは以下のリンクを保持する – successor and predecessor link – K long-distance links (for efficient intra-hub) – one cross-hub link per hub (for connecting to other hubs) Node Join 1. 最低一つのノードの情報を知っている必 要 2. 接続後存在するノードとhubsの情報をリ ストで貰う 3. 参加するhubをランダムで一つ選択し、そ のメンバーの一人mにコンタクト 4. 自身をmのpredecessorとしてインストール し、mのrangeの半分を請け負う Node Join 1. 参加後、自身のsuccessor mのルーティン グ情報をコピー(long-distance linksと他の hubへのlinksを含む) 1. 自身のlong-distanceの設定 2. random-walkしてcross-hub neighborsの検索 Node Departure • 各ノードが時計周りに連続するノードのリ ストを保持 • successorが離脱していたらその先のノード へ転送 • successor/predecessorのlinkを更新 Efficiency in the face of nonuniformity • 各value領域のquery到達性は一様とは限 らない • query selectivityとdata popularityという側 面から解決アプローチ – Random Samplingを利用したhistogramの維持 によってquery selectivityを実現 – システム全体のload averageをhistogramから 算出し、それを利用しdata popularityを実現 Random Sampling • expanderによるhub overlayの構築 – Linkを跨ぐrandom walk→素早くrandom walkの定常 分布に収束する • Log nのTTLでsample-requestメッセージを送信 • 各ノードはランダムにリンクを選びメッセージを転 送しTTLを減少させる • TTLが切れたノードをsampleとして送り返す Maintaining Approximate Histograms • それぞれのノードがrandom samplingから 自らが計測したローカルなシステム統計の 概算を出す • 各ノードはある一定数サンプリングし、サン プリングされたノードが前述の概算を返す Query Selectivity • ルーティングに利用するqueryのpredicates を適切に選択する必要 – wildcard predicateによfloodingの低減 • ある特定のbucketのノード数を知る必要 – histogramの情報により可能 Data Popularity and Load Balancing • 一部にqueryが集中する領域が存在してし まう • システム全体のaverage loadをhistogramか ら出し、それを基準にノードの負荷を分類 – heavily loaded node – lightly loaded node Data Popularity and Load Balancing • heavily loaded nodeがlightly loaded nodeに 助けを求める • lightly loaded nodeがネットワークから一端 離脱しheavily loaded nodeに隣接して再参 加 Evaluation • Mercury用のシミュレータを実装 • queuing delayまたはpacket lossは考慮しな い • 評価のポイントは2つ – Scalable routing for queries and data records – Balancing of routing load throughout the system リンク構築パターン • NodeLink – 理想的なsmall-world overlay – harmonic distribution on node-link distanceによる構築 • ValueLink – harmonic distribution on value-link distanceによる構築 • HistoLink – node-cound histogramによる構築 ValueLink • Section3.3参照 HistoLink • Histogramの情報から、n台が存在ノードと して見積もられる • [1, n]間の数字value n1がharmonic probability distributionにより生成 • これがスキップするノード数となりlongdistance link張る Figure.3 • 基礎をなす既存ネットワークがサンプリン グ精度に及ぼす影響を示すグラフ • Y軸がuniform distributionからの統計的距 離 – 統計的距離…A、Bを確率変数とする。 AとB との統計的距離を∑xはkビットのビット列|Pr(A=x)Pr(B=x)| により定義する。 Figure.4 • Long-distance linkの分布を示すグラフ Figure.5 • Histogramの正確さを示す – (a)histogramの平均精度 – (b)各ノードの概算の結果 – (c)パラメータ変更によるrouting performanceの 変化 Figure.5 • Histogramによりパフォーマンスが上がる がhistogramの精度に依存するため限界あ り – (a)と(c)を見比べるとわかる Figure.6 • Uniform workloadとZipf-skewed workload によるbasic protocolの評価 • Y軸が平均ホップ数 • HistoLinkの図だけど他の2つも類似 • 対数的に増えるのでスケールすることがい える Figure.7 • Long-distance linkの選択を決める histogramがある場合とない場合のprotocol の評価 – Node-range distributionとdata distributionは non-uniform→Zipf-skewedを利用 – ジップ分布…離散型のパレート分布 • http://stat.sci.kagoshimau.ac.jp/~cse/contents/orency2/doc/p411.html Figure.8 • Load balanceの処理を1周り行うround数と Load skewのグラフ Distributed Application Design • Mercuryを基盤にしてその上にpublishscribeシステムを実装した • Cadeuceusという2Dシューティングゲームを アプリケーションとして実装 Publish-Scribe architecture • 省略
© Copyright 2025 ExpyDoc
