<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 簡單動態字符串 [TOC=2,3] Sds (Simple Dynamic String,簡單動態字符串)是 Redis 底層所使用的字符串表示,幾乎所有的 Redis 模塊中都用了 sds。 本章將對 sds 的實現、性能和功能等方面進行介紹,并說明 Redis 使用 sds 而不是傳統 C 字符串的原因。 ### sds 的用途 Sds 在 Redis 中的主要作用有以下兩個: 1. 實現字符串對象(StringObject); 1. 在 Redis 程序內部用作 `char*` 類型的替代品; 以下兩個小節分別對這兩種用途進行介紹。 ### 實現字符串對象 Redis 是一個鍵值對數據庫(key-value DB),數據庫的值可以是字符串、集合、列表等多種類型的對象,而數據庫的鍵則總是字符串對象。 對于那些包含字符串值的字符串對象來說,每個字符串對象都包含一個 sds 值。 Note “包含字符串值的字符串對象”,這種說法初聽上去可能會有點奇怪,但是在 Redis 中,一個字符串對象除了可以保存字符串值之外,還可以保存 `long` 類型的值,所以為了嚴謹起見,這里需要強調一下:當字符串對象保存的是字符串時,它包含的才是 sds 值,否則的話,它就是一個 `long` 類型的值。 舉個例子,以下命令創建了一個新的數據庫鍵值對,這個鍵值對的鍵和值都是字符串對象,它們都包含一個 sds 值: ~~~ redis> SET book "Mastering C++ in 21 days" OK redis> GET book "Mastering C++ in 21 days" ~~~ 以下命令創建了另一個鍵值對,它的鍵是字符串對象,而值則是一個集合對象: ~~~ redis> SADD nosql "Redis" "MongoDB" "Neo4j" (integer) 3 redis> SMEMBERS nosql 1) "Neo4j" 2) "Redis" 3) "MongoDB" ~~~ ### 用 sds 取代 C 默認的 char* 類型 因為 `char*` 類型的功能單一,抽象層次低,并且不能高效地支持一些 Redis 常用的操作(比如追加操作和長度計算操作),所以在 Redis 程序內部,絕大部分情況下都會使用 sds 而不是 `char*` 來表示字符串。 性能問題在稍后介紹 sds 定義的時候就會說到,因為我們還沒有了解過 Redis 的其他功能模塊,所以也沒辦法詳細地舉例說那里用到了 sds ,不過在后面的章節中,我們會經常看到其他模塊(幾乎每一個)都用到了 sds 類型值。 目前來說,只要記住這個事實即可:在 Redis 中,客戶端傳入服務器的協議內容、aof 緩存、返回給客戶端的回復,等等,這些重要的內容都是由 sds 類型來保存的。 ### Redis 中的字符串 在 C 語言中,字符串可以用一個 `\0` 結尾的 `char` 數組來表示。 比如說, `hello world` 在 C 語言中就可以表示為 `"hello world\0"` 。 這種簡單的字符串表示,在大多數情況下都能滿足要求,但是,它并不能高效地支持長度計算和追加(append)這兩種操作: - 每次計算字符串長度(`strlen(s)`)的復雜度為 \(\theta(N)\) 。 - 對字符串進行 N 次追加,必定需要對字符串進行 N 次內存重分配(`realloc`)。 在 Redis 內部,字符串的追加和長度計算很常見,而 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 和 [STRLEN](http://redis.readthedocs.org/en/latest/string/strlen.html#strlen "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/strlen.html#strlen] 更是這兩種操作,在 Redis 命令中的直接映射,這兩個簡單的操作不應該成為性能的瓶頸。 另外,Redis 除了處理 C 字符串之外,還需要處理單純的字節數組,以及服務器協議等內容,所以為了方便起見,Redis 的字符串表示還應該是[二進制安全的](http://en.wikipedia.org/wiki/Binary-safe) [http://en.wikipedia.org/wiki/Binary-safe]:程序不應對字符串里面保存的數據做任何假設,數據可以是以 `\0` 結尾的 C 字符串,也可以是單純的字節數組,或者其他格式的數據。 考慮到這兩個原因,Redis 使用 sds 類型替換了 C 語言的默認字符串表示:sds 既可高效地實現追加和長度計算,同時是二進制安全的。 ### sds 的實現 在前面的內容中,我們一直將 sds 作為一種抽象數據結構來說明,實際上,它的實現由以下兩部分組成: ~~~ typedef char *sds; struct sdshdr { // buf 已占用長度 int len; // buf 剩余可用長度 int free; // 實際保存字符串數據的地方 char buf[]; }; ~~~ 其中,類型 `sds` 是 `char *` 的別名(alias),而結構 `sdshdr` 則保存了 `len` 、 `free` 和 `buf` 三個屬性。 作為例子,以下是新創建的,同樣保存 `hello world` 字符串的 `sdshdr` 結構: ~~~ struct sdshdr { len = 11; free = 0; buf = "hello world\0"; // buf 的實際長度為 len + 1 }; ~~~ 通過 `len` 屬性, `sdshdr` 可以實現復雜度為 \(\theta(1)\) 的長度計算操作。 另一方面,通過對 `buf` 分配一些額外的空間,并使用 `free` 記錄未使用空間的大小,`sdshdr` 可以讓執行追加操作所需的內存重分配次數大大減少,下一節我們就會來詳細討論這一點。 當然,sds 也對操作的正確實現提出了要求 —— 所有處理 `sdshdr` 的函數,都必須正確地更新 `len` 和 `free` 屬性,否則就會造成 bug 。 ### 優化追加操作 在前面說到過,利用 `sdshdr` 結構,除了可以用 \(\theta(1)\) 復雜度獲取字符串的長度之外,還可以減少追加(append)操作所需的內存重分配次數,以下就來詳細解釋這個優化的原理。 為了易于理解,我們用一個 Redis 執行實例作為例子,解釋一下,當執行以下代碼時, Redis 內部發生了什么: ~~~ redis> SET msg "hello world" OK redis> APPEND msg " again!" (integer) 18 redis> GET msg "hello world again!" ~~~ 首先, `SET` 命令創建并保存 `hello world` 到一個 `sdshdr` 中,這個 `sdshdr` 的值如下: ~~~ struct sdshdr { len = 11; free = 0; buf = "hello world\0"; } ~~~ 當執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令時,相應的 `sdshdr` 被更新,字符串 `" again!"` 會被追加到原來的 `"hello world"` 之后: ~~~ struct sdshdr { len = 18; free = 18; buf = "hello world again!\0 "; // 空白的地方為預分配空間,共 18 + 18 + 1 個字節 } ~~~ 注意,當調用 `SET` 命令創建 `sdshdr` 時,`sdshdr` 的 `free` 屬性為 `0` ,Redis 也沒有為 `buf` 創建額外的空間 ——而在執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 之后,Redis 為 `buf` 創建了多于所需空間一倍的大小。 在這個例子中,保存 `"hello world again!"` 共需要 `18 + 1` 個字節,但程序卻為我們分配了 `18 + 18 + 1 = 37` 個字節 ——這樣一來,如果將來再次對同一個 `sdshdr` 進行追加操作,只要追加內容的長度不超過 `free` 屬性的值,那么就不需要對 `buf` 進行內存重分配。 比如說,執行以下命令并不會引起 `buf` 的內存重分配,因為新追加的字符串長度小于 `18` : ~~~ redis> APPEND msg " again!" (integer) 25 ~~~ 再次執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令之后,`msg` 的值所對應的 `sdshdr` 結構可以表示如下: ~~~ struct sdshdr { len = 25; free = 11; buf = "hello world again! again!\0 "; // 空白的地方為預分配空間,共 18 + 18 + 1 個字節 } ~~~ `sds.c/sdsMakeRoomFor` 函數描述了 `sdshdr` 的這種內存預分配優化策略,以下是這個函數的偽代碼版本: ~~~ def sdsMakeRoomFor(sdshdr, required_len): # 預分配空間足夠,無須再進行空間分配 if (sdshdr.free >= required_len): return sdshdr # 計算新字符串的總長度 newlen = sdshdr.len + required_len # 如果新字符串的總長度小于 SDS_MAX_PREALLOC # 那么為字符串分配 2 倍于所需長度的空間 # 否則就分配所需長度加上 SDS_MAX_PREALLOC 數量的空間 if newlen < SDS_MAX_PREALLOC: newlen *= 2 else: newlen += SDS_MAX_PREALLOC # 分配內存 newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1) # 更新 free 屬性 newsh.free = newlen - sdshdr.len # 返回 return newsh ~~~ 在目前版本的 Redis 中,`SDS_MAX_PREALLOC` 的值為 `1024 * 1024` ,也就是說,當大小小于 `1MB` 的字符串執行追加操作時,`sdsMakeRoomFor` 就為它們分配多于所需大小一倍的空間;當字符串的大小大于 `1MB` ,那么 `sdsMakeRoomFor` 就為它們額外多分配 `1MB` 的空間。 Note 這種分配策略會浪費內存嗎? 執行過 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令的字符串會帶有額外的預分配空間,這些預分配空間不會被釋放,除非該字符串所對應的鍵被刪除,或者等到關閉 Redis 之后,再次啟動時重新載入的字符串對象將不會有預分配空間。 因為執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 命令的字符串鍵數量通常并不多,占用內存的體積通常也不大,所以這一般并不算什么問題。 另一方面,如果執行 [APPEND](http://redis.readthedocs.org/en/latest/string/append.html#append "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/append.html#append] 操作的鍵很多,而字符串的體積又很大的話,那可能就需要修改 Redis 服務器,讓它定時釋放一些字符串鍵的預分配空間,從而更有效地使用內存。 ### sds 模塊的 API sds 模塊基于 `sds` 類型和 `sdshdr` 結構提供了以下 API : | 函數 | 作用 | 算法復雜度 | |-----|-----|-----| | `sdsnewlen` | 創建一個指定長度的 `sds` ,接受一個 C 字符串作為初始化值 | \(O(N)\) | | `sdsempty` | 創建一個只包含空白字符串 `""` 的 `sds` | \(O(1)\) | | `sdsnew` | 根據給定 C 字符串,創建一個相應的 `sds` | \(O(N)\) | | `sdsdup` | 復制給定 `sds` | \(O(N)\) | | `sdsfree` | 釋放給定 `sds` | \(O(N)\) | | `sdsupdatelen` | 更新給定 `sds` 所對應 `sdshdr` 結構的 `free` 和 `len` | \(O(N)\) | | `sdsclear` | 清除給定 `sds` 的內容,將它初始化為 `""` | \(O(1)\) | | `sdsMakeRoomFor` | 對 `sds` 所對應 `sdshdr` 結構的 `buf` 進行擴展 | \(O(N)\) | | `sdsRemoveFreeSpace` | 在不改動 `buf` 的情況下,將 `buf` 內多余的空間釋放出去 | \(O(N)\) | | `sdsAllocSize` | 計算給定 `sds` 的 `buf` 所占用的內存總數 | \(O(1)\) | | `sdsIncrLen` | 對 `sds` 的 `buf` 的右端進行擴展(expand)或修剪(trim) | \(O(1)\) | | `sdsgrowzero` | 將給定 `sds` 的 `buf` 擴展至指定長度,無內容的部分用 `\0` 來填充 | \(O(N)\) | | `sdscatlen` | 按給定長度對 `sds` 進行擴展,并將一個 C 字符串追加到 `sds` 的末尾 | \(O(N)\) | | `sdscat` | 將一個 C 字符串追加到 `sds` 末尾 | \(O(N)\) | | `sdscatsds` | 將一個 `sds` 追加到另一個 `sds` 末尾 | \(O(N)\) | | `sdscpylen` | 將一個 C 字符串的部分內容復制到另一個 `sds` 中,需要時對 `sds` 進行擴展 | \(O(N)\) | | `sdscpy` | 將一個 C 字符串復制到 `sds` | \(O(N)\) | `sds` 還有另一部分功能性函數,比如 `sdstolower` 、 `sdstrim` 、 `sdscmp` ,等等,基本都是標準 C 字符串庫函數的 `sds` 版本,這里不一一列舉了。 ### 小結 - Redis 的字符串表示為 `sds` ,而不是 C 字符串(以 `\0` 結尾的 `char*`)。 - 對比 C 字符串, `sds` 有以下特性: - 可以高效地執行長度計算(`strlen`); - 可以高效地執行追加操作(`append`); - 二進制安全; - `sds` 會為追加操作進行優化:加快追加操作的速度,并降低內存分配的次數,代價是多占用了一些內存,而且這些內存不會被主動釋放。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看