入門 : Redis のデータ構造と概念

Redis は プレーン なキー・バリューストアではありません。実質的には、異なる種類の値をサポートする データ構造サーバー (data structures server) といえます。つまり、従来のキー・バリューストアでは、キーに文字列値を関連づけるのに対して、Redis では値はシンプルな文字列に限定されず、もっと複雑なデータ構造を格納することができます。以下のリストは、Redis でサポートされるすべてのデータ構造の一覧です。このチュートリアルで、それぞれについて説明していきいます:

これらのデータタイプがどのような働きをし、与えられた問題を解決するためにどう使えばよいのか、 command reference から把握するのはしばしば簡単ではありません。このドキュメントは、Redis のデータタイプとそれらがよく使われるパターンについての、速習コースです。

すべての例で、私たちは ‘redis-cli’ ユーティリティを使います。これは、Redis サーバーとやりとりするための、シンプルですが便利なコマンドライン・ユーティリティです。

Redis のキー

Redis のキーはバイナリ・セーフです。つまり、”foo” のような文字列から、JPEG ファイルのコンテンツまで、どのようなバイナリ列でもキーとして使うことができます。空文字列も有効なキーです。

キーに関するいくつかのルール:

  • 長すぎるキーを使うのは良くありません。たとえば、1024 バイトのキーはメモリ消費の面からだけでなく、データセットからのキーのルックアップ時、キーの比較に高いコストを要します。手元のタスクが、ある大きな値が存在するか、というマッチングである場合も、(SHA1 などで) ハッシングしておくことは、メモリ使用量と帯域の観点から良い考えです。

  • 短すぎるキーもしばしば良い考えではありません。 “user:1000:followers” と書けるところを、 “u1000flw” と書くのはあまり意味がありません。前者のほうがより読みやすく、追加で必要となるスペースは、キーオブジェクトそのものやバリューオブジェクトに比較するとささいなものです。しかし、短いキーのほうが少ないメモリを消費する、ということは否定できません。適切なバランスを見極めるのがあなたの仕事です。

  • スキーマにこだわってください。たとえば、”user:1000” のように “object-type:id” という形は良いアイディアです。”comment:1234:reply.to” や “coment:1234:reply-to” のように、ドットやダッシュはしばしば複数ワードのフィールドに使われます。

  • 許容される最大のキー長は 512 MB です。

Redis の Strings

Redis の String タイプは、キーに値を関連づけるための最もシンプルなタイプです。Memcached で使える唯一のデータタイプであり、Redis 初心者にとってもごく自然なものでしょう。

Redis のキーは文字列であるため、String タイプを値として使うとき、ある文字列を別の文字列にマッピングしている、ということになります。String データタイプは、HTML フラグメントやページのキャッシングなど、様々なユースケースで有用です。

‘redis-cli’ を使って、少し String タイプで遊んでみましょう(このチュートリアルのすべてのサンプルは、’redis-cli’ を使って実行します)。

> set mykey somevalue
OK
> get mykey
"somevalue"

As you can see using the SET and the GET commands are the way we set and retrieve a string value. Note that SET will replace any existing value stored already into the key, in case the key already exists, even if the key is associated with a non-string value. So SET performs an assignment.

値には(バイナリデータを含む)どんな種類の String も指定できます。たとえば、あるキーに jpeg 画像データも格納できます。値は、512 MB よりも大きくはできません。

SET コマンドには、追加の引数として指定される、興味深いオプションがあります。たとえば、キーがすでに存在する場合は SET が失敗するように指示したり、またその逆、すでに存在する場合のみ成功するように指示したりできます:

> set mykey newval nx
(nil)
> set mykey newval xx
OK

String は Redis の基本的な値ですが、興味深い操作も行えます。一例としてはアトミックなインクリメントがあります:

> set counter 100
OK
> incr counter
(integer) 101
> incr counter
(integer) 102
> incrby counter 50
(integer) 152

INCR コマンドは文字列値を整数としてパースし、1 だけインクリメントし、得られた値を新しい値としてセットします。その他、類似する INCRBY, DECR, DECRBY といったコマンドがあります。内部的には、これらは同じコマンドの振る舞いを少し変えたものです。

INCR がアトミックである、とは何を意味するのでしょう?これは複数のクライアントが、同じキーに対して INCR を発行しても、競合状態が発生しない、ということです。たとえば、クライアント1 が “10” を読み、同時にクライアント2 が “10” を読み、両方が 11 にインクリメントして、新しい値が 11 になる、ということは起こりません。最終的な値は常に 12 になります。read-increment-set 操作は、他のすべてのクライアントが同時にコマンドを実行していない間に実行されます。

