字典（dict）

dict?字典是基于?hash算法?來實現(xiàn)，是?Hash?數(shù)據(jù)類型的底層存儲數(shù)據(jù)結(jié)構(gòu)京景。我們來看下?redis 3.0.0?版本的?dict.h?頭文件定義徽职。

typedefstructdict{dictType *type;void*privdata;? ? dictht ht[2];longrehashidx;intiterators; } dict;

typedefstructdictht{dictEntry **table;unsignedlongsize;unsignedlongsizemask;unsignedlongused;} dictht;

typedefstructdictEntry{void*key;union{void*val;uint64_tu64;int64_ts64;doubled;? ? } v;structdictEntry*next;} dictEntry;

說到?hash table?有兩個東西是我們經(jīng)常會碰到的幕庐，首先就是?hash 碰撞?問題解愤，redis dict?是采用鏈地址法來解決冈绊，dictEntry->next?就是指向下個沖突?key的節(jié)點侠鳄。

還有一個經(jīng)常碰到的就是?rehash?的問題，提到?rehash?我們還是有點擔心性能的死宣。那么redis 實現(xiàn)是非常巧妙的伟恶，采用?惰性漸進式 rehash 算法?。

在?dict struct?里有一個?ht[2]?組數(shù)毅该，還有一個?rehashidx?索引博秫。redis?進行?rehash?的大致算法是這樣的，首先會開辟一個新的?dictht?空間眶掌，放在?ht[2]?索引上挡育，此時將?rehashidx?設(shè)置為0，表示開始進入?rehash?階段朴爬，這個階段可能會持續(xù)很長時間即寒，rehashidx?表示?dictEntry?個數(shù)。

每次當有對某個?ht[1]?索引中的?key?進行訪問時召噩，獲取母赵、刪除、更新蚣常，redis?都會將當前?dictEntry?索引中的所有?key?rehash?到?ht[2]?字典中市咽。一旦?rehashidx=-1?表示?rehash?結(jié)束。

跳表（skip list）

skip list?是?zset?的底層數(shù)據(jù)結(jié)構(gòu)抵蚊，有著高性能的查找排序能力施绎。

我們都知道一般用來實現(xiàn)帶有排序的查找都是用?Tree?來實現(xiàn)，不管是各種變體的?B Tree?還是?B+ Tree贞绳，本質(zhì)都是用來做順序查找谷醉。

skip list?實現(xiàn)起來簡單，性能也與?B Tree?相接近冈闭。

typedefstructzskiplistNode{robj *obj;doublescore;structzskiplistNode*backward;structzskiplistLevel{structzskiplistNode*forward;unsignedintspan;? ? } level[];} zskiplistNode;typedefstructzskiplist{structzskiplistNode*header, *tail;unsignedlonglength;intlevel;} zskiplist;

zskiplistNode->zskiplistLevel->span?這個值記錄了當前節(jié)點距離下個節(jié)點的跨度俱尼。每一個節(jié)點會有最大不超過?zskiplist->level?節(jié)點個數(shù)，分別用來表示不同跨度與節(jié)點的距離萎攒。

每個節(jié)點會有多個?forward?向前指針遇八，只有一個?backward?指針矛绘。每個節(jié)點會有對象 __*obj__ 和?score?分值，每個分值都會按照順序排列刃永。

整數(shù)集合（int set）

int set?整數(shù)集合是?set?數(shù)據(jù)類型的底層實現(xiàn)數(shù)據(jù)結(jié)構(gòu)货矮，它的特點和使用場景很明顯，只要我們使用的集合都是整數(shù)且在一定的范圍之內(nèi)都會使用整數(shù)集合編碼斯够。

SADDset:userid100200300(integer)3

OBJECTencodingset:userid"intset"

int set?使用一塊連續(xù)的內(nèi)存來存儲集合數(shù)據(jù)囚玫，它是數(shù)組結(jié)構(gòu)不是鏈表結(jié)構(gòu)。

typedefstructintset{uint32_tencoding;uint32_tlength;int8_tcontents[];} intset;

