Chocolat使い始めた

金曜くらいから色々と環境をいじり始めて止まらなくなり、ついにエディタ周りをこれまでのemacsからChocolatに置き換えるにまで至った。emacsに特に不満はなかった(とはいえ時々undoできなくなるのには困ったけど)のだけれども、最近はGUIエディタも機能が充実してていいみたいなのでお試しで使ってみている。この記事もChocolatで書いているけどMarkdownのリアルタイムプレビューができるしすごい便利。このへんはGUIエディタの大きなメリット。

GUIエディタを使うにあたって個人的にネックだったのがサーバ上のファイルの編集で、これができないとどうにもならないので躊躇していた。調べてみるとsshfsを使ってローカルにマウントしてやると簡単にできるようなのでちょっとツールの紹介。

ツールはMacFusionとExpanDriveなど色々というのがあるらしいけれど後者はシェアウェアでお試しなので躊躇。そこでMacFusionを使ってsshfs環境を整えてみた・・・んだけどとてもバギーで諦めた。sshの認証で何回やってもこけてしまう。

最終的にたどり着いたのはTransmit 4。ftpツールだけど4からExpanDriveのようにドライブとしてマウントする機能が実装されていて、速度もExpanDriveよりも速いようなのでこちらを選択。シェアウェアなので躊躇とか言ってたけど結局シェアウェアに・・・。トライアル期間で乗り換える踏ん切りがついたら買おうかな。App Storeにもあります。ライセンス的にはこっちの方がお得な気がする(複数台で運用する場合本家から買うと台数分ライセンスを買わないといけない)。

しばらく使ってみてなにか思うところがあればまたpostします。

Hadoop Conference Japan 2011 Fall に参加してきました

月曜日の話ですが、ベルサール汐留で開催されたHadoop Conference Japan 2011 Fallに参加してきました。

そもそもHadoopを使い始めたのが最近で、カンファレンスの参加は初めてなのですが、コミッターの方や大規模に運用されている方の話が聞けて大変参考になりました。

当日は速攻でMacbook Airの電池が切れてしまったため手書きだったのでメモが大変でした…。

Keynote

"The role of the Distribution in the Apache Hadoop Ecosystem" by Todd Lipcon, Cloudera Inc

Hadoop Distributionの一つであるCDHに関する説明。
何故Distributionを使うのか？→バージョン管理、インストールを簡単にできる

エンタープライズ向けのSCM Expressはサポートと管理用GUIツールが充実している。50ノードまでは無料。

"About Hortonworks" by Owen O'Malley, HortonWorks

Yahoo IncのHadoop部門が2011年7月に独立してできた会社。
HadoopへのContributionはYahoo Incと同じくらい。

検索の運用ではScience用クラスタとProduction用クラスタを分離して運用している。

  • 質問
    • Yahooで4000台のクラスタをどのように管理していたか？ → ほとんど手で運用。環境構築などにスクリプトを使ったりはしていた。ノードを管理するツールを将来Apacheプロジェクトでリリースする予定。
"How Hadoop needs to evolve and integrate into the enterprise" by Ted Dunning, MapR Technology Inc

  • Web企業やスタートアップ企業と大企業とでHadoopの採用率が違うのはなぜか？
    • スタートアップ企業などは生き残るために新しい技術を導入していく必要がある
    • スタートアップの初期の設備と成長してからの設備は変わりすぎるので互換性が必要ない→導入しやすい
    • 大企業などで既に導入されているRDBMSやNASとHDFS間のファイルのやり取りのコストが大きい→導入しにくい
    • MapRは分散ファイルシステムを実装しなおしたもので、RDBMSやNASをサポートしているのでこのコストを低減できる

Lunch Time LT

"MapReduceをコーディングなしで？新しいデータ探索ツール BigSheets" by 土屋 敦, IBM

IBM製のツールの紹介。
表計算ソフトのようにHDFS上のデータを処理できる。
グラフなどのVisualizationもプラグイン(js)で簡単に実装できる。
コーディングがないのでビジネスの人も簡単に使える。

"Hadoopログを全員で使う方法と課題" by 宵 勇樹, DeNA

モバゲーにおけるHadoopの利用事例の紹介。

