Home Database Mysql Tutorial Redis源码解析2

Redis源码解析2

Jun 07, 2016 pm 05:56 PM
redis Source code parse

DICT数据结构 Dict其实就是一个hash表,但在Redis中,已经存在一种叫Hash的数据结构,所以,就把Hash表改名成Dict吧。。。 Dict是Redis进行键值处理的灵魂,不管多大的数据量,始终维持O(1)的时间复杂度(排除bucket下链表很长的情况) 全局保存的所有key,

DICT数据结构

Dict其实就是一个hash表,但在Redis中,已经存在一种叫“Hash”的数据结构,所以,就把Hash表改名成Dict吧。。。
Dict是Redis进行键值处理的灵魂,不管多大的数据量,始终维持O(1)的时间复杂度(排除bucket下链表很长的情况)
全局保存的所有key,都存在于一个Dict中
而且别的数据结构,比如set、hash也可能会用到Dict

Dict实现于 dict.h  dict.c 两个文件中

其类型定义如下图:

1. dict:表示一个独立的dict结构,提供给外部使用

1 typedef struct dict { *privdata; rehashidx; iterators; } dict;

2. dictht:表示一个独立的dict容器,内部使用,外部程序不建议直接操作该结构

1 typedef struct dictht { unsigned unsigned unsigned } dictht;

3. dictEntry:数据结点,香港服务器租用,其实就是一个kv键值对,还包含一个next指针

1 typedef struct dictEntry { 2 void *key; 3 void *val; 4 struct dictEntry *next; 5 } dictEntry;

4. dictType:定义了一组回调函数,进行数据结点的操作

