[StreamWeb] StreamTwitter デモ(日本語版)

日本語版StreamTwitterのコア部分のソースのディレクトリ
/nfs/home/oiki/spade/uryu/japantwitter

起動の仕方. まずrootで
/nfs/home/oiki/web/webserverの
./core.py
でWebサーバーを起動

次に
/nfs/home/oiki/spade/uryu/japantwitterの
./start_streams_streamtwitter.sh ; ./submitjob_streamtwitter.sh
でSystemS部分を起動

終了は./stop_streams_streamtwitter.shを実行し, core.pyをkill

[StreamWeb] デモの起動方法

demoにログイン.

StreamTwitterのコア部分のソース: ~oiki/spade/uryu/streamtwitter
Webサーバーのソース: ~oiki/web/webserver

[System S の 起動方法]
~/oiki/spade/uryu/streamtwitterの
% ./start_streams_streamtwitter.sh ;
%./submitjob_streamtwitter.sh
でSystemS部分を起動

[Web サーバーの起動]
% cd ~oiki/web/webserverの
% ./core.py


[停止方法]
% /stop_streams_streamtwitter.sh
- core.pyをkill

以下、老木君によるプログラム解説


streamtwitter.zip : System S 部分
web.zip : Webインターフェイス部分

プログラム間の通信は以下の流れで行われる。
1.ブラウザからWebインターフェイス。新しく補足する単語の指示や、単語の要求命令などが送られる。
2.WebインターフェイスからSystem S。新しく補足する単語の指示が送られる。
3.System SからWebインターフェイス。ポストデータが送られる
4.Webインターフェイスからブラウザ。ポストデータが送られる

streamtwitter:
streamtwitterにはSystem S関連のdpsファイルやソースファイルなどが含まれる。
streamtwitterの設定は以下のように変更する。

1.streamtwitter.dpsを変更する
nodepoolを変更することで配置するノードを変更したり、#define HTML_SERVERを変更することでWebインターフェイスを担当するノードを変更する

2.src/config.hを変更する
大量の#define文を変更することで細かい設定を変更できる。
重要なものとして、
GEOMETRY_FILE 経度・緯度変換情報を格納したファイル
COMMAND_PORT 通信2を受け取るポート

web:
webには３つのプログラムが含まれる。

・streammaker
Twitterのふりをするダミーサーバー。負荷テストに、用いる。これについては詳しく説明しない。

・html
Webサーバーによって公開されるフォルダ。現在のディレクトリは ~oiki/web/mimemapper/
index.htmlを代表とする画像やページやjavascriptが格納されている。
設定を変更するには、主にcore.jsを変更する。core.jsには設定用の変数が先頭で宣言されており、
periodtime : 通信4の頻度を設定する
zoom,centerpos : 地図の縮尺、場所

・webserver
Webサーバープログラム。apacheのように静的ファイルを外部に公開する機能と、SystemSからポストデータを受け取り、ブラウザからの要求に応じてそれを送信する機能を持つ。
設定はserver.confを変更することで行う。
html_base : 公開するフォルダ
html_port : 通信1を受け取るポート
post_port : 通信3を受け取るポート
server : System Sが起動しているノード
command_port : System Sが公開しているポート

またwebserverフォルダに含まれるCommander.pyを実行することで、ブラウザを用いることなく監視する単語を追加できる。
./Commander.py word といった風に用いる。
細かい使用法は-hオプションを参考にしてください。

起動手順:
start_streams_streamtwitter.sh,submit...を用いてSystem Sを起動し、webserver/core.pyを起動する。
なお、順番を気にする必要は無い。

補足：
かつてのバージョンでは場所によって、1時間中どれぐらい特定のキーワードが用いられたかを集計する機能が存在したが、InfoSphereStream1.2において、Aggregateオペレーターがtimebasedな場合、perGroupを用いることができなくなったため、現在は機能しない。

バグ：
長時間プログラムを実行させると、WebインターフェイスがSystem Sからポストデータを受け取るのに遅延が発生しはじめる。1時間あたり3分ほど？

[ExaGraph/Twitter] GraphCT

Massive Social Network Analysis: Mining Twitter for Social Good