intset->encoding?用來確定?contents[]?是什么類型的整數(shù)編碼读规，以下三種值之一抓督。

#defineINTSET_ENC_INT16(sizeof(int16_t))#defineINTSET_ENC_INT32(sizeof(int32_t))#defineINTSET_ENC_INT64(sizeof(int64_t))

redis?會根據(jù)我們設(shè)置的值類型動態(tài)?sizeof?出一個對應(yīng)的空間大小。如果我們集合原來是?int16?，然后往集合里添加了?int32?整數(shù)將觸發(fā)升級，一旦升級成功不會觸發(fā)降級操作须床。

壓縮表（zip list）

zip list?壓縮表是?list、zset涌穆、hash?數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)之一。它是為了節(jié)省內(nèi)存通過壓縮數(shù)據(jù)存儲在一塊連續(xù)的內(nèi)存空間中雀久。

typedefstructzlentry{unsignedintprevrawlensize, prevrawlen;unsignedintlensize, len;unsignedintheadersize;unsignedcharencoding;unsignedchar*p;} zlentry;

它最大的優(yōu)點就是壓縮空間，空間利用率很高趁舀。缺點就是一旦出現(xiàn)更新可能就是連鎖更新赖捌，因為數(shù)據(jù)在內(nèi)容空間中都是連續(xù)的，最極端情況下就是可能出現(xiàn)順序連鎖擴張矮烹。

壓縮列表會由多個?zlentry?節(jié)點組成越庇，每一個?zlentry?記錄上一個節(jié)點長度和大小，當前節(jié)點長度?lensize?和大小?len?包括編碼?encoding?奉狈。

這取決于業(yè)務(wù)場景卤唉，redis?提供了一組配置，專門用來針對不同的場景進行閾值控制仁期。

hash-max-ziplist-entries512hash-max-ziplist-value64

list-max-ziplist-entries512list-max-ziplist-value64

zset-max-ziplist-entries128zset-max-ziplist-value64

上述配置分別用來配置?ziplist?作為?hash?桑驱、list、zset?數(shù)據(jù)類型的底層壓縮閾值控制跛蛋。

Redis Object 類型與映射

redis 內(nèi)部每一種數(shù)據(jù)類型都是對象化的熬的，也就是我們所說的5種數(shù)據(jù)類型其實內(nèi)部都會對應(yīng)到 redisObject 對象，然后在由 redisObject 來包裝具體的存儲數(shù)據(jù)結(jié)構(gòu)和編碼赊级。

typedefstructredisObject {unsignedtype:4;unsignedencoding:4;unsignedlru:REDIS_LRU_BITS;intrefcount;void*ptr;} robj;

這是一個很?OO?的設(shè)計押框，redisObject->type?是?5?種數(shù)據(jù)類型之一，redisObject->encoding?是這個數(shù)據(jù)類型所使用的數(shù)據(jù)結(jié)構(gòu)和編碼理逊。

我們看下?redis?提供的?5?種數(shù)據(jù)類型與每一種數(shù)據(jù)類型對應(yīng)的存儲數(shù)據(jù)結(jié)構(gòu)和編碼橡伞。

/* Object types */#defineREDIS_STRING 0#defineREDIS_LIST 1#defineREDIS_SET 2#defineREDIS_ZSET 3#defineREDIS_HASH 4

#defineREDIS_ENCODING_RAW 0#defineREDIS_ENCODING_INT 1#defineREDIS_ENCODING_HT 2#defineREDIS_ENCODING_ZIPMAP 3#defineREDIS_ENCODING_LINKEDLIST 4#defineREDIS_ENCODING_ZIPLIST 5#defineREDIS_ENCODING_INTSET 6#defineREDIS_ENCODING_SKIPLIST 7#defineREDIS_ENCODING_EMBSTR 8

REDIS_ENCODING_ZIPMAP 3?這個編碼可以忽略了盒揉，在特定的情況下有性能問題，在?redis 2.6?版本之后已經(jīng)廢棄兑徘，為了兼容性保留预烙。

