Redis的5種類型對象與底層實現(xiàn)

redis在日常coding中使用的場景越來越多，關于redis的背景鋪墊就不在此贅述，獻上官方介紹。

Redis is an open source (BSD licensed), in-memory data structure store, used as a database, cache and message broker. It supports data structures such as strings, hashes, lists, sets, sorted sets with range queries, bitmaps, hyperloglogs, geospatial indexes with radius queries and streams. Redis has built-in replication, Lua scripting, LRU eviction, transactions and different levels of on-disk persistence, and provides high availability via Redis Sentinel and automatic partitioning with Redis Cluster.

本篇主要講解redis的五種類型對象及底層的實現(xiàn)原理，并簡單總結redis在實現(xiàn)過程中的部分優(yōu)化方式。

redis的對象都可以用以下結構表示

typedef struct redisObject{
   //類型
   unsigned tyep:4;
   //編碼
   unsingned encoding:4;
   //指向底層實現(xiàn)的數(shù)據(jù)結構的指針
   void *ptr;
   //...
}

其中的類型屬性(type)即我們通常說的五種類型對象分別為：STRING,LIST,HASH,SET以及ZSET。而encoding屬性記錄對象所使用的編碼，即底層的實現(xiàn)，每種類型屬性都對應著兩種以上編encoding屬性。Redis的類型與底層編碼共有以下的對應關系

String

編碼格式

String 的底層實現(xiàn)為int,sds(simple dynamic string)和embrStr,其中embtSds是sds的優(yōu)化版。其中embstr是只讀的，對string對象的任何修改都會使embstr升級為sds.
1、當存儲對象為整數(shù)，且可以被表現(xiàn)為long類型時，redis會使用int存儲對象。
2、當存儲對象為string，且長度小于等于32字節(jié)時候，會使用embstr存儲對象。
3、當存儲對象為string，且長度大于32字節(jié)時會使用sds存儲對象。
embstr與sds的區(qū)別在于redisObject對象創(chuàng)建時只生成一次，redisObject與ptr對象排列在一起，而sds編碼格式下會生成兩次，首先創(chuàng)建redisObject，再創(chuàng)建*ptr對象。

優(yōu)化點

SDS屬于redis實現(xiàn)的str，具有其基本格式如下

sds示例.png

sds具有以下特點
1、存在參數(shù)表示sds的長度，求長度時間復雜度O(1)
2、存在預分配策略，新增字段不需要頻繁分配內存，不存在緩沖區(qū)溢出風險(string小于1M，未分配長度等于已分配長度，string大于1M, 未分配長度為1M)，且存在惰性釋放的能力。

List

list底層基于linledList和zipList
linkedlist屬于雙端無環(huán)鏈表

壓縮列表組成部分.png

壓縮節(jié)點組成部分.png

為什么說壓縮列表的壓縮體現(xiàn)在哪里？
如上圖所示：字段與字段之間是是緊密排列在一起的，通過previous可以定位到前一個節(jié)點，實現(xiàn)從后到前的遍歷。而linkedlist通過pre next指針指向下一個節(jié)點，兩個指針至少占用16個字節(jié)。

Hash

hash底層基于ziplist或hashtable
其中ziplist如list中介紹，其中的區(qū)別在于作為hash的底層實現(xiàn)時候，key與value緊密存儲在一起，其他與作為list底層一致。

hash表結構.png

hashtable示意.png

Set

整數(shù)集合.png

而hashTable存儲時候，將相關值存儲在key上，value為null

ZSet

zset底層基于ziplist以及 skipList與hashTable的結合。其中zipList中集合的元素按分值從小到大排序，分值較小的元素放在左邊，元素值與分值緊密排列在一起。

有序集合同時保存在字典和跳躍表中.png