There are a number of commands operating on strings. For example the GETSET command sets a key to a new value, returning the old value as result. You can use this command, for example, if you have a system that increments a Redis key using INCR every time your web site receives a new visit. You want to collect this information one time every hour, without losing a single increment. You can GETSET the key, assigning it the new value of “0” and reading the old value back.

ひとつのコマンドで複数の値をセットしたり、検索ができると、レイテンシを削減するのに役立ちます。このため、 MSETMGET コマンドがあります。

> mset a 10 b 20 c 30
OK
> mget a b c
1) "10"
2) "20"
3) "30"

MSET [訳注: MGET の間違い?]が呼ばれると、Redis は値の配列を返却します。

キー・スペースに対する変更と問合せ

特定のタイプに対してではなく、キー・スペースに対して作用するコマンドがあります。これらはどのようなタイプのキーにも使えます。

たとえば EXISTS コマンドは、指定されたキーがデータベース中に存在するかどうかに応じて 1 または 0 を返します。一方、 DEL コマンドは値が何であるかに関わらず、キーとそれに関連する値を削除します。

> set mykey hello
OK
> exists mykey
(integer) 1
> del mykey
(integer) 1
> exists mykey
(integer) 0

この例から、キーが削除された(存在した)か削除されなかった(そのような名前のキーが存在しなかった)かに応じて、 DEL が 1 または 0 のいずれかを返すことがわかります。

キー・スペースに関連するコマンドは多くありますが、上記の 2 つとともに TYPE コマンドと同様に最も重要なものです。これは特定のキーに格納されている値の種類を返します。

> set mykey x
OK
> type mykey
string
> del mykey
(integer) 1
> type mykey
none

Redis expires: 有効期間(time to live)が制限されたキー

より複雑なデータ構造に進む前に、 Redis expires と呼ばれる別の特徴についてふれておく必要があります。これはどのようなタイプの値にも作用します。ざっくり言うと、制限された有効期間(time to live), タイムアウトをキーに設定できます。期間が過ぎると、ちょうどユーザーが DEL コマンドを発行したのと全く同じように、キーは自動的に消去されます。

Redis expires について、即席の情報をいくつか:

  • 秒またはミリ秒の精度が指定できる

  • ただし、 expire 時の精度は常に 1 ミリ秒

  • expire に関する情報はレプリケーションおよびディスクに永続化され、Redis サーバーが停止している間も、実質的な時間が経過する(つまり、 Redis はキーが expire される日時を保存している)。

expire をセットするのは簡単です:

> set key some-value
OK
> expire key 5
(integer) 1
> get key (immediately)
"some-value"
> get key (after some time)
(nil)

2 つの GET コマンドの間で、キーは消えてなくなっています。2 回めの呼び出しの時点で、5 秒以上が経過しているためです。上記の例では、expire をセットするために EXPIRE を使いました(すでに expire が設定されているキーに対して、異なる expire をセットすることもできます。同様に PERSIST を使うと、expire を取り除き、キーを永久に永続化できます)。他の Redis コマンドを使って、expire を設定しながらキーを作成することも可能です。たとえば SET に次のようなオプションを指定します:

> set key 100 ex 10
OK
> ttl key
(integer) 9

この例では、キーに ‘100’ という String 値をセットしながら、10 秒の expire を指定しています。その後、キーの残り有効期間を確認するため TTL コマンドを呼んでいます。

ミリ秒の精度で expire をセットしたり確認するには、 PEXPIREPTTL コマンド、また SET のオプション一覧を参照してください。

Redis Lists

List データタイプを説明するために、ちょっとした理論から始めます。なぜなら、情報技術に関わる人たちの間で、しばしば List という語は正しくない使い方をされるためです。たとえば、 “Python Lists” はそれが示唆するもの(Linked List)ではなく、実質的に配列(Ruby では実際に配列と呼ばれているデータタイプと同じもの)です。

非常に一般的な観点からいうと、リストは整列した要素の並びにすぎません: 10,20,1,2,3 というのはリストです。しかし、配列を使って実装されたリストの性質は、 Linked List を使って実装されたリストのそれとは非常に異なります。

Redis の List は Linked List で実装されています。これが何を意味するかというと、たとえリスト中に数百万個の要素があったとしても、新しい要素をリストの先頭や末尾に追加する操作は 定数時間 で完了します。 LPUSH コマンドで、10 要素からなるリストの先頭に新しい要素を追加するのも、1000 万要素からなるリストの先頭に新しい要素を追加するのも、速度は同じです。

