(3分シリーズ)Redisにおける辞書の内部原理と使用方法を詳しく解く

3865 ワード
分散キャッシュ

前言


Redisでは、辞書は特に広く使われているデータ構造で、基本的に各機能モジュールで使用されています。
  • の主な用途は2つの側面です
  • は、データベースキー空間
    • として機能する.
  • は、Hashタイプキーの下位実装の1つである
    • である.

    目次

  • 辞書の使用例
  • 辞書の下位構造とソースコード解析
  • Rehashのプロセス
  • ビジネスシーンの実際の運用

    • 1.辞書の使用例


    1.1データベースキースペースの実現
  • データベース内のすべてのキー値ペア
    • をクリア
    redis> FLUSHDB
OK
  • データベース内のすべてのキー値ペアを取得する
    • redis> DBSIZE
(integer) 0
  • キー値対空間
    • を設定する.
    redis> set space dong
OK

redis> get space 
"dong"

    以上の3つは,辞書がRedisデータベース内でキー空間として用いられる例であり,データベースを操作するコマンドは,実際には辞書上で操作される.
    1.2 Hashタイプキーの下位実装
    Hashキーの下部には2つのデータ構造があり、1つは圧縮リストであり、1つは辞書のデフォルトは圧縮リストによって実現され、条件が満たされるまで変換が実現されない.
    条件:
  • ハッシュテーブルのキーまたは値の長さが64より大きい場合
  • ハッシュテーブルのノード数が512より大きい場合
    • 使用例:
    redis> HSET spacedong redis "redis"
(integer) 1

redis> HSET spacedong mysql "mysql"
(integer) 1

redis>HSET spacedong memcached "memcached"
(integer) 1

redis> HGETALL spacedong
 1)  "mysql"
 2)  "mysql"
 3)  "redis"
 4)  "redis"
 5)  "memcached"
 6)  "memcached"

    2.辞書の下位構造とソースコードの解析


    2.1辞書の構造
    /*
 *   
 *
 *            ，        rehash
 */
typedef struct dict {

    //           
    dictType *type;

    //            
    void *privdata;

    //    （2  ）
    dictht ht[2];

    //    rehash      ，   -1    rehash    
    int rehashidx;

    //               
    int iterators;

} dict;
  • ここでのハッシュテーブルには2つのポインタがあり、それぞれ2つのhashテーブルを指している.ht[0]は0番hashテーブルを指し、0番hashテーブルは使用中のテーブルであり、1番hashテーブルは0番hashテーブルがrehash中である場合に使用されるので、後でrehashの手順を詳しく説明します.

    • 2.2 Hashテーブルの構成
    /*
 *    
 */
typedef struct dictht {

    //          （   ，bucket）
    dictEntry **table;

    //        
    unsigned long size;

    //          ，       
    unsigned long sizemask;

    //           
    unsigned long used;

} dictht;
  • Hashテーブルのtableは1つの配列であり、1つのdictEntryからなり、図には長さ4の空のtableが示されている.

    • 2.3 DictEntryの構成
    typedef struct dictEntry {

    //  
    void *key;

    //  
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    //          ，    
    struct dictEntry *next;

} dictEntry;
  • keyに保存されているのはキーで、vに保存されているのはポインタかunit 64_かもしれません.tの整数、またはint 64_tの整数.nextポインタは次のhashテーブルノードを指し,チェーンテーブルの構造を以下の図に示す.

    • 2.3キー競合の解決
    hashテーブルにキー競合が発生した場合、Redisでの処理は、挿入されたこのキーのnextポインタを現在のキーに直接指向し、一般的にはこのノードのヘッダに直接挿入し、チェーンテーブルを形成することである.

    3.Rehashプロセス

  • は、まずHashテーブルである拡張または収縮が必要か否かを判断する
    • である.
  • は次にht[1]で拡張または収縮を行い、毎回の拡張または収縮は元のhashテーブルの量の倍または半分、例えば元のhashテーブルノードが8であり、拡張が完了すると16であり、収縮が完了すると4である.
  • 次いでRehashのプロセス
    • である.
    3.1以下のReHashの前提条件のいずれかを満たすと拡張Hashテーブルが行われる
  • サーバは現在、BGSAVEまたはBGREWRITEAOFコマンドを実行する際に、現在の負荷係数が1
    • 以上である.
  • サーバは現在、BGSAVEまたはBGREWRITAOFのコマンドを実行する際に、現在の負荷係数が5
    • 以上である.
    補足:
    サーバがBGSAVEまたはBGREWRITEAOFのコマンドを実行している場合、このときサーバはサブプロセスを作成してバックアップを完了し、オペレーティングシステムは一般的に書き込み時にコピーした(copr-on-write)を使用してサブプロセスの効率を向上させるため、サブプロセス実行中に負荷因子を拡大し、サブプロセスが存在する間に拡張テーブルを行うことを可能な限り回避し、不要なメモリ消費を低減することができる。

    負荷係数(load_factor)=既存のノード数収容可能なノード数
  • 収縮であれば負荷因子が0.1未満であれば
    • である.
    3.2 Rehashプロセス
  • まずHashテーブル拡張
    • を行う.
  • は、次に、Hashテーブルのテーブル0がテーブル1に移行するプロセス
    • である.
  • ReHashプロセス終了後

    • 4.実際の運用シーン分析

  • は、オブジェクトの情報
    • を記憶する.
    以上の辞書の特性から,辞書とHashMapの特性は差が少なく,配列とチェーンテーブルの組合せにも基づいていることが分かるので,一般的にキー値ペアを格納するために用いられる.しかし、実際の運用シーンでは、オブジェクトの情報を格納するためによく使用されます.例えば、name、age、weightなどのオブジェクトの属性は、この辞書に直接キー値として格納できる利点は、このオブジェクトの属性を使用する必要がある場合、このオブジェクトをすべてシーケンス化する必要はなく、特定のものを取り出すだけでよいが、従来のすべてのシーケンス化が必要である場合に比べてリソースを消費することである.
    参考書:Redisの設計と実現
    asp.NetとMVC 4のルーティング原理と過程【学習ノート】
    Redisパイプの理解