koie blog

• 2016-03-21 13:40〜18:20
• 東工大 西8 W809
• https://facebook.com/events/494071657461395

家を出るのが遅くなって目黒乗り換えにミスってトータル9分ロスしてゆっくり昼飯くう時間はなさそうで、駅前のマックで100円x2で腹ふくらかそうとしたら人があふれてたので、大岡山駅前のスーパーでおにぎり2個で昼食205円。しかし205円で320kcalは少なかった失敗。

どうやら応用物理学会(JSAP)をやっているようでキャンパスはダークスーツ集団で埋めつくされていた。かなり規模でかそう。

西8号館のエレベータ乗ったらE棟だったらしくエレベータおりてすぐ土禁になっててびっくり引き返す。3階にひきかえしてW棟のエレベータの乗って8階へいくとまだ部屋が開いてなかったのでリフレッシュルームでおにぎりもぐもぐ。天気がよくなってきて見晴らしがよい。

[2016-03-21 13:38]

• 首藤さん前説

[2016-03-21 13:41]

SensorBeeの紹介 / 柏原秀蔵 (@suma90h) (PFN)

• http://www.slideshare.net/suma_/sensorbee-59828977
• bit.ly/distributed2_sensorbee
• ネットワークエッジでストリームデータを機械学習
• ETL: extract(前処理) transform(加工) load(DBなどに書き出し)
  • storm norikra sparkなど
• BQL (sql like language)でfilter,aggregate(平均とか),join(複数のストリームの結合とか)できる。
• LIDAR(ライダー)は可視光カメラと併用されていくのではないか。
• source/sink/state/stream
  • 状態をもてる(user-defined state)
• ETLツールなので分散システムというわけではない。
• UDF/UDSはstaticlink。だいたい30MBくらいになる。Go言語。
  • 実行の種類: run,runfile,shell,topology,... (マイクロサービスっぽい感じ)
• python C-APIがハマリポイントだった。いろいろメンドクサイらしい。
• JavaのJNIは重いかわりにつかいやすかった(首藤)
• http://sensorbee.io
• Q: BQLからつくられたグラフはどう処理されているのか？
• A: パイプで非同期に動いているとおもう。
• Q: UDF/UDSのとっかかりは？
• A: goで書く。pythonでも書ける(基本オブジェクトのやりとりしかできない)。
• Q: wc
• A: UDSが必要。
• Q: 耐故障は？
• A: キューが伸びるとドロップする。マシンが落ちたらおわり(作り込んでない)。
• Q: なぜgo?
• A: 社内がgo。C++はいや。静的コンパイルしたい。
• 静的リンクはあり。
• JITコンパイラは実地での再現がめんどくさい。(首藤研で研究中)
• chainer連携
• BQL: source=opencv sink=fileというのを簡単に書ける。opencvを書かなくてもよい。
  • tee的なUDFがオフィシャルにあればデバッグにいいかも。
• 分散処理にする予定はない。
  • sinkとsourceをfluentdでつなぐとかは、最悪あり。
• 人物検出をCPUでやってて遅い(i5)。FHDで15fps。
• フロー制御はない。Javaで標準化しようとしている。(reactive stream?, NETFLIX:reactive socket?) なぜHTTP2じゃない？とか
• PFIは投資をうけない、PFNは投資をうけるために分けた。IとNは関連会社。

[2016-03-21 15:04]

休憩

[2016-03-21 15:30]

分散処理と関数型プログラミング / 岡本雄太 (@okapies)

• https://speakerdeck.com/okapies/distributed-system-and-functional-programming
• 東工大の授業でJavaからScalaに変わったらしい。
• Scala: ネットワークプログラミングや分散につかわれている。
• Steve Yegge の Google とプラットフォームに関するぶっちゃけ話を訳した（前編）
• 分散システムをなぜやるか: スケーラビリティ・耐障害性・組織(マイクロサービス)NEW!
• マイクロサービスアーキテクチャの特性を2つに分けると:
  • 組織の特性(目的)
  • 技術の特性(手段)