上圖是?redis 5?種數(shù)據(jù)類型與底層數(shù)據(jù)結(jié)構(gòu)和編碼的對應(yīng)關(guān)系，但是這種對應(yīng)關(guān)系在每一個版本中都會有可能發(fā)生變化道媚，這也是?redisObject?的靈活性所在扁掸，有著?OO?的這種多態(tài)性。

redisObject->refcount?表示當前對象的引用計數(shù)最域，在?redis?內(nèi)部為了節(jié)省內(nèi)存采用了共享對象的方法谴分，當某個對象被引用的時候這個?refcount?會加?1，釋放的時候會減?1镀脂。

redisObject->lru?表示當前對象的?空轉(zhuǎn)時長牺蹄，也就是?idle time?，這個時間會是?redis lru?算法用來釋放對象的時間依據(jù)薄翅∩忱迹可以通過?OBJECT idletime?命令查看某個?key?的空轉(zhuǎn)時長?lru?時間。

Redis 內(nèi)存管理策略

redis?在服務(wù)端分別為不同的?db index?維護一個?dict?這個?dict?稱為?key space?鍵空間 翘魄。每一個?redis client?只能屬于一個?db index?鼎天，在?redis?服務(wù)端會維護每一個鏈接的?redisClient?。

typedefstructredisClient{uint64_tid;intfd;? ? redisDb *db;} redisClient;

在服務(wù)端每一個?redis?客戶端都會有一個指向?redisDb?的指針暑竟。

typedefstructredisDb{dict *dict;? ? dict *expires;? ? dict *blocking_keys;? ? dict *ready_keys;? ? dict *watched_keys;structevictionPoolEntry*eviction_pool;intid;longlongavg_ttl;} redisDb;

key space?鍵空間就是這里的?redisDb->dict?斋射。redisDb->expires?是維護所有鍵空間的每一個?key?的過期時間。

鍵 過期時間但荤、生存時間

對于一個?key?我們可以設(shè)置它多少秒罗岖、毫秒之后過期，也可以設(shè)置它在某個具體的時間點過期腹躁，后者是一個時間戳桑包。

EXPIRE?命令可以設(shè)置某個?key?多少秒之后過期

PEXPIRE?命令可以設(shè)置某個?key?多少毫秒之后過期

EXPIREAT?命令可以設(shè)置某個?key?在多少秒時間戳之后過期

PEXPIREAT?命令可以設(shè)置某個?key?在多少毫秒時間戳之后過期

PERSIST?命令可以移除鍵的過期時間

其實上述命令最終都會被轉(zhuǎn)換成對?PEXPIREAT?命令。在?redisDb->expires?指向的?key?字典中維護著一個到期的毫秒時間戳纺非。

TTL哑了、PTTL?可以通過這兩個命令查看某個?key?的過期秒、毫秒數(shù)铐炫。

redis?內(nèi)部有一個?事件循環(huán)垒手，這個事件循環(huán)會檢查鍵的過期時間是否小于當前時間，如果小于則會刪除這個鍵倒信。

過期鍵刪除策略

在使用?redis?的時候我們最關(guān)心的就是鍵是如何被刪除的科贬，如何高效的準時的刪除某個鍵。其實?redis?提供了兩個方案來完成這件事情。

redis?采用?惰性刪除?榜掌、?定期刪除?雙重刪除策略优妙。

當我們訪問某個?key?的時候?redis?會檢查它是否過期，這是惰性刪除憎账。

robj *lookupKeyRead(redisDb *db, robj *key) {? ? robj *val;? ? expireIfNeeded(db,key);val= lookupKey(db,key);if(val==NULL)? ? ? ? server.stat_keyspace_misses++;elseserver.stat_keyspace_hits++;returnval;}

