REDIS

redis的全稱是REmote DIctionary Service，直接翻譯過來就是遠(yuǎn)程字典服務(wù)

redis的定位和特性

• SQL與NoSQL

在絕大部分時(shí)候，我們都會(huì)首先考慮用關(guān)系型數(shù)據(jù)庫來存儲我們的數(shù)據(jù)，比如Oracle，MySQL，SQLServer 等

關(guān)系型數(shù)據(jù)庫的特點(diǎn)：
1、它以表格的形式，基于行存儲數(shù)據(jù)，是一個(gè)二維的模式。
2、它存儲的是結(jié)構(gòu)化的數(shù)據(jù)，數(shù)據(jù)存儲有固定的模式（schema），數(shù)據(jù)需要適應(yīng)表結(jié)構(gòu)。
3、表與表之間存在關(guān)聯(lián)（Relationship）。
4、大部分關(guān)系型數(shù)據(jù)庫都支持 SQL（結(jié)構(gòu)化查詢語言）的操作，支持復(fù)雜的關(guān)聯(lián)查詢。
5、通過支持事務(wù)（ACID 酸）來提供嚴(yán)格或者實(shí)時(shí)的數(shù)據(jù)一致性。

局限性（缺點(diǎn)）：
1、要實(shí)現(xiàn)擴(kuò)容的話，只能向上（垂直）擴(kuò)展，比如磁盤限制了數(shù)據(jù)的存儲，就要擴(kuò)大磁盤容量，通過堆硬件的方式，不支持動(dòng)態(tài)的擴(kuò)縮容。水平擴(kuò)容需要復(fù)雜的技術(shù)來實(shí)現(xiàn)，比如分庫分表。

2、表結(jié)構(gòu)修改困難，因此存儲的數(shù)據(jù)格式也受到限制。

3、在高并發(fā)和高數(shù)據(jù)量的情況下，我們的關(guān)系型數(shù)據(jù)庫通常會(huì)把數(shù)據(jù)持久化到磁盤，基于磁盤的讀寫壓力比較大。

為了規(guī)避關(guān)系型數(shù)據(jù)庫的一系列問題，我們就有了非關(guān)系型的數(shù)據(jù)庫，我們一般把它叫做“non-relational”或者“Not Only SQL”。NoSQL 最開始是不提供 SQL 的數(shù)據(jù)庫的意思，但是后來意思慢慢地發(fā)生了變化。

非關(guān)系型數(shù)據(jù)庫的特點(diǎn)：
1、存儲非結(jié)構(gòu)化的數(shù)據(jù)，比如文本、圖片、音頻、視頻。

2、表與表之間沒有關(guān)聯(lián)，可擴(kuò)展性強(qiáng)。

3、保證數(shù)據(jù)的最終一致性。遵循 BASE（堿）理論。 Basically Available（基本可用）； Soft-state（軟狀態(tài)）； Eventually Consistent（最終一致性）。

4、支持海量數(shù)據(jù)的存儲和高并發(fā)的高效讀寫。

5、支持分布式，能夠?qū)?shù)據(jù)進(jìn)行分片存儲，擴(kuò)縮容簡單。

幾種常見的非關(guān)系型數(shù)據(jù)庫的存儲類型：
1、KV 存儲，用 Key Value 的形式來存儲數(shù)據(jù)。比較常見的有 Redis 和MemcacheDB。
2、文檔存儲，MongoDB。
3、列存儲，HBase。
4、圖存儲，這個(gè)圖（Graph）是數(shù)據(jù)結(jié)構(gòu)，不是文件格式。Neo4j。
5、對象存儲。
6、XML 存儲。

• redis的特性
  中文網(wǎng)站：http://www.redis.cn/

特性：
1、更豐富的數(shù)據(jù)類型
2、進(jìn)程內(nèi)與跨進(jìn)程；單機(jī)與分布式
3、功能豐富：持久化機(jī)制、過期策略
4、支持多種編程語言
5、高可用，集群

Redis的安裝啟動(dòng)

CentOS7安裝Redis單實(shí)例

1、下載redis
下載地址在：redis.io
比如把Redis安裝到/usr/local/soft/

cd /usr/local/soft/
wget http://download.redis.io/releases/redis-5.0.5.tar.gz

2、解壓壓縮包
tar -zxvf redis-5.0.5.tar.gz
3、安裝gcc依賴，Redis是C語言編寫的，編譯需要
yum install gcc
4、編譯安裝

cd redis-5.0.5
make MALLOC=libc

將/usr/local/redis-5.0.5/src目錄下二進(jìn)制文件安裝到/usr/local/bin
cd src
make install

5、修改配置文件

默認(rèn)的配置文件是/usr/local/redis-5.0.5/redis.conf
后臺啟動(dòng)
daemonize no  改為   daemonize yes

下面一行必須改成 bind 0.0.0.0 或注釋，否則只能在本機(jī)訪問
bind 127.0.0.1 

如果需要密碼訪問，取消requirepass的注釋
requirepass yourpassword

6、使用指定配置文件啟動(dòng)Redis
/usr/local/soft/redis-5.0.5/src/redis-server /usr/local/soft/redis-5.0.5/redis.conf
7、進(jìn)入客戶端
/usr/local/soft/redis-5.0.5/src/redis-cli
8、停止redis（在客戶端中）

redis> shutdown
或
ps -aux | grep redis
kill -9 xxxx

服務(wù)啟動(dòng)

1、src 目錄下，直接啟動(dòng)./redis-server

2、后臺啟動(dòng)（指定配置文件）

1、redis.conf 修改兩行配置
daemonize yes
bind 0.0.0.0

2、啟動(dòng) Redis
redis-server /usr/local/soft/redis-5.0.5/redis.conf

