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 内の複数のスラブのトランク サイズはすべて同じです。 slabclass には、解放された未割り当ての項目を保存するポインター スロットがあります (実際にはメモリが解放されているわけではなく、使用されなくなっただけです)。使用されていない項目がある場合、それらはスロットの先頭に置かれます。現在のスラブにアイテムを割り当てるときは、アイテムが未割り当てか解放されているかに関係なく、スロットに直接アクセスできます。

然后，每一个slabclass对应一个链表，有head数组和tail数组，它们分别保存了链表的头节点和尾节点。链表中的节点就是改slabclass所分配的item，新分配的放在头部，链表越往后的item，表示它已经很久没有被使用了。当slabclass的内存不足，需要删除一些过期item的时候，就可以从链表的尾部开始删除，没错，这个链表就是为了实现LRU。光靠它还不行，因为链表的查询是O（n）的，所以定位item的时候，使用hash表，这已经有了，所有分配的item已经在hash表中了，所以，hash用于查找item，然后链表有用存储item的最近使用顺序，这也是lru的标准实现方法。

每次需要新分配item的时候，找到slabclass对于的链表，从尾部往前找，看item是否已经过期，过期的话，直接就用这个过期的item当做新的item。没有过期的，则需要从slab中分配trunk，如果slab用完了，则需要往slabclass中添加slab了。

memcached支持设置过期时间，即expire time，但是内部并不定期检查数据是否过期，而是客户进程使用该数据的时候，memcached会检查expire time，如果过期，直接返回错误。这样的优点是，不需要额外的cpu来进行expire time的检查，缺点是有可能过期数据很久不被使用，则一直没有被释放，占用内存。

memcached是多线程的，而且只维护了一个数据库，所以可能有多个客户进程操作同一个数据，这就有可能产生问题。比如，A已经把数据更改了，然后B也更改了改数据，那么A的操作就被覆盖了，而可能A不知道，A任务数据现在的状态时他改完后的那个值，这样就可能产生问题。为了解决这个问题，memcached使用了CAS协议，简单说就是item保存一个64位的unsigned int值，标记数据的版本，每更新一次（数据值有修改），版本号增加，然后每次对数据进行更改操作，需要比对客户进程传来的版本号和服务器这边item的版本号是否一致，一致则可进行更改操作，否则提示脏数据。

以上就是memcached如何实现一个key-value的数据库的介绍。

2. redis数据库实现

首先redis数据库的功能强大一些，因为不像memcached只支持保存字符串，redis支持string， list， set，sorted set，hash table 5种数据结构。例如存储一个人的信息就可以使用hash table，用人的名字做key，然后name super， age 24， 通过key 和 name，就可以取到名字super，或者通过key和age，就可以取到年龄24。这样，当只需要取得age的时候，不需要把人的整个信息取回来，然后从里面找age，直接获取age即可，高效方便。

为了实现这些数据结构，redis定义了抽象的对象redis object，如下图。每一个对象有类型，一共5种：字符串，链表，集合，有序集合，哈希表。 同时，为了提高效率，redis为每种类型准备了多种实现方式，根据特定的场景来选择合适的实现方式，encoding就是表示对象的实现方式的。然后还有记录了对象的lru，即上次被访问的时间，同时在redis 服务器中会记录一个当前的时间（近似值，因为这个时间只是每隔一定时间，服务器进行自动维护的时候才更新），它们两个只差就可以计算出对象多久没有被访问了。 然后redis object中还有引用计数，这是为了共享对象，然后确定对象的删除时间用的。最后使用一个void*指针来指向对象的真正内容。正式由于使用了抽象redis object，使得数据库操作数据时方便很多，全部统一使用redis object对象即可，需要区分对象类型的时候，再根据type来判断。而且正式由于采用了这种面向对象的方法，让redis的代码看起来很像c++代码，其实全是用c写的。

//#define REDIS_STRING 0    // 字符串类型
//#define REDIS_LIST 1        // 链表类型
//#define REDIS_SET 2        // 集合类型(无序的)，可以求差集，并集等
//#define REDIS_ZSET 3        // 有序的集合类型
//#define REDIS_HASH 4        // 哈希类型

//#define REDIS_ENCODING_RAW 0     /* Raw representation */ //raw  未加工
//#define REDIS_ENCODING_INT 1     /* Encoded as integer */
//#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
//#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
//#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
//#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
//#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
//#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
//#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds 
                                                                     string encoding */

typedef struct redisObject {
    unsigned type:4;            // 对象的类型，包括 /* Object types */
    unsigned encoding:4;        // 底部为了节省空间，一种type的数据，
                                                // 可   以采用不同的存储方式
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
    int refcount;         // 引用计数
    void *ptr;
} robj;

说到底redis还是一个key-value的数据库，不管它支持多少种数据结构，最终存储的还是以key-value的方式，只不过value可以是链表，set，sorted set，hash table等。和memcached一样，所有的key都是string，而set，sorted set，hash table等具体存储的时候也用到了string。 而c没有现成的string，所以redis的首要任务就是实现一个string，取名叫sds（simple dynamic string），如下的代码， 非常简单的一个结构体，len存储改string的内存总长度，free表示还有多少字节没有使用，而buf存储具体的数据，显然len-free就是目前字符串的长度。

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 サイトの他の関連記事を参照してください。