• Conway's Law (軍事組織のソフトウェア開発の研究) 組織の構造がソフトウェアの構造に反映される。
• SOA(service-oriented architecture)は失敗した。ESB(enterprize service bus)はスマートなパイプを実現しようとした。
• マイクロサービスでは賢いエンドポイントと愚かなパイプ。
• SOAとESBの違いはトップダウンかボトムアップの違いではないか。(みずほはSOAらしいが..)
• 強いモジュール境界・独立した配備・技術的多様性
• 分散オブジェクト設計の第一法則： オブジェクトを分散させるな。
• マイクロサービスのコスト: 分散・結果整合性・運用の複雑さ
• ネットワークレイテンシの壁: googleサービスを日本で使うのと西海岸でつかうのとで体感速度が違う。
• kumagi:asyncとnon-blockingをつかいわけよう。
• 同期呼出で待ち時間がもったいない→コールバック→地獄/破滅のピラミッッド
• 分散と関数型プログラミングでモジュール化が簡単になる(実用的にはモジュール性を高めるための手法)
  • モジュール性を高めるためにOOは状態をカプセル化した。FPは状態をなくした(状態はモジュールの境界に置く)。
• composabilityが鍵。そのために数学的な手法をつかう。
• 外界←→副作用あり→副作用なし
• 糊: 高階関数(コンビネータ)と遅延評価
  • 問題を分割する方法は解と解を貼り合せる方法に... (quickcheckの作者...)
• whatとhowの分離: whatはDSLで記述、how(ランタイム)で解釈実行。 → SensorBeeのBQLがDSLに相当
• (...モナド...)
• Future/Promiseもモナド
  • 成功・失敗: RPC失敗したらmapで関数適用してくれない便利なやつらしい
• scalaだと: futureはreadonly, promiseだとwritable。言語によりまちまち。
• 便利なやつ: map, flatMap, sequence.
• val userAndTweets = Future.join(userService.findByUserId(userId), tweetService.findByUserId(userId))
• RPCだから副作用は発生しているが、プログラマ視点では副作用がない純粋な記述になっている。
• 失敗からの復帰はrecoverを書く。
• タイムアウトは別途書く必要がある。
• マイクロサービス向けフレームワーク
  • Netflix OSS
  • Twitter Finagle(フィネーグル), Zipkin, etc..
• finagleがつかえるからscalaをつかうという流れ
• your server as a function: futureとservice,filterの組み合わせでサーバを記述する。
  • service: requestをうけとってresponseを返す関数
  • filter: requestとserviceをつけとってresponseをつつんだfutureを返す。
• これってデータフロー処理?
• FRP(reactive extension)
• Akka streams: actorベースの上でデータフロープログラミング
  • FlowGraph DSLという、きもちわるい記述がある 〜＞
• Rubyは動的にメソッド定義できるところがDSL向き(首藤)
• 業界標準のデータフロー定義の流れ: Apache Dataflow (apache Beam)

[2016-03-21 17:28]

休憩

[2016-03-21 17:39]

分散データストアの因果整合性違反度測定手法 / 高塚康成

• データ間の依存関係の整合性は保証しないんものがほとんど。
• 保証するのにDBがやるかミドルウェアがやるか。アクセス性能が低下してしまう。
• そもそもどのくらい因果整合性が違反している頻度はどのくらいなのか？ → 測ってみた。
• アクセスログで測定する手法の提案。
• これまでに読みだしたデータが依存するデータより古いバージョンを読み出してしまったかどうかをチェックする。
• 依存関係グラフ: write-after-write(同一クライアント) or write-after-read(任意クライアント)
• 実験対象: CassandraとDynamoDB
  • Cassandra: 直感と反してアクセス範囲が狭いときに違反がほとんどない。
  • DynamoDB: 直感どおりアクセス範囲が広ければ違反が減っていく。
• 既存研究とのちがい: 測定ワークロードを限定しないところ。

[2016-03-21 18:03]

[2016-03-21 18:05]

@kumagi

