Redis 數據結構-簡單動態字元串

来源:https://www.cnblogs.com/taojietaoge/archive/2023/01/09/17036696.html
-Advertisement-
Play Games

Redis 數據結構-簡單動態字元串 無邊落木蕭蕭下,不盡長江滾滾來。 1、簡介 Redis 之所以快主要得益於它的數據結構、操作記憶體資料庫、單線程和多路 I/O 復用模型,進一步窺探下它常見的五種基本數據的底層數據結構。 Redis 常見數據類型對應的的底層數據結構。 String:簡單動態字元串 ...


Redis 數據結構-簡單動態字元串

 

      無邊落木蕭蕭下,不盡長江滾滾來。

 

1、簡介

Redis 之所以快主要得益於它的數據結構、操作記憶體資料庫、單線程和多路 I/O 復用模型,進一步窺探下它常見的五種基本數據的底層數據結構。

Redis 常見數據類型對應的的底層數據結構。

  • String:簡單動態字元串。
  • List:雙向鏈表、壓縮列表。
  • Hash:壓縮列表、哈希表。
  • Sorted Set:壓縮列表、跳錶。
  • Set:哈希表、整數數組。

2、簡單動態字元串

String是Redis 最基本的類型,最大能存儲 512MB 的數據,String類型是二進位安全的,它可以存儲任何數據包括數字、圖片、序列化對象等。雖然Redis 是C 語言寫的,但Redis 中並沒有使用 C 中 char 來表示字元串,而是自定義了一種新的字元串結構 簡單動態字元串(Simple Dynamic Strings,SDS)來存儲字元串和整型數據。

C 語言字元串有以下幾個問題:

  • C 中獲取字元串長度的需要通過運算,複雜度為O(n)。
  • 非二進位安全,不能出現類似於’\0’的字元,因為在C 字元串中,'\0’代表字元串結束。
  • 每一次刪除和增加字元串的長度,都需要重新分配空間。

SDS 結構

例如執行以下命令

set name "tjt"

set命令執行後,Redis將在底層創建兩個SDS,一個是包含name 的SDS,另一個是包含“tjt”的SDS。 

從Redis 源碼的sds.h 文件中可以看到SDS 的結構體。

 從sds.h 源碼中截取出sdshdr8 如下。

1 struct __attribute__ ((__packed__)) sdshdr8 {
2     uint8_t len; /* used */
3     uint8_t alloc; /* excluding the header and null terminator */
4     unsigned char flags; /* 3 lsb of type, 5 unused bits */
5     char buf[];
6 };
  • len: 記錄 char buf [] 數組中已使用位元組的數量,等於 SDS 保存字元串的長度,不包含結束標識符'\0'
  • alloc:記錄 char buf [] 數組申請的總位元組數,不包含結束標識符'\0'
  • buf:位元組數組,用戶保存字元串
  • flags:不同SDS 頭類型,sds 會根據字元串實際的長度,選擇不同的數據結構,節省記憶體空間,更好的提升記憶體效率。當前 sdshdr 結構分為 5 種子類型,分別為 sdshdr5sdshdr8sdshdr16sdshdr32sdshdr64。如下圖對應的幾種SDS_TYPE。

例如,一個包含字元串“tjt"的SDS 結構如下: 

動態字元串SDS 具備動態擴容的能力,例如給SDS 'tjt' 追加一段字元串 ",go”,這裡首先會申請新記憶體空間。

  • 如果新字元串小於1M,則新空間為 擴展後字元串長度的兩倍 + 1;
  • 如果新字元串大於1M,則新空間為 擴展後字元串長度 + 1M +1 ,空間預分配用於優化 SDS 的字元串增長操作。

3、Redis 使用SDS 的優勢

1、SDS可以通過常數級別獲取字元串的長度

redis的結構中存儲了字元串的長度,所以獲取字元串的長度複雜度為O(1),c 中字元串沒記錄長度,需要遍歷整個長度,複雜度為O(N)。

