ついでに Sawzall も勉強中

http://labs.google.com/papers/sawzall.html

これは予定外だけど、スクリプト言語らしいので一応読んでみる。

メモ：

• 型のある script language ... お、いいね。そういうの、好き。
• ex. input の sum:
  
• total: table sum of int;
• x: float = input;
  
• emit total <- x;
• domain specific language ですかね。
• 　今朝こんな言語作ってみたんだけどどうかな、、、なんてやってんだろうね。楽しそう。
• GFS
  
• MapReduce　... execution model
• Sawzall runs in the map phase. ↓これ
  
• map(in_key, in_value) -> list(out_key, intermediate_value)
• 　The aggregators run in the reduce phase. ... emit してるやつ
•  at the statement level Sawzall is a fairly ordinary language
• それほどでも
  
• 統計っぽい香りのする The Aggregators
• Collection ... Ruby の collect{|x| x}
• Sample ... 無作為抽出
• Sum, Maximum ... [].sum, [].max
• Quantile ... これは統計っぽいな。R (S-plus) みたい
• Top, Uniq etc.
• 無駄なトラフィックが出ないように最適化します！！
• Sum だったら subtotal でいいよね。とか。
• いや最適というか、Sum のインプリがそうなっているってだけか。
• indexed aggregator
• out_key もうまく使いましょ。
• saw の起動
• プログラム, queue, 入力ファイル指定、出力ファイル？指定。至極ストレートな感じ。
• /gfs/cluster1/... だって。　/gfs/で普通の Linux file system と区別してる？
• reduce phase の worker 数指定もできる。
  
• Implement
• Chaining ... お、、とおもったら、ちょっと薄いな。
• Domain-specific Property
• def ... nil?
• Quantifier ... まあそうね。ruby と　R　を比較対象にしてるもんで、さほど感動はない。
• Performance
• script にしてはがんばってるな。こんだけ強い型付きでだったら C++ とかと比べても良さそうだ。え、10倍遅い。まあ、、、いいか。　C＋＋へのconverter とか簡単そうだけど。まあ、ボトルネックは script じゃあないってことだな。

感想：

• まあ、DSL の例ですかね。
• 特に何かを期待していた訳ではないけど、、、、まあ、型があるのはいいね。
  
• このへんは人（プログラマ）との接点（インタフェース）なわけで。機能性能が全てって訳ではないわな。
• GFS とか BigTable に限らず、分散DBを扱うってのはこういう感じなんですかね、、。
• DBって殆ど使ったことないんだよな、、、、。ちょっとは勉強するかな。

MapReduce 勉強中

http://labs.google.com/papers/mapreduce.html

Wikipedia はスルー。ちょっと疲れたのでスライドで。

概要：

• map(in_key, in_value) -> list(out_key, intermediate_value)
• 中間ファイルは (worker, out_key) 毎に別ファイルぽい。(out_key)毎の中間ファイルにしてatomic append なんてことをすると fault tolerance が崩れるかな？
  
• reduce(out_key, list(intermediate_value)) ->list(out_value)
  
•  out_key のファイルを読んで、実行するだけ。

• Fault tolerance
• worker failure ... detect via heartbeat. re-execute
• まあ、map も reduce もやり直せばよし。
  
• master failure ... あまりない
• Slow workers のせいで遅くなったりする。
• Weird things: processor caches disabled (!!) だって ;-)
• バックアップタスクを起動する。(Near end of phase)
• GFS chunks の replica のあるマシン(または同じラック)上で処理するようにスケジュール
• 64MB にあうように map する。データ構造をあわせておく必要ありかな。
• BigTable ならその辺は考慮済みか。
• Bad recoreds
• SEGV signal handler から　UDP で master に通知
• 3rd party libでもOK
• 1800 Machines
• 4GB mem, Dual 2GHz Xeons with Hyper-threading @ 2004
• Dual 160GB IDE
• GbE, Bisection bandwidth approx. 100Gbps
• Result
• start overhead
• 1800 machines read 1TB data at 31TB @ peak.
• Experience
• 故障とか遅いマシンの面倒を見てくれる！
• simple な code. MapReduce の組み合わせ。
• Fun to use!!
  

メモ：

• shuffle ... read する順をかえてるってだけかな。
  

感想：

• BigTable の論文を読むと、BigTable 用みたいなイメージがあったが、BigTableなしでもOK。chunk へのデータのアラインとか考えると、直接GFSをさわるのは面倒そうではある。
• GFS とセットでの運用で真価を発揮。まあこの辺は勉強するまでもないか。
• 結局肝は、故障とかトラブルを隠蔽できるところにあるのかな。
• Fun to use!!
• まあ、サーバーセンターが一つのマシンに見たてたくなる気分が少しわかる、、、かな。
  

