コンセプトから学ぶAmazon DynamoDB【ハッシュキーテーブル篇】

よく訓練されたアップル信者、都元です。最近DynamoDBづいております。DynamoDBについて全くご存知無い方は、まずは下記エントリーを読んで頂ければと思います。

Amazon RDSとの比較で学ぶDynamoDB

要するに、即時一貫性・操作の原子性・検索条件の自由度を犠牲にして、可用性と拡張性を手に入れたデータベースがDynamoDBであります。では具体的に、データの読み書きはどのように行うのでしょうか。

DynamoDBにおけるコンセプト

DynamoDBには主に「table」「item（項目）」「attribute（属性）」という3つの概念が現れます。それに従属する概念として「キー」「インデックス」が出てきます。まずはこの辺りを整理していきましょう。

tableというのはみなさん分かりやすいでしょう。概ねRDBで言うところのテーブルに相当し、itemの集合体です。itemについても、概ねRDBで言うところのrow（行）に相当し、attributeの集合体です。そしてattributeといのも、概ねRDBで言うところのcolumn（列）に相当します。

ただ、DynamoDBにおけるitemは、正規化を行う必要はなく、要するに1つのJSONオブジェクトの形で表現できるデータがitemに相当します。つまり、データとしては文字列でも配列でも、ネストされたオブジェクトでも構わない、ということです。下記にitemの一例を示します。これは製品情報（ProductCatalog）というtableに入っている2つのitemのイメージです。

{
"Id": 101,
"ProductName": "Book 101 Title",
"ISBN": "111-1111111111",
"Authors": [ "Author 1", "Author 2" ],
"Price": -2,
"Dimensions": "8.5 x 11.0 x 0.5",
"PageCount": 500,
"InPublication": true,
"ProductCategory": "Book"
}

{
"Id": 205,
"Title": "20-Bicycle 205",
"Description": "205 description",
"BicycleType": "Hybrid",
"Brand": "Brand-Company C" ,
"Price": 500,
"Gender": "B",
"Color": [ "Red", "Black" ],
"ProductCategory": "Bike"
}

この、IdとPriceとProductCategoryくらいしか共通点のない感じ。RDBのテーブル設計の考え方からはちょっとかけ離れた印象を受けると思いますが、NoSQLデータベースとは得てしてそういうものです。

key-valueによるデータ保存

さて、こんな感じでtableにitemが一杯入ってますよ、というところまではよろしいかと。ただし、データベースはデータの読み出しが出来なければ意味がありません。SQLの考え方では SELECT * FROM ProductCatalog WHERE BicycleType = 'Hybrid'; なんてことをすると思いますが、その手は使えません。前述の通り、DynamoDBでは一定の「検索条件の自由度」を諦めています。

結論から言えば、Idでしか探せません。「Idが205のアイテムをください（GetItem）」です。もしくは「探すんじゃなくて全部ください（Scan）」です。両極端。

多くのプログラミング言語には、Mapや連想配列等と呼ばれるデータ構造があると思います。これは、あるデータを「key」と「value」の組として記録し、「key」を与えることで「value」を取り出せる、というものですね。これと同じです。

var productCatalog = {
"101": {
"Id": 101,
"ProductName": "Book 101 Title",
// ...
},
"205": {
"Id": 205,
"Title": "20-Bicycle 205",
// ...
}
}

このようなJavaScriptのオブジェクトから、自転車のitemを取り出したかったらproductCatalog["205"] ですよね。一方、BicycleTypeがHybridのものを探したかったら、

Object.keys(productCatalog).forEach(function(key){
if (productCatalog[key]["BicycleType"] == "Hybrid") {
// ...
}
});

とか何とかするんでしょうねぇ。こんなイメージです。DynamoDBでは、テーブル作成時にあらかじめ「Idをキーとして利用しますよ」という宣言をし、その上でデータを保存します。その結果、そのキーを使ってデータを取り出せます。万が一、キー以外のもので検索したくなったら、全件ループScanで頑張るしか道がありません。

DynamoDBにおいて、キーはitem上に必須となります。つまり{"foo": "bar"}というデータはProductCatalogに保存できません。また、キーの値は重複できません。つまり{"Id": 1, "foo": "bar"}と{"Id": 1, "baz": "qux"}を同じテーブルに同時に格納できません。

つまり、全てのデータはキーによって一意に特定でき、キーによる検索は0個または1個のitemを返します。この辺りはRDBにおける主キーと非常に似ていますね。この操作を、DynamoDBではGetItemと呼びます。

ここに示したようなキーのことを「ハッシュキー」と呼びます。また、ハッシュキーを宣言したDynamoDBのtableを、本稿では便宜的に「ハッシュキーテーブル」と呼びます。

