字符串类型
在redis内部结构中，字符串类型表示为sds（实际类型是char*）。之外，redis还用sdshdr结构体包含了sds类型，优化了很多操作。sdshdr定义如下：
|
1 2 3 4 5 |
struct sdshdr { unsigned int len; // sds长度 unsigned int free; // sds 预留空间长度 char buf[]; // sds指针地址 }; |
上面的结构中，buf所指的概念是可变伸缩数组。它在结构体中不占内存大小。上面的字节大小是8。 如果要获取sds的长度，就可以通过len直接得到，减少了strlen的使用。时间复杂度上是O(1)和O(N)的区别。
二进制安全
我们经常会遇到二进制安全这个概念。比如说，PHP是二进制安全的，C不是二进制安全的。当然，redis也是二进制安全的。所谓的二进制安全，是通过sdshdr中的len来实现的。len记录了sds的长度，即使遇到’\0’，也能正常的包含在字符串中。当然，在C实现中，如果遇到’\0’，会截断字符串。PHP实现中也有类似的结构体去保证数据的完整性。
sds的内存布局
上面提到，sds的实际的类型是char*， 那么怎么通过sds得到sdshdr结构体的地址，进而获取len，free相关数据？理解这一点，先来看下如何创建一个sds字符串。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// 创建sds sds sdsnewlen(const void *init, size_t initlen) { struct sdshdr *sh; // 最后的+1 表示，字符串的最后一位会设置成’\0' if (init) { sh = zmalloc(sizeof(struct sdshdr)+initlen+1); } else { sh = zcalloc(sizeof(struct sdshdr)+initlen+1); } if (sh == NULL) return NULL; sh->len = initlen; sh->free = 0; if (initlen && init) memcpy(sh->buf, init, initlen); // 数据copy sh->buf[initlen] = '\0'; return (char*)sh->buf; } |
首先会创建sdshdr结构体，然后分配相关内存空间，最后把字符串数据copy到buf中。注意最后，返回的是buf地址。 为了回答上面的问题，我们再看下系统的内存分配布局。
系统在执行程序，会分配相应的堆和栈。堆和栈之间的内存空间是相当大的。堆起始地址在内存的低地址，并向高地址分配。而栈正相反。回到上面的问题，内存的分配如下。
由sds地址定位到sdshdr地址，只相差sizeof(struct sdshdr)字节。如果要获得sds的长度，看下redis是怎么实现的。
|
1 2 3 4 5 |
//返回 len 长度 static inline size_t sdslen(const sds s) { struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); return sh->len; } |
通过上面两个图，就很容易明白了。
redis的内存分配策略
在创建sds过程中，我们没有看到malloc等内存分配系统调用，取而代之的是redis自己实现的zmalloc等分配函数。我们来看下zmalloc函数的实现。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void *zmalloc(size_t size) { void *ptr = malloc(size+PREFIX_SIZE); if (!ptr) zmalloc_oom_handler(size); #ifdef HAVE_MALLOC_SIZE update_zmalloc_stat_alloc(zmalloc_size(ptr)); return ptr; #else *((size_t*)ptr) = size; update_zmalloc_stat_alloc(size+PREFIX_SIZE); return (char*)ptr+PREFIX_SIZE; #endif } |
zmalloc实际上调用了malloc，但是多分配了PREFIX_SIZE大小的内存。PREFIX_SIZE定义为size_t，也就是说32位机器是4字节，64位是8字节。
我们看到后面，*((size_t*)ptr) = size; 实际上用PREFIX_SIZE大小的内存指针记录了所分配内存的大小。那么，在redis中，给定一个内存指针，能很快得到这块内存所占的内存大小。 再看下返回值， 返回的还是size分配的内存指针。
redis字符串预分配策略
redis对于value的操作，除了set，还有append。append操作就是把字符串添加到原有字符串的后面。最直观得操作是，获取到新添加字符串的长度，分配内存空间，然后复制字符串。
redis优化了这一模式。结构体中的free字段就派上用场了。
在创建新字符串的时候，free是设置为0的。假设新添加字符串的长度表示为addlen。新字符串的长度应该是len + addlen。 redis在实现中会预先分配内存，总共分配 2 * (len + addlen)大小的内存（这个数值包含原先的内存大小）。free 会赋值为多分配的内存大小。那么以后对字符串再进行append操作的时候，有可能就不会再分配内存了，直接进行复制操作。但从另一方面说，这实际造成了内存的浪费。应该进行少使用append操作。如果碰到append的情况，在应用层面去控制，然后使用set操作。
总的来说，redis使用的空间换时间的思路去执行操作，尽可能减少操作时间。
redis中链表结构
redis也大规模使用了链表结构，在内部实现中，redis使用的是双向链表。redis实现的双向链表并没有什么特殊之处。 在链表结构中，还有一个链表迭代器,用于遍历链表。
|
1 2 3 4 |
typedef struct listIter { listNode *next; // 当前的链表节点 int direction; // 遍历方向， AL_START_HEAD 从头开始；AL_START_TAIL，从尾开始 } listIter; |