redis源碼分析之有序集SortedSet

来源:http://www.cnblogs.com/lfls/archive/2017/11/20/7864798.html
-Advertisement-
Play Games

有序集SortedSet算是redis中一個很有特色的數據結構，通過這篇文章來總結一下這塊知識點。 原文地址：http://www.jianshu.com/p/75ca5a359f9f 一、有序集SortedSet命令簡介 redis中的有序集，允許用戶使用指定值對放進去的元素進行排序，並且基於該已 ...


有序集SortedSet算是redis中一個很有特色的數據結構，通過這篇文章來總結一下這塊知識點。

原文地址：http://www.jianshu.com/p/75ca5a359f9f

一、有序集SortedSet命令簡介

redis中的有序集，允許用戶使用指定值對放進去的元素進行排序，並且基於該已排序的集合提供了一系列豐富的操作集合的API。
舉例如下：

//添加元素，table1為有序集的名字，100為用於排序欄位（redis把它叫做score），a為我們要存儲的元素
127.0.0.1:6379> zadd table1 100 a
(integer) 1
127.0.0.1:6379> zadd table1 200 b
(integer) 1
127.0.0.1:6379> zadd table1 300 c
(integer) 1
//按照元素索引返回有序集中的元素，索引從0開始
127.0.0.1:6379> zrange table1 0 1
1) "a"
2) "b"
//按照元素排序範圍返回有序集中的元素，這裡用於排序的欄位在redis中叫做score
127.0.0.1:6379> zrangebyscore table1 150 400
1) "b"
2) "c"
//刪除元素
127.0.0.1:6379> zrem table1 b
(integer) 1

在有序集中，用於排序的值叫做score，實際存儲的值叫做member。

由於有序集中提供的API較多，這裡只舉了幾個常見的，具體可以參考redis文檔。

關於有序集，我們有一個十分常見的使用場景就是用戶評論。在APP或者網站上發佈一條消息，下麵會有很多評論，通常展示是按照發佈時間倒序排列，這個需求就可以使用有序集，以發佈評論的時間戳作為score，然後按照展示評論的數量倒序查找有序集。

二、有序集SortedSet命令源碼分析

老規矩，我們還是從server.c文件中的命令表中找到相關命令的處理函數，然後一一分析。
依舊從添加元素開始，zaddCommand函數：

void zaddCommand(client *c) {
    zaddGenericCommand(c,ZADD_NONE);
}

這裡可以看到流程轉向了zaddGenericCommand，並且傳入了一個模式標記。
關於SortedSet的操作模式這裡簡單說明一下，先來看一條完整的zadd命令：

zadd key [NX|XX] [CH] [INCR] score member [score member ...]

其中的可選項我們依次看下：

  1. NX表示如果元素存在，則不執行替換操作直接返回。
  2. XX表示只操作已存在的元素。
  3. CH表示返回修改（包括添加，更新）元素的數量，只能被ZADD命令使用。
  4. INCR表示在原來的score基礎上加上新的score，而不是替換。

上面代碼片段中的ZADD_NONE表示普通操作。

接下來看下zaddGenericCommand函數的源碼，很長，耐心一點點看：

