Amazon DynamoDB での多様なクエリのための Z オーダーインデックス: パート 2

Amazon DynamoDB での多様なクエリのための Z オーダーインデックス: パート 2:

以前の AWS データベースに関するブログ記事で、複数の属性の範囲の境界を使用して Amazon DynamoDB のテーブルを効率的に照会できるように、データを並べ替えることができる Z オーダーインデックスを紹介しました。この記事では、インデックス用のスキーマを作成するプロセスについて説明します。スキーマに含める属性を決定する方法、インデックスのスキーマがクエリの効率に与える影響、さまざまなデータ型の操作方法について説明します。

この記事はパート 1 で説明した概念に基づいていますので、先へ進む前に少し時間をとってその内容を確認されることをお勧めします。

Z オーダーインデックスのスキーマの作成

前の記事で説明したように、インデックスに保存されている各レコードには Z アドレスが割り当てられます。Z アドレスとは固定長のバイナリ値であり、レコードの属性の既知のセットのビットをインターリーブすることで見つけることができます。次の図は、2つの属性 x と y による Z アドレスの計算を示しています。

Z アドレスは、DynamoDB テーブルのソートキー (またはローカルのセカンダリインデックスキー) として使用されます。ソートキーは、高速でバインドされたクエリを可能にするために保存されているテーブルのデータを並べ替えること、パーティション内のレコードを一意に識別することという 2 つの目的を果たします。パーティションおよびソートキーの詳細については、DynamoDB のドキュメントのプライマリキーを参照してください。

スキーマは、テーブルまたはインデックスに保存される情報の構造を記述します。Z オーダーインデックスの文脈では、スキーマには次のものが含まれます。

インデックス付けされる属性の名前 (上記の図の x と y)。
属性がエンコードされる順序 (y に続いて x)。
属性のそれぞれのデータ型 (x と y は符号なし整数、0 以上の整数) とそれらをバイナリで表現する方法。

新しいレコードをテーブルに挿入するか既存のレコードを更新するたびに、そのレコードの Z アドレスを計算する必要があります。同様に、クエリを作成するときは、範囲の境界を表す最小レコードと最大レコードの Z アドレスを計算する必要があります。Z アドレスを計算するたびに、同じ属性を同じ順序でエンコードし、それらの属性のデータ型を計算間で一貫して扱う必要があります。スキーマは、どの操作をどの順序で実行すべきかを指示します。

Z オーダーインデックスのスキーマは、DynamoDB テーブルのプライマリキーを定義する DynamoDB テーブル KeySchemaとは異なります。ここからは、「スキーマ」という言葉を使用する場合、DynamoDB テーブル KeySchema ではなく、Z インデックスのスキーマを意味することとします。

スキーマに含める属性の選択

従来の複合インデックスとは異なり、Z オーダーインデックスに対する検索では、それらが含む属性のサブセットに対してクエリを実行することになります。ただし、データのすべての属性を使用してインデックスを作成するべきではありません。

Z オーダーインデックスは、クエリによって提供される範囲と同じ程度に役立つだけです。クエリでインデックスの各属性に対して定義されている範囲が狭ければ、クエリは迅速に実行されます。ただし、前回の記事で示したように、いくつかの属性を制限しないとクエリのパフォーマンスは低下します。クエリに対する制限が少なくなるほど、インデックスの検索範囲が狭くならないからです。

このトレードオフについてより詳しく説明するために、その基礎となる数学を見てみましょう。同じインデックスに保存されているすべての Z アドレスは同じビット数を持つ必要があり、2 つのレコードが同じ Z アドレスを共有することはできません。つまり、アドレスの長さが 32 ビットのインデックスは、2³² (または 4,294,967,296) の異なるレコードを保持できるということです。インデックスに保存できる Z アドレスの範囲は、Z アドレス検索スペースと呼ばれます。

検索スペース内の各 Z アドレスには、レコードが含まれていてもいなくてもかまいません。クエリを実行するときは、まず、対象となるレコードが入力される Z アドレスの範囲を特定します。その後、レコードが存在するかどうかを調べるために、データベースに Z アドレスを参照するよう指示します。Z アドレスを参照するには時間がかかり、読み込みキャパシティーユニットを消費します。クエリを実行するために参照しなければならない Z アドレスが多いほど、そのパフォーマンスは悪化します。

特定のインデックスに対してクエリがどの程度うまく実行されるかを推定するには、次の数式を使用して、Z アドレス検索スペースのうち参照する必要がある部分を計算します。

