通過分析底層的資料結構，學習如何根據場景選型和設計
redis使用的字元串sds有别于c語言中的字元串
free字段為已配置設定但未使用的空間
len為已使用的空間（不計入'\0'）
buf為char數組
redis的字元環結構可以了解為将c字元串封裝了一層，通過加入的屬性字段降低字元串操作的複雜度，提高安全性。
通過len屬性可以在常數複雜度擷取字元串的長度，僅通過len屬性可直接擷取長度，而c語言字元串複雜度需要周遊，長度為o（n）。
二進制安全的。c字元串是ascii編碼的，以'\0'來判斷字元串是否結束，如果資料中包含'\0'字元便會将資料截斷，當做兩個字元串，是以僅限于儲存文本資料。redis字元串通過len屬性來擷取資料而不是通過周遊尋找結束标志，是以可以存儲任意内容的二進制資料。
相容c字元串的操作。預設在字元串最後加'\0‘，使用c庫字元串的部分操作。
避免緩沖區溢出。其實原理就是根據redis字元串的特點重寫了c可能造成記憶體溢出的函數，如strcat拼接字元串函數，c語言中需人為保證目标字元串的空間足夠大，否會造成溢出，而redis字元串通過free屬性來自動判斷是否可容納源字元串，否則會擴充自身記憶體再拼接。
減少記憶體配置設定次數。空間和效率的問題，redis采用的是犧牲空間來換取效率的提升，避免多次的申請或釋放記憶體。redis是kv型資料庫，要求速度快，資料也多為頻繁修改，是以犧牲一部分空間是可取的。它提供了兩種政策，空間預配置設定和惰性釋放。預配置設定指的是一個字元串修改後會同時配置設定一定大小的空間給free預留，避免再次修改配置設定記憶體。惰性釋放是字元串縮短後不是放空間而是給free記錄，避免釋放空間。
預配置設定和惰性釋放在memcache中也使用了，不過它是從記憶體管理的角度出發的。通過在初始化時對整個記憶體進行預配置設定，減少動态申請記憶體的操作帶來的消耗，使用的記憶體都是連續的，避免了記憶體碎片，記憶體也不會回收而是通過内個slab的slot指針數組來儲存。關于memcache的記憶體管理的機制具體見這裡
該類型是字元串對象的一種實作方式，并用于aof緩沖區和用戶端輸入緩沖區。
redis使用的聯表示标準的雙端無環連結清單
其中，head和tail表示連結清單的表頭和表尾節點，len表示連結清單中節點的數目，dup、free、match分别為複制、釋放和對比函數。
連結清單結構的特點是可以快速的在表頭和表尾插入和删除元素，但查找複雜度高，是清單的底層實作之一，也是以清單沒有提供判斷某一進制素是否在清單中的借口，因為在連結清單中查找複雜度高。
redis的字典使用哈希表作為底層實作。
上圖為字典結構圖
dict結構中，type表示是dicttype類型的指針，表示操作特定類型的鍵值對的函數，privdata是傳給特定函數的可選參數。ht是包含兩個哈希表的數組，ht[0]表示正常存放資料的hash表，而ht[1]用于rehash，rehashidx是記錄了rehash的進度，正常情況下為-1。
dictht是哈希表，table表示哈希表數組，指針數組，size表示哈希表的大小，used表示已有節點的數目，used/size為負載因子，決定何時進行rehash。sizemask用于計算索引值。
每個哈希表元素是dictentry結構，key為鍵，value可以是一個指針或是一個整數。，next為指向下一個的指針。是傳統的hash表。
redis使用murmurhash算法計算hash值，能有很好的随機分布性，速度也很快。
當負載因子大于3/2時進行擴容操作，擴容大小為第一個大于ht[0].used*2的2^n，當負載因子小于0.1進行縮容，為第一個大于ht[0].used的2^n。
redis采用漸進式rehash，将rehash操作分攤到每次增删改查，具體過程見這裡
字典是資料庫和哈希對象的底層實作，資料庫中dict存放所有kv，v可能是各種對象，而expire存放有過期時間的k和過期時間。用作hash底層時，k和v都是字元串對象。
跳躍表是一種可以快速通路節點的資料結構，性能接近于平衡術，且實作簡單。
跳躍連結清單是一種随機化資料結構，基于并聯的連結清單。跳躍清單是對有序的連結清單增加上附加的前進連結，增加是以随機化的方式進行的，是以在清單中的查找可以快速的跳過部分清單。所有操作都以對數随機化的時間進行。
header和tail指向表頭和表尾，level表示最大層級，length表示節點數目（不包括首節點）
跳躍表是有序集合的底層實作之一，跳躍表将指向有序集的 score 值和 member 域的指針作為元素， 并以 score 值為索引， 對有序集元素進行排序。
redis根據自己的需求對跳躍表做了更改：
score 值可重複。
對比一個元素需要同時檢查它的 score 和 memeber 。
每個節點帶有高度為 1 層的後退指針，用于從表尾方向向表頭方向疊代，當執行zrevrange或 zrevrangebyscore 這類以逆序處理有序集的指令時，就會用到這個屬性。
redis的整數集合實質上是動态的數組。reids的整數集合是可以根據整數的值，自動選擇用什麼長度來存儲。
encoing标會編碼方式，8/16/32/64位，length表示集合元素的數量，contents表示資料，元素由小到大排列。
當加入的數大于encoding對應的最大長度時，自動進行更新操作。流程是：首先擴充數組空間的大小。将原數組中的原書進行類型擴充并存儲，最後将新插入的數放入對應位置。整數集合不做降級操作。
整數集合是redis集合對象的底層實作之一。當鍵數量小于512并且鍵值為整數時集合使用整數集合作為底層存儲，節約記憶體。如何保證不重複？（待解決）。
redis使用壓縮清單來存儲小整數值或長度比較短的字元串
壓縮清單是為了節省記憶體開發的，是一系列特殊編碼的連續記憶體塊組成的順序型資料結構。
zlbytes記錄整個清單所占的記憶體數
zltail記錄距離尾節點的距離
zllen記錄節點數目
entry是每個節點
zlend清單結束标志
每個節點的組成，previous_entry_length是前一節點的長度，可用于從尾節點向前周遊，encoding記錄content的資料類型和長度，content為節點的值。
當插入或者删除元素時，會導緻previous_entry_length的長度發生變化，如有1子節點為5位元組，如果原先本節點的總大小處于250至253之間，會導緻笑一個節點的previous..的長度發生變化，可能引起連鎖更新的情況。需要不停的重複配置設定空間來存放增大的大小。
但redis中假定的是處于臨界大小的資料很多并且連續這種情況幾率很低，同僚假定被更新的節點數目少。
redis使用壓縮清單來作為清單鍵和哈希鍵的底層實作之一，存儲小整數值或長度比較短的字元串時使用，previous_entry_length的存在使其可以像連結清單一樣周遊。實作hash時順序添加相鄰接的節點為k和v。
type記錄了對象的類型，可以使字元串，清單，哈希，集合和有序集合對象。
encoding記錄的是type對象對應的底層實作，在redis中每種類型隻有少兩種底層實作的資料結構。通過不同的編碼方式是redis可以根據不同的使用場景來選擇不同的實作方式。同時不同編碼在滿足條件時會觸發轉換。
ptr是指向底層實作資料結構的指針。
字元串對象是使用最廣泛的類型，如memcache中的kv的v相似。也是redis其他資料類型嵌套使用的對象類型。有三種編碼方式：int、raw、embstr三種。
字元串對象是大于39位元組的字元串時則私用raw編碼方式存儲，即sds。
smbstr編碼方式是專門儲存短字元産的一種編碼方式，與raw相似，但會調用一次記憶體配置設定函數申請redisobject和sdshdr，連續存儲。但它是隻讀的，當對它修改時類型轉換為raw編碼方式。
ptr指向一個整數，當對已int編碼方式編碼的字元串對象進行append等操作時，會類型轉換為sds類型。
在使用指令incr系列（ incr, decr, incrby）指令時将字元串作為的原子計數器。
使用append指令追加字元串。
将字元串作為getrange 和 setrange的随機通路向量。
在小空間裡編碼大量資料, 或者使用 getbit 和 setbit建立一個redis支援的bloom過濾器。
string是最常用的一種資料類型，普通的key/value存儲都可以歸為此類，value其實不僅是string，
也可以是數字。
redis清單是簡單的字元串清單，按照插入順序排序。你可以添加一個元素導清單的頭部（左邊）或者尾部（右邊） lpush 指令插入一個新的元素導頭部, 而 rpush插入一個新元素導尾部.
redis的清單有兩種實作方式ziplist和linkedlist，
當元素數目小于512個并且每個元素的長度都小于64個位元組時使用該編碼方式。當插入的元素不滿足上述條件則轉換為linkedlist編碼。
實作最新消息排行等功能。
lists的另一個應用就是消息隊列，可以利用lists的push操作，将任務存在lists中，然後工作線程再用pop操作将任務取出進行執行。
從時間複雜度的角度來看redis清單的主要特征是在頭和尾的元素插入和删除是固定時間，即便是數以百萬計的插入。.
在清單的兩端通路元素是非常快的但是如果你試着通路一個非常大的清單的中間的元素是很慢的，因為那是一個o(n)操作。是以list不支援判斷某個key是否在清單中這一指令。
在類似memcache中，結構化的資訊打包成
hashmap，在用戶端序列化後存儲為一個字元串的值（一般是 json
格式），比如使用者的昵稱、年齡、性别、積分等。這時候在需要修改其中某一項時，通常需要将字元串（json）取出來，然後進行反序列化，修改某一項的值，再序列化成字元串（json）存儲回去。操作複雜、也不便于更新修改操作，并發情況。hash完美解決。兩種編碼方式，ziplist和dict，一個ziplist存放了一個key對應的結構化資料。
類似于清單，檔大小和數量不滿足時也會轉換為dict編碼。
這裡k和v都是字元串對象
存儲、讀取、修改使用者的結構化資料
redis 集合（set）是一個無序不重複的字元串集合. 你可以以o(1)的時間複雜度 (無論集合中有多少元素時間複雜度都是常量)完成添加，删除，以及測試元素是否存在。有兩種編碼方式intset和hashtable。
a, inset編碼方式
所有元素都儲存在整數集合中
多次添加相同的元素，最終在集合裡隻會有一個元素。是以在添加元素的時候無須檢測元素是否存在。
一個redis集合支援一些服務端的指令從現有的集合出發去進行集合運算，求交集、并集、差集
set 的内部實作是一個 value永遠為null的hashmap，實際就是通過計算hash的方式來快速排重的，不同于list，可以實作檢查某一key是否在set中，因為底層是hashtable，常量複雜度。
實際應用如計算獨立ip，微網誌共同好友，好友推薦等
有序集合是将集合中的元素增加了一個權重參數 score，使得集合中的元素能夠按 score 進行有序排列，集合的成員是唯一的，但是評分可以是重複了。有序集合使用ziplist和skiplist+dict兩種編碼方式。
第一個節點儲存元素成員，相鄰第二個節點儲存score，編碼方式類似于哈希的ziplist編碼方式。
zset結構同時包含一個字典和一個跳躍表，skiplist儲存了分支從小到大的所有元素，由于跳躍表的查找複雜度較高，是以使用dict結構存成員和分值，查找複雜度為o(1)，而而zrank和zrange指令式則使用skiplist進行範圍操作。
排行榜相關，使用zadd指令去更新它，使用 zrange指令來得到前多少名的使用者，,使用zrank指令傳回該使用者的名詞。同時使用zrank 和 zrange 可以顯示和給定使用者分數相同的所有使用者。
來做帶權重的隊列，如普通消息的score為1，重要消息的score為2，然後工作線程可以選擇按score的倒序來擷取工作任務。讓重要的任務優先執行。
score設為過期時間，需要精準設定過期時間，定期清除過期的資料。
使用有序集合你可以以非常快的速度（o(log(n))）添加，删除和更新元素。因為元素是有序的,
可以很快的根據評分或者次序來擷取一個範圍的元素。通路有序集合的中間元素也是非常快的,是以你能夠使用有序集合作為一個沒有重複成員的智能清單。在有序集合中，可以很快捷的通路一切需要的東西：有序的元素，快速的存在性測試，快速通路集合的中間元素。
原文連結:[http://wely.iteye.com/blog/2337745]