Redis 誕生歷程

從一個故事開始

08 年的時候有一個意大利西西里島的小伙子,筆名 antirez(http://invece.org/),創(chuàng)建了一個訪客信息網(wǎng)站 LLOOGG.COM.有的時候我們需要知道網(wǎng)站的訪問情況,比如訪客的 IP,操作系統(tǒng),瀏覽器,使用的搜索關鍵詞,所在地區(qū),訪問的網(wǎng)頁地址等等.在國內(nèi),有很多網(wǎng)站提供了這個功能,比如 CNZZ,百度統(tǒng)計,國外也有谷歌的 Google Analytics.我們不用自己寫代碼去實現(xiàn)這個功能,只需要在全局的 footer 里面嵌入一段 JS 代碼就行了,當頁面被訪問的時候,就會自動把訪客的信息發(fā)送到這些網(wǎng)站統(tǒng)計的服務器,然后我們登錄后臺就可以查看數(shù)據(jù)了

LLOOGG.COM 提供的就是這種功能,它可以查看最多 10000 條的最新瀏覽記錄.這樣的話,它需要為每一個網(wǎng)站創(chuàng)建一個列表(List),不同網(wǎng)站的訪問記錄進入到不同的列表.如果列表的長度超過了用戶指定的長度,它需要把最早的記錄刪除(先進先出)

image

當 LLOOGG.COM 的用戶越來越多的時候,它需要維護的列表數(shù)量也越來越多,這種記錄最新的請求和刪除最早的請求的操作也越來越多.LLOOGG.COM 最初使用的數(shù)據(jù)庫是 MySQL,可想而知,因為每一次記錄和刪除都要讀寫磁盤,因為數(shù)據(jù)量和并發(fā)量太大,在這種情況下無論怎么去優(yōu)化數(shù)據(jù)庫都不管用了

考慮到最終限制數(shù)據(jù)庫性能的瓶頸在于磁盤,所以 antirez 打算放棄磁盤,自己去實現(xiàn)一個具有列表結(jié)構(gòu)的數(shù)據(jù)庫的原型,把數(shù)據(jù)放在內(nèi)存而不是磁盤,這樣可以大大地提升列表的 push 和 pop 的效率.antirez 發(fā)現(xiàn)這種思路確實能解決這個問題,所以用 C 語言重寫了這個內(nèi)存數(shù)據(jù)庫,并且加上了持久化的功能,09 年,Redis 橫空出世了.從最開始只支持列表的數(shù)據(jù)庫,到現(xiàn)在支持多種數(shù)據(jù)類型,并且提供了一系列的高級特性,Redis 已經(jīng)成為一個在全世界被廣泛使用的開源項目

為什么叫 REDIS 呢?它的全稱是 Remote Dictionary Service,直接翻譯過來是遠程字典服務

從 Redis 的誕生歷史我們看到了,在某些場景中,關系型數(shù)據(jù)庫并不適合用來存儲我們的 Web 應用的數(shù)據(jù).那么,關系型數(shù)據(jù)庫和非關系型數(shù)據(jù)庫,或者說 SQL 和 NoSQL,到底有什么不一樣呢

Redis 定位與特性

SQL 與 NoSQL

在絕大部分時候,我們都會首先考慮用關系型數(shù)據(jù)庫來存儲我們的數(shù)據(jù),比如 SQLServer,Oracle,MySQL 等等
關系型數(shù)據(jù)庫的特點:

• 它以表格的形式,基于行存儲數(shù)據(jù),是一個二維的模式
• 它存儲的是結(jié)構(gòu)化的數(shù)據(jù),數(shù)據(jù)存儲有固定的模式(schema),數(shù)據(jù)需要適應表結(jié)構(gòu)
• 表與表之間存在關聯(lián)(Relationship)
• 大部分關系型數(shù)據(jù)庫都支持 SQL(結(jié)構(gòu)化查詢語言)的操作,支持復雜的關聯(lián)查詢
• 通過支持事務(ACID 酸)來提供嚴格或者實時的數(shù)據(jù)一致性

但是使用關系型數(shù)據(jù)庫也存在一些限制,比如:

• 要實現(xiàn)擴容的話,只能向上(垂直)擴展,比如磁盤限制了數(shù)據(jù)的存儲,就要擴大磁盤容量,通過堆硬件的方式,不支持動態(tài)的擴縮容.水平擴容需要復雜的技術來實現(xiàn),比如分庫分表
• 表結(jié)構(gòu)修改困難,因此存儲的數(shù)據(jù)格式也受到限制
• 在高并發(fā)和高數(shù)據(jù)量的情況下,我們的關系型數(shù)據(jù)庫通常會把數(shù)據(jù)持久化到磁盤,基于磁盤的讀寫壓力比較大

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

非關系型數(shù)據(jù)庫的特點:

• 存儲非結(jié)構(gòu)化的數(shù)據(jù),比如文本,圖片,音頻,視頻
• 表與表之間沒有關聯(lián),可擴展性強
• 保證數(shù)據(jù)的最終一致性.遵循 BASE(堿)理論.Basically Available(基本可用)；Soft-state(軟狀態(tài))；Eventually Consistent(最終一致性)
• 支持海量數(shù)據(jù)的存儲和高并發(fā)的高效讀寫
• 支持分布式,能夠?qū)?shù)據(jù)進行分片存儲,擴縮容簡單