参照する Z アドレスの数 = n^((a-b)/a)

この数式で:

n は、検索スペース内のアドレスの数です。
a は、インデックスに含まれる属性の数です。この数式では、インデックス内の各属性が同じビット数で表されると簡略化しています。
b は、クエリによって提供される正確な境界がある属性の数です。正確な境界は、可能な値の範囲 (たとえば、7 <= x <= 10) ではなく、次元を 1 つの可能な値 (たとえば、x = 7) に制限します。この数式で範囲を使用するには、その次元の検索スペースのうちどれだけがその境界によって除外されるかを示す小数を b に代入します。

この数式は、検索スペースのうち、レコードの一部ではなく、参照する必要がある部分を示していることに注意してください。これら 2 つの量が実際にどのくらい近いかは、テーブル内のアイテムが検索スペースに関してどれだけ均等に分布しているかによって異なります。

例として、a、b、c、d の 4 つの属性で構成されるインデックスを見てみましょう。それぞれの属性は符号なし整数であり、2 バイトで表されます。これは、Z アドレスがそれぞれ 8 バイトであり、64 ビットの検索スペースを作成することを意味します。

次のテーブルは、ますます広範になるサンプルクエリのために参照しなければならない Z アドレスの数を示しています。

クエリ	正確な境界がある次元	数式	簡素化	参照する Z アドレス
a = 5 AND b = 2 AND c = 8 AND d = 1	4	(2⁶⁴)^((4-4)/4)	2⁰	1
a = 5 AND b = 2 AND c = 8	3	(2⁶⁴)^((4-3)/4)	2¹⁶	65,535
a = 5 AND b = 2	2	(2⁶⁴)^((4-2)/4)	2³²	4,294,967,296
a = 5	1	(2⁶⁴)^((4-1)/4)	2⁴⁸	281,474,976,710,656
<無制限>	0	(2⁶⁴)^((4-0)/4)	2⁶⁴	18,446,744,073,709,551,616

上のテーブルから分かるように、ディメンションを制限しないままにすると、インデックスの有用性が急激に低下します。この影響を最小限に抑えるには、ほとんどのクエリで重みを保持する属性だけがインデックスに含まれているか確認する必要があります。これを行うには、データに対して実行する予定であるクエリのリストを作成します。このクエリのリストを確認しながら、以下の両方に該当する境界を持つ属性を特定します。

頻繁に定義されている。 属性の値がいくつかのクエリで自由に設定できることは問題ありません—その柔軟性は、Z オーダーインデックスが非常に汎用性がある理由の一部です。しかし、インデックスの属性がバインドされているよりも頻繁にアンバインドされていると、結果的に全体的なクエリのパフォーマンスが低下する可能性があります。
非常に選択的である。索引内の属性に配置された境界によって、検索スペースの大きな部分が除外されます。境界がほとんどの可能な結果を除外しない場合、属性を含める価値はありません。例として、レコードの 5% にだけ当てはまる Boolean 属性を考えてみましょう。これは、Users テーブルの isPlatinumMember フラグのようなものです。クエリがプラチナメンバーのみに適用される場合、この属性は非常に選択的です。ただし、プラチナ以外のメンバーを探しているのであれば、インデックスにこの 1 ビットの true-or-false 属性を指定すると、定義されている場合に可能性がある値の 5% しか排除されないのに、検索スペースは倍増します。

属性のバイナリ表現を選択する

どの属性をインデックスに含めるかを選択したので、それらの属性値をバイナリでどのように表現するかを決定する必要があります。残念ながら、これは選択したプログラミング言語で採用されている表現を使用するほど簡単ではありません。DynamoDB に Z アドレスでレコードをソートさせるには、既存の DynamoDB バイナリソートキーのソート動作で機能するように属性データをエンコードする必要があります。

辞書式順序

DynamoDB は 1,024 バイトのソートキーをサポートしており、それらのキーを辞書式順序でソートします。これは、データベースが各バイナリキーのバイトを左から右へ一度に 1 つずつ比較して、キーに共通してない最初のバイト値を探し出すことを意味します。データベースがバイト値の違いを検出すると、下位バイト値を持つキーがリストの最初に配置されます。たとえば、次の 2 つの 4 バイトのバイナリソートキーの比較を考えてみましょう。

	バイト 0	バイト 1	バイト 2	バイト 3
バイナリソートキー A	0111 1010	0110 0001	0110 0011	0110 1011
バイナリソートキー B	0111 1010	0110 0001	0110 1011	0110 1011