2、杜絕緩衝區溢出

  • 如果在修改字元的時候,沒有分配足夠的記憶體大小,就很容易造成緩存溢出,記憶體越界。
  • strcat 函數常見的錯誤就是數組越界,即兩個字元串連接後,長度超過第一個字元串數組定義的長度,導致越界。
  • SDS 中的空間分配策略可以杜絕這種情況,當對 SDS 進行修改時,API 會檢查 SDS 的空間是否滿足修改所需的要求,如果不滿足的話,API 會自動將 SDS 的空間擴展至執行修改所需的大小,然後才執行實際的修改操作。空間的申請是自動完成的,所以就避免了緩存溢出。

3、減少修改字元串時的記憶體分配次數

  • 對於 C 字元串來說,如果修改字元串的長度,都需要重新執行記憶體分配操作;但是對於 Redis 資料庫來說,如果頻繁執行記憶體分配/釋放操作,必然會對性能產生一定影響。為了避免 C 字元串的缺陷,SDS 採用了空間預分配和惰性空間釋放兩種優化策略。
  • 空間預分配:redis分配的空間不是按照需要的分配,一般會有多餘的空間。所以字元串長度增加時,剩餘的空間足夠,就可以避免重新分配空間,減少修改字元串時的空間分配次數。
  • 惰性釋放:減少字元的長度時也不是直接刪除多餘的內容。而是設置已使用空間的長度,隱藏刪除內容。

4、二進位安全

  • 對於 C 字元串來說,字元串中不能包含空字元,否則最先被程式讀入的空字元串被誤認為是字元串結尾,這使得 C 字元串只能保存文本數據,而不能保存圖片、音視頻等二進位文件。
  • 對於 SDS 來說,採用二進位存儲,所有 SDS 都會以處理二進位的方式來處理 SDS 保存在 buf 數組中的內容,程式不會對裡面的內容做任何限制。

5、Int、Raw和 embstr 動態存儲

簡單動態字元串結構在數據存儲過程中,字元串對象會根據保存值的類型、長度不同,動態匹配三種存儲結構:Int、Raw和 embstr 。

  • Int:如果存儲的是整數值(可以用long表示),則底層存儲結構為Int;
  • raw:如果存儲的是字元串且字元串長度超過39 位元組,則底層存儲結構為raw;
  • embstr:如果存儲的是字元串且字元串長度未超過39 位元組,則底層存儲結構為embstr(需要一塊連續的記憶體空間);
  • embstr 和raw 都使用redisObject 和sdshdr 結構來表示字元串對象,但是raw 會分別兩次創建redisObject 與sdshdr,記憶體不一定是連續的,而embstr 直接創建一塊連續的記憶體。embstr 是一塊連續的記憶體空間,因此其效率上比raw 方式要高。

