偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

Redis SDS 是以時(shí)間換空間,還是空間換時(shí)間?

數(shù)據(jù)庫(kù) Redis
本文從 Redis 的底層 SDS 實(shí)現(xiàn)分析了 String 的實(shí)現(xiàn)原理,可以說(shuō) SDS 是一種很優(yōu)秀的設(shè)計(jì),它即遵循了 C語(yǔ)言的部分功能,又規(guī)避了 C語(yǔ)言字符串常見(jiàn)的一些問(wèn)題。

在 Redis中,String稱得上一個(gè)萬(wàn)精油數(shù)據(jù)結(jié)構(gòu), 它即可以存放普通的字符串,也可以存放對(duì)象,同樣可以存圖片,視頻等二進(jìn)制數(shù)據(jù),使用頻次特別高,真可謂是一個(gè)萬(wàn)精油。

為什么 Redis 的 String 可以存放這么多類型的數(shù)據(jù)?Redis 底層到底是如何實(shí)現(xiàn) String 的呢?今天我們就來(lái)聊一聊。

一、String的特性

String 的特性主要包含下面4點(diǎn):

  • String 是Redis中最基本的數(shù)據(jù)類型;
  • String 是二進(jìn)制安全,存入和獲取的數(shù)據(jù)相同;
  • Redis 字符串存儲(chǔ)字節(jié)序列,包括文本、序列化對(duì)象和二進(jìn)制數(shù)組;
  • String 存儲(chǔ)的 value值最大為 512MB;

二、String常用指令 

String 高頻指令如下表:

指令

舉例

說(shuō)明

set

set key value

設(shè)置值

get

get key

獲取值

getset

getset key

先獲取之前的值,然后設(shè)置一個(gè)新的值

del

del key

刪除key

incr

incr key

從0開始自增1

incrby

incrby key n

自增指定的步長(zhǎng)

decr

decr key 

自減1

decrby

decrby key n

自減指定的步長(zhǎng)

append

append key

追加內(nèi)容

如下圖,展示了 String常用指令:

三、實(shí)現(xiàn)原理 

上文介紹了 String數(shù)據(jù)對(duì)象的一些基礎(chǔ)知識(shí),接下來(lái)進(jìn)入核心內(nèi)容:String 的 Redis 底層實(shí)現(xiàn)。

1. SDS 結(jié)構(gòu)

Redis 底層是 C語(yǔ)言實(shí)現(xiàn)的,但是 Redis 的 String數(shù)據(jù)對(duì)象并沒(méi)有直接使用 C語(yǔ)言傳統(tǒng)的字符串,而是自創(chuàng)了一套 SDS,用于 Redis 默認(rèn)字符串表示。SDS(simple dynamic string),簡(jiǎn)單動(dòng)態(tài)字符串。

SDS 的結(jié)構(gòu)定義在 sds.h 文件中,每個(gè) sds.h/sdshdr 結(jié)構(gòu)表示一個(gè) SDS 值,在 Redis 3.2 版本之后,SDS 由一種數(shù)據(jù)結(jié)構(gòu)變成了 5 種數(shù)據(jù)結(jié)構(gòu),如下源碼截圖:

  • sdshdr5:存儲(chǔ)大小為 32 byte = 2^ 5 ,被棄用;
  • sdshdr8:存儲(chǔ)大小為 256 byte = 2^ 8;
  • sdshdr16:存儲(chǔ)大小為 64KB = 2 ^16
  • sdshdr32:存儲(chǔ)大小為 4GB = 2^ 32;
  • sdshdr64:存儲(chǔ)大小為 2^ 64;

5 種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)不同長(zhǎng)度的內(nèi)容,Redis 會(huì)根據(jù) SDS 存儲(chǔ)的內(nèi)容長(zhǎng)度來(lái)選擇不同的結(jié)構(gòu),源碼實(shí)現(xiàn)對(duì)應(yīng) sds.c/sdsReqType,截圖如下:

為了對(duì) SDS 有一個(gè)更好的體感,這里以 sdshdr8 為例,執(zhí)行指令:SET name Redis

執(zhí)行上述 set 指令后,值對(duì)象對(duì)應(yīng)的 SDS 結(jié)構(gòu)如下圖:

SDS 各個(gè)屬性說(shuō)明:

  • len:表示 buf 已用空間的長(zhǎng)度,占 4 個(gè)字節(jié),不包括 \0;
  • alloc:表示 buf 的實(shí)際分配長(zhǎng)度,占 4 個(gè)字節(jié),不包括 \0;
  • flags:標(biāo)記當(dāng)前字節(jié)數(shù)組是 sdshdr8/16/32/64 中的哪一種,占 1 個(gè)字節(jié);
  • buf:表示字節(jié)數(shù)組,保存實(shí)際數(shù)據(jù)。為了表示字節(jié)數(shù)組的結(jié)束,Redis 會(huì)自動(dòng)在數(shù)組最后加一個(gè)\0,需要額外占用 1 個(gè)字節(jié)的開銷;

從上面 SDS 的結(jié)構(gòu)可以看出,SDS 依然遵循了 C語(yǔ)言中字符串以 \0 結(jié)尾的規(guī)則, 但是,\0占用的1 個(gè)字節(jié)空間并沒(méi)有計(jì)算在 SDS 的 len 屬性里面。

分析完 SDS 的結(jié)構(gòu),我們會(huì)問(wèn),SDS 在 Redis 中是如何存放的呢?

因?yàn)?Redis 的數(shù)據(jù)類型有很多(String、List、Set、Hash等等),不同數(shù)據(jù)類型會(huì)包含相同的元數(shù)據(jù),所以值對(duì)象并不是直接存儲(chǔ),而是被包裝成 redisObject 對(duì)象(源碼位于 server.h中),其定義如下圖:

所以,SDS 在 Redis Server 端的存儲(chǔ)如下圖:

另外,為了節(jié)省內(nèi)存空間,Redis 還做了如下優(yōu)化:

  • 當(dāng)保存 Long 類型整數(shù),RedisObject 中的指針直接賦值為整數(shù)數(shù)據(jù),這樣就不用額外的指針指向整數(shù)。這種方式稱為 int 編碼方式。
  • 當(dāng)保存字符串?dāng)?shù)據(jù),且字符串小于等于 44 字節(jié)時(shí),RedisObject 中的元數(shù)據(jù)、指針和 SDS 是一塊連續(xù)的內(nèi)存區(qū)域,這樣可以避免內(nèi)存碎片。這種方式稱為 embstr 編碼方式。
  • 當(dāng)保存字符串?dāng)?shù)據(jù),且字符串大于 44 字節(jié)時(shí),Redis 不再把 SDS 和 RedisObject 放在一起,而是給 SDS 分配獨(dú)立的空間,并用指針指向 SDS 結(jié)構(gòu)。這種方式稱為 raw 編碼模式。

下圖為 int、embstr 和 raw 這三種編碼模式的對(duì)比:

如果想查看一個(gè)值對(duì)象是采用哪種編碼模式,可以使用 OBJECT ENCODING((大小寫不敏感)命令,下面給了幾個(gè)示例截圖:

到此,SDS 的實(shí)現(xiàn)原理分析完成,需要補(bǔ)充的是:Redis 官方為了保證 String 的性能,在 SDS 設(shè)計(jì)上采用了兩個(gè)非常優(yōu)秀的設(shè)計(jì):空間預(yù)分配 和 惰性空間釋放。

2. 空間預(yù)分配

在對(duì) SDS 進(jìn)行修改操作時(shí)(追加字符串,拷貝字符串等),通常會(huì)調(diào)用 sds.c/sdsMakeRoomFor 方法對(duì) SDS 的剩余容量進(jìn)行檢查,如有必要會(huì)對(duì) SDS 進(jìn)行擴(kuò)容,當(dāng)計(jì)算修改之后字符串(用target_string表示)的目標(biāo)長(zhǎng)度之后分以下幾種情況:

(1) 剩余的 freespace 足夠容納 target_string 和末尾\0字符,則不作任何操作

(2) 剩余的 freespace 不夠容納 target_string 和末尾的\0字符

  • 當(dāng)target_string_size < 1MB,則會(huì)直接分配2 * target_string_size 的空間用于存儲(chǔ)字符串
  • 當(dāng)target_string_size >= 1MB,則會(huì)再額外多分配1MB的空間用于存儲(chǔ)字符串(target_string_size + 1024*1024)

3. 惰性空間釋放

當(dāng) SDS 字符串縮短時(shí), 空余出來(lái)的空間并不會(huì)直接釋放,而是會(huì)被保留,等待下次再次使用,字符串縮短操作需要更新 sdshdr 頭中的 Len 字段以及alloced buffer中的\0字符的位置,如下源碼截圖,在更新字符串長(zhǎng)度的過(guò)程中并沒(méi)有涉及到內(nèi)存的重分配策略,只是簡(jiǎn)單的修改sdshdr 頭中的 Len 字段。

四、SDS 的缺點(diǎn) 

從上面 SDS 的結(jié)構(gòu)可以看出,SDS 除了存儲(chǔ) String 的內(nèi)容外,還需要額外的內(nèi)存空間記錄數(shù)據(jù)長(zhǎng)度、空間使用等信息,這個(gè)就導(dǎo)致了 SDS 的一個(gè)比較大的缺點(diǎn):占內(nèi)存。那么有什么更好的數(shù)據(jù)結(jié)構(gòu)呢?我們下篇文章會(huì)進(jìn)行分析。

不過(guò),計(jì)算機(jī)領(lǐng)域很多時(shí)候都在空間和時(shí)間上的一種權(quán)衡。而Redis String 這種浪費(fèi)內(nèi)存換取讀寫速度就是一個(gè)很好的體現(xiàn)。

五、SDS 與 C字符串比較

1. 獲取字符串長(zhǎng)度復(fù)雜度

C字符串不記錄長(zhǎng)度,獲取長(zhǎng)度必須遍歷整個(gè)字符串,復(fù)雜度為O(N),SDS 在 len 屬性中記錄了 SDS 本身的長(zhǎng)度, 獲取 SDS 長(zhǎng)度的復(fù)雜度為 O(1) ;

2. 緩沖區(qū)溢出

C字符串不記錄自身的長(zhǎng)度,每次增長(zhǎng)或縮短一個(gè)字符串,都要對(duì)底層的字符數(shù)組進(jìn)行一次內(nèi)存重分配操作。如果在 append 操作之前沒(méi)有通過(guò)內(nèi)存重分配來(lái)擴(kuò)展底層數(shù)據(jù)的空間大小,就會(huì)產(chǎn)生緩存區(qū)溢出;如果進(jìn)行 trim 操作之后沒(méi)有通過(guò)內(nèi)存重分配來(lái)釋放不再使用的空間,就會(huì)產(chǎn)生內(nèi)存泄漏;

SDS 通過(guò)未使用空間解除了字符串長(zhǎng)度和底層數(shù)據(jù)長(zhǎng)度的關(guān)聯(lián),3.0版本用 free屬性記錄未使用空間,3.2版本用 alloc屬性記錄總的分配字節(jié)數(shù)量。通過(guò)未使用空間,SDS實(shí)現(xiàn)了空間預(yù)分配和惰性空間釋放兩種優(yōu)化的空間分配策略,解決了字符串拼接和截取的空間問(wèn)題;

3. 二進(jìn)制安全

C 字符串以 \0結(jié)尾(即 以 \0判斷字符串結(jié)束),所以在 C字符串的內(nèi)容里面不能包含 \0,否則會(huì)被認(rèn)為是字符串結(jié)尾,因此,C字符串只能保存文本數(shù)據(jù),不能保存像圖片這樣的二進(jìn)制數(shù)據(jù);

而 SDS 的 API 會(huì)以處理二進(jìn)制的方式來(lái)處理存放在 bu f數(shù)組里的數(shù)據(jù),不會(huì)對(duì)里面的數(shù)據(jù)做任何的限制。SDS 使用 len 屬性來(lái)判斷字符串是否結(jié)束,而不是空字符。

兩者比較歸納如下表:

C字符串

SDS

獲取字符串長(zhǎng)度復(fù)雜度為O(N)

獲取字符串長(zhǎng)度復(fù)雜度為O(1)

API是不安全的,可能會(huì)造成緩沖區(qū)溢出

API是安全的,不會(huì)造成緩沖區(qū)溢出

修改字符串長(zhǎng)度必然需要內(nèi)存重分配

修改字符串長(zhǎng)度 N次最多需要執(zhí)行 N次內(nèi)存重分配

只能保存文本數(shù)據(jù)

可以保存文本或二進(jìn)制數(shù)據(jù)

可以使用所有<string.h>庫(kù)中的函數(shù)

可以使用一部分<string.h>庫(kù)中的函數(shù)

六、總結(jié)

本文從 Redis的底層 SDS 實(shí)現(xiàn)分析了 String 的實(shí)現(xiàn)原理,可以說(shuō) SDS 是一種很優(yōu)秀的設(shè)計(jì),它即遵循了 C語(yǔ)言的部分功能,又規(guī)避了 C語(yǔ)言字符串常見(jiàn)的一些問(wèn)題,這或許就是 Redis 優(yōu)秀的一個(gè)原因。

另外,SDS 為了保證讀寫速度,盡管做了很多節(jié)省內(nèi)存的操作(比如:sdshdr8/16/32/64,int/embstr/raw),但是,還在是一定程度上采用空間換時(shí)間。

通過(guò) SDS 的設(shè)計(jì),我們可以看出:在程序的世界里沒(méi)有“銀彈”,每種數(shù)據(jù)結(jié)構(gòu)似乎總有其擅長(zhǎng)的場(chǎng)景以及不足之處,這也正是各種數(shù)據(jù)結(jié)構(gòu)百花齊放的原因。

責(zé)任編輯:趙寧寧 來(lái)源: 猿java
相關(guān)推薦

2011-04-18 11:27:49

空間時(shí)間數(shù)據(jù)庫(kù)設(shè)計(jì)

2011-08-16 09:05:21

SQL Server數(shù)測(cè)試索引空間換時(shí)間

2011-04-12 13:44:39

緩存

2024-11-15 09:41:03

2024-11-07 22:57:30

2021-12-17 07:30:42

排序算法效率

2024-03-14 10:30:05

緩存場(chǎng)景DEMO

2025-07-03 02:15:00

2019-06-06 10:00:22

2023-11-07 10:22:26

自動(dòng)駕駛技術(shù)

2019-05-15 10:23:58

AI人工智能視頻換臉技術(shù)

2020-12-30 05:35:56

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

2024-06-17 11:59:39

2021-01-14 09:37:20

內(nèi)核空間用戶

2023-02-17 08:14:29

C語(yǔ)言C技巧內(nèi)存

2024-05-13 10:24:09

Ngram存儲(chǔ)Google

2021-06-28 06:15:14

算法Algorithm時(shí)間空間復(fù)雜度

2020-11-03 11:18:35

Go語(yǔ)言GoLang編程語(yǔ)言

2022-06-17 07:49:14

緩存LRU

2022-05-10 08:11:15

MySQL技巧結(jié)構(gòu)
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)