読者です 読者をやめる 読者になる 読者になる

ひつじのにっき

mhidakaのにっきです。たまに長文、気が向いたとき更新。

【13-B-1】Programming the Cloud クラウドをプログラミングする

Googleの秘密が分かる50分。

について。

クラウドコンピューティング世代では処理の並列化もキー技術の一つ。
MapReduceアルゴリズムを例に並列化ソースコードの紹介など。


マルチコアの事前学習をしていたので、専門外ながらある程度ついて行けました。
やはり並列化が今後のコンピューティングの鍵になりそう。
その際、宣言型のプログラミング言語が重要そうです。Lispあたりから勉強してみよう!

13-B-1 Programming the Cloud / クラウドをプログラミングする
 Programming The Cloud the Internet as Platform

Google Engineering Senior Staff Engineer
Gregor Hohpe (グレゴー・ホーペ)

◆概要
 今日のポイント
 ・クラウドコンピューティングの一般的概念と課題
 ・Google社内での課題解決手法
 ・Google App Engineの紹介

◆クラウドコンピューティングがホットな3つの理由
 コスト低下
  ビックカメラで1TBハードディスクが1万円(日本語で“イチマンエン")
  廉価に高度な計算が可能に。=誰もが高速な演算能力を活用できる
 帯域幅の問題
  ブロードバンドが普及
 通信の高速化

 Google社にとっても(環境を)活用するためのツールが必要
 → 使いやすく安価であること、利用するための手法が必要

 トレンドとして
  クラウドコンピューティング二には目新しい内容はないが
  三つの要因が大きな流れとなって研究用途から一般的になった

◆クラウドコンピューティングの世界観
 アーキテクチャ:夢のようなアーキテクチャ(Architecture Dream)
  少し特徴をあげるだけでも分散化、演算力、標準化技術など
  ⇒ 〜bilityを持つ。拡張性、柔軟性、etc

  開発:開発は悪夢(Development's Nightmare)
  =夢のようなアーキテクチャと引き替えに開発が悪夢になってしまわないように。
  クラウドコンピューティングの開発では今までの手法が通じない
   メソッドの多重呼び出し(Call Stack Stackを呼ぶこと)
   トランザクション処理を行うに当たってのACID原則も崩れる
   
  ⇒ どれだけ分散できるかを追求
   トレードオフとしてスループットの確保などで制限
  
  ※ACID:以下Wikipediaより
  ACIDとは、Atomicity, Consistency, Isolation, Durabilityから合成された頭字語である。
  これ以上分解すると意味のないものとなる最小の処理単位という意味の
    原子性(Atomicity:アトミック性)、
    一貫性(Consistency)、
    独立性(Isolation)、
    永続性(Durability)
  は、トランザクション処理を行うにあたって不可欠な機能であると考えられている。
  もしACIDがなければデータベースの完全な状態は保証されない。
  
  
 クラウドはいままでの一貫性を持ち込めない世界★
 開発者として今までの想定事項、環境、Runtimeは通用しない

 従来型ACIDとのクラウドコンピューティングのACIDを比較

 従来:    Atomic      Consistent  Isolate    Durable
 クラウド:Associative Commutative Idempotant Distributed
 
 Associateve:数学用語 結合 (A+B)+C = A+B+C と同じ
 Commutative:数学用語 可換 柔軟性を確保できる
 Idempotend :数学用語 べき等 同一の演算を何度やっても結果が変化しない
  オペレーションがうまく行かないときはくりかえしを行う必要がある
  2回やったときも同じ結果を得られるようにしなければならない
 Distributed:Dがなかったので追加:-)

◆Google社の取り組み
 インフラを支える4つのシステム
 ・Google FileSystem
 ・Bigtablemapreduce
 ・sawzall
 
◆Google FileSystem(GFS):障害対応機能を内蔵
 いまのHDDは信頼性が高いが、HDDが5万枚、10万枚あった場合は障害は必ず発生する。
 その場合は、障害の有無ではなくて、「いつ」障害が起こるか、をかんがえる
 
 GFSの特徴
  クラスタサイズは64MB
  高速大域にフォーカス。
 シーケンシャルアクセスを最適化したのでランダムアクセスに不向き
  どこかで妥協点を見いだす必要がある
  クラス他は5PB以上を1クラス他とする

 GFSは低レベルのファイルシステムBigtable
 データベースとのアクセスは?
 Bigtable:リレーショナルデータベースと異なる。
 ソーティングされている、多面的なデータベース
  Sparse,Distributed,Persistend,Multidimensional,Sorted
  
 スキーマ、ジョイン、やクロステーブルなどを持ち合わせていない
 基礎に立ち返り基本的なストレージを大規模環境で提供
  
 今のリレーショナルデータベースはOSのように複雑だが
 BigTableはBigDataBaseではない。一つのテーブルである。
 
 データのセルあたりのストレージ使用量は数百TB以上★
   
◆MapReduceアルゴリズム
 分割統治。Map、ソート、Reduceの3ステップに分かれる

 Hadoopプロジェクト
  GoogleMapReduceアルゴリズムのクローン
  オープンソースプロジェクト
    
 疑似コード: Map、Reduceという2つの関数を用意
 テキストに対してマップを呼びだす
    map(in_key, line)
    words = split(line)
    for each word in words
      Output(word, 1) <= theがもし100回あれば100回この行に到達

    reduce(key values)
      print( key + ":" + Sum(values)) 

 事前に〜しておくこと、といった前提条件などはプラットフォーム側で処理
 呼び出すタイミングを考慮する必要はない
  上位レベルでの抽象化なので複数同時一考できる
  詳しくは http://wwww.research.google.com/mapreduce.html

◆Sawzall(ソウゾウ)
  ログの並列ログプロセッシング
  通常はGrepなどのマッチング結果を数え上げるときは
 
  通常、ループのなかで、加算が行われる
   while(line != EOF)
    word = sprit(line)
    if(match)
      map[match]++
   
  クラウドコンピューティングでの正解はこっち★
   map_table sum[String] of Int
   line=input
   words = sprit(line)
   for each word in words
     emit map[words]

   Emit:マップを出力する

 input - process - sum 
 上記3ステップのうちループ構造を持つのはprocessのみ。
 処理部分を並列化する
 
 マップテーブルのSumは可換であり、結合が可能
 オーダーの変更に強いプログラムに。

 トレードオフが存在
 Sawzallは並列化のために順序構造に依存した制約を諦めた
 (Lineそのものの重複を探すなど)
    ※Sawzallは1つのLineや個別のStateごとに機能する。

◆Google And The Could And You!
 クラウドをより使いやすく
 
◆Google Data API
 標準化技術を幅広く採用。ATOM等
  ※この場合のATOMはCPUではなくてXML Feedの標準化技術
  
 Google calendar APIのデモ
  スケジュールをXML Feed等で配信できる

 Google App Engine
  ソースコードGoogle上で走らせる仕組み
  データはGoogleのビッグテーブル上で管理
  
  拡張性を重要視しており、Web上でのユーザ認証のためのLoginなど
  一般的なことができる。
  無料で提供(1ヶ月あたり500万ページビューまで)

  OpenSocial向けWebアプリをAPIを使えば数時間でできる
  

 GoogleAPI群は毎月リリースされている
  SDKは先月に1.1.9をリリース

 クラウドコンピューティングは
  ・プログラミングの手法は大きく異なる★
  ・従来型のトランザクションではない、結合可能な世界