sds.h 文件完整源碼

  1 /* SDSLib 2.0 -- A C dynamic strings library
  2  *
  3  * Copyright (c) 2006-2015, Salvatore Sanfilippo <antirez at gmail dot com>
  4  * Copyright (c) 2015, Oran Agra
  5  * Copyright (c) 2015, Redis Labs, Inc
  6  * All rights reserved.
  7  *
  8  * Redistribution and use in source and binary forms, with or without
  9  * modification, are permitted provided that the following conditions are met:
 10  *
 11  *   * Redistributions of source code must retain the above copyright notice,
 12  *     this list of conditions and the following disclaimer.
 13  *   * Redistributions in binary form must reproduce the above copyright
 14  *     notice, this list of conditions and the following disclaimer in the
 15  *     documentation and/or other materials provided with the distribution.
 16  *   * Neither the name of Redis nor the names of its contributors may be used
 17  *     to endorse or promote products derived from this software without
 18  *     specific prior written permission.
 19  *
 20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 21  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 23  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 24  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 30  * POSSIBILITY OF SUCH DAMAGE.
 31  */
 32 
 33 #ifndef __SDS_H
 34 #define __SDS_H
 35 
 36 #define SDS_MAX_PREALLOC (1024*1024)
 37 const char *SDS_NOINIT;
 38 
 39 #include <sys/types.h>
 40 #include <stdarg.h>
 41 #include <stdint.h>
 42 
 43 typedef char *sds;
 44 
 45 /* Note: sdshdr5 is never used, we just access the flags byte directly.
 46  * However is here to document the layout of type 5 SDS strings. */
 47 struct __attribute__ ((__packed__)) sdshdr5 {
 48     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 49     char buf[];
 50 };
 51 struct __attribute__ ((__packed__)) sdshdr8 {
 52     uint8_t len; /* used */
 53     uint8_t alloc; /* excluding the header and null terminator */
 54     unsigned char flags; /* 3 lsb of type, 5 unused bits */
 55     char buf[];
 56 };
 57 struct __attribute__ ((__packed__)) sdshdr16 {
 58     uint16_t len; /* used */
 59     uint16_t alloc; /* excluding the header and null terminator */
 60     unsigned char flags; /* 3 lsb of type, 5 unused bits */
 61     char buf[];
 62 };
 63 struct __attribute__ ((__packed__)) sdshdr32 {
 64     uint32_t len; /* used */
 65     uint32_t alloc; /* excluding the header and null terminator */
 66     unsigned char flags; /* 3 lsb of type, 5 unused bits */
 67     char buf[];
 68 };
 69 struct __attribute__ ((__packed__)) sdshdr64 {
 70     uint64_t len; /* used */
 71     uint64_t alloc; /* excluding the header and null terminator */
 72     unsigned char flags; /* 3 lsb of type, 5 unused bits */
 73     char buf[];
 74 };
 75 
 76 #define SDS_TYPE_5  0
 77 #define SDS_TYPE_8  1
 78 #define SDS_TYPE_16 2
 79 #define SDS_TYPE_32 3
 80 #define SDS_TYPE_64 4
 81 #define SDS_TYPE_MASK 7
 82 #define SDS_TYPE_BITS 3
 83 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
 84 #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
 85 #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
 86 
 87 static inline size_t sdslen(const sds s) {
 88     unsigned char flags = s[-1];
 89     switch(flags&SDS_TYPE_MASK) {
 90         case SDS_TYPE_5:
 91             return SDS_TYPE_5_LEN(flags);
 92         case SDS_TYPE_8:
 93             return SDS_HDR(8,s)->len;
 94         case SDS_TYPE_16:
 95             return SDS_HDR(16,s)->len;
 96         case SDS_TYPE_32:
 97             return SDS_HDR(32,s)->len;
 98         case SDS_TYPE_64:
 99             return SDS_HDR(64,s)->len;
100     }
101     return 0;
102 }
103 
104 static inline size_t sdsavail(const sds s) {
105     unsigned char flags = s[-1];
106     switch(flags&SDS_TYPE_MASK) {
107         case SDS_TYPE_5: {
108             return 0;
109         }
110         case SDS_TYPE_8: {
111             SDS_HDR_VAR(8,s);
112             return sh->alloc - sh->len;
113         }
114         case SDS_TYPE_16: {
115             SDS_HDR_VAR(16,s);
116             return sh->alloc - sh->len;
117         }
118         case SDS_TYPE_32: {
119             SDS_HDR_VAR(32,s);
120             return sh->alloc - sh->len;
121         }
122         case SDS_TYPE_64: {
123             SDS_HDR_VAR(64,s);
124             return sh->alloc - sh->len;
125         }
126     }
127     return 0;
128 }
129 
130 static inline void sdssetlen(sds s, size_t newlen) {
131     unsigned char flags = s[-1];
132     switch(flags&SDS_TYPE_MASK) {
133         case SDS_TYPE_5:
134             {
135                 unsigned char *fp = ((unsigned char*)s)-1;
136                 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
137             }
138             break;
139         case SDS_TYPE_8:
140             SDS_HDR(8,s)->len = newlen;
141             break;
142         case SDS_TYPE_16:
143             SDS_HDR(16,s)->len = newlen;
144             break;
145         case SDS_TYPE_32:
146             SDS_HDR(32,s)->len = newlen;
147             break;
148         case SDS_TYPE_64:
149             SDS_HDR(64,s)->len = newlen;
150             break;
151     }
152 }
153 
154 static inline void sdsinclen(sds s, size_t inc) {
155     unsigned char flags = s[-1];
156     switch(flags&SDS_TYPE_MASK) {
157         case SDS_TYPE_5:
158             {
159                 unsigned char *fp = ((unsigned char*)s)-1;
160                 unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
161                 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
162             }
163             break;
164         case SDS_TYPE_8:
165             SDS_HDR(8,s)->len += inc;
166             break;
167         case SDS_TYPE_16:
168             SDS_HDR(16,s)->len += inc;
169             break;
170         case SDS_TYPE_32:
171             SDS_HDR(32,s)->len += inc;
172             break;
173         case SDS_TYPE_64:
174             SDS_HDR(64,s)->len += inc;
175             break;
176     }
177 }
178 
179 /* sdsalloc() = sdsavail() + sdslen() */
180 static inline size_t sdsalloc(const sds s) {
181     unsigned char flags = s[-1];
182     switch(flags&SDS_TYPE_MASK) {
183         case SDS_TYPE_5:
184             return SDS_TYPE_5_LEN(flags);
185         case SDS_TYPE_8:
186             return SDS_HDR(8,s)->alloc;
187         case SDS_TYPE_16:
188             return SDS_HDR(16,s)->alloc;
189         case SDS_TYPE_32:
190             return SDS_HDR(32,s)->alloc;
191         case SDS_TYPE_64:
192             return SDS_HDR(64,s)->alloc;
193     }
194     return 0;
195 }
196 
197 static inline void sdssetalloc(sds s, size_t newlen) {
198     unsigned char flags = s[-1];
199     switch(flags&SDS_TYPE_MASK) {
200         case SDS_TYPE_5:
201             /* Nothing to do, this type has no total allocation info. */
202             break;
203         case SDS_TYPE_8:
204             SDS_HDR(8,s)->alloc = newlen;
205             break;
206         case SDS_TYPE_16:
207             SDS_HDR(16,s)->alloc = newlen;
208             break;
209         case SDS_TYPE_32:
210             SDS_HDR(32,s)->alloc = newlen;
211             break;
212         case SDS_TYPE_64:
213             SDS_HDR(64,s)->alloc = newlen;
214             break;
215     }
216 }
217 
218 sds sdsnewlen(const void *init, size_t initlen);
219 sds sdsnew(const char *init);
220 sds sdsempty(void);
221 sds sdsdup(const sds s);
222 void sdsfree(sds s);
223 sds sdsgrowzero(sds s, size_t len);
224 sds sdscatlen(sds s, const void *t, size_t len);
225 sds sdscat(sds s, const char *t);
226 sds sdscatsds(sds s, const sds t);
227 sds sdscpylen(sds s, const char *t, size_t len);
228 sds sdscpy(sds s, const char *t);
229 
230 sds sdscatvprintf(sds s, const char *fmt, va_list ap);
231 #ifdef __GNUC__
232 sds sdscatprintf(sds s, const char *fmt, ...)
233     __attribute__((format(printf, 2, 3)));
234 #else
235 sds sdscatprintf(sds s, const char *fmt, ...);
236 #endif
237 
238 sds sdscatfmt(sds s, char const *fmt, ...);
239 sds sdstrim(sds s, const char *cset);
240 void sdsrange(sds s, ssize_t start, ssize_t end);
241 void sdsupdatelen(sds s);
242 void sdsclear(sds s);
243 int sdscmp(const sds s1, const sds s2);
244 sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
245 void sdsfreesplitres(sds *tokens, int count);
246 void sdstolower(sds s);
247 void sdstoupper(sds s);
248 sds sdsfromlonglong(long long value);
249 sds sdscatrepr(sds s, const char *p, size_t len);
250 sds *sdssplitargs(const char *line, int *argc);
251 sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
252 sds sdsjoin(char **argv, int argc, char *sep);
253 sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen);
254 
255 /* Low level functions exposed to the user API */
256 sds sdsMakeRoomFor(sds s, size_t addlen);
257 void sdsIncrLen(sds s, ssize_t incr);
258 sds sdsRemoveFreeSpace(sds s);
259 size_t sdsAllocSize(sds s);
260 void *sdsAllocPtr(sds s);
261 
262 /* Export the allocator used by SDS to the program using SDS.
263  * Sometimes the program SDS is linked to, may use a different set of
264  * allocators, but may want to allocate or free things that SDS will
265  * respectively free or allocate. */
266 void *sds_malloc(size_t size);
267 void *sds_realloc(void *ptr, size_t size);
268 void sds_free(void *ptr);
269 
270 #ifdef REDIS_TEST
271 int sdsTest(int argc, char *argv[]);
272 #endif
273 
274 #endif
View Code

 

 

 

 