總結(jié)：redis 的參數(shù)可以通過三種方式配置：一種是 redis.conf，一種是啟動(dòng)時(shí)--攜帶的參數(shù)，一種是 config set

redis基本操作

redis默認(rèn)有16個(gè)庫（0-15），可以在配置文件中修改，默認(rèn)使用的第一個(gè)db0

缺點(diǎn)：因?yàn)闆]有完全隔離，不像數(shù)據(jù)庫的 database，不適合把不同的庫分配給不同的業(yè)務(wù)使用。

在redis的客戶端中可以操作（所有庫不受限制操作）：
切換數(shù)據(jù)庫
select 0

清空當(dāng)前數(shù)據(jù)庫
flushdb

清空所有數(shù)據(jù)庫
flushall

Redis 是字典結(jié)構(gòu)的存儲方式，采用 key-value 存儲。key 和 value 的最大長度限制是 512M

key大小限制.png

命令參考

最新版的redis的基本數(shù)據(jù)類型
String、Hash、Set、List、Zset、Hyperloglog、Geo、Streams

Redis基本數(shù)據(jù)類型

最基本也是最常用的數(shù)據(jù)類型就是 String，set 和 get 命令就是 String 的操作命令。

String 字符串

• 存儲類型
  可以用來存儲字符串、整數(shù)、浮點(diǎn)數(shù)

• 操作命令

設(shè)置多個(gè)值：
mset tom 123 amry 456
設(shè)置值，如果key存在，則不成功

基于setnx可實(shí)現(xiàn)分布式鎖，用 del key 釋放鎖：
setnx jenson

使用參數(shù)的方式：
set key value [expiration EX seconds|PX milliseconds][NX|XX]
eg：set lock1 1 EX 10 NX

（整數(shù)）值遞增：
incr vincent
incrby vincent10

（整數(shù)）值遞減：
decr vincent
decrby vincent 10

浮點(diǎn)數(shù)增量：
set f  2.1
incrbyfloat f 3.3

獲取多個(gè)值：
mget tom  amry 

獲取值長度：
strlen vincent

字符串追加內(nèi)容：
append vincent 666

獲取指定范圍的字符：
getrange vincent 0 8

• 存儲（實(shí)現(xiàn)）原理
  1.數(shù)據(jù)模型
  set hello word 為例，因?yàn)?Redis 是 KV 的數(shù)據(jù)庫，它是通過 hashtable 實(shí)現(xiàn)的（我們把這個(gè)叫做外層的哈希）。所以每個(gè)鍵值對都會(huì)有一個(gè) dictEntry（源碼位置：dict.h），里面指向了 key 和 value 的指針，next 指向下一個(gè) dictEntry。

#dict.h源碼：

typedef struct dictEntry {
    void *key; /* key 關(guān)鍵字定義 */
    union {
        void *val; uint64_t u64; /* value 定義 */
        int64_t s64; double d;
} v;
    struct dictEntry *next; /* 指向下一個(gè)鍵值對節(jié)點(diǎn) */
} dictEntry;

存儲結(jié)果圖.png

key 是字符串，但是 Redis 沒有直接使用 C 的字符數(shù)組，而是存儲在自定義的 SDS中。

value 既不是直接作為字符串存儲，也不是直接存儲在 SDS 中，而是存儲在redisObject 中。實(shí)際上五種常用的數(shù)據(jù)類型的任何一種，都是通過 redisObject 來存儲的。

2.redisObject
redisObject 定義在 src/server.h 文件中

typedef struct redisObject {
    unsigned type:4; /* 對象的類型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET */

    unsigned encoding:4; /* 具體的數(shù)據(jù)結(jié)構(gòu) */

    unsigned lru:LRU_BITS; /* 24 位，對象最后一次被命令程序訪問的時(shí)間，與內(nèi)存回收有關(guān) */

    int refcount; /* 引用計(jì)數(shù)。當(dāng) refcount 為 0 的時(shí)候，表示該對象已經(jīng)不被任何對象引用，則可以進(jìn)行垃圾回收了*/

    void *ptr; /* 指向?qū)ο髮?shí)際的數(shù)據(jù)結(jié)構(gòu) */

} robj;

在redis中，可以用type key值 命令來查看對外的類型

3.內(nèi)部編碼

內(nèi)部編碼結(jié)構(gòu).png

查詢對應(yīng)的存儲結(jié)構(gòu)：
127.0.0.1:6379> set number 6
OK
127.0.0.1:6379> set vincent "collections of string elements sorted according to the order of insertion. They are basically linked lists."
OK
127.0.0.1:6379> set big bighead
OK
127.0.0.1:6379> object encoding number
"int"
127.0.0.1:6379> object encoding big
"embstr"
127.0.0.1:6379> object encoding vincent
"raw"

字符串類型的內(nèi)部編碼有三種：
1）、int，存儲 8 個(gè)字節(jié)的長整型（long，2^63-1）。
2）、embstr, 代表 embstr 格式的 SDS（Simple Dynamic String 簡單動(dòng)態(tài)字符串），存儲小于 44 個(gè)字節(jié)的字符串。
3）、raw，存儲大于 44 個(gè)字節(jié)的字符串（3.2 版本之前是 39 字節(jié)）。

4.幾個(gè)問題的解答：
4.1）什么是 SDS？
Redis 中字符串的實(shí)現(xiàn)，在 3.2 以后的版本中，SDS 又有多種結(jié)構(gòu)（sds.h）：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，用于存儲不同的長度的字符串，分別代表 2^5 =32byte，2^8 =256byte，2^16 =65536byte=64KB，2^32byte =4GB。

