本文已收錄在Github，關注我，緊跟本系列專欄文章，咱們下篇再續！

• ?? 魔都架構師 | 全網30W技術追隨者
• ?? 大廠分布式系統/數據中臺實戰專家
• ?? 主導交易系統百萬級流量調優 & 車聯網平臺架構
• ?? AIGC應用開發先行者 | 區塊鏈落地實踐者
• ?? 以技術驅動創新，我們的征途是改變世界！
• ?? 實戰干貨：編程嚴選網

0 概述

數據結構和內部編碼

無傳統關系型數據庫的 Table 模型

schema所對應的db僅以編號區分。同一 db 內，key 作為頂層模型，它的值是扁平化的。即 db 就是key的命名空間。

key的定義通常以 : 分隔，如：Article:Count:1

常用的Redis數據類型有：string、list、set、map、sorted-set

redisObject通用結構

Redis中的所有value 都是以object 的形式存在的，其通用結構：

typedef struct redisObject {
  	// type數據類型：指 string、list 等類型
    unsigned type:4;
  
    // 編碼方式：這些結構化類型具體實現方式，同一類型可有多種實現。如string可用int實現，也可用char[]；list可用ziplist或鏈表實現
    unsigned encoding:4;

    /**
     * 對象最后一次被訪問的時間
     * 本對象的空轉時長，用于有限內存下長時間不訪問的對象清理
     * 記錄LRU信息，LRU_BITS=24 bits
     * LRU time（LRU時鐘值） (relative to global lru_clock，相對于全局LRU時鐘) or
     * LFU data (least significant 8 bits frequency
     * and most significant 16 bits access time).
     */
    unsigned lru:LRU_BITS;
		
  	// 對象引用計數，用于GC
    int refcount;

    // 指向實際值的指針 數據指針：指向以 encoding 方式實現這個對象實際實現者的地址。如：string 對象對應的SDS地址（string的數據結構/簡單動態字符串）
    void *ptr;
} robj;

單線程

單線程為何這么快？

• 純內存
• 非阻塞I/O
• 避免線程切換和競態消耗

• 一次只運行一條命令
• 拒絕長(慢)命令：keys, flushall, flushdb, slow lua script, mutil/exec, operate big value(collection)
• 其實不是單線程
  fysnc file descriptor
  close file descriptor

1 string

Redis中的 string 可表示很多語義

• 字節串（bits）
• 整數
• 浮點數

redis會按具體場景完成自動轉換，并按需選取底層的實現方式。如整數可由32-bit/64-bit、有符號/無符號承載，以適應不同場景對值域的要求。

字符串鍵值結構，也能是JSON串或XML結構

內存結構

在Redis內部，string的內部以 int、SDS（簡單動態字符串 simple dynamic string）作為存儲結構

• int 用來存放整型
• SDS 用來存放字節/字符和浮點型SDS結構

SDS

typedef struct sdshdr {
    // buf中已經占用的字符長度
    unsigned int len;
    // buf中剩余可用的字符長度
    unsigned int free;
    // 數據空間
    char buf[];
}

結構圖：

存儲內容為“Redis”，Redis用類似C語言存儲方法，用'\0'結尾（僅是定界符)。
SDS的free 空間大小為0，當free > 0時，buf中的free 區域的引入提升了SDS對字符串的處理性能，可減少處理過程中的內存申請和釋放次數。

buf的擴縮容

當對SDS 進行操作時，若超出容量。SDS會對其進行擴容，觸發條件如下：

• 字節串初始化時，buf的大小 = len + 1，即加上定界符'\0'剛好用完所有空間
• 當對串的操作后小于1M時，擴容后的buf 大小 = 業務串預期長度 * 2 + 1，也就是擴大2倍。
• 對于大小 > 1M的長串，buf總是留出 1M的 free空間，即2倍擴容，但是free最大為 1M。

字節串與字符串

SDS中存儲的內容可以是ASCII 字符串，也可以是字節串。由于SDS通過len 字段來確定業務串的長度，因此業務串可以存儲非文本內容。對于字符串的場景，buf[len] 作為業務串結尾的'\0' 又可以復用C的已有字符串函數。

SDS編碼的優化