HadoopのWebGUI(GitHubで公開中)のHUEを使ってマイニングエンジニア以外でもセキュアにデータを見れるような環境構築。
HUEによってPigやHiveを権限付きで実行できるようにしている。
グループ管理でユーザの追加などにNameNodeの再起動が必要だが、LDAPで管理することで回避している。

"Hadoop+HBaseを基盤としたPaaSプラットフォームの構築" by 岡本 晴芳

HadoopとHBaseを使ったPaaSプラットフォームの開発基盤の構築の紹介。
Hadoop, HBase, ZooKeeper, Mahout, JMX, JDOなどを使う。

"パネルログ分析" by 小林 隆

Hadoopを使ったパネルログ(ユーザの行動ログ)の紹介。
ユーザの行動ログを使うので、サイトの時系列分析・リピート分析・サイト間の分析を行うことができる。

Technical Track

"Apache HBase: an Introduction" by Todd Lipcon, Cloudera Inc

HBaseのアーキテクチャ紹介と他のファイルシステムとの比較。
途中から入室したので後半しか聞けていません。

  • HBaseにアクセスするための方法
  • HBase vs HDFS
    • ランダムRead/WriteはHBaseが速い。しかし、扱えるデータ量が少ない(〜1PB, 〜1000node)等デメリットがある。
    • ランダムRead/Writeしない限りはHDFSのほうが良い。
  • HBase vs RDBMS
    • HBaseはColumn-family
    • RDBMSはRow-oriented
"Architectural details and implications of MapR technology" Ted Dunning, MapR Technology Inc

MapReduceのボトルネック

  • Read only file
  • Many copies in I/O path
  • Shuffle based on HTTP
  • Spills go to local file space

MapRはファイルシステムとMapReduceを再実装してパフォーマンスを向上させた

  • Hadoopよりも倍以上のRead/Writeのパフォーマンス
  • 小容量で大量のファイルの処理でパフォーマンスが向上
  • Random ReadのパフォーマンスはHBaseの倍
  • NameNodeの冗長化
"NTTデータ流 Hadoop活用のすすめ 〜インフラ構築・運用の勘所〜" by 猿田 浩輔, NTTデータ

Hadoopインフラ構築・運用のベストプラクティスの紹介。

  • マスタノードの可用性向上
    • スレーブは冗長だがマスタには改善の余地あり
    • MapReduce → JobTrackerが停止するとアウト
    • HDFS → NameNodeが停止するとアウト
    • MapReduce → ZooKeeper、HDFS → AvatarNode, BackupNodeなど


しかし、実際にはHadoopの可用性だけではなくシステム全体としての可用性を考慮しないといけないので実績のある技術を駆使したほうが良い場合も

  • 数千台規模のクラスタ運用
    • 初期設定・設定変更・増設のコスト、障害時のコスト → オペレーションのパターンを最小限に
    • OSの自動インストール、一貫した設定による構成管理 → 共通的な方法で簡潔に
  • 例 :
    • PXEブート+kickstartでボタンひとつでOSインストール(CentOS)
    • Puppetで複数サーバに一貫した設定
    • 機器交換に伴うヘテロな構成も考慮 → 100台のサーバを90分で構築・設定変更は3分
  • ある程度の割り切りは必要
    • OSが入らないときは代替機
    • あらかじめ許容出来る縮退率を把握して機器交換のタイミングの計画をする
  • クラスタリソース情報の取得
    • Gangliaによるリソース情報の可視化
  • トポロジ設計
    • エッジスイッチごとにラックアウェアネスを設計すると電源ごとにデータが分散されるとは限らない
  • まとめ
"Hadoop 0.23 and MapReduce v2" by Owen O'Malley, HortonWorks
  • HDFS federation
    • namenode scaling
    • split namespace between namenodes
    • all datanodes are shared between all namenodes
  • JobTrackerを2つのコンポーネントに
    • Cluster resource management
    • Application life-cycle managements

SPOFの解消やスケールの向上(6000-10000台のマシン)
Wire Compatibilityの解消
MapReduce以外のparadigmsのサポート

Community Track

"リクルート式Hadoopの使い方" by 石川 信行, リクルート

