Redis的數(shù)據(jù)庫就是使用字典(哈希表)來作為底層實(shí)現(xiàn)的，對(duì)數(shù)據(jù)庫的增刪改查都是構(gòu)建在字典(哈希表)的操作之上的。
typedef struct redisDb {
int id; // 數(shù)據(jù)庫ID標(biāo)識(shí)
dict *dict; // 鍵空間，存放著所有的鍵值對(duì)
dict *expires; // 過期哈希表，保存著鍵的過期時(shí)間
dict *watched_keys; // 被watch命令監(jiān)控的key和相應(yīng)client
long long avg_ttl; // 數(shù)據(jù)庫內(nèi)所有鍵的平均TTL（生存時(shí)間）
} redisDb;
每次在Redis中創(chuàng)建數(shù)據(jù)時(shí)都會(huì)生成兩個(gè)對(duì)象：鍵對(duì)象、值對(duì)象。Redis對(duì)象用redisObject結(jié)構(gòu)表示，其中類型、編碼和指針記錄了Redis五個(gè)數(shù)據(jù)類型和六個(gè)底層數(shù)據(jù)結(jié)構(gòu)的關(guān)系。
typedef struct redisObject{
//類型
unsigned type:4;
//編碼
unsigned encoding:4;
//指向底層數(shù)據(jù)結(jié)構(gòu)的指針
void *ptr;
//引用計(jì)數(shù)
int refcount;
//記錄最后一次被程序訪問的時(shí)間
unsigned lru:22;
}robj
1. string對(duì)象
- Redis 是用 C 語言寫的，但Redis的字符串是自己構(gòu)建了一種名為 簡(jiǎn)單動(dòng)態(tài)字符串（simple dynamic string,SDS）的抽象類型。
struct sdshdr{
//記錄buf數(shù)組中已使用字節(jié)的數(shù)量
//等于 SDS 保存字符串的長(zhǎng)度
int len;
//記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量
int free;
//字節(jié)數(shù)組，用于保存字符串
char buf[];
}
字符串對(duì)象的編碼可以是int，raw或者embstr。int 編碼是用來保存整數(shù)值，raw編碼是用來保存長(zhǎng)字符串，而embstr是用來保存短字符串。其實(shí) embstr 編碼是專門用來保存短字符串的一種優(yōu)化編碼。
-
raw 和 embstr 的區(qū)別？
- embstr的使用只分配一次內(nèi)存空間（因此redisObject和sds是連續(xù)的），而raw需要分配兩次內(nèi)存空間（分別為redisObject和sds分配空間）。
- 因?yàn)閞edis中的embstr實(shí)現(xiàn)為只讀，所以只要是修改embstr對(duì)象，修改后的對(duì)象一定是raw的。
2. list對(duì)象
- Redis中鏈表也是自己定義實(shí)現(xiàn)的，雙向鏈表結(jié)構(gòu)為：
typedef struct listNode{
//前置節(jié)點(diǎn)
struct listNode *prev;
//后置節(jié)點(diǎn)
struct listNode *next;
//節(jié)點(diǎn)的值
void *value;
}listNode
typedef struct list{
//表頭節(jié)點(diǎn)
listNode *head;
//表尾節(jié)點(diǎn)
listNode *tail;
//鏈表所包含的節(jié)點(diǎn)數(shù)量
unsigned long len;
//節(jié)點(diǎn)值復(fù)制函數(shù)
void (*free) (void *ptr);
//節(jié)點(diǎn)值釋放函數(shù)
void (*free) (void *ptr);
//節(jié)點(diǎn)值對(duì)比函數(shù)
int (*match) (void *ptr,void *key);
}list;
鏈表具有前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的引用，表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL，通過 len 屬性獲取鏈表長(zhǎng)度，鏈表節(jié)點(diǎn)使用 void* 指針來保存節(jié)點(diǎn)值，可以保存各種不同類型的值。
- 壓縮列表（ziplist）是Redis為了節(jié)省內(nèi)存而開發(fā)的，它并不是對(duì)數(shù)據(jù)利用某種算法進(jìn)行壓縮，而是將數(shù)據(jù)按照一定規(guī)則編碼在一塊連續(xù)的內(nèi)存區(qū)域的順序型數(shù)據(jù)結(jié)構(gòu)。
- list對(duì)象可以是 ziplist(壓縮列表) 和 linkedlist(雙端鏈表)，當(dāng)列表保存元素個(gè)數(shù)小于512個(gè)且每個(gè)元素長(zhǎng)度小于64字節(jié)時(shí)為ziplist，可以更改list-max-ziplist-value選項(xiàng)和 list-max-ziplist-entries 選項(xiàng)進(jìn)行配置。
3. hash對(duì)象
- 字典哈希表，Redis 的字典使用哈希表作為底層實(shí)現(xiàn)，通過字典里面的 *next 指針指向下一個(gè)具有相同索引值的哈希表節(jié)點(diǎn)，也就是鏈地址法解決哈希沖突問題。
# hash表
typedef struct dictht{
//哈希表數(shù)組
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩碼，用于計(jì)算索引值
//總是等于 size-1
unsigned long sizemask;
//該哈希表已有節(jié)點(diǎn)的數(shù)量
unsigned long used;
}dictht
# hash表節(jié)點(diǎn)
typedef struct dictEntry{
//鍵
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一個(gè)哈希表節(jié)點(diǎn)，形成鏈表
struct dictEntry *next;
}dictEntry
# 字典
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
- hash對(duì)象的編碼可以是 ziplist 或者 hashtable。當(dāng)列表保存元素個(gè)數(shù)小于512個(gè)且每個(gè)元素長(zhǎng)度小于64字節(jié)時(shí)為ziplist，可以更改list-max-ziplist-value選項(xiàng)和 list-max-ziplist-entries 選項(xiàng)進(jìn)行配置。
-
rehash擴(kuò)容過程
- 在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將設(shè)置為0，表示rehash開始。
- 在rehash期間每次對(duì)字典進(jìn)行增加、查詢、刪除和更新操作時(shí)，除了執(zhí)行指定命令外；還會(huì)將ht[0]中rehashidx索引上的值rehash到ht[1]，操作完成后rehashidx+1。
- 字典操作不斷執(zhí)行，最終在某個(gè)時(shí)間點(diǎn)，所有的鍵值對(duì)完成rehash，這時(shí)將rehashidx設(shè)置為-1，表示rehash完成。
- 在漸進(jìn)式rehash過程中，字典會(huì)同時(shí)使用兩個(gè)哈希表ht[0]和ht[1]，所有的更新、刪除、查找操作也會(huì)在兩個(gè)哈希表進(jìn)行。例如要查找一個(gè)鍵的話，服務(wù)器會(huì)優(yōu)先查找ht[0]，如果不存在，再查找ht[1]，諸如此類。此外當(dāng)執(zhí)行新增操作時(shí)，新的鍵值對(duì)一律保存到ht[1]，不再對(duì)ht[0]進(jìn)行任何操作，以保證ht[0]的鍵值對(duì)數(shù)量只減不增，直至變?yōu)榭毡怼?/li>
4. set對(duì)象
- 整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)類型，不會(huì)出現(xiàn)重復(fù)元素。
typedef struct intset{
//編碼方式
uint32_t encoding;
//集合包含的元素?cái)?shù)量
uint32_t length;
//保存元素的數(shù)組
int8_t contents[];
}intset;
set對(duì)象的編碼可以是 intset 或者 hashtable。當(dāng)集合對(duì)象中所有元素都是整數(shù)且所有元素?cái)?shù)量不超過512時(shí)為intset類型，可通過set-max-intset-entries 進(jìn)行配置。
intset 編碼的集合對(duì)象使用整數(shù)集合作為底層實(shí)現(xiàn)，集合對(duì)象包含的所有元素都被保存在整數(shù)集合中。
hashtable 編碼的集合對(duì)象使用 字典作為底層實(shí)現(xiàn)，字典的每個(gè)鍵都是一個(gè)字符串對(duì)象，這里的每個(gè)字符串對(duì)象就是一個(gè)集合中的元素，而字典的值則全部設(shè)置為 null。
5. zset對(duì)象
-
跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其它節(jié)點(diǎn)的指針，從而達(dá)到快速訪問節(jié)點(diǎn)的目的。
跳躍表類似公司的組織架構(gòu)：董事會(huì)->C？O->部門->組長(zhǎng)->員工
- 由很多層結(jié)構(gòu)組成
- 每一層都是一個(gè)有序的鏈表，排列順序?yàn)橛筛邔拥降讓?，都至少包含兩個(gè)鏈表節(jié)點(diǎn)，分別是前面的head節(jié)點(diǎn)和后面的nil節(jié)點(diǎn)
- 最底層的鏈表包含了所有的元素
- 如果一個(gè)元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全都會(huì)出現(xiàn)（上一層的元素是當(dāng)前層的元素的子集）
- 鏈表中的每個(gè)節(jié)點(diǎn)都包含兩個(gè)指針，一個(gè)指向同一層的下一個(gè)鏈表節(jié)點(diǎn)，另一個(gè)指向下一層的同一個(gè)鏈表節(jié)點(diǎn)
typedef struct zskiplistNode {
//層
struct zskiplistLevel{
//前進(jìn)指針
struct zskiplistNode *forward;
//跨度
unsigned int span;
}level[];
//后退指針
struct zskiplistNode *backward;
//分值
double score;
//成員對(duì)象
robj *obj;
} zskiplistNode
typedef struct zskiplist{
//表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
structz skiplistNode *header, *tail;
//表中節(jié)點(diǎn)的數(shù)量
unsigned long length;
//表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)
int level;
}zskiplist;
zset集合的編碼可以是 ziplist 或者 skiplist，當(dāng)保存的元素?cái)?shù)量小于128且長(zhǎng)度都小于64字節(jié)為ziplist類型，通過zset-max-ziplist-entries 選項(xiàng)和 zset-max-ziplist-value 進(jìn)行修改。
ziplist 編碼的有序集合對(duì)象使用壓縮列表作為底層實(shí)現(xiàn)，每個(gè)集合元素使用兩個(gè)緊挨在一起的壓縮列表節(jié)點(diǎn)來保存，第一個(gè)節(jié)點(diǎn)保存元素的成員，第二個(gè)節(jié)點(diǎn)保存元素的分值。并且壓縮列表內(nèi)的集合元素按分值從小到大的順序進(jìn)行排列，小的放置在靠近表頭的位置，大的放置在靠近表尾的位置。
- skiplist 編碼的有序集合對(duì)象使用 zet 結(jié)構(gòu)作為底層實(shí)現(xiàn)，一個(gè) zset 結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表，字典的鍵保存元素的值，字典的值則保存元素的分值；跳躍表節(jié)點(diǎn)的 object 屬性保存元素的成員，跳躍表節(jié)點(diǎn)的 score 屬性保存元素的分值。
typedef struct zset{
//跳躍表
zskiplist *zsl;
//字典
dict *dice;
} zset;
6. 內(nèi)存回收和共享
-
Redis自己構(gòu)建了一個(gè)內(nèi)存回收機(jī)制，通過在 redisObject 結(jié)構(gòu)中的 refcount 屬性實(shí)現(xiàn)。
- 創(chuàng)建一個(gè)新對(duì)象，屬性 refcount 初始化為1
- 對(duì)象被一個(gè)新程序使用，屬性 refcount 加 1
- 對(duì)象不再被一個(gè)程序使用，屬性 refcount 減 1
- 當(dāng)對(duì)象的引用計(jì)數(shù)值變?yōu)?0 時(shí)，對(duì)象所占用的內(nèi)存就會(huì)被釋放
定期刪除+惰性刪除
定期刪除： redis默認(rèn)是每隔 100ms 就隨機(jī)抽取一些設(shè)置了過期時(shí)間的key，檢查其是否過期，如果過期就刪除。
惰性刪除 ： 當(dāng)去查詢已經(jīng)過期的key時(shí)，Redis才會(huì)對(duì)其刪除。
-
當(dāng)存在循環(huán)引用就會(huì)造成內(nèi)存泄露，所以redis可以配置6種清除策略，maxmemory-policy ：當(dāng)內(nèi)存使用達(dá)到最大值時(shí)，有以下幾種策略：
- volatile-lru 利用LRU算法移除設(shè)置過過期時(shí)間的key (LRU:最近使用 Least Recently Used )
- allkeys-lru 利用LRU算法移除任何key
- volatile-random 移除設(shè)置過過期時(shí)間的隨機(jī)key
- allkeys-random 移除隨機(jī)key
- volatile-ttl 移除即將過期的key(minor TTL)
- noeviction 不移除任何key，只是返回一個(gè)寫錯(cuò)誤 ，默認(rèn)選項(xiàng)
- volatile-lfu：從所有配置了過期時(shí)間的鍵中移除使用頻率最少的鍵
- allkeys-lfu：從所有鍵中移除使用頻率最少的鍵
Redis 4.0 引入了 volatile-lfu 和 allkeys-lfu 淘汰策略。
LFU 策略：通過統(tǒng)計(jì)訪問頻率，將訪問頻率最少的數(shù)據(jù)淘汰。
LRU策略：通過最近訪問，將長(zhǎng)時(shí)間沒有訪問的數(shù)據(jù)淘汰。 refcount 屬性除了能實(shí)現(xiàn)內(nèi)存回收以外，還能用于內(nèi)存共享：將數(shù)據(jù)庫鍵的值指針指向一個(gè)現(xiàn)有值的對(duì)象 、將被共享的值對(duì)象引用refcount 加 1。
7. 降低內(nèi)存占用的幾種方式
降低內(nèi)存占用有助于減少創(chuàng)建快照和加載快照的時(shí)間、提升載入AOF文件和重新文件的效率、縮短主從同步所需的時(shí)間等！
短結(jié)構(gòu)：如ziplist、intset、string符合條件解析的int和embstr等。但操作一個(gè)長(zhǎng)壓縮列表或者大整數(shù)集合會(huì)對(duì)性能帶來影響，嚴(yán)重時(shí)可能導(dǎo)致不可用?？墒窃O(shè)置元素不超過1024個(gè)字節(jié)不超過64位。
分片結(jié)構(gòu)：分片本質(zhì)上是基于某些簡(jiǎn)單的規(guī)則將數(shù)據(jù)劃分為更小的部分，如根據(jù)算法計(jì)算key的組成。
打包存儲(chǔ)二進(jìn)制位和字節(jié)。
春暖花開 應(yīng)該走出去看看這片春色
