NoSQL編 Papers & Presentations Onizuka Laboratory NoSQL

クラウドにおける大規模データ管理・

分散処理の研究動向

-- NoSQL 編 --

鬼塚真

主幹研究員 ( 特別研究員 )

NTT サイバースペース研究所

目次

データクラウドの基本

データクラウドと分散 DBMS の違い

ACID と BASE

CAP 定理と PACELC

代表的な NoSQL

Bigtable

Dynamo

PNUTS

Megastore

研究の方向性

データクラウドの基礎

分散 DBMS とは？

分散型のデータベース管理システム (DBMS)

DBMS の特徴

リレーショナルモデル , SQL による検索処理

ACID トランザクション ( データを正しく保つ機能 ) 銀行業務などの OLTP 向け ( オンライントランザクショ ン ₎

DBMS を複数並べて (participant), 調停役

(coordinator) が束ねる

ハッシュジョイン , セミジョインなどの高速化 二相コミットプロトコル (prepare + commit)

データクラウドと分散 DBMS の違

データクラウドとは？ い

100 台～ 1 万台のマシンで運用されるデータサービス ( 例 : Google app engine) ．本発表ではサービスそのもの ではなく，バックエンドで利用されている技術について議論 する

分散ファイルとは異なり，データベース的な機能が付加さ れている ( 簡易トランザクション，簡易 SQL 操作 )

データクラウドと分散 DBMS の違

データクラウドとは？ い

100 台～ 1 万台のマシンで運用されるデータサービス ( 例 : Google app engine) ．本発表ではサービスそのもの ではなく，バックエンドで利用されている技術について議論 する

分散ファイルとは異なり，データベース的な機能が付加さ れている ( 簡易トランザクション，簡易 SQL 操作 )

大きく分けて 2 つの流れがある

1. トランザクションを簡略化して大規模化する

(BigTable, Dynamo, PNUT, Cassandra, …) 2. MapReduce を SQL 対応 / 高度化する

(SCOPE, Pig Latin, Clustera,…)

データクラウドと分散 DBMS の違

い 分散 DBMS

1. NoSQL 系列 2. MapReduce 系列

データクラウドと分散 DBMS の違

い 分散 DBMS

1. NoSQL 系列 2. MapReduce 系列

マシン 台数

0.1K

10K

データ量

TB

PB

データクラウドと分散 DBMS の違

い 分散 DBMS

1. NoSQL 系列 2. MapReduce 系列

マシン 台数

0.1K

10K

トラ ン^ザ

ク^シ ョン

ACID

BASE

トラン ザク

ション ACID

なし

トランザクション

BASE ^なし

データ量

TB

PB

データクラウドと分散 DBMS の違

い 分散 DBMS

1. NoSQL 系列 2. MapReduce 系列

マシン 台数

0.1K

10K

トラ ン^ザ

ク^シ ョン

ACID

BASE

トラン ザク

ション ACID

なし

トランザクション

BASE ^なし

デ^ー タ^処

理

SQL

データ処理

簡易 SQL ^{汎用 API}

SQL + UDF

汎用 API デー

タ処 理

簡略化

データ量

TB

PB

データクラウドと分散 DBMS の違

い 分散 DBMS

1. NoSQL 系列 2. MapReduce 系列

マシン 台数

0.1K

10K

トラ ン^ザ

ク^シ ョン

ACID

BASE

トラン ザク

ション ACID

なし デ^ー

タ^処 理

SQL

データ処理

簡易 SQL ^{汎用 API}

トランザクション

BASE ^なし

データ量

TB

PB

最適化

生データ デー

タ形 式 SQL +

UDF

汎用 API デー

タ処 理

データ形式

最適化 ^生データ

簡略化

トランザクションのレベル

トランザクションのレベル

ACID とは？

Atomicity Consistency Isolation

Durability

Base: An Acid Alternative

Dan Pritchett , ACM QUEUE May/June 2008

トランザクションのレベル

ACID とは？

Atomicity Consistency Isolation

Durability

　 BASE とは？

Basically Available Soft state

Eventual consistency

Base: An Acid Alternative

Dan Pritchett , ACM QUEUE May/June 2008

トランザクションのレベル

ACID とは？

Atomicity Consistency Isolation

Durability

　 BASE とは？

Basically Available Soft state

Eventual consistency

Base: An Acid Alternative

Dan Pritchett , ACM QUEUE May/June 2008

トランザクションの分離 永続キューの利用

データクラウドと分散 DBMS の違い

処理特性 データ量 マシン数

(/ サイ 業務 特徴 ト )

DBMS オンライン系

(OLTP) ^銀行業務 random read/write

， ACID ^{～ TB ～ 100}

分析系(OLAP) ^{戦略的 意}思決定支援 sequential read , スナップショット一貫 性

～ PB ～ 100

NoSQL

系列 オフライン系 検索エンジ ンのバック エンド用途

sequential read, random write ( ク ローラ )

～ 100TB ( 日 本 ) ～ 1PB ( 世 界 )

1K ～10K 　

オンライン系 web アプリ random read/write, BASE

？ 1K ～

10K 　 MapRe オフライン系 分析処理 sequential read ～ PB 1K ～

Megastore 2010

データクラウドの変遷 ( 継承した機

能 )

Cassandra 2008 Bigtable 2006

MapReduce 2004

Dynamo 2007 Pig latin 2008

PNUTS 2008

C-store/Vertica 2005 分散データベース

垂直分割 / カラム圧縮

タブレット

コンシステント ハッシュ

タブレット

Clustera 2008

水平垂直分散

SCO 2008

ＳＱＬ

分散処理 ハッシュ分散

転置ファイル

圧縮

垂直分散

Dryad 2007

Haloop 2010 ²⁰¹⁰ Azure 2009

データクラウドの設計

CAP 定理 (Eric Brewer, 2000)

If (network Partitions) then Consistency or Availability

分散システム (P) では一貫性と可用性を両立できない CA: 単体のデータベース

Copyright 2011 日本電信電話株式会社

データクラウドの設計

CAP 定理 (Eric Brewer, 2000)

If (network Partitions) then Consistency or Availability

分散システム (P) では一貫性と可用性を両立できない CA: 単体のデータベース

PACELC (Daniel Abadi, 2010)

If P then C or A else Latency or C

CAP 定理 + P が生じない時は性能か一貫性かを重 視

PC/EC: 分散データベース , BigTable ( 全レプリカ同 期 )

PA/EL: Dynamo ( レプリカ非同期＆版マージ )

25

代表的な NoSQL

PC: Bigtable (Google) の特徴

主に web ページの保管用途

(google earth のようなオンライン系での用途でも利用 )

垂直分散 + 水平 ( 範囲 ) 分散型のデータベース

垂直分散 : locality group

水平分散 : tablet 群を Btree 構造 (meta tablet) で管理

PC: Bigtable (Google) の特徴

主に web ページの保管用途

(google earth のようなオンライン系での用途でも利用 )

垂直分散 + 水平 ( 範囲 ) 分散型のデータベース

垂直分散 : locality group

水平分散 : tablet 群を Btree 構造 (meta tablet) で管理

全レプリカ同期書き込み

PC: Bigtable (Google) の特徴

主に web ページの保管用途

(google earth のようなオンライン系での用途でも利用 )

垂直分散 + 水平 ( 範囲 ) 分散型のデータベース

垂直分散 : locality group

水平分散 : tablet 群を Btree 構造 (meta tablet) で管理

全レプリカ同期書き込み

DBMS との違い : 簡易クエリ・簡易トランザクション

KVS, レコード単位のアトミック性

重要な特徴 : GFS をストレージとして利用

GFS レベルでデータを多重化 ( 同期型 )

キー値でソートして GFS に格納．定期的なファイルマージ ( コン パクション ) が必要． sequential read の性能を上げるための設計

．

PA: Dynamo (Amazon) の特徴

Amazon ショッピングカートのデータ管理

重要な特徴 : 高可用性の実現に注力した設計 定足数アルゴリズム (quorum)

定足数を同期 write ( 全 3 replica なら 2 replica) 3 write + 1 read, 1 write + 3 read などバリエーショ

書き込みン

少なくとも W=2 の書き込み成功

古いデータのまま

読み取り

R=2 のみの応答で OK

（どの 2 つからでも最新データを取得）

一貫性と性能を両立 一貫性と性能を両立

ITpro テクノロジ・カンファレンス「徹底理解『 Amazon クラウドサービス』」 井上氏資料より

Copyright 2011 日本電信電話株式会社

PA: Dynamo (Amazon) の特徴

Amazon ショッピングカートのデータ管理

重要な特徴 : 高可用性の実現に注力した設計 定足数アルゴリズム (quorum)

定足数を同期 write ( 全 3 replica なら 2 replica) 3 write + 1 read, 1 write + 3 read などバリエーショ ン

sloppy quorum: network partitions が生じても独立に

更新 ³¹

書き込み

少なくとも W=2 の書き込み成功

古いデータのまま

読み取り

R=2 のみの応答で OK

（どの 2 つからでも最新データを取得）

一貫性と性能を両立 一貫性と性能を両立

ITpro テクノロジ・カンファレンス「徹底理解『 Amazon クラウドサービス』」 井上氏資料より

PC/EL: PNUTS (Yahoo) の特

徴

ordered table は BigTable と同様に tablet を利 用

BigTable との違い : オンライン系サービス向け レコード単位の timeline consistency 保障

ストレージには MySQL を利用 (ordered table)

参照系の性能に優れる

多重化管理をファイルシステムに頼らない

フェール時のリカバリが高速

PC/EL: PNUTS (Yahoo) の特

徴

ordered table は BigTable と同様に tablet を利 用

BigTable との違い : オンライン系サービス向け レコード単位の timeline consistency 保障

ストレージには MySQL を利用 (ordered table)

参照系の性能に優れる

多重化管理をファイルシステムに頼らない

フェール時のリカバリが高速

PACELC について

マスタレプリカ更新方式

データクラウドの設計のまとめ

レプリケーショ

ン方式 ^{全レプリカ同期}更新 ^{マスタレプリカ}更新 ^定足数

利点 データ一貫性

が強い ^{書き込み応答}時間が速い ^{データ一貫性}が強い

欠点 書き込み応答

時間が遅い ^{データ一貫性}が弱い ^{制御が複雑} プロダクト Bigtable,

HBase ^{PNUTS Dynamo,} Cassandra

Megastore (Google) の特徴

オンラインサービス向け． 100 以上の内外応用で商用利 用．

ACID 性 or 高可用性を実現

entity group 内は ACID トランザクションを実現 99.999% 以上の可用性も実現

その他機能

paxos の高速実装によりデータセンタ間レプリカ同期 二次インデックス

entity group 間は永続キューにより BASE をサポート ACID トランザクションも Megastore はサポート

但し，Ｃと A は両立ではなく設計レベルにおいて選択する

研究の方向性

研究の方向性

問い合わせ機能の拡張

簡易 SQL 検索から汎用 SQL への拡張 分散問い合わせの最適化

クラウド環境における動的ワークロードの最適化

研究の方向性

問い合わせ機能の拡張

簡易 SQL 検索から汎用 SQL への拡張 分散問い合わせの最適化

クラウド環境における動的ワークロードの最適化

高可用性と強一貫性の組合せは Megastore で実現 それぞれを独立に追及するのは研究的に攻めにくい 設計者は機能を的確に組み合わせるのが難しい

→ ワークロードを入力とした自動設計技術

　　参照重視の操作と更新重視の操作のバランス

　　強一貫性を保証しつつ高い応答性能を出すためのデータ配 置

研究の方向性

NoSQL 向けベンチマーク

Yahoo Cloud Serving Benchmark

R/W の組合せワークロードであり，クラウドの特性で の観点が不十分

→ 拡張性・耐障害性を想定した，可用性と一貫性を測 るベンチマーク