intexpireIfNeeded(redisDb *db, robj *key){mstime_twhen = getExpire(db,key);mstime_tnow;if(when <0)return0;/* No expire for this key */if(server.loading)return0;? ? ? ? now = server.lua_caller ? server.lua_time_start : mstime();if(server.masterhost !=NULL)returnnow > when;/* Return when this key has not expired */if(now <= when)return0;/* Delete the key */server.stat_expiredkeys++;? ? propagateExpire(db,key);? ? notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,"expired",key,db->id);returndbDelete(db,key);}

redis?也會通過?事件循環(huán)?周期性的執(zhí)行?key?的過期刪除動作套硼，這是定期刪除。

intserverCron(structaeEventLoop *eventLoop,longlongid,void*clientData) {/* Handle background operations on Redis databases. */databasesCron();}

voiddatabasesCron(void){/* Expire keys by random sampling. Not required for slaves

? ? * as master will synthesize DELs for us. */if(server.active_expire_enabled && server.masterhost ==NULL)? ? ? ? activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);}

惰性刪除?是每次只要有讀取胞皱、寫入都會觸發(fā)惰性刪除代碼邪意。周期刪除?是由?redis EventLoop?來觸發(fā)的。redis?內(nèi)部很多維護性工作都是基于?EventLoop?反砌。

AOF?雾鬼、RDB?處理過期鍵策略

既然鍵會隨時存在過期問題，那么涉及到持久化?redis?是如何幫我們處理的宴树。

當?redis?使用?RDB?方式持久化時策菜，每次持久化的時候就會檢查這些即將被持久化的?key?是否已經(jīng)過期，如果過期將直接忽略酒贬，持久化那些沒有過期的鍵又憨。當?redis作為?master 主服務(wù)器?啟動的時候，在載入?rdb?持久化鍵時也會檢查這些鍵是否過期锭吨，將忽略過期的鍵蠢莺，只載入沒過期的鍵。

當?redis?使用?AOF?方式持久化時耐齐，每次遇到過期的?key redis?會追加一條?DEL?命令 到?AOF?文件浪秘，也就是說只要我們順序載入執(zhí)行?AOF?命令文件就會刪除過期的鍵。

如果?redis?作為從服務(wù)器啟動的化埠况，它一旦與?master 主服務(wù)器?建立鏈接就會清空所有數(shù)據(jù)進行完整同步，當然新版本的?redis?支持?SYCN2?的半同步棵癣。如果是已經(jīng)建立了?master/slave?主從同步之后辕翰，主服務(wù)器會發(fā)送?DEL?命令給所有從服務(wù)器執(zhí)行刪除操作。

Redis?LRU?算法

在使用?redis?的時候我們會設(shè)置?maxmemory?選項狈谊，64?位的默認是?0?不限制喜命。線上的服務(wù)器必須要設(shè)置的，要不然很有可能導(dǎo)致?redis?宿主服務(wù)器直接內(nèi)存耗盡最后鏈接都上不去河劝。

所以基本要設(shè)置兩個配置：

maxmemory 最大內(nèi)存閾值

maxmemory-policy 到達閾值的執(zhí)行策略

可以通過?CONFIG GET maxmemory/maxmemory-policy?分別查看這兩個配置值壁榕，也可以通過?CONFIG SET?去分別配置。

maxmemory-policy?有一組配置赎瞎，可以用在很多場景下：

noeviction：客戶端嘗試執(zhí)行會讓更多內(nèi)存被使用的命令直接報錯

allkeys-lru： 在所有key里執(zhí)行l(wèi)ru算法

volatile-lru：在所有已經(jīng)過期的key里執(zhí)行l(wèi)ru算法

allkeys-random：在所有key里隨機回收

volatile-random：在已經(jīng)過期的key里隨機回收

volatile-ttl：回收已經(jīng)過期的key牌里，并且優(yōu)先回收存活時間（TTL）較短的鍵

關(guān)于?cache?的命中率可以通過?info?命令查看 鍵空間的命中率和未命中率。

# Statskeyspace_hits:33keyspace_misses:5

maxmemory?在到達閾值的時候會采用一定的策略去釋放內(nèi)存，這些策略我們可以根據(jù)自己的業(yè)務(wù)場景來選擇牡辽，默認是?noeviction?喳篇。

