key-valueストアの基礎知識

首藤 一幸

Last-updated: April 21, 2010

注: このページの文章は Software Design 誌 2010年 2月号に掲載された以下の記事の元原稿です。 Software Design 誌編集部の了承の元に、本ウェブページに掲載しております。
首藤一幸: "key-valueストアの基礎知識", Software Design 2010年 2月号, p.14-21, (株)技術評論社, 2010年 1月 18日

クラウド、特にPaaS向けのソフトウェア開発が現実のものとなり、 そこではリレーショナルデータベースとは違ったデータベースが 勢いを増しています。 その代表であるkey-valueストアを解説します。

もくじ

key-valueストアとは

key-valueストアとは、キーと値の組を書き込み、 キーを指定することで値を読み出せるデータベース管理ソフトウェアです。 最近のプログラミング言語は、標準で、 連想配列や辞書（dictionary）、mapといったデータ型、クラスを提供しています （リスト1）。 アレと同じ使い方ができるデータベースだと思ってください。 実装も日増しに増えています（表1）。

Javaのjava.util.Map型: 
Map aMap = new HashMap();
aMap.put("key1", "value1");  // "key1" をキーとして "value1" を格納
... = aMap.get("key1");	     // "key1" に対応する "value1" を取得
Pythonのdictionary: 
aMap = dict()
aMap['key1'] = 'value1'      # 'key1' をキーとして 'value1' を格納
... = aMap['key1']           # 'key1' に対応する 'value1' を取得
リスト1: プログラミング言語やライブラリが提供するmap
表1: 各種key-valueストア

シンプルな問い合わせ

リレーショナルデータベース（RDB）をご存知の方は、 問い合わせ（読み出し）の際に指定する条件がキー１つだけというのは なんともシンプル、というか貧弱に感じることと思います。 key-valueストアは、このシンプルさを逆に武器にして、 高い性能とスケーラビリティを達成します。

ソフトウェアによっては、範囲検索、つまりキーの範囲を指定しての 問い合わせができるものもあります。 その場合、例えば、キーが英単語だとして、 辞書順にaで始まる語からcで始まる語まで（のキーと値の組）を読み出す、 ということができます。

どこまでがkey-valueストアか

key-valueストアはネットワーク越しに使うことが一般的です（図１）。 通信プロトコルとしては、memcachedというkey-valueストアのものを実装した ソフトウェアが多いです。 クライアント側としては、 そういった通信プロトコルに沿った通信を自身で行ってもよいのですが、 たいてい、それを行ってくれるライブラリが用意されています。 memcachedプロトコルを喋るライブラリはたくさんあり、 Java、Python、Ruby、Perl、PHP、C、C++、C#など主要な言語用のものが手に入ります。

キーと値の組を書き込むという意味では、 ライブラリとして使ってローカルファイルにデータを格納する DBM（Database Manager）（Tokyo Cabinet編 参照）も key-valueストアと呼んでいいような気がしますが、 通常、key-valueストアには含めません。


図1: key-valueストアの構造

データの格納先

データの格納先は、ソフトウェアによって メモリ上だったりHDDやSSD上だったりします。 設定によって格納先を切り替えられるソフトウェアが多いです。 その場合、メモリやディスクへの最終的な格納を担当する部分、 つまりストレージエンジンをいくつかの中から選べるようになっています。 格納先がメモリだと読み書きが速く、 HDDだと遅い、かというと、そうとも限りません。 UNIX系OSやWindowsといったサーバ・PC向けのOSは ファイルの内容を空きメモリに載せてキャッシュするので、 注意深く作られていれば、メモリ使用と同等の性能を達成できます （Tokyo Cabinet編、kumofs編 参照）。

分散key-valueストア

key-valueストアには、1台、単独での動作が前提のものと、 複数台にデータを分散させられるものがあります。 後者を特に「分散（distributed）」key-valueストアと呼びます。 複数台で、性能と容量、耐故障性を稼ぐわけです。

あるキーと値の組を書き込む際、 どのサーバに保持させるかはキーごとに決まります。 担当サーバを決定・管理する方法にはいろいろあります。 空き容量の多いサーバに割り当てるなどして、割り当て先を表で管理する方式、 表を不要とするためにキーの内容から割り当て先を決める方式など、様々です。 後者には、mod N（Nはサーバ数）の方法、 consistent hashingなどがあります。

また、たいていは、いくつかのサーバ上に複製（replica）を作ります。 これによって耐故障性を高めます。 1台が故障で停止しても他のサーバから複製を読み出せる、というわけです。

