这里只会记录在学习 Redis 源码时觉得比较好玩的地方，不会一五一十的讲细节。
内存分配
zmalloc 在实际 malloc 到的内存前面加一个 size 。
void *zmalloc(size_t size) {
void *ptr = malloc(size+PREFIX_SIZE);
*((size_t*)ptr) = size;
update_zmalloc_stat_alloc(size+PREFIX_SIZE);
return (char*)ptr+PREFIX_SIZE;
}
动态字符串 sds
sds 在基础的 char* 前面加一段 header 来记录信息（类似于 Go 实现）。
// 除了 sdshdr64，还有 sdshdr32、sdshdr16... 区分不同的长度上限
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
sds sdsnewlen(const void *init, size_t initlen) {
...
sh = s_malloc(hdrlen+initlen+1);
s = (char*)sh+hdrlen; // 实际字符串
memcpy(s, init, initlen);
return s;
}
字典 dict
-
基本数据结构
- dictEntry：键值对。（冲突处理：开链）
- dictht：哈希表。记录使用情况用来
rehash - dict
typedef struct dict { dictType *type; // 不同type有不同的hash算法 void *privdata; dictht ht[2]; // 两个 ht 来实现渐进式的 rehash long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict;
哈希算法
-
rehash：冲突元素太多时扩容。通过两个哈希表进行
- 渐进式策略：
- 每次执行操作时转移一个
- 定时每次转移100个
- 渐进式策略：
-
数据操作
- 每次操作前尽可能进行一次
rehash。 -
rehash时，要依次在两个表里查询；其他操作类似。
- 每次操作前尽可能进行一次
跳跃表 zset
- 数据结构
- span
整数集合 intset
- 数据结构
-
encoding记录元素大小，对于小的数字，使用int16_t来节省内存。
-
- resize
- 先分配足够内存，再调用
memmove函数进行搬移 - 单向升级，只有在插入元素的时候，如果
encoding过小时会进行
- 先分配足够内存，再调用