redis LRU?算法有一個取樣的優(yōu)化機制，可以通過一定的取樣因子來加強回收的?key?的準確度态辛。CONFIG GET maxmemory-samples?查看取樣配置麸澜，具體可以參考更加詳細的文章。

Redis 持久化方式

redis?本身提供持久化功能奏黑，有兩種持久化機制炊邦，一種是數(shù)據(jù)持久化?RDB?，一種是命令持久化?AOF熟史，這兩種持久化方式各有優(yōu)缺點馁害，也可以組合使用，一旦組合使用?redis?在載入數(shù)據(jù)的時候會優(yōu)先載入?aof?文件以故，只有當?AOF?持久化關(guān)閉的時候才會載入?rdb?文件蜗细。

RDB?(Redis DataBase)

RDB?是?redis?數(shù)據(jù)庫，redis?會根據(jù)一個配置來觸發(fā)持久化怒详。

#save<seconds><changes>save9001save30010save6010000

CONFIGGET save1)"save"2)"3600 1 300 100 60 10000"

表示在多少秒之類的變化次數(shù)炉媒，一旦達到這個觸發(fā)條件 redis 將觸發(fā)持久化動作。redis 在執(zhí)行持久化的時候有兩種模式?BGSAVE昆烁、SAVE?吊骤。BGSAVE?是后臺保存，redis?會?fork?出一個子進程來處理持久化静尼，不會?block?用戶的執(zhí)行請求白粉。而?SAVE?則會?block?用戶執(zhí)行請求。

structredisServer{longlongdirty;/* Changes to DB from the last save */time_tlastsave;/* Unix time of last successful save */longlongdirty_before_bgsave;pid_trdb_child_pid;/* PID of RDB saving child */structsaveparam*saveparams;/* Save points array for RDB */}

structsaveparam{time_tseconds;intchanges;};

redisServer?包含的信息很多鼠渺，其中就包含了有關(guān)于?RDB?持久化的信息鸭巴。redisServer->dirty?至上次?save?到目前為止的?change?數(shù)。redisServer->lastsave?上次?save?時間拦盹。

saveparam struct?保存了我們通過?save?命令設(shè)置的參數(shù)鹃祖，time_t?是個?long?時間戳。

typedef__darwin_time_ttime_t;

typedeflong__darwin_time_t;/* time() */

intserverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {for(j =0; j = sp->changes &&server.unixtime-server.lastsave > sp->seconds &&? ? ? ? ? ? ? ? (server.unixtime-server.lastbgsave_try >? ? ? ? ? ? ? ? REDIS_BGSAVE_RETRY_DELAY ||server.lastbgsave_status == REDIS_OK))? ? ? ? ? ? {? ? ? ? ? ? ? ? redisLog(REDIS_NOTICE,"%d changes in %d seconds. Saving...",? ? ? ? ? ? ? ? ? ? sp->changes, (int)sp->seconds);? ? ? ? ? ? ? ? rdbSaveBackground(server.rdb_filename);? ? ? ? ? ? ? ? break;? ? ? ? ? ? }? ? ? ? }}

redis?事件循環(huán)會周期性的執(zhí)行?serverCron?方法普舆，這段代碼會循環(huán)遍歷?server.saveparams?參數(shù)鏈表恬口。

如果?server.dirty?大于等于 我們參數(shù)里配置的變化并且?server.unixtime-server.lastsave?大于參數(shù)里配置的時間并且?server.unixtime-server.lastbgsave_try?減去?bgsave?重試延遲時間或者當前?server.lastbgsave_status==REDIS_OK?則執(zhí)行?rdbSaveBackground?方法。

AOF?(Append-only file)

AOF?持久化是采用對文件進行追加對方式進行沼侣，每次追加都是?redis?處理的 命令祖能。有點類似?command sourcing 命令溯源?的模式。

只要我們可以將所有的命令按照執(zhí)行順序在重放一遍就可以還原最終的?redis?內(nèi)存狀態(tài)蛾洛。

