Amazon DynamoDBのプライマリーキーの2つのタイプについて理解できたことをまとめました

AWS, Bash

はじめに

Amazon DynamoDBの構成要素について理解できたことをまとめました | ゲンゾウ用ポストイット で「テーブル」、「項目」、「属性」、「プライマリーキー」について整理しましたが、今回は「プライマリーキー」についてもう少しわかったことをまとめてみました。

プライマリーキーのタイプとデータの保存方法

プライマリーキーを構成する「属性」の数が1つか複数かで用途や考えないといけないことが異なるようです。

  • 単一「属性」で構成されるプライマリーキー : 「パーティションキー」 タイプ
  • 複数「属性」で構成されるプライマリーキー : 「パーティションキー+ソートキー」 タイプ

データの保存方法にも違いがあります。
両者はどう違うのでしょう?

「パーティションキー」タイプ

1つの属性で構成されたシンプルなプライマリーキーとなっています。

キーの値を「ハッシュ関数」という特殊な関数を使って変換します。
変換後の値で、「項目」を配置するデータ格納場所がきまります。
つまり「ハッシュ関数」とは、データ置き場を決めるための関数なのです。

「ハッシュ関数」を使ったデータ配置のメリットは、データの検索が高速であることです。
データが一箇所に集まってしまうと検索が遅くなってしまいます。データが整理されないまま入れ物にごった煮にされている状態を想像してください。
「ハッシュ関数」を使ってデータの配置場所を決められれば、データの検索が高速にできるわけです。

「ハッシュ関数」の結果はできる限りバラバラになるように考えられています。(このあたりはハッシュ関数の実装次第なのでおそらくそうなっているはずです。)
もしバラバラにならなかったとすると、特定のデータ配置場所にだけデータが集まってしまい、やはり検索が遅くなってしまうからです。

「パーティションキー+ソートキー」タイプ

2つの属性で構成されたプライマリーキーは、 属性のうち一つがパーティションキーとなり他方がソートキーとなります。
( 複合プライマリーキーと呼ばれたりもします。 )

パーティションキーのメリットはデータ配置場所が分散することでスキャンが高速になることでした。
プライマリーキーが2つの属性で構成された場合、当然のことながら1つの属性でしか構成できないパーティションキーの値は重複する可能性があります。

これではハッシュ関数を利用したデータ分散のメリットが薄れてしまいます。
ハッシュ関数で計算したデータ配置場所にデータが集まる傾向が高くなるためフルスキャンの問題と同様のことが発生します。

そこでソートキーです。
データがバラバラに並んでいる場合にはフルスキャンを行わなければデータを見つけることができません。
しかし、データがソートされていれば高速な探索アルゴリズムを使うことができます。
( 僕は高速な探索アルゴリズムを知っているわけじゃないのですが二分探索の速さぐらいはイメージできます。 )

図鑑で探しものをする場合を例に上げましょう。
分からない単語は一番後ろの索引を使って掲載ページを特定します。掲載ページが特定できたら、ページをペラペラ送りながら該当ページを探していきます。
該当ページを用意に探す事が出来るのも ページ番号が小さい値から大きな値に正しく並んでくれてるからこそです。

パーティションキーは1つしか設定できず、他方はソートキーになることにはメリットもあります。
ソートキーを構成する「属性」は範囲を指定して検索することができます。

※ユーザのアクセス履歴情報(未ソート)に対して12:00〜14:00のデータを検索する場合

※ユーザのアクセス履歴情報(ソート済)に対して12:00〜14:00のデータを検索する場合

「パーティションキー+ソートキー」タイプの注意点

「パーティション+ソートキー」タイプを利用場合には、注意しないといけないケースがあります。
ホットパーティション問題 と呼ばれる事象です。

パーティションキーの偏りにより発生する問題です。

以下の手書きのメモを例に取り上げます。

プライマリーキーは2つの属性から構成されているものとします。

パーティションキー ソートキー ハッシュ関数で算出されたデータ配置場所
001 x A
001 y A
001 z A
001 a A
001 b A
-------------------- ------------ ----------------------------------------
002 x B
-------------------- ------------ ----------------------------------------
003 y C

このとき、パーティションキー属性の値が 001 であるデータが非常に多いため、A のパーティションのみデータ量が増加することとなります。当然アクセス数もこのパーティションだけ多くなることでしょう。

特定のパーティションに対する負荷が多くなり、システム全体としてのボトルネックとなってしまいます。
なんとかしてデータを分割してやる必要があります。

いっそ「パーティションキー」と「ソートキー」をひっくり返してしまう

いっそ「パーティションキー」と「ソートキー」をひっくり返してしまうというのもありかと思います。

例えばロングテール商品を扱っているを扱っているショップのユーザ購入履歴情報があるとします。

ユーザID 商品ID
A ITEM001
A ITEM002
A ITEM003
A ITEM004
A ITEM005
A ITEM006
A ITEM007
---------- ---------
B ITEM008
B ITEM009
---------- ---------
C ITEM010

もし本当にこんなショップがあったら商品管理が大変でしょう(笑)。

「ユーザID」をパーティションキー、「商品ID」をソートキーとした場合にはホットパーティション問題が発生します。
逆にして「商品ID」をパーティションキー、「ユーザID」をソートキーとした場合にはホットパーティション問題が発生しません。

このようにカーディナリティ(値のユニーク度)が高い属性を使ってパーティショニングを行うことでデータ配置を分散できます。

HadoopやHBaseといった分散処理技術を使う場合にはデータ配置を「分散」させる方法で悩むことがありますが、これはその1つの方法です。

とはいえ、この方法を取ると、「ソートキー」による範囲指定検索ができなくなってしまいます。

ひとこと

DynamoDBを使う場合にも他のデータストレージを利用する場合と同様の「分散」配置に注意する必要があるようですね。

AWS, Bash