スライド 1

Size: px

Start display at page:

Download "スライド 1"

りさこたけくま
4 years ago
Views:

1 丸山先生レクチャーシリーズ 2010 第 3 回 2010 年 4 月 22 日 ( 木 ) 楽天株式会社本社 key-value ストアの基礎知識首藤一幸 1

2 内容 key-value ストア NoSQL データストア特徴とその根源さらなるスケーラビリティをデモスライド 30 枚 2

3 key-value ストアとはキーと値の組を書き込みキーを指定することで値を読み出せるデータベース管理ソフトウェアサーバキー値サーバクラスタを複数台で構成分散 key-value ストア書き込み (put) 要求読み出し (get) 要求削除 (remove) 要求 HDD や SSD メモリ上返答 ( 成否等 ) 値クライアントユーザID : 最終ログイン時刻証券の銘柄 : 株価 3

4 key-value ストアとはプログラミング言語でいうと連想配列, 辞書 (dictionary), map ハッシュ表実装の仕方, データ構造アルゴリズム Java 標準ライブラリの java.util.map 型 Map amap = new HashMap(); amap.put( key1, value1 ); = amap.get( key1 ); // key1 をキーとして value1 を格納 // key1 に対応する値を取得 Python の dictionary amap = dict() amap[ key1 ] = value1 = amap[ key1 ] # key1 をキーとして value1 を格納 # key1 に対応する値を取得 4

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

6 key-value ストアとはデータの格納先ソフトウェアによってメモリ上だったり HDD や SSD 上だったり格納先, ストレージエンジンを選べるものも多い HDD だから遅いとも限らない UNIX 系 OS, Windows などは空きメモリでファイルの内容をキャッシュする cf. kumofs ( 古橋 ), Tokyo Cabinet ( 平林 ) 6

7 key-value ストアとは分散 key-value ストア複数台にデータを分散させられる key-value ストア台数で性能容量を稼ぎ複製で耐故障性を稼ぐ key value key value 格納格納 key value 格納 key value 格納 key value key value クライアントライブラリ格納要求クライアントライブラリによる複製の作成分散 key-value ストアでのサーバ群の連携例 7

8 ソフトウェアオープンソースソフトウェア Flare ( 藤本氏 ) GREE で活用 Kai kumofs ( 古橋氏 ) memcached Facebook 他で活用 ROMA 楽天で活用 Tokyo Cabinet / Tokyo Tyrant ( 平林氏 ) mixi で活用 Voldemort (LinkedIn 社発 ) 商品 Coherence (Oracle) Velocity (Microsoft) WebSphere extreme Scale (IBM) 8

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

10 高性能狙い volatile なデータを対象とする RDB のキャッシュとして使う GREE, mixi アクセス履歴というか足あと : 数万 qps Amazon (2007 年 ) 分散 key-value ストア Dynamo を使ってショッピングカートのデータを管理 1 日あたり数千万の要求と 300 万以上のチェックアウトを処理 Facebook (2008 年 12 月 ) memcached を使って RDB へのアクセスを軽減 800 台以上のサーバで 28 テラバイトを超えるメモリ領域 10

11 高性能狙いエンタープライズでの例金融機関からの RFP 応答 10 ミリ秒以内 RDB だけの設計では満たせなかったところ key-value ストアを活用することで達成 RDB のキャッシュ実はエンタープライズでの歴史は長い Tangosol 社 Coherence 現 Oracle 社 Coherence 2001 年第 4 四半期リリース IBM 社 ObjectGrid 現 WebSphere extreme Scale 2005 年 7 月リリース memcached 2003 年 5 月 30 日 ver リリース 11

12 大容量狙い Google row key com.cnn.www ウェブから取得しまくったコンテンツを Bigtable に保存 ~1 千台? でクラスタを構成 com.example.www 2009/12/ /12/ /12/3 contents: anchor:cnnsi.com anchor:my.look.ca <html> CNN CNN.com <html> Example.com <html> <html> anchor: Google の基盤ソフト機能狙い性質 Google File System (GFS) ファイルを保持大容量 Bigtable 表形式データストア低遅延 12 MapReduce データ処理高スループット

13 ん? キーと値のペアではなくて表だよね 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 of bytes. (row:string, column:string, time:int64) string キーから値を取り出すのだから key-value ストアだろ Google App Engine のウェブサイト Bigtable, a large, distributed key-vlaue store 13

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

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

