[解決済み】Redisに使用されている基礎的なデータ構造は何ですか？

質問

私は2つの質問に確定リストで答えようとしています。

1. Redisに使用されている基本的なデータ構造は何ですか？
2. また、それぞれのタイプの主なメリット/デメリット/ユースケースは何ですか？

Redisのリストは、実はリンクリストで実装されているんですね。しかし、他の型については、情報を掘り起こすことができません。また、もし誰かがこの質問につまずき、異なるデータ構造を変更したりアクセスしたりすることの長所と短所を高レベルでまとめていない場合、その人は完全に 特定の型を使うのに最適な時期 を参照することができます。

具体的には、string、list、set、zset、hashの全型の概要を知りたいです。

あ、今までにこの記事、他の記事も見てきました。

• http://redis.io/topics/data-types
• http://redis.io/topics/data-types-intro
• http://redis.io/topics/faq

解決方法は？

質問に答えていきますが、最初は奇妙に見えるかもしれないことから始めます：もしあなたがRedisの内部に興味がなければ 気にする必要はありません は、データ型が内部でどのように実装されているかということです。これは単純な理由です。Redisのすべての操作について、ドキュメントに時間の複雑さが記載されており、操作のセットと時間の複雑さがあれば、あとはメモリ使用量についての手がかりが必要なだけです（データによって異なる多くの最適化を行っているので、後者の数字を得るには、実際にいくつかのつまらないテストをしてみることが一番です）。

でも、せっかくなので、すべてのRedisデータ型の基本的な実装を紹介します。

• 文字列 は C の動的文字列ライブラリを用いて実装されており、追加操作の際に (漸近的に言って) 割り当てを行わないようにしています。こうすることで、例えばO(N)個の追加を、2次関数的な動作ではなく、行うことができます。
• リスト はリンクリストを使用して実装されています。
• セット内容 と ハッシュ はハッシュテーブルで実装されています。
• ソートされたセット が実装されています。 スキップリスト (バランスツリーの特殊なタイプ)。

しかし、リストや集合、ソートされた集合が、項目数や最大値の大きさが小さい場合、別のもっとコンパクトなエンコーディングが使われるのです。このエンコーディングは種類によって異なりますが、コンパクトなデータの塊でありながら、多くの場合、操作のたびにO(N)スキャンを強いられるという特徴をもっています。このフォーマットは小さなオブジェクトにしか使わないので、これは問題ではありません。小さなO(N)ブロブのスキャンは キャッシュを意識しない また、要素が多くなると自動的にネイティブなエンコーディング（リンクリスト、ハッシュなど）に切り替わります。

しかし、あなたの質問は、本当は内部だけの話ではなく、あなたの言いたいことは 何を達成するためにどの型を使うか？ .

文字列

これはすべての型の基本型です。4つの型のうちの1つですが、複合型の基本型でもあります。なぜなら、Listは文字列のリスト、Setは文字列のセット、などだからです。

Redisの文字列は、HTMLページを保存するような明白なシナリオだけでなく、すでにエンコードされたデータの変換を避けたい場合にも有効なアイデアです。例えば、JSONやMessagePackがある場合、オブジェクトを文字列として保存することができます。Redis 2.6では、Luaスクリプトを使って、この種のオブジェクトをサーバーサイドで操作することもできます。

文字列のもうひとつの興味深い使い方は、ビットマップや、一般的なバイトのランダムアクセス配列です。例えば、次のようにチェックします。 このブログの記事 Redisを使った高速で簡単なリアルタイムメトリクス .

リスト

リストは、リストの末尾や先頭に近い部分しか触らないような場合に有効です。ランダムアクセスはO(N)と遅いので、ページ付けにはあまり向いていません。 したがって、リストの良い使い方は、プレーンなキューやスタック、または、アイテムのリングを "rotate"するために同じソースとデスティネーションで RPOPLPUSH を使ったループ内のアイテムを処理することです。

リストは、N個のアイテムからなる上限付きのコレクションを作成したい場合にも適しています。 通常 のように、上位または下位の項目だけにアクセスする場合、あるいはNが小さい場合です。

セット内容

セットは順序のないデータコレクションであるため、アイテムのコレクションがあり、コレクションの存在やサイズを非常に高速にチェックすることが非常に重要である場合に適しています。また、セットにはランダムな要素を覗き見したり、飛び出したりする機能があります（SRANDMEMBERとSPOPコマンド）。

集合は、例えば「ユーザーXの友人は誰か？しかし、この種のものに適した他のデータ構造は、これから説明するように、ソートされたセットです。

セットは交差や結合などの複雑な操作をサポートしているので、データを持っていて、そのデータに変換を加えて何らかの出力を得たいときに、Redisをquot;computational"的に使うには良いデータ構造です。

小さな集合は非常に効率的な方法でエンコードされます。

ハッシュ

ハッシュは、フィールドと値からなるオブジェクトを表現するのに最適なデータ構造です。ハッシュのフィールドは、HINCRBYを使ってアトミックに増やすこともできる。ユーザーやブログの投稿などのオブジェクトがある場合、そのオブジェクトを表すのに最適なデータ構造です。 アイテム JSONのような独自のエンコーディングを使いたくない場合は、ハッシュを使用するのがよいでしょう。

しかし、小さなハッシュはRedisによって非常に効率的にエンコードされ、非常に高速な方法で個々のフィールドをアトミックにGET、SET、またはインクリメントするようRedisに求めることができることを覚えておいてください。

ハッシュは、参照を使用してリンクされたデータ構造を表現するために使用することもできます。例えば、lamernews.comのコメントの実装をチェックしてみてください。

ソートされたセット

ソートされたセットは リスト以外のデータ構造で、順序付き要素を保持するのは . ソートされた集合を使うと、さまざまなクールなことができます。例えば、あらゆる種類の トップなんとか のリストを作成します。しかし、単一のRedisインスタンスは、1秒間に何度も挿入とget-top-elements操作をサポートします。

ソートされたセットは、通常のセットと同様に、関係を記述するために使用することができますが、項目のリストをページ分割し、順序を記憶することも可能です。例えば、ユーザーXの友人をソートされたセットで覚えておくと、受け入れた友情の順番に簡単に思い出すことができます。

ソートされたセットは、優先キューに適しています。

ソートされた集合は、より強力なリストのようなもので、挿入、削除、またはリストの中央からの範囲の取得が常に高速に行われます。しかし、より多くのメモリを使用し、O(log(N))データ構造です。

まとめ

この記事でいくつかの情報を提供できたと思いますが、lamernewsのソースコードは、以下のサイトからダウンロードしたほうがはるかによいでしょう。 http://github.com/antirez/lamernews を読んで、その仕組みを理解しましょう。Lamer News内部ではRedisの多くのデータ構造が使われており、与えられたタスクを解決するために何を使うべきかの手がかりがたくさんあります。

文法の誤字脱字をお詫びします。）