マイナス面は何でしょう?ある要素に インデックスによって アクセスするのは、配列で実装されたリストの場合、非常に高速です(定数時間のインデックスアクセス)。一方、linked list で実装されたリストの場合、それほど速くはありません(アクセスされる要素のインデックスに比例する操作が必要)。

Redis のリストが Linked List で実装されているのは、非常に長いリストに要素を高速に追加できることが、データベースシステムにおいてとても重要だからです。別の強力な利点として、少し後で見るように、Redis のリストは、長さが固定の場合には定数時間でアクセスできます。

もし、大きなコレクション中の中間部分へ高速にアクセスすることが重要なら、Sorted set と呼ばれる別のデータ構造が使えます。Sorted set については、後ほどこのチュートリアルで触れます。

Redis List のファースト・ステップ

LPUSH コマンドはリストの左(先頭)から新しい要素を追加します。一方、 RPUSH コマンドはリストの右(末尾)から要素を追加します。最後に、 LRANGE コマンドはリスト中のある範囲の要素群を抽出します。

> rpush mylist A
(integer) 1
> rpush mylist B
(integer) 2
> lpush mylist first
(integer) 3
> lrange mylist 0 -1
1) "first"
2) "A"
3) "B"

LRANGE は、返却される範囲の最初と最後を示す 2 つのインデックスをとることに注意してください。どちらのインデックスも負の値をとることができ、その場合は末尾からカウントします。すなわち、-1 は最後の要素、-2 は最後から 2 番目の要素、となります。

例からわかるように、 RPUSH はリストの右から要素を追加し、最後の LPUSH は左から要素を追加しています。

どちらのコマンドも、 可変個の引数をとるコマンド です。つまり、1 回の呼び出しでリストに複数の要素を push することができます:

> rpush mylist 1 2 3 4 5 "foo bar"
(integer) 9
> lrange mylist 0 -1
1) "first"
2) "A"
3) "B"
4) "1"
5) "2"
6) "3"
7) "4"
8) "5"
9) "foo bar"

Redis の List に対して定義されている重要な操作の一つに、 要素の pop があります。要素の pop 操作は、リスト中の要素を検索し、同時にリストからその要素を削除します。リストの両端から要素を push できたように、左から、または右から要素を pop することができます。

> rpush mylist a b c
(integer) 3
> rpop mylist
"c"
> rpop mylist
"b"
> rpop mylist
"a"

ここでは 3 つの要素を追加した後に 3 つの要素を pop しています。このコマンド列の最後では、リストは空になっていて pop する要素は残っていません。もしさらに要素を pop しようとすると、次のような結果を得ます:

> rpop mylist
(nil)

Redis はリスト中に要素がないことを示すシグナルとして、NULL 値を返します。

List のよくある使い方

リストは様々なタスクで有用ですが、以下に 2 つの代表的な使い方を挙げます:

  • あるソーシャルネットワークのユーザーの、最後に更新された投稿を覚えておく

  • consumer-producer パターンを用いたプロセス間通信。ここで producer はアイテムをリストに push し、consumer (通常 worker と呼ばれる) がアイテムを消費してアクションを実行する。

たとえば resquesidekiq といった人気のある Ruby ライブラリはバックグラウンドジョブを実行するために内部で Redis の List を使っています。

人気の高い Twitter ソーシャルネットワークでは、ユーザーの投稿を Redis に格納することで 最新のツイートを取得しています

よくあるユースケースについて、順を追って説明するため、あなたの写真共有ソーシャルネットワークで、ホームページに公開する最新の写真一覧の更新をスピードアップすることを想像してください。

  • ユーザーが新しい写真を投稿する度に、 LPUSH でリストにその ID を追加します。

  • ユーザーがホームページを訪問したとき、最新の 10 投稿を取得するために ‘LRANGE 0 9’ を利用します。

上限つきの List (Capped Lists)

多くのユースケースにおいて、 最新のアイテム だけを格納するためにリストを使いたい場合があります。それがなんであれ: ソーシャルネットワークのアップデート、ログ、その他もろもろ。

LTRIM コマンドを使って、最新の N アイテムだけを覚えておき、それよりも古い要素をすべて取り除くことで、リストを上限つきのコレクションとして使うことができます。

LTRIM コマンドは LRANGE と似ていますが、 指定された範囲の要素を表示する代わりに 、この範囲をリストの新しい値としてセットします。範囲に含まれない要素はすべて取り除かれます。