value在內存中有2個部分：redisObject和ptr指向的字節串部分。創建時，通常要分別為2個部分申請內存，但是對于小字節串，可一次性申請。

incr userid:pageview（單線程：無競爭）。緩存視頻的基本信息（數據源在MySQL）

public VideoInfo get(Long id) {
	String redisKey = redisPrefix + id;
	VideoInfo videoInfo e redis.get(redisKey);
	if (videoInfo == null) {
		videoInfo = mysql.get(id);
		if (videoInfo != null) {
			// 序列化
			redis.set(redisKey serialize(videoInfo)):
		}
	}
}			

實現分布式id生成器

incr id (原子操作)

set setnx setxx

• set key value #不管key是否存在，都設置 o(1)
• setnx key value #key不存在，才設置 o(1)
• set key value xx #key存在，才設置 o(1)

mget mset

mget key1 key2 key3 #批量獲取key，原子操作 o(n)
mset key1 valuel key2 value2 key3 value3 #批量設置key-value o(n)

n次get

n次get = n次網絡時間 + n次命令時間

1次mget

1次mget = 1次網絡時間 + n次命令時間

getset、append、strlen

getset key newvalue #set key newvalue 并返回舊的value O(1)
append key value #將value追加到舊的value O(1)
strlen key #返回字符串的長度(注意中文) O(1)

incrbyfloat getrange setrange

#增加key對應的值3.5  o(1)
incrbyfloat key 3.5

#獲取字符串指定下標所有的值  o(1)
getrange key start end

#設置指定下標所有對應的值  o(1)
setrange key index value

字符串總結

命令	含義	復雜度
set key value	設置key-value	O(1)
get key	獲取key-value	O(1)
del key	刪除key-value	O(1)
setnx setxx	根據key是否存在設置key-value	O(1)
Incr decr	計數	O(1)
mget mset	批量操作key-value	O(n)

String類型的value基本操作

針對數字類型的操作：

操作	描述
inc	將指定key內容+1
decr	將指定key內容-1
incrby	將指定key的內容增加指定值
decrby	將指定key的內容減少指定值
incrbyfloat	將指定key的內容減少指定的浮點值

針對字符串類型的操作：

操作	描述
append	將指定字符串添加到key的value后
getrange	對字符串value做范圍截取
setrange	對字符串的指定start和end 做覆蓋操作
strlen	獲取字符串value的長度
getbit	對字符串value，獲取指定偏移量上的bit(位)
setbit	將字符串value視為bit，并設置給定起始位置設置值
bitcount	將字符串value視為bit，并統計1的數量
bitop	對多個key的value做位運算，如：XOR、OR、AND、NOT

string類型value還有一些CAS原子操作，如：get、set、set value nx（如果不存在就設置）、set value xx（若存在就設置)。

String類型是二進制安全的，即在Redis中String類型可包含各種數據，比如一張JPEG圖片或者是一個序列化的Ruby對象。一個String類型的值最大長度512M。

場景

• 原子計數器，使用INCR家族命令：[INCR], [DECR], [INCRBY]
• 使用[APPEND]命令給一個String追加內容
• 做一個隨機訪問的向量（Vector），使用[GETRANGE]和 [SETRANGE]
• 使用[GETBIT] 和[SETBIT]方法，在一個很小的空間中編碼大量的數據或創建一個基于Redis的Bloom Filter 算法

2 List

可從頭部（左側）加入元素，也可以從尾部（右側）加入元素。有序列表。

可通過lrange命令，即從某元素開始讀取多少元素，可基于list實現分頁查詢，這就是基于redis實現簡單的高性能分頁，可以做類似微博那種下拉不斷分頁的東西，性能高，就一頁一頁走。

搞個簡單的消息隊列，從list頭推進去，從list尾拉出來。

List類型中存儲一系列String值，這些String按照插入順序排序。

2.1 數據結構

List 類型的value對象，由 linkedlist 或 ziplist 實現，滿足以下任一條件，會從 ziplist 升級為 linkedlist：

• 元素個數 > list-max-ziplist-entries（默認 512）
• 任一元素長度 > list-max-ziplist-value 字節（默認 64 字節）

2.1.1 linkedlist實現

雙向鏈表：

