スポンサーサイト

--年--月--日 --:--

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Jung使ってみる

2010年04月29日 04:04

Jungを使おうと思ってダウンロードページを見てみる。
http://jung.sourceforge.net/download.html

三つのライブラリが必要とのこと。

・JDK5以上
Collections-Generic
Cern Colt

三つのライブラリをEclipseプロジェクトに置いてビルドパスを通しておく。
そして、Sourceforgeから Jung2.0.1を持ってくる。

jung-samples-2.0.1.jarの中なんとかDemoクラスのmainメソッドを実行すると
デモを見ることができる。個人的にはClusteringDemoが面白かった。

clustering

↑媒介性の高い辺を順に取り去っていってクラスタリングできる

さて、以下1からコードを書いてみる。

Jung 2からは Graphクラスは Graph<V, E>てな感じでVertexとEdgeのクラスを
指定できるようだ。VとかEにInterfaceはいらんのですね。
とりあえずGraph<String, String>で進めてみる。


Graph g = new DirectedSparseGraph();
g.addVertex("v1");
g.addEdge("e1", "v1", "v2");
...



のような感じでGraphを作成して、以下のようにViewerをJframeにaddすればOK


JFrame window = new JFrame("Graph");
Layout layout = new FRLayout(g);
VisualizationViewer viewer = new VisualizationViewer(layout);
window.add(viewer);
window.setSize(600, 600);
window.setLocationRelativeTo(null);
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
window.setVisible(true);



結果:グラフが表示された。
sample1

Vertexにラベルを表示するには?
PluggableRendererはなくなった?→なくなったようだ。
代わりにToStringLabellerをVertexLabelTransformerとしてsetする。
サンプルのコードを参照すれば何でも出来そう。


Renderer renderer = new BasicRenderer();
VisualizationViewer viewer = new VisualizationViewer(layout);
viewer.getRenderContext().setVertexLabelTransformer(new ToStringLabeller());
viewer.setRenderer(renderer);



結果:ラベルが表示された。
sample2



今日はここまで。


(追記)Jung2を使って測定できる指標について調べ中。

BetweennessCentrality を使うと、媒介中心性を計算してくれる。
Betweenness centrality (媒介中心性)は以前調べていた。

・ある点の媒介中心性は他のすべての点同士の測地線にその点が
 含まれる割合。
 (最短のパスで通ろうとすると、その点を遠ってしまうペアの割合)
 あるネットワークの媒介性の集中度は、その大きさのネットワークが
 持ちうる最大の最大の媒介中心性の分散(スター型)で実際の分散を割ったもの。



KStepMarkovを使うとkステップでのページランクを計算してくれそう。

MarkovCentralityでマルコフ中心性を計算してくれそう。

RandomWalkBetweennessはランダムウオークで情報が伝わる際にどのくらい媒介するかしらべてくれそう。
スポンサーサイト

Introducing Gizzard メモ(3)

2010年04月13日 02:18

Gizzardというミドルウェアの話が紹介をメモ取りながら読んでいます。元記事は以下、
Introducing Gizzard, a framework for creating distributed datastores.

前半と中盤のメモ:
Introducing Gizzard メモ(1)
Introducing Gizzard メモ(2)

今回で最後まで読みました。

Gizard はフォールトトレラント

障害許容性は分散システムの最大の関心事である。なぜならそのような系では多くの計算機と
関係しているので、どんな時でもある確率で一つ(または多く)の機能不全が
起こっているからである。Gizzardは単一障害点をどのような形でも避けている。
もし、パーティション中のあるレプリカがクラッシュしたら、重み付け関数にしたがって、
Gizzardは残りの健康なレプリカにリクエストを案内する。もしパーティション中のすべての
レプリカが動作しない場合、Gizzardはそのshardに対する読みリクエストを実行することができないが、
ほかのshardには影響を及ぼさない。動作しないshardへの書き込みは再び書き込み可能になるまで
バッファされる。

実はいくつのレプリカが応答しなくても、Gizzardは応答するレプリカに可能な限り書き込みかつ
応答しないレプリカへの書き込みをバッファリングし、応答しないshardが生き返ったら後で
書き込む。標準的な戦略としてはすべての書き込みを二重化し、トランザクションの記録をとる。
書き込みはshard中のレプリカに対し非同期に(しかし可能な限り低い遅延で)処理される。
もしshardが応答しない場合は、書き込み操作はエラーキューに入れ、後で再実行する。

