丸山先生レクチャーシリーズ 2010 第3回
2010年 4月 22日(木) 楽天株式会社 本社

key-value ストアの基礎知識
首藤 一幸

1

内容
• key-value ストア• NoSQL データストア• 特徴とその根源• さらなるスケーラビリティを– デモ• スライド 30枚2key-value ストアとは• キーと値の組を書き込み、キーを指定することで値を読み出せる
データベース管理ソフトウェア
サーバ

キー 値

サーバクラスタを複数台で構成→ 分散 key-value ストア

HDDやSSD、メモリ上書き込み(put) 要求読み出し(get) 要求削除(remove) 要求
クライアント返答 (成否 等)
値
ユーザID : 最終ログイン時刻
証券の銘柄 : 株価3…

key-value ストアとは• プログラミング言語でいうと連想配列, 辞書 (dictionary), map– 「ハッシュ表」← 実装の仕方, データ構造・アルゴリズム

Java 標準ライブラリの java.util.Map 型
Map aMap = new HashMap();
aMap.put(“key1”, “value1”);… = aMap.get(“key1”);// “key1” をキーとして “value1” を格納// “key1” に対応する値を取得

Python の dictionaryaMap = dict()aMap[‘key1’] = ‘value1’… = aMap[‘key1’]# ‘key1’ をキーとして ‘value1’ を格納 4# ‘key1’ に対応する値を取得

key-value ストアとは• シンプルな問い合わせ– キーを１つ指定• ものによっては、範囲検索も。例：aで始まる語からcで始まる語まで– シンプル、というか貧弱– それを武器にして、高い性能とスケーラビリティを達成• ネットワーク越しにアクセス– クライアントライブラリを使ってアクセスする。
– データをローカルディスクに保存する DBM は key-value
ストアか？
• 例: Berkeley DB, Tokyo Cabinet, …

– 通常、key-value ストアとは呼ばない。

5

key-value ストアとは• データの格納先– ソフトウェアによって、メモリ上だったり HDD や SSD 上だったり。
– 格納先, ストレージエンジンを選べるものも多い。
– HDD だから遅いとも限らない。

• UNIX 系 OS, Windows などは、空きメモリでファイルの内容をキャッシュする。
• cf. kumofs (古橋), Tokyo Cabinet (平林)6

key-value ストアとは• 分散 key-value ストア– 複数台にデータを分散させられる key-value ストア。
– 台数で性能・容量を稼ぎ、複製で耐故障性を稼ぐ。
key value

key value格納

key value

格納

格納

key value

格納

クライアントライブラリ

クライアントライブラリによる複製の作成

key value

key value

格納 要求

分散 key-value ストアでの7サーバ群の連携例

ソフトウェア
• オープンソースソフトウェア– Flare (藤本氏)– Kai– kumofs (古橋氏)– memcached– ROMA– Tokyo Cabinet / Tokyo Tyrant (平林氏)– Voldemort (LinkedIn 社発)

GREE で活用

Facebook 他で活用
楽天で活用
mixi で活用• 商品– Coherence (Oracle)– Velocity (Microsoft)– WebSphere eXtreme Scale (IBM)8

どう使われているか• 強みが活きて、割り切っている点を許容できるような応用• ○ 強み– RDB とは桁違いの高性能 (qps, 低遅延)
– 数十台以上へのスケーラビリティに支えられた大容量• △ 割り切っている点– シンプルな問い合わせ方法– キー１つといった小さな単位での atomic な読み書き9
詳細は後ほど– 複製間の緩めの整合性

高性能 狙い• volatile なデータを対象とする• RDB のキャッシュとして使う• GREE, mixi

– アクセス履歴、というか足あと：数万 qps• Amazon (2007年)– 分散 key-value ストア Dynamo を使ってショッピングカートのデータを管理– １日あたり、数千万の要求と300万以上のチェックアウトを処理• Facebook (2008年12月)– memcached を使って RDB へのアクセスを軽減

10– 800台以上のサーバで 28 テラバイトを超えるメモリ領域

高性能 狙い• エンタープライズでの例– 金融機関からの RFP「応答 10ミリ秒以内」– RDB だけの設計では満たせなかったところ、key-value ストアを活用することで達成– RDB のキャッシュ• 実は、エンタープライズでの歴史は長い– Tangosol 社 Coherence → 現 Oracle社 Coherence• 2001年第4四半期 リリース