AOF?持久化最大的優(yōu)勢是可以縮短數(shù)據(jù)丟失的間隔养铸，可以做到秒級的丟失率。RDB?會丟失上一個保存周期到目前的所有數(shù)據(jù)，只要沒有觸發(fā)?save?命令設(shè)置的?save seconds changes?閾值數(shù)據(jù)就會一直不被持久化揭厚。

structredisServer{/* AOF buffer, written before entering the event loop */sds aof_buf; }

structsdshdr{unsignedintlen;unsignedintfree;charbuf[];};

aof_buf?是命令緩存區(qū)却特，采用?sds?結(jié)構(gòu)緩存，每次當有命令被執(zhí)行當時候都會寫一次到?aof_buf?中筛圆。有幾個配置用來控制?AOF?持久化的機制裂明。

appendonlynoappendfilename"appendonly.aof"

appendonly?用來控制是否開啟?AOF?持久化，appendfilename?用來設(shè)置?aof?文件名太援。

appendfsyncalwaysappendfsync everysecappendfsyncno

appendfsync?用來控制命令刷盤機制∶龌蓿現(xiàn)在操作系統(tǒng)都有文件?cache/buffer?的概念，所有的寫入和讀取都會走?cache/buffer提岔，并不會每次都同步刷盤仙蛉，因為這樣性能一定會受影響。所以?redis?也提供了這個選項讓我們來自己根據(jù)業(yè)務(wù)場景控制碱蒙。

always?：每次將?aof_buf?命令寫入?aof?文件并且執(zhí)行實時刷盤荠瘪。

everysec?：每次將?aof_buf?命令寫入?aof?文件，但是每隔一秒執(zhí)行一次刷盤赛惩。

no?：每次將?aof_buf?命令寫入?aof?文件不執(zhí)行刷盤哀墓，由操作系統(tǒng)來自行控制。

AOF?也是采用后臺子進程的方式進行喷兼，與主進程共享數(shù)據(jù)空間也就是?aof_buf篮绰，但是只要開始了?AOF?子進程之后?redis 事件循環(huán)文件事件處理器?會將之后的命令寫入另外一個?aof_buf?，這樣就可以做到平滑的切換季惯。

AOF?會不斷的追加命令進?aof?文件吠各，隨著時間和并發(fā)量的加大?aof?文件會極速膨脹，所以有必要對這個文件大小進行優(yōu)化勉抓。redis?基于?rewrite?重寫對文件進行壓縮贾漏。

no-appendfsync-on-rewriteno/yesauto-aof-rewrite-percentage100auto-aof-rewrite-min-size64mb

no-appendfsync-on-rewrite?控制是否在?bgrewriteaof?的時候還需要進行命令追加，如果追加可能會出現(xiàn)磁盤?IO?跑高現(xiàn)象藕筋。

上面說過磕瓷，當?AOF?進程在執(zhí)行的時候原來的事件循環(huán)還會正常的追加命令進?aof?文件，同時還會追加命令進另外一個?aof_buf?念逞，用來做新?aof?文件的重寫。這是兩條并行的動作边翁，如果我們設(shè)置成?yes?就不追加原來的?aof_buf?因為新的?aof?文件已經(jīng)包含了之后進來的命令翎承。

auto-aof-rewrite-percentage、auto-aof-rewrite-min-size 64mb?這兩個配置前者是文件增長百分比來進行?rewrite?符匾，后者是按照文件大小增長進行?rewrite?叨咖。

歡迎工作一到五年的Java工程師朋友們加入Java架構(gòu)開發(fā)： 854393687

群內(nèi)提供免費的Java架構(gòu)學習資料（里面有高可用、高并發(fā)、高性能及分布式甸各、Jvm性能調(diào)優(yōu)垛贤、Spring源碼，MyBatis趣倾，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構(gòu)資料）合理利用自己每一分每一秒的時間來學習提升自己聘惦，不要再用"沒有時間“來掩飾自己思想上的懶惰！趁年輕儒恋，使勁拼善绎，給未來的自己一個交代！