【Redisソースプロファイリング】-Redisデータ型のリスト

オリジナル作品、転載は明記してください:http://blog.csdn.net/Xiejingfa/article/details/51166709
今日はRedisの5つのデータ型の1つであるListのソースコード分析をお届けします.
RedisにおけるListタイプは双方向チェーンテーブル構造であり、主に以下のコマンドをサポートする.

lpush、rpush、lpushx、rpushx

lpop、rpop、lrange、ltrim、lrem、rpoplpush

linsert、llen、lindex、lset

blpop、brpop、brpoplpush

Listの関連操作は主にt_で定義されるlist.cとredis.hファイルにあります.まとめると、主に以下のポイントがあります.
1、符号化方式
前の記事では、Listタイプには主に2つの符号化方式があることを紹介しました:REDIS_ENCODING_ZIPLISTとREDIS_ENCODING_LINKEDLIST.ここでREDIS_ENCODING_ZIPLIST符号化は圧縮リストziplist,REDIS_を用いるENCODING_LINKEDLIST符号化は双方向チェーンテーブルlist(区別しやすいようにlinked listと呼ぶ)を用いる.デフォルトではListはREDIS_を使用しますENCODING_ZIPLIST符号化は、次の2つの条件を満たすときにREDIS_に遷移するENCODING_LINKEDLISTコード:

追加する新しい文字列の長さがserverを超える場合.list_max_ziplist_value(既定値64)の場合.

ziplistに保存するノードの数はserverを超える.list_max_ziplist_entries(デフォルト値512)の場合.

リストタイプに2つの下位構造がある以上、t_list.cの主な機能の1つはziplistとlinked listの2つの構造の上で1部の統一的なList操作インタフェースを維持して、下層の違いを遮蔽することです.
たとえばlistType Pushのソースコードを見てみましょう.

void listTypePush(robj *subject, robj *value, int where) {
    /* Check if we need to convert the ziplist */
    //           （REDIS_ENCODING_ZIPLIST => REDIS_ENCODING_LINKEDLIST）
    listTypeTryConversion(subject,value);
    if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
        // list_max_ziplist_entries     512，  ziplist                  
        ziplistLen(subject->ptr) >= server.list_max_ziplist_entries)
            listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);

    //      ziplist linked list     
    if (subject->encoding == REDIS_ENCODING_ZIPLIST) {
        /*        ziplist    */

        //                
        int pos = (where == REDIS_HEAD) ? ZIPLIST_HEAD : ZIPLIST_TAIL;
        value = getDecodedObject(value);
        //     ziplist           
        subject->ptr = ziplistPush(subject->ptr,value->ptr,sdslen(value->ptr),pos);
        decrRefCount(value);
    } else if (subject->encoding == REDIS_ENCODING_LINKEDLIST) {
        /*          linked list    */
        if (where == REDIS_HEAD) {
            listAddNodeHead(subject->ptr,value);
        } else {
            listAddNodeTail(subject->ptr,value);
        }
        incrRefCount(value);
    } else {
        redisPanic("Unknown list encoding");
    }
}

ListType Push関数の役割は、リストタイプオブジェクトに要素を追加することです.パラメータwhereは、ヘッダーに追加するか、末尾に追加するかを指定するために使用されます.ListType Pushの実行手順は次のとおりです.

は、新たに追加する値の長いがserverを超えるか否かを判定する.list_max_ziplist_value、超えた場合は符号化方式を変換する必要があります.

Listの現在の符号化がREDIS_である場合ENCODING_ZIPLIST方式は、その格納ノード数がserverを超えるか否かを判定する.list_max_ziplist_entriesは、超える場合は符号化変換が必要です.

Listの現在の符号化を判定し、REDIS_であればENCODING_ZIPLISTではziplistの内部関数を呼び出して追加操作を実現する.REDIS_ならENCODING_LINKEDLISTはlinked listの内部関数を呼び出して追加操作を実現する.

リストの操作は基本的に現在使用されている最下位のデータ構造によって行われていることがわかります.これらのデータ構造の基本操作は以前から分析していましたが、ここでは説明しません.
上記のlistType-Push操作に加えて、ListにはlistType-Pop、listType-Length、listType-Insert、listType-Equal、listType-Delete、listType-Convertなどの操作があります.これらの操作の実現はlistType-Pushと同様に下位データ構造で実現され、コードが簡単で直感的で、類比的に学ぶことができます.
2、反復器実現
Redisはリストタイプに簡単な反復器構造体を封入し、redisに定義する.hファイル内:

/* List         */
typedef struct {
    //  listType  
    robj *subject;
    //     
    unsigned char encoding;
    //     
    unsigned char direction; /* Iteration direction */
    // ziplist   
    unsigned char *zi;
    // linked list   
    listNode *ln;
} listTypeIterator;

反復ノードも定義されています.

/* List       */
typedef struct {
    listTypeIterator *li;
    unsigned char *zi;  /* Entry in ziplist */
    listNode *ln;       /* Entry in linked list */
} listTypeEntry;

実際、このlistType Iteratorはziplistとlinke listの反復器を一緒に包装して2つの符号化方式の違いをさらに遮断している.反復器に関連する操作は主にいくつかあります.

//             
listTypeIterator *listTypeInitIterator(robj *subject, long index, unsigned char direction);
//   listType    
void listTypeReleaseIterator(listTypeIterator *li);
//         
int listTypeNext(listTypeIterator *li, listTypeEntry *entry);
//     listTypeEntry        
robj *listTypeGet(listTypeEntry *entry);

3、ブロック操作
これは重点的に理解しなければならないところです!
Redisには、クライアントがブロックされる可能性のある3つのブロックコマンドblpop、brpop、brpoplpushがあります.次にblpopコマンドを例に、ブロック版のlpopコマンドがどのように実行されているかを説明します.
(1)、ユーザがBLPOPコマンドを実行し、リストが空でないことを指定すると、プログラムは非ブロックLPOPコマンドを直接呼び出す(したがってblpop、brpop、brpoplpushはクライアントがブロックする可能性があるだけである).(2)、ユーザがBLPOPコマンドを実行し、リストが空であることを指定した場合、操作をブロックする必要がある.Redisは、対応するクライアントの状態を「ブロック」状態に設定し、db->blocking_にクライアントを追加します.keysで.db->blocking_keysは辞書構造で、keyはブロックされたキーであり、valueはブロックされたクライアントを保存するリストである.このプロセスをひとまず「ブロックプロセス」と呼ぶ.(3)、その後、PUSHコマンドがブロックされたキーに要素を追加した場合、Redisはこのキーをready状態として識別する.このコマンドの実行が完了すると、Redisは、先にブロックされたサービスの順にリストの要素をブロックされたクライアントに戻し、ブロック解除状態のクライアントの数は、PUSHコマンドによって追加された要素の数に依存する.この過程をひとまず「ブロック解除過程」と呼ぶ.
次に、「ブロッキング・プロシージャ」と「ブロッキング解除プロシージャ」の実行手順を詳しく説明します.
3.1、ブロックプロセス
ブロック操作はblockForKeys関数で行われ、関数のプロトタイプは次のとおりです.

void blockForKeys(redisClient *c, robj **keys, int numkeys, time_t timeout, robj *target)

blockForKeys関数は、指定したキーに対するクライアントのブロック状態を設定するために使用されます.パラメータkeysは任意の数のキーを指定し、timeoutはタイムアウト時間を指定し、パラメータtargetはターゲットリストオブジェクトであり、主にbrpoplpushコマンドに用いられ、ユーザーはソースリストからpopが出た値を格納する.この関数では、次の手順に従います.
(1)、ブロックタイムアウト時間timeoutとターゲットオプションtargetを設定します.(2)、クライアント情報をc->db->blocking_に記録するkeys構造で.前に言ったようにb->blocking_keysは辞書構造で、keyはブロックされたキーであり、valueはブロックされたクライアントを保存するリストである.blocking_keys定義はredisClient->redisDb構造で、観察を容易にするために、他の無関係コードを省略しました.

typedef struct redisDb {
    ...
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */
    ...
} redisDb;

構造全体がこうです

(3)、クライアントを「ブロック」状態に設定する.
blockForKeysのソースコードは次のとおりです.