例を見ればよりわかりやすいでしょう:

> rpush mylist 1 2 3 4 5
(integer) 5
> ltrim mylist 0 2
OK
> lrange mylist 0 -1
1) "1"
2) "2"
3) "3"

この LTRIM コマンドは Redis に、インデックス 0 から 2 の範囲の要素だけを残し、その他の要素はすべて捨てるように指示しています。これは非常にシンプルですが有用な道具を提供します。List の push 操作と trim 操作を組み合わせることで、新しい要素を追加しながら余分な要素を取り除くことができます:

LPUSH mylist <some element>
LTRIM mylist 0 999

上記の組合せでは、最新の 1000 要素だけをリストに残しながら、新しい要素を追加しています。併せて LRANGE を使うことにより、古いデータを覚えておく必要なしに、上位のアイテムを取得することができます。

覚書: LRANGE は技術的に O(N) の計算量がかかります。ただし、先頭や末尾に近い、小さな範囲に対してアクセスする場合は定数時間の操作とみなせます。

リストに関するブロッキング操作

List は、キュー (より一般的に言うと、プロセス間通信を行うシステムに欠かせない要素) を実装するのに適した特別な機能を備えています: ブロッキング操作といわれるものです。

あるプロセスがリストにアイテムを push し、別のプロセスにそれを使って何らかの仕事をさせたい場合を考えます。これは普通の producer / consumer 構成で、以下のシンプルな方法で実装できます。

  • リストにアイテムを push するため、producer が LPUSH をコールする

  • アイテムを抽出 / 処理するため、consumer が RPOP をコールする

However it is possible that sometimes the list is empty and there is nothing to process, so RPOP just returns NULL. So a consumer is forced to wait some time and retry again with RPOP. This is called polling, and is not a good idea in this context because it has several drawbacks:

  1. Redis とクライアントの双方に、不要なコマンドを強いる(リストが空で、実際になすべき仕事がないとき、すべてのリクエストは単に NULL を返す)。

  2. あるワーカーは NULL を受け取った後、次のアイテムを処理するまでの遅延時間を追加し、しばらく待ちます。遅延を小さくすると、 RPOP 発行の間隔が短くなり、問題 1 よりもっと悪い状況になります: Redis に対するさらなる不要なコマンド呼び出し。

このため、Redis は BRPOPBLPOP と呼ばれるコマンドを実装しています。これらは RPOPLPOP の、リストが空の場合にブロックを可能にするバージョンです: リストに新しい要素が追加された場合、またはユーザーが指定したタイムアウトに達した場合のみ呼び出し元に返ります。

以下は BRPOP をワーカー内で呼ぶ例です:

> brpop tasks 5
1) "tasks"
2) "do_something"

これは次の意味をもちます: ” ‘tasks’ リストに要素が追加されるのを待て、しかし 5 秒経過しても要素が得られなければ戻れ”

タイムアウトを 0 に指定することで、要素が追加されるのを永久に待つことができます。また、同時に複数のリストを待ち、最初のリストが要素を受信したときに通知を受け取るために、ひとつのリストのみでなく複数のリストを指定できます。

BRPOP に関するいくつかの留意点があります。

  1. クライアントは、順序よくサーブされます: あるリストを待っている最初のクライアントが、他のクライアントにより push された最初の要素を受け取ります。以下同様です。

  2. RPOP と比べると、戻り値が異なります: 戻り値は 2 つの要素からなる配列で、キーの名前を含みます。 BRPOPBLPOP は複数のリストを待ってブロックできるためです。

  3. タイムアウトに達すると、NULL が返されます。

List とブロッキング操作について、さらに知っておくべきことがあります。以下のページを参照することを勧めます:

  • RPOPLPUSH を使うと、安全なキュー、および循環キューを構築できます。

  • また、このコマンドのブロッキング版として BRPOPLPUSH があります。

キーの自動生成、削除

ここまでの例で、要素の追加前に空のリストを作成したり、もう要素をもたなくなった空のリストの削除を行う必要はありませんでした。これは、リストが空になった場合はキーを削除し、また存在しないキーに対して要素を追加しようとした場合(たとえば LPUSH などで)は空のリストを作成するよう、Redis が気を配っているためです。

これはリストに限った話ではなく、複数の要素をから構成されるすべての Redis データタイプについて適用されます。すなわち、Sets, Sorted Sets, Hashes についても同様です。

