［Redis源碼閱讀］sds字元串實現

来源:http://www.cnblogs.com/hoohack/archive/2017/11/13/7824972.html
-Advertisement-
Play Games

從開始工作就開始使用Redis，也有一段時間了，但都只是停留在使用階段，沒有往更深的角度探索，每次想讀源碼都止步在閱讀書籍上，因為看完書很快又忘了，這次逼自己先讀代碼。因為個人覺得寫作需要閱讀文字來增強靈感，那麼寫代碼的，就閱讀更多代碼來增強靈感吧。 ...


初衷

從開始工作就開始使用Redis，也有一段時間了，但都只是停留在使用階段，沒有往更深的角度探索，每次想讀源碼都止步在閱讀書籍上，因為看完書很快又忘了，這次逼自己先讀代碼。因為個人覺得寫作需要閱讀文字來增強靈感，那麼寫代碼的，就閱讀更多代碼來增強靈感吧。

redis的實現原理，在《Redis設計與實現》一書中講得很詳細了，但是想通過結合代碼的形式再深入探索，加深自己的理解，現在將自己探索的心得寫在這兒。

sds結構體的定義

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7

// sds結構體，使用不同的結構體來保存不同長度大小的字元串
typedef char *sds;

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* flags共8位，低三位保存類型標誌，高5位保存字元串長度，小於32(2^5-1) */
    char buf[]; // 保存具體的字元串
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字元串長度，buf已用的長度 */
    uint8_t alloc; /* 為buf分配的總長度，alloc-len就是sds結構體剩餘的空間 */
    unsigned char flags; /* 低三位保存類型標誌 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

sds結構體從4.0開始就使用了5種header定義，節省記憶體的使用，但是不會用到sdshdr5，我認為是因為sdshdr5能保存的大小較少，2^5=32，因此就不使用它。

其他的結構體保存了len、alloc、flags以及buf四個屬性。各自的含義見代碼的註釋。

sds結構體的獲取

上面可以看到有5種結構體的定義，在使用的時候是通過一個巨集來獲取的：

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

"##"被稱為連接符，它是一種預處理運算符， 用來把兩個語言符號(Token)組合成單個語言符號。比如SDS_HDR(8, s)，根據巨集定義展開是：

((struct sdshdr8 *)((s)-(sizeof(struct sdshdr8))))

而具體使用哪一個結構體，sds底層是通過flags屬性與SDS_TYPE_MASK做與運算得出具體的類型（具體的實現可見下麵的sdslen函數），然後再根據類型去獲取具體的結構體。

sds特性的實現

在Redis設計與實現一書中講到，相比C字元串而言，sds的特性如下：

  • 常數複雜度獲取字元串長度
  • 杜絕緩衝區溢出
  • 減少記憶體重新分配次數
  • 二進位安全

那麼，它是怎麼做到的呢？看代碼。

常數複雜度獲取字元串長度

因為sds將長度屬性保存在結構體中，所以只需要讀取這個屬性就能獲取到sds的長度，具體調用的函數時sdslen，實現如下：

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

可以看到，函數是根據類型調用SDS_HDR巨集來獲取具體的sds結構，然後直接返回結構體的len屬性。

杜絕緩衝區溢出

對於C字元串的操作函數來說，如果在修改字元串的時候忘了為字元串分配足夠的空間，就有可能出現緩衝區溢出的情況。而sds中的API就不會出現這種情況，因為它在修改sds之前，都會判斷它是否有足夠的空間完成接下來的操作。

拿書中舉例的sdscat函數來看，如果strcat想在原來的"Redis"字元串的基礎上進行字元串拼接的操作，但是沒有檢查空間是否滿足，就有可能會修改了"Redis"字元串之後使用到的記憶體，可能是其他結構使用了，也有可能是一段沒有被使用的空間，因此有可能會出現緩衝區溢出。但是sdscat就不會，如下麵代碼所示：

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}

從代碼中可以看到，在執行memcpy將字元串寫入sds之前會調用sdsMakeRoomFor函數去檢查sds字元串s是否有足夠的空間，如果沒有足夠空間，就為其分配足夠的空間，從而杜絕了緩衝區溢出。sdsMakeRoomFor函數的實現如下：

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* 只有有足夠空間就馬上返回，否則就繼續執行分配空間的操作 */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // SDS_MAX_PREALLOC == 1MB，如果修改後的長度小於1M，則分配的空間是原來的2倍，否則增加1MB的空間
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 新增空間後超過當前類型的長度，使用malloc，並把原字元串拷貝過去 */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type; // 給類型標誌位賦值
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