– IBM社 ObjectGrid → 現 WebSphere eXtreme Scale• 2005年 7月 リリース– memcached• 2003年 5月 30日 ver.1.0.0 リリース11

大容量 狙い• Google– ウェブから取得しまくったコンテンツを Bigtable に保存。
– ～１千台？でクラスタを構成。

row key“contents:”“anchor:cnnsi.com” “anchor:my.look.ca” “anchor:…

“com.cnn.www”“<html>…

“CNN”“com.example.www” “<html>…
<html>…
2009/12/17…
<html>…
2009/12/10…

“CNN.com”…

“Example.com”…

2009/12/3…

Google の基盤ソフト
Google File System (GFS)
Bigtable
MapReduce機能
狙い・性質
ファイルを保持大容量
表形式データストア
低遅延
12
データ処理
高スループットん？
• キーと値のペアではなくて、表だよね。
• Bigtable は key-value ストアなのか？
• key-value ストアだ！派の論拠– Bigtable 論文• A Bigtable is … sorted map. The map is indexed by a row key, column
key, and a timestamp; each value in the map is an uninterpreted array ofbytes.”(row:string, column:string, time:int64) → string• キーから値を取り出すのだから key-value ストアだろ– Google App Engine のウェブサイト

• … Bigtable, a large, distributed key-vlaue store … 13

key-value ストアとは呼ばない派• データモデルが key-value ペアのものに限って key-value ストアと呼ぶのがいいのでは？
• Bigtable の類 (データモデル: 表) が key-value ストアだとすると、RDB (表) も key-value ストアではないのか？
• RDB を key-valueストアに含めるとなると「key-valueストア」という語の存在意義がなくなる→ 含めない• Bigtable の類と RDB の間に違いはあるが、「key-value」という表現は当たらないのではないか。
14

Bigtable の類と RDB の違い• 効率よい問い合わせ処理のためには、特定 column / 列についての条件指定が要る。
– row を担当するサーバを特定するため• JOIN処理はサポートしない。その代わり、表のスキーマが固定されていない。
• 表全体にわたる ACID 性は緩和されている。
15

NoSQL というムーブメント• NoSQL is an umbrella term for a loosely defined class of
non-relational data stores that break with a long historyof relational databases and ACID guarantees. Data storesthat fall under this term may not require fixed table
schemas, and usually avoid join operations. The term wasfirst popularised in early 2009. (Wikipedia, 2009/12時点)• RDB ではないデータストア• 表全体に渡る ACID 性は緩和して、代わりに何かを得る。

– ACID: データベースのトランザクションが満たすべき性質。
atomicity/原子性, consistency/一貫性, isolation/独立性, durability/永続性。1970年代終わり頃に定義。
– CAP則とか eventual consistency とか…略
16

NoSQL: いっぱいあります• memcached, Bigtable, Dynamo, Amazon SimpleDB,
Cassandra, Voldemort, Ringo, VPork, MongoDB,
CouchDB, Tokyo Cabinet/Tokyo Tyrant, Flare, ROMA,
kumofs, Kai, Redis, HadoopのHBase, Hypertable,PNUTS, Scalaris, Dynomite, ThruDB, Neo4j, IBM
ObjectGrid, Oracle Coherence, Velocity, …
• データモデル– OSS memcached– Amazon Dynamo– Google Bigtable– Amazon SimpleDB– Windows Azure Table

key valuemap (key-value)map (key-value)
table
column
row
table
table

17

NoSQL データストアとkey-value ストア• key-value ストアは、NoSQL データストアとして扱われたり、そうでなかったり。

• 性質が共通– 強み：高性能, スケーラビリティ → 大容量– 割り切り：問い合わせ方法に制約, …

以降の話は、両者に共通

18

特徴の根源：atomic: 不可分な分散と atomicity との関係

row key• 1 key, 1行が基本単位– key-valueペア– 行 (row, item, entity)の集合• atomic な更新の単位 ⊆ 分散の単位とする

この列の値に基づいて– key-value ペア, 行は、同一マシンに載る。
担当サーバが決まる– key, 行が異なると、同一マシンに載るとは限らない。