基本的に、この振る舞いは 3 つのルールに集約されます:

  1. 集約データタイプに要素を追加するとき、もし対象のキーが存在しなければ、要素の追加前に空の集約データタイプが作成される。

  2. 集約データタイプから要素を削除したとき、もしその値が空になったら、キーは自動的に破棄される。

  3. 空のキーに対して LLEN のような read-only コマンドや、要素を削除するコマンドを発行すると、そのキーが、コマンドが期待する空の集約データタイプを保持しているかのように結果を生成する。

ルール 1 の例:

> del mylist
(integer) 1
> lpush mylist 1 2 3
(integer) 3

しかし、すでにキーが存在し、それが誤ったデータタイプをもつ場合は実行できません:

> set foo bar
OK
> lpush foo 1 2 3
(error) WRONGTYPE Operation against a key holding the wrong kind of value
> type foo
string

ルール 2 の例:

> lpush mylist 1 2 3
(integer) 3
> exists mylist
(integer) 1
> lpop mylist
"3"
> lpop mylist
"2"
> lpop mylist
"1"
> exists mylist
(integer) 0

要素がすべて pop された後は、キーはもはや存在しない。

ルール 3 の例:

> del mylist
(integer) 0
> llen mylist
(integer) 0
> lpop mylist
(nil)

Redis Hashes

Redis のハッシュは、あなたが期待する “hash” のイメージと一致するでしょう:

> hmset user:1000 username antirez birthyear 1977 verified 1
OK
> hget user:1000 username
"antirez"
> hget user:1000 birthyear
"1977"
> hgetall user:1000
1) "username"
2) "antirez"
3) "birthyear"
4) "1977"
5) "verified"
6) "1"

これはちょうど、フィールドと値のペアの集合です。ハッシュは オブジェクト を表現するのにも便利ですが、ひとつのハッシュに put できるフィールド数に実質上の制限はないため(メモリが許す限り)、アプリケーションの様々な用途で使うことができます。

The command HMSET sets multiple fields of the hash, while HGET retrieves a single field. HMGET is similar to HGET but returns an array of values:

> hmget user:1000 username birthyear no-such-field
1) "antirez"
2) "1977"
3) (nil)

HINCRBY のように、個々のフィールドに対して作用する操作もあります:

> hincrby user:1000 birthyear 10
(integer) 1987
> hincrby user:1000 birthyear 10
(integer) 1997

ハッシュコマンド一覧 も参照してください。

小さなハッシュ(少ない要素数、大きすぎない値)は、大変メモリ効率の良い特殊な方法でエンコードされる、ということにも留意する価値があります。

Redis Sets

Redis の Set は、順序をもたない文字列のコレクションです。 SADD コマンドはセットに新しい要素を追加します。その他、指定された要素がすでに存在するかチェックしたり、複数のセット間で共通集合や和集合や差集合をとったり、セットに対して多くの操作が可能です。

> sadd myset 1 2 3
(integer) 3
> smembers myset
1. 3
2. 1
3. 2

ここでは、3 つの要素をセットに追加し、その後ですべての要素を返すよう、Redis に指示しています。見てわかるとおり、これらは順序づけられていません。要素間の順序についてどのような約束事も存在しないため、Redis は呼び出しごとに任意の順で要素を返却します。

メンバーシップを検査するためのコマンドもあります。ある要素は[訳注: セット中に]存在するでしょうか?

> sismember myset 3
(integer) 1
> sismember myset 30
(integer) 0

“3” はセットのメンバーですが、”30” はメンバーではありません。

セットは、オブジェクト間の関係を表現するのに有用です。たとえば、タグを実装するのに、セットが簡易に使えます。

この問題をモデリングする簡単な方法は、タグを付与したいすべてのオブジェクトごとにセットを用意することです。セットには、オブジェクトに関連するタグの ID をもたせます。

ニュースにタグづけすることを考えましょう。ID 1000 をもつニュースに、タグ 1,2,5,77 を付与したい場合、これらのタグ ID とニュースを関連づける一つのセットを作れます。

> sadd news:1000:tags 1 2 5 77
(integer) 4

しばしば、逆の関係も保持しておきたいことがあります。つまり、あるタグが付与されたすべてのニュースの一覧です:

> sadd tag:1:news 1000
(integer) 1
> sadd tag:2:news 1000
(integer) 1
> sadd tag:5:news 1000
(integer) 1
> sadd tag:77:news 1000
(integer) 1

あるオブジェクトに付与されたすべてのタグを取得するのはとても簡単です:

> smembers news:1000:tags
1. 5
2. 1
3. 77
4. 2

注意: この例では、タグ ID とタグの名前をマッピングするためのデータ構造(たとえば Redis のハッシュ)が別にあることを想定しています。