Eventual Consistency を実現するために、「後でリトライ」する戦略はあなたに書き込み
操作を冪等かつ可換であることを要求する。これは「後でリトライ」戦略は操作を順序に
関係なく適用する(一例として、失敗したジョブのリトライより先に新しいジョブを適用したりする)。
多くの場合はこの要求は難しくはない。GizzardのデモアプリRowzでは可換で冪等な書き込みが
実践されている。

素早いマイグレーション

時にshardからある計算機から別の計算機にデータをコピーしたり移動したりすることは手軽である。
あなたは負荷分散のために多くまたは少ないマシンへそれを行ったり、ハードの故障をとり扱うために
行うだろう。マイグレーションがどのように働くかのある側面を説明するのは興味深い、
ちょうど下に示すようなより不明瞭な論理shardタイプにおいて。データストアAからデータストアA'
いマイグレーションする時に、複製shardは両者の間に置かれ、さらにデータストアA'の前には
WriteOnly shardが配置される。そして古いshardから新しいshardへデータがコピーされる。
WriteOnly shardは新しいshardが立ち上がるのを守る、データはそこからは読まれない(なぜなら
そこには大きな全体の一部の絵しかないから)。

書き込みが順序関係なく起こるため(新しい書き込みが古いものより先に行われたり、ある
書き込み動作は二回行われたりする。)、すべての書き込みはデータの一貫性を保つために冪等である
必要がある。

以上。まあ、Rowzみてみろと、いうことでしょうか。

Introducing Gizzard メモ(2)

2010年04月11日 03:56

Introducing Gizzard, a framework for creating distributed datastores.

TwitterエンジニアブログでGizzardというミドルウェアの話が紹介されていて非常に興味深かったのでメモ取りながら読んでいます。続きです。GizzardはConsistent Hashingではないのですね。


Gizzardはフォワーディングテーブルを通して、パーティショニング処理する。

GIzzardはデータの範囲を各々のシャードにマッピングすることによって
パーティショニングする(つまり排他的な範囲で複数のホストに分割される)。
このマッピングは下記のテーブルのように、数値のレンジの下限と所属する
シャードの情報がフォワーディングテーブルに保管される。

正確にはあなた方はGizzardに次のようなカスタムハッシング関数を供給する:
データにキーを与え(このキーはアプリケーションに特別なキーであるべき)、
フォワーディングテーブル中のある範囲にいくつキーが属すのか決める。
この関数は必要に応じて自分でデータの所在やバランスに最適化するよう
プログラミングできる。

このようなテーブル形式のアプローチは様々の他のデータストアで使われている
いわゆる「コンシステントハッシング」とは異なる。この形式は一様でない
サイズのパーティションを許すため、非常に人気のあるデータのセグメントである
ホットスポットを簡単に管理することができる。実はGizzardはコンシステントハッシング
に似せてフォワーディング戦略を完全にカスタマイズすることもできるが、
これは推奨しないアプローチである。

Gizzardはレプリケーションツリーを通じてレプリケーションを取り扱う

フォワーディングテーブルから参照されるShardは物理Shardでも論理Shard
でも構わない。物理ShardはバックエンドにSQL Databaseのような
個別のデータストレージを参照している。対照的に論理shardはただの
別のshardのツリーであり、それぞれのツリー中のブランチはそれぞれ
バックエンドがデータストレージになっているノードの論理的なデータ変換と
なっている。これらのブランチにおける論理変換は普通、どのように読み・書き
の操作がブランチの子要素に伝わるかを規定する。例えばここに2階層の
レプリケーションツリーがあったとする。これが(フォワーディングテーブルから参照される)
「ひとつの」パーティションを表していることに注意。

図中の"Replicate"は単純な戦略でブランチは書き込みはすべての子要素に繰り返し、
読み込みは子要素の健康状態や重み付け関数によってバランスさせる。特定の
データストレージの要求により、自由にカスタムブランチや論理shardを作る
ことができる、例えば原始的なトランザクション/調停やクオーラム戦略を追加
することができる。しかしGizzardは多くの効果を得る少ない標準的な戦略のみを
採用している、それはWrite-Only, Read-Only, そしてBloacked(書き込みも読み込み
も許さない?)である。もっと無名なshardタイプの効用はMigrationセクションで
議論する。

レプリケーショントポロジーの厳密な性質はパーティションによって様々になる。
つまり高いレプリケーションレベルを「熱い」パーティションに、低いレプリケーション
レベルを「冷えた」ものにすることが出来る。これはシステムを高度に設定可能にする。
例えばバックエンドミラーをプライマリ、二次、三次、その他と定義することができる。
他にはより良い耐障害性のために(高度に複雑になるが)マシンにわたって「ストライプ」
パーティションを作りそれぞれがミラーにはなっていないようなものを作ることもできる。