BigTable 勉強中

これはWikiがあった。http://ja.wikipedia.org/wiki/BigTable

• 列指向DBMS
• 大きいデータは圧縮される。
• Google File System を使用
  
• Chubby Lock System ...？
• MapReduce,  Google Earth, 等などいくつものGoogle Applicationで使われている。
• （MapReduce はDBのメンテに使ったりとかぽい）
• "Googleが自社のデータベースを開発する理由はコスト、スケーラビリティ、パフォーマンス特性のより良いコントロールなどである"　そうな。
• 各テーブルは多次元。フィールドはその時点のスナップショットを持つ。バージョニング可能。
• 構造は map: (key:string, column:string, timespamp:int64t) -> string.  バージョニングやGC機能あり。
  

メモ：

• Single Master Server タイプだが、クライアントライブラリがうまくキャッシュを用いることで性能低下を防いでいる。
• BigTable でも、クライアント用のライブラリをあわせて設計(Co-design)しているようだ。
• "Co-design Application and File System API" (GFS)
  
• エラー忘却型コンピューティング (ja.wikipedia.org)
• GFS, BigTable, MapReduce はこの概念を適用しているという。
• GFS の例だと、concurrent write とか atomic append に相当するかな。
• 性能を出すために、完全な consistency を持つ土台だけの提供をあきらめ、アプリケーション側で対策する設計になっている。checkpoint をもうけて問題をチェックする機構など。
• トータルコスト、性能、課題を解決するシンプルな設計、など。もはや旧来の美学は遺物であるのか。
• "re-examined traditional choices!"
• 　Google はエラー忘却というか、うまく飼いならしてる気がするけどね。
  
• 列指向DBMS (ja.wikipedia.org)
  
• 列に含まれるデータの型は一致する。ある行全体の取得とかは遅い。
• 大量のデータをゴッソリ処理するには向いてそうだ。

感想：

• まあ、何となくわかったが、使われ方を理解する必要あり。
• 「万能な土台」よりも「simpleだが高性能な土台」を目指しているっぽい。
• 現実の問題を解決するための、コスト最適解なのだろう。
• infinite information と言うことばをドコゾで読んだが、「現実の問題」とは infinite information をうまく扱うことだろう。もしくは世界征服か

あ、これも論文あるのか　( bigtable-odsi06.pdf ) ...
Introduction:

• distributed storage system for managing structured data.
• Bigtable does not support a full relational data model
• simple data model, that supports dynamic control over data layout and format, and allows clients to reason about the locality ... in the underlying storage!!!
• Data is indexed using row and column names that can be arbitarary strings.
• treat data as uninterpreted strings.
• Bigtable schema parameters let clients dynamically control whether to serve data out of memory or from disk!!!

Data Model:

• A Bigtable is a sparse, distributed, persistent multi-dimensional sorted map.
• map: (row:string, column:string , timestamp:int64) --> string
• We settled ... after examining a variety of potential uses of a Bigtable-like system!!
• i.e. Webtable
• Rows: 10-100bytes, upto 64KB. atomic!!
• Each row range called a tablet. reads of short row range is efficient. lexicographic order.
• ex. com.google.maps/* のほうが maps.google.com/*　より近傍にまとまってよかったりとか。

Column Families:

• basic unit of access control. read/write/? for different types of apps.
  
• same type.
  
• compress data in the same column family.
• column key は column family に含まれる。 column family は少なくしたい。in the hundreds at most. rarely change.
• In contrast, ... unbounded number of columns!!
• column key syntax:  family:qualifier

Timestamps:

• realtime in microseconds by Bigtable , or explicitly assigned by client.
• collision control (uniq. id is needed)
• GC: the last N versions, new-enough versions etc.

API:

• allows cells to be used as integer counters
• supports the execution of client-supplied scripts!!! in the address spaces of the servers. ... written in Sawzall [28]
• can be used with MapReduce, a framework for running large-scale parallel computations developed at Google.
  

Building blocks:

• GFS
• SSTable file format privides persistent, ordered immutable map from keys to values.
• distributed lock service called Chubby[8]
• これも client がちょっとかしこいっぽい。unavailability was 0.0047%、って、、。

Implementation:

• client library, one master server, many tablet servers.
• Tablet Location
• B+-tree
• Tablet Assignment, Tablet serving, Compactions
  

Refinements:

• locality group
• compression
• Caching for read performance.
  
• Bloom filter
• Commit-log impl.
• 対故障性か、、
• Speeding up tablet recovery
• Exploiting immutability
• effective concurrency control!!

Performance Evaluation
Real Applications
Lessons:

• vulnerable to many types of filures.
• memory and network corruption, large clock skew, hung machines, extended and asymmetric network partitions, bugs in other systems that we are using, overflow of GFS quotas, planned and unplanned HW maintenance.
• check sum for RPC
• stopped assuming a given Chubby operation could return only one of a fixed set of errors.
• it is important to delay adding new features until it is clear how the new features will be used. 必要な機能を見極められる。
  
• importance of proper system-level monitoring (Bigtable itself, as well as the clients)
• simple designs
• 枯れてない機能使った複雑なアルゴリズムを捨てて、シンプルに。何をデバッグしてるかわからなくなる。

Related Work:

感想：

• 良くできてるなー。いや、良くできてるというより、大変そうというか、寿命が縮みそう。
• ここでもやはり故障との戦いというか共生？。メンテナンスのコストまでふくめ鍛えられている。
• Application と DB 両方やってるからこそできる Co-design
• MapReduce が BigTable の裏方として使われてるのね、、、
• 何となく使い方も見えてきた。
• GFS にキャッシュがないのもここまでくれば納得できる。メモリに乗せるか乗せないかというのは、アプリケーションの性能を大きく左右するところで、アプリケー ションのデザインによってうまくコントロールできないといけない。BigTable はそのシンプルでreasonableな挙動によって、そういう controllability を獲得しているのだ。
• メモってないけど、Real Aplication とか、なかなか面白い。
• 「大規模なデータセンタを効率よく運用できれば云々、、、」なんて話が馬鹿げて聞こえるな。
• 大企業はデータセンタを自前で持った方がいいなんて話も見かけるがどうだろう。グローバルなデータセンタの成長（と低コスト化）に対し、 ローカルなデータセンタのメリットによるオフセットと成長曲線の関係を考えると確かに可能性はあるかもしれない。少なくとも管理のアウトソースや鍛えられ たSWの導入は必要な気がするな。どっちがお特とか定性的な話じゃなくて、実際にいくらかかってるか定量的にみないと、技術や運用のレベルによるコストの差がえら い大きそうな気がするよ。まだまだよくわからん。要勉強かな、、、。
• あと、Wiki だけだと誤解があった。論文スルーしないでよかった。 
• あと、講演のvideoもあった、、、。 特に新しい情報はなさげ。
  

Google File System 勉強中

Google Wave, App Engine, MapReduce などなど、凄く面白そうではあるが、どうもよくわかった気がしないので自分なりにまとめようと思う。

まずは、、、

SOSP'03 "The Google File System", gfs-sosp2003.pdf

Google File System II ( http://www.publickey.jp/blog/09/google_file_system.html ) なんて話もあるらしいですが、まずは Google File Syetem について。論文を客観的にまとめてから、主観を書こうと思ったが、既に良いメモがあるので客観的まとめは省略

• http://dev.ariel-networks.com/column/tech/google_file_system

まとめ（主観まじりですので注意）：

• 概要
  
• 安いPCで分散ファイルシステム
• 例： 1000+の strage node, 300+TBの disk, 数百の client
  
• 想定
• failure are the norm rather than the exception.
• ファイルは大きい
• 現実のアクセスパターン
  
• Co-design Application and File System API.
• 特殊なAPIを作ってでも、現実的な課題を解決する。
• アプリケーションもうまくGFSを使わないといけない。
  
• アーキテクチャ
• 構成
• single master server, multiple chunkservers and multiple clients
  
• single master server
  
• メタデータの保持. メモリ上におくのがポイント
• 故障対策をいろいろがんばっている
• single なのは simple にするため。single の欠点には触れてないっぽい
  
• chunk (fixed size, 64MB)
• chunk が大きいほどメタデータを小さくできる。
• chunk が大きいと、ファイルが小さ場合に分散されないのがデメリット。
• でもだいたいファイルは大きいからいいよ！
• 分散実行しようとしたバッチファイルに負荷が集中しちゃった！
• chunk毎に処理するバッチ. 
• いっぱいファイルをreplicateして、時間をずらして解決
• API
  
• POSIXなどでないが、一般的な操作はできる。
• client が libGFS をリンクすると、ごっそりGFSをアクセスするようになったりするのでは？　知らんけど。
• cache
• client cache は効かないのでない。coherence 問題から解放される。
• メタデータは client でキャッシュする
• chunkserver は Linux 君が良きにキャッシュしてくれる。　Linux のファイルシステムの上に乗っかるのでこの辺は枯れた技術が使える。
• metadata
• これを小さくするのが大事！ master server でも client cache でも効く
• 64B for 64MB chunk
• 100TB chunk だと 100MB　のmetadata になりますな。
• 64GB memory だと 64PB ぐらいいけますかな。
• 64-B for namespace data for file
• ファイルのパスの圧縮も大事
• logging とか　chunk location の管理
• サーバ故障、chunkserver 故障などの対策は重要。
• 多少のダウン時間は許容する設計になっている。まあそういう用途向けってことか。
  

Section 3,4,5 はさほど興味ないので斜め読みした。情報を取りこぼしてる可能性あり。

感想：

• 重要そうなデザインに関する選択について
• chunk size = 64MB に関して
• メタデータを小さくオンメモりにするために大きく設定されている。
• デメリットもあるので、性能が低下しない範囲で小さくしたいところではある。
• お安い感じで、4GB を chunk 用 metadata に使えるとすると
• 4GB chunk-metadata = 4PB
• レプリケーションを４とすると 1PB ぐらいまでは余裕ですかね。
• 2桁PBぐらいで満足する人たちとは思えないが。
  
• single master server
• 故障時等のリカバリにかかる時間は結構長そうだ。この辺は今となっては課題だろうな。少なくともダウンタイムをほぼ０にしたいだろう。
• リクエストをさばくのが１台だけというのも問題になりえるか。
  
• chunkserver あたりのディスクが増えると、、、
• ディスク容量あたりのCPUパワー、メモリが減ることになる。
• Atom + 4G mem + 1TB SSD みたいな構成でいいのか？
• 全体として故障の影響が小さくなるような構成にして、現実や近未来のアプリケーションにあわせてCPUやメモリを積むんだろうね。まあ、どういう故障が起こるかの統計を持ってない以上、深読みに意味はないか

調べる前に気になっていた点：

• 今でも現役？
• まだ行けそうだが、そろそろつらいかもね。
  
• コスト比較
• まあ、NetApp と比較してもしょうがないか、という気がしてきた。
  
• MapReduce とかとの関係は？
• MapReduce はともかく、m-producer-1-consumer パターンを対象のワークロードとして作ってある。m-producer-1-consumer パターンと MapReduce の関係は、、、MapReduce ももうちょっと勉強するか。
  
• その手のフレームワーク？を使わない場合は、結構うまく使うのは大変に思える。ちょっとこの辺は要勉強だな。MapReduceの適用範囲とか、その他のフレームワークの可能性とか、逆に cloud application から求められる機能とか。BigTableとか。
  
• 一般人には必要ないもの？適用領域は？
• まあ、直接GFS　APIをたたくことはないだろうな。
• Open source になったところで、お家に置こうとは思えない。おうち用の分散ファイルシステムはもっと別の物だろう。その手のプロジェクトがきっとあるはず
• USB HDD をいっぱい刺せるとか、複数のNASをまとめて一つに見せるとか、そんなの。でもまだ先かな。Time Capsule ぐらいが現実解なのかも。
  
• データベースとの関係は？
• むー、まあ、使われ方をもうちょっと理解する必要があるな。super MySQL の土台に best match とは思えない。BigTable？
  

うーん、感想とか考察が幼稚だな。ま、もっと勉強を進めないとダメだな。まだよくわかってません。これが2003年だもんなー。今更論文読んでる自分が恥ずかしい、、。

Wavelet and short-time Fourier transform.

Continuous Wavelet transform with R:

折角なんだからMATLAB 使えよって気もするけど、入手しやすいRで。

R での Wavelet Transform に関する情報は Google 先生に聞いてもよくわからなかったので、ちょっと簡単な例をためしてみる。(legendにバグあり)

require('Rwave')

fps = 15
nframes = 512
t = (1:nframes)/fps
seq01 = (1:nframes)/nframes

f = 1.0*sin(2*pi*t) + 0.1*rnorm(nframes) + 0.8*sin((0.6+seq01*0.8)*2*pi*t)
ts_f = ts(f, deltat=1/fps)

plot(ts_f, type='l')
spectrum(ts_f)

#freqwave(ts_f, NA, 8, color.palette=heat.colors)

a = cwt(ts_f, noctave=8, nvoice=48, plot=FALSE)
filled.contour(Mod(a), color.palette=terrain.colors, nlovels=32)

a = cgt(ts_f, nvoice=256, scale=64, plot=FALSE)
filled.contour(Mod(a), color.palette=terrain.colors, nlevels=32)

matplot(cbind(Re(gabor(512, 256, frequency=2/15, 64)), 0.004*cos(2*pi*t)), type='l')
legend(0, 0.006, col=c(1, 2), lty=c(1, 2), legend=c("gabor", "cos 15Hz"))

まずは適当に信号(ts_f)を作成。
plot してみる。

spectrum してみる。これは多分、中身はfftだと思う。調べてない。

cwt してみる ... これは　'Rwave' ライブラリの関数だ。'wavelets' は dwt, 'Rwave' は cwt とかぽい。

Short-time Fourier transform with R:

時 間窓に Gauss 窓を使った Gabor 変換だ。ちょっと用語には自信なし。Wavelet 変換としての Gabor と Short-time Fourier transform としての Gabor って使い分けかたがあるのかね。まあどっちでも良いが、ここでは STFT だ。

cgt がそれ、のはず。なんか自信なくなってきた、、、。

周波数 1HZ (0.133)と、周波数が徐々にあがっていく信号が見える。えらいお気楽だな。
大学の授業では　DWT を C かなんかで書かされた記憶があるが。
ていうか、まず先に discrete じゃなくて continuous じゃなかろうか。聞いてなかっただけかな。

いまいち使い方に自信がない、ていうか、ドキュメントがなっていない。
ちなみに使われている Gabor は、こんな感じ(のはず)。@1Hz (0.133)

legend の 15Hz は間違えた。正しくは1Hzだ。1Hz, 15fps, 512 frame という設定のつもりだった。
今回は、一定周波数の信号、緩い周波数変化のある信号を見たかったので、時間窓をちょっと広めにとってみた。cwt より時間分解能が下がっているはずだが、まあ欲しい情報にあわせてできるだけ広くとるのが個人的には好みだ。

感想：
cwt は非常にお気楽、設定項目が少ない。Morlet が自動的に使われる。変更はできなっぽい。今回の例は簡単だからいいが、ノイズの多い信号の cwt を睨むのは結構大変そうだ。「うわーノイズだらけやな」とか感心する用途にはいいが、図から隠れた信号を見極めるのは職人芸ぽい。
一方 cgt はより図的には直感的。どういう信号があるはずで、どういうノイズが乗っているのかわかっていれば、自分で適当にいい感じの時間窓を選んであげれば、より直感的な図が得られると思った。

補足：
freqwave ... コメントアウトされてるのは google 先生に教えてもらった関数だから。ググるとちょっといい pdf が見れるかもしれない。
Emacs Speaks Statistics ... 良い感じです。
quartz (作図デバイス) ... 複数 png とかを出力しようとすると、絵が上書きされます。字とかAnti Alias とかきれいなのに。がっかり。ていうか、pdf が普通にGoogle Docs とかに貼れればいいんだけどな。

Blogger 試用中

Google Docs とか Gmail の IMAP + OS X Mail.app とか Evernote とか、いろいろ日々の記録を取るための環境を試行錯誤中です。自分メモは Google Docs に落ち着きつつあるが、Blogの使い心地も一応評価。

いろいろ調べていると、多くの情報は Wikipedia か Blog か News site から拾っていて、特に Blog は結構いい情報源になっているものだなと、今更ながらに思った。特に還元を目標としている訳ではないが、１０年近くぶりにちょっと書いてみようかと思う。主に評価なのですぐにやめるかも。継続できれば、後々見返すのは好きなんだけど、、、。

ちなみにここに書くかもしれない内容は多分、日々の生活的な物は無しで（かわいい写真とかは貼らない）、雑多なツールとかのメモっぽい物など。

以下、テスト：

H3

ああ、こうなるのか。

H4

H5

H6小さすぎだろ

本文

• Ctrl+8 とかしたくなる。

1. Ctrl+7 とかしたくなる。Google Docsのショートカットが使いたい。
   

本文

def codeblock
end

図を張ってみる。

 複数アップロードはやや便利か、Google Docs よりは。いや、普通に考えると使いにくいんですけど、、、。

Wavelet and short-time Fourier transform.

Continuous Wavelet transform with R:

MATLAB も使ってみた方がいいかな。

Google Docs からコピペしてみた。ていうか、普通に見えちゃうけど、いいんだっけ。 まあいいか。

うーん。まあ、H3, H4, block quote とかはテンプレート書けば良いかもね。（書いた）
絵のリンクがしょぼいな。&.png とか手で付け加えればあるいは。（面倒）