リクルートにおけるHadoop利用事例の紹介。

Sqoop+Hiveで集計
Mahoutで分析
BIツール

  • Hadoopの真価
    • 高速に処理できるのでTry and Errorを繰り返せる
    • 全データを使えるのでサンプリングに頼らなくても良い
  • MapRとCDHの比較
    • MapRは約2倍速い
"ミクシィにおけるhadoopの利用" by 伊藤 敬彦, ミクシィ

ミクシィにおけるHadoopの利用

  • ログデータ : 保存サーバからHDFSへ日ごとにコピー

LSHを利用した推薦システム

  • 推薦 → 類似インスタンス(文書・ユーザなど)集合の抽出
  • 類似インスタンスの特徴の抽出(例: ユーザの商品購買履歴)
  • LSHｈで高速に抽出

LSH

実験

  • mixiのニュース記事で実験
  • 速度: 1週間分で30分弱
  • 精度: イマイチ
  • ユーザはカテゴリを横断して記事を見るのでカテゴリが精度を下げているのでは
  • カテゴリ毎に分割してLSHを適用

おわりに

  • Oluolu: スペル訂正の辞書抽出
  • Anuenue: Solrのラッパー

ACL2011論文読み会で発表してきました

昨日開かれたACL2011論文読み会で発表してきました。参加された皆様お疲れ様でした。

発表した論文は「 A Graph Approach to Spelling Correction in Domain-Centric Search」です。

2011/09/03 ACL論文読み会

論文の概要は、メール検索やデスクトップ検索のようなクエリログの少ない検索におけるスペル訂正で、クエリログを使わずにメールの本文などをコーパスとしたデータから学習していこうという内容です。スペル訂正にグラフベースのアルゴリズムを使った！と主張しているのですが、id:mamorukさんもつっこまれているように、グラフベースというよりは形態素解析に使うようなラティスを組んでやったという感じです。

所感としては、グラフベースと言うにはアレですがスペル誤りにおけるmergeやsplitを同時に扱えて形態素解析やかな漢字変換の手法を使って改良していけそうに感じました。

他の方の発表についてはid:nokunoさんの記事をご覧ください。

今回参加して自分の勉強不足を強く感じました・・・。
機械学習や数式周りが半分くらいしかついていけず、基本的な勉強が足りない気がするのでその辺を重点的にしばらく勉強していこうと思います。

最速と最遅のソートアルゴリズム

前回はMBAくれとかクソみたいなエントリ書いてますね。ちなみに木曜日は僕の誕生日なのでMBAくれてもいいですよ。

ソートアルゴリズムについて調べて同僚と話していたらクソみたいなソートアルゴリズムについて知ることができたのでまとめてみます。

最速のLucky Sort

オーダーはなんとO(0)！素晴らしいですね。
気持ちとしては、ソート出来てるものが来ればソートしなくてもいいんだし最速じゃね？

擬似コードは以下の通り。

vector<int> LuckySort(vector<int> a) { return a; }

うーん、実にひどい。天和で上がった気分でしょうか。

最遅のBogo Sort

オーダーはなんとO(n*n!)！どれだけかかるのか見当もつきませんね。
毎回の繰り返しでソートされてるのを祈り続けるアルゴリズム。スピリチュアルソート。

擬似コードは以下の通り。

vector<int> BogoSort(vector<int> a) {
  while(std::is_sorted(a.begin(), a.end()) {
    std::random_suffle(a.begin(), a.end());
  }
  return a;
}

うーん、実にひどい。延々と天和になるまで待ち続ける。

Bogo Sortは可視化したものをjsdo.itで発見しました。-id:cou929_laがグラフで可視化してカオスになるやつを教えてくれたんですが失念しました。

http://jsdo.it/norahiko/oxIy

ええっと・・・

クソみたいなソートアルゴリズムでしたが面白かったのでまとめてみました。今回色々調べてみて知らないアルゴリズムがたくさんあったので面白かったです。真面目に調べたのもあるので、割と当たり前な内容なんですがいずれまとめてみようと思います。

参考URL

http://en.wikipedia.org/wiki/Luckysort
http://en.wikipedia.org/wiki/Bogosort