David Ediger, Karl Jiang, Jason Riedy, David A. Bader, Courtney Corley, Rob Farber and William N. Reynolds. ``Massive Social Network Analysis: Mining Twitter for Social Good,'' The 39th International Conference on Parallel Processing (ICPP 2010), San Diego, CA, September 13-16, 2010.

Social networks produce an enormous quantity of data. Facebook consists of over 400 million active users sharing over 5 billion pieces of information each month. Analyzing this vast quantity of unstructured data presents challenges for software and hardware. We present GraphCT, a Graph Characterization Toolkit for massive graphs representing social network data. On a 128-processor Cray XMT, GraphCT estimates the betweenness centrality of an artificially generated (R-MAT) 537 million vertex, 8.6 billion edge graph in 55 minutes and a realworld graph (Kwak, et al.) with 61.6 million vertices and 1.47 billion edges in 105 minutes. We use GraphCT to analyze public data from Twitter, a microblogging network. Twitter's message connections appear primarily tree-structured as a news dissemination system. Within the public data, however, are clusters of conversations. Using GraphCT, we can rank actors within these conversations and help analysts focus attention on a much smaller data subset.

[StreamWeb] StreamWeb の論文が ICWS 2011 に採択されました

国際学会 ICWS 2011 (9th International Conference on Web Services) に出していた以下の論文が採択されました。採択率は 11%でした。

"StreamWeb: Real-Time Web Monitoring with Stream Computing" Toyotaro Suzumura and Tomoaki Oiki, ICWS 2011, Washington DC

有害 Tweet リアルタイム監視

データストリーム処理が応用できる例

http://japan.internet.com/busnews/20100831/5.html

"利用者のツイートが掲載される企業のキャンペーンページなどに無関係な宣伝や公序良俗に反するツイートが投稿された際は、リアルタイムでブロックしたり、メールでアラート"
"オプションで、ハッシュタグや一般キーワードの監視、商品購入を薦めるフレーズなどの自動ピックアップ機能"

WWW 2010 に論文提出完了