typedef struct list {
  // 頭結點
  listNode *head;
  // 尾節點
  listNode *tail;
  // 節點值復制函數
  void *(*dup)(void * ptr);
  // 節點值釋放函數
  void *(*free)(void *ptr);
  // 節點值對比函數
  int (*match)(void *ptr, void *key);
  // 鏈表長度
  unsigned long len;  
} list;

// Node節點結構
typedef struct listNode {
	struct listNode *prev;
	struct listNode *next;
	void *value;
} listNode;

linkedlist結構圖：

2.1.2 ziplist實現

存儲在連續內存

• zlbytes，ziplist 的總長度
• zltail，指向最末元素
• zllen，元素的個數
• entry，元素內容
• zlend，恒為0xFF，作為ziplist的定界符

linkedlist和ziplist的rpush、rpop、llen的時間復雜度都是O(1)：

• ziplist的lpush、lpop都會牽扯到所有數據的移動，時間復雜度為O(N)
  由于List的元素少，體積小，這種情況還是可控的。

ziplist的Entry結構：

記錄前一個相鄰的Entry的長度，便于雙向遍歷，類似linkedlist的prev指針。

ziplist是連續存儲，指針由偏移量來承載。Redis中實現了2種方式：

• 當前鄰Entry的長度小于254時，prevlen 只用 1 字節存儲長度
• 否則，prevlen 用 5 字節存儲：第 1 個字節固定為 254（十六進制 FE），表示后面跟著一個 4 字節的長度。
  后面 4 個字節用小端序存儲前一個 entry 的實際長度。

當前一個Entry長度變化時，可能導致后續的所有空間移動，雖然這種情況發生可能性較小。

Entry內容本身是自描述的，意味著第二部分（Entry內容）包含了幾個信息：Entry內容類型、長度和內容本身。而內容本身包含：類型長度部分和內容本身部分。類型和長度同樣采用變長編碼：

• 00xxxxxx ：string類型；長度小于64，0~63可由6位bit 表示，即xxxxxx表示長度

• 01xxxxxx|yyyyyyyy ： string類型；長度范圍是[64, 16383]，可由14位 bit 表示，即xxxxxxyyyyyyyy這14位表示長度。

• 10xxxxxx|yy..y(32個y) : string類型，長度大于16383.

• 1111xxxx ：integer類型，integer本身內容存儲在xxxx 中，只能是1~13之間取值。也就是說內容類型已經包含了內容本身。

• 11xxxxxx ：其余情況，Redis用1個字節的類型長度表示了integer的其他幾種情況，如：int_32、int_24等。
  由此可見，ziplist 的元素結構采用的是可變長的壓縮方法，針對于較小的整數/字符串的壓縮效果較好

• LPUSH：頭部加入一個新元素

• RPUSH：尾部加入一個新元素

在一個空的K執行這些操作時，會創建一個新list。當一個操作清空了一個list時，該list對應的key會被刪除。若使用一個不存在的K，就會使用一個空list。

LPUSH mylist a   # 現在list是 "a"
LPUSH mylist b   # 現在list是"b","a"
RPUSH mylist c   # 現在list是 "b","a","c" (注意這次使用的是 RPUSH)

list的最大長度是2^32 – 1個元素（4294967295，一個list中可以有多達40多億個元素）。

從時間復雜度的角度來看，Redis list類型的最大特性是：即使是在list的頭端或者尾端做百萬次的插入和刪除操作，也能保持穩定的很少的時間消耗。在list的兩端訪問元素是非?？斓模侨绻L問一個很大的list中的中間部分的元素就會比較慢了，時間復雜度是O(N)

2.2 適用場景

粉絲列表

key = 某大v

value = [zhangsan, lisi, wangwu]

• 文章的評論列表

• 社交中作為時間表的建模，LPUSH在用戶時間線中加入新元素，再用LRANGE獲得最近加入的元素

• 可將LPUSH、LTRIM結合用來實現定長列表，列表中只保存最近N個元素

• 做MQ，依賴BLPOP這種阻塞命令

3 Set

類似List，但無序且元素不重復。

向集合中添加多次相同的元素，集合中只存在一個該元素。實際應用中，意味著在添加一個元素前不需要先檢查元素是否存在。