・・・どんどん訳が酷くなってきたが・・・続く(たぶん)

Introducing Gizzard メモ(1)

2010年04月08日 04:01

Introducing Gizzard, a framework for creating distributed datastores (1)

TwitterエンジニアブログでGizzardというミドルウェアの話が紹介されていて非常に興味深かったのでメモ取りながら読んでいます。以下メモ。

sharding入門

現代のWebサイトは一台の計算機では効率的に情報を保存できないような量の情報に高速にアクセスする必要がある。
この問題に対する良い方法は情報を"shard"することである。つまり、情報を複数のコンピュータに分けて保存する。

シャーディング戦略はパーティショニングとレプリケーションの二つの技術を使う。
パーティショニングによってデータは細かい単位に分けて複数の計算機に保存する。それぞれの
塊はそれぞれのコンピュータで効率的に保管して操作やクエリできるように十分細かくしておく。
レプリケーションによって複数のデータのコピーをいくつかのマシンに跨って保存する。
それぞれのコピーは多くのクエリに答えられるようにそれぞれのマシンで稼働する。
レプリケーションはどこかのデータのコピーが壊れたり汚れたりしても他のコピーが
同じタスクをうまくこなせるようにも働く。

問題はシャーディングが難しいことである。ある種のデータを賢くパーティショニングするには
よく考える必要がある。さらに難しいのは信頼できないコミュニケーションや
予測できないコンピュータの障害に関わらずデータの一貫性を保つことである。
最近nオープンソースのDBはこの問題を解く助けになる。残念ながら
これを書いている時点では、ほとんどのオープンソースのプロジェクトは未発達で
現実の問題を解くには限られている。これらの新しいデータベースは将来の見込みは大きいが
現在はもっと経験的なカスタマイズが必要である。

シャーディングフレームワークとは

Twitterはいくつか分散データストアをカスタマイズした。多くは一般的によく知られているもので
我々で拡張することができ、簡単にメンテナンスできて再利用可能である。我々は
ScalaフレームワークのGizzardを拡張した。耐障害性を持った分散データベースを簡単に作る
ことができる。

Gizzardはあるクラスの問題をとくための標準的なテンプレートを提供するフレームワーク
である。このテンプレートは万人に完璧ではないがデータストレージ問題に関しては広く
活用できる。高いレベルでは、Gizzardは任意のバックエンドのデータストア(SQL Database,
Lucene,...)によるパーティショニングをマネージするネットワークサービスとも言える。
パーティショニングルールはフォワーディングテーブルに置かれ、それはパーティションする
キーのレンジをマッピングする。それぞれのパーティションは宣言されたレプリケーションツリーを
通じて自分のレプリケーションを管理する。Gizzardは「マイグレーション」(たとえばクラスタへの
弾力的なマシンの追加など)をサポートし、優雅に障害を処理する。システムは
すべての書き込み操作が操作が失敗して(例えばネットワーク障害などで)後で
やり直せば冪等であるような要求の元、Eventually consistetになる。

Gizzardの非常にシンプルな例がRowzという分散key-valueストアである。Gizzardを素早く
動かしてみたいならRowzをクローンしてカスタマイズするといいだろう。

しかし、最初にGizzardがどのように動いているか、詳細を見てみる。

Gizzardはミドルうウェアのようにネットワーキングサービスを操作する。それは
クライアント(標準的にはPHPやRoRのようなWebのフロントエンド)と多くのパーティションニングされ
レプリケーションされたデータの間に入る。中間に立ち、すべてのクエリと操作の流れが
Gizzardを通る。Gizzardインスタンスはステートレスでスループットを持続させることとTCP接続の
期限を管理する事だけが必要である、なぜならこれはJVM上で動作し極めて効率的だからだ。
TwitterのGizzardアプリケーション(FlockDB 分散グラフDB)はコモディティマシンを使って
10000のクエリを一秒間でさばくことができる。あなたのがたの受ける利益はもっと違ったものになるだろう。

Gizzardはどんなデータストレージでもバックエンドに持ってくることができる。

Gizzardはネットワークで扱えるデータストレージサービスをどんなものでもレプリケーションするように
設計されている。これはレリーショナルデータベースでもいいし、Lucene,Redis,何でも想像するもの
すべてよい。一般的なルールとしてGizzardは書き込み操作がすべての冪等であることを要求する、この
ことによりバックエンドのデータストアを使うためにいくつかの制約が設けられるだろう。特に
Gizzardは操作の順序を保証しない。それゆえに書き込み操作の順序がシステムの一貫性に影響を
与えないような設計が必須である。

続く(多分)



上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。