上周看完Redis設(shè)計(jì)與實(shí)現(xiàn)，過程結(jié)合Redis的unstable分支的源碼來對(duì)照，
基本對(duì)Redis的實(shí)現(xiàn)原理有了個(gè)深入的理解邓梅。（書本基于3.0版本，源碼unstable分支現(xiàn)已去到4.0 rc2邑滨，代碼略有不同日缨，但思路總體一致）
最大感受，無論從設(shè)計(jì)還是源碼掖看，Redis都盡量做到簡(jiǎn)單匣距，其中運(yùn)用到的原理也通俗易懂，一點(diǎn)也不會(huì)覺得晦澀哎壳。特別是源碼毅待，簡(jiǎn)潔易讀，真正做到clean and clear归榕， 而且作者對(duì)于代碼的設(shè)計(jì)組織能力功力深厚尸红。
這篇文章以u(píng)nstable分支的源碼為基準(zhǔn)，先從大體上整理Redis的對(duì)象類型以及底層編碼。
對(duì)象類型
Redis對(duì)象由redisObject結(jié)構(gòu)體表示驶乾。
Redis中的每個(gè)鍵值對(duì)的鍵和值都是一個(gè)redisObject邑飒。
共有五種類型的對(duì)象：字符串（String）循签、列表（List）级乐、哈希（Hash）、集合（Set）县匠、有序集合（SortedSet）风科，源碼
server.h如下定義：
/* The actual Redis Object */
#define OBJ_STRING 0
#define OBJ_LIST 1
#define OBJ_SET 2
#define OBJ_ZSET 3
#define OBJ_HASH 4
- 每種類型的對(duì)象至少都有兩種或以上的encoding方式，不同編碼
可以在不同的使用場(chǎng)景上優(yōu)化對(duì)象的使用場(chǎng)景乞旦。用TYPE命令可查看某個(gè)鍵值對(duì)的類型
對(duì)象編碼
Redis目前使用的編碼方式：
/* Objects encoding. Some kind of objects like Strings and Hashes can be
* internally represented in multiple ways. The 'encoding' field of the object
* is set to one of this fields for this object.
*/
#define OBJ_ENCODING_RAW /* Raw representation */ 簡(jiǎn)單動(dòng)態(tài)字符串
#define OBJ_ENCODING_INT /* Encoded as integer */ 整數(shù)
#define OBJ_ENCODING_HT /* Encoded as hash table */ 字典
#define OBJ_ENCODING_ZIPLIST /* Encoded as ziplist */ 壓縮列表
#define OBJ_ENCODING_INTSET /* Encoded as intset */ 整數(shù)集合
#define OBJ_ENCODING_SKIPLIST /* Encoded as skiplist */ 跳躍表
#define OBJ_ENCODING_EMBSTR /* Embedded sds string encoding */ embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串
#define OBJ_ENCODING_QUICKLIST /* Encoded as linked list of ziplists */
本質(zhì)上贼穆，Redis就是基于這些數(shù)據(jù)結(jié)構(gòu)而構(gòu)造出一個(gè)對(duì)象存儲(chǔ)系統(tǒng)。redisObject結(jié)構(gòu)體有個(gè)ptr指針兰粉，指向?qū)ο蟮牡讓訉?shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)故痊，encoding屬性記錄對(duì)象所使用的編碼，即該對(duì)象使用什么數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn)玖姑。
字符串
字符串對(duì)象的編碼可以是 INT愕秫、RAW 或 EMBSTR。
字符串對(duì)象保存的是整數(shù)值并且可以用long表示焰络，那么編碼會(huì)設(shè)置為INT戴甩。當(dāng)字符串值得長(zhǎng)度大于39字節(jié)使用RAW，小于等于39字節(jié)使用EMBSTR闪彼。
Redis在3.0引入EMBSTR編碼甜孤，這是一種專門用于保存短字符串的一種優(yōu)化編碼方式，這種編碼和RAW編碼都是用sdshdr簡(jiǎn)單動(dòng)態(tài)字符串結(jié)構(gòu)來表示畏腕。RAW編碼會(huì)調(diào)用兩次內(nèi)存分配函數(shù)來分別創(chuàng)建redisObject和sdshdr結(jié)構(gòu)缴川，
而EMBSTR只調(diào)用一次內(nèi)存分配函數(shù)來分配一塊連續(xù)的空間保存數(shù)據(jù)，比起RAW編碼的字符串更能節(jié)省內(nèi)存描馅，以及能提升獲取數(shù)據(jù)的速度把夸。
不過要注意！Ａ骰琛扎即！ EMBSTR是不可修改的，當(dāng)對(duì)EMBSTR編碼的字符串執(zhí)行任何修改命令况凉，總會(huì)先將其轉(zhuǎn)換成RAW編碼再進(jìn)行修改谚鄙；而INT編碼在條件滿足的情況下也會(huì)被轉(zhuǎn)換成RAW編碼。
列表
Redis3.0之前的列表對(duì)象的編碼可以是ziplist或者linkedlist刁绒。
當(dāng)列表對(duì)象保存的字符串元素的長(zhǎng)度都小于64字節(jié)并且保存的元素?cái)?shù)量小于512個(gè)闷营，使用ziplist編碼，可以通過修改配置list-max-ziplist-value和list-max-ziplist-entries來修改這兩個(gè)條件的上限值、兩個(gè)條件任意一個(gè)不滿足時(shí)傻盟，ziplist會(huì)變?yōu)閘inkedlist速蕊。
從3.2開始Redis只使用quicklist作為列表的編碼，
quicklist是ziplist和雙向鏈表的結(jié)合體娘赴，quicklist的每個(gè)節(jié)點(diǎn)都是一個(gè)ziplist规哲。可以通過修改list-max-ziplist-size來設(shè)置一個(gè)quicklist節(jié)點(diǎn)上的ziplist的長(zhǎng)度诽表，取正值表示通過元素?cái)?shù)量來限定ziplist的長(zhǎng)度唉锌；負(fù)數(shù)表示按照占用字節(jié)數(shù)來限定，并且Redis規(guī)定只能取-1到-5這五個(gè)負(fù)值
-5: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過64 Kb竿奏。（注：1kb => 1024 bytes）
-4: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過32 Kb袄简。
-3: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過16 Kb。
-2: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過8 Kb泛啸。（默認(rèn)值）
-1: 每個(gè)quicklist節(jié)點(diǎn)上的ziplist大小不能超過4 Kb绿语。
另外配置參數(shù)list-compress-depth表示一個(gè)quicklist兩端不被壓縮的節(jié)點(diǎn)個(gè)數(shù)
0: 表示都不壓縮。默認(rèn)值候址。
1: 表示quicklist兩端各有1個(gè)節(jié)點(diǎn)不壓縮吕粹，中間的節(jié)點(diǎn)壓縮。
2: 表示quicklist兩端各有2個(gè)節(jié)點(diǎn)不壓縮宗雇，中間的節(jié)點(diǎn)壓縮昂芜。
3: 表示quicklist兩端各有3個(gè)節(jié)點(diǎn)不壓縮，中間的節(jié)點(diǎn)壓縮赔蒲。
依此類推…
這里采用的是一種叫LZF的無損壓縮算法
哈希
哈希對(duì)象的編碼可以是ziplist或者h(yuǎn)ashtable泌神。
使用ziplist 編碼時(shí)，保存同一鍵值對(duì)的兩個(gè)節(jié)點(diǎn)總是緊挨在一起舞虱，鍵節(jié)點(diǎn)在前欢际，值節(jié)點(diǎn)在后
同時(shí)滿足以下兩個(gè)條件將使用ziplist編碼：
- 所有鍵和值的字符串長(zhǎng)度小于64字節(jié)；
- 鍵值對(duì)的數(shù)量小于512個(gè)矾兜。
不能滿足這兩個(gè)條件的都需要使用hashtable編碼损趋。以上兩個(gè)上限值可以通過hash-max-ziplist-value和hash-max-ziplist-entries來修改
集合
集合對(duì)象的編碼可以是intset或者h(yuǎn)ashtable。
當(dāng)滿足以下兩個(gè)條件時(shí)使用intset編碼：
- 所有元素都是整數(shù)值椅寺；
- 元素?cái)?shù)量不超過512個(gè)浑槽。
可以修改set-max-intset-entries設(shè)置元素?cái)?shù)量的上限。使用hashtable編碼時(shí)返帕，字典的每一個(gè)鍵都是字符串對(duì)象桐玻，每個(gè)字符串對(duì)象包含一個(gè)集合元素，字典的值全部設(shè)置為null荆萤。
有序集合
有序集合對(duì)象的編碼可以是ziplist或者skiplist镊靴。同時(shí)滿足以下條件時(shí)使用ziplist編碼：
- 元素?cái)?shù)量小于128個(gè)铣卡；
- 所有member的長(zhǎng)度都小于64字節(jié)，
以上兩個(gè)條件的上限值可通過zset-max-ziplist-entries和zset-max-ziplist-value來修改偏竟。
ziplist編碼的有序集合使用緊挨在一起的壓縮列表節(jié)點(diǎn)來保存煮落，第一個(gè)節(jié)點(diǎn)保存member，第二個(gè)保存score踊谋。ziplist內(nèi)的集合元素按score從小到大排序蝉仇，score較小的排在表頭位置。
skiplist編碼的有序集合底層是一個(gè)命名為zset的結(jié)構(gòu)體褪子，而一個(gè)zset結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表量淌。跳躍表按score從小到大保存所有集合元素。
而字典則保存著從member到score的映射嫌褪，這樣就可以用O(1)的復(fù)雜度來查找member對(duì)應(yīng)的score值。
雖然同時(shí)使用兩種結(jié)構(gòu)胚股，但它們會(huì)通過指針來共享相同元素的member和score笼痛，因此不會(huì)浪費(fèi)額外的內(nèi)存。
參考：
Redis設(shè)計(jì)與實(shí)現(xiàn)
New encoding for string: embedded SDS. #543
Redis內(nèi)部數(shù)據(jù)結(jié)構(gòu)詳解(5)——quicklist
Redis Quicklist - From a More Civilized Age