前のテーブルの 2 つのキーをソートする場合、DynamoDB は次の処理を行います。

キー A とキー B の両方のバイト 0 (それぞれ、A₀ と B₀) を参照し、そこに保存されているバイトを比較します。
A₀ と B₀は等しい (01111010 == 01111010) ので、DynamoDB はバイト 1 へ移動します。
A₁ と B₁は等しい (01100001 == 01100001) ので、DynamoDB はバイト 2 へ移動します。
A₂ は B₂ より小さい (01100011 < 01101011) ので、DynamoDB はデータベースでキー A のレコードをキー B のレコードの前に保存します。

DynamoDB で Z オーダーインデックスを使用する場合、テーブルのソートキーとして機能する属性は Z アドレスです。すべてが期待どおりに動作するためには、Z アドレスが意味のある辞書順であることが必要です。幸いなことに、Z アドレスの各次元を辞書順に並べ替えることができれば、Z アドレス自体も同様にできることが分かります。

これまでの例 (前の記事での例を含む) では、次元が符号なし整数である Z オーダーインデックスを見てきました。これは、符号なし整数を辞書編集で並べ替えることができ、数字で並べ替えたのと同じ順序付けを生成できるためです。このプロパティを使用すると、一般に理解されているバイナリ表現を使用して、Z オーダーインデックスがどのように機能するかを示すことができます。ただし、他のデータ型を Z オーダーインデックスに含めることもできますが、その多くはコンピュータープログラムで使用するバイナリレイアウトと同じものを使用して表現することはできません。これらのデータ型を扱えるいくつかの方法を見てみましょう。

符号付き整数

2 の補数表現は、符号付き整数の一般的なバイナリ表現です。符号なし整数とは異なり、符号付き整数のバイナリ表現のコレクションを辞書順に並べ替えると、数値順とは非常に異なる順序になります。次のテーブルに示すように、辞書順にソートすると、負の整数は正の整数の後に現れます。

10 進値	2 の補数符号付き整数
0	0000 0000
1	0000 0001
2	0000 0010
126	0111 1110
127	0111 1111
-128	1000 0000
-127	1000 0001
-126	1000 0010
-2	1111 1110
-1	1111 1111

この順序付けは問題です。符号付き整数のバイトを他のインデックス付き属性のバイトとインターリーブして、レコードの Z アドレスを生成できる必要があります。残念ながら、符号付き整数のバイナリ表現を辞書順に並び替えることができない場合、それらで作成した Z アドレスを辞書順に並び替えることはできません。

幸い、Z オーダーインデックスには、この順序付けの問題を回避できるプロパティがあります。各次元で選択するバイナリ表現が、エンコードされた値を表現する必要はありません。辞書順で並び替えたときにその次元の自然な順序を維持する必要があるだけです。この概念を掘り下げましょう。

値をバイナリでエンコードして、インターリーブされたビットを Z アドレスに追加する場合、このプロセスを元に戻せる必要はありません。たとえば、次のドキュメントをテーブルに保存しているとします。

{ 
  “timestamp”: 1469566800, 
  “celsius”: -5, 
  “latitude”: 40.749207, 
  “longitude”: -73.985174 
}

すべての属性を含む Z オーダーインデックスを作成することにしたので、z_address 属性をドキュメントに追加して、計算されたバイナリ値を保存します。

{ 
  “timestamp”: 1469566800, 
  “celsius”: -5, 
  “latitude”: 40.749207, 
  “longitude”: -73.985174, 
  “z_address”: … 
}

z_address 属性の役割は、DynamoDB がテーブルを順序付けることができるようにして、B ツリーのルックアップ操作を容易にすることです。このドキュメントをデータベースから取得した後は、z_address 属性の内容は使用しません。作成時に使用した元の次元の値は、その横にネイティブな形式で保存され、すぐに使用できるため、Z アドレスから次元の値を抽出する必要はありません。つまり、Z アドレスにインターリーブする値のバイナリ表現は、その辞書順の順序がデータ型の自然な順序と同じであれば、どんなものでも構わないことになります。

これをさらに明確にするために、符号付き整数をエンコードするタスクに戻ります。その辞書式の順序が数値の順序と同じではないため、整数の 2 の補数表現を直接使用することはできません。ただし、マッピング関数を使用して値の 2 の補数表現を取得し、最初のビットを反転することができます。次のテーブルに示すように、整数のバイナリ表現の最初のビットを反転し、結果の値を符号なし整数として再解釈すると、期待される順序が得られます。

