首页 数据库 mysql教程 Redis源码研究

Redis源码研究

Jun 07, 2016 pm 05:39 PM
redis 源码 研究

计划每天花1小时学习Redis 源码。在博客上做个记录。 --------6月18日----------- redis的字典dict主要涉及几个数据结构, dictEntry:具体的k-v链表结点 dictht:哈希表 dict:字典 具体关系为 1 typedef struct dict { 2 dictType * type; 3 void * privda

计划每天花1小时学习Redis 源码。在博客上做个记录。

--------6月18日-----------

redis的字典dict主要涉及几个数据结构,

dictEntry:具体的k-v链表结点

dictht:哈希表

dict:字典

具体关系为

1 typedef struct dict { 2 dictType *type; 3 void *privdata; 4 dictht ht[2]; iterators; } dict;

1 typedef struct dictht { 2 dictEntry **table; 3 unsigned long size; 4 unsigned long sizemask; 5 unsigned long used; 6 } dictht;

1 typedef struct dictEntry { 2 void *key; 3 union { 4 void *val; 5 uint64_t u64; 6 int64_t s64; 7 } v; 8 struct dictEntry *next; 9 } dictEntry;

一个字典有两个哈希表, 冲突后采用了链地址法,很好理解。

一些简单操作采用了宏

#define dictGetKey(he) ((he)->key) #define dictGetVal(he) ((he)->v.val) #define dictGetSignedIntegerVal(he) ((he)->v.s64) #define dictGetUnsignedIntegerVal(he) ((he)->v.u64)

 ------------6月19日----------------------

字典具体用到了两种哈希算法,我只看了简单的那一种,没想到代码竟然可以那么少,算法名字为djb2,

unsigned int dictGenCaseHashFunction(const unsigned char *buf, int len) { 3 unsigned int hash = (unsigned int)dict_hash_function_seed; (len--) hash; 8 }

dict_hash_function_seed是个全局变量,为5381.
The magic of number 33 (why it works better than many other constants, prime or not) has never been adequately explained.
JDK中采用的哈希算法取得数字是31,一个素数。
创建一个新字典并初始化:

1 dict *dictCreate(dictType *type, void *privDataPtr){ 2 dict *d = malloc(sizeof(*d)); 3 _dictInit(d,type,privDataPtr); 4 return d; 5 } _dictInit(dict *d, dictType *type, void *privDataPtr){ 8 _dictReset(&d->ht[0]); 9 _dictReset(&d->ht[1]); 10 11 d->type = type; 12 d->privdata = privDataPtr; 13 d->rehashidx = -1; 14 d->iterators = 0; DICT_OK; 17 } _dictReset(dictht *ht){ 20 ht->table = NULL; 21 ht->size = 0; 22 ht->sizemask = 0; 23 ht->used = 0; 24 } 

学了这么多年c语言了,malloc(sizeof(*d))我还是第一次看到。
说到sizeof,我还要提一句,c99之后,sizeof是运行时确定的,c99还加入了动态数组这一概念。csdn上的回答是错的。
对字典进行紧缩处理,让 哈希表中的数/哈希表长度接近1:

1 int dictResize(dict *d){ 2 int minimal; (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR; 5 6 minimal = d->ht[0].used; (minimal DICT_HT_INITIAL_SIZE) 9 minimal = DICT_HT_INITIAL_SIZE; dictExpand(d, minimal); 12 } dictIsRehashing(ht) ((ht)->rehashidx != -1) 15 #define DICT_HT_INITIAL_SIZE 4

当字典正在Rehash的时候不能进行Resize操作,初始时哈希表大小为4,哈希表大小一般都是2的幂次方。
如果minimal是5,经过dictExpand后,哈希表大小变为8.

1 static unsigned long _dictNextPower(unsigned long size){ 2 unsigned long i = DICT_HT_INITIAL_SIZE; (size >= LONG_MAX) return LONG_MAX; 5 while(1) { 6 if (i >= size) 7 return i; 8 i *= 2; 9 } 10 } dictExpand(dict *d, unsigned long size){ unsigned long realsize = _dictNextPower(size); the size is invalid if it is smaller than the number of (dictIsRehashing(d) || d->ht[0].used > size) 20 return DICT_ERR; n.size = realsize; 24 n.sizemask = realsize-1; 25 n.table = zcalloc(realsize*sizeof(dictEntry*)); 26 n.used = 0; Is this the first initialization? If so it's not really a rehashing (d->ht[0].table == NULL) { 31 d->ht[0] = n; 32 return DICT_OK; 33 } d->ht[1] = n; 37 d->rehashidx = 0; DICT_OK; 40 }

新建了一个哈希表n,size是扩展后的size,,ht[0].table 为空说明这是第一次初始化,不是扩展,直接赋值。
ht[0].table 不为空,说明这是一次扩展,把n赋给ht[1],ReHash标志rehashix也被设为0.
上边这段不大好理解,先看后面的,一会返过来再研究dictExpand函数。
--------------------6月20日--------------------------

向字典中添加元素需要调用dictAdd函数:
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

热门话题

Java教程
1660
14
CakePHP 教程
1417
52
Laravel 教程
1311
25
PHP教程
1261
29
C# 教程
1234
24
redis集群模式怎么搭建 redis集群模式怎么搭建 Apr 10, 2025 pm 10:15 PM

Redis集群模式通过分片将Redis实例部署到多个服务器,提高可扩展性和可用性。搭建步骤如下:创建奇数个Redis实例,端口不同;创建3个sentinel实例,监控Redis实例并进行故障转移;配置sentinel配置文件,添加监控Redis实例信息和故障转移设置;配置Redis实例配置文件,启用集群模式并指定集群信息文件路径;创建nodes.conf文件,包含各Redis实例的信息;启动集群,执行create命令创建集群并指定副本数量;登录集群执行CLUSTER INFO命令验证集群状态;使

redis数据怎么清空 redis数据怎么清空 Apr 10, 2025 pm 10:06 PM

如何清空 Redis 数据:使用 FLUSHALL 命令清除所有键值。使用 FLUSHDB 命令清除当前选定数据库的键值。使用 SELECT 切换数据库,再使用 FLUSHDB 清除多个数据库。使用 DEL 命令删除特定键。使用 redis-cli 工具清空数据。

redis怎么读取队列 redis怎么读取队列 Apr 10, 2025 pm 10:12 PM

要从 Redis 读取队列,需要获取队列名称、使用 LPOP 命令读取元素,并处理空队列。具体步骤如下:获取队列名称:以 "queue:" 前缀命名,如 "queue:my-queue"。使用 LPOP 命令:从队列头部弹出元素并返回其值,如 LPOP queue:my-queue。处理空队列:如果队列为空,LPOP 返回 nil,可先检查队列是否存在再读取元素。

centos redis如何配置Lua脚本执行时间 centos redis如何配置Lua脚本执行时间 Apr 14, 2025 pm 02:12 PM

在CentOS系统上,您可以通过修改Redis配置文件或使用Redis命令来限制Lua脚本的执行时间,从而防止恶意脚本占用过多资源。方法一:修改Redis配置文件定位Redis配置文件:Redis配置文件通常位于/etc/redis/redis.conf。编辑配置文件:使用文本编辑器(例如vi或nano)打开配置文件:sudovi/etc/redis/redis.conf设置Lua脚本执行时间限制:在配置文件中添加或修改以下行,设置Lua脚本的最大执行时间(单位:毫秒)

redis命令行怎么用 redis命令行怎么用 Apr 10, 2025 pm 10:18 PM

使用 Redis 命令行工具 (redis-cli) 可通过以下步骤管理和操作 Redis:连接到服务器,指定地址和端口。使用命令名称和参数向服务器发送命令。使用 HELP 命令查看特定命令的帮助信息。使用 QUIT 命令退出命令行工具。

redis计数器怎么实现 redis计数器怎么实现 Apr 10, 2025 pm 10:21 PM

Redis计数器是一种使用Redis键值对存储来实现计数操作的机制,包含以下步骤:创建计数器键、增加计数、减少计数、重置计数和获取计数。Redis计数器的优势包括速度快、高并发、持久性和简单易用。它可用于用户访问计数、实时指标跟踪、游戏分数和排名以及订单处理计数等场景。

redis过期策略怎么设置 redis过期策略怎么设置 Apr 10, 2025 pm 10:03 PM

Redis数据过期策略有两种:定期删除:定期扫描删除过期键,可通过 expired-time-cap-remove-count、expired-time-cap-remove-delay 参数设置。惰性删除:仅在读取或写入键时检查删除过期键,可通过 lazyfree-lazy-eviction、lazyfree-lazy-expire、lazyfree-lazy-user-del 参数设置。

如何优化debian readdir的性能 如何优化debian readdir的性能 Apr 13, 2025 am 08:48 AM

在Debian系统中,readdir系统调用用于读取目录内容。如果其性能表现不佳,可尝试以下优化策略:精简目录文件数量:尽可能将大型目录拆分成多个小型目录,降低每次readdir调用处理的项目数量。启用目录内容缓存:构建缓存机制,定期或在目录内容变更时更新缓存,减少对readdir的频繁调用。内存缓存(如Memcached或Redis)或本地缓存(如文件或数据库)均可考虑。采用高效数据结构:如果自行实现目录遍历,选择更高效的数据结构(例如哈希表而非线性搜索)存储和访问目录信

See all articles