=• 分散トランザクションは availability を損ねる
→ 避ける
atomic な更新は
19
同一サーバ上の key-value ペア、行でだけ保証

特徴
• 強み

– 高い性能• 水平分散 → サーバ台数を増やせる• atomicity 保証を同一サーバ上に限定 → スケールアウト– 高いスケーラビリティ → 大容量• 水平分散• 割り切り– 効率のよい問い合わせ方法が限られる• 特定 column / 列についての条件指定がないと、全サーバに問い合わせる必要が生じる。

– 細かい単位に限られた atomic な更新– 複製間の緩い整合性

20

講演概要の意味• “クラウド、特に PaaS 向けのソフトウェア開発が現実のものとなり、そこではリレーショナルデータベースとは違ったデータベースが勢いを増しています。その代表である key-value ストアを解説します。”• 意味– PaaS の一部として当たり前のようにNoSQL データストアや key-value ストアが提供されている– Google App Engine の datastore (Bigtable) や memcache,Azure Table, Amazon SimpleDB, …
利用者のSaaS

アプリケーション

利用者の情報システム

アプリケーション

PaaS

アプリケーション
フレームワーク / 実行環境

Iaas / HaaS

Iaas / HaaS(仮想) マシン / ネットワーク

Amazon EC2, S3, … Google App Engine, Google Apps, …
Windows Azure, …

ミドルウェア,DB 等

21さらなるスケーラビリティを
NoSQL / key-value ストアとpeer-to-peer のいいとこ取り

22考案した新方式を本日発表• 首藤研メンバが、今朝、発表したはず。

23

分散 key-value ストア / NoSQL データストアのアーキテクチャ• 担当サーバの判断を誰が行うか？
担当サーバ

サーバ群

中継サーバ / ゲートウェイ
クライアントサーバの一覧表

クライアントクライアント(1) クライアント側が判断する(2) 中継サーバが判断する(3) サーバが判断・転送する

例：memcached, ROMA,Dynamo

例：kumofs

例：Dynamo, Cassandra
24

それぞれの得失・向き不向きについて、かなり議論の余地がある分散データストアが狙うスケーラビリティ• Dynamo: Amazon の分散 key-value ストア– 数百台まで “its initial design targets a scale of サーバ側
up to hundreds of storage hosts.”

性能 重視– 本当にそこまで行けるか？
経路表 (サーバ一覧表) の一貫性維持が極めて大変。

• peer-to-peer…というか、非集中分散システムの技術

DHT (分散ハッシュ表) / 構造化オーバレイネットワーク– 数百万ノード以上

スケーラビリティ 重視
25
peer-to-peer 由来分散データストアが狙うスケーラビリティ

分散 key-value ストア 分散ハッシュ表 (DHT)•サーバ側•担当サーバに直接到達•全サーバが全サーバを把握•高性能 (低遅延)•～ 数百ノード？
01

2 …

全対全ID 空間

•peer-to-peer 由来•中継を繰り返して到達•一部のサーバのみを把握•高 スケーラビリティ•～ 数百万ノード？
経路表

例えば 0 ～ 2^160 のリング

0 1

2 …

26

Overlay Weaver – デモ
http://pl.shudo.net:3998/
DHT として運用してDNS を模擬
7ホップで (データ保持) 担当ノードに到達

40ヶ国 669台で DHT を構成
27

両方のいいとこ取り• 新しいルーティング アルゴリズムを開発

長尾洋也, 首藤一幸

新方式

中継なしのゼロホップ DHT• ノード数 少 → 担当サーバに直接到達• ノード数 多 → 中継を許容しきちんと到達

高性能28
高 スケーラビリティ

今後• NoSQL / key-value ストアへの実装– Cassandra ? 楽天 ROMA ?

• 「柔軟な経路表管理」概念の応用– よりよい DHT• ネットワーク近接性の考慮• 複数の表の管理– 経路表爆発の起きない広域ルーティング方式
–…
29

内容
• key-value ストア– ネットワーク越しに使う連想配列, map• NoSQL データストア– RDB ではないデータストア– ムーブメント• 特徴とその根源– キー, 行を単位として分散– 分散トランザクションを避ける• さらなるスケーラビリティを– peer-to-peer 由来の新方式

30