私は、2 つの質問に明確なリストで答えようとしています。
- Redis で使用される基礎データ構造は何ですか?
- それぞれのタイプの主な利点、欠点、使用例は何ですか?
Redis リストは実際にはリンク リストで実装されていると読みました。しかし、他のタイプについては、情報を掘り出すことができません。また、誰かがこの質問に偶然出くわし、さまざまなデータ構造を変更またはアクセスすることの長所と短所の概要を持っていない場合、特定のタイプを参照して使用する最適なタイミングの完全なリストも持っているでしょう。
具体的には、文字列、リスト、セット、zset、ハッシュなど、すべての型の概要を説明したいと思います。
ああ、これまでに、次のような記事を見てきました:
ベストアンサー1
質問にお答えしようと思いますが、最初は奇妙に思えるかもしれないことから始めましょう。Redis の内部に興味がないのであれば、データ型が内部でどのように実装されているかは気にするべきではありません。その理由は単純です。すべての Redis 操作の時間計算量はドキュメントに記載されており、操作セットと時間計算量がわかれば、あと必要なのはメモリ使用量に関するヒントだけです (データによって異なる最適化を多数行っているため、後者の数値を取得する最良の方法は、実際の簡単なテストをいくつか行うことです)。
しかし、ご質問いただいたので、すべての Redis データ型の基礎となる実装をここに示します。
- 文字列は C 動的文字列ライブラリを使用して実装されるため、追加操作での割り当てに (漸近的に言えば) コストがかかりません。この方法では、たとえば、2 次動作ではなく O(N) の追加が行われます。
- リストはリンクリストを使用して実装されます。
- セットとハッシュはハッシュ テーブルを使用して実装されます。
- ソートセットは次のように実装されますスキップリスト(バランスのとれた独特なタイプの木)。
しかし、リスト、セット、ソート済みセットの項目数や最大値のサイズが小さい場合は、別の、はるかにコンパクトなエンコーディングが使用されます。このエンコーディングはタイプによって異なりますが、コンパクトなデータ ブロブであるという特徴があり、多くの場合、すべての操作で O(N) スキャンが強制されます。この形式は小さなオブジェクトにのみ使用するため、これは問題になりません。小さな O(N) ブロブのスキャンはキャッシュを無視するため、実質的に非常に高速であり、要素が多すぎる場合は、エンコーディングは自動的にネイティブ エンコーディング (リンク リスト、ハッシュなど) に切り替わります。
しかし、あなたの質問は実際には内部に関することだけではなく、何を達成するためにどの型を使用するかということがポイントでした。
文字列
これはすべての型の基本型です。これは 4 つの型のうちの 1 つですが、複合型の基本型でもあります。List は文字列のリストであり、Set は文字列のセットであるなどです。
Redis 文字列は、HTML ページを保存したい場合だけでなく、すでにエンコードされたデータを変換したくない場合など、あらゆる明らかなシナリオに適しています。たとえば、JSON または MessagePack がある場合は、オブジェクトを文字列として保存できます。Redis 2.6 では、Lua スクリプトを使用して、この種のオブジェクトをサーバー側で操作することもできます。
文字列のもう一つの興味深い使い方はビットマップであり、一般的にはバイトのランダムアクセス配列です。Redisはバイトのランダムな範囲や単一ビットにアクセスするコマンドをエクスポートします。例えば、この優れたブログ記事: Redis を使用した高速で簡単なリアルタイム メトリック。
リスト
リストは、リストの両端、つまり末尾近くまたは先頭近くだけに触れる可能性が高い場合に適しています。リストは、ランダム アクセスが遅く、O(N) であるため、ページ付けにはあまり適していません。そのため、リストの適切な使用法は、単純なキューとスタック、または同じソースと宛先を持つ RPOPLPUSH を使用してループでアイテムを処理し、アイテムのリングを「回転」させることです。
リストは、通常は最上位または最下位の項目のみにアクセスするN 個の項目の上限付きコレクションを作成する場合や、N が小さい場合にも適しています。
セット
セットは順序付けされていないデータ コレクションなので、アイテムのコレクションがある場合や、コレクションの存在やサイズを非常に高速に確認する必要がある場合に便利です。セットのもう 1 つの優れた点は、ランダムな要素のピークまたはポップ (SRANDMEMBER コマンドと SPOP コマンド) をサポートしていることです。
セットは、関係を表すのにも適しています。たとえば、「ユーザー X の友達は誰か?」などです。しかし、この種のものに適した他のデータ構造は、後で説明するように、ソートされたセットです。
セットは、交差、結合などの複雑な操作をサポートしているため、データがあり、そのデータに対して変換を実行して何らかの出力を取得する場合に、Redis を「計算」方法で使用するのに適したデータ構造です。
小さなセットは非常に効率的な方法でエンコードされます。
ハッシュ
ハッシュは、フィールドと値で構成されるオブジェクトを表すのに最適なデータ構造です。ハッシュのフィールドは、HINCRBY を使用してアトミックに増分することもできます。ユーザー、ブログ投稿、またはその他の種類のアイテムなどのオブジェクトがある場合、 JSON などの独自のエンコードを使用しない場合は、ハッシュが適している可能性があります。
ただし、小さなハッシュは Redis によって非常に効率的にエンコードされるため、Redis に個々のフィールドを非常に高速にアトミックに GET、SET、または増分するように要求できることに留意してください。
ハッシュは、参照を使用してリンクされたデータ構造を表すためにも使用できます。たとえば、lamernews.com のコメントの実装を確認してください。
ソートされたセット
ソート セットは、リスト以外で、順序付けられた要素を維持するための唯一のデータ構造です。ソート セットを使用すると、さまざまな便利な機能を実現できます。たとえば、Web アプリケーションであらゆる種類のトップリストを作成できます。スコアによるトップ ユーザー、ページビューによるトップ 投稿、トップの何でも、ただし単一の Redis インスタンスは、1 秒あたり大量の挿入操作とトップ要素の取得操作をサポートします。
ソートされたセットは、通常のセットと同様に、関係を記述するために使用できますが、アイテムのリストをページ付けしたり、順序を記憶したりすることもできます。たとえば、ソートされたセットを使用してユーザー X の友達を記憶すると、承認された友情の順序で簡単に思い出すことができます。
ソートされたセットは優先キューに適しています。
ソートされたセットは、リストの中央からの範囲の挿入、削除、取得が常に高速である、より強力なリストのようなものです。ただし、より多くのメモリを使用し、O(log(N)) のデータ構造です。
結論
この投稿でいくらかの情報を提供できたと思いますが、lamernewsのソースコードをダウンロードする方がはるかに良いでしょう。http://github.com/antirez/lamernewsそしてそれがどのように機能するかを理解します。Lamer News では Redis の多くのデータ構造が使用されており、特定のタスクを解決するために何を使用すればよいかについての手がかりが数多くあります。
文法の間違いはごめんなさい。ここは真夜中なので、投稿を確認するには疲れすぎています ;)