支持多個服務器端命令來從現有集合開始計算集合，所以執行集合的交集，并集，差集都很快。

set的最大長度是2^32 – 1個元素（一個set中可多達40多億個元素）。

3.1 數據結構

Set在Redis中以intset 或 hashtable存儲：

• 對于Set，HashTable的value永遠為NULL
• 當Set中只包含整型數據時，采用intset作為實現

intset

核心元素是一個字節數組，從小到大有序的存放元素

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數量
    uint32_t length;
    // 保存元素的數組
    int8_t contents[];
} intset;

結構圖：

因為元素有序排列，所以SET的獲取操作采用二分查找，復雜度為O(log(N))。

進行插入操作時：

• 首先通過二分查找到要插入位置
• 再對元素進行擴容
• 然后將插入位置之后的所有元素向后移動一個位置
• 最后插入元素

時間復雜度為O(N)。為使二分查找的速度足夠快，存儲在content 中的元素是定長的。

插入2018時，所有元素向后移動，且不會發生覆蓋。當Set中存放的整型元素集中在小整數范圍[-128, 127]內時，可大大節省內存空間。

IntSet支持升級，不支持降級。

3.2 API

基本操作

操作	命令	描述
sadd	sadd key member [member ...]	將一個或多個member放入集合
srem	srem key member [member ...]	移除一個或多個member
sismember	sismember key member	檢查member是否在集合中
scard	scard key	返回集合中元素的個數
smembers	smembers key	返回集合中所有的元素
srandmember	srandmember key [count]	隨機返回1個（默認）或多個成員

復合操作

操作	命令	描述
sinter	sinter key [key...]	返回多個集合的交集
sunion	sunion key [key...]	返回多個集合的并集
sdiff	sdiff key [key...]	返回第一個集合與后面所有集合的差集

復合存儲

操作	命令	描述
sinterstore	sinterstore destination key [key...]	與sinter類似，不過將結果集存儲放到destination集合中
sunionstore	sunionstore destination key [key...]	與sunion類似，將結果集存儲放到destination中
sdiffstore	sdiffstore destination key [key...]	與sdiff類似，將結果集存儲放到destination中

3.3 適用場景

無序集合，自動去重，數據太多時不推薦用。對數據快速全局去重，若系統集群部署，就需基于redis進行全局set去重。

可基于set玩交集、并集、差集操作，如交集：

• 把兩個人的粉絲列表整一個交集，看看倆人的共同好友
• 把兩個大v的粉絲都放在兩個set中，對兩個set做交集

全局這種計算開銷也大。

• 記錄唯一的事物：如想知訪問某博客的IP地址，不要重復的IP，這種情況只需要在每次處理一個請求時簡單的使用SADD命令就可以了，可確保不會插入重復IP

• 表示關系：可用Redis創建一個標簽系統，每個標簽使用一個Set表示。然后可用SADD把具有特定標簽的所有對象的所有ID放在表示這個標簽的Set中。如想知道同時擁有三個不同標簽的對象，那么使用SINTER

• 可使用[SPOP]或 [SRANDMEMBER]命令從集合中隨機的提取元素。

4 Hash

一般可將結構化的數據，如一個對象（前提是這個對象未嵌套其他對象）緩存在Redis。每次讀寫緩存時，直接操作hash里的某字段。

key=150

value={
  "id": 150,
  "name": "JavaEdge",
  "age": 18
}

hash類的數據結構，主要存放一些對象，緩存一些簡單對象，后續操作時，可直接僅修改該對象中的某個字段值。

value={
  "id": 150,
  "name": "JavaEdge",
  "age": 25
}

因為Redis本身是一個KV存儲結構，Hash結構可理解為subkey - subvalue
這里面的subkey - subvalue只能是

• 整型
• 浮點型
• 字符串

因為Map的 value 可表示整型和浮點型，因此Map也可用 hincrby 對某個field的value值做自增操作。

5.1 內存數據結構

hash有HashTable 和 ziplist 兩種實現。對于數據量較小的hash，使用ziplist 實現。

5.1.1 HashTable實現

HashTable在Redis中分為3層，自底向上：