void zaddGenericCommand(client *c, int flags) {
    //一條錯誤提示信息
    static char *nanerr = "resulting score is not a number (NaN)";
    //有序集名字
    robj *key = c->argv[1];
    robj *zobj;
    sds ele;
    double score = 0, *scores = NULL;
    int j, elements;
    int scoreidx = 0;
    //記錄元素操作個數
    int added = 0;     
    int updated = 0;    
    int processed = 0;  
    
    //查找score的位置，預設score在位置2上，但由於有各種模式，所以需要判斷
    scoreidx = 2;
    while(scoreidx < c->argc) {
        char *opt = c->argv[scoreidx]->ptr;
        //判斷命令中是否設置了各種模式
        if (!strcasecmp(opt,"nx")) flags |= ZADD_NX;
        else if (!strcasecmp(opt,"xx")) flags |= ZADD_XX;
        else if (!strcasecmp(opt,"ch")) flags |= ZADD_CH;
        else if (!strcasecmp(opt,"incr")) flags |= ZADD_INCR;
        else break;
        scoreidx++;
    }

    //設置模式
    int incr = (flags & ZADD_INCR) != 0;
    int nx = (flags & ZADD_NX) != 0;
    int xx = (flags & ZADD_XX) != 0;
    int ch = (flags & ZADD_CH) != 0;

    //通過上面的解析，scoreidx為真實的初始score的索引位置
    //這裡客戶端參數數量減去scoreidx就是剩餘所有元素的數量
    elements = c->argc - scoreidx;
    //由於有序集中score，member成對出現，所以加一層判斷
    if (elements % 2 || !elements) {
        addReply(c,shared.syntaxerr);
        return;
    }
    //這裡計算score，member有多少對
    elements /= 2; 

    //參數合法性校驗
    if (nx && xx) {
        addReplyError(c,
            "XX and NX options at the same time are not compatible");
        return;
    }
    //參數合法性校驗
    if (incr && elements > 1) {
        addReplyError(c,
            "INCR option supports a single increment-element pair");
        return;
    }

    //這裡開始解析score，先初始化scores數組
    scores = zmalloc(sizeof(double)*elements);
    for (j = 0; j < elements; j++) {
        //填充數組，這裡註意元素是成對出現，所以各個score之間要隔一個member
        if (getDoubleFromObjectOrReply(c,c->argv[scoreidx+j*2],&scores[j],NULL)
            != C_OK) goto cleanup;
    }

    //這裡首先在client對應的db中查找該key，即有序集
    zobj = lookupKeyWrite(c->db,key);
    if (zobj == NULL) {
        //沒有指定有序集且模式為XX（只操作已存在的元素），直接返回
        if (xx) goto reply_to_client; 
        //根據元素數量選擇不同的存儲結構初始化有序集
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
        {
            //哈希表 + 跳錶的組合模式
            zobj = createZsetObject();
        } else {
            //ziplist（壓縮鏈表）模式
            zobj = createZsetZiplistObject();
        }
        //加入db中
        dbAdd(c->db,key,zobj);
    } else {
        //如果ZADD操作的集合類型不對，則返回
        if (zobj->type != OBJ_ZSET) {
            addReply(c,shared.wrongtypeerr);
            goto cleanup;
        }
    }
    //這裡開始往有序集中添加元素
    for (j = 0; j < elements; j++) {
        double newscore;
        //取出client傳過來的score
        score = scores[j];
        int retflags = flags;
        //取出與之對應的member
        ele = c->argv[scoreidx+1+j*2]->ptr;
        //向有序集中添加元素，參數依次是有序集，要添加的元素的score，要添加的元素，操作模式，新的score
        int retval = zsetAdd(zobj, score, ele, &retflags, &newscore);
        //添加失敗則返回
        if (retval == 0) {
            addReplyError(c,nanerr);
            goto cleanup;
        }
        //記錄操作
        if (retflags & ZADD_ADDED) added++;
        if (retflags & ZADD_UPDATED) updated++;
        if (!(retflags & ZADD_NOP)) processed++;
        //設置新score值
        score = newscore;
    }
    //操作記錄
    server.dirty += (added+updated);

//返回邏輯
reply_to_client:
    if (incr) {
        if (processed)
            addReplyDouble(c,score);
        else
            addReply(c,shared.nullbulk);
    } else {
        addReplyLongLong(c,ch ? added+updated : added);
    }
//清理邏輯
cleanup:
    zfree(scores);
    if (added || updated) {
        signalModifiedKey(c->db,key);
        notifyKeyspaceEvent(NOTIFY_ZSET,
            incr ? "zincr" : "zadd", key, c->db->id);
    }
}

代碼有點長，來張圖看一下存儲結構：
有序集存儲結構
註：每個entry都是由score+member組成

有了上面的結構圖以後，可以想到刪除操作應該就是根據不同的存儲結構進行，如果是ziplist就執行鏈表刪除，如果是哈希表+跳錶結構，那就要把兩個集合都進行刪除。真實邏輯是什麼呢？
我們來看下刪除函數zremCommand的源碼，相對短一點：

void zremCommand(client *c) {
    //獲取有序集名
    robj *key = c->argv[1];
    robj *zobj;
    int deleted = 0, keyremoved = 0, j;
    //做校驗
    if ((zobj = lookupKeyWriteOrReply(c,key,shared.czero)) == NULL ||
        checkType(c,zobj,OBJ_ZSET)) return;

    for (j = 2; j < c->argc; j++) {
        //一次刪除指定元素
        if (zsetDel(zobj,c->argv[j]->ptr)) deleted++;
        //如果有序集中全部元素都被刪除，則回收有序表
        if (zsetLength(zobj) == 0) {
            dbDelete(c->db,key);
            keyremoved = 1;
            break;
        }
    }
    //同步操作
    if (deleted) {
        notifyKeyspaceEvent(NOTIFY_ZSET,"zrem",key,c->db->id);
        if (keyremoved)
            notifyKeyspaceEvent(NOTIFY_GENERIC,"del",key,c->db->id);
        signalModifiedKey(c->db,key);
        server.dirty += deleted;
    }
    //返回
    addReplyLongLong(c,deleted);
}