typedef struct dictType { unsigned *(*keyDup)(*(*valDup)((*keyCompare)(*key2); (*keyDestructor)((*valDestructor)(void *privdata, void *obj); //销毁val } dictType;

 

 

DICT操作

Redis中的dict是一个标准的 “bucket + 开链” 的哈希表
并未进行更复杂的处理
包括防止哈希冲突导致开链过长的问题,也没有考虑
如果精心构造一串key来打redis,很容易打死的
所以,企业级应用的同学们,如果你的Redis服务对用户比较Open,别下个源码就用了,还是动手改改HashFunction再用吧!

 

Redis用两个dictht结构,作用是为了能够渐进地导数据,防止Rehash时阻塞时间太长
这种做法在memcache中就已经用了,不过memcache中是开辟一个线程专门做rehash而已
相比之下,不开线程的处理方式不用锁,BUG更少一些

 

命名空间 

Redis中的Dict分为两类:

1. 系统级Dict,具有全局的命名空间,其定义如下:

typedef struct redisDb { dict *dict; dict *expires; dict *blocking_keys; dict *io_keys; dict *watched_keys; id; } redisDb;

2. 应用级Dict,由metadata数据结构自己维护,主要是一些 set、hash结构中的dict

    如下图: 

Rehash

当满足以下条件时,会启动Rehash

1 // 当有效空间使用率 htNeedsResize(dict *dict) { size, used; 5 6 size = dictSlots(dict); 7 used = dictSize(dict); 8 return (size && used && size > DICT_HT_INITIAL_SIZE && 9 (used*100/size REDIS_HT_MINFILL)); 10 }

 

1 // 当有效空间使用率 > 100%时, _dictExpandIfNeeded(dict *d) 4 { 5 ... ... (d->ht[0].used >= d->ht[0].size && 8 (dict_can_resize || 9 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) 10 { 11 return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ? 12 d->ht[0].size : d->ht[0].used)*2); 13 } 14 return DICT_OK; 15 }

 

Rehash启动后,就要开始进行Rehash操作了
但是,Rehash的代价是很大的,特别是当容量超过千万级以后,往往会耗费数十秒来进行操作(视机器性能)
所以,Redis采用了渐进式的Rehash,把操作分片,一步步来,总不能阻塞用户响应吧

根据Dict的类型不同,会采用不同的Rehash策略:
1. 全局性的DICT结构(就是全局命名空间中的key),会周期性的进行rehash,每次进行 1ms
    而且,不受稍后提到的 SafeIterator的干扰,可以一直执行(但是,虚拟主机,不受干扰是一回事,在iterator循环空间中,还是得用Safe模式的,所以,源码中也会看到大量针对全局dict的SafeIterator,这一点需要理解一下)
    毕竟,全局的,是重要的嘛,挤也要挤出1ms来,用吧!而且还甭想打扰它,别不服气了

2. 应用级DICT结构(就是用户自定义的一些DICT),Redis会采取一种 Lazy Rehash 的策略
    所谓 Lazy Rehash,就是用得越多,处理得越快;用得越少,处理得越慢
    什么叫“用”呢?
    很好理解,“增删查”操作都叫用,源码里对应:dictAdd、dictGenericDelete、dictFind、dictGetRandomKey操作,都会促发_dictRehashStep函数进行Rehashing
    但别高兴太早,每次只触发一条而已,所以,慢慢来吧~~

    

Iterator

由于Dict内部结构的复杂性,虚拟主机,提供一个遍历所有数据的iterator,是非常必要的

Dict提供两种Iterator:

1. dictGetIterator:普通iter,在遍历时不可对dict做更多操作,否则会引起数据遗漏或重复

2. dictGetSafeIterator:安全iter,什么操作都能做,安全的,你懂的。

可以参考上图理解这一点,不再赘述

DictType

dictType 定义了dict的操作行为。Redis预定义了一组dictType,规范各种类型dict的操作

相关代码如下:

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to build the redis cluster mode How to build the redis cluster mode Apr 10, 2025 pm 10:15 PM

Redis cluster mode deploys Redis instances to multiple servers through sharding, improving scalability and availability. The construction steps are as follows: Create odd Redis instances with different ports; Create 3 sentinel instances, monitor Redis instances and failover; configure sentinel configuration files, add monitoring Redis instance information and failover settings; configure Redis instance configuration files, enable cluster mode and specify the cluster information file path; create nodes.conf file, containing information of each Redis instance; start the cluster, execute the create command to create a cluster and specify the number of replicas; log in to the cluster to execute the CLUSTER INFO command to verify the cluster status; make

How to clear redis data How to clear redis data Apr 10, 2025 pm 10:06 PM

How to clear Redis data: Use the FLUSHALL command to clear all key values. Use the FLUSHDB command to clear the key value of the currently selected database. Use SELECT to switch databases, and then use FLUSHDB to clear multiple databases. Use the DEL command to delete a specific key. Use the redis-cli tool to clear the data.

How to read redis queue How to read redis queue Apr 10, 2025 pm 10:12 PM

To read a queue from Redis, you need to get the queue name, read the elements using the LPOP command, and process the empty queue. The specific steps are as follows: Get the queue name: name it with the prefix of "queue:" such as "queue:my-queue". Use the LPOP command: Eject the element from the head of the queue and return its value, such as LPOP queue:my-queue. Processing empty queues: If the queue is empty, LPOP returns nil, and you can check whether the queue exists before reading the element.

How to use the redis command How to use the redis command Apr 10, 2025 pm 08:45 PM

Using the Redis directive requires the following steps: Open the Redis client. Enter the command (verb key value). Provides the required parameters (varies from instruction to instruction). Press Enter to execute the command. Redis returns a response indicating the result of the operation (usually OK or -ERR).

How to use redis lock How to use redis lock Apr 10, 2025 pm 08:39 PM

Using Redis to lock operations requires obtaining the lock through the SETNX command, and then using the EXPIRE command to set the expiration time. The specific steps are: (1) Use the SETNX command to try to set a key-value pair; (2) Use the EXPIRE command to set the expiration time for the lock; (3) Use the DEL command to delete the lock when the lock is no longer needed.

How to configure Lua script execution time in centos redis How to configure Lua script execution time in centos redis Apr 14, 2025 pm 02:12 PM

On CentOS systems, you can limit the execution time of Lua scripts by modifying Redis configuration files or using Redis commands to prevent malicious scripts from consuming too much resources. Method 1: Modify the Redis configuration file and locate the Redis configuration file: The Redis configuration file is usually located in /etc/redis/redis.conf. Edit configuration file: Open the configuration file using a text editor (such as vi or nano): sudovi/etc/redis/redis.conf Set the Lua script execution time limit: Add or modify the following lines in the configuration file to set the maximum execution time of the Lua script (unit: milliseconds)

How to use the redis command line How to use the redis command line Apr 10, 2025 pm 10:18 PM

Use the Redis command line tool (redis-cli) to manage and operate Redis through the following steps: Connect to the server, specify the address and port. Send commands to the server using the command name and parameters. Use the HELP command to view help information for a specific command. Use the QUIT command to exit the command line tool.

How to set the redis expiration policy How to set the redis expiration policy Apr 10, 2025 pm 10:03 PM

There are two types of Redis data expiration strategies: periodic deletion: periodic scan to delete the expired key, which can be set through expired-time-cap-remove-count and expired-time-cap-remove-delay parameters. Lazy Deletion: Check for deletion expired keys only when keys are read or written. They can be set through lazyfree-lazy-eviction, lazyfree-lazy-expire, lazyfree-lazy-user-del parameters.

See all articles