redis内部データ構造

5103 ワード
redis
redis内部データ構造とは、redisが自身の構築において、これらの特定の内部データ構造に基づいて行われることを意味する.
  • 単純動文字列:Simple Dynamic String
  • 両端チェーンテーブル
  • 辞書:Dictonary
  • ジャンプテーブル:skipList
  • 単純動的文字列
     
  • 用途
  • 文字列オブジェクト(StringObject)を実装する.
  • Redisプログラムの内部でchar*タイプの代替品として使用される.

  • データ構造
  • typedef char *sds;





struct sdshdr {



    // buf      

    int len;



    // buf       

    int free;



    //             

    char buf[];

};


  • まとめ
  • Redisの文字列は、C文字列(0で終わるchar*)ではなくsdsとして表されます.
  • C文字列を比較すると、sdsには次の特性があります.
  • は、長さ計算(strlen)を効率的に実行することができる.
  • は、追加操作(append)を効率的に実行することができる.
  • バイナリセキュリティ;

  • sdsは、追加操作を最適化します.追加操作の速度を速め、メモリの割り当て回数を低減します.その代価として、メモリを多く消費し、これらのメモリはアクティブに解放されません.



    •  
     
  • 両端チェーンテーブル
    デュアルエンドチェーンテーブルは汎用的なデータ構造として、Redis内部で非常に多く使用されています.Redisリスト構造の最下位実装の1つであり、同時に大量のRedisモジュールに使用され、Redisの他の機能を構築するために使用されます.
  • 用途
  • Redisを実装するリストタイプ
  • RPUSH、LPOPまたはLLENの操作対象の実装
    • .
  • Redis自身の機能の構築
  • 実装リストタイプに加えて、両端チェーンテーブルは多くのRedis内部モジュールに適用される:
    • .
  • トランザクションモジュールは、入力されたコマンドを両端チェーンテーブルを使用して順番に保存します.
  • サーバモジュールは、複数のクライアントを保存するために両端チェーンテーブルを使用する.
  • サブスクリプション/送信モジュールは、サブスクリプションモードの複数のクライアントを保存するために両端チェーンテーブルを使用する.
  • イベントモジュールは、時間イベント(time event)を保存するために両端チェーンテーブルを使用する.


  • データ構造
  • 図:

    • typedef struct listNode {



    //     

    struct listNode *prev;



    //     

    struct listNode *next;



    //  

    void *value;



} listNode;



typedef struct list {



    //     

    listNode *head;



    //     

    listNode *tail;



    //     

    unsigned long len;



    //     

    void *(*dup)(void *ptr);

    //     

    void (*free)(void *ptr);

    //     

    int (*match)(void *ptr, void *key);

} list
  • Redisは独自の両端チェーンテーブル構造を実現した.
  • 両端チェーンテーブルには主に2つの役割があります.
  • は、Redisリストタイプの下位実装の1つとして機能する.
  • は汎用データ構造として、他の機能モジュールによって使用される.

  • 両端チェーンテーブルとそのノードの性能特性は以下の通りである.
  • ノードは、前駆および後継ポインタを有し、前駆ノードおよび後継ノードへのアクセスの複雑さはO(1)であり、チェーンテーブルの反復は、ヘッダからヘッダ、およびヘッダからヘッダの2つの方向で行うことができる.
  • チェーンテーブルは、ヘッダとヘッダとヘッダを指すポインタを有するため、ヘッダとヘッダを処理する複雑さはO(1)である.
  • チェーンテーブルは記録ノード数の属性を有するので、O(1)複雑度内にチェーンテーブルのノード数(長さ)を返すことができる.


  • とにかく
    •  
  • 辞書

  • ジャンプテーブル
    • redis関連コマンド
    ubuntuにredisをインストールする