對于不同的存儲類型,我們又有各種各樣的非關系型數(shù)據(jù)庫,比如有幾種常見的類型:

• KV 存儲,用 Key Value 的形式來存儲數(shù)據(jù).比較常見的有 Redis 和 MemcacheDB
• 文檔存儲,MongoDB
• 列存儲,HBase
• 圖存儲,這個圖(Graph)是數(shù)據(jù)結(jié)構(gòu),不是文件格式.Neo4j
• 對象存儲
• XML 存儲等

這個網(wǎng)頁列舉了各種各樣的 NoSQL 數(shù)據(jù)庫 http://nosql-database.org/
New SQL 結(jié)合了 SQL 和 NoSQL 的特性(例如 PingCAP 的 TiDB)

Redis 特性

官網(wǎng)介紹:https://redis.io/topics/introduction
中文網(wǎng)站:http://www.redis.cn

硬件層面有 CPU 的緩存；瀏覽器也有緩存；手機的應用也有緩存.我們把數(shù)據(jù)緩存起來的原因就是從原始位置取數(shù)據(jù)的代價太大了,放在一個臨時位置存儲起來,取回就可以快一些

Redis 的特性:

• 更豐富的數(shù)據(jù)類型
• 進程內(nèi)與跨進程；單機與分布式
• 功能豐富:持久化機制,過期策略
• 支持多種編程語言
• 高可用,集群

Redis 安裝啟動

服務端安裝

Linux 安裝

參考:
CentOS7 安裝 Redis 單實例 https://gper.club/articles/7e7e7f7ff7g5egc4g6b
Docker 安裝 Redis 集群 https://gper.club/articles/7e7e7f7ff7g5egc5g6c

主要是注意配置文件幾處關鍵內(nèi)容(后臺啟動,綁定 IP,密碼)的修改,配置別名

Windows 服務端安裝

Redis 作者沒有為 Windows 編寫 Redis 服務端,微軟自行編寫了一個 Redis 服務端,可用于基本的測試和學習
https://github.com/MicrosoftArchive/redis/tags

服務啟動

src 目錄下,直接啟動

./redis-server

后臺啟動(指定配置文件)

• redis.conf 修改兩行配置

daemonize yes bind 0.0.0.0

• 啟動 Redis

redis-server /usr/local/soft/redis-5.0.5/redis.conf

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

基本操作

默認有 16 個庫(0-15),可以在配置文件中修改,默認使用第一個 db0

databases 16

因為沒有完全隔離,不像數(shù)據(jù)庫的 database,不適合把不同的庫分配給不同的業(yè)務使用

• 切換數(shù)據(jù)庫

select 0

• 清空當前數(shù)據(jù)庫

flushdb

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

flushallRedis