• twitterやfacebookでばらさないようにということだったので
• 要約すると「副業してないといえる10の理由」という感じか。
• 才能の無駄遣いだなぁと思う一方、楽しそうだ。

[2016-03-21 18:17]

懇親会

大岡山周辺のお店は(おそらく学会の影響で)どこも満席のため、緑ヶ丘の「ちゃんこ芝松」へ。

腰痛はひどくもならず無事帰宅。

東工大西8号館W棟としか書いてないのでちょい迷った。

• 2011-06-18 14:00〜19:00
• http://www.siprop.org/ja/2.0/index.php?%B3%AB%C8%AF%2F%A5%B3%A5%DF%A5%E5%A5%CB%A5%C6%A5%A3%A1%BC%2F%CA%D9%B6%AF%B2%F1

Discussion on the P2P Distributed Serach System

• 藤坂祐介さん @ceeflyer
• 情報検索とは: ある語句に対して紐づけられたデータをとりだすこと
• アメーバブログ 1日100万件ずつ増加 → 10件/s テキストだけでTB越え
• 故障対策、スケールアップ/スケールアウト(小さなところから始めるので)、インデックス構造の作りかた
• AKB総選挙 検索要求 200件/s
• Solr(そら) search → application ←→ broer ←→ slave ←→ master ←→ index date ← index
• マスターサーバの存在がクリティカルポイント ダウンするとサービスが止まる マルチマスターなどの対策もあるけど
• とにかくサービスを止めない
• リアルタイム検索 反映に何分ではイケナイ サービス的な要請
• 既存 Zoie (with Lucene)、 Caffeine (google)
• FARE(フェア) systemをつくった
• 1. No Master-Slave, 2. Peer to Peer, 3. Realtime indexing
• No Master-Slave
  • 1台で起動する→Primary mode
  • 起動したノードにアタッチ → Secondary mode
• msgpackRPC使用
• ./fare --secondary 10.0.1.2 でアタッチ
• レプリケーション
  • データの消失をふせぐ
  • Consistent hashingの考え方でレプリケートする
  • replication=3だと前3ノードまでが責任範囲
• 仮想ノードがないと、ハッシュ値がかたよったりノードの責任範囲がかたよったり検索ワードのかたよりとか、ノードが過負荷になることがある。
• indexing
  • RPCをうけとったノードが形態素解析
    • 単語ごとにハッシュ計算
    • 本文情報に