• dictEntry：管理一個field - value 對，保留同一桶中相鄰元素的指針，以此維護Hash 桶中的內部鏈
• dictht：維護Hash表的所有桶鏈
• dict：當dictht需要擴容/縮容時，用戶管理dictht的遷移

dict是Hash表存儲的頂層結構

// 哈希表（字典）數據結構，Redis 的所有鍵值對都會存儲在這里。其中包含兩個哈希表。
typedef struct dict {
    // 哈希表的類型，包括哈希函數，比較函數，鍵值的內存釋放函數
    dictType *type;
    // 存儲一些額外的數據
    void *privdata;
    // 兩個哈希表
    dictht ht[2];
    // 哈希表重置下標，指定的是哈希數組的數組下標
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 綁定到哈希表的迭代器個數
    int iterators; /* number of iterators currently running */
} dict;

Hash表的核心結構是dictht，它的table 字段維護著 Hash 桶，桶（bucket）是一個數組，數組的元素指向桶中的第一個元素（dictEntry）。

typedef struct dictht { 
    //槽位數組
    dictEntry **table; 
    //槽位數組長度
    unsigned long size; 
    //用于計算索引的掩碼 
    unsigned long sizemask;
    //真正存儲的鍵值對數量
    unsigned long used; 
} dictht;

結構圖：

Hash表使用【鏈地址法】解決Hash沖突。當一個 bucket 中的 Entry 很多時，Hash表的插入性能會下降，此時就需要增加bucket的個數來減少Hash沖突。

Hash表擴容

和大多數Hash表實現一樣，Redis引入負載因子，判定是否需增加bucket個數：

負載因子 = Hash表中已有元素 / bucket數量

擴容后，bucket 數量是原先2倍。目前有2 個閥值：

• ＜1：一定不擴容

• ＞5：一定擴容

• 1 ~ 5 之間：Redis 若未進行bgsave/bdrewrite 操作時則會擴容

• 當key - value 對減少時，低于0.1時會進行縮容?？s容之后，bucket的個數是原先的0.5倍

5.1.2 ziplist 實現

和List#ziplist實現類似，都是通過Entry 存放元素。不同的是，Map#ziplist的Entry個數總是2的整數倍：

• 第奇數個Entry存放key
• 下個相鄰Entry存放value

ziplist承載時，Map的大多數操作不再是O(1)，而是由Hash表遍歷，變成鏈表遍歷，復雜度變為O(N)。
由于Map相對較小時采用ziplist，采用Hash表時計算hash值的開銷較大，因此綜合起來ziplist性能相對好一些。

哈希鍵值結構

特點

• Map的map
• Small redis
• field不能相同，value可相同

hget key field O(1)
# 獲取 hash key 對應的 field 的 value

hset key field value O(1)
#  設置 hash key 對應的 field 的 value

hdel key field O(1)
# 刪除 hash key 對應的 field 的 value

5.2 實操

127.0.0.1:6379> hset user:1:info age 23
(integer) 1
127.0.0.1:6379> hget user:1:info age
"23"
127.0.0.1:6379> hset user:1:info name JavaEdge
(integer) 1
127.0.0.1:6379> hgetall user:1:info
1) "age"
2) "23"
3) "name"
4) "JavaEdge"
127.0.0.1:6379> hdel user:1:info age
(integer) 1
127.0.0.1:6379> hgetall user:1:info
1) "name"
2) "JavaEdge"

hexists key field O(1)
# 判斷hash key是否有field
hlen key O(1)
# 獲取hash key field的數量

127.0.0.1:6379> hgetall user:1:info
1) "name"
2) "JavaEdge"
127.0.0.1:6379> HEXISTS user:1:info name
(integer) 1
127.0.0.1:6379> HLEN user:1:info
(integer) 1

hmget key field1 field2... fieldN O(N)
# 批量獲取 hash key 的一批 field 對應的值
hmset key field1 value1 field2 value2...fieldN valueN O(N)
# 批量設置 hash key的一批field value

redis-cli
127.0.0.1:6379> hmset user:2:info age 30 name kaka page 50
OK

127.0.0.1:6379> hlen user:2:info
(integer) 3

127.0.0.1:6379> hmget user:2:info age name
1) "30"
2) "kaka"

記錄網站每個用戶個人主頁的訪問量