是字典結(jié)構(gòu)的存儲方式,采用 key-value 存儲.key 和 value 的最大長度限制是 512M(來自官網(wǎng) https://redis.io/topics/data-types-intro/)

鍵的基本操作
命令參考:http://redisdoc.com/index.html
存值

set qingshan 2673

取值

get qingshan 7

查看所有鍵

keys *

獲取鍵總數(shù)

dbsize

查看鍵是否存在

exists qingshan

刪除鍵

del qingshan jack

重命名鍵

rename qingshan pengyuyan

查看類型

type qingshan Redis

一共有幾種數(shù)據(jù)類型?(注意是數(shù)據(jù)類型不是數(shù)據(jù)結(jié)構(gòu))
官網(wǎng):https://redis.io/topics/data-types-intro

String,Hash,Set,List,Zset,Hyperloglog,Geo,Streams

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

最基本也是最常用的數(shù)據(jù)類型就是 String. set 和 get 命令就是 String 的操作命令.為什么叫 Binary-safestrings 呢?

String 字符串

存儲類型

可以用來存儲字符串,整數(shù),浮點數(shù)

操作命令

設置多個值(批量操作,原子性)

mset qingshan 2673 jack 666

設置值,如果 key 存在,則不成功

setnx qingshan

基于此可實現(xiàn)分布式鎖.用 del key 釋放鎖
但如果釋放鎖的操作失敗了,導致其他節(jié)點永遠獲取不到鎖,怎么辦?
加過期時間.單獨用 expire 加過期,也失敗了,無法保證原子性,怎么辦?多參數(shù)

set key value [expiration EX seconds|PX milliseconds][NX|XX]

使用參數(shù)的方式

set lock1 1 EX 10 NX

(整數(shù))值遞增

incr qingshan incrby qingshan 100

(整數(shù))值遞減

decr qingshan decrby qingshan 100

浮點數(shù)增量

set f 2.6 incrbyfloat f 7.3

獲取多個值

mget qingshan jack

獲取值長度

strlen qingshan

字符串追加內(nèi)容

append qingshan good

獲取指定范圍的字符

getrange qingshan 0 8

存儲(實現(xiàn))原理

數(shù)據(jù)模型

set helloword 為例,因為 Redis 是 KV 的數(shù)據(jù)庫,它是通過 hashtable 實現(xiàn)的(我們把這個叫做外層的哈希).所以每個鍵值對都會有一個 dictEntry(源碼位置:dict.h),里面指向了 key 和 value 的指針.next 指向下一個 dictEntry

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

image

key 是字符串,但是 Redis 沒有直接使用 C 的字符數(shù)組,而是存儲在自定義的 SDS 中
value 既不是直接作為字符串存儲,也不是直接存儲在 SDS 中,而是存儲在 redisObject 中.實際上五種常用的數(shù)據(jù)類型的任何一種,都是通過 redisObject 來存儲的

redisObject

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

typedef struct redisObject {
    /* 對象的類型，包括：OBJ_STRING、OBJ_LIST、OBJ_HASH、OBJ_SET、OBJ_ZSET */
    unsigned type:4;
    /* 具體的數(shù)據(jù)結(jié)構(gòu) */
    unsigned encoding:4;
    /* 24 位，對象最后一次被命令程序訪問的時間，與內(nèi)存回收有關 */
    unsigned lru:LRU_BITS;
    /* 引用計數(shù)。當 refcount 為 0 的時候，表示該對象已經(jīng)不被任何對象引用，則可以進行垃圾回收了*/
    int refcount;
    /* 指向?qū)ο髮嶋H的數(shù)據(jù)結(jié)構(gòu) */
    void *ptr;
} robj;

可以使用 type 命令來查看對外的類型

127.0.0.1:6379> type qs
string 11

內(nèi)部編碼

image

127.0.0.1:6379> set number 1
OK
127.0.0.1:6379> set qs "is a good teacher in gupao, have crossed mountains and sea"
OK
127.0.0.1:6379> set jack bighead
OK
127.0.0.1:6379> object encoding number
"int"
127.0.0.1:6379> object encoding jack
"embstr"
127.0.0.1:6379> object encoding qs
"raw"

字符串類型的內(nèi)部編碼有三種:

• int,存儲 8 個字節(jié)的長整型(long,2^63-1)
• embstr,代表 embstr 格式的 SDS(Simple Dynamic String 簡單動態(tài)字符串),存儲小于 44 個字節(jié)的字符串
• raw,存儲大于 44 個字節(jié)的字符串(3.2 版本之前是 39 字節(jié)).為什么是 39?

/* object.c */
#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44

問題 1,什么是 SDS?
Redis 中字符串的實現(xiàn)
在 3.2 以后的版本中,SDS 又有多種結(jié)構(gòu)(sds.h):sdshdr5,sdshdr8,sdshdr16,sdshdr32,sdshdr64,用于存儲不同的長度的字符串,分別代表 2^5=32byte,28=256byte,2^{16=65536byte=64KB,2}32byte=4GB

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

問題 2,為什么 Redis 要用 SDS 實現(xiàn)字符串?
我們知道,C 語言本身沒有字符串類型(只能用字符數(shù)組 char[]實現(xiàn))

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

SDS 的特點:

• 不用擔心內(nèi)存溢出問題,如果需要會對 SDS 進行擴容
• 獲取字符串長度時間復雜度為 O(1),因為定義了 len 屬性
• 通過“空間預分配”(sds Make Room For)和“惰性空間釋放”,防止多次重分配內(nèi)存
• 判斷是否結(jié)束的標志是 len 屬性(它同樣以'\0'結(jié)尾是因為這樣就可以使用 C 語言中函數(shù)庫操作字符串的函數(shù)了),可以包含'\0'

存儲二進制:BytesTest.java

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

問題 4:int 和 embstr 什么時候轉(zhuǎn)化為 raw?
當 int 數(shù)據(jù)不再是整數(shù),或大小超過了 long 的范圍(2^63-1=9223372036854775807)時,自動轉(zhuǎn)化為 raw

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

問題 5:明明沒有超過閾值,為什么變成 raw 了?

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

對于 embstr,由于其實現(xiàn)是只讀的,因此在對 embstr 對象進行修改時,都會先轉(zhuǎn)化為 raw 再進行修改
因此,只要是修改 embstr 對象,修改后的對象一定是 raw 的,無論是否達到了 44 個字節(jié)

問題6:當長度小于閾值時,會還原嗎?
關于 Redis 內(nèi)部編碼的轉(zhuǎn)換,都符合以下規(guī)律:編碼轉(zhuǎn)換在 Redis 寫入數(shù)據(jù)時完成,且轉(zhuǎn)換過程不可逆,只能從小內(nèi)存編碼向大內(nèi)存編碼轉(zhuǎn)換(但是不包括重新 set)

問題7:為什么要對底層的數(shù)據(jù)結(jié)構(gòu)進行一層包裝呢?
通過封裝,可以根據(jù)對象的類型動態(tài)地選擇存儲結(jié)構(gòu)和可以使用的命令,實現(xiàn)節(jié)省空間和優(yōu)化查詢速度.應用場景緩存 String 類型例如:熱點數(shù)據(jù)緩存(例如報表,明星出軌),對象緩存,全頁緩存.可以提升熱點數(shù)據(jù)的訪問速度

應用場景

緩存

String 類型
例如:熱點數(shù)據(jù)緩存(例如報表,明星出軌),對象緩存,全頁緩存
可以提升熱點數(shù)據(jù)的訪問速度

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

STRING 類型,因為 Redis 是分布式的獨立服務,可以在多個應用之間共享,例如:分布式 Session

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

分布式鎖

STRING 類型 setnx 方法,只有不存在時才能添加成功,返回 true
http://redisdoc.com/string/set.html
建議用參數(shù)的形式

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 1000

(分庫分表的場景,一次性拿一段)

計數(shù)器

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

限流

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

位統(tǒng)計

String 類型的 BITCOUNT(1.6.6 的 bitmap 數(shù)據(jù)結(jié)構(gòu)介紹)
字符是以8位二進制存儲的

set k1 a
setbit k1 6 1
setbit k1 7 0
get k1

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

因為 bit 非常節(jié)省空間(1MB=8388608bit),可以用來做大數(shù)據(jù)量的統(tǒng)計
例如:在線用戶統(tǒng)計,留存用戶統(tǒng)計

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

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

BITOP AND destkey key [key ...] ，對一個或多個 key 求邏輯并，并將結(jié)果保存到 destkey
BITOP OR destkey key [key ...] ，對一個或多個 key 求邏輯或，并將結(jié)果保存到 destkey
BITOP XOR destkey key [key ...] ，對一個或多個 key 求邏輯異或，并將結(jié)果保存到 destkey
BITOP NOT destkey key ，對給定 key 求邏輯非，并將結(jié)果保存到 destkey

計算出7天都在線的用戶

BITOP "AND" "7_days_both_online_users" "day_1_online_users" "day_2_online_users" ... "day_7_online_users"

如果一個對象的 value 有多個值的時候,怎么存儲?
例如用一個 key 存儲一張表的數(shù)據(jù)

image

序列化?例如 JSON/Protobuf/XML,會增加序列化和反序列化的開銷,并且不能單獨獲取,修改一個值
可以通過 key 分層的方式來實現(xiàn),例如:

mset student:1:sno GP16666 student:1:sname 沐風 student:1:company 騰訊

獲取值的時候一次獲取多個值:

mget student:1:sno student:1:sname student:1:company

缺點:key 太長,占用的空間太多.有沒有更好的方式?

Hash 哈希

image

存儲類型

包含鍵值對的無序散列表.value 只能是字符串,不能嵌套其他類型
同樣是存儲字符串,Hash 與 String 的主要區(qū)別?

• 把所有相關的值聚集到一個 key 中,節(jié)省內(nèi)存空間
• 只使用一個 key,減少 key 沖突
• 當需要批量獲取值的時候,只需要使用一個命令,減少內(nèi)存/IO/CPU 的消耗

Hash 不適合的場景:

• Field 不能單獨設置過期時間
• 沒有 bit 操作
• 需要考慮數(shù)據(jù)量分布的問題(value 值非常大的時候,無法分布到多個節(jié)點)

操作命令

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

hget h1 a
hmget h1 a b c d
hkeys h1
hvals h1
hgetall h1

key 操作

hget exists h1
hdel h1
hlen h1

存儲(實現(xiàn))原理

Redis 的 Hash 本身也是一個 KV 的結(jié)構(gòu),類似于 Java 中的 HashMap
外層的哈希(Redis KV 的實現(xiàn))只用到了 hashtable.當存儲 hash 數(shù)據(jù)類型時,我們把它叫做內(nèi)層的哈希.內(nèi)層的哈希底層可以使用兩種數(shù)據(jù)結(jié)構(gòu)實現(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 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(integer)1
127.0.0.1:6379> object encoding h2
"ziplist"
127.0.0.1:6379> object encoding h3
"hashtable"

ziplist 壓縮列表

ziplist 壓縮列表是什么?

/* ziplist.c 源碼頭部注釋 */
The ziplist is a specially encoded dually linked list that is designed to be very memory efficient. It stores both strings and integer values, where integers are encoded as actual integers instead of a series of characters. It allows push and pop operations on either side of the list in O(1)time. However, because every operation requires a reallocation of the memory used by the ziplist, the actual complexity is related to the amount of memory used by the ziplist

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

ziplist 的內(nèi)部結(jié)構(gòu)?
ziplist.c 源碼第 16 行的注釋:

• <zlbytes><zltail><zllen><entry><entry>...<entry><zlend>

image

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

編碼 encoding(ziplist.c 源碼第 204 行)

define ZIP_STR_06B (0 << 6)//長度小于等于 63 字節(jié)

define ZIP_STR_14B (1 << 6)//長度小于等于 16383 字節(jié)

define ZIP_STR_32B (2 << 6)//長度小于等于 4294967295 字節(jié)

image

問題:什么時候使用 ziplist 存儲?
當 hash 對象同時滿足以下兩個條件的時候,使用 ziplist 編碼:

• 所有的鍵值對的健和值的字符串長度都小于等于 64byte(一個英文字母一個字節(jié))；
• 哈希對象保存的鍵值對數(shù)量小于512個

/* src/redis.conf 配置 */

// ziplist 中最大能存放的值長度
hash-max-ziplist-value 64
// ziplist 中最多能存放的 entry 節(jié)點數(shù)量
hash-max-ziplist-entries 512

/* 源碼位置：t_hash.c ，當達字段個數(shù)超過閾值，使用 HT 作為編碼 */
if (hashTypeLength(o)> server.hash_max_ziplist_entries){
    hashTypeConvert(o, OBJ_ENCODING_HT);
}

/*源碼位置： t_hash.c，當字段值長度過大，轉(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;
    }
}

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

hashtable(dict)

在 Redis 中,hashtable 被稱為字典(dictionary),它是一個數(shù)組+鏈表的結(jié)構(gòu).源碼位置:dict.h
前面我們知道了,Redis 的 KV 結(jié)構(gòu)是通過一個 dictEntry 來實現(xiàn)的
Redis 又對 dictEntry 進行了多層的封裝

typedef struct dictEntry {
    /* key 關鍵字定義 */
    void *key;
    union {
        /* value 定義 */
        void *val; uint64_t u64;
        int64_t s64; double d;
    } v;
    
    /* 指向下一個鍵值對節(jié)點 */
    struct dictEntry *next;
} 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 {
    /* 哈希表數(shù)組 */
    dictEntry **table;
    /* 哈希表大小 */
    unsigned long size;
    /* 掩碼大小，用于計算索引值。總是等于 size-1 */
    unsigned long sizemask;
    /* 已有節(jié)點數(shù) */
    unsigned long used;
} dictht;

ht 放到了 dict 里面:

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

從最底層到最高層 dictEntry——dictht——dict——OBJ_ENCODING_HT
總結(jié):哈希的存儲結(jié)構(gòu)

image

注意:dictht 后面是 NULL 說明第二個 ht 還沒用到.dictEntry*后面是 NULL 說明沒有 hash 到這個地址.dictEntry 后面是 NULL 說明沒有發(fā)生哈希沖突

問題:為什么要定義兩個哈希表呢?
ht[2]redis 的 hash 默認使用的是 ht[0],ht[1]不會初始化和分配空間
哈希表 dictht 是用鏈地址法來解決碰撞問題的.在這種情況下,哈希表的性能取決于它的大小(size 屬性)和它所保存的節(jié)點的數(shù)量(used 屬性)之間的比率:

• 比率在 1:1 時(一個哈希表 ht 只存儲一個節(jié)點 entry),哈希表的性能最好；
• 如果節(jié)點數(shù)量比哈希表的大小要大很多的話(這個比例用 ratio 表示,5 表示平均一個 ht 存儲 5 個 entry),那么哈希表就會退化成多個鏈表,哈希表本身的性能優(yōu)勢就不再存在

在這種情況下需要擴容.Redis 里面的這種操作叫做 rehash

rehash 的步驟:

• 為字符 ht[1]哈希表分配空間,這個哈希表的空間大小取決于要執(zhí)行的操作,以及 ht[0]當前包含的鍵值對的數(shù)量
  擴展:ht[1]的大小為第一個大于等于 ht[0].used*2
• 將所有的 ht[0]上的節(jié)點 rehash 到 ht[1]上,重新計算 hash 值和索引,然后放入指定的位置
• 當 ht[0]全部遷移到了 ht[1]之后,釋放 ht[0]的空間,將 ht[1]設置為 ht[0]表,并創(chuàng)建新的 ht[1],為下次 rehash 做準備

問題:什么時候觸發(fā)擴容?
負載因子(源碼位置:dict.c):

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

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

擴容判斷_dictExpandIfNeeded(源碼 dict.c)

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;

擴容方法 dictExpand(源碼 dict.c)

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;
}