データが複数台に分散していても、 使う側、つまりクライアントソフトウェアはそれを意識する必要はありません。 どれか1台に対してアクセスすればよいか、そうでなくとも、 アクセスに使うライブラリがアクセス先を自動的に選んでくれます。

単独動作のkey-valueストアであっても、 複数台にデータを分散させることはできます。 ライブラリがアクセス先サーバを決めればよいのです（図2(a)）。 実際、memcachedライブラリの多くはこれを行います。 ただし、分散key-valueストア（図2(b)）と比べると限界はあります。 ここで詳細は述べませんが、例えば、 複製の作成はできるものの効率的な維持が難しいです。


図2: 複製の作り方

なぜkey-valueストアか

key-valueストアには、一般的に、次の特徴があります。

こういった利点は、次の割り切りによって得られています。

もちろん、実際の特徴・性質はソフトウェアによって様々です。 例えば、整合性について厳しめの条件を保証するkey-valueストアもあるでしょう。

この章では、こういった強みと割り切りについて詳細に説明していきます。 少々ツッコんだ内容になるので、概要がわかれば充分という方は 次の章（「key-valueストアの使いどころ」）まで 読み飛ばして下さって構いません。

ここで言う性能とは、1秒あたりにさばける読み書き要求の数、 つまりqueries per second (qps)、要求数についてのスループットです。 key-valueストアは、RDBと比べて文字通り桁違いに高い性能を発揮します。 遅延（latency）、つまり、要求から返答までの時間も短いです。 一方、データ量についてのスループットは、 BLOB (binary large object)（画像ファイルなど）用データストアの 場合に問われるくらいです。

高いスケーラビリティとは、台数に応じた性能を得やすいということです。 これはスループットについてだけでなく、容量についても言えます。 例えば、データ全体のコピー、つまりレプリケーションは耐故障性を高めますが、 保持できるデータ量は1台の場合と変わりません。 分散key-valueストアの場合、このようなコピーが可能なものもありますが、 加えてキーを単位としてデータを分散させられることが一般的です。 Amazon社DynamoやOracle社Coherenceは、 少なくとも数百台での動作実績があると聞きます。

RDBでも、表を水平分割しての複数台への分散、つまりshardingが可能です。 例えばeBay社ではユーザデータを20台に分散しているそうです（2008年時点） [1]。 ただし、台数を増やして、なおかつ、まともな性能を得るためには、 結局は、key-valueストアと同様の割り切り （例：インデックスをほとんど作成しない）が必要となります。

分散システム、より広く言うと、 並列処理において10台で10倍の性能を得ることは難しいことです (*1)。 性能を稼ぐために、サーバ1台の性能を強化するアプローチをスケールアップ （scale upまたはvertical scaling）、 台数を増やすアプローチをスケールアウト （scale outまたはhorizontal scaling）と言います。 つまり分散key-valueストアには、 スケールアウトが可能という強みがあるわけです。 一方、スケールアップとは、例えばCPUを高速なものに交換するといった アプローチを指します。 すると、コストパフォーマンスの良いコモディティ製品では済まなくなり、 2倍の性能を得るために10倍のお金がかかりかねません。 高くつき、なおかつ限界があります。

(*1) 昔、友人の親父さんが「10台なら10倍以上の性能にするのがプロだろう！」 と言ったそうです。 これはもっともな感想ですが、 理論的には無理で、実際にもごくごく限られた状況でだけ起こります。

可用性（availability）は、古典的には、故障などによる停止時間の短さを表します。 しかし分散key-valueストアの場合、 サーバが停止していっても最後の1台までアクセスを受け付けるものもあります。 ここで、停止中か動作中かを考えてもあまり意味がありません。 そこで、本稿では特に、動作中であっても （ロックされているといった理由で） クライアントからの要求に返答できない状況を、可用ではない、として扱います。 この観点でも、key-valueストアは高い可用性を発揮します。

耐故障性（fault-tolerance）は、キーと値の組を単位としての複製や、 データ全体のレプリケーションによって高めることができます。 これは、RDBでも機能やツールがあればできることですが、 たいていの分散key-valueストアはこれを当然のこととして行うので、 より容易に行えます。

強みと割り切りの関係

こういった強みを獲得するため、以下の通り、逆に何かを割り切って捨てています。

・シンプルな問い合わせ方法