WWW 2010 (http://suzumura-lab.blogspot.com/2009/10/www-2010-cfp.html) になんとか金曜日から４日連続で書き続け、submit まではこぎつけました。

MapReduce と DBMS の比較

SIGMOD 2009 の "A Comparison of Approaches to Large-Scale Data Analysis" (PDF)

DBSM 界の巨匠である Michael Stonebraker が 昨今のMapReduce 騒ぎに、一石を投じる論文。Hadoop と 並列 DBMS を比較し, Parallel DBMS の方が速いという。しかし、Hadoop は Java ベースで、並列 DBMS は C/C++ で書かれているだろうが、あまり fair な比較ではないところが甘い。

詳細は以下の通り。

- 並列 DBMS は 100ノードにおいて、MR よりも 3.1 ～ 6.5 倍高速
- MR(MapReduce) は１０００ノードでスケールする、と主張しているが、Interactive Media などの企業でも40ノード弱であり、 eBay は Teradataという製品を使っており、72 ノードのみを使用しており、現実的にはそんな巨大なマシンは使っていない

SEDA の論文（続き）

このエントリのさらに続き

- Matt Welsh による SEDA の過負荷時の制御手法について論じた論文. DSMS における Load Shedding に関しても大いに関係してくる。
Matt Welsh and David Culler, "Adaptive Overload Control for Busy Internet Servers"

- SEDA の肝は 2.2 章に書かれているが、ソフトウェアをステージに分割し、開発者に明示的にキューのコントロールを許すことによって、アプリケーションに特化したパフォーマンスコントロールが可能になること。System S 自身はキュー自身は見えていないので、その部分は UDOP (User-Defined Operator) で実装する必要がある。また、ステージ化することのその他の利点は、パフォーマンスのボトルネックを発見するのが容易になること。ステージごとのキューの状態（常に満杯になっているか？）を監視することで、容易にボトルネックがわかるし、そこのキューだけを制御しさえすれば良くなる。

- ニュースサイトなどではある突発的な事故などが起きると、システムの想定するリクエスト数の百倍、千倍のリクエストが到着することがある (これを Slashdot Effect とかつては呼んでいた）。しかし、これらを想定して Capacity Planning していては Over Spec なシステム構築となる。よって、ソフトウェア的にそれらを回避する必要がある。

- 回避方法としては、コネクション数やスレッド数の上限を設定しておき、リクエストを受け付けない方法と、もう一つは、結果のクオリティを下げる方法がある。後者は例えば、HTML を通常版と軽量版 (Ethernet パケットに収まるぐらい。例えば、画像も解像度を低くするなど）の２つを用意しておき、過負荷時には軽量版の HTML ファイルをクライアントに返す方法などがある。

- この従来の手法は、コネクション数とスレッド数をサーバー管理者が Web サーバーの設定ファイルなどに設定する必要があるが、これは経験的に決められたものであり、必ずしも最適値にならない。よって、低い値にしまいすぎて、スループットが出なかったり、大きくしすぎると、常にシステムが満杯状態で、すべてのリクエストに対してレスポンスタイムが悪くなるという事態に陥ってしまう。

- このようなケースは、Web サイトの運営者側からすると宜しくない状況で、レスポンス時間が長いと、顧客が離れていってしまう恐れが高まる。運営者からすると、平均的にすべてのユーザーに悪いレスポンスタイムを返すよりも、一部のユーザー（例えば１０％）には、きっぱりと、「今は混んでるから後から来てね」と断り、他の90％に対して、それなりに acceptable なレスポンスを返してしまった方が良いだろう。

- この論文では、上記のような問題に対して、パフォーマンスコントロールを柔軟に可能にするフレームワークを SEDA 上に構築。Web Mail システム Arashi を構築して評価している。

- SEDA のキューに入ってくるメッセージの処理時間（レスポンスタイム）をモニタリングし、その傾向によって性能制御する仕組みを設計。例えば、レスポンスタイムが悪くなってきたら、ある一定数の確率でリクエストを Drop したり、他のサーバーに割り振ったりする。

- キューを監視するコントローラを設定し、リクエストがキューに入った時間と、処理を完了し、クライアントに結果を返すまでの end-to-end の時間を測定。その TAT (Turn around time) がある閾値以上になったときには、Load Shedding アルゴリズムを発動させ、一部のリクエストを優先して処理し、一部はあきらめることによって、全体のレスポンスタイムの中央値を良くする手法を提案。

StreamWeb の方向性(続き)

このエントリの続き

　研究の Contribution が「単に既存のアルゴリズムを System S にのっけました」的な論文になる恐れがある。これや、これなどのアイデアを核に研究を進めて行く方が、新規性も出しやすいし、かつ論文にも通りやすいはず.

ただし、産業界が即求めているのは、このエントリに書いたようなこと。研究としての新規性を出すのか、実用性を重視するのかの判断は難しいが、確実に学会では前者が評価される。

Click Fraud Detection Algorithm

WWW2005 に採択されたクリックストリームに関する論文

Duplicate Detection in Click Streams, Ahmed Metwall (UCSB), WWW 2005
http://www2005.org/cdrom/docs/p12.pdf

StreamWeb の方向性

StreamWeb プロジェクト、特に森田君が卒論で行う研究テーマに関する Main Contribution は以下の通り。

- ストリームコンピューティングの Web への（ほぼ）初の応用
- 以下の３つの応用を DSMS で実装し、有効性を示す。評価は、DSMS なしのバッチ型のバージョンと、DSMS でリアルタイムに処理する手法を比較。結果が得られるまでの時間、および必要なストレージ量が DSMS のバージョンが上回ることを示す。

(1) リアルタイムログ処理および圧縮処理
(2) 売り上げ状況を店舗にリアルタイムに伝える
(3) Click Fraud Detection (既存の Fraud Detection Algorithmを作る）

- 上記アプリケーションを GPU で性能最適化

研究の方向性としては、上記作業によってパフォーマンス特性がわかるので、この後、以下の研究テーマに広がっていく。
(X) Online と Offline の処理の融合 (スケジューリングなど）
(Y) Cloud との融合 (Eucalyptus)
(Z) Load Shedding の技術の融合

ClickStream の分析ツール

ClickStream の分析ツールのオープンソースソフトウェアは、ここに
リストアップされている. いずれも、Apache などのログから、グラフ視覚ツール graphviz を用いて視覚化。
Apache2Dot
Visitors
Web Utilization Miner
Statviz
"StatViz can actually show you these reports LIVE... If you configure the logfile to "php://stdin" then StatViz will read the log lines from STDIN. It will then periodically generate reports as the log is processed, thus allowing you to watch your traffic patterns in real-time" だそうで、リアルタイムに視覚化することも可能。

クリックストリームの過去の研究は、ここ (PDF) などが参考になるので、見てみてください。

Predicting Online Task Completion with Clickstream Complexity Measures: A Graph-Based Approach
http://www.net-question.com/chairerbc/fichiers/KSN06.pdf

ここによると、Click Fraud (Wikipedia) の Real-time Detection にも System S が使えそうです。

"As pay-per-click advertising becomes the fastest growing segment of all　advertising tools, malicious click fraud is keeping pace and shows no signs of　containment.　Advertisers are demanding resolution to this problem because it can cost them millions of dollars. Successful search engines, marketing companies and e-businesses know that fighting click fraud means quickly recognizing patterns, either through statistical algorithms automated for online filtering, or manual offline analysis. These analyses require comprehensive processing of terabytes of dynamic, detailed data in near real-time to quickly detect and stop the fraud from spreading."

また、Google でも Click Fraud Detection の対策をしているようです.

Botnet （悪意のあるコンピュータプログラム）による Click Fraudによる非常に深刻らしく、Fraud の31％が Botnet によることを示したグラフ（http://www.techcrunch.com/2009/01/27/report-click-fraud-at-record-high/）

ClickStream

Web サイトでのユーザーの行動履歴 ClickStream はWikipedia によると、売買されているものらしい。しかし、このデータ自体は場合によっては個人を特定できてしまう。AOL は一時期、研究用途に限り、検索クエリのログデータを Web 上で公開していたが、個人が特定できることがわかり、裁判沙汰になったことがある。

ユーザーのクリックストリームデータは、ユーザー（顧客）の嗜好や行動パターンなどの分析に非常に意味があり、以下のようにも書かれている。StreamWeb プロジェクトでは、このクリックストリームをリアルタイムで即座に解析することによって、よりビジネスの差別化につながれる技術基盤を作れると良いだろう。

As discussed in Van den Poel & Buckinx (2005), clickstream analysis can be used to predict whether a customer is likely to purchase from an e-commerce website. Clickstream analysis can also be used to improve customer satisfaction with the website and with the company itself. Both of these uses generate a huge business advantage. It can also be used to assess the effectiveness of advertising on a web page or site

大規模 Web サイトの内部アーキテクチャ

大規模 Web サイトの内部アーキテクチャについて語るサイト
http://highscalability.com/
http://highscalability.com/youtube-architecture

ストリームコンピューティングのすごさを伝えるデモ

　昨日も松浦くんと森田くんと雑談したが、ストリームコンピューティングの凄さを伝える Visual なデモがあると良い。ストリームコンピューティングという計算パラダイムのシフトによって、今の世界がこんなにも変わる、というようなことが伝えられたらいい。以下は候補。アイデア募集。

- ストリームコンピューティングの概念的なデモ
- 大量データを実時間でオンメモリ上で処理する様子を写し、ストレージ容量の削減とリアルタイム性
　　を削減する様子を視覚的に見せる
- （一般向け＆うけねらい）　回転寿司

- ストリームコンピューティングの応用のデモ
　- StreamDNA: パーソナル医療への応用など。（もっと深める）
- StreamWeb:
　　　 - SNAzzy で見せたような、CDR (Call Data Record) のグラフを
　　　　リアルタイムに行う様子を見せる
- 数百万の人の群れの動きを可視化し、自分があるストリートを歩いていたら、自分の嗜好に合う
　　　　イベント広告が配信される

VWAP

System S のサンプルには、VWAP (出来高加重平均価格) というアルゴリズムトレーディングで標準的に使われている実装があります

楽天技術研究所

　今日は千葉研（数理計算科学専攻）出身の西澤さんが勤める楽天技術研究所に、松浦君、森田君と訪問させて頂きました。ストリームコンピューティングの話しをしましたが、それなりに興味を持って聞いて頂いたように思います。実際に、ネット企業に勤めている人のご意見を伺えて少しは、StreamWeb の妥当性が目に見えてきたのではないでしょうか。また、お話しを伺いにいきましょう。

今日、紹介してもらった Fairy と ROMA 以外に、２６００万商品と４８００万人のレコメンドエンジン「万華鏡」、似ている画像を識別する検索エンジン「似姿」というものがあるようです。（参考サイト）

ここやここを見ると、大体の出店数が把握できるので、チェックしておいてください。

楽天で発表した資料はここ

データストリーム処理とバッチ処理への動的リソース割り当て

　Web への応用を考えているのだが、DSMS の一つの応用はリアルタイムログ解析、ログ圧縮などである。しかしながら、トラフィックが少ない時には、DSMS に割り当てたハードウェアリソースもアイドル状態のままになる。データ解析は DSMS のみで完結するわけではなく、後処理としてやはり従来手法のバッチ処理が必要になる。よって、上記のアイドル状態のときは、バッチ処理にアイドル状態のリソースを割り当てる方が好ましい。一つの研究テーマとしては、これをダイナミックにコントロールするメカニズムを考案することである。

上記の考え方は、Web のみならず、様々なアプリケーションに適用可能なはずだ。

GPU を用いた DSMS のスケールアウト処理

以下、研究テーマ。

研究概要

近年の DSMS 処理の研究では System S などを代表として、分散処理によるスケールアウト技術が注目されている。しかしながら、スケールアウトを実現する手法としては、現在の所、ノードレベルでしか考えられていない。本研究では、GPU の超並列コアによるスレッドレベルの並列化と Stream Processor による命令レベルの並列化を組み合わせることで、DSMS におけるスケールアウトを実現する手法を提案する。また、System S のプログラミングモデルである SPADE をそのまま踏襲し、そのコンパイラを拡張することによって、下位のハードウェアやスケールアウトの実現方法を隠蔽し、アプリケーション開発者から透過的に実現する。

本研究の評価として、YY 種類のXX 億個の株価データ（合成データ）を用い、ZZ 個のウィンドウサイズ(スライドサイズ 1)に対して移動平均、最大値、最小値を計算する。このウィンドウ処理は　DSMS における典型的な処理であり、応用範囲は広く、 例えば、金融の分野における株価分析、通信会社の通話時間分析などが挙げられる。通常の CPU (1ノード、2～4 core、SSE 命令使用)、GPU 版 (1ノードのみ）、複数ノード (4ノード以上）を用いてそれぞれスループットを求め、GPU が明らかに最高性能が得られることを目指す。

本研究の Contribution は以下の通りである
- ストリーム処理と GPU 処理の組み合わせ
これはまだ未開拓の分野である。
- GPU 上で実現することによる性能最適化手法
CPU から GPU へのデータ転送時間と GPU 上の計算時間をオーバーラップさせることにより、通信のレイテンシを省く. また、その他の実装上の工夫について述べる。
---------------

この研究の続き
- アプリケーションの例としては移動平均であるが、国際論文として通すためにはもう一つアプリケーション例があると更に良い

ヒューリスティックスを用いた性能最適化

Zipf の法則というものを知っていますか？ 一般化したものは Power Law といいますが、様々な分野で起こる現象のヒューリスティックス（経験則）です。

Zipf のひとつのインスタンスに、パレートの法則や80:20 の法則というものがあります。たとえば、２割の顧客がその店の８割の売り上げに貢献している、などです。インターネットの検索キーワードにもこの法則が成り立つことがわかっていて、２割のキーワードが全体の８割に近くになります。

このようなヒュースリティックスは、パフォーマンスの最適化、たとえば、キャッシュのポリシーの設計方法などに大きく参考になります。たとえば、われわれは、データストリーム処理システムにおける性能最適化を研究していきますが、過負荷時に処理を間引く技術分野として Load Shedding といわれる分野があります。まだまだ発展途上の研究分野ですが、Power Law の経験則を用いた Load Shedding などは良い研究テーマになると思われます。