前言当我们在Redis数据库中set一个KV的时候,这个KV保存在哪里?如果我们get的时候,又从哪里get出来。时间复杂度,空间复杂的等等,怎么优化等等一系列问题。 服务器中的数据库Redis服务器将所有数据库信息都保存在redis.h##redisService结构体中。代码如下: 1 struct redisServer { 2 3 // ... 4 5 /* General */ 6 7 // 配置文件的绝对路径 8 char *configfile; /* Absolute config file path, or NULL */ 9 10 // 数据库 11 redisDb *db; 12 13 // 是否设置了密码 14 char *requirepass; /* Pass for AUTH command, or NULL */ 15 16 // PID 文件 17 char *pidfile; /* PID file path */ 18 19 // TCP 监听端口 20 int port; /* TCP listening port */ 21 22 // ... 23 24 } 列了几个,我认为比较重要的。其中最重要的,肯定是redisDb *db; 这个数据结构保存了我们所有的数据。 Redis 是一个键值对(key-value pair)数据库服务器, 服务器中的每个数据库都由一个 /* Redis database representation. There are multiple databases identified * by integers from 0 (the default database) up to the max configured * database. The database number is the 'id' field in the structure. */ typedef struct redisDb { // 数据库键空间,保存着数据库中的所有键值对 dict *dict; /* The keyspace for this DB */ // 键的过期时间,字典的键为键,字典的值为过期事件 UNIX 时间戳 dict *expires; /* Timeout of keys with a timeout set */ // 正处于阻塞状态的键 dict *blocking_keys; /* Keys with clients waiting for data (BLPOP) */ // 可以解除阻塞的键 dict *ready_keys; /* Blocked keys that received a PUSH */ // 正在被 WATCH 命令监视的键 dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */ struct evictionPoolEntry *eviction_pool; /* Eviction pool of keys */ // 数据库号码 int id; /* Database ID */ // 数据库的键的平均 TTL ,统计信息 long long avg_ttl; /* Average TTL, just for stats */ } redisDb; 其中最重要的就是 dict *dict; 他是一个字典,不太了解的小伙伴,可以看我前一篇的文章(https://www.cnblogs.com/wenbochang/p/11673590.html),对redis的字典有详细的介绍。 这个dict存储了我们真正的数据。 键空间和用户所见的数据库是直接对应的:
因为数据库的键空间是一个字典, 所以所有针对数据库的操作 —— 比如添加一个键值对到数据库, 或者从数据库中删除一个键值对, 又或者在数据库中获取某个键值对, 等等, 实际上都是通过对键空间字典进行操作来实现的。那么复杂度显而易见基本就是O(1)级别了,这也是redis为什么能这么快的一个重要原因。
对键取值对一个数据库键进行取值, 实际上就是在键空间中取出键所对应的值对象。代码如下: 1 /* 2 * 返回字典中包含键 key 的节点 3 * 4 * 找到返回节点,找不到返回 NULL 5 * 6 * T = O(1) 7 */ 8 dictEntry *dictFind(dict *d, const void *key) 9 { 10 dictEntry *he; 11 unsigned int h, idx, table; 12 13 // 字典(的哈希表)为空 14 if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */ 15 16 // 如果条件允许的话,进行单步 rehash 17 if (dictIsRehashing(d)) _dictRehashStep(d); 18 19 // 计算键的哈希值 20 h = dictHashKey(d, key); 21 // 在字典的哈希表中查找这个键 22 // T = O(1) 23 for (table = 0; table <= 1; table++) { 24 25 // 计算索引值 26 idx = h & d->ht[table].sizemask; 27 28 // 遍历给定索引上的链表的所有节点,查找 key 29 he = d->ht[table].table[idx]; 30 // T = O(1) 31 while(he) { 32 33 if (dictCompareKeys(d, key, he->key)) 34 return he; 35 36 he = he->next; 37 } 38 39 // 如果程序遍历完 0 号哈希表,仍然没找到指定的键的节点 40 // 那么程序会检查字典是否在进行 rehash , 41 // 然后才决定是直接返回 NULL ,还是继续查找 1 号哈希表 42 if (!dictIsRehashing(d)) return NULL; 43 } 44 45 // 进行到这里时,说明两个哈希表都没找到 46 return NULL; 47 }
看代码其实是很简单的。
对键增加,删除,更新类似于查找。我就不一一列出源码了。 后言当使用 Redis 命令对数据库进行读写时, 服务器不仅会对键空间执行指定的读写操作, 还会执行一些额外的维护操作, 其中包括:
|
|