memcached と Redis 実装の比較を紹介する詳細なグラフィック コード

Memcached と redis は近年最もよく使われているキャッシュサーバーとして皆さんもよくご存じかと思います。 2年前に学生だったときに、彼らの主要なソースコードを読んだことがありますが、個人的な観点から簡単に実装方法を比較するためにメモを書いています。間違いがあればそれを使用してください。ご理解いただければ、修正を歓迎します。

この記事で使用されているアーキテクチャの写真のほとんどはインターネットから取得したものであり、記事内で指摘されているように、一部の写真は最新の実装とは異なります。

1. 概要

ソフトウェアのソース コードを読むには、まずソフトウェアが何に使用されているかを理解する必要があります。memcached と redis は何に使用されるのでしょうか。ご存知のとおり、データは通常データベースに配置されますが、データのクエリは比較的遅く、特にユーザーが多い場合、頻繁にクエリを実行すると時間がかかります。どうやってするの？すぐにクエリできるようにデータはどこに配置されますか?それは記憶にあるはずです。 Memcached と redis はデータをメモリに保存し、キーと値の方法でクエリを実行するため、効率が大幅に向上します。したがって、これらは一般に、よく使用されるデータをキャッシュするキャッシュ サーバーとして使用され、クエリが必要な場合はそこから直接取得されるため、データベース クエリの数が減り、クエリの効率が向上します。

2.サービス方法

memcached と redis はどのようにサービスを提供しますか?これらは独立したプロセスなので、必要に応じてデーモン プロセスに変えることができます。そのため、ユーザー プロセスが memcached サービスと redis サービスを使用したい場合は、プロセス間通信が必要になります。ユーザープロセス、memcached、redis が必ずしも同じマシン上にあるわけではないことを考慮すると、ネットワーク間通信をサポートする必要があります。したがって、memcached と redis 自体はネットワーク サーバーであり、ユーザー プロセスはそれらを使用してネットワーク経由でデータを送信します。最も単純で最も一般的に使用されるのは、tcp 接続を使用することです。さらに、memcached と redis は両方とも udp プロトコルをサポートします。また、ユーザー プロセスが memcached および redis と同じマシン上にある場合は、unix ドメイン ソケット通信も使用できます。

3. イベントモデル

まずはそれを実装する方法から見てみましょう。まず、イベント モデルを見てみましょう。

epoll が登場して以来、ほとんどすべてのネットワーク サーバーは選択とポーリングを放棄し、epoll に置き換えました。 Redis にも同じことが当てはまりますが、選択とポーリングのサポートも提供されます。どちらを使用するかを構成できますが、一般的には epoll が使用されます。さらに、BSD では、kqueue の使用もサポートされています。 Memcached は libevent をベースとしていますが、libevent の最下層も epoll を使用しているため、すべて epoll を使用していると考えられます。 epoll の特徴については、ネット上にたくさんの紹介記事がありますので、ここでは紹介しません。

これらはすべてイベント ループに epoll を使用しますが、redis はシングルスレッド サーバーです (redis はマルチスレッドでもありますが、メイン スレッドを除く他のスレッドはイベント ループを持たず、一部のバックグラウンド ストレージ作業のみを実行します)。のマルチスレッドです。 Redis のイベント モデルは非常に単純で、イベント ループが 1 つだけあり、これは単純なリアクターの実装です。ただし、redis イベント モデルには明るい点があります。epoll は fd 用であり、redis の fd はサーバーとクライアントを接続するソケットの fd のみであることがわかっています。処理するには、この fd に基づく必要があります。特定のクライアント情報を見つけるにはどうすればよいですか?通常の処理方法は、赤黒ツリーを使用して fd とクライアント情報を保存し、fd を介して検索することであり、効率は lgn です。ただし、redis は特殊で、redis クライアント数の上限が設定でき、同時に redis がオープンする fd の上限もわかりません。 (fd は閉じた後にのみ復元できます)。このように、redis は配列を使用し、配列の要素がクライアント情報になります。 、クライアント情報は fd を介して直接見つけることができます。検索効率は O(1) で、これにより、赤黒ツリーの実装も複雑になります (以前はネットワーク サーバーを作成するために C を使用していました。 fd と connect の間の対応関係を調べ、自分で赤黒ツリーを書きたくなかったので、STL でセットを使用しました。その結果、プロジェクトは C++ になりました。プロジェクトは g++ を使用してコンパイルされました。言わないの？）明らかに、この方法は接続数の上限が決まっているネットワーク サーバーにのみ使用でき、nginx のような独自の赤黒ツリーを書き込むだけの HTTP サーバーには適していません。

Memcached はマルチスレッドであり、マスター ワーカー メソッドを使用します。メイン スレッドはポートをリッスンして接続を確立し、それを各ワーカー スレッドに順番に割り当てます。各スレーブ スレッドにはイベント ループがあり、異なるクライアントにサービスを提供します。マスター スレッドとワーカー スレッドの間ではパイプライン通信が使用され、各ワーカー スレッドはパイプを作成し、書き込み端と読み取り端を保存し、読み取り可能なイベントをリッスンするために読み取り端をイベント ループに追加します。同時に、各スレーブ スレッドには準備完了の接続キューがあり、メイン スレッドが接続した後、接続されたアイテムをこのキューに入れ、スレッドのパイプの書き込み端に接続コマンドを書き込みます。イベント ループ 読み取り側の準備が整い、スレッドからコマンドを読み取り、コマンドを解析して接続があることを確認すると、独自の準備完了キューから接続を取得して処理します。マルチスレッドの利点は、マルチコアの利点を最大限に発揮できることですが、Memcached にはスレッド同期のためのさまざまなロックや条件変数があり、プログラムを書くのが少し面倒です。

4. メモリ割り当て

memcached と redis の中心的なタスクはメモリ内のデータを操作することであり、当然ながらメモリ管理が中心的な内容になります。

まず、メモリがどのように割り当てられるかを見てください。 Memcached には独自のメモリ プールがあり、事前に大きなメモリ ブロックを割り当ててから、そのメモリ プールからメモリを割り当てることで、メモリ割り当ての数を減らし、効率を向上させることができます。これは、ほとんどのネットワーク サーバーでも行われている方法です。ただし、各メモリ プールの管理方法は状況に応じて異なります。 Redis には独自のメモリ プールはありませんが、使用時に直接割り当てられます。つまり、メモリ管理はカーネルに任されており、カーネルはフェッチと解放のみを担当します (Redis はシングルスレッドであり、実行します)。独自のメモリ プールがありません。実装が単純すぎるように感じますか? それはデータベース モジュールに重点を置いているためです)。ただし、redis は glibc の malloc を置き換える tcmalloc の使用をサポートしています。前者は Google 製品であり、glibc の malloc よりも高速です。

