redis学习笔记

redis是一个key-value存储系统。和Memcached类似，它的效率很高。目前推出了LIN版

本和WIN版本.虽然不怎么使用数据库，但是抱着开卷有益的心态，我学习了下其中的数

据结构，还是受益良多的。

参考 <Redis 设计与实现> 黄健宏 (huangz1990).

1、内存管理 redis使用内存头加内存结构 redist支持多个系统，分配的内存的方式也有多种。

代码中并没有使用引用计数等复杂技术，直接根据根据宏来决定使用tc_malloc(size)或者je_malloc(size)或者其他库函数。

<code>/* Explicitly override malloc/free etc when using tcmalloc. */</code>

<code>#if defined(USE_TCMALLOC)</code>

<code>#define malloc(size) tc_malloc(size)</code>

<code>#define calloc(count,size) tc_calloc(count,size)</code>

<code>#define realloc(ptr,size) tc_realloc(ptr,size)</code>

<code>#define free(ptr) tc_free(ptr)</code>

<code>#elif defined(USE_JEMALLOC)</code>

<code>#define malloc(size) je_malloc(size)</code>

<code>#define calloc(count,size) je_calloc(count,size)</code>

<code>#define realloc(ptr,size) je_realloc(ptr,size)</code>

<code>#define free(ptr) je_free(ptr)</code>

<code>#endif</code>

内存头中包含内存大小尺寸。

（win系统下）

___________________________________

| 内存尺寸 |

内存

|________ _|________________________|

获取内存大小时候即通过内存地址减去内存头的大小可以轻易获取内存头及内存头中尺寸的信息。内存大小以sizeof(long)对齐.

<code>#define PREFIX_SIZE (sizeof(size_t))</code>

<code>#ifndef HAVE_MALLOC_SIZE</code>

<code>size_t zmalloc_size(</code><code>void</code>

<code>*realptr = (</code><code>char</code><code>*)ptr-PREFIX_SIZE;</code>

<code> </code><code>size_t size = *((size_t*)realptr);</code>

<code> </code><code>/* Assume at least that all the allocations are padded at sizeof(long) by</code>

<code> </code><code>* the underlying allocator. */</code>

<code>(size&(</code><code>sizeof</code><code>(</code><code>long</code><code>)-1)) size +=</code><code>sizeof</code><code>(</code><code>long</code><code>)-(size&(</code><code>sizeof</code><code>(</code><code>long</code><code>)-1));</code>

<code> </code><code>return</code>

<code>size+PREFIX_SIZE;</code>

以一个变量used_memory统计分配的内存总量分配或者释放内存对变量加上或者减去分配释放的内存量

代码中使用两个宏来记录内存量的变化

update_zmalloc_stat_alloc与update_zmalloc_stat_free(__n)

其实也就是在used_memory这个变量上加减分配释放的内存量需要注意的有两点：

1、对于内存长度按sizeof（ULONG）对齐 size_t _n = (__n); \

if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1));

2、线程安全下使用了锁， pthread_mutex_lock(&used_memory_mutex);

pthread_mutex_unlock(&used_memory_mutex);

在windows系统下，根据宏来看，即是使用了CRITICAL_SECTION。

#define pthread_mutex_lock EnterCriticalSection

#define pthread_mutex_unlock LeaveCriticalSection

/////////////////////////////////////////////////////

2、redis字符串sds

redis使用的字符串其实本质也就是char字符串，不过添加了头描述其长度和剩余空间。这样在使用数据库时候，进行长度调整就比较方便。

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

_______________________________________

| len | free

| char buf[]

|_______|_____ |______________|_________|

而获取SDS长度和可用空间即从SDS的地址减去（前移）SDSHDR的长度，再来获取长度和可用空间

static inline size_t sdslen(const sds s)

{

struct sdshdr* sh = (struct sdshdr*)(s-sizeof(sdshdr)); return

sh->len;

}

static inline size_t sdsavail(const sds s)