縮容:server.c

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));
}

應用場景

String

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

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

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

購物車

image

購物車 key:用戶 id
field:商品 id
value:商品數(shù)量
+1:hincr
-1:hdecr
刪除:hdel
全選:hgetall
商品數(shù):hlen

List 列表

存儲類型

存儲有序的字符串(從左到右),元素可以重復.可以充當隊列和棧的角色.操作命令

image

操作命令

元素增減:

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

image

存儲(實現(xiàn))原理

在早期的版本中,數(shù)據(jù)量較小時用 ziplist 存儲,達到臨界值時轉(zhuǎn)換為 linkedlist 進行存儲,分別對應 OBJ_ENCODING_ZIPLIST 和 OBJ_ENCODING_LINKEDLIST
3.2 版本之后,統(tǒng)一用 quicklist 來存儲.quicklist 存儲了一個雙向鏈表,每個節(jié)點都是一個 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 中一共存了多少個元素 */
    unsigned long len; /* 雙向鏈表的長度，node 的數(shù)量 */
    int fill : 16; /* fill factor for individual nodes */
    unsigned int compress : 16; /* 壓縮深度，0：不壓縮； */
} quicklist;

redis.conf 相關參數(shù):

quicklistNode 中的*zl 指向一個 ziplist,一個 ziplist 可以存放多個元素

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