減少記憶體分配操作

sds字元串的很多操作都涉及到修改字元串內容，比如sdscat拼接字元串、sdscpy拷貝字元串等等。這時候就需要記憶體的分配與釋放，如果每次操作都分配剛剛好的大小，那麼對程式的性能必定有影響，因為記憶體分配涉及到系統調用以及一些複雜的演算法。

sds使用了空間預分配以及惰性空間釋放的策略來減少記憶體分配操作。

空間預分配

前面提到，每次涉及到字元串的修改時，都會調用sdsMakeRoomFor檢查sds字元串，如果大小不夠再進行大小的重新分配。sdsMakeRoomFor函數有下麵這幾行判斷：

// SDS_MAX_PREALLOC == 1MB，如果修改後的長度小於1M，則分配的空間是原來的2倍，否則增加1MB的空間
if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

函數判斷字元串修改後的大小，如果修改後的長度小於1M，則分配給sds的空間是原來的2倍，否則增加1MB的空間。

惰性空間釋放

如果操作後減少了字元串的大小，比如下麵的sdstrim函數，只是在最後修改len屬性，不會馬上釋放多餘的空間，而是繼續保留多餘的空間，這樣在下次需要增加sds字元串的大小時，就不需要再為其分配空間了。當然，如果之後檢查到sds的大小實在太大，也會調用sdsRemoveFreeSpace函數釋放多餘的空間。

sds sdstrim(sds s, const char *cset) {
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    /* 從頭部和尾部逐個字元遍歷往中間靠攏，如果字元在cest中，則繼續前進 */
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > sp && strchr(cset, *ep)) ep--;
    len = (sp > ep) ? 0 : ((ep-sp)+1); // 全部被去除了，長度就是0
    if (s != sp) memmove(s, sp, len); // 拷貝內容
    s[len] = '\0';
    sdssetlen(s,len);
    return s;
}

二進位安全

二進位安全指的是只關心二進位化的字元串，不關心具體格式。只會嚴格的按照二進位的數據存取，不會妄圖以某種特殊格式解析數據。比如遇到'\0'字元不會停止解析。

對於C字元串來說，strlen是判斷遇到'\0'之前的字元數量。如果需要保存二進位的數據，就不能通過傳統的C字元串來保存，因為獲取不到它真實的長度。而sds字元串是通過len屬性保存字元串的大小，所以它是二進位安全的。

其他小函數實現

在閱讀源碼的過程中，也發現了兩個個人比較感興趣趣的函數：

  • sdsll2str（將long long類型的整型數字轉成字元串）
  • sdstrim （去除頭部和尾部的指定字元）

我這兩個函數拉出來做了測試，在項目的redis-4.0/tests目錄下。sdstrim函數的實現源碼上面有列出，看看sdsll2str的實現：

int sdsll2str(char *s, long long value) {
    char *p, aux;
    unsigned long long v;
    size_t l;

    /* 通過取餘數得到原字元串的逆轉形式 */
    v = (value < 0) ? -value : value;
    p = s;
    do {
        *p++ = '0'+(v%10);
        v /= 10;
    } while(v);
    if (value < 0) *p++ = '-';

    /* Compute length and add null term. */
    l = p-s;
    *p = '\0';

    /* 反轉字元串 */
    p--;
    while(s < p) {
        aux = *s;
        *s = *p;
        *p = aux;
        s++;
        p--;
    }
    return l;
}

函數是通過不斷取餘數，得到原字元串的逆轉形式，接著，通過從尾部開始將字元逐個放到字元串s中，看起來像是一個反轉操作，從而實現了將整型轉為字元串的操作。

覺得感興趣是因為sdsll2str這個函數在之前學習C語言的時候經常能看到作為問題出現，能看到如此簡潔的實現，表示眼前一亮。而在PHP開發時經常使用trim函數，所以想看看它們的區別。

總結