看下具體的刪除操作源碼：

//參數zobj為有序集，ele為要刪除的元素
int zsetDel(robj *zobj, sds ele) {
    //與添加元素相同，根據不同的存儲結構執行不同的刪除邏輯
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *eptr;
        //ziplist是一個簡單的鏈表刪除節點操作
        if ((eptr = zzlFind(zobj->ptr,ele,NULL)) != NULL) {
            zobj->ptr = zzlDelete(zobj->ptr,eptr);
            return 1;
        }
    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        dictEntry *de;
        double score;

        de = dictUnlink(zs->dict,ele);
        if (de != NULL) {
            //查詢該元素的score
            score = *(double*)dictGetVal(de);
            //從哈希表中刪除元素
            dictFreeUnlinkedEntry(zs->dict,de);

            //從跳錶中刪除元素
            int retval = zslDelete(zs->zsl,score,ele,NULL);
            serverAssert(retval);
            //如果有需要則對哈希表進行resize操作
            if (htNeedsResize(zs->dict)) dictResize(zs->dict);
            return 1;
        }
    } else {
        serverPanic("Unknown sorted set encoding");
    }
    //沒有找到指定元素返回0
    return 0;
}

最後看一個查詢函數zrangeCommand源碼，也是很長，汗~~~，不過放心，有了上面的基礎，大致也能猜到查詢邏輯應該是什麼樣子的：

void zrangeCommand(client *c) {
    //第二個參數，0表示順序，1表示倒序
    zrangeGenericCommand(c,0);
}

void zrangeGenericCommand(client *c, int reverse) {
    //有序集名
    robj *key = c->argv[1];
    robj *zobj;
    int withscores = 0;
    long start;
    long end;
    int llen;
    int rangelen;
    //參數校驗
    if ((getLongFromObjectOrReply(c, c->argv[2], &start, NULL) != C_OK) ||
        (getLongFromObjectOrReply(c, c->argv[3], &end, NULL) != C_OK)) return;

    //根據參數附加信息判斷是否需要返回score
    if (c->argc == 5 && !strcasecmp(c->argv[4]->ptr,"withscores")) {
        withscores = 1;
    } else if (c->argc >= 5) {
        addReply(c,shared.syntaxerr);
        return;
    }
    //有序集校驗
    if ((zobj = lookupKeyReadOrReply(c,key,shared.emptymultibulk)) == NULL
         || checkType(c,zobj,OBJ_ZSET)) return;

    //索引值重置
    llen = zsetLength(zobj);
    if (start < 0) start = llen+start;
    if (end < 0) end = llen+end;
    if (start < 0) start = 0;
     //返回空集
    if (start > end || start >= llen) {
        addReply(c,shared.emptymultibulk);
        return;
    }
    if (end >= llen) end = llen-1;
    rangelen = (end-start)+1;

    //返回給客戶端結果長度
    addReplyMultiBulkLen(c, withscores ? (rangelen*2) : rangelen);
    //同樣是根據有序集的不同結構執行不同的查詢邏輯
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl = zobj->ptr;
        unsigned char *eptr, *sptr;
        unsigned char *vstr;
        unsigned int vlen;
        long long vlong;
        //根據正序還是倒序計算起始索引
        if (reverse)
            eptr = ziplistIndex(zl,-2-(2*start));
        else
            eptr = ziplistIndex(zl,2*start);

        serverAssertWithInfo(c,zobj,eptr != NULL);
        sptr = ziplistNext(zl,eptr);

        while (rangelen--) {
            serverAssertWithInfo(c,zobj,eptr != NULL && sptr != NULL);
            //註意嵌套的ziplistGet方法就是把eptr索引的值讀出來保存在後面三個參數中
            serverAssertWithInfo(c,zobj,ziplistGet(eptr,&vstr,&vlen,&vlong));
            //返回value
            if (vstr == NULL)
                addReplyBulkLongLong(c,vlong);
            else
                addReplyBulkCBuffer(c,vstr,vlen);
            //如果需要則返回score
            if (withscores)
                addReplyDouble(c,zzlGetScore(sptr));
            //倒序從後往前，正序從前往後
            if (reverse)
                zzlPrev(zl,&eptr,&sptr);
            else
                zzlNext(zl,&eptr,&sptr);
        }

    } else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
        zset *zs = zobj->ptr;
        zskiplist *zsl = zs->zsl;
        zskiplistNode *ln;
        sds ele;

        //找到起始節點
        if (reverse) {
            ln = zsl->tail;
            if (start > 0)
                ln = zslGetElementByRank(zsl,llen-start);
        } else {
            ln = zsl->header->level[0].forward;
            if (start > 0)
                ln = zslGetElementByRank(zsl,start+1);
        }
         //遍歷並返回給客戶端
        while(rangelen--) {
            serverAssertWithInfo(c,zobj,ln != NULL);
            ele = ln->ele;
            addReplyBulkCBuffer(c,ele,sdslen(ele));
            if (withscores)
                addReplyDouble(c,ln->score);
            ln = reverse ? ln->backward : ln->level[0].forward;
        }
    } else {
        serverPanic("Unknown sorted set encoding");
    }
}