image

ziplist 的結(jié)構(gòu)前面已經(jīng)說過了,不再重復

應用場景

用戶消息時間線 timeline

因為 List 是有序的,可以用來做用戶時間線

image

消息隊列

List 提供了兩個阻塞的彈出操作:BLPOP/BRPOP,可以設置超時時間

• BLPOP:BLPOP key1 timeout 移出并獲取列表的第一個元素,如果列表沒有元素會阻塞列表直到等待超時或發(fā)現(xiàn)可彈出元素為止
• BRPOP:BRPOP key1 timeout 移出并獲取列表的最后一個元素,如果列表沒有元素會阻塞列表直到等待超時或發(fā)現(xiàn)可彈出元素為止

隊列:先進先出:rpush blpop,左頭右尾,右邊進入隊列,左邊出隊列
棧:先進后出:rpush brpop

Set 集合

存儲類型

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

image

操作命令

添加一個或者多個元素

sadd myset a b c d e f g

獲取所有元素

smembers myset

統(tǒng)計元素個數(shù)

scard myset

隨機獲取一個元素

srandmember key

隨機彈出一個元素

spop myset

移除一個或者多個元素

srem myset d e f

查看元素是否存在

sismember myset a

存儲(實現(xiàn))原理

Redis 用 intset 或 hashtable 存儲 set.如果元素都是整數(shù)類型,就用 inset 存儲.如果不是整數(shù)類型,就用 hashtable(數(shù)組+鏈表的存來儲結(jié)構(gòu))
問題:KV 怎么存儲 set 的元素?key 就是元素的值,value 為 null
如果元素個數(shù)超過 512 個,也會用 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"