/* Set a client in blocking mode for the specified key, with the specified * timeout */
/*               。  keys          ，timeout      ，  target   listType  ，     brpoplpush  ，         pop    。 */
void blockForKeys(redisClient *c, robj **keys, int numkeys, time_t timeout, robj *target) {
    dictEntry *de;
    list *l;
    int j;

    //          
    c->bpop.timeout = timeout;
    //       ，    brpoplpush  
    c->bpop.target = target;

    // target   rpoplpush  
    if (target != NULL) incrRefCount(target);

    //  c->db->blocking_keys              
    for (j = 0; j < numkeys; j++) {
        /* If the key already exists in the dict ignore it. */
        // bpop.keys        
        if (dictAdd(c->bpop.keys,keys[j],NULL) != DICT_OK) continue;
        incrRefCount(keys[j]);

        /* And in the other "side", to map keys -> clients */
        //                  
        de = dictFind(c->db->blocking_keys,keys[j]);
        if (de == NULL) {
            int retval;

            /* For every key we take a list of clients blocked for it */
            //                   ，     
            l = listCreate();
            retval = dictAdd(c->db->blocking_keys,keys[j],l);
            incrRefCount(keys[j]);
            redisAssertWithInfo(c,keys[j],retval == DICT_OK);
        } else {
            l = dictGetVal(de);
        }
        //                
        listAddNodeTail(l,c);
    }

    /* Mark the client as a blocked client */
    //        “  ”  
    c->flags |= REDIS_BLOCKED;
    server.bpop_blocked_clients++;
}

3.2、ブロック解除プロセス
Listのブロック解除過程は以下の通りである.
(1)、他のクライアントから実行命令があればそのkey(すなわちList)に新しい値を追加し、blocking_keysでは、そのkeyによってクライアントがブロックするかどうかをチェックし、ある場合はsignalListAsReadyを呼び出してそのkeyのためにreadyList構造を作成しserverに入れる.ready_keysチェーンテーブルにキーを追加し、db->ready_にキーを追加keysで.db->ready_keysはハッシュテーブルで、valueはNULLです.このサーバーready_keysリストは最後にhandleClientsBlockedOnLists関数で処理されます.
ここで注意したいのは、チェーンテーブルとハッシュテーブルを使用して同じkeyを格納する理由です.1つのkeyに複数の新しい値が追加された場合、Redisはserverにのみ必要です.ready_keysは、そのkeyに関連するreadyListノードを保存すればよく、1つのトランザクションまたはスクリプトにおいて同じkeyがserverに何度も追加することを回避することができる.ready_keysリストにあります.繰り返し追加しないためには、追加検索を実行するたびに「チェック」操作を行う必要がありますが、server.ready_keysはチェーンテーブルであり,検索操作を行う時間の複雑さはO(n)であり,効率は比較的悪い.この問題を解決するためにRedisはdb->ready_を導入したkeysハッシュテーブル構造は同じkeyを保存するため、ハッシュテーブルの検索効率が高いため、server.ready_keysノードを追加するときはdb->ready_ちょっとチェックすればわかるready_keysは同じノードがありますか.
次に、signalListAsReady関数に関連する構造体を見てみましょう.
readyListはredisで定義する.hファイル内:

typedef struct readyList {
    // key      
    redisDb *db;
    //       
    robj *key;
} readyList;

readyList構造はserverを表す.ready_keysチェーンテーブルのノードです.keyフィールドはブロックされたkeyを表し、dbはキーが存在するデータベースを指します.
db->ready_keysはredisDb構造体において、準備されたデータのブロック状態を格納するためのkeyを定義する.

typedef struct redisDb {
    ...
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    ...
} redisDb;

SignalListAsReady関数のソースコードは次のとおりです.

void signalListAsReady(redisDb *db, robj *key) {
    // readyList   redis.h ，  server.ready_keys     
    readyList *rl;

    /* No clients blocking for this key? No need to queue it. */
    //           key    ，     
    if (dictFind(db->blocking_keys,key) == NULL) return;

    /* Key was already signaled? No need to queue it again. */
    //     key     ready_keys，           
    if (dictFind(db->ready_keys,key) != NULL) return;

    /* Ok, we need to queue this key into server.ready_keys. */
    //     readyList  ，     server.ready_keys  
    rl = zmalloc(sizeof(*rl));
    rl->key = key;
    rl->db = db;
    incrRefCount(key);
    listAddNodeTail(server.ready_keys,rl);

    /* We also add the key in the db->ready_keys dictionary in order * to avoid adding it multiple times into a list with a simple O(1) * check. */
    incrRefCount(key);
    //  key   db->ready_keys ，      
    redisAssert(dictAdd(db->ready_keys,key,NULL) == DICT_OK);
}