10 進値	2 の補数符号付き整数	最初のビットを反転	結果の符号なし整数の 10 進値
0	0000 0000	1000 0000	128
1	0000 0001	1000 0001	129
2	0000 0010	1000 0010	130
126	0111 1110	1111 1110	254
127	0111 1111	1111 1111	255
-128	1000 0000	0000 0000	0
-127	1000 0001	0000 0001	1
-126	1000 0010	0000 0010	2
-2	1111 1110	0111 1110	126
-1	1111 1111	0111 1111	127

元の符号付きの値はマッピングで失われますが、順序プロパティが保持されていることだけが必要であるため問題はありません。もし必要な場合には、この Z アドレスに関連付けられたレコードでも、元の符号付きの値を引き続き使用できます。

浮動小数点値

バイナリ浮動小数点演算の IEEE 754 仕様では、次のように記述されています。

「同じフォーマットの 2 つの浮動小数点数が順序付けられている場合 (例えば x < y)、そのビットが符号絶対値の整数として再解釈されたときと同じ順序で順序付けられます。」

これは、ソート時に、浮動小数点値のバイナリ表現を符号絶対値整数であるかのように扱うことができることを意味します (以下の説明を参照)。符号絶対値整数を辞書順にソート可能なバイナリ表現にマッピングする方法を見つけることができれば、IEEE 754 準拠の浮動小数点値に対しても同じマッピングが機能します。

符号絶対値表現は、整数の最初のビットをその値が正であるか負であるかを示すために使用します。残りのビットは、数値の大きさを示すために使用されます。次のテーブルは、エンコードの例を示しています。

10 進値	絶対値符号付き整数
0	0000 0000
1	0000 0001
2	0000 0010
-2	1000 0010
-1	1000 0001

このエンコーディングで、利用可能な順序に近づけますが、負の数が正の数よりも大きく扱われます。また、絶対値が大きい負の数値は、絶対値が小さい負の数値よりも大きいものとして扱われています (たとえば、-2 は -1 より大きい値として扱われています)。以下を行うことでこれに対処することができます。

正の数のバイナリ表現の最初のビットを反転する。
負の数のバイナリ表現のすべてのビットを反転する。
結果の値を符号なし整数として解釈する。

10 進値	絶対値符号付き整数	ビットを反転	結果の符号なし 10 進値
0	0000 0000	1000 0000	128
1	0000 0001	1000 0001	129
2	0000 0010	1000 0010	130
-2	1000 0010	0111 1101	125
-1	1000 0001	0111 1110	126

ご覧ください！このマッピング関数をインデックス内の浮動小数点値に適用することにより、値の辞書順および数値順を揃えることができます。

UTF-8 テキスト

幸いにも、UTF-8 でエンコードされたテキストは、すでに辞書順でソート可能です。また、UTF-8 は ASCII エンコーディングと下位互換性があるため、ASCII 文字列とマルチバイトコードポイントのシーケンスの両方をそのままソートし、期待される順序にすることができます。ただし、Z アドレススキーマにテキスト属性を含める場合は、その属性のすべての値が同じバイト数である必要があります。つまり、任意の長さの文字列を取り、その文字列の辞書順を保持する固定長のバイトシーケンスを生成するマッピング関数が必要です。

英語の単語が必ず 1 つ含まれている Z オーダーインデックスのスキーマにテキスト属性を追加するとします。その属性を 4 バイトで表現することに決めました。UTF-8 を使用してエンコードすると、英語の単語の中には 4 バイトよりも短い単語もありますが、多くはより長いです。

各単語の 4 バイト値を生成するには、次の手順を実行します。

単語の長さが正確に 4 バイトの場合は、単語の UTF-8 表現をそのまま使用します。
単語の長さが 4 バイトより短い場合は、単語の UTF-8 表現の末尾にゼロの値を持つバイトを正確に 4 バイトになるまで追加します。
単語が 4 バイトより長い場合は、その UTF-8 表現の最初の 4 バイトだけを使用します。

このようにバイトを追加または削除すると、最終的に 4 バイトの値が有効な UTF-8 値にならなくなる可能性があります。それは大丈夫です—意味のある辞書式順序を持つバイナリ表現を生成することだけが必要です。

単語	UTF-8 バイト (16 進数)	変更された 4 バイト値
car	63 61 72	63 61 72 00
cart	63 61 72 74	63 61 72 74
cartographer	63 61 72 74 6f 67 72 61 70 68 65 72	63 61 72 74
carton	63 61 72 74 6f 6e	63 61 72 74