應用場景

抽獎

隨機獲取元素 spop myset

點贊,簽到,打卡

image

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

比關系型數(shù)據(jù)庫簡單許多

商品標簽用

tags:i5001 來維護商品所有的標簽

image

sadd tags:i5001 畫面清晰細膩
sadd tags:i5001 真彩清晰顯示屏
sadd tags:i5001 流暢至極

商品篩選

獲取差集

sdiff set1 set2

獲取交集(intersection)

sinter set1 set2

獲取并集

sunion set1 set2

image

iPhone11 上市了

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 有序集合

存儲類型

image

sorted set,有序的 set,每個元素有個 score
score 相同時,按照 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ù) scorerank 刪除

zrem myzset php cpp

統(tǒng)計元素個數(shù)

zcard myzset

分值遞增

zincrby myzset 5 python

根據(jù)分值統(tǒng)計個數(shù)

zcount myzset 20 60

獲取元素 rank

zrank myzset java

獲取元素 score

zsocre myzset java

也有倒序的 rev 操作(reverse)

存儲(實現(xiàn))原理

同時滿足以下條件時使用 ziplist 編碼:

• 元素數(shù)量小于128個
• 所有 member 的長度都小于 64 字節(jié)

在 ziplist 的內(nèi)部,按照 score 排序遞增來存儲.插入的時候要移動之后的數(shù)據(jù)
對應 redis.conf 參數(shù):

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

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