その他に、Redis のコマンドを適切に使えば、少し難しい操作も簡単に実装できます。たとえば、タグ 1, 2, 10, 27 がすべて付与されたニュースの一覧を取得したいとしましょう。これは SINTER (複数のセットの共通集合をとるコマンド) で実現できます。使い方はこれだけです:

> sinter tag:1:news tag:2:news tag:10:news tag:27:news
... results here ...

利用できる操作は共通集合だけではありません。和集合、差集合、ランダムな要素の抽出、その他いろいろあります:

ひとつの要素を抽出するコマンドは SPOP と呼ばれるもので、ある種の問題をモデル化するのに便利です。たとえば、Web ベースのポーカーゲームを実装するのに、デッキをセットで表現したいとしましょう。(C)lubs, (D)iamonds, (H)earts, (S)pades のようにプレフィックスとして 1 文字を使います

>  sadd deck C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 CJ CQ CK
   D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 DJ DQ DK H1 H2 H3
   H4 H5 H6 H7 H8 H9 H10 HJ HQ HK S1 S2 S3 S4 S5 S6
   S7 S8 S9 S10 SJ SQ SK
   (integer) 52

各プレーヤーに 5 枚のカードを配ります。 SPOP コマンドはランダムな要素をひとつ取り除き、それをクライアントに返します。このケースに完璧にマッチする操作です。

しかし、これを直接デッキに適用してしまうと、ゲームの次のプレイ時に再度デッキにカードを投入する必要があります。これは望ましくはないでしょう。そのため、’deck’ キーに格納されているセットを、’game:1:deck’ キーにコピーすることができます。

これは SUNIONSTORE で実現できます。通常は複数のセットの和集合をとり、別のセットに結果を格納する操作ですが、ひとつのセットの和集合はそれ自身であるため、デッキのコピーをこのように書けます:

> sunionstore game:1:deck deck
(integer) 52

最初のプレーヤーに 5 枚のカードを配る準備が整いました:

> spop game:1:deck
"C6"
> spop game:1:deck
"CQ"
> spop game:1:deck
"D1"
> spop game:1:deck
"CJ"
> spop game:1:deck
"SJ"

ジャックの 1 ペア、いまいち...

セット中の要素の数を取得するコマンドを導入する、良いタイミングです。集合論ではしばしば 濃度(cardinality) と呼ばれるため、Redis コマンドは SCARD といいます。

> scard game:1:deck
(integer) 47

算数の問題: 52 - 5 = 47.

セットから要素を削除せずにランダムな要素を取得したい場合は、 SRANDMEMBER コマンドが適切です。これは、返却される要素に繰り返しがある場合、繰り返しなしの場合の、どちらにも対応できる機能を備えています。

Redis Sorted sets

ソート済みセットは、セットとハッシュの混合に似ています。セットのように、ソート済みセットはユニークで繰り返しのない文字列要素から構成されます。そのため、ソート済みセットはある種のセットとみなすことができます。

しかし一方、セットの要素は順序づけされていませんが、ソート済みセットのそれぞれの要素は、スコア と呼ばれる浮動小数点数と関連づけられています(ハッシュと似ている、というのは、各要素がある値にマッピングされるためです)。

さらに、ソート済みセット内の要素は 順序を意識します (リクエスト時に順序づけられるわけではなく、順番はソート済みセットに使われるデータ構造に特有のものです)。要素は以下のルールに従って並べられます:

  • もし A と B が異なるスコア値をもつなら、A.score > B.score ならば A > B となる。

  • もし A と B がまったく同じスコア値をもつなら、A の文字列が辞書順で B より大きいならば A > B となる。ソート済みセットの要素はユニークなので、A と B の文字列は等しくなることはない。

シンプルな例から始めましょう。何人かのハッカーの名前を、彼らの生年を “スコア” としてソート済みセットに追加します。

> zadd hackers 1940 "Alan Kay"
(integer) 1
> zadd hackers 1957 "Sophie Wilson"
(integer 1)
> zadd hackers 1953 "Richard Stallman"
(integer) 1
> zadd hackers 1949 "Anita Borg"
(integer) 1
> zadd hackers 1965 "Yukihiro Matsumoto"
(integer) 1
> zadd hackers 1914 "Hedy Lamarr"
(integer) 1
> zadd hackers 1916 "Claude Shannon"
(integer) 1
> zadd hackers 1969 "Linus Torvalds"
(integer) 1
> zadd hackers 1912 "Alan Turing"
(integer) 1