このアプローチでは、共通の接頭辞を持つ単語が同じ 4 バイト値になる可能性があることに注意してください。これは注意が必要です。それぞれの UTF-8 文字列を 4 バイトに切り詰めると、かなりの精度が失われます。インデックスに関しては、「cart」、「carton」、「cartographer」というエントリに違いはありません。

この 4 バイト値の衝突は、クエリの正確さには影響しませんが、インデックスの有用性を制限します。たとえば、最小値「candy」と最大値「cartographer」を使用して単語属性で範囲クエリを実行すると、インデックスはその範囲に辞書順で表示されるすべての単語を返します。ただし、インデックスは、最小の単語および最大の単語と同じ 4 バイト値を持つ単語も返します。つまり、インデックスの結果セットには、「candor」という単語 (クエリの最小値「candy」と同じ 4 バイト値を持つ単語) と「carton」という単語 (クエリの最大値「cartographer」と同じ 4 バイト値を持つ単語) が含まれます。

クエリの FilterExpression は、こうした誤った値が API によって返されるのを防ぎますが、このフィルタリングは値が既にデータベースから読み取られた後に行われます。クエリを実行しているクライアントは正しい結果を得ますが、データベースはこうした不正確な値にアクセスする読み込みキャパシティーユニットを消費してしまいます。

ほとんどの場合、これは大きな問題ではありません。保存されているテキストのプレフィックスが比較的均等に分布している場合は、値の衝突の数を管理する必要があります。ただし、そのインデックスに referrer_url 属性を含むテーブルがあるとします。その属性の値の大半は http://www などで始まり、広範な衝突につながります。この場合、インデックスはほとんど役に立たないでしょう—referrer_url の範囲がどれほど正確であっても、クエリごとに大量の読み込みキャパシティーユニットを消費します。

Unicode テキストには、Z オーダーインデックス付けに固有ではないいくつかの課題が他にもあることは言及しておく価値があります。同じテキストをさまざまな方法でエンコードすることができるので、テーブルの異なる場所に表示されるテキストと同じ文字列が表示される可能性があります。この概念の詳細については、Unicode 正規化形式を参照してください。

タイムスタンプ

さまざまなエンコーディングを使用してタイムスタンプを表現することができます。タイムスタンプをテキストとして書く場合、ISO 8601 の日付と時刻のインターチェンジ形式は、一貫した形式と精度を使用するときに辞書順に並び替え可能になるように設計されています。たとえば、常に YYYY-MM-DD の形式で日付を書く場合、値は常に辞書順に並び替え可能です。ただし、日付の一部が YYYY-MM-DD の形式で書かれ、他の日付が週の日付 (例、YYYY-Www-D) または序数の日付 (YYYY-DDD) を使用して書かれている場合、それらを並び替えようとすると予測できない結果になります。

エポックタイムスタンプ (1970 年 1 月 1 日からのミリ秒数) の使用も選択肢です。エポックタイムスタンプが符号なし整数として表現される場合、特別なマッピングロジックは必要ありません。

まとめ

この記事では、インデックスのスキーマを作成するプロセスについて検討しました。スキーマに含める属性を決定する方法、インデックスのスキーマがクエリのパフォーマンスに与える影響、さまざまなデータ型の操作方法について説明しました。特に、以下を示しました。

クエリが除外する検索スペース合計の割合を計算することにより、特定の Z オーダーインデックスでクエリがどれだけ効率的に実行されるかを簡単に推定できます。
Z オーダーインデックスに含める属性は、頻繁に定義され、同時に高度に選択的でなければなりません。
バイナリソートキーを使用する場合、DynamoDB はキーを符号なしバイトとして辞書順に並び替えます。
Z アドレスに含まれる各属性のバイナリ表現を辞書順に並び替えることができれば、Z アドレス自体も辞書順で並び替えることができます。
バイナリ表現の辞書順がデータ型の自然な順序と同じである限り、インデックスにはさまざまなデータ型を使用できます。

著者について

Zack Slayton は、Amazon のソフトウェア開発エンジニアです。 彼は、大規模なサービス指向アーキテクチャーに関連するラピッドデベロップメント、デカップリング、効率の課題に対処するために構築されたオープンソースの Ion データシリアライズ形式の仕事をしています。

このブログを検索

IT音痴オーバーフォーティーおやじのストック記事倉庫