{

struct sdshdr* sh = (struct sdshdr*)(s-sizeof(sdshdr));

return sh->free;

sdsnewlen这个函数是创建sds字符串的主体函数，无论是创建空sds字符串(sdsempty()

函数)还是初始化一个指定char字符串的sds字符串(sdsnew(const char *init)函数)或

者复制一个sds字符串(dsdup(const sds s)函数)最终经过创建内容和长度的计算后都汇

聚到sdsnewlen这个函数中来了。 sdsnewlen()函数处理流程如下: 分配长度为初始化字符串长度+1+sds头长度的内存块

sds头len设置为初始化长度initlen。讲指定初始化char字符串的内容拷贝进sds的buf中，最后一位填入‘\0‘;

<code>sds sdsnewlen(</code><code>const</code>

<code>void</code> <code>*init, size_t initlen) {</code>

<code>struct</code>

<code>sdshdr *sh;</code>

<code>sh = malloc(</code><code>sizeof</code><code>(</code><code>struct</code>

<code>sdshdr)+initlen+1);</code>

<code>if</code> <code>(sh == NULL)</code><code>return</code>

<code>sh->len = (</code><code>int</code><code>)initlen;</code>

<code>if</code> <code>(initlen)</code>

<code>if</code> <code>(init) memcpy(sh->buf, init, initlen);</code>

<code>memset(sh->buf,0,initlen);</code>

<code>sh->buf[initlen] =</code><code>‘\0‘</code><code>;</code>

<code>return</code>

我们试着分析下创建一个 redis 这个包含5个字符串的流程首先是用户输入，到代码这一层即调用sdsnew("redis");

改函数计算出字符串的长度

然后调用sdsnewlen("redis",5); 最后创建的内存块如下:

___________________

| 5| 0|

"redis" |

|__|____|___________|

^ ^

sh sh->buf

注意：sdsnewlen返回的是sh->buf

其他函数类似基本都是char字符串操作的SDS版本不过要配合修改sds头的len和 free

的值。

///////////////////////////////////////////////////// 3、redis哈希词典dict

用哈希的方法对指定的值进行分类，通过key在字典中对其进行快速查找。

哈希方法为dictGenHashFunction函数哈希初始值为5381 素数。

通过哈希值*33依次加上需要哈希的值的每个char值，得出最终哈希索引值。

<code>static</code>

<code>unsigned</code><code>int</code>

<code>dictGenHashFunction(</code><code>const</code>

<code>unsigned</code><code>char</code>

<code>while</code>

几个初始化的相关函数都很简单，顾名思义 _dictReset 将dict结构体的几个值置零 _dictInit调用_dictReset

将dict置零，赋值type和privdata。 dictCreate分配内存调用_dictInit初始化。

接着是 win32版本的dictExpand函数。扩展哈希表的容量，重新计算一个新哈希表来分

类保存已有的值。 redis哈希采用链表方式解决哈希碰撞问题，即两个不同值哈希到同一个索引值的情况下

,用链表将其连接起来，但是对于固定哈希表大小来说，随着值越来越多，同一哈希索引

下的值也越来越多，那么查找的时候可能需要遍历大半个链表。查找效率会越来越低下

。那么需要扩展哈希表的大小，将所有哈希值重新以新哈希表的大小来进行计算。避免

同一哈希索引下的链表过长，提高小轮车。 dictExpand处理流程:

计算扩展哈希表需要的大小，调用_dictNextPower函数获得最接近当前哈希表大小的2的

平方数()。范围为4-2147483647L 各种错误检测，按计算出的新大小分配内存，即新的哈希字典。由指针变量dict* n指向

这块新分配内存。依次遍历旧表的每个哈希索引项 for (i = 0; i < ht->size &&

ht->used > 0; i++)

对每个索引项下的各个值重新以新表再次计算索引值并插入新哈希字典。

<code>dictEntry *he, *nextHe;</code>

<code>if</code> <code>(ht->table[i] == NULL)</code><code>continue</code><code>;</code>

<code>/* For each hash entry on this slot... */</code>

<code>he = ht->table[i];</code>

<code>while</code><code>(he) {</code>

<code>nextHe = he->next;</code>

<code>/* Get the new element index */</code>

<code>h = dictHashKey(ht, he->key) & n.sizemask;</code>

<code>he->next = n.table[h];</code>

<code>n.table[h] = he;</code>

<code>/* Pass to the next element */</code>

<code>he = nextHe;</code>

<code>最后释放旧表指向的哈希字典，将n指向的地址复制给旧表指针。</code>

<code>free(ht->table);</code>

<code>/* Remap the new hashtable in the old */</code>

dictAdd函数,顾名思义将值添加进指定的字典里首先调用_dictKeyIndex计算该值在哈希字典里的索引值，如果已经存在则得到-1返回值

然后分配内存。复制需要哈希的值到内存中，将内存插入哈希字典。由于插入值类型的不同，所以复制需要哈希的值使用了专门的宏dictSetHashKey和

dictSetHashVal调用该插入值类型的赋值函数。

dictReplace函数为替换在哈希字典中的值。首先调用dictAdd函数，成功则直接返回1.

不成功则调用dictFind在字典中查找该值(已经确定其存在，否则dictAdd则成功)。调用

宏dictSetHashVal替换其值，并且调用宏dictFreeEntryVal释放原来的值

其他函数多半是哈希碰撞后操作链表，插入，删除。

难点和重点在于rehash，也是涉及到哈希表扩容,之前提到的dictExpand函数.

扩容的原因已经在之前说明，解决哈希碰撞后链表过长影响效率的问题。那么什么时候rehash，如何防止查询、写入的时候rehash出问题呢? Redis

设计与实现是这么说的 Redis实际上是有两个哈希表的。rehash状态下是逐步，将表1的值移动到表2中.ht[0]->ht[1]

,rehashidx则表示ht[0]中哪些索引已经处理移动到ht[1]中了。rehash期间，有插入的动作都是插入到ht[1]新字典中.而改动读取则需要自行判断在哪个ht中。

redis学习笔记

继续阅读

C/C++头文件、函数使用说明

SOFTICE 使用说明 (断点)

DOS命令(2) 磁盘操作类命令

在DOS下运行不了ipconfig命令

tabpanel 使用问题

c写文件

对于0-1分数规划的Dinkelbach算法的分析

不用iconv函数实现UTF-8编码转换GB2312的PHP函数

浮点数计算精度控制

C#多线程——前台线程和后台线程

Android – ListView 中添加按钮，动态删除添加ItemView的操作

IE8 CSS设置DIV居中，添加“margin:0 auto”

Small tricks

C++ 第十五周报告1--《冒泡法排序》

[转]九大排序算法——C语言实现及详解

QR码编码原理三（日本汉字和中文编码）