/* sds.h */
struct __attribute__ ((__packed__)) sdshdr8 {
  uint8_t len; /* 當(dāng)前字符數(shù)組的長度 */
  uint8_t alloc; /*當(dāng)前字符數(shù)組總共分配的內(nèi)存大小 */
  unsigned char flags; /* 當(dāng)前字符數(shù)組的屬性、用來標(biāo)識到底是   sdshdr8 還是 sdshdr16 等 */
  char buf[]; /* 字符串真正的值 */
};

4.2）為什么 Redis 要用 SDS 實(shí)現(xiàn)字符串？
C 語言本身沒有字符串類型（只能用字符數(shù)組 char[]實(shí)現(xiàn)）。

1、使用字符數(shù)組必須先給目標(biāo)變量分配足夠的空間，否則可能會(huì)溢出。
2、如果要獲取字符長度，必須遍歷字符數(shù)組，時(shí)間復(fù)雜度是 O(n)。
3、C 字符串長度的變更會(huì)對字符數(shù)組做內(nèi)存重分配。
4、通過從字符串開始到結(jié)尾碰到的第一個(gè)'\0'來標(biāo)記字符串的結(jié)束，因此不能保存圖片、音頻、視頻、壓縮文件等二進(jìn)制(bytes)保存的內(nèi)容，二進(jìn)制不安全。

SDS的特點(diǎn)：
1、不用擔(dān)心內(nèi)存溢出問題，如果需要會(huì)對 SDS 進(jìn)行擴(kuò)容。
2、獲取字符串長度時(shí)間復(fù)雜度為 O(1)，因?yàn)槎x了 len 屬性。
3、通過“空間預(yù)分配”（ sdsMakeRoomFor）和“惰性空間釋放”，防止多次重分配內(nèi)存。
4、判斷是否結(jié)束的標(biāo)志是** len 屬性**（它同樣以'\0'結(jié)尾是因?yàn)檫@樣就可以使用 C語言中函數(shù)庫操作字符串的函數(shù)了），可以包含'\0'。

存儲二進(jìn)制：BytesTest.java

4.3）embstr 和 raw 的區(qū)別？
embstr 的使用只分配一次內(nèi)存空間（因?yàn)?RedisObject 和 SDS 是連續(xù)的），而 raw需要分配兩次內(nèi)存空間（分別為 RedisObject 和 SDS 分配空間）。

因此與 raw 相比，embstr 的好處在于創(chuàng)建時(shí)少分配一次空間，刪除時(shí)少釋放一次空間，以及對象的所有數(shù)據(jù)連在一起，尋找方便。而 embstr 的壞處也很明顯，如果字符串的長度增加需要重新分配內(nèi)存時(shí)，整個(gè)RedisObject 和 SDS 都需要重新分配空間，因此 Redis 中的 embstr 實(shí)現(xiàn)為只讀。

4.4）int 和embstr 什么時(shí)候轉(zhuǎn)化為raw?
當(dāng) int 數(shù) 據(jù) 不 再 是 整 數(shù) ， 或大小超過了 long 的 范 圍
（2^63-1 =9223372036854775807）時(shí)，自動(dòng)轉(zhuǎn)化為 embstr

127.0.0.1:6379> set s1 1
OK
127.0.0.1:6379> append s1 a
(integer) 2
127.0.0.1:6379> object encoding s1
"raw"

4.5）明明沒有超過閥值，為什么變成raw了？

127.0.0.1:6379> set s2 a
OK
127.0.0.1:6379> object encoding s2
"embstr"
127.0.0.1:6379> append s2 b
(integer) 2
127.0.0.1:6379> object encoding s2
"raw"

對于 embstr，由于其實(shí)現(xiàn)是只讀的，因此在對 embstr 對象進(jìn)行修改時(shí)，都會(huì)先轉(zhuǎn)化為 raw 再進(jìn)行修改。

因此，只要是修改 embstr 對象，修改后的對象一定是 raw 的，無論是否達(dá)到了 44個(gè)字節(jié)。

4.6）當(dāng)長度小于閾值時(shí)，會(huì)還原嗎？
Redis 內(nèi)部編碼的轉(zhuǎn)換，都符合以下規(guī)律：編碼轉(zhuǎn)換在 Redis 寫入數(shù)據(jù)時(shí)完成，且轉(zhuǎn)換過程不可逆，只能從小內(nèi)存編碼向大內(nèi)存編碼轉(zhuǎn)換（但是不包括重新 set）。

4.7）為什么要對底層的數(shù)據(jù)結(jié)構(gòu)進(jìn)行一層包裝呢？
通過封裝，可以根據(jù)對象的類型動(dòng)態(tài)地選擇存儲結(jié)構(gòu)和可以使用的命令，實(shí)現(xiàn)節(jié)省空間和優(yōu)化查詢速度。

5.應(yīng)用場景

緩存

String 類型
例如：熱點(diǎn)數(shù)據(jù)緩存（例如報(bào)表，官員貪污），對象緩存，全頁緩存，可以提升熱點(diǎn)數(shù)據(jù)的訪問速度。

數(shù)據(jù)共享分布式

STRING 類型，因?yàn)?Redis 是分布式的獨(dú)立服務(wù)，可以在多個(gè)應(yīng)用之間共享
例如：分布式 Session

<dependency>
    <groupId>org.springframework.session</groupId>
    <artifactId>spring-session-data-redis</artifactId>
</dependency>

分布式鎖

String 類型 setnx 方法，只有不存在時(shí)才能添加成功，返回 true
SET key value [EX seconds] [PX milliseconds] [NX|XX]

public Boolean getLock(Object lockObject){
    jedisUtil = getJedisConnetion();
    boolean flag = jedisUtil.setNX(lockObj, 1);
    if(flag){
        expire(locakObj,10);
    }
    return flag;
}
?
public void releaseLock(Object lockObject){
    del(lockObj);
}

全局ID