問い合わせ方法をキー1つの指定に限定することで、 高速な検索のための表（例：ハッシュ表やB+木）は1つで済み、 データ書き込み時に書き換えなければならない個所を少なく抑えています。 問い合わせの解釈、実行も素早く済み、性能を稼げます。 複雑・高度な問い合わせをサポートし、 複数のカラムに検索表・インデックスを作成できるRDBと対称的です。

・細かい単位に限られたatomicな更新

キーと値の組、また、読み出しや書き込みといった細かい単位でだけ、 atomicな処理が可能です。 これには、atomic性保証のための重めの処理を避けるという性能上の理由と、 可用性を高く保つという理由があります。

atomic（不可分）とは、まとまった読み書き要求のすべてが、完遂されるか、 あるいはまったく行われないかのどちらかになることを指します。 例えば、キーAの値を読み出して、1を加算し、書き戻すという処理を考えます。 Aさんのウェブページが参照されて参照カウンタを増やすという場合や、 Aさんの銀行口座に1円を振り込むという場合を想像してください。 読み出しから書き戻しまでの間に、 自分以外のクライアントがAの値を書き込むするかもしれません（図3）。 その場合、他クライアントによる書き込みはなかったことになってしまいます。 これでは困ります。 こういた状態や、それを引き起こすバグを競争状態（race condition）と言います。


図3: 競争状態（race condition）

これを防ぐ1つの方法は、読み出しから書き戻しまでを データストアがatomicに処理することです。 すると、読んでから書くまでの間に割り込まれなくなるので、 処理前後の整合性（consistency）を保てます。 atomicに処理を行うためには、割り込まれないようにロックをかけます。 RDBでは、まとまったいくつかの要求を1つのトランザクションとして扱って、 atomicに処理することができます。

key-valueストアでatomicに処理できるのは、 単一キーに対する、読み書き要求1つだけです。 これでは図3の競争状態を防げません。 そこで、多くのkey-valueストアは、 CAS (compare-and-swap) という条件付き更新要求を受け付けることができます。 これを使うと「値が10なら11に更新する」という条件付き更新を要求でき、 この条件判断と更新はatomicに処理されます。 すると、図3では11の書き戻しが失敗し、 またあらためて読み出しからやり直せる、というわけです。

処理前後の整合性を維持するために、 ロックをかけて他からの書き込みを防ぐ方法を非観的（pessimistic）、 CASのようにロックをかけない方法を楽観的（optimistic）と言います。 ロックは、分散システムやマルチプロセッサのCPUでは高くつき、 スケールアウトを妨げるため、 今日、いかにロックを避けるかが技術者・研究者にとって重要な課題となっています。

RDBのトランザクションでは、データ1つと言わず、 表の複数個所や複数の表にまたがったatomicな処理が可能です。 key-valueストアは、それ自体では、 複数のキーにまたがってatomicな処理を行う手段は用意していません。 複数のキーにまたがると、複数のサーバにまたがる可能性があり、 ネットワーク越しにatomic性を保証するという大変重い処理が必要になってしまいます。 RDBで言うところの分散トランザクションです。 これは、重いだけではなくて、 ロックを伴い、他のクライアントからのアクセスを妨げます。 つまり、可用性を下げます。

key-valueストアは、これを避けるために atomic性を保証する単位を細かく保っているのです。

・複製間の緩い整合性

サーバをまたがったatomicな読み書きをサポートしないとはいえ、 複製どうしの整合性は何かしら保証しないと使いものになりません。 値を5から10に更新したのに、 更新が他の複製に伝播せず、いつまでも5が読み出されるのでは困ります。

これに対して多くのkey-valueストアは、 ある程度の保証はしながらも緩い保証にとどめることで、性能と可用性を得ています。

クライアントからのアクセスが必ず決まった複製に届くのであれば、 整合性維持はサーバ1台上の問題、つまりプロセス間、スレッド間の問題となり、 比較的ミクロな、ナノ秒〜マイクロ秒単位で解決できる課題となります。 ところが実際は、サーバが停止して 別の複製に要求が届くようになるということが起こります。 また、複数の複製にアクセスを分散させて性能を稼ぐということもよく行われます。 そのため、サーバをまたがった複製間の整合性について考えざるを得ません。

