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 种子类型，分别为 sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。如下图对应的几种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
无边落木萧萧下
不尽长江滚滚来
 

最新文章

  1. ASP.NET MVC5+EF6+EasyUI 后台管理系统（71）-微信公众平台开发-公众号管理
  2. Javascript提交表单
  3. SPOJ DISUBSTR ——后缀数组
  4. ApsCMS AspCms_SettingFun.asp、AspCms-qqkfFun.asp、AspCms_Slide.asp、AspCms_StyleFun.asp、login.asp、AspCms_CommonFun.asp Vul
  5. linux下python版webshell后门查杀工具
  6. linux+asp.net core+nginx+sql server
  7. jquery选择器及效率问题
  8. 吧php脚本打包成 exe程序
  9. J2SE知识点摘记(二十四)
  10. Ubuntu系统中初次下载Android源码的一点经验
  11. a标签href跳转---传值---禁止单引号
  12. 撸基础篇系列，JAVA的NIO部分
  13. Excel 数据导出
  14. 阿森纳vs托特纳姆热刺
  15. MacBook使用笔记1 - 快捷键与命令学习
  16. C#容器类，性能介绍
  17. [python][spark]wholeTextFiles 读入多个文件的例子
  18. QML常用控件
  19. Pollard Rho大质数分解学习笔记
  20. 微信小程序——template的循环嵌套

热门文章

  1. Kubeadm部署高可用K8S集群
  2. 深入浅出TCP与IP协议笔记
  3. 三、Go环境安装
  4. 【YOLOv5】手把手教你使用LabVIEW ONNX Runtime部署 TensorRT加速，实现YOLOv5实时物体识别（含源码）
  5. python简单的tcp服务端
  6. 我的 React 最佳实践
  7. CSS基础知识筑基
  8. python字符串的一些操作
  9. 2流高手速成记（之七）：基于Dubbo&amp;Nacos的微服务简要实现
  10. miniconda使用