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

da1a9cc9.jpg057a5589.jpg

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プラットフォーム」をおく
  • イベント: 属性名=属性値
  • ルール: イベント条件 属性条件(属性名=属性値の組) と 配信先指定 配信先=サービス
  • 要件
    • スケーラビリティ: イベント数、ルール数、ルール変更数
    • 多種多様な属性の収容: 種類が増加してもスケーラビリティを維持
    • ルールの必要十分な記述: 包含指定も必要
  • キー空間でマシンわりふり
  • 従来技術の課題
スケーラビリティ 属性数 包含指定
chord N/A ×
mercury ×
  • - mercuryは属性ごとに空間が別になるのでスケールしない
  • 拡張局所性保存ハッシュ関数
    • 局所性保存ハッシュ関数 f (従来技術MAAN) a
    • 拡張局所性保存ハッシュ関数 F : F(x,a) <= F(y,b) iff (x
    • 属性名がおなじならf()の順序が保存される。ちがうなら属性名の辞書順に。
  • 実験: スループット(イベント/s)がO(n/log n)に一致した。nはサーバ台数。log nはホップ数。
    • ルール 属性条件1 イベント 属性数1
    • サーバ数32で遅延46.8ms スループット=248万イベント/s。
    • 100万イベント/sが目安 4000万人が利用したとして 1分ごとに位置情報を通知する というのを想定
  • N次元トーラス CAN スケーラビリティがちょっと劣ったような気が
  • 全ルールを全サーバにばらまくのと比べてどうか?
    • ルールの更新が一定頻度あるはずなので
  • 属性数がぐんぐん増えるのはどういうこと?
  • ルールの条件が長くなった場合: ながくなるとは想定していない
  • センサーが携帯だとすると1つのイベントにたくさんの属性がくっついてくる。
  • 静的な情報(年齢性別)は別あつかいに。
  • ストリーム処理
  • ルールから1つの属性を決めてキー空間を担当するサーバにばらまく。どの属性を選択するかは???
  • イベントは属性のハッシュ値にもとづいてサーバにばらまく。
  • なのでちょうど1台しか発火しない。
  • O(n/log n) ホップ数log nが効くのはネットワークI/Oがサチっているから。
  • b7be3cdf.jpg

    のりつなさん

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

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