Redis は独自のメモリ プールを持たないため、メモリの適用と解放の管理がはるかに簡単になり、malloc と free を直接実行できるため、非常に便利です。 Memcached はメモリ プールをサポートしているため、メモリ リクエストはメモリ プールから取得され、free もメモリ プールに返されるため、追加の管理操作が多く、実装が非常に面倒です。 memcached のスラブ機構の詳細を説明します。後で分析します。

5. データベースの実装

次に、中心となるコンテンツであるそれぞれのデータベースの実装を見てみましょう。

1. Memcached データベースの実装

Memcached はキーと値のみをサポートします。つまり、1 つの値に対応できるのは 1 つのキーのみです。そのデータはメモリ内のキーと値のペアにも保存され、スラブ メカニズムを使用します。

まず、memcached がデータをどのように保存するか、つまりキーと値のペアを保存するかを見てみましょう。次の図に示すように、各キーと値のペアは、関連する属性、キーと値の値を含む項目構造に格納されます。

アイテムにはキーと値のペアが格納されます。アイテムが多数ある場合、特定のアイテムを見つける方法が問題になります。そのため、memcached はアイテムをすばやく見つけるために使用されるハッシュ テーブルを維持します。ハッシュ テーブルは、キーの競合を解決するためにオープン チェーン方式 (redis と同じ) を適用します。 上の図に示すように、リンク リストのノードは、h_next を参照します。バケット内のリンクされたリストの次のノード。ハッシュテーブルは拡張（アイテム数がバケット数の1.5を超える場合の拡張）をサポートしています。primary_hashtableとold_hashtableがあり、拡張する場合は、old_hashtable = Primary_hashtableが設定されます。 Primary_hashtable は新しく適用されたハッシュ テーブル (バケットの数を 2 倍) に設定し、old_hashtable のデータを新しいハッシュ テーブルに順番に移動し、変数 Expand_bucket を使用してバケットの数を記録します。移動が完了したら、元の old_hashtable を解放します (Redis には 2 つのハッシュ テーブルもあり、これらも移動されますが、バックグラウンド スレッドによって完了するわけではなく、一度に 1 つのバケットを移動します)。展開操作はバックグラウンドの展開スレッドによって完了します。展開が必要な場合は、条件変数を使用して展開が完了すると、展開を待機している条件変数がブロックされます。このようにして、展開するときに、アイテムがprimary_hashtableまたはold_hashtableのいずれかで見つかる可能性があります。そのバケットの位置とexpand_bucketのサイズを比較して、それがどのテーブルにあるかを判断する必要があります。

アイテムはどこから割り当てられますか?スラブから。以下の図に示すように、memcached には多数のスラブクラスがあり、各スラブは実際にはトランクの集合であり、1 つのトランクに 1 つのアイテムが割り当てられます。スラブ内の幹のサイズは同じですが、新しいアイテムを申請する必要がある場合は、そのサイズに応じて幹のサイズが大きくなります。それよりも大きい。このようにして、異なるサイズのアイテムが異なるスラブに割り当てられ、異なるスラブクラスによって管理されます。 この欠点は、トランクがアイテムよりも大きい可能性があるため、一部のメモリが無駄になることです。図 2 に示すように、100B アイテムを割り当てる場合は 112 トランクを選択しますが、12B が無駄になります。メモリリソースの一部は使用されません。

上の図に示すように、slabclass はスラブを管理するための構造です。slabclass には slab_list があり、同じ slabclass 内の複数のスラブのトランク サイズはすべて同じです。スラブクラスには、解放された未割り当ての項目を保存するポインター スロットがあります (実際には空きメモリではなく、使用されなくなっただけです)。使用されていない項目がある場合、それらはスロットの先頭に置かれます。現在のスラブにアイテムを割り当てるときは、アイテムが未割り当てか解放されているかに関係なく、スロットに直接アクセスできます。

次に、各スラブクラスは、先頭配列と末尾配列を備えたリンク リストに対応し、それぞれリンク リストの先頭ノードと末尾ノードが格納されます。リンク リストのノードは、変更されたスラブクラスによって割り当てられたアイテムです。新しく割り当てられたアイテムは、リンク リストの後ろにあるアイテムは、長期間使用されていないことを意味します。スラブクラスのメモリが不十分で、期限切れのアイテムを削除する必要がある場合は、リンク リストの末尾から削除できます。はい、このリンク リストは LRU を実装するように設計されています。リンク リストのクエリは O(n) であるため、これだけに依存するのは十分ではありません。そのため、アイテムを見つけるときは、ハッシュ テーブルを使用します。これは、割り当てられたすべてのアイテムがすでにハッシュ テーブルに存在しているためです。ハッシュを使用して項目を検索すると、リンクされたリストに最近使用された項目の順序が保存されます。これは、lru の標準実装方法でもあります。