INT 類型，INCRBY，利用原子性（分庫分表的場景，一次性拿一段）
incrby userid 5000

計(jì)數(shù)器

INT 類型，INCR 方法
例如：文章的閱讀量，微博點(diǎn)贊數(shù)，允許一定的延遲，先寫入 Redis 再定時(shí)同步到數(shù)據(jù)庫。

限流

INT 類型，INCR 方法
以訪問者的 IP 和其他信息作為 key，訪問一次增加一次計(jì)數(shù)，超過次數(shù)則返回 false。

位統(tǒng)計(jì)

String 類型的 BITCOUNT

字符是以 8 位二進(jìn)制存儲的。
set s1 a
setbit s1 6 1
setbit s1 7 0
get s1

a 對應(yīng)的 ASCII 碼是 97，轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)是 01100001
b 對應(yīng)的 ASCII 碼是 98，轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)是 01100010

因?yàn)?bit 非常節(jié)省空間（1 MB=8388608 bit），可以用來做大數(shù)據(jù)量的統(tǒng)計(jì)。

例如：在線用戶統(tǒng)計(jì)，留存用戶統(tǒng)計(jì)

setbit onlineusers 0 1
setbit onlineusers 1 1
setbit onlineusers 2 0

支持按位與、按位或等操作

BITOP AND destkey key [key ...] ，對一個(gè)或多個(gè) key 求邏輯并，并將結(jié)果保存到 destkey 。

BITOP OR destkey key [key ...] ，對一個(gè)或多個(gè) key 求邏輯或，并將結(jié)果保存到 destkey 。

BITOP XOR destkey key [key ...] ，對一個(gè)或多個(gè) key 求邏輯異或，并將結(jié)果保存到 destkey 。

BITOP NOT destkey key ，對給定 key 求邏輯非，并將結(jié)果保存到 destkey 。

Hash哈希

Hash存儲.png

• 存儲類型

包含鍵值對的無序散列表，value 只能是字符串，不能嵌套其他類型。

同樣是存儲字符串，Hash 與 String 的主要區(qū)別？
1、把所有相關(guān)的值聚集到一個(gè) key 中，節(jié)省內(nèi)存空間
2、只使用一個(gè) key，減少 key 沖突
3、當(dāng)需要批量獲取值的時(shí)候，只需要使用一個(gè)命令，減少內(nèi)存/IO/CPU 的消耗

Hash不適合的場景：
1、Field 不能單獨(dú)設(shè)置過期時(shí)間
2、沒有 bit 操作
3、需要考慮數(shù)據(jù)量分布的問題（value 值非常大的時(shí)候，無法分布到多個(gè)節(jié)點(diǎn)）

• 操作命令

set操作
hset h1 f 6
hset h1 e 5
hmset h1 a 1 b 2 c 3 d 4

get操作
hget h1 a
hmget h1 a b c d
hkeys h1
hvals h1
hgetall h1

判斷是否存在于哈希表 hash 當(dāng)中。
hget exists h1
刪除操作
hdel h1
獲取數(shù)量
hlen h1

• 存儲（實(shí)現(xiàn)）原理
  Redis 的 Hash 本身也是一個(gè) KV 的結(jié)構(gòu)，類似于 Java 中的 HashMap

外層的哈希（Redis KV 的實(shí)現(xiàn)）只用到了 hashtable。當(dāng)存儲 hash 數(shù)據(jù)類型時(shí)，我們把它叫做內(nèi)層的哈希

內(nèi)層的哈希底層可以使用兩種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)：
ziplist：OBJ_ENCODING_ZIPLIST（壓縮列表）

hashtable：OBJ_ENCODING_HT（哈希表）

127.0.0.1:6379> hset h2 f aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer) 1

127.0.0.1:6379> hset h3 f bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
(integer) 1

127.0.0.1:6379> object encoding h2
"ziplist"

127.0.0.1:6379> object encoding h3
"hashtable"

• ziplist 壓縮列表

ziplist 壓縮列表是什么？
ziplist 是一個(gè)經(jīng)過特殊編碼的雙向鏈表，它不存儲指向上一個(gè)鏈表節(jié)點(diǎn)和指向下一個(gè)鏈表節(jié)點(diǎn)的指針，而是存儲上一個(gè)節(jié)點(diǎn)長度和當(dāng)前節(jié)點(diǎn)長度，通過犧牲部分讀寫性能，來換取高效的內(nèi)存空間利用率，是一種時(shí)間換空間的思想。只用在字段個(gè)數(shù)少，字段值小的場景里面。

typedef struct zlentry {
    unsigned int prevrawlensize; /* 上一個(gè)鏈表節(jié)點(diǎn)占用的長度 */
    unsigned int prevrawlen; /* 存儲上一個(gè)鏈表節(jié)點(diǎn)的長度數(shù)值所需要的字節(jié)數(shù) */
    unsigned int lensize; /* 存儲當(dāng)前鏈表節(jié)點(diǎn)長度數(shù)值所需要的字節(jié)數(shù) */
    unsigned int len; /* 當(dāng)前鏈表節(jié)點(diǎn)占用的長度 */
    unsigned int headersize; /* 當(dāng)前鏈表節(jié)點(diǎn)的頭部大?。╬revrawlensize + lensize），即非數(shù)據(jù)域的大小 */
    unsigned char encoding; /* 編碼方式 */
    unsigned char *p; /* 壓縮鏈表以字符串的形式保存，該指針指向當(dāng)前節(jié)點(diǎn)起始位置 */
} zlentry;

#define ZIP_STR_MASK 0xc0
#define ZIP_INT_MASK 0x30
#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)
#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

圖解.png