hincrby user:1:info pageview count

緩存視頻的基本信息（數據源MySQL）偽代碼

public VideoInfo get(long id) {
  String redisKey = redisPrefix + id;
  Map<String,String> hashMap = redis.hgetAll(redisKey);
  VideoInfo videoInfo = transferMap ToVideo(hashMap);
  if (videoInfo == null) {
  videoInfo = mysql.get(id);
    if (videoInfo != nul) {
    	redis.hmset(redisKey transferVideo ToMap(videoInfol);
    }
  }
  return videoInfo;
}

hgetall key O(N) 小心使用，牢記單線程?。。?返回 hash key 對應所有的 filed 和 value

hvals key O(N)
返回 hash key 對應所有的 filed 的 value

hkeys key O(N)
返回 hash key 對應所有 filed

用戶信息，string實現：

Key  user:1
value(serializable:json,xml,protobuf)

{
  "id": 1,
  "name": "JavaEdge",
  "age": 18,
  "pageView": 500000
}

set user:1 serialize(userinfo)

5.3 適用場景

用戶信息

方便單條更新，但信息非整體，不便管理：

用戶信息(string實現-v2)

41
set user:1:age 41

key               value
user:1:name       world
user:1:age        40
user:1:pageView   500000

用戶信息(hash)

key            field     value

user:1:info →  name      ronaldo
               age       40
               pageView  500000
  

  
key                    field        value
                      ┌─────────────┬─────────────────┐
user:1:info ────────> │ name        │ ronaldo         │
                      ├─────────────┼─────────────────┤
                      │ age         │ 41              │
                      ├─────────────┼─────────────────┤
                      │ pageView    │ 500000          │
                      ├─────────────┼─────────────────┤
                      │ link        │ tv.sohu.com     │
                      └─────────────┴─────────────────┘
  
hset user:1:info age 41
hset user:1:info link tv.sohu.com

3種方案比較：

命令	優點	缺點
string v1	編程簡單 可能節約內存	1. 序列化開銷 2. 設置屬性要操作整個數據
string v2	直觀 可以部分更新	1. 內存占用較大 2. key較為分散
hash	直觀 節省空間 可以部分更新	1. 編程稍微復雜 2. ttl不好控制

hsetnx、hincrby、hincrbyfloat

# 設置hash key對應field的value(如field已經存在，則失敗) o(1)
hsetnx key field value

# hash key對應的field的value自增intCounter o(1)
hincrby key field intCounter

#hincrby浮點數版 o(1)
hincrbyfloat key field floatCounter

5.4 小結

命令	復雜度
hget hset hdel	O(1)
hexists	O(1)
hincrby	O(1)
hgetall hvals hkeys	O(n)
hmget hmset	O(n)

Redis Hashes 保存String域和String值之間的映射，所以它們是用來表示對象的絕佳數據類型（比如一個有著用戶名，密碼等屬性的User對象)

| `1` | `@cli` |

| `2` | `HMSET user:1000 username antirez password P1pp0 age 34` |

| `3` | `HGETALL user:1000` |

| `4` | `HSET user:1000 password 12345` |

| `5` | `HGETALL user:1000` |

一個有著少量數據域（這里的少量大概100上下）的hash，其存儲方式占用很小的空間，所以在一個小的Redis實例中就可以存儲上百萬的這種對象

Hash的最大長度是2^32 – 1個域值對（4294967295，一個Hash中可以有多達40多億個域值對）。

5 Sorted Set

6 Bitmaps

位圖類型，String類型上的一組面向bit操作的集合。由于 strings是二進制安全的blob，并且它們的最大長度是512m，所以bitmaps能最大設置 2^32個不同的bit。

7 HyperLogLogs

pfadd/pfcount/pfmerge。

redis使用標準錯誤小于1％的估計度量結束。

無需與需要統計的項相對應的內存，而是使用的內存恒定不變。最壞只需12k，就可計算接近2^64個不同元素的基數。

8 GEO

geoadd/geohash/geopos/geodist/georadius/georadiusbymember

Redis 3.2推出，可將用戶給定的地理位置（經、緯度）信息儲存起來并操作。

本文由博客一文多發平臺 OpenWrite 發布！