新しい項目を割り当てる必要があるたびに、スラブクラスに対応するリンク リストを検索し、項目の有効期限が切れているかどうかを確認します。有効期限が切れている場合は、期限切れの項目を直接新しい項目として使用します。有効期限が切れていない場合は、スラブからトランクを割り当てる必要があります。スラブが使い果たされている場合は、スラブクラスにスラブを追加する必要があります。

Memcached は有効期限、つまり有効期限の設定をサポートしていますが、データが内部で期限切れになっているかどうかを定期的にチェックすることはありません。代わりに、クライアント プロセスがデータを使用するときに、memcached が有効期限をチェックし、期限切れの場合はチェックします。直接エラーを返します。この利点は、有効期限を確認するために追加の CPU が必要ないことです。欠点は、期限切れのデータが長期間使用されず、解放されずにメモリを占有する可能性があることです。

Memcached はマルチスレッドであり、1 つのデータベースのみを維持するため、同じデータに対して複数のクライアント プロセスが動作する可能性があり、問題が発生する可能性があります。たとえば、A がデータを変更し、その後 B もデータを変更すると、A の操作は上書きされ、A は、A のタスク データの現在の状態が変更後の値であることを認識していないため、問題が発生する可能性があります。 。この問題を解決するために、memcached は CAS プロトコルを使用します。簡単に言えば、アイテムは更新される (データ値が変更される) たびに、データのバージョンをマークするために 64 ビットの unsigned int 値を保存します。が増加し、そのたびにデータが変更されるため、クライアントプロセスから送信されたバージョン番号とサーバー側のアイテムのバージョン番号が一致しているかどうかを比較する必要があります。操作を変更しないと、ダーティ データが要求されます。

上記は、memcached がキーと値のデータベースを実装する方法の概要です。

2. Redisデータベースの実装

まず、文字列の保存のみをサポートする memcached とは異なり、redis データベースは 5 つのデータ構造 (文字列、リスト、セット、ソート セット、およびハッシュ テーブル) をサポートするため、redis データベースはより強力です。たとえば、人の情報を保存するには、ハッシュ テーブルを使用し、その人の名前をキーとして使用し、次に super、年齢 24 という名前を付けることができます。キーと名前を通じて、またはキーと年齢を通じて、名前 super を取得できます。 24歳までは取得できます。このように、年齢だけを取得する必要がある場合、その人の情報全体を取得してから内部から年齢を探し、直接年齢を取得する必要がなく、効率的で便利です。

これらのデータ構造を実装するために、redis は以下に示すように抽象オブジェクト redis オブジェクトを定義します。各オブジェクトにはタイプがあり、文字列、リンク リスト、セット、順序付きセット、ハッシュ テーブルの合計 5 つのタイプがあります。 同時に、効率を向上させるために、redis は型ごとに複数の実装メソッドを用意し、特定のシナリオに応じて適切な実装メソッドを選択します。エンコーディングはオブジェクトの実装メソッドを表します。次に、オブジェクトの最後にアクセスされた時刻である LRU が記録されます。同時に、現在の時刻が Redis サーバーに記録されます (この時刻はサーバーが自動実行するときに一定の間隔でのみ更新されるため、おおよその値です)。メンテナンス)、これら 2 つの差を使用して、オブジェクトがアクセスされていない期間を計算できます。 さらに、redis オブジェクト内にも参照カウントがあり、これはオブジェクトを共有し、オブジェクトの削除時刻を決定するために使用されます。最後に、 void* ポインターを使用して、オブジェクトの実際のコンテンツを指します。公式には、抽象 redis オブジェクトを使用することで、データベース内のデータを操作する際に、オブジェクトの種類を区別する必要がある場合に、すべての redis オブジェクトを統一して使用できるようになり、より便利になります。そして、このオブジェクト指向アプローチの採用により、公式には Redis コードは C++ コードによく似ていますが、実際にはすべて C で書かれています。

りー

結局のところ、redis はサポートするデータ構造の数に関係なく、キーと値のデータベースであることに変わりはなく、最終的なストレージは依然としてキーと値のモードですが、値はリンク リスト、セット、ソート セット、ハッシュ テーブルなどにすることができます。 。 memcached と同様に、すべてのキーは文字列であり、文字列はセット、ソート セット、ハッシュ テーブルなどの特定のストレージにも使用されます。 C には既製の文字列がないため、redis の最初のタスクは sds (単純な動的文字列) という名前の文字列を実装することです。次のコードは、文字列の合計メモリ長を格納する非常に単純な構造です。 free はまだ使用可能なバイト数を意味し、buf は文字列の現在の長さを示します。

struct sdshdr {
    int len;
    int free;
    char buf[];
};

字符串解决了，所有的key都存成sds就行了，那么key和value怎么关联呢？key-value的格式在脚本语言中很好处理，直接使用字典即可，C没有字典，怎么办呢？自己写一个呗（redis十分热衷于造轮子）。看下面的代码，privdata存额外信息，用的很少，至少我们发现。 dictht是具体的哈希表，一个dict对应两张哈希表，这是为了扩容（包括rehashidx也是为了扩容）。dictType存储了哈希表的属性。redis还为dict实现了迭代器（所以说看起来像c++代码）。