什么時(shí)候使用 ziplist 存儲？
當(dāng) hash 對象同時(shí)滿足以下兩個(gè)條件的時(shí)候，使用 ziplist 編碼：
1）所有的鍵值對的健和值的字符串長度都小于等于 64byte（一個(gè)英文字母一個(gè)字節(jié)）；
2）哈希對象保存的鍵值對數(shù)量小于 512 個(gè)。

/* src/redis.conf 配置 */
hash-max-ziplist-value 64 // ziplist 中最大能存放的值長度
hash-max-ziplist-entries 512 // ziplist 中最多能存放的 entry 節(jié)點(diǎn)數(shù)量

/* 源碼位置：t_hash.c ，當(dāng)達(dá)字段個(gè)數(shù)超過閾值，使用 HT 作為編碼 */
if (hashTypeLength(o) > server.hash_max_ziplist_entries)
hashTypeConvert(o, OBJ_ENCODING_HT);
/*源碼位置： t_hash.c，當(dāng)字段值長度過大，轉(zhuǎn)為 HT */
for (i = start; i <= end; i++) {
    if (sdsEncodedObject(argv[i]) &&
        sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
    {
    hashTypeConvert(o, OBJ_ENCODING_HT);
    break;
    }
}

一個(gè)哈希對象超過配置的閾值（鍵和值的長度有>64byte，鍵值對個(gè)數(shù)>512 個(gè)）時(shí)，會(huì)轉(zhuǎn)換成哈希表（hashtable）

• hashtable（dict）
  在 Redis 中，hashtable 被稱為字典（dictionary），它是一個(gè)數(shù)組+鏈表的結(jié)構(gòu)。

Redis 的 KV 結(jié)構(gòu)是通過一個(gè) dictEntry 來實(shí)現(xiàn)的，Redis 同時(shí)又對 dictEntry 進(jìn)行了多層的封裝。

源碼位置：dict.h
typedef struct dictEntry {
    void *key; /* key 關(guān)鍵字定義 */
    union {
        void *val; uint64_t u64; /* value 定義 */
        int64_t s64; double d;
} v;
    struct dictEntry *next; /* 指向下一個(gè)鍵值對節(jié)點(diǎn) */
} dictEntry;

dictEntry 放到了 dictht（hashtable 里面）：

/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table; /* 哈希表數(shù)組 */
    unsigned long size; /* 哈希表大小 */
    unsigned long sizemask; /* 掩碼大小，用于計(jì)算索引值?？偸堑扔?size-1 */
    unsigned long used; /* 已有節(jié)點(diǎn)數(shù) */
} dictht;

ht 放到了 dict 里面：

typedef struct dict {
    dictType *type; /* 字典類型 */
    void *privdata; /* 私有數(shù)據(jù) */
    dictht ht[2]; /* 一個(gè)字典有兩個(gè)哈希表 */
    long rehashidx; /* rehash 索引 */
    unsigned long iterators; /* 當(dāng)前正在使用的迭代器數(shù)量 */
} dict;

由源碼可知：從最底層到最高層dictEntry——dictht——dict——OBJ_ENCODING_HT

哈希的存儲結(jié)構(gòu).png

dictht 后面是 null 說明第二個(gè) ht 還沒用到。dictEntry*后面是 null說明沒有 hash 到這個(gè)地址，dictEntry 后面是null 說明沒有發(fā)生哈希沖突。

為什么要定義兩個(gè)哈希表呢？
redis 的 hash 默認(rèn)使用的是 ht[0]，ht[1]不會(huì)初始化和分配空間，只有在rehash的時(shí)候會(huì)用到。

哈希表 dictht 是用鏈地址法來解決碰撞問題的。在這種情況下，哈希表的性能取決于它的大小（size 屬性）和它所保存的節(jié)點(diǎn)的數(shù)量（used 屬性）之間的比率：
1）比率在 1:1 時(shí)（一個(gè)哈希表 ht 只存儲一個(gè)節(jié)點(diǎn) entry），哈希表的性能最好；
2）如果節(jié)點(diǎn)數(shù)量比哈希表的大小要大很多的話（這個(gè)比例用 ratio 表示，5 表示平均一個(gè) ht 存儲 5 個(gè) entry），那么哈希表就會(huì)退化成多個(gè)鏈表，哈希表本身的性能優(yōu)勢就不再存在。

在這種情況下需要擴(kuò)容，Redis 里面的這種操作叫做 rehash

rehash的步驟：
1、為字符 ht[1]哈希表分配空間，這個(gè)哈希表的空間大小取決于要執(zhí)行的操作，以及 ht[0]當(dāng)前包含的鍵值對的數(shù)量
ht[1]的大小為第一個(gè)大于等于 ht[0].used*2。

2、將所有的ht[0]上的節(jié)點(diǎn) rehash 到 ht[1]上，重新計(jì)算 hash 值和索引，然后放入指定的位置。

3、當(dāng) ht[0]全部遷移到了 ht[1]之后，釋放 ht[0]的空間，將 ht[1]設(shè)置為 ht[0]表，并創(chuàng)建新的 ht[1]，為下次 rehash 做準(zhǔn)備。

什么時(shí)候觸發(fā)擴(kuò)容？

負(fù)載因子(dict.c)

static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

ratio = used / size，已使用節(jié)點(diǎn)與字典大小的比例
dict_can_resize 為 1 并且 dict_force_resize_ratio 已使用節(jié)點(diǎn)數(shù)和字典大小之間的比率超過 1：5，觸發(fā)擴(kuò)容

擴(kuò)容判斷 _dictExpandIfNeeded