参考までに、DynamoDBのtableには「（ハッシュキーを宣言した）ハッシュキーテーブル」と「（ハッシュ＋レンジの複合キーを宣言した）複合キーテーブル」の2種類があります。しかし、複合キーテーブルについては次回以降に触れる予定で、今回はハッシュキーテーブルに話題を絞ります。ちなみに「ハッシュキーテーブル」「複合キーテーブル」の両者とも正式な用語ではなく、本稿独自で便宜的に名づけたものなので、利用にあたってはご注意ください。

ハッシュキーテーブルにおける拡張性担保

さて、ここからは一段レベルを上げた話をします。

DynamoDBでは高い拡張性（大量の読み書きリクエストに耐えうる）を持っています。具体的にはどのように性能を担保しているのでしょうか。

性能の担保は、Amazon RDSとの比較で学ぶDynamoDBで触れた通り、「シャーディング」作戦が有効であり、DynamoDBにおいても同様です。つまり、高い性能を必要とする場合は、複数のノードを用意し、データごとに受け持つノードを分けて対応します。このノードのことを、DynamoDBにおいては「パーティション」と呼びます。

もっと具体的な話に落としこんでみましょう。（ただし、DynamoDBは具体的な実装を公表していませんので、下記はイメージを助けるための想像でしかありませんのでご注意ください。）

例えば、ProductCatalogテーブルに必要な性能の確保のためには16個のパーティションが必要だと判断し、それを用意した場合を考えます。それぞれのパーティションに 0, 1, 2...9, a, b...f という番号を付けます。

この状態でDynamoDBが上記のBookのデータを書き込むリクエストを受けた場合、どのパーティションに書き込めばいいでしょうか。キーである"101"というデータにハッシュ関数SHA-1を適用すると、その結果はdbc0f004854457f59fb16ab863a3a1722cef553fです。この結果の1桁目はdなので、このデータはパーティションdに書こう。とまぁこんな感じです。（これはあくまでも理解のための描写で、実際はconsistent hashing法とか使ってるはずです。）

その後、DynamoDBが"101"のデータをくれという読み込みリクエストを受けた場合、どのパーティションを探しに行けばいいでしょうか。同じ計算をすることによって、このデータはパーティションdに格納されていることが分かるため、値を探しやすくなります。

上記の読み書き操作においては、パーティションd以外は負荷が全く掛かりません。また、"102"のパーティションはc、"103"は9、という感じで、すべてのデータが確率的には均一に全てのパーティションに分散するため、パーティション1つだけで受け持つ状況とくらべて16倍の性能が確保できることになります。

上記のように、もちろん同じパーティションに属するキー（104と106）もあります。ハッシュ関数によってパーティションを決定する要素となるキーだから「ハッシュキー」と呼ばれるんですね。この技術は、DynamoDBのパフォーマンス担保に大きな役割を果たしています。

DynamoDBにおける可用性担保と結果整合性

可用性の担保は、Amazon RDSとの比較で学ぶDynamoDBで触れた通り、「冗長化」作戦が有効であり、DynamoDBにおいても同様です。具体的には、DynamoDBはデータをコピーして3箇所に分散配置保持しています。仮に1つのノードが障害のため応答を返せなくなったとしても、残り2つのノードが応答できれば可用性の低下はありません。

ところで、DynamoDBには結果整合性という特性があります。つまり、データを更新した直後には一定の確率で古いデータが取得できてしまうことがあります。

この2つの特徴には高い関連性があります。こちらもイメージをつかむために、もっと具体的な話に落としこんでみましょう。（こちらも、DynamoDBは具体的な実装を公表していませんので、下記はイメージを助けるための想像でしかありませんのでご注意ください。）

まず、あるデータが3つのノードにおいて「foo」と記録されている状態をイメージします。

ここでDynamoDBが「このデータをbarに書き換えて」というリクエストを受け付けたとします。最終的に、DynamoDBの目標は、3つとも全てをbarに書き換えることです。が、DynamoDBは3つ中2つのデータが更新されたことを確認し次第、クライアントに「OK、できたよ」という成功のレスポンスを返してしまいます。

この時、クライアントがこのデータを読み出そうと試みると、ランダムに1つのノードを選択し、その値を返します。つまり1/3の確率で"foo"（古いデータ）を返すことがわかります。ただし、この状態は長く続かず、DynamoDBはすみやかに3つ目のノードにも新しいデータを伝播させようとします。

さて一方で、DynamoDBのデータ読み込みリクエストには「強い整合性の読み込み」というオプションがあります。DynamoDBは強い整合性の読み込みリクエストを受けると、ランダムに2つのノードを選択し、その値を比較します。値が一致した場合（ランダムに選んだ2つがnode-Bとnode-Cだった場合）はその値"bar"を返し、もし値が不一致だった場合は残りの1つも読み出して、多数決で多い方の値"bar"を返します。つまり、必ず"bar"（新しいデータ）を返すことがわかります。

これを考えると、強い整合性の読み込みは、結果整合性読み込みと比較して2倍〜それ以上のreadコストを掛けているわけで、スループットを2倍消費することにも合点が行きますね。

参考

Amazon - DynamoDB Strong consistent reads, Are they latest and how? - Stack Overflow