Redis作为当前使用非常广泛的内存数据库，在代码层面做了很多极致的优化，已获取更好的性能。其中重要的一部分，就是对于底层数据结构的使用。Redis会根据数据量、数据大小等来优化对于不同结构的使用，从而获得更佳的运行效率和内存占用。Redis的核心数据结构包括简单动态字符串、列表、字典、跳跃表、整数集合、压缩列表。

接下来，我们就依次讲讲这些数据结构。

简单动态字符串（SDS）

Redis是用C语言实现的。先复习一下C，C里的字符串中不记录字符串长度，以空字符标记结尾。这样会显而易见的带来三个问题：1.获取字符串长度需要O(n)的复杂度；2.操作不慎会导致缓冲区溢出，例如内存中紧邻的两个字符串，如果对前一个调用strcat拼接其他字符串，就会造成溢出；3. 一些特殊内容，如图像、音频等转成二进制时，难免其中夹杂空字符等特殊字符，这样就无法被C字符串存储了，即C字符串不具备二进制安全性。

而这几点，对于Redis的应用场景来说，影响其实都是非常大的。因此，在redis中定义了一个新的结构，用来保存字符串，即SDS。

SDS的核心思想就是额外使用一个字段记录字符串的长度，这样，上面三个问题就都迎刃而解了。

此外，redis从4.0开始对SDS做了一个代码层面的优化，优化了内存占用，不过不影响其底层逻辑。

这是redis 3.0里SDS的源码：

struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

而这是redis 4.0之后SDS的源码:

...
  struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
Mobility
Mobility
马上订阅 Mobility RSS 更新: http://lichuanyang.top/atom.xml
redis里的数据结构
2020年7月11日 16:47
Redis作为当前使用非常广泛的内存数据库，在代码层面做了很多极致的优化，已获取更好的性能。其中重要的一部分，就是对于底层数据结构的使用。Redis会根据数据量、数据大小等来优化对于不同结构的使用，从而获得更佳的运行效率和内存占用。Redis的核心数据结构包括简单动态字符串、列表、字典、跳跃表、整数集合、压缩列表。
接下来，我们就依次讲讲这些数据结构。
简单动态字符串（SDS）
Redis是用C语言实现的。先复习一下C，C里的字符串中不记录字符串长度，以空字符标记结尾。这样会显而易见的带来三个问题：1.获取字符串长度需要O(n)的复杂度；2.操作不慎会导致缓冲区溢出，例如内存中紧邻的两个字符串，如果对前一个调用strcat拼接其他字符串，就会造成溢出；3. 一些特殊内容，如图像、音频等转成二进制时，难免其中夹杂空字符等特殊字符，这样就无法被C字符串存储了，即C字符串不具备二进制安全性。
而这几点，对于Redis的应用场景来说，影响其实都是非常大的。因此，在redis中定义了一个新的结构，用来保存字符串，即SDS。
SDS的核心思想就是额外使用一个字段记录字符串的长度，这样，上面三个问题就都迎刃而解了。
此外，redis从4.0开始对SDS做了一个代码层面的优化，优化了内存占用，不过不影响其底层逻辑。
这是redis 3.0里SDS的源码：
1
2
3
4
5
struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};
而这是redis 4.0之后SDS的源码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
  struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章
🍊
柑橘 RSS
订阅源浏览器信息
Mobility
Mobility
马上订阅 Mobility RSS 更新: http://lichuanyang.top/atom.xml
redis里的数据结构
2020年7月11日 16:47
Redis作为当前使用非常广泛的内存数据库，在代码层面做了很多极致的优化，已获取更好的性能。其中重要的一部分，就是对于底层数据结构的使用。Redis会根据数据量、数据大小等来优化对于不同结构的使用，从而获得更佳的运行效率和内存占用。Redis的核心数据结构包括简单动态字符串、列表、字典、跳跃表、整数集合、压缩列表。
接下来，我们就依次讲讲这些数据结构。
简单动态字符串（SDS）
Redis是用C语言实现的。先复习一下C，C里的字符串中不记录字符串长度，以空字符标记结尾。这样会显而易见的带来三个问题：1.获取字符串长度需要O(n)的复杂度；2.操作不慎会导致缓冲区溢出，例如内存中紧邻的两个字符串，如果对前一个调用strcat拼接其他字符串，就会造成溢出；3. 一些特殊内容，如图像、音频等转成二进制时，难免其中夹杂空字符等特殊字符，这样就无法被C字符串存储了，即C字符串不具备二进制安全性。
而这几点，对于Redis的应用场景来说，影响其实都是非常大的。因此，在redis中定义了一个新的结构，用来保存字符串，即SDS。
SDS的核心思想就是额外使用一个字段记录字符串的长度，这样，上面三个问题就都迎刃而解了。
此外，redis从4.0开始对SDS做了一个代码层面的优化，优化了内存占用，不过不影响其底层逻辑。
这是redis 3.0里SDS的源码：
1
2
3
4
5
struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};
而这是redis 4.0之后SDS的源码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
  struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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...剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章