if (d->ht[0].used >= d->ht[0].size && (dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;

擴(kuò)容方法 dictExpand

static int dictExpand(dict *ht, unsigned long size) {
dict n; /* the new hashtable */
    unsigned long realsize = _dictNextPower(size), i;
?
/* the size is invalid if it is smaller than the number of
* elements already inside the hashtable */
    if (ht->used > size)
        return DICT_ERR;
?
    _dictInit(&n, ht->type, ht->privdata);
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = calloc(realsize,sizeof(dictEntry*));
?
/* Copy all the elements from the old to the new table:
* note that if the old hash table is empty ht->size is zero,
* so dictExpand just creates an hash table. */
    n.used = ht->used;
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;
?
        if (ht->table[i] == NULL) continue;
?
        /* For each hash entry on this slot... */
        he = ht->table[i];
        while(he) {
            unsigned int h;
?
            nextHe = he->next;
            /* Get the new element index */
            h = dictHashKey(ht, he->key) & n.sizemask;
            he->next = n.table[h];
            n.table[h] = he;
            ht->used--;
            /* Pass to the next element */
            he = nextHe;
        }
    }
    assert(ht->used == 0);
    free(ht->table);
?
    /* Remap the new hashtable in the old */
    *ht = n;
    return DICT_OK;
}

縮容

int htNeedsResize(dict *dict) {
    long long size, used;
?
    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
        (used*100/size < HASHTABLE_MIN_FILL));
}

• 應(yīng)用場景

String

String 可以做的事情，Hash 都可以做

存儲對象類型的數(shù)據(jù)

對象或者一張表的數(shù)據(jù)，比 String 節(jié)省了更多 key 的空間，也更加便于集中管理。

購物車

key：用戶 id；field：商品 id；value：商品數(shù)量
+1：hincr。-1：hdecr。刪除：hdel。全選：hgetall。商品數(shù)：hlen。

List列表

• 存儲類型
  存儲有序的字符串（從左到右），元素可以重復(fù)?？梢猿洚?dāng)隊(duì)列和棧的角色。

  
  
  存儲結(jié)構(gòu).png

• 操作命令

元素增減：
lpush queue a
lpush queue b c

rpush queue d e
lpop queue
rpop queue
?
阻塞：
blpop queue
brpop queue

取值
lindex queue 0
lrange queue 0 -1

存儲結(jié)構(gòu).png

• 存儲（實(shí)現(xiàn)）原理
  在早期的版本中，數(shù)據(jù)量較小時(shí)用 ziplist 存儲，達(dá)到臨界值時(shí)轉(zhuǎn)換為 linkedlist 進(jìn)行存儲，分別對應(yīng)OBJ_ENCODING_ZIPLIST 和OBJ_ENCODING_LINKEDLIST。

3.2 版本之后，統(tǒng)一用 quicklist 來存儲。quicklist 存儲了一個(gè)雙向鏈表，每個(gè)節(jié)點(diǎn)都是一個(gè) ziplist。

127.0.0.1:6379> object encoding queue
"quicklist"

• quicklist
  quicklist（快速列表）是 ziplist 和 linkedlist 的結(jié)合體。
  quicklist.h，head 和 tail 指向雙向列表的表頭和表尾

typedef struct quicklist {
    quicklistNode *head; /* 指向雙向列表的表頭 */
    quicklistNode *tail; /* 指向雙向列表的表尾 */
    unsigned long count; /* 所有的 ziplist 中一共存了多少個(gè)元素 */
    unsigned long len; /* 雙向鏈表的長度，node 的數(shù)量 */
    int fill : 16; /* fill factor for individual nodes */
    unsigned int compress : 16; /* 壓縮深度，0：不壓縮； */
} quicklist;

redis.conf 相關(guān)參數(shù)：

quicklistNode 中的*zl 指向一個(gè) ziplist，一個(gè) ziplist 可以存放多個(gè)元素。

typedef struct quicklistNode {
    struct quicklistNode *prev; /* 前一個(gè)節(jié)點(diǎn) */
    struct quicklistNode *next; /* 后一個(gè)節(jié)點(diǎn) */
    unsigned char *zl; /* 指向?qū)嶋H的 ziplist */
    unsigned int sz; /* 當(dāng)前 ziplist 占用多少字節(jié) */
    unsigned int count : 16; /* 當(dāng)前 ziplist 中存儲了多少個(gè)元素，占 16bit（下同），最大 65536 個(gè) */
    unsigned int encoding : 2; /* 是否采用了 LZF 壓縮算法壓縮節(jié)點(diǎn)，1：RAW 2：LZF */
    unsigned int container : 2; /* 2：ziplist，未來可能支持其他結(jié)構(gòu)存儲 */
    unsigned int recompress : 1; /* 當(dāng)前 ziplist 是不是已經(jīng)被解壓出來作臨時(shí)使用 */
    unsigned int attempted_compress : 1; /* 測試用 */
    unsigned int extra : 10; /* 預(yù)留給未來使用 */
} quicklistNode;

存儲結(jié)構(gòu).png

• 應(yīng)用場景

用戶消息時(shí)間線

由于List 是有序的，可以用來做用戶時(shí)間線

消息隊(duì)列

List 提供了兩個(gè)阻塞的彈出操作：BLPOP / BRPOP，可以設(shè)置超時(shí)時(shí)間
BLPOP：BLPOP key1 timeout 移出并獲取列表的第一個(gè)元素， 如果列表沒有元素會(huì)阻塞列表直到等待超時(shí)或發(fā)現(xiàn)可彈出元素為止。

BRPOP：BRPOP key1 timeout 移出并獲取列表的最后一個(gè)元素， 如果列表沒有元素會(huì)阻塞列表直到等待超時(shí)或發(fā)現(xiàn)可彈出元素為止。

隊(duì)列：先進(jìn)先出：rpush blpop，左頭右尾，右邊進(jìn)入隊(duì)列，左邊出隊(duì)列
棧：先進(jìn)后出：rpush brpop

set集合

String 類型的無序集合，最大存儲數(shù)量為2^32-1（40 億左右）