通過詳細地閱讀sds的源碼，不僅學習到sds的實現細節，還學習到了一些常用字元串操作函數的實現。如果只是僅僅看看數據結構的定義也可以初步瞭解，但是要深入瞭解的話還是需要詳細的閱讀具體函數的實現代碼。還是那句，寫代碼的，需要閱讀更多代碼來增強靈感。

我在github有對Redis源碼更詳細的註解。感興趣的可以圍觀一下，給個star。Redis4.0源碼註解。可以通過commit記錄查看已添加的註解。

原創文章，文筆有限，才疏學淺，文中若有不正之處，萬望告知。

更多精彩內容，請關註個人公眾號。


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

-Advertisement-
Play Games
更多相關文章
  • 簡易RPC框架-代理
    代理 代理的意思就是請求者不直接與終端交互，而是通過一個中間者來做請求轉發，舉幾個生活中的代理案例： 翻牆上網 國外有很多網站在國內不能訪問，所以就需要利用一個代理中轉發請求，達到瞞天過海的目的。 用戶炒股 要想投資股票，你只能通過在證券商那開通賬戶然後，通過在證券商那提供的功能才能實現在上海證券交 ...
  • SQLAlchemy外鍵的使用
    orm可以將資料庫存儲的數據封裝成對象，同時，如果封裝的好的話，所有的資料庫操作都可以封裝到對象中。這樣的代碼在組織結構上會非常的清晰，並且相對與使用sql語句在sql註入方面會極具降低。 SQLAlchemy中的映射關係有四種，分別是一對多，多對一，一對一，多對多 實現這種映射關係只需要外鍵(Fo ...
  • 分散式系統中有關一致性的理解
    首先什麼是一致性？ 一致性就是分散式系統中相互獨立多個節點就某個值達成一致。 具體可分為強一致性和弱一致性。 強一致性：在任意時刻，所有節點中的數據是一樣的。同一時間點，你在節點A中獲取到key1的值與在節點B中獲取到key1的值應該都是一樣的。 弱一致性：不保證任意時刻所有節點數據一樣，有很多不同 ...
  • 一起寫框架-MVC框架-基礎功能-ServletAPI的動態綁定(五)
    實現功能 以上的代碼實現了通過路徑執行對應的執行方法，但執行方法的參數是必須需要傳入請求後響應的參數的。 分別為：HttpServletRequest和HttpServletResponse。然後通過這個兩個對象獲得參數和處理參數。 需求：我們希望根據方法聲明的參數列表決定是否需要ServletAP ...
  • 微服務化路上的隻言片語
    類似於雜談性質的文，總結下公司實行微服務化上遇到的一些問題。 雖然參與了開發過程，但整體更像是個旁觀者，前期還是大家討論怎麼做，後來慢慢就由負責架構的同事專職做規劃，拆分任務去完成。 萬事開頭難 最初的架構(資料庫和其他部分都做了簡化) 初衷並不是為了趕時髦，為了團隊KPI之類的，而是遇到了一個很現 ...
  • SqlServer 資料庫附加問題:不是主資料庫文件
    一、前言 今天公司要切換資料庫伺服器，資料庫文件大於2G，結果再附加到另一伺服器的資料庫裡面，就產生了一個問題。如下： 二、解決方案 在網上找了很多方法，最後在CSDN上找到了相關的解決方式，經測試可用。 網上看到的整理了一下。 在SQL Server 7.0中，微軟推出了 和`sp_attach_ ...
  • [20171113]修改表結構刪除列相關問題.txt
    [20171113]修改表結構刪除列相關問題.txt--//維護表結構刪除欄位一般都是先ALTER TABLE <table_name> SET UNUSED (<column_name>);--//然後等空閑時候刪除列.ALTER TABLE <table_name> DROP UNUSED CO ...
  • SQL註入(轉)
    轉自維基百科: SQL註入是一種代碼註入技術，用於攻擊數據驅動的應用程式，在這種應用程式中，惡意的SQL語句被插入輸入欄位中執行（例如將資料庫內容轉儲給攻擊者）。[1] SQL註入必須利用應用程式軟體中的安全漏洞，例如，當用戶輸入被錯誤地過濾為嵌入在SQL語句中的字元串文字 轉義字元，或者用戶輸入沒 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類