読み書きを行うクライアント側から見て、 読み出しの際に、どのクライアントがいつ書いたどの値が読み出され得るのか、 つまりどのくらい厳しく、または緩く整合性（consistency）が維持されるのかを 規定・記述したものを整合性モデル（consistency model）と言います。 最も厳しいモデルはstrict consistencyで、 最後に書き込まれた値が読み出されるというものです。 詳細は省きますが、これは分散システムはおろか マルチプロセッサでも実用的な性能にはできません。 実用上最も厳しいのがsequential consistencyで、 これを達成するためには、異なるクライアントからの すべての書き込みを順序付けする必要があります。 これでもまだ分散システムでは現実的ではありません。 このように、緩めていくほど性能上有利になっていくのですが、 一方では読み出される値がどれになるか定まらず、 使い勝手は悪くなっていきます。

多くのkey-valueストアでは、これを eventual consistencyというところまで緩めます。 あるキーに対する値を5から10に変更したとして、その後であっても、 どの複製を読むかによって5が読み出されてしまうことを許容します。 そして、その後の上書きがなければ、「いつかは必ず（eventually）」 すべての複製に10が伝わり、どの複製を読んでも10が得られるようになります。 ここでは、全複製への伝播にかかる時間の長短は問題ではありません。 例えば、伝播にかかる時間が平均1マイクロ秒といった素早さだったとしても、 何秒以内、とか、次の読み込みまでには、といった何らかの保証がないのなら、 eventual consistencyです。

eventual consistencyまで緩めることで、 書き込まれた値を複製に対して非同期に伝えていくことが可能になります。 いつまでに伝播させねばならないという制約がないため、 クライアントからの書き込み要求にはひとまずすぐに返答しておいて、 その後で書き込まれた値を複製に伝播させればよいのです。 複製の伝播が完了しておらずとも、 クライアントからの要求に応えることの方を優先できるので、性能を稼げます。 また、可用性を下げずに済みます。

key-valueストアの使いどころ

key-valueストアは万能でも、 あらゆる面でRDBより優れているというわけでもありません。 適材適所であって、それぞれに使いどころがあります。 RDBなどと組み合わせて使うことも一般的です。

使いどころはやはり、key-valueストアの強み

が活きて、割り切っている点 を許容できるような応用です。 以下、具体例から、使いどころの考え方を探っていきましょう。

高い性能の活用

Flare編、Tokyo Cabinet編にあるように、つまりGREE、mixiともに、 アクセス履歴といった数万qpsに達するデータを key-valueストアで管理しています。 それによって、RDBを用いた場合に比べて サーバの台数を数分の一以下で済ませています。 これによってサーバ管理の手間を抑えられたとのことです。 この場合、ユーザIDをキーとした問い合わせさえできれば充分なので、 key-valueストアで対応できます。 また、複数のキーにまたがって厳しく整合性が求められることもありません。

Amazon社は、自社開発の分散key-valueストアDynamoで、 ショッピングカートのデータを管理しています（2007年時点）。 一日あたり数千万の要求と300万以上のチェックアウトをさばいているとのことです [2]。 この場合も上述のアクセス履歴と同じ理由でkey-valueストアを活用できます。

key-valueストアの一番メジャーな使い方は、 RDBのキャッシュとしての活用ではないでしょうか。 例えばFacebook社では、800台以上のサーバで key-valueストアmemcachedを動作させて RDBへのアクセスを軽減しているとのことです（2008年12月時点） [3]。

Oracle社のkey-valueストアCoherenceは、まさにRDBのキャッシュが主用途です。 キャッシュに加えて、RDBが停止している間はCoherenceだけで要求に応え、 RDBが復帰すると変更内容を書き出すといった機能まで備えます。 RDBが数時間停止しても大丈夫だったという事例もあるそうです。

この用途では、 RDBを相手に読み書きしたデータをkey-valueストアにも格納しておきます。 RDBへの問い合わせの際は、まずkey-valueストアに問い合わせ、 もし求めるデータが載っていればそれを使います。 key-valueストアへの書き込みに使うキーは RDBへの問い合わせ条件から生成すればいい、というわけです。 どのくらい厳しく整合性が求められるかは、 応用ごとに検討する必要があります。

高スループットというより低遅延が活きた例として、こういう話をうかがいました。 金融機関からの開発提案依頼書（RFP）に 「応答10ミリ秒以内」と書かれていたそうです。 RDBを使った従来の設計ではこの条件を満たせなかったところ、 key-valueストアを活用することで達成できたとのことです。 RDBのキャッシュとして活用したと思われます。

大容量の活用

Bigtableは、Google社がペタバイト級の大量データを扱うために開発した データストアです。 ユーザは2次元以上の表にデータを格納するのですが、 Bigtable自体は実は、それを、キーと値の組としてHDDやSSDに書き込みます。 また、key-valueストアと同様に、 読み書きのatomic性を保証する範囲を細かく保ち、 サーバをまたがったatomic性の保証を避けています。 表と言っても、RDBのそれと比べると、 可能な問い合わせの形式にある程度の制限があります。