• 操作命令

添加一個(gè)或者多個(gè)元素
sadd myset a b c d e f g

獲取所有元素
smembers myset

統(tǒng)計(jì)元素個(gè)數(shù)
scard myset

隨機(jī)獲取一個(gè)元素
srandmember key

隨機(jī)彈出一個(gè)元素
spop myset

移除一個(gè)或者多個(gè)元素
srem myset d e f

查看元素是否存在
sismember myset a

• 存儲（實(shí)現(xiàn)）原理
  Redis 用 intset 或 hashtable 存儲 set，如果元素都是整數(shù)類型，就用 inset 存儲，如果不是整數(shù)類型，就用 hashtable（數(shù)組+鏈表的存來儲結(jié)構(gòu)）

KV 怎么存儲 set 的元素？
key 就是元素的值，value 為 null。
如果元素個(gè)數(shù)超過 512 個(gè)，也會(huì)用 hashtable 存儲。

配置文件 redis.conf
set-max-intset-entries 512

127.0.0.1:6379> sadd iset 1 2 3 4 5 6
(integer) 6
127.0.0.1:6379> object encoding iset
"intset"
127.0.0.1:6379> sadd myset a b c d e f
(integer) 6
127.0.0.1:6379> object encoding myset
"hashtable"

• 應(yīng)用場景

抽獎(jiǎng)

隨機(jī)獲取元素：spop myset

點(diǎn)贊、簽到、打卡

微博.png

如微博的 ID 是 t1001，用戶 ID 是 u3001
用 like：t1001 來維護(hù) t1001 這條微博的所有點(diǎn)贊用戶
點(diǎn)贊了這條微博：sadd like:t1001 u3001
取消點(diǎn)贊：srem like:t1001 u3001
是否點(diǎn)贊：sismember like:t1001 u3001
點(diǎn)贊的所有用戶：smembers like:t1001
點(diǎn)贊數(shù)：scard like:t1001

商品標(biāo)簽

用 tags:i5001 來維護(hù)商品所有的標(biāo)簽
sadd tags:i5001 畫面清晰細(xì)膩
sadd tags:i5001 真彩清晰顯示屏
sadd tags:i5001 流暢至極

商品篩選

獲取差集
sdiff set1 set2

獲取交集（ intersection ）
sinter set1 set2

獲取并集
sunion set1 set2

sadd brand:apple iPhone11
sadd brand:ios iPhone11
sad screensize:6.0-6.24 iPhone11
sad screentype:lcd iPhone11
篩選商品，蘋果的，iOS 的，屏幕在 6.0-6.24 之間的，屏幕材質(zhì)是 LCD 屏幕
sinter brand:apple brand:ios screensize:6.0-6.24 screentype:lcd

ZSet 有序集合

• 存儲類型

  
  
  存儲結(jié)構(gòu).png

sorted set，有序的 set，每個(gè)元素有個(gè) score

score 相同時(shí)，按照 key 的 ASCII 碼排序

數(shù)據(jù)結(jié)構(gòu)對比：

• 操作命令

添加元素
zadd myzset 10 java 20 php 30 ruby 40 cpp 50 python

獲取全部元素
zrange myzset 0 -1 withscores
zrevrange myzset 0 -1 withscores

根據(jù)分值區(qū)間獲取元素
zrangebyscore myzset 20 30

移除元素
也可以根據(jù) score rank 刪除
zrem myzset php cpp

統(tǒng)計(jì)元素個(gè)數(shù)
zcard myzset

分值遞增
zincrby myzset 5 python

根據(jù)分值統(tǒng)計(jì)個(gè)數(shù)
zcount myzset 20 60

獲取元素 rank
zrank myzset java

獲取元素 score
zsocre myzset java
也有倒序的 rev 操作（reverse）

• 存儲（實(shí)現(xiàn)）原理
  同時(shí)滿足以下條件時(shí)使用 ziplist 編碼：
  1）元素?cái)?shù)量小于 128 個(gè)
  2）所有 member 的長度都小于 64 字節(jié)

在 ziplist 的內(nèi)部，按照 score 排序遞增來存儲，插入的時(shí)候要移動(dòng)之后的數(shù)據(jù)

對應(yīng) redis.conf 參數(shù)為：
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

超過閾值之后，使用 skiplist+dict 存儲。

什么是skiplist ?

有序鏈表.png

在這樣一個(gè)鏈表中，如果我們要查找某個(gè)數(shù)據(jù)，那么需要從頭開始逐個(gè)進(jìn)行比較，直到找到包含數(shù)據(jù)的那個(gè)節(jié)點(diǎn)，或者找到第一個(gè)比給定數(shù)據(jù)大的節(jié)點(diǎn)為止（沒找到）。也就是說，時(shí)間復(fù)雜度為 O(n)。同樣，當(dāng)我們要插入新數(shù)據(jù)的時(shí)候，也要經(jīng)歷同樣的查找過程，從而確定插入位置。

二分查找法只適用于有序數(shù)組，不適用于鏈表

假如我們每相鄰兩個(gè)節(jié)點(diǎn)增加一個(gè)指針（或者理解為有三個(gè)元素進(jìn)入了第二層），讓指針指向下下個(gè)節(jié)點(diǎn)

image.png

這樣所有新增加的指針連成了一個(gè)新的鏈表，但它包含的節(jié)點(diǎn)個(gè)數(shù)只有原來的一半（上圖中是 5，11）。在插入一個(gè)數(shù)據(jù)的時(shí)候，決定要放到那一層，取決于一個(gè)算法
（在 redis 中 t_zset.c 有一個(gè) zslRandomLevel 這個(gè)方法）。