As you can see ZADD is similar to SADD, but takes one argument more (placed before the element to add itself), which is the score. ZADD is also variadic, so you are free to specify multiple score-value pairs, even if this is not used in the example above.

ソート済みセットを使うと、ハッカーのリストが生年でソートされた状態で返却されるのは自明です。なぜなら、実際のところ それらはすでにソート済みである ためです。

実装上の注意: ソート済みセットは、スキップリストとハッシュテーブルの両方を含む、 dual-ported なデータ構造で実装されています。そのため、ひとつの要素を追加するたびに Redis は O(log(N)) の計算量の操作を実行します。悪くありません。一方、ソート済みセットを取得するとき、Redis はどのような仕事もこなす必要がありません。すべては既にソート済みであるためです:

> zrange hackers 0 -1
1) "Alan Turing"
2) "Hedy Lamarr"
3) "Claude Shannon"
4) "Alan Kay"
5) "Anita Borg"
6) "Richard Stallman"
7) "Sophie Wilson"
8) "Yukihiro Matsumoto"
9) "Linus Torvalds"

注意: 0 と -1 は、インデックス 0 の要素から最後の要素まで、を意味します(-1 は LRANGE のときと同じはたらきをします)。

逆方向、若い順に並べたい場合はどうしたら良いでしょう? ZRANGE の代わりに ZREVRANGE が使えます。

> zrevrange hackers 0 -1
1) "Linus Torvalds"
2) "Yukihiro Matsumoto"
3) "Sophie Wilson"
4) "Richard Stallman"
5) "Anita Borg"
6) "Alan Kay"
7) "Claude Shannon"
8) "Hedy Lamarr"
9) "Alan Turing"

‘WITHSCORES’ 引数を使うと、スコアも一緒に返すことが可能です。

> zrange hackers 0 -1 withscores
1) "Alan Turing"
2) "1912"
3) "Hedy Lamarr"
4) "1914"
5) "Claude Shannon"
6) "1916"
7) "Alan Kay"
8) "1940"
9) "Anita Borg"
10) "1949"
11) "Richard Stallman"
12) "1953"
13) "Sophie Wilson"
14) "1957"
15) "Yukihiro Matsumoto"
16) "1965"
17) "Linus Torvalds"
18) "1969"

範囲操作

ソート済みセットは上記で説明したよりももっとパワフルで、範囲を扱う操作を実行できます。1950年以降に生まれた人、を取得してみましょう。 ZRANGEBYSCORE コマンドがこの仕事をします:

> zrangebyscore hackers -inf 1950
1) "Alan Turing"
2) "Hedy Lamarr"
3) "Claude Shannon"
4) "Alan Kay"
5) "Anita Borg"

ここでは Redis に、スコアが負の無限大から 1950 の範囲(両端を含む)にあるすべての要素を返すように問い合わせています。

特定の範囲にある要素を削除することもできます。ソート済みセット中の 1940 から 1960 の間に生まれたハッカーをすべて削除してみましょう。

> zremrangebyscore hackers 1940 1960
(integer) 4

ZREMRANGEBYSCORE はおそらく最適なコマンド名ではないですが、しかしとても役に立ち、戻り値としては削除された要素数を返します。

ソート済みセットに対して定義される、別の非常に便利な操作に、ランクを取得する操作があります。これはざっくり言って、順序づけられた要素の中で、ある要素が何番目にあるのかを問い合わせるものです。

> zrank hackers "Anita Borg"
(integer) 4

要素を降順に並べた場合のランクを取得するため、 ZREVRANK コマンドも使うことができます。

辞書順のスコア

Redis 2.8 以降のバージョンでは、すべての要素が同じスコア値で追加されていることを前提として、辞書順で範囲を取得する新しい機能が導入されました(要素は C の ‘memcmp’ 関数で比較されるため、衝突がなく、すべての Redis インスタンスが同じ出力を返すことが保証されます)。

辞書順での範囲操作を行う主なコマンドには ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX, そして ZLEXCOUNT があります。

たとえば、リストにもう一度、有名なハッカーを追加してみましょう。ただし今度は、すべての要素のスコアに 0 を指定します:

> zadd hackers 0 "Alan Kay" 0 "Sophie Wilson" 0 "Richard Stallman" 0
  "Anita Borg" 0 "Yukihiro Matsumoto" 0 "Hedy Lamarr" 0 "Claude Shannon"
  0 "Linus Torvalds" 0 "Alan Turing"

ソート済みセットの順序づけルールに従い、これらは辞書順でソートされます。