問題:什么是 skiplist?
我們先來看一下有序鏈表:

image

在這樣一個鏈表中,如果我們要查找某個數(shù)據(jù),那么需要從頭開始逐個進行比較,直到找到包含數(shù)據(jù)的那個節(jié)點,或者找到第一個比給定數(shù)據(jù)大的節(jié)點為止(沒找到).也就是說,時間復雜度為 O(n).同樣,當我們要插入新數(shù)據(jù)的時候,也要經(jīng)歷同樣的查找過程,從而確定插入位置
而二分查找法只適用于有序數(shù)組,不適用于鏈表
假如我們每相鄰兩個節(jié)點增加一個指針(或者理解為有三個元素進入了第二層),讓指針指向下下個節(jié)點

image

這樣所有新增加的指針連成了一個新的鏈表,但它包含的節(jié)點個數(shù)只有原來的一半(上圖中是 7,19,26).在插入一個數(shù)據(jù)的時候,決定要放到那一層,取決于一個算法(在 redis 中 t_zset.c 有一個 zslRandomLevel 這個方法)
現(xiàn)在當我們想查找數(shù)據(jù)的時候,可以先沿著這個新鏈表進行查找.當碰到比待查數(shù)據(jù)大的節(jié)點時,再回到原來的鏈表中的下一層進行查找.比如,我們想查找23,查找的路徑是沿著下圖中標紅的指針所指向的方向進行的:

image

• 23首先和7比較,再和19比較,比它們都大,繼續(xù)向后比較
• 但23和26比較的時候,比26要小,因此回到下面的鏈表(原鏈表),與22比較
• 23比22要大,沿下面的指針繼續(xù)向后和26比較.23比26小,說明待查數(shù)據(jù)23在原鏈表中不存在

在這個查找過程中,由于新增加的指針,我們不再需要與鏈表中每個節(jié)點逐個進行比較了.需要比較的節(jié)點數(shù)大概只有原來的一半.這就是跳躍表
為什么不用 AVL 樹或者紅黑樹?因為 skiplist 更加簡潔

源碼:server.h

typedef struct zskiplistNode {
    sds ele; /* zset 的元素 */
    double score; /* 分值 */
    struct zskiplistNode *backward; /* 后退指針 */

    struct zskiplistLevel {
        struct zskiplistNode *forward; /* 前進指針，對應 level 的下一個節(jié)點 */
        unsigned long span; /* 從當前節(jié)點到下一個節(jié)點的跨度（跨越的節(jié)點數(shù)） */
    } level[]; /* 層 */
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; /* 指向跳躍表的頭結(jié)點和尾節(jié)點 */
    unsigned long length; /* 跳躍表的節(jié)點數(shù) */
    int level; /* 最大的層數(shù) */
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

隨機獲取層數(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;
}

應用場景

排行榜

id 為 6001 的新聞點擊數(shù)加 1:

zincrby hotNews:20190926 1 n6001

獲取今天點擊最多的15條:

zrevrange hotNews:20190926 0 15 withscores

其他數(shù)據(jù)結(jié)構(gòu)簡介

https://redis.io/topics/data-types-intro

BitMaps

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

image

set k1 a

獲取 value 在 offset 處的值(a 對應的 ASCII 碼是 97,轉(zhuǎn)換為二進制數(shù)據(jù)是 01100001)

getbit k1 0

修改二進制數(shù)據(jù)(b 對應的 ASCII 碼是 98,轉(zhuǎn)換為二進制數(shù)據(jù)是 01100010)

setbit k1 6 1
setbit k1 7 0
get k1

統(tǒng)計二進制位中1的個數(shù)

bitcount k1

獲取第一個1或者0的位置

bitpos k1 1
bitpos k1 0

BITOP 命令支持 AND,OR,NOT,XOR 這四種操作中的任意一種參數(shù):
BITOP AND destkey srckey1 … srckeyN,對一個或多個 key 求邏輯與,并將結(jié)果保存到 destkey
BITOP OR destkey srckey1 … srckeyN,對一個或多個 key 求邏輯或,并將結(jié)果保存到 destkey
BITOP XOR destkey srckey1 … srckeyN,對一個或多個 key 求邏輯異或,并將結(jié)果保存到 destkey
BITOP NOT destkey srckey,對給定 key 求邏輯非,并將結(jié)果保存到 destkey

應用場景

用戶訪問統(tǒng)計
在線用戶統(tǒng)計

Hyperloglogs

Hyperloglogs:提供了一種不太準確的基數(shù)統(tǒng)計方法,比如統(tǒng)計網(wǎng)站的 UV,存在一定的誤差.HyperLogLogTest.java

Streams

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

總結(jié)

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

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

應用場景總結(jié)

緩存——提升熱點數(shù)據(jù)的訪問速度
共享數(shù)據(jù)——數(shù)據(jù)的存儲和共享的問題
全局 ID——分布式全局 ID 的生成方案(分庫分表)
分布式鎖——進程間共享數(shù)據(jù)的原子操作保證
在線用戶統(tǒng)計和計數(shù)
隊列,?！邕M程的隊列/棧
消息隊列——異步解耦的消息機制
服務注冊與發(fā)現(xiàn)——RPC 通信機制的服務協(xié)調(diào)中心(Dubbo 支持 Redis)
購物車
新浪/Twitter
用戶消息時間線
抽獎邏輯(禮物,轉(zhuǎn)發(fā))
點贊,簽到,打卡
商品標簽
用戶(商品)關注(推薦)模型
電商產(chǎn)品篩選
排行榜