無邊落木蕭蕭下 不盡長江滾滾來  

 

 

 


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

-Advertisement-
Play Games
更多相關文章
  • 每條if語句的核心都是一個值為True或False的表達式。Python根據條件測試的值為True還是False來決定是否執行if語句中的代碼。如果條件測試的值為True,Python就執行緊跟在if語句後面的代碼;如果為False,Python就忽略這些代碼。 1. 檢查是否相等:將一個變數的當前 ...
  • 最近刷leetcode題,使用了move()函數及優先隊列(堆)priority_queue數據結構,記錄一下! 1.move函數 move(obj)函數的功能是把obj當做右值處理,可以應用在對象的移動上。 右值引用 為了支持移動操作,新標準引入了一種新的引入類型——右值引用,所謂右值引用就是必須 ...
  • 元組 1. 元組:不可變的列表。元組一經創建不能被修改。 2. 表示:用圓括弧()來表示,並用逗號來分隔其中的元素。可通過索引訪問其元素。 3. 訪問:訪問列表元素,指出元組的名稱,再指出元素的索引,並將其放在方括弧內。請求獲取列表元素時,Python只返回該元素,而不包括方括弧和引號。元組訪問與列 ...
  • 2023-01-09 一、Mybatis映射文件 1、映射文件根標簽 mapping標簽: 該標簽中的namespace要求與介面的全類名一致 2、映射文件子標簽 (1)cache(該命名空間的緩衝配置) (2)cache-ref(引用其他命名空間的緩存配置) (3)resultMap(描述如何從數 ...
  • python數據分析與可視化常用庫 numpy+matplotlib+pandas 思維導圖 圖中難免有錯誤,後期隨著學習與應用的深入,會不斷修改更新。 當前版本號:1.0 numpy介紹 NumPy 是什麼? NumPy是使用Python進行科學計算的基礎軟體包。除其他外,它包括: 功能強大的N維 ...
  • 【列表一:操作列表】:這裡總結了操作列表的部分知識,包括使用for迴圈遍歷列表、range()函數介紹、使用range()函數創建數值列表,以及是列表的切片。 ...
  • 前言 前段時間一直使用到word文檔轉pdf或者pdf轉word,尋思著用Java應該是可以實現的,於是花了點時間寫了個文件轉換工具 源碼weloe/FileConversion (github.com) 主要功能就是word和pdf的文件轉換,如下 pdf 轉 word pdf 轉 圖片 word ...
  • 2023-01-09 一、Mybatis核心配置文件概述及根標簽 1、核心配置文件的概述(即“mybatis-config.xml”) MyBatis的配置文件包含了會深深影響MyBatis行為的設置和屬性信息。 2、標簽 (1)configuration(配置) (2)properties(屬性) ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 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 ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...