• インデックス構造: Queries(単語の空間) → Invert Index(ポインタのかたまり) →→→ Contents
• インデックス情報
  • skip pointer( → dictionary(単語が辞書順) → invert index ... id ...> skip pointer → content → appendix
    • invert indexはkey,valueでいえばvalueだけならんでいるイメージ
• searching
  • queryを形態素解析
  • 単語のハッシュ値で検索→intersection(and検索)
  • 文書IDのハッシュ値で文書取得
• インデクシングがリアルタイム
• 検索に秒がかかってはぜったいにダメ
• ノード間連携
  • 1000台以下の中小規模ネットワークを想定 なのでフルメッシュになっている
  • 生存確認はbeaconをだしているlive応答を返す 応答がなければRunnging→Suspendになる
  • ノードを切り離すには手動で Dead にして全員に通知 クラウドストレージとP2Pの違い
  • suspend→runningになったらそれまでのデータをあつめる
• ラックまるごと落ちた場合はあきらめる。
• 同時更新の場合の一貫性はやや課題がのこっっている。
• http://code.google.com/p/fujene/
• 文書(コンテンツ)自体ももってる。(ストレージの役割もある)
• ノードダウンはメンテナンスのときくらいで8時間くらい。
• 文書の更新頻度 100文書/s くらい
• 1物理マシンにつき仮想ノード1000くらい
• ホットスポット(特定のコンテンツに集中)
• 負荷状況を監視しているノードがあってもいい。このノードがおちてもサービスは継続できる。
• 形態素解析ではNグラムのはいったものをつかっている。N=1,2,3でやっている。
• ノードは100台単位で用意できるときいている。

スケーラブルなストリームPub/Subプラットフォームの提案と評価

• 見上紗和子さん NECサービスプラットフォーム研究所
• コンテキストアウェアサービス
• 実世界情報=イベント
• モバイル広告 位置情報に基づいたクーポン送信とか
• 考慮すべきこと
  • せっかく来たのに店が混んでた → より詳細な情報を活用してサービスを提供(店が空いているかどうかなど)
  • 4時間前にいた場所の広告 → タイムリーにサービスを提供
• センサーから事業者の間に「ストリームPub/Subプラットフォーム」をおく
• イベント: 属性名=属性値
• ルール: イベント条件 属性条件(属性名=属性値の組) と 配信先指定 配信先=サービス
• 要件
  • スケーラビリティ: イベント数、ルール数、ルール変更数
  • 多種多様な属性の収容: 種類が増加してもスケーラビリティを維持
  • ルールの必要十分な記述: 包含指定も必要
• キー空間でマシンわりふり
• 従来技術の課題

• - mercuryは属性ごとに空間が別になるのでスケールしない
• 拡張局所性保存ハッシュ関数
  • 局所性保存ハッシュ関数 f (従来技術MAAN) a
  • 拡張局所性保存ハッシュ関数 F : F(x,a) <= F(y,b) iff (x
  • 属性名がおなじならf()の順序が保存される。ちがうなら属性名の辞書順に。

のりつなさん

• ベトナム
  • 声をかけられたタクシーにのるとぼったくれる法則
  • コインはない。1000ドン以下だとおつりはアメがかえってくる。
  • 20000ドン以上だと偽造防止でプラスチック製
  • 米ドルもつかえるがタクシーでつかえない。
• 台湾
  • ケータイのデコレーションが日本よりすごい
  • レシートに宝くじの番号が印刷されている。max 1000万円くらい。レシートデータをおくって税務署から番号が発行されているので脱税できない。
• (あまりに大量なので消化しきれず途中でおわた)

どーでもいいけどtip9ugでよく利用してたいろはがなくなってたというはなしをきいていたのを確認した。

第二十四回P2PSIP勉強会にいってきた。場所はいつもの首藤研ではなくギークハウス武蔵小杉。(天気が雨で風も強かったので行くかどうか実はちょっと迷った)

@did2memo 「FRTに基づくルーティングアルゴリズムデザイン」

DHTの説明があったあと、経路表がIDしか考えてないのは制限がきつすぎるよねーという問題提起。そもそも経路表はいろんなのがあるはずで、DHTはノード数Nに対して経路表のエントリ数がO(log N)になる経路表の集合のなかの1つにすぎない。そこでIDだけで決めるのをやめるにはどうすればいいかという話に。

そこでFlexible Routing Tables (FRT)の提案:

ルーティングアルゴリズムに合せて ≦ID という経路表を比較する演算(小さい方が良い経路表を定義して

• 1. 到達性保証操作(最低限の保証)
• 2. エントリ学習操作 (知ってしまったエントリをどんどんつっこむ)
• 3. エントリ厳選操作 エントリを削ったときに ≦ID 的にもっともよくなるように。

1→2→3→2→3→のように1を保証した上でエントリを増やしたり減らしたりすることで次第に最適な経路表になるというしかけ。

具体例としてFRT-Chordの説明があって、最低限のエントリを経路表につっこんだ上で、短縮倍率 = HOP後の残りID距離 / HOP前の残りID距離 (距離というのはID空間での距離) を定義して、経路表の中で短縮倍率が最悪(最大)なものを経路表の短縮倍率として≦IDを短縮倍率の大小比較として定義することで、短縮倍率が均等な経路表ができあがるということであった。

単純にエントリ数を増やせばどんどん短縮倍率は小さくなってゆくが、増やしすぎるとノードダウンで経路表を再構築するコストが増えてくるので、適当なサイズがあるのではないかということであった。

[2011-04-30追加]

• [NS研究会][Flexible Routing Tables]柔軟な経路表：経路表空間上の順序関係を利用したオーバレイネットワークルーティング方式(2011/03/04)
• ChordアルゴリズムによるDHT入門

@kumagi 「範囲検索の一貫性」

前提条件としてISPをまたがるようなネットワークではなくてデータセンターのようなall-to-allができる環境を想定。

範囲検索を分散してスケールさせるために一貫性と耐障害性を確保するにはどうすればよいかということで、

• KVS(キーバリューストア)が耐障害性を担保して
• その上に分散ハッシュテーブルをのせて
• さらにその上にSTM流のトランザクションをのせて
• 自由なデータ構造を構築できる

という方向らしい。

• STMでアトミックな更新を実現する構造(おれおれメモ)

struct Variable {
    struct Locator* locator;
};
struct Locator {
    T* old;
    T* new;
    Owner* owner;
};
struct Owner {
    enum { COMMIT, ACTIVE, ABORT } state;
};

[2011-04-30追加]

• 範囲検索の一貫性

@did2memo 匿名掲示板の開発

wikileaksみたいなに属人性(特定の個人が単一障害点になる)のはマズい。

そこで受信者ではなくて送信者を隠せるようにして匿名の情報提供ができるようにしたい。

その手法として

• つねにあやしい送信をつづけることで情報発信を隠す
  • このため大きなファイルを送信することはできないという制限あり
• 2つのパケットを待ち合わせてから転送することでパケット間の相関をなくす
• chordで大きくジャンプすると発信者の可能性が高くなってしまうのであえて効率を無視して小さくジャンプするとか。
  • token ringっぽいね。

しかしこのようなソフトウェアが一般化してしまうと「道端に包丁を置くようなもの」になっていまい問題があるとして、採択はされなかった。いまのところこのようなソフトを必要としているのは中国の人権団体くらいらしいが、他にいい応用例はないだろうか?とのこと。

@nekomatu 実世界とオンラインサービスと融合するためのオーバレイネットワーク構築手法

人間か感じる範囲に限定した通信というのを考えている。いってみれば観光地のゲストノートみたいなもの。人が集まっているときは安定していて解散するとネットワークが消えるイメージ。似たようなものにiDovatterやNintendoDSのすれちがい通信などがある。会場でのブレストでは以下のような意見がでた:

• 加速度でクラスタリング 列車特定
• 環境音で場所特定

@ohnishim 災害ネットワークのはなし

• メッシュネットワークはリンクがいっぱいあるので分断するのがとっても難しい。
• 低レイヤはスケーラビリティがない。
• 災害時は上のレイヤ(ネットワークやDB)は使えなくなる。
• ロケーターの広告が重要。
• リンクはしょちゅう切れるので、そのたびにフラッディングするとルーティングテーブルが安定して組めない。
• 世の中ではノードをクラスタリングして代表ノードだけにすることでネットワークを小さくして回避している。
• そもそも離散グラフをベースにすると広告の量がへらせないという問題! (これ重要、らしい)
• ジオメトリックルーティング (グリーディルーティング)
  • 位置情報をベースに近づく方向に転送する。
  • でも袋小路に嵌り込む危険性がある。
• そこでドロネーグラフ!
  • なんでも三角にしちゃう。
  • 基本中の基本らしい。
  • 三角にならないなら足りないリンクをトンネルでつくっちゃう。
• 世間でおこなわれているルーティングを安定させる方法は
  • 品質をあげる
  • 帯域をあげる
• もういっかいさがす
  • L2はtreeを決めたらそれをずっとつかいつづける
  • P2Pはちかくまでいったらしらべなおす
    • ちかくという概念がむつかしい
    • 離散グラフで「方向」という概念はむつかしい
• 宛先をかきかえてしまうのもある。コンテントベースルーティング。
• 世の中の論文でヒューリスティックを試してみました!これだけ改善しました!論文が多すぎる。こんなのは終わりがない。こういうのを書いてる奴はいったい何考えてるんだろうか.

本格カレー

• 懇親会をキークハウスでやることになって、@kitaindia さんがつくってくれた。
• ふつうのトマトカレーとマスタードの種入り大根カレー
  • ちょっと辛め
  • 香辛料がしっかり
• 
  

グダグダタイム

• binary XML のメリット
  • 小さくなる
  • あいまいさがなくなる

• 高専卒で就職
  • 推薦がほとんど。自由応募はほとんどなし。企業側が推薦を受け入れるのは辞退されないという側面もある。
  • リーマンショック後、ほんとにきびしい。数字にでてる。

• なんでSIになりたい学生が多いんだろうか
  • かっこいい金融系SIの例
    • 「おれがトランザクションをロックしてあるあいだに逃げろ!」
    • 「一貫性がくずれるぞ!」
    • 「abort!」「abort!」「abort!」

• 社会人ドクター
  • 時間の問題。働きながら研究の時間をつくるのはたいへん。
  • 修士のテーマがそのままつかえない。
  • 留学で一気に仕上げる方がいいかも。

• 成田空港で景気がわかる
  • 不景気になるとスルスルに。

• 大西さんはカードゲーム収集家
  • ドイツ人は同人誌をつくるノリでボードゲームをつくって毎年アワードをきめている。
  • なぜか鞄にカードゲームがいくつも入っている。
  • 「はやぶさ君の冒険」がはじまる。
    • 勝ち負けがない。ゲームとしてはめずらしい。
    • 結局、地球に帰還できなかったようだ。プレイ時間は1時間ほど。
  • 
    

• SNZI
  • アトミック命令でインクリメントはキャッシュコヒーレンシをとるために遅い。
  • そこでSNZI
    • ツリーをつくって書き換えを減らす。
    • そのかわりメモリを消費するのでキャッシュのサイズとスピードを交換しているとも考えられる。

• おすすめchrome拡張
  • bubble translate
  • galc

• gnunet
  • ダウンロード量に制限がある。
  • 中継するとたくさんダウンロードできるようになるらしい。

ネットワーク高度利用推進協議会シンポジウム

「商用Ｐ２Ｐによるコンテンツ配信ビジネス最前線」

• http://www.fmmc.or.jp/news/H103index.html
• 株式会社ビットメディア http://scast.bitmedia.ne.jp/fmmc/
  • chromeで再生しようとしたらプラグインが自動installできなかったのであきらめて
• ウタゴエ株式会社 http://utagoe.com/p2p/
  • こっちをつかった。
  • Java + flash
  • よく切れる。プロトタイプだからしかたないというところか。
• Twitter: http://twitter.com/search?q=%23fmmc

ほんの一部しか聞いてなかったのが、ちょっとまとめ:

• UG Live:Flaashでのスケーラブルライブ配信が創造する事業
  • 日本では ustream.tv が有名だけど、世界的には justin.tv がNo.1。
  • 回線費用を考えると 1万人へ配信コスト＝1000万円 くらいになる。
  • UG Liveをflashにしたのは、広告代理店などクリエイターな人たちに使ってもらいたいから。
  • flash化でインストールなしで使えるようになった。
  • 配信コストは 品質 - 接続人数 - 配信時間 の3軸で考える必要がある。
  • このバランスによって P2P がいいか通常のストリーミングがよいか分かれる。
    • たとえば視聴者のうちの1%くらいが有料会員として獲得できるようなケースや
    • 逆に有料で配信するようなケース
  • iPhone版は数ヶ月後に出るらしい。
  • yahooの調査によるとTV関係のキーワード検索が半数を占めているので、配信ビジネスには可能性がある。
    • 会場ではメールを送るとニコニコ動画のように動画にコメントが流れ、抽選で商品券が当るというデモをやっていた。
• 商用Ｐ２Ｐによるコンテンツ配信ソリューション事例
  • サーバにftpで流し込むとbittorrent改で配信されるしかけ。
  • ゲーム配信はピークが普段の100倍もあるので、ピークに合せて設備をととのえると大変なことになる。
  • CDNは従量課金なので大量にダウンロードがあるとたいへんなことになる。
  • μTorrent for USBを買った人だけに配信するなどということも考えている。