こういった、key-valueストアにも共通する性質や傾向を持つ データストアを指して「NoSQL」という言葉が作られました（コラム参照）。

一方で、純粋なkey-valueストアとして大容量を狙っているものに、 楽天発のROMA（ROMA編参照）や、 LinkedIn社発のVoldemortがあります。

今日時点では、数十台から数千台を要するような大規模データを扱いたい場合、 キーと値の組という単純な形式よりも、 2次元以上の表形式で管理しようという傾向があるようです。 同様のソフトウェアはBigtableやそのクローンであるHBase、Hypertableに加えて、 Yahoo! ResearchのPNUTS、 Facebook発のCassandraがあります。 また、ネットワーク越しで使うものに、 Amazon Web ServicesのAmazon SimpleDB、 Microsoft社Windows Azure Platformの一部であるWindows Azure Tableがあります。 この2つはクラウドと呼ばれるものの一部で、 両社が提供するPaaSの重要なパーツです。

key-valueストアとNoSQLのこれから

key-valueストアがこれだけ注目を集めたのは、 Facebook、YouTube、Twitterをはじめとする数々の著名ウェブ向けサービスで memcachedが使われていることが広く知られたからではないでしょうか。 2007年10月のSOSP'07国際会議にて発表された Amazon社のDynamoも大変注目を集めました。

これらはここ2,3年の話ですが、 memcachedは6年半前、2003年5月30日にはすでにver.1.0.0がリリースされています。 key-valueストアはまた、ウェブの裏側だけでなく、 エンタープライズ利用の歴史も長いです。 IBM社WebSphere eXtreme Scale、旧名ObjectGridのリリースは2005年7月、 Oracle社が買収する前のTangosol社Coherenceに至っては 2001年第4四半期、なんと8年も前にリリースされています。

その間、これら先駆者は経験を積み、 彼らの知識が様々な資料や講演を通じてある程度入手可能になってきました。 それを元に、今後いよいよ、 使いどころや採否の判断、ソフトウェアの選択ができる技術者が 増えていくことでしょう。 そうやってkey-valueストアもシステム構築の際の当たり前の部品になっていきます。

一方、Bigtableなど、「NoSQL」に分類される表形式データストアは、 クラウド上で提供されるPaaSにおいて 中心的なデータストアの座を占めています： Google社Google App EngineのApp Engine datastore (Bigtable)、 Amazon Web ServicesのAmazon SimpleDB、 Windows Azure PlatformのWindows Azure Table。

これらのデータストアはkey-valueストアと共通の性質を持ちます。 そのため、この種のデータストアを使ったソフトウェア開発、 つまりクラウド上のPaaSを対象とした開発では、 それなりの作法、方法論が求められます。 例えば、行や表をまたがって整合性を保つためには、 RDBであればトランザクションを行うことになりますが、 この種のデータストアではメッセージキューを活用することになるでしょう。

これはいわば、クラウド向けの設計・開発方法論であり、 今日まさに模索、整理がなされているところです。 今日時点では未来のスキルというわけです。 そのうち定番となる教科書が現れるのでしょうが、 自分の手で探求するのも面白いかもしれません。 エンジニアの前にはどこまでも未開の荒野が広がっています。

コラム：NoSQL

key-value…という言葉は、RDBとは違ったデータストア、 また、非RDB、脱RDBというムーブメントを指して 非常に大雑把に使われてきた感があります。 このムーブメントは、 人々の耳目を集めるウェブ向け大規模サービスやクラウドで起きたので、 それを象徴する言葉を皆が欲しがったのも無理ありません。 しかし今日では、まさにそれを指す「NoSQL」という言葉があります。

これはまさにムーブメントを表すとしか言いようのない造語で、 2009年に広まりました。 従来からのRDBとは異なるものを広く指します。 NoSQLデータストアというと、一般的な特徴として、 固定されたスキーマがないこと、 リレーショナルモデル・演算を捨てるかまたは重視しないこと、 eventual consistency、などがあります。 これらは必要条件ではなく、あくまで一般的に見られる傾向です。 NoSQLとみなされるデータストアとして、 key-valueストア全般、 GoogleのBigtableやそのクローンたち、 Yahoo!のPNUTS、 Facebook発のCassandra、 LinkedIn発のVoldemortなどがあります。

参考文献

Copyright (C) 2010 首藤 一幸