哈希表的具体实现是和mc类似的做法，也是使用开链法来解决冲突，不过里面用到了一些小技巧。比如使用dictType存储函数指针，可以动态配置桶里面元素的操作方法。又比如dictht中保存的sizemask取size（桶的数量）-1，用它与key做&操作来代替取余运算，加快速度等等。总的来看，dict里面有两个哈希表，每个哈希表的桶里面存储dictEntry链表，dictEntry存储具体的key和value。

前面说过，一个dict对于两个dictht，是为了扩容（其实还有缩容）。正常的时候，dict只使用dictht[0]，当dict[0]中已有entry的数量与桶的数量达到一定的比例后，就会触发扩容和缩容操作，我们统称为rehash，这时，为dictht[1]申请rehash后的大小的内存，然后把dictht[0]里的数据往dictht[1]里面移动，并用rehashidx记录当前已经移动万的桶的数量，当所有桶都移完后，rehash完成，这时将dictht[1]变成dictht[0], 将原来的dictht[0]变成dictht[1]，并变为null即可。不同于memcached，这里不用开一个后台线程来做，而是就在event loop中完成，并且rehash不是一次性完成，而是分成多次，每次用户操作dict之前，redis移动一个桶的数据，直到rehash完成。这样就把移动分成多个小移动完成，把rehash的时间开销均分到用户每个操作上，这样避免了用户一个请求导致rehash的时候，需要等待很长时间，直到rehash完成才有返回的情况。不过在rehash期间，每个操作都变慢了点，而且用户还不知道redis在他的请求中间添加了移动数据的操作，感觉redis太贱了 :-D

typedef struct dict {
    dictType *type;    // 哈希表的相关属性
    void *privdata;    // 额外信息
    dictht ht[2];    // 两张哈希表，分主和副，用于扩容
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 记录当前数据迁移的位置，在扩容的时候用的
    int iterators; /* number of iterators currently running */    // 目前存在的迭代器的数量
} dict;

typedef struct dictht {
    dictEntry **table;  // dictEntry是item，多个item组成hash桶里面的链表，table则是多个链表头指针组成的数组的指针
    unsigned long size;    // 这个就是桶的数量
    // sizemask取size - 1, 然后一个数据来的时候，通过计算出的hashkey, 让hashkey & sizemask来确定它要放的桶的位置
    // 当size取2^n的时候，sizemask就是1...111，这样就和hashkey % size有一样的效果，但是使用&会快很多。这就是原因
    unsigned long sizemask;  
    unsigned long used;        // 已经数值的dictEntry数量
} dictht;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);     // hash的方法
    void *(*keyDup)(void *privdata, const void *key);    // key的复制方法
    void *(*valDup)(void *privdata, const void *obj);    // value的复制方法
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);    // key之间的比较
    void (*keyDestructor)(void *privdata, void *key);    // key的析构
    void (*valDestructor)(void *privdata, void *obj);    // value的析构
} dictType;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;
} dictEntry;

有了dict，数据库就好实现了。所有数据读存储在dict中，key存储成dictEntry中的key（string），用void* 指向一个redis object，它可以是5种类型中的任何一种。如下图，结构构造是这样，不过这个图已经过时了，有一些与redis3.0不符合的地方。