上面就是關於有序集SortedSet的添加，刪除，查找的源碼。可以看出SortedSet會根據存放元素的數量選擇ziplist或者哈希表+跳錶兩種數據結構進行實現，之所以源碼看上去很長，主要原因也就是要根據不同的數據結構進行不同的代碼實現。只要掌握了這個核心思路，再看源碼就不會太難。

三、有序集SortedSet命令總結

有序集的邏輯不難，就是代碼有點長，涉及到ziplist，skiplist，dict三套數據結構，其中除了常規的dict之外，另外兩個數據結構內容都不少，準備專門寫文章進行總結，就不在這裡贅述了。本文主要目的是總結一下有序集SortedSet的實現原理。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 通過nodejs將less文件轉為css文件
    已經安裝過nodejs 1，安裝less； dos界面下進入node.js安裝目錄，通過命令npm install less –g 全局進行安裝less.（安裝過程可能需要等待一段時間） 2、先在控制台編譯一遍：lessc 文件路徑\文件名.less（可省略）； 3、在dos界面輸入：文件路徑\文件 ...
  • nodejs文件運行
    電腦中已經安裝nodejs。 cmd進入dos界面，輸入文件路徑；然後輸入>node 文件名.js ...
  • 隨機產生20個單詞
    隨機產生20個單詞 一、問題來源： 老師給了一份專業單詞word，說第二天要全背下來。錯了就五十遍啊五十遍。 然後，有人提出要做一個產生隨機單詞的Demo，來測試自己。 老師表示呵呵，做出來的就可以不用聽寫。 頓時，我就表示，是可忍，孰不可忍啊。這是在侮辱我們啊。這票我幹了，不能讓人看低了。我這麼做 ...
  • 來個Button看一看
    每次寫代碼總會忘記一些東西，又要重新Goooooooooogle，好煩吶~ ...
  • Android系統的三種分屏顯示模式
    本文介紹了Android 7系統原生支持的多視窗分屏顯示及VR系統的兩種分屏顯示模式。 ...
  • protobuf/android 交叉編譯筆記
    protobuf 交叉編譯筆記 目標是使用 android ndk 的工具鏈編譯出 android armeabi v7a 可用的 protobuf 庫。 交叉編譯環境配置 windows 平臺 1. 下載 "NDK x86_64" 或者 "NDK x86" 並解壓縮 2. 下載 "protobuf ...
  • SQL Server 在生產環境中這樣寫存儲過程的坑都避免了嗎？
    概述 最近因為業務的需求寫了一段時間存儲過程，發現之前寫的存儲過程存在一些不嚴謹的地方，特別是TRY...CATCH中嵌套事務的寫法；雖然之前寫的並沒有錯，但是還是埋藏著很大的隱患在裡面。希望這篇文章能給大家一些參考；文章內容有點長還望耐心閱讀。 1.插入測試數據 創建表 DROP TABLE sc ...
  • [20171120]11g select for update skip locked.txt
    [20171120]11g select for update skip locked.txt--//11G在select for update遇到阻塞時可以通過skipped locked跳過阻塞的記錄,測試看看:1.環境:SCOTT@book> @ &r/ver1PORT_STRING VERS ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類