これまでRedisは,データの準備ができているブロック状態にあるkey情報を収集しただけで,次にクライアントのブロック状態を本当に解除する操作であった.
(2)、serverを巡回するhandleClientsBlockedOnLists関数を呼び出す.ready_keysでデータが準備されているkeyは、そのkeyにブロックされているすべてのクライアントを巡回しながら(c->db->blocking_keysサイトからクライアントリストを直接取得します).キーが空でない場合、キーから要素がポップアップされてクライアントに戻り、キーが空であるか、クライアントがキーのためにブロックされていないかまでクライアントのブロック状態を解除します.
handleClientsBlockedOnLists関数のソースコードは以下の通りで、コードも簡単です.

void handleClientsBlockedOnLists(void) {
    //   server.ready_keys  
    while(listLength(server.ready_keys) != 0) {
        list *l;

        /* Point server.ready_keys to a fresh list and save the current one * locally. This way as we run the old list we are free to call * signalListAsReady() that may push new elements in server.ready_keys * when handling clients blocked into BRPOPLPUSH. */
        //   server.ready_keys，              。          server.ready_keys   
        l = server.ready_keys;
        server.ready_keys = listCreate();

        while(listLength(l) != 0) {
            //   server.ready_keys      
            listNode *ln = listFirst(l);
            readyList *rl = ln->value;

            /* First of all remove this key from db->ready_keys so that * we can safely call signalListAsReady() against this key. */
            //  db->ready_keys     key
            dictDelete(rl->db->ready_keys,rl->key);

            /* If the key exists and it's a list, serve blocked clients * with data. */
            //   listType  
            robj *o = lookupKeyWrite(rl->db,rl->key);
            if (o != NULL && o->type == REDIS_LIST) {
                dictEntry *de;

                /* We serve clients in the same order they blocked for * this key, from the first blocked to the last. */
                //        key        
                de = dictFind(rl->db->blocking_keys,rl->key);
                if (de) {
                    list *clients = dictGetVal(de);
                    int numclients = listLength(clients);

                    while(numclients--) {
                        //        
                        listNode *clientnode = listFirst(clients);
                        redisClient *receiver = clientnode->value;
                        //   pop      
                        robj *dstkey = receiver->bpop.target;
                        //         
                        int where = (receiver->lastcmd &&
                                     receiver->lastcmd->proc == blpopCommand) ?
                                    REDIS_HEAD : REDIS_TAIL;
                        robj *value = listTypePop(o,where);

                        //   listType    ，        
                        if (value) {
                            /* Protect receiver->bpop.target, that will be * freed by the next unblockClientWaitingData() * call. */
                            if (dstkey) incrRefCount(dstkey);
                            //             
                            unblockClientWaitingData(receiver);

                            //  pop             receiver
                            if (serveClientBlockedOnList(receiver,
                                rl->key,dstkey,rl->db,value,
                                where) == REDIS_ERR)
                            {
                                /* If we failed serving the client we need * to also undo the POP operation. */
                                //       ，   （   listType  ）
                                    listTypePush(o,value,where);
                            }

                            if (dstkey) decrRefCount(dstkey);
                            decrRefCount(value);
                        } else {
                            //   listType      ，                ，       push  
                            break;
                        }
                    }
                }

                //           ，    
                if (listTypeLength(o) == 0) dbDelete(rl->db,rl->key);
                /* We don't call signalModifiedKey() as it was already called * when an element was pushed on the list. */
            }

            /* Free this item. */
            //     
            decrRefCount(rl->key);
            zfree(rl);
            listDelNode(l,ln);
        }
        listRelease(l); /* We have the new list on place at this point. */
    }
}

以上の解析から,リストは「先ブロック先サービス」のポリシーに従ってブロック解除を処理していることが分かる.
また、クライアントのブロック状態の解除は、ブロックタイムアウトによる可能性もある.このプロセスは簡単で、ブロック状態にあるクライアントを一度遍歴し、タイムアウトしたクライアントに対してブロック状態を取り消し、空の返信を返すだけでよい.
リストのソースコードはここまで分析されます.慣例に従って、最後に注釈のコードを提供して参考にします:ドアを転送します.