現(xiàn)在當(dāng)我們想查找數(shù)據(jù)的時(shí)候，可以先沿著這個(gè)新鏈表進(jìn)行查找。當(dāng)碰到比待查數(shù)據(jù)大的節(jié)點(diǎn)時(shí)，再回到原來的鏈表中的下一層進(jìn)行查找。比如，我們想查找 16，查找的路徑是沿著下圖中的指針?biāo)赶虻姆较蜻M(jìn)行的：

查找.png

1. 16 首先和 5 比較，再和 11 比較，比它們都大，繼續(xù)向后比較
2. 但 16 和 17 比較的時(shí)候，比 17 要小，因此回到下面的鏈表（原鏈表），與 13比較
3. 16 比 13 要大，沿下面的指針繼續(xù)向后和 17 比較。16 比 17 小，說明待查數(shù)據(jù) 16 在原鏈表中不存在

在這個(gè)查找過程中，由于新增加的指針，我們不再需要與鏈表中每個(gè)節(jié)點(diǎn)逐個(gè)進(jìn)行比較了，需要比較的節(jié)點(diǎn)數(shù)大概只有原來的一半，這就是跳躍表

為什么不用 AVL 樹或者紅黑樹？
因?yàn)?skiplist 更加簡潔

server.h源碼：

typedef struct zskiplistNode {
    sds ele; /* zset 的元素 */
    double score; /* 分值 */
    struct zskiplistNode *backward; /* 后退指針 */
    struct zskiplistLevel {
        struct zskiplistNode *forward; /* 前進(jìn)指針，對應(yīng) level 的下一個(gè)節(jié)點(diǎn) */
        unsigned long span; /* 從當(dāng)前節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)的跨度（跨越的節(jié)點(diǎn)數(shù)） */
    } level[]; /* 層 */
} zskiplistNode;
?
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; /* 指向跳躍表的頭結(jié)點(diǎn)和尾節(jié)點(diǎn) */
    unsigned long length; /* 跳躍表的節(jié)點(diǎn)數(shù) */
    int level; /* 最大的層數(shù) */
} zskiplist;
?
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

隨機(jī)獲取層數(shù)的函數(shù)（t_zset.c）：

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

• 應(yīng)用場景

排行榜

id 為 1001 的新聞點(diǎn)擊數(shù)加 1
zincrby hotNews:20191001 1 n1001

獲取今天點(diǎn)擊最多的 15 條：
zrevrange hotNews:20191001 0 15 withscores

BitMaps 位圖

Bitmaps 是在字符串類型上面定義的位操作，一個(gè)字節(jié)由 8 個(gè)二進(jìn)制位組成

存儲結(jié)構(gòu).png

• 操作命令

set k1 a
獲取 value 在 offset 處的值（a 對應(yīng)的 ASCII 碼是 97，轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)是 01100001）

getbit k1 0
修改二進(jìn)制數(shù)據(jù)（b 對應(yīng)的 ASCII 碼是 98，轉(zhuǎn)換為二進(jìn)制數(shù)據(jù)是 01100010）

setbit k1 6 1
setbit k1 7 0
get k1

統(tǒng)計(jì)二進(jìn)制位中 1 的個(gè)數(shù)
bitcount k1

獲取第一個(gè) 1 或者 0 的位置
bitpos k1 1
bitpos k1 0

BITOP 命令支持 AND 、 OR 、 NOT 、 XOR 這四種操作中的任意一種參數(shù)：

BITOP AND destkey srckey1 … srckeyN ，對一個(gè)或多個(gè) key 求邏輯與，并將結(jié)果保存到 destkey

BITOP OR destkey srckey1 … srckeyN，對一個(gè)或多個(gè) key 求邏輯或，并將結(jié)果保存到 destkey

BITOP XOR destkey srckey1 … srckeyN，對一個(gè)或多個(gè) key 求邏輯異或，并將結(jié)果保存到 destkey

BITOP NOT destkey srckey，對給定 key 求邏輯非，并將結(jié)果保存到 destkey

• 應(yīng)用場景
  在線用戶統(tǒng)計(jì)、用戶訪問統(tǒng)計(jì)

Hyperloglogs

Hyperloglogs：提供了一種不太準(zhǔn)確的基數(shù)統(tǒng)計(jì)方法，比如統(tǒng)計(jì)網(wǎng)站的 UV，存在一定的誤差

Streams

redis 5.0 推出的數(shù)據(jù)類型，支持多播的可持久化的消息隊(duì)列，用于實(shí)現(xiàn)發(fā)布訂閱功能，借鑒了 kafka 的設(shè)計(jì)。

總結(jié)

• 數(shù)據(jù)結(jié)構(gòu)總結(jié)

• 編碼轉(zhuǎn)換總結(jié)：

  
  
  編碼轉(zhuǎn)換總結(jié).png

應(yīng)用場景總結(jié)

緩存——提升熱點(diǎn)數(shù)據(jù)的訪問速度

共享數(shù)據(jù)——數(shù)據(jù)的存儲和共享的問題

全局 ID —— 分布式全局 ID 的生成方案（分庫分表）

分布式鎖——進(jìn)程間共享數(shù)據(jù)的原子操作保證

在線用戶統(tǒng)計(jì)和計(jì)數(shù)

隊(duì)列、?！邕M(jìn)程的隊(duì)列/棧

消息隊(duì)列——異步解耦的消息機(jī)制

服務(wù)注冊與發(fā)現(xiàn) —— RPC 通信機(jī)制的服務(wù)協(xié)調(diào)中心（Dubbo 支持 Redis）

購物車

新浪/Twitter 用戶消息時(shí)間線

抽獎(jiǎng)邏輯（禮物、轉(zhuǎn)發(fā)）

點(diǎn)贊、簽到、打卡

商品標(biāo)簽

用戶（商品）關(guān)注（推薦）模型

電商產(chǎn)品篩選

排行榜