> zrange hackers 0 -1
1) "Alan Kay"
2) "Alan Turing"
3) "Anita Borg"
4) "Claude Shannon"
5) "Hedy Lamarr"
6) "Linus Torvalds"
7) "Richard Stallman"
8) "Sophie Wilson"
9) "Yukihiro Matsumoto"

ZRANGEBYLEX を使うと、辞書順での範囲問い合わせができます:

> zrangebylex hackers [B [P
1) "Claude Shannon"
2) "Hedy Lamarr"
3) "Linus Torvalds"

範囲は、端を含むことも含まないこともでき(最初の文字に依存する)、また、無限大や負の無限大はそれぞれ、’+’ と ‘-‘ という文字列で表現されます。より詳しい情報はドキュメントを参照してください。

これにより、ソート済みセットを一般的なインデックスとして使うことができるようになるため、この機能は重要です。たとえば、要素を 128 bit の符号なし整数によりインデックスしたい、としましょう。必要なのは、ソート済みセットに、同じスコア(たとえば 0)で、ただし 128 bit をビッグエンディアン方式で表現した 8 byte をプレフィックスに付与した要素を追加するだけです。数値はビッグエンディアン方式なので、辞書順(生のバイトオーダー)で並べたものは数値で並べたものと一致します。そのため、128 bit 空間で範囲を問合せることができ、その後でプレフィクスを除去することで求める要素が得られます。

この機能をより本格的なデモで見てみたいなら、 Redis autocomplete demo を見てください。

スコア更新: 順位表(leader boards)

次のトピックに移る前に、ソート済みセットについて、最後の覚書です。ソート済みセットのスコアはいつでも更新可能です。ソート済みセット中にすでに含まれている要素に対して ZADD を呼ぶと、そのスコア(と位置)が更新されます。計算量は高々 O(log(N)) のため、ソート済みセットは大量の更新があるケースに適しています。

この性質をもつため、よくあるユースケースのひとつは順位表(leader boards)です。典型的なアプリケーションに Facebook ゲームがあります。これは、ユーザーをスコアの高い順に並べる機能に加えて、ランキングを取得する操作を備えます。ユーザーに、上位 の N ユーザー、およびリーダーボードにおける自分の順位(「あなたはベストスコア順で 4932 位です」)を示すためです。

HyperLogLogs

HyperLogLog はユニークなものを数えるための確率的なデータ構造です(技術的には、集合の濃度を推定する際に言及されます)。通常、ユニークなアイテムを数え上げるためには、数えたいアイテム数に比例するメモリを必要とします。なぜなら、過去に数えた要素を、何度も数えてしまわないように覚えておく必要があるためです。メモリと精度のトレードオフを考慮して、いくつかのアルゴリズムが存在します: Redis の実装では、標準誤差を 1% 未満に抑えながらも、(アルゴリズムの魔法により)数え上げる対象の数に比例するメモリを必要とせず、必要なのは一定量のメモリだけです!最悪で 12k バイト、HyperLogLog (以降、単に HLL と呼びます) で考慮する要素数が非常に少ない場合は、もっと少なくて済みます。

Redis の HLL は、(技術的には異なるデータ構造ですが、) 文字列としてエンコードされるため、シリアライズするために GET を、アンシリアライズしてサーバーに書き戻すために SET が使えます。

概念的に、HLL API はセットを使って同じタスクを実行するときとよく似ています。セットに要素を追加するのには SADD を、セット中の要素数(SADD はすでに追加済みの要素を再追加しないため、これらはユニークです)を数えるのに SCARD を使います。

HLL のデータ構造が含むのは状態だけで要素自体を含まないため、実際には 要素の追加 を行うわけではありませんが、API は同様です:

  • 新しい要素が見つかる都度、それを PFADD で数え上げます。

  • PFADD追加された ユニークな要素数の現在の近似値を検索する都度、 PFCOUNT を使います。

    pfadd hll a b c d (integer) 1 pfcount hll (integer) 4

このデータ構造のひとつのユースケースは、ユーザーが検索フォームから実行した、日々のユニーククエリの数を数える、というものです。

Redis は HLL の和集合をとることもできます。より詳しい情報は ドキュメント を参照してください。

その他、特筆すべき機能

Redis API には他にも、このドキュメントでは詳しく掘り下げることができなかった重要な事項があります:

さらに学ぶ

このチュートリアルは、包括的なものではなく、API の基礎にすぎません。さらに学ぶため、 コマンドリファレンス を読んでください。

Thanks for reading, and have a good hacking with Redis!