16 NoSQL というムーブメント NoSQL is an umbrella term for a loosely defined class of non-relational data stores that break with a long history of relational databases and ACID guarantees. Data stores that fall under this term may not require fixed table schemas, and usually avoid join operations. The term was first popularised in early (Wikipedia, 2009/12 時点 ) RDB ではないデータストア表全体に渡る ACID 性は緩和して代わりに何かを得る ACID: データベースのトランザクションが満たすべき性質 atomicity/ 原子性, consistency/ 一貫性, isolation/ 独立性, durability/ 永続性 1970 年代終わり頃に定義 CAP 則とか eventual consistency とか略 16

17 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 map (key-value) Amazon Dynamo map (key-value) Google Bigtable table Amazon SimpleDB table Windows Azure Table table key row column value 17

18 NoSQL データストアと key-value ストア key-value ストアは NoSQL データストアとして扱われたりそうでなかったり性質が共通強み : 高性能, スケーラビリティ大容量割り切り : 問い合わせ方法に制約, 以降の話は両者に共通 18

19 特徴の根源 : atomic: 不可分な分散と atomicity との関係 1 key, 1 行が基本単位 key-value ペア行 (row, item, entity) の集合 row key atomic な更新の単位分散の単位とする key-value ペア, 行は同一マシンに載る key, 行が異なると同一マシンに載るとは限らない = この列の値に基づいて担当サーバが決まる分散トランザクションは availability を損ねる避ける atomic な更新は同一サーバ上の key-value ペア行でだけ保証 19

20 特徴強み高い性能水平分散サーバ台数を増やせる atomicity 保証を同一サーバ上に限定スケールアウト高いスケーラビリティ大容量水平分散割り切り効率のよい問い合わせ方法が限られる特定 column / 列についての条件指定がないと全サーバに問い合わせる必要が生じる細かい単位に限られた atomic な更新複製間の緩い整合性 20

21 講演概要の意味クラウド特に PaaS 向けのソフトウェア開発が現実のものとなりそこではリレーショナルデータベースとは違ったデータベースが勢いを増していますその代表である key-value ストアを解説します意味 PaaS の一部として当たり前のように NoSQL データストアや key-value ストアが提供されている Google App Engine の datastore (Bigtable) や memcache, Azure Table, Amazon SimpleDB, 利用者の情報システム利用者のアプリケーション PaaS SaaS アプリケーションアプリケーションフレームワーク / 実行環境ミドルウェア, DB 等 Iaas / HaaS Iaas / HaaS ( 仮想 ) マシン / ネットワーク Amazon EC2, S3, Google App Engine, Windows Azure, Google Apps, 21

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

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

24 分散 key-value ストア / NoSQL データストアのアーキテクチャ担当サーバの判断を誰が行うか? サーバ群担当サーバ中継サーバ / ゲートウェイクライアントクライアントサーバの一覧表クライアント (1) クライアント側が判断する (2) 中継サーバが判断する (3) サーバが判断転送する例 :memcached, ROMA, Dynamo 例 :kumofs 例 :Dynamo, Cassandra それぞれの得失向き不向きについてかなり議論の余地がある 24

25 分散データストアが狙うスケーラビリティ 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 由来

26 分散データストアが狙うスケーラビリティ分散 key-value ストア分散ハッシュ表 (DHT) サーバ側担当サーバに直接到達全サーバが全サーバを把握高性能 ( 低遅延 ) ~ 数百ノード? peer-to-peer 由来中継を繰り返して到達一部のサーバのみを把握高スケーラビリティ ~ 数百万ノード? 全対全経路表 ID 空間例えば 0 ~ 2^160 のリング 26

27 Overlay Weaver デモ DHT として運用して DNS を模擬 7 ホップで ( データ保持 ) 担当ノードに到達 40 ヶ国 669 台で DHT を構成 27

28 両方のいいとこ取り新しいルーティングアルゴリズムを開発新方式長尾洋也, 首藤一幸中継なしのゼロホップ DHT ノード数少担当サーバに直接到達高性能ノード数多中継を許容しきちんと到達高スケーラビリティ 28

29 今後 NoSQL / key-value ストアへの実装 Cassandra? 楽天 ROMA? 柔軟な経路表管理概念の応用よりよい DHT ネットワーク近接性の考慮複数の表の管理経路表爆発の起きない広域ルーティング方式 29

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

Microsoft PowerPoint - shudo-NoSQL-data-model ppt

Microsoft PowerPoint - shudo-NoSQL-data-model ppt 28 2009 12 17 NoSQL 1 NoSQL, key-value store, documentoriented DB, graph DB, memcached, Bigtable, Dynamo, Amazon SimpleDB, Cassandra, Voldemort, Ringo, VPork, MongoDB, CouchDB, Tokyo Cabinet/Tokyo Tyrant,