タイプ 5 の各オブジェクトには、少なくとも 2 つの基礎となる実装があります。文字列には REDIS_ENCODING_RAW、REDIS_ENCIDING_INT、REDIS_ENCODING_EMBSTR の 3 種類があります。リストには、通常の双方向リンク リストと圧縮リンク リストがあり、配列がリンク リスト、連続スペース、およびリンク リストに変換されることを意味します。文字列のサイズ情報を格納することでシミュレートされます。通常のリンク リストと比較してスペースを節約できますが、連続したスペースであるため、メモリ サイズを変更する際に再割り当てが必要になるという副作用があります。文字列のバイト サイズが保存されるため、継続的な更新が発生する可能性があります (具体的な実装の詳細はコードを参照してください)。 Set には dict と intset (すべての整数を格納するために使用) があり、sorted set にはスキップリストと ziplist があり、ハッシュテーブルの実装には圧縮リスト、dict、ziplist があります。 Skiplist はスキップ リストであり、効率は赤黒ツリーに近いですが、実装が赤黒ツリーよりも簡単であるため、採用されています (奇妙なことに、ここでは車輪の再発明がありません。このホイールは少し難しいですか？）。ハッシュ テーブルは dict を使用して実装できます。 dict では、各辞書のキーにはキー (ハッシュ テーブル内のキーと値のペアのキー) が格納され、値には値が格納されます。 セット内の辞書に関しては、各辞書内のキーにはセット内の特定の要素の値が格納され、その値は null です。画像の zset (順序付きセット) は間違っています。zset は Skiplist と ziplist を使用して実装されています。最初に、skiplist はわかりやすいので、赤黒の木の代わりとして考えてください。並べ替えることもできます。 ziplist を使用して zset を保存するにはどうすればよいですか?まず、zset では、セット内の各要素にスコアがあり、ソートに使用されます。したがって、ziplist では、スコアに従って、要素が最初に保存され、次にそのスコア、次の要素、そしてスコアの順に保存されます。これは連続ストレージであるため、挿入または削除するときにメモリを再割り当てする必要があります。したがって、要素の数が特定の数を超えるか、要素の文字数が特定の数を超えると、redis は zset を実装するためにスキップリストを使用することを選択します (現在 ziplist が使用されている場合は、ziplist 内のデータが取り出され、新しい Skiplist に保存され、ziplist を削除して変更します。これが基本的な変換であり、他の種類の Redis オブジェクトも変換できます。 さらに、ziplist はハッシュテーブルをどのように実装するのでしょうか?実際、これは非常に簡単で、キーを保存し、値を保存し、次にキーを保存し、次に値を保存するだけです。 zset 実装と同様にシーケンシャルに格納されるため、要素が一定数を超えるか、要素の文字数が一定数を超えると、ハッシュテーブルに変換されて実装されます。基盤となるさまざまな実装方法を変換でき、redis が状況に応じて最適な実装方法を選択できることも、同様のオブジェクト指向の実装方​​法を使用する利点です。

Skiplist を使用して zset を実装する場合、同じキーと値のペアを格納する dict が実際に使用されることに注意してください。なぜ？ Skiplist の検索は lgn (n になる可能性があります) のみであり、dict は O(1) である可能性があるため、検索を高速化するために dict が使用されます。無駄にならないように。さらに、ziplist を使用して zset を実装する場合、検索を高速化するために dict を使用しないのはなぜでしょうか。 ziplist はサポートする要素の数が少ないため (数が多い場合はスキップリストに変換されます)、シーケンシャル トラバースも高速であるため、dict は必要ありません。

この観点から見ると、上記の dict、dictType、dictHt、dictEntry、および redis オブジェクトはすべて非常によく考えられており、オブジェクト指向のカラーを備えた柔軟で効率的なデータベースを実装しています。 Redis データベースの設計は依然として非常に強力であると言わざるを得ません。

memcached とは異なり、redis には複数のデータベースがあり、デフォルトでは 0 ～ 15 の番号が付けられた 16 個のデータベースがあります。どのデータベースを使用するかは顧客が選択でき、デフォルトではデータベース No.0 が使用されます。 異なるデータベース データは共有されません。つまり、同じキーが異なるデータベースに存在できますが、同じデータベース内ではキーは一意である必要があります。

Redis は有効期限の設定もサポートしています。上記の Redis オブジェクトを見てみましょう。有効期限を保存するフィールドはありません。では、Redis はデータの有効期限をどのように記録するのでしょうか。 Redis は各データベースに別の dict を追加します。この dict は、expired dict と呼ばれます。この dict エントリのキーは 1 組のキーであり、値は 64 ビット int である Redis オブジェクトです。この int は有効期限です。 。このようにして、キーの有効期限が切れているかどうかを判断するときは、有効期限辞書でキーを見つけ、有効期限を取り出して、現在の時刻と比較することができます。なぜこれを行うのでしょうか? すべてのキーに有効期限が設定されているわけではないため、有効期限が設定されていないキーの場合、有効期限を保存するとスペースが無駄になります。代わりに、期限切れ辞書を使用して個別に保存すると、必要に応じてメモリを柔軟に使用できます。検出されたキーの有効期限が切れると、期限切れ辞書から削除されます)。

redis的expire 机制是怎样的呢？ 与memcahed类似，redis也是惰性删除，即要用到数据时，先检查key是否过期，过期则删除，然后返回错误。单纯的靠惰性删除，上面说过可能会导致内存浪费，所以redis也有补充方案，redis里面有个定时执行的函数，叫servercron，它是维护服务器的函数，在它里面，会对过期数据进行删除，注意不是全删，而是在一定的时间内，对每个数据库的expire dict里面的数据随机选取出来，如果过期，则删除，否则再选，直到规定的时间到。即随机选取过期的数据删除，这个操作的时间分两种，一种较长，一种较短，一般执行短时间的删除，每隔一定的时间，执行一次长时间的删除。这样可以有效的缓解光采用惰性删除而导致的内存浪费问题。

以上就是redis的数据的实现，与memcached不同，redis还支持数据持久化，这个下面介绍。

4.redis数据库持久化

redis和memcached的最大不同，就是redis支持数据持久化，这也是很多人选择使用redis而不是memcached的最大原因。 redis的持久化，分为两种策略，用户可以配置使用不同的策略。

4.1 RDB持久化

用户执行save或者bgsave的时候，就会触发RDB持久化操作。RDB持久化操作的核心思想就是把数据库原封不动的保存在文件里。

那如何存储呢？如下图， 首先存储一个REDIS字符串，起到验证的作用，表示是RDB文件，然后保存redis的版本信息，然后是具体的数据库，然后存储结束符EOF，最后用检验和。关键就是databases，看它的名字也知道，它存储了多个数据库，数据库按照编号顺序存储，0号数据库存储完了，才轮到1，然后是2, 一直到最后一个数据库。

每一个数据库存储方式如下，首先一个1字节的常量SELECTDB，表示切换db了，然后下一个接上数据库的编号，它的长度是可变的，然后接下来就是具体的key-value对的数据了。

int rdbSaveKeyValuePair(rio *rdb, robj *key, robj *val,
                        long long expiretime, long long now)
{
    /* Save the expire time */
    if (expiretime != -1) {
        /* If this key is already expired skip it */
        if (expiretime < now) return 0;
        if (rdbSaveType(rdb,REDIS_RDB_OPCODE_EXPIRETIME_MS) == -1) return -1;
        if (rdbSaveMillisecondTime(rdb,expiretime) == -1) return -1;
    }

    /* Save type, key, value */
    if (rdbSaveObjectType(rdb,val) == -1) return -1;
    if (rdbSaveStringObject(rdb,key) == -1) return -1;
    if (rdbSaveObject(rdb,val) == -1) return -1;
    return 1;
}

由上面的代码也可以看出，存储的时候，先检查expire time，如果已经过期，不存就行了，否则，则将expire time存下来，注意，及时是存储expire time，也是先存储它的类型为REDIS_RDB_OPCODE_EXPIRETIME_MS，然后再存储具体过期时间。接下来存储真正的key-value对，首先存储value的类型，然后存储key（它按照字符串存储），然后存储value，如下图。

在rdbsaveobject中，会根据val的不同类型，按照不同的方式存储，不过从根本上来看，最终都是转换成字符串存储，比如val是一个linklist，那么先存储整个list的字节数，然后遍历这个list，把数据取出来，依次按照string写入文件。对于hash table，也是先计算字节数，然后依次取出hash table中的dictEntry，按照string的方式存储它的key和value，然后存储下一个dictEntry。 总之，RDB的存储方式，对一个key-value对，会先存储expire time（如果有的话），然后是value的类型，然后存储key（字符串方式），然后根据value的类型和底层实现方式，将value转换成字符串存储。这里面为了实现数据压缩，以及能够根据文件恢复数据，redis使用了很多编码的技巧，有些我也没太看懂，不过关键还是要理解思想，不要在意这些细节。

保存了RDB文件，当redis再启动的时候，就根据RDB文件来恢复数据库。由于以及在RDB文件中保存了数据库的号码，以及它包含的key-value对，以及每个key-value对中value的具体类型，实现方式，和数据，redis只要顺序读取文件，然后恢复object即可。由于保存了expire time，发现当前的时间已经比expire time大了，即数据已经超时了，则不恢复这个key-value对即可。

RDB ファイルの保存は大規模なプロジェクトであるため、redis はバックグラウンド保存メカニズムも提供します。つまり、bgsave が実行されると、redis は子プロセスをフォークして保存された作業を子プロセスに実行させますが、親プロセスは redis の通常のデータベース サービスを提供し続けます。子プロセスは親プロセスのアドレス空間をコピーするため、つまり、親プロセスがフォークしたときに子プロセスがデータベースを所有するため、子プロセスは保存操作を実行し、親プロセスから継承したデータベースを一時ファイルに書き込みます。子プロセスのコピー中に、redis はデータベースの変更 (ダーティ) の数を記録します。子プロセスが完了すると、SIGUSR1 シグナルが親プロセスに送信され、親プロセスがこのシグナルを受け取ると、子プロセスがコピーを完了したことがわかります。その後、親プロセスは、子プロセスによって保存された一時ファイルの名前を に変更します。実際の rdb ファイル (つまり、実際の保存が成功した場合のみターゲット ファイルに変更されます。これが安全な方法です)。次に、この保存の終了時間を記録します。

ここで問題が発生します。子プロセスの保存期間中に親プロセスのデータベースが変更され、親プロセスは修正操作を行わずに変更数 (ダーティ) のみを記録します。 RDBが保存するのはリアルタイムデータベースではないようで、ちょっと地味です。 ただし、後で紹介する AOF 永続化により、この問題は解決されます。

savaコマンドやbgsaveコマンドをお客様が実行するほか、RDBの保存条件も設定できます。つまり、データベースが t 時間以内に変更された場合、それはバックグラウンドで保存されます。 redis が cron を提供する場合、ダーティ オブジェクトの数と最後の保存時刻に基づいて条件を満たしているかどうかを判断します。条件が満たされている場合、子プロセスは 1 つしか存在できないことに注意してください。保存は非常に高価な IO 操作であるため、いつでもバックグラウンドで保存できます。複数のプロセスでの多数の IO 操作は非効率的であり、管理が困難です。

4.2 AOF 永続性

まず、データベースを保存するには、RDB のようにデータベース内のすべてのデータを保存する必要がありますか?他に方法はありますか?

RDB は結果である最終的なデータベースのみを保存します。結果はどうなりましたか?ユーザーのさまざまなコマンドによって確立されるため、結果を保存する必要はありませんが、結果を作成したコマンドのみが保存されます。 redisのAOFはRDBとは異なり、データベースを作成するためのコマンドを1つずつ保存します。

まず、AOF ファイルの形式を見てみましょう。最初にコマンドの長さが保存され、次にコマンドが保存されます。これは重要ではありません。とにかく、AOF ファイルがどのように保存されるかはわかります。これは Redis クライアントによって実行されるコマンドです。

Redis サーバーには sds aof_buf があり、aof 永続性がオンになっている場合、データベースを変更する各コマンドはこの aof_buf に保存され (aof ファイル内のコマンド形式の文字列が保存されます)、イベント ループが実行されます。サーバー cron では、flushaofbuf を呼び出し、aof_buf 内のコマンドを aof ファイルに書き込み (実際には書き込みます。実際に書き込まれるのはカーネル バッファーです)、その後 aof_buf をクリアして次のループに入ります。このようにして、aof ファイル内のコマンドを使用してデータベースのすべての変更を復元でき、データベースを保存する効果が得られます。

flashaofbuf で呼び出される書き込みはカーネル バッファにデータを書き込むだけであることに注意してください。ファイルの実際の書き込みはカーネル自体によって決定され、一定期間遅延する必要がある場合があります。 ただし、redis は構成をサポートしており、書き込みのたびに同期を構成し、redis で sync を呼び出してカーネル内のデータをファイルに書き込むことができます。これにはシステム コールのみが必要ですが、時間がかかります。 1 秒に 1 回同期するようにポリシーを構成することもできます。その後、redis がバックグラウンド スレッドを開始し (つまり、redis は単一のスレッドではなく、単一のイベントループになります)、このバックグラウンド スレッドは 1 秒ごとに sync を呼び出します。ここで疑問に思うのは、なぜ RDB を使用するときに同期が考慮されなかったのかということです。 RDBは複数回のAOFとは異なり一度保存されるため、RDB中にsyncを1回呼び出しても効果はなく、bg saveを使用すると子プロセスが勝手に終了(exit)してしまい、このときexit関数でバッファがフラッシュされます。 . 領域にある場合は、自動的にファイルに書き込まれます。

もう一度見てみると、各変更コマンドを保存するために aof_buf を使用したくない場合は、aof 永続性を使用することもできます。 Redis は、既存のデータベースに基づいてコマンドを生成し、そのコマンドを aof ファイルに書き込む aof_rewrite を提供します。とても奇妙ですよね？はい、それは素晴らしいことです。 aof_rewrite を実行すると、各データベースで redis 変数が使用され、リストなどのキーと値のペアの特定の種類の値に基づいてさまざまなコマンドが生成され、リストを保存するコマンドが生成されます。リストの保存に必要な情報。リストのデータが長すぎる場合は、複数のコマンドに分割されます。つまり、リストに要素を追加するコマンドが生成されます。データに基づいて逆にします。次に、これらのコマンドを aof ファイルに保存すると、aof append と同じ効果が得られませんか?

再来看，aof格式也支持后台模式。执行aof_bgrewrite的时候，也是fork一个子进程，然后让子进程进行aof_rewrite，把它复制的数据库写入一个临时文件，然后写完后用新号通知父进程。父进程判断子进程的退出信息是否正确，然后将临时文件更名成最终的aof文件。好了，问题来了。在子进程持久化期间，可能父进程的数据库有更新，怎么把这个更新通知子进程呢？难道要用进程间通信么？是不是有点麻烦呢？你猜redis怎么做的？它根本不通知子进程。什么，不通知？那更新怎么办？ 在子进程执行aof_bgrewrite期间，父进程会保存所有对数据库有更改的操作的命令（增，删除，改等），把他们保存在aof_rewrite_buf_blocks中，这是一个链表，每个block都可以保存命令，存不下时，新申请block，然后放入链表后面即可，当子进程通知完成保存后，父进程将aof_rewrite_buf_blocks的命令append 进aof文件就可以了。多么优美的设计，想一想自己当初还考虑用进程间通信，别人直接用最简单的方法就完美的解决了问题，有句话说得真对，越优秀的设计越趋于简单，而复杂的东西往往都是靠不住的。

至于aof文件的载入，也就是一条一条的执行aof文件里面的命令而已。不过考虑到这些命令就是客户端发送给redis的命令，所以redis干脆生成了一个假的客户端，它没有和redis建立网络连接，而是直接执行命令即可。首先搞清楚，这里的假的客户端，并不是真正的客户端，而是存储在redis里面的客户端的信息，里面有写和读的缓冲区，它是存在于redis服务器中的。所以，如下图，直接读入aof的命令，放入客户端的读缓冲区中，然后执行这个客户端的命令即可。这样就完成了aof文件的载入。

// 创建伪客户端
fakeClient = createFakeClient();

while(命令不为空) {
   // 获取一条命令的参数信息 argc， argv
   ...

    // 执行
    fakeClient->argc = argc;
    fakeClient->argv = argv;
    cmd->proc(fakeClient);
}

整个aof持久化的设计，个人认为相当精彩。其中有很多地方，值得膜拜。

5. redis的事务

redis另一个比memcached强大的地方，是它支持简单的事务。事务简单说就是把几个命令合并，一次性执行全部命令。对于关系型数据库来说，事务还有回滚机制，即事务命令要么全部执行成功，只要有一条失败就回滚，回到事务执行前的状态。redis不支持回滚，它的事务只保证命令依次被执行，即使中间一条命令出错也会继续往下执行，所以说它只支持简单的事务。

首先看redis事务的执行过程。首先执行multi命令，表示开始事务，然后输入需要执行的命令，最后输入exec执行事务。 redis服务器收到multi命令后，会将对应的client的状态设置为REDIS_MULTI，表示client处于事务阶段，并在client的multiState结构体里面保持事务的命令具体信息（当然首先也会检查命令是否能否识别，错误的命令不会保存），即命令的个数和具体的各个命令，当收到exec命令后，redis会顺序执行multiState里面保存的命令，然后保存每个命令的返回值，当有命令发生错误的时候，redis不会停止事务，而是保存错误信息，然后继续往下执行，当所有的命令都执行完后，将所有命令的返回值一起返回给客户。redis为什么不支持回滚呢？网上看到的解释出现问题是由于客户程序的问题，所以没必要服务器回滚，同时，不支持回滚，redis服务器的运行高效很多。在我看来，redis的事务不是传统关系型数据库的事务，要求CIAD那么非常严格，或者说redis的事务都不是事务，只是提供了一种方式，使得客户端可以一次性执行多条命令而已，就把事务当做普通命令就行了，支持回滚也就没必要了。

我们知道redis是单event loop的，在真正执行一个事物的时候（即redis收到exec命令后），事物的执行过程是不会被打断的，所有命令都会在一个event loop中执行完。但是在用户逐个输入事务的命令的时候，这期间，可能已经有别的客户修改了事务里面用到的数据，这就可能产生问题。所以redis还提供了watch命令，用户可以在输入multi之前，执行watch命令，指定需要观察的数据，这样如果在exec之前，有其他的客户端修改了这些被watch的数据，则exec的时候，执行到处理被修改的数据的命令的时候，会执行失败，提示数据已经dirty。 这是如何是实现的呢？ 原来在每一个redisDb中还有一个dict watched_keys，watched_kesy中dictentry的key是被watch的数据库的key，而value则是一个list，里面存储的是watch它的client。同时，每个client也有一个watched_keys，里面保存的是这个client当前watch的key。在执行watch的时候，redis在对应的数据库的watched_keys中找到这个key（如果没有，则新建一个dictentry），然后在它的客户列表中加入这个client，同时，往这个client的watched_keys中加入这个key。当有客户执行一个命令修改数据的时候，redis首先在watched_keys中找这个key，如果发现有它，证明有client在watch它，则遍历所有watch它的client，将这些client设置为REDIS_DIRTY_CAS，表面有watch的key被dirty了。当客户执行的事务的时候，首先会检查是否被设置了REDIS_DIRTY_CAS，如果是，则表明数据dirty了，事务无法执行，会立即返回错误，只有client没有被设置REDIS_DIRTY_CAS的时候才能够执行事务。 需要指出的是，执行exec后，该client的所有watch的key都会被清除，同时db中该key的client列表也会清除该client，即执行exec后，该client不再watch任何key（即使exec没有执行成功也是一样）。所以说redis的事务是简单的事务，算不上真正的事务。

以上就是redis的事务，感觉实现很简单，实际用处也不是太大。

6. redis的发布订阅频道

redis支持频道，即加入一个频道的用户相当于加入了一个群，客户往频道里面发的信息，频道里的所有client都能收到。

实现也很简单，也watch_keys实现差不多，redis server中保存了一个pubsub_channels的dict，里面的key是频道的名称（显然要唯一了），value则是一个链表，保存加入了该频道的client。同时，每个client都有一个pubsub_channels，保存了自己关注的频道。当用用户往频道发消息的时候，首先在server中的pubsub_channels找到改频道，然后遍历client，给他们发消息。而订阅，取消订阅频道不够都是操作pubsub_channels而已，很好理解。

同时，redis还支持模式频道。即通过正则匹配频道，如有模式频道p, 1, 则向普通频道p1发送消息时，会匹配p，1，除了往普通频道发消息外，还会往p，1模式频道中的client发消息。注意，这里是用发布命令里面的普通频道来匹配已有的模式频道，而不是在发布命令里制定模式频道，然后匹配redis里面保存的频道。实现方式也很简单，在redis server里面有个pubsub_patterns的list（这里为什么不用dict？因为pubsub_patterns的个数一般较少，不需要使用dict，简单的list就好了），它里面存储的是pubsubPattern结构体，里面是模式和client信息，如下所示，一个模式，一个client，所以如果有多个clint监听一个pubsub_patterns的话，在list面会有多个pubsubPattern，保存client和pubsub_patterns的对应关系。 同时，在client里面，也有一个pubsub_patterns list，不过里面存储的就是它监听的pubsub_patterns的列表（就是sds），而不是pubsubPattern结构体。

typedef struct pubsubPattern {
    redisClient *client;    // 监听的client
    robj *pattern;            // 模式
} pubsubPattern;

当用户往一个频道发送消息的时候，首先会在redis server中的pubsub_channels里面查找该频道，然后往它的客户列表发送消息。然后在redis server里面的pubsub_patterns里面查找匹配的模式，然后往client里面发送消息。 这里并没有去除重复的客户，在pubsub_channels可能已经给某一个client发过message了，然后在pubsub_patterns中可能还会给用户再发一次（甚至更多次）。 估计redis认为这是客户程序自己的问题，所以不处理。

/* Publish a message */
int pubsubPublishMessage(robj *channel, robj *message) {
    int receivers = 0;
    dictEntry *de;
    listNode *ln;
    listIter li;

/* Send to clients listening for that channel */
    de = dictFind(server.pubsub_channels,channel);
    if (de) {
        list *list = dictGetVal(de);
        listNode *ln;
        listIter li;

        listRewind(list,&li);
        while ((ln = listNext(&li)) != NULL) {
            redisClient *c = ln->value;

            addReply(c,shared.mbulkhdr[3]);
            addReply(c,shared.messagebulk);
            addReplyBulk(c,channel);
            addReplyBulk(c,message);
            receivers++;
        }
    }
 /* Send to clients listening to matching channels */
    if (listLength(server.pubsub_patterns)) {
        listRewind(server.pubsub_patterns,&li);
        channel = getDecodedObject(channel);
        while ((ln = listNext(&li)) != NULL) {
            pubsubPattern *pat = ln->value;

            if (stringmatchlen((char*)pat->pattern->ptr,
                                sdslen(pat->pattern->ptr),
                                (char*)channel->ptr,
                                sdslen(channel->ptr),0)) {
                addReply(pat->client,shared.mbulkhdr[4]);
                addReply(pat->client,shared.pmessagebulk);
                addReplyBulk(pat->client,pat->pattern);
                addReplyBulk(pat->client,channel);
                addReplyBulk(pat->client,message);
                receivers++;
            }
        }
        decrRefCount(channel);
    }
    return receivers;
}

六. 总结

总的来看，redis比memcached的功能多很多，实现也更复杂。 不过memcached更专注于保存key-value数据（这已经能满足大多数使用场景了），而redis提供更丰富的数据结构及其他的一些功能。不能说redis比memcached好，不过从源码阅读的角度来看，redis的价值或许更大一点。 另外，redis3.0里面支持了集群功能，这部分的代码还没有研究，后续再跟进。

以上がmemcached と Redis 実装の比較を紹介する詳細なグラフィック コードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。