第 14回の目次

前回: RDB, Memcached今回:

サーバー高性能化技術ビッグデータ処理基盤

【参考書 1: 伊藤ほか: サーバ/インフラを支える技術,技術評論社】【参考書 2: 西田ほか: Googleを支える技術,技術評論社】【参考書 3: ルイス・バロッソほか: Googleクラウドの核心，日経BP】

1 / 28

The 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 framework4 Real partitioning of IO5 Route new data through data partitions6 Cheat more on reliability

L1キャッシュ参照 – 0.5 ns分岐予測ミス – 5 nsL2キャッシュ参照 – 7 nsミューテックスのロック／アンロック – 25 nsメインメモリ参照 – 100 ns1Kバイトの Zip圧縮 – 3,000 ns1Gbpsネットワーク上の 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

現実のサーバー構成：Googleデータセンター x 60箇所

DNSによる負荷分散

Google Web server Spell checker

Ad server

Document serversIndex servers

HardwareLoad Balancer

１つのデータセンター＝1万台程度のPCクラスター

80億ページの検索を支える仕組み

DC間は一貫性制御はせずただのコピー

+ NetScaler ApplicationDelivery (Citrix)

Google File System

http://research.google.com/pubs/papers.htmlの論文より

19

Google検索エンジンのプロトタイプ期のアーキテクチャ

URL Server CrawlerCrawler Store Server

IndexerURL Resolver

Page Rank Searcher

SorterSorterSorter

RepositoryAnchor

Links

DocIndex

LexiconBarrels

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” Content

Cuong Do の”Youtube Scalability Talk”よりの想像図

LighttpdNetScaler

サーバーLighttpd

サーバーLighttpd

MySQL

メタデータ

MySQLMySQLMySQL

thumbnail生成サーバー

thumbnail生成サーバーthumbnail生成サーバー

thumbnail

ビデオ系

メタデータ系サムネール系 →今はGoogle BigTableに移行

アプリはpythonで記述

レプリカや並列読出の工夫

BigData 処理基盤

Big Dataはバズワード．ともあれ，なぜ RDBじゃ駄目なのか?

元々はWebの解析 (Indexer)

とにかく大きい (PBクラス)

不定型 (スキーマが作れない)

ACID特性は必ずしも必要でない

応用例:

マーケティング情報 (POS等)→データマイニング

システムログ情報

センサー情報→ストリーム DB

位置情報→例: ドコモモバイル空間統計

システム例:

バッチ系: Hadoop，Google MapReduce

ストリーム系: Oracle Complex Event Processing, NEC CONNEXIVE, ...

9 / 28

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 / 28

MapReduce処理の概要

Map

Map

Map

Map

Reduce

Reduce

Data Data

HDFS HDFS<key, value>

keyごとにまとめる

<key, 結果>

12 / 28

入力と出力

Map入力

基本的には 1スプリットは 1ブロック．最寄りのものを利用．

TextInputFormat

キーはスプリット内オフセット

SequenceFileInputFormat

バイナリの入力 (同期点で分割可能)

スプリットをレコードに分解して Mapに入力

レコード境界とスプリットのずれをあわせる

圧縮されていれば戻す (レコード圧縮とブロック圧縮)

Reduce出力

reducer一つごとに一つのファイルを出力→ partなんとかという名前になる

reducerローカルに出力 (HDFSが 2つコピーを作る)

MultipleOutputFormat: 各出力 (KVペア)ごとにファイル名を決められる．

13 / 28

shuffleとsortの詳細

入力

White: Hadoop, Oreillyより引用

map

Map Task

spill file

map output file

reduce出力

partition,sort,

combine

copy

Reduce Taskcombine,merge sort

merge sort

memorybuffer

メモリ上

ディスク上

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));

}

}

16 / 28

Hadoop 関連のその他の BigData 技術

Hbaseカラム指向データベースRDBっぽいことをしたい時 (Joinはない)Javaから使う

HiveSQL風言語 (Hadoopへコンパイル)

PigRDB処理をスクリプトで書ける (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%

19 / 28

インターネットの今後

端末: PC，スマホ，タブレット,センサー?, IoT?

ブラウザ: Google, Apple, Mozilla, ?

標準規格: HTML, HTTP→ HTML5, WhatWG, HTTP2.0

クラウド: 広域分散,メモリ化,データマイニング (機械学習)

ビジネス: 広告費以外のビジネスモデルは?

20 / 28

この授業で取り上げられなかったこと

プライバシー個人情報保護法,不正指令電磁的記録罪最近のいろいろな事件仮想化・クラウド仮想マシン技術 (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

以下は時間があれば

22 / 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$

25 / 28

8

ビジネスの側面から見たWeb2.0

ロングテール部分

梅田「ウェブ進化論」を模式化

販売数

製品種別1位：ハリーポッターと不死鳥の騎士団2位：世界の中心で愛をさけぶ

3位：バカの壁

10mの首

5μの尻尾

年間７万点

従来のビジネスのターゲット

99

ロングテール広告

Google Adwords

Google Adsense

バナー

広告の対象となる人数

広告の種類

10

なぜロングテールビジネスが可能になったか

世界中（∞）の情報を0円で集める

光ファイバ

インターネット

ハイパーテキスト

すべての情報（∞）を0円で処理

CPU，HDD 検索エンジン

MapReduce, BigTable

価値化（∞ × 0 ＝ Value） AdWords，AdSense Wikipedia SNS

Access Front End Monetize Engine

•ロングテールビジネスはこれまでのビジネスとオーダーが違う（0と∞を扱うビジネス）

•皮膚感覚で語るのは危険•やりながら考えるしかない＝早くやったもん勝ち