第
14
回の目次
前回: RDB, Memcached 今回: サーバー高性能化技術 ビッグデータ処理基盤 【参考書1:伊藤ほか: サーバ/インフラを支える技術,技術評論社】 【参考書2:西田ほか: Googleを支える技術,技術評論社】 【参考書3:ルイス・バロッソほか: Googleクラウドの核心，日経 BP】 1 / 28The 5 Stages of Scale (by. C. Smith)
1 Session partitioning (load balancer, multi-XX) 2 Read caching (reverse-proxy, memcached, CDN) 3 Get a real persistence framework
4 Real partitioning of IO
5 Route new data through data partitions 6 Cheat more on reliability
L1キャッシュ参照– 0.5 ns 分岐予測ミス– 5 ns L2キャッシュ参照– 7 ns ミューテックスのロック／アンロック– 25 ns メインメモリ参照– 100 ns 1KバイトのZip圧縮– 3,000 ns 1Gbpsネットワーク上の1Kバイト送信– 10,000 ns (0.01 ms) SSDから4Kのランダム読み込み– 150,000 ns (0.15 ms) メモリから1MBの順次読み込み– 250,000 ns (0.25 ms) 同一データセンタ内のラウンドトリップ時間– 500,000 ns (0.5 ms) SSDから1MBの順次読み込み– 1,000,000 ns (1 ms) ディスクシーク時間– 10,000,000 ns (10 ms) 2 / 28
サーバー高性能化技術
要求の分散化1: DNS, CDN (Contents Delivery Network)
要求の分散化2: load balancer サーバー高性能化: Scale Up (含memcached) サーバー大規模化: Scale Out DB高性能化: Scale Up DB大規模化: 分散DB (前回少し触れた) 3 / 28
17
サーバー側の構成
ディスクIOの待ち を利用して多重度 を上げる。プロセッ サ負荷は比較的 軽い。 （例：Amazon data warehouse） 検索エンジン 検索処理はサブタス クに分割しやすい。 多重化により性能を 上げる。 （例：Google） メインタスクの処 理量が多く、分 割も容易でない。 ハードウェアエン ジンなどもある （例：Netezza） wait wait CPU HDD データマイニング処理 ゲートウェイ トランザクション処理 パイプライン化 と並列化でス ループットを上 げる （例：CiRCUS） ロードバランサー Data is next “intel inside”18
現実のサーバー構成：
データセンター x 60箇所
DNSによる 負荷分散
Google Web server Spell checker
Ad server Document servers Index servers Hardware Load Balancer １つのデータセンター＝1万台程度のPCクラスター
80億ページの検索を支える仕組み
DC間は一貫性制御 はせずただのコピー + NetScaler Application Delivery (Citrix)Google File System
19
Google検索エンジンのプロトタイプ期のアーキテクチャ
URL Server CrawlerCrawler Store Server
Indexer
URL Resolver
Page Rank Searcher
SorterSorter Sorter Repository Anchor Links Doc Index Lexicon Barrels Crawler
20
Google File System
アプリケーション マスター ファイル名前空間管理 ファイル名 (+ chunk index) チャンクハンドラ コマンド発行 状態管理 チャンクデータ or エラー アクセス エラー処理は アプリの責任 ファイル名管理 チャンクのGC 故障管理 １つのチャンクは3箇所 にコピーされる 一番近くのチャンクか ら読み出す チャンクサーバー チャンクサーバー
ロバストかつ広帯域なデータアクセスを廉価PCで実現する仕組み
普通のLinux PC + 普通のHDD (80GB)チャンク ＝
64MB
21
Youtubeの構成（Google売却前）
Internet CDNs (Google他) Mini cluster Mini cluster Mini cluster The Most Popular Content “Long-tail” ContentCuong Do の”Youtube Scalability Talk”よりの想像図
Lighttpd NetScaler サーバー Lighttpd サーバー Lighttpd MySQL メタデータ MySQL MySQL MySQL thumbnail 生成サーバー生成サーバーthumbnailthumbnail 生成サーバー thumbnail ビデオ系 メタデータ系 サムネール系 →今はGoogle BigTable に移行 アプリは pythonで記述 レプリカや並 列読出の工夫
BigData
処理基盤
Big Dataはバズワード．ともあれ，なぜRDBじゃ駄目なのか? 元々はWebの解析(Indexer) とにかく大きい(PBクラス) 不定型(スキーマが作れない) ACID特性は必ずしも必要でない 応用例: マーケティング情報(POS等)→データマイニング システムログ情報 センサー情報→ストリームDB 位置情報→例:ドコモ モバイル空間統計 システム例:バッチ系: Hadoop，Google MapReduce
ストリーム系:Oracle Complex Event Processing, NEC CONNEXIVE, ...
Hadoop
の概要
HDFS (Hadoop Distributed File System) MapReduce処理 Scale Outが容易 ノードは落ちて当たり前(SPoFあり) バッチ型(リアルタイム，ストリームは苦手) RDB的な処理も可能(HBase/Hive) 同期処理(一貫性保証)は別システム(ZooKeeper) 10 / 28
HDFS (Hadoop Distributed File System)
UNIX風階層ファイルシステム 巨大ブロック(64MB)単位 3重コピー ラックを意識(Rack Awareness) ベースのLinuxの上にアプリ層(Java)で実装 11 / 28MapReduce処理の概要
Map Map Map Map Reduce Reduce Data Data HDFS <key, value> HDFS keyごとにまとめる <key, 結果> 12 / 28入力と出力
Map入力 基本的には1スプリットは1ブロック．最寄りのものを利用． TextInputFormat キーはスプリット内オフセット SequenceFileInputFormat バイナリの入力(同期点で分割可能) スプリットをレコードに分解してMapに入力 レコード境界とスプリットのずれをあわせる 圧縮されていれば戻す(レコード圧縮とブロック圧縮) Reduce出力 reducer一つごとに一つのファイルを出力 →partなんとかという名前になる reducerローカルに出力(HDFSが2つコピーを作る) MultipleOutputFormat: 各出力(KVペア)ごとにファイル名を決め られる． 13 / 28shuffleとsortの詳細
入 力
White: Hadoop, Oreillyより引用
map Map Task
spill file
map output file
reduce 出力 partition, sort, combine copy Reduce Task combine, merge sort merge sort memory buffer メモリ上 ディスク上 14 / 28
MapReduce
で転置インデックスを作る
map (各ページ毎): 入力: 1つのページ 処理: ワードの数を数える 出力: <ワード, ワード出現数, URL> reduce (各ワード毎): 入力: <ワード出現数, URL> 処理: <ワード出現数, URL> のペアをリストにする 出現数でリストをsort (実際はセカンダリソート) 出力: <ワード, sortしたリスト> 15 / 28プログラム例
public static class Map extends Mapper<LongWritable, Text, Text, IntWritable>{ final static IntWritable iw_one = new IntWritable(1);
public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
String line = value.toString(); String[] words = line.split(" "); for(int i=0; i<words.length; i++)
context.write(new Text(words[i]), iw_one); }
}
public static class Reduce extends Reducer<Text,IntWritable,Text,IntWritable>{ public void reduce(Text key, Iterable<IntWritable> values,
Context context)
throws IOException, InterruptedException { int sum = 0;
for (IntWritable value : values) sum = sum + value.get();
context.write(key, new IntWritable(sum)); }
}
Hadoop
関連のその他の
BigData
技術
Hbase カラム指向データベース RDBっぽいことをしたい時(Joinはない) Javaから使う Hive SQL風言語(Hadoopへコンパイル) Pig RDB処理をスクリプトで書ける(Hadoopへコンパイル) Dremel (Hadoop上ではない) カラム指向データベース ネストしたカラムも扱える ─ Mahout 機械学習ライブラリ 17 / 28分散処理記述
分散システムの制御は別に必要 Hadoopは非同期のバッチシステム 全map終了後にreduceが開始されるという同期しかない ZooKeeper, Paxos 18 / 28運用
実際に大変なのは運用 落ちる 壊れる 偏る(ボトルネック) 頻繁な拡張The Datacenter as a Computer (Googleクラウドの核心)によると DIMM:サーバ1台あたり2.5時間に1回訂正可能エラー ECC→1台一年間で1.3%が訂正不可能エラー
HDD:一年間に障害で交換される2∼4%
別の調査でも32ケ月で3.5%
インターネットの今後
端末: PC，スマホ，タブレット,センサー?, IoT?
ブラウザ: Google, Apple, Mozilla, ?
標準規格: HTML, HTTP→HTML5, WhatWG, HTTP2.0
クラウド: 広域分散,メモリ化,データマイニング(機械学習)
ビジネス: 広告費以外のビジネスモデルは?
この授業で取り上げられなかったこと
プライバシー個人情報保護法,不正指令電磁的記録罪 最近のいろいろな事件
仮想化・クラウド
仮想マシン技術(Xen, KVM), Eucalyptus, OpenStack SDN, OpenFlow
プログラム言語・環境
Erlang, Haskel, JavaFX, Android, iPhone, Widget
大学院アンケートをお願いします(1/15∼1/28) 次回は発表会 発表時間5分(+質疑3∼5分) パワポをShareFoldersに前日までに提出 最終提出物の詳細は第11回資料を参照 締切りは1月28日一杯とする 21 / 28
以下は時間があれば
13
クラウドに至るコンピューティングの流れ
メインフレーム Web UI 無し ユーザのデータと それを扱うプログラム UI クラウド P2P クライアント・サーバ パソコン • 膨大な数の安価なPC （計算資源の有効活用 が目的ではない） • データはあちら側に • 広帯域通信とWeb（リッ チなUI）14
クラウドの分類
IaaS型 （Infrastructure as a Service） SaaS型 (Software as a Service) PaaS型 (Platform as a Service) 最終 利用者 サービス1 サービス2 サービス3 部品 部品 部品 サービスを 直接利用 アプリ アプリを実装 部品 プロバイダは 部品を提供 プロバイダはサービス そのものを提供 仮想マシン 仮想マシン 仮想マシン アプリ 部品を利用し てアプリ構築 アプリ アプリ 直接利用者 プロバイダは仮想マシ ンやストレージを提供インターネット広告
年 米国(1$=100円) 日本 2006 16879M$ (16879億円) 4826億円 2007 21206M$ (21206億円) 6003億円 2008 23448M$ (23448億円) 6983億円 2009 22661M$ (22661億円) 7069億円 2010 26041M$ (26041億円) 7747億円 2011 31735M$ (31735億円) 8062億円(IAB Internet Advertising Revenue Report,電通「日本の広告費」)
Googleは
2011のRevenues = 37905M$ (37905憶円)
内訳:
* Network Members’ Websites Revenues = 10386M$ * Google Websites Revenues = 26145M$
8
ビジネスの側面から見た
Web2.0
ロングテール部分 梅田「ウェブ進化論」を模式化 販売数 製品種別 1位：ハリーポッターと不死鳥の騎士団 2位：世界の中心で愛をさけぶ 3位：バカの壁 10mの首 5μの尻尾 年間７万点 従来のビジネスのターゲット9 9
ロングテール広告
Google Adwords Google Adsense バナー 広告の対 象となる 人数 広告の種類10
なぜロングテールビジネスが可能になったか
世界中（∞）の情報を0円で集める 光ファイバ インターネット ハイパーテキスト すべての情報（∞）を0円で処理 CPU，HDD 検索エンジン MapReduce, BigTable 価値化（∞ × 0 ＝ Value） AdWords，AdSense Wikipedia SNSAccess Front End Monetize Engine
•ロングテールビジネスはこれまでのビジネスと オーダーが違う（0と∞を扱うビジネス） •皮膚感覚で語るのは危険
