鑽石舞台

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

中國畲鄉·景畲宜人

2022首屆畲鄉景寧文創設計大賽（銀飾、彩帶）

民族的就是世界的。畲族是華東最古老的少數民族，他們自稱山哈，有着鮮明的民族特色和獨特的文化藝術。

(繼續閱讀...)

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

鑽石舞台 發表在 痞客邦 留言(0) 人氣()

作者 | 就是碼哥呀

來源 |碼哥字節

當你面試或者工作中你遇到如下問題，那就使出今天講到的知識，一招定乾坤！

❝如何用更少的內存保存更多的數據？

我們應該從 Redis 是如何保存數據的原理展開，分析鍵值對的存儲結構和原理。

從而繼續延展出每種數據類型底層的數據結構，針對不同場景使用更恰當的數據結構和編碼實現更少的內存占用。

為了保存數據， Redis 需要先申請內存，數據過期或者內存淘汰需要回收內存，從而拓展出內存碎片優化。

最後，說下 key、value 使用規範和技巧、 Bitmap 等高階數據類型，運用這些技巧巧妙解決有限內存去存儲更多數據難題……

這一套組合拳下來直接封神。

具體詳情，我們在下文中一一呈現

主要優化神技如下：

鍵值對優化；

小數據集合的編碼優化；

使用對象共享池；

使用 Bit 比特位或 byte 級別操作

使用 hash 類型優化；

內存碎片優化；

使用 32 位的 Redis。

在優化之前，我們先掌握 Redis 是如何存儲數據的。

Redis 如何存儲鍵值對

Redis 以 redisDb為中心存儲，redis 7.0 源碼在 https://github.com/redis/redis/blob/7.0/src/server.h：

redisDb

dict：最重要的屬性之一，就是靠這個定義了保存了對象數據鍵值對，dcit 的底層結構是一個哈希表。

expires：保存着所有 key 的過期信息.

blocking_keys 和 ready_keys 主要為了實現 BLPOP 等阻塞命令

watched_keys用於實現watch命令，記錄正在被watch的一些key，與事務相關。

id 為當前數據庫的id，redis 支持單個服務多數據庫，默認有16個；

clusterSlotToKeyMapping：cluster 模式下，存儲key 與哈希槽映射關係的數組。

Redis 使用「dict」結構來保存所有的鍵值對（key-value）數據，這是一個全局哈希表，所以對 key 的查詢能以 O(1) 時間得到。

所謂哈希表，我們可以類比 Java 中的 HashMap，其實就是一個數組，數組的每個元素叫做哈希桶。

dict 結構如下，源碼在 https://github.com/redis/redis/blob/7.0/src/dict.h：

structdict{//特定類型的處理函數dictType*type;//兩個全局哈希表指針數組，與漸進式rehash有關dictEntry**ht_table[2];//記錄 dict 中現有的數據個數。unsignedlonght_used[2];//記錄漸進式rehash進度的標誌，-1表示當前沒有執行rehashlongrehashidx;//小於0表示rehash暫停int16_tpauserehash;signedcharht_size_exp[2];};

dictType：存儲了hash函數，key和value的複製等函數；

ht_table：長度為 2 的 數組，正常情況使用 ht_table[0] 存儲數據，當執行 rehash 的時候，使用 ht_table[1] 配合完成 。

key 的哈希值最終會映射到 ht_table 的一個位置，如果發生哈希衝突，則拉出一個哈希鍊表。

大家重點關注 dictEntry 類型的 ht_table，ht_table 數組每個位置我們也叫做哈希桶，就是這玩意保存了所有鍵值對。

❝Redis 支持那麼多的數據類型，哈希桶咋保存？

哈希桶的每個元素的結構由 dictEntry 定義：

typedefstructdictEntry{//指向key的指針void*key;union{//指向實際value的指針void*val;uint64_tu64;int64_ts64;doubled;}v;//哈希衝突拉出的鍊表structdictEntry*next;}dictEntry;

key 指向鍵值對的鍵的指針，key 都是 string 類型。

value 是個 union（聯合體）當它的值是 uint64_t、int64_t 或 double 類型時，就不再需要額外的存儲，這有利於減少內存碎片。（為了節省內存操碎了心）當然，val 也可以是 void 指針，指向值的指針，以便能存儲任何類型的數據。

next 指向另一個 dictEntry 結構， 多個 dictEntry 可以通過 next 指針串連成鍊表， 從這裡可以看出， ht_table 使用鏈地址法來處理鍵碰撞：當多個不同的鍵擁有相同的哈希值時，哈希表用一個鍊表將這些鍵連接起來。

哈希桶並沒有保存值本身，而是指向具體值的指針，從而實現了哈希桶能存不同數據類型的需求。

而哈希桶中，鍵值對的值都是由一個叫做 redisObject 的對象定義，源碼地址：https://github.com/redis/redis/blob/7.0/src/server.h。

typedefstructredisObject{unsignedtype:4;unsignedencoding:4;unsignedlru:LRU_BITS;intrefcount;void*ptr;}robj;

type：記錄了對象的類型，string、set、hash 、Lis、Sorted Set 等，根據該類型才可以確定是哪種數據類型，使用什麼樣的 API 操作。

encoding：編碼方式，表示 ptr 指向的數據類型具體數據結構，即這個對象使用了什麼數據結構作為底層實現保存數據。同一個對象使用不同編碼實現內存占用存在明顯差異，內部編碼對內存優化非常重要。

lru:LRU_BITS：LRU 策略下對象最後一次被訪問的時間，如果是 LFU 策略，那麼低 8 位表示訪問頻率，高 16 位表示訪問時間。

refcount ：表示引用計數，由於 C 語言並不具備內存回收功能，所以 Redis 在自己的對象系統中添加了這個屬性，當一個對象的引用計數為 0 時，則表示該對象已經不被任何對象引用，則可以進行垃圾回收了。

ptr 指針：指向對象的底層實現數據結構，指向值的指針。

如下圖是由 redisDb、dict、dictEntry、redisObejct 關係圖：

redis存儲結構

再嘮叨幾句，void *key 和 void *value 指針指向的是 redisObject，Redis 中每個對象都是用 redisObject 表示。

知道了 Redis 存儲原理以及不同數據類型的存儲數據結構後，我們繼續看如何做性能優化。

1. 鍵值對優化

當我們執行 set key value 的命令，*key指針指向 SDS 字符串保存 key，而 value 的值保存在 *ptr 指針指向的數據結構，消耗的內存：key + value。

第一個優化神技：降低 Redis 內存使用的最粗暴的方式就是縮減鍵（key）與值（value）的長度。

對於 key 的命名使用「業務模塊名:表名:數據唯一id」這樣的方式方便定位問題。

比如：users:firends:996 表示用戶系統中，id = 996 的朋友信息。我們可以簡寫為：u:fs:996

對於 key 的優化：使用單詞簡寫方式優化內存占用。

對於 value 的優化那就更多了：

過濾不必要的數據：不要大而全的一股腦將所有信息保存，想辦法去掉一些不必要的屬性，比如緩存登錄用戶的信息，通常只需要存儲暱稱、性別、賬號等。

精簡數據：比如用戶的會員類型：0 表示「普通」、1 表示 「VIP」、2表示「VVIP」。而不是存儲 VIP 這個字符串。

數據壓縮：對數據的內容進行壓縮，比如使用 GZIP、Snappy。

使用性能好，內存占用小的序列化方式。比如 Java 內置的序列化不管是速度還是壓縮比都不行，我們可以選擇 protostuff，kryo等方式。如下圖 Java 常見的序列化工具空間壓縮比：

序列化工具壓縮比

❝我們通常使用 json 作為字符串存儲在 Redis，用 json 存儲與二進制數據存儲有什麼優缺點呢？

json 格式的優點：方便調試和跨語言；缺點是：同樣的數據相比字節數組占用的空間更大。

一定要 json 格式的話，那就先通過壓縮算法壓縮 json，再把壓縮後的數據存入 Redis。比如 GZIP 壓縮後的 json 可降低約 60% 的空間。

2. 小數據集合編碼優化

key 對象都是 string 類型，value 對象主要有五種基本數據類型：String、List、Set、Zset、Hash。

數據類型與底層數據結構的關係如下所示：

編碼與數據結構

特別說明下在最新版（非穩定版本，時間 2022-7-3），ziplist 壓縮列表由 quicklist 代替（3.2 版本引入），而雙向鍊表由 listpack 代替。

另外，同一數據類型會根據鍵的數量和值的大小也有不同的底層編碼類型實現。

在 Redis 2.2 版本之後，存儲集合數據（Hash、List、Set、SortedSet）在滿足某些情況下會採用內存壓縮技術來實現使用更少的內存存儲更多的數據。

當這些集合中的數據元素數量小於某個值且元素的值占用的字節大小小於某個值的時候，存儲的數據會用非常節省內存的方式進行編碼，理論上至少節省 10 倍以上內存（平均節省 5 倍以上）。

比如 Hash 類型裡面的數據不是很多，雖然哈希表的時間複雜度是 O(1)，ziplist 的時間複雜度是 O(n)，但是使用 ziplist 保存數據的話會節省了內存，並且在少量數據情況下效率並不會降低很多。

所以我們需要儘可能地控制集合元素數量和每個元素的內存大小，這樣能充分利用緊湊型編碼減少內存占用。

並且，這些編碼對用戶和 api 是無感知的，當集合數據超過配置文件的配置的最大值， Redis 會自動轉成正常編碼。

❝數據類型對應的編碼規則如下所示

String 字符串

int：整數且數字長度小於 20，直接保存在 *ptr 中。

embstr：開闢一塊連續分配的內存（字符串長度小於等於 44 字節）。

raw：動態字符串（大於 44 字節的字符串，同時字符串小於 512 MB）。

List 列表

ziplist：元素個數小於hash-max-ziplist-entries配置，同時所有的元素的值大小都小於 hash-max-ziplist-value配置。

ziplist

linkedlist：3.0 版本之前當列表類型無法滿足 ziplist 的條件時，Redis會使用 linkedlist 作為列表的內部實現。

quicklist：Redis 3.2 引入，並作為 List 數據類型的底層實現，不再使用雙端鍊表 linkedlist 和 ziplist 實現。

Set 集合

intset 整數集合：元素都是整數，且元素個數小於 set-max-intset-entries配置

hashtable 哈希表：集合類型無法滿足intset的條件時就會使用hashtable 編碼。

Hash 哈希表

ziplist：元素個數小於 hash-max-ziplist-entries配置，同時任意一個 value 的占用字節大小都小於hash-max-ziplist-value 。

hashtable：hash 類型無法滿足 intset 的條件時就會使用hashtable。

Sorted Set 有序集合

ziplist：元素個數小於 zset-max-ziplist-entries 同時每個元素的value小於``zset-max-ziplist-value`配置。

skiplist：當ziplist條件不滿足時，有序集合會使用skiplist作為內部實現。

以下是 Redis redis.conf 配置文件默認編碼閾值配置：

hash-max-ziplist-entries512hash-max-ziplist-value64zset-max-ziplist-entries128zset-max-ziplist-value64set-max-intset-entries512

下圖是 reidsObject 對象的 type 和 encoding 對應關係圖：

type 與編碼

❝為啥對一種數據類型實現多種不同編碼方式？

主要原因是想通過不同編碼實現效率和空間的平衡。

比如當我們的存儲只有100個元素的列表，當使用雙向鍊表數據結構時，需要維護大量的內部字段。

比如每個元素需要：前置指針，後置指針，數據指針等，造成空間浪費。

如果採用連續內存結構的壓縮列表(ziplist)，將會節省大量內存，而由於數據長度較小，存取操作時間複雜度即使為O(n) 性能也相差不大，因為 n 值小 與 O(1) 並明顯差別。

數據編碼優化技巧

ziplist 存儲 list 時每個元素會作為一個 entry，存儲 hash 時 key 和 value 會作為相鄰的兩個 entry。

存儲 zset 時 member 和 score 會作為相鄰的兩個entry，當不滿足上述條件時，ziplist 會升級為 linkedlist, hashtable 或 skiplist 編碼。

由於目前大部分Redis運行的版本都是在3.2以上，所以 List 類型的編碼都是quicklist。

quicklist 是 ziplist 和 linkedlist 的混合體，它將 linkedlist 按段切分，每一段使用 ziplist 來緊湊存儲，多個 ziplist 之間使用雙向指針串接起來。

考慮了綜合平衡空間碎片和讀寫性能兩個維度所以使用了新編碼 quicklist。

ziplist 的不足

每次修改都可能觸發 realloc 和 memcopy, 可能導致連鎖更新(數據可能需要挪動)。

因此修改操作的效率較低，在 ziplist 的元素很多時這個問題更加突出。

優化手段：

key 儘量控制在 44 字節以內，走 embstr 編碼。

集合類型的 value 對象的元素個數不要太多太大，充分利用 ziplist 編碼實現內存壓縮。

3. 對象共享池

整數我們經常在工作中使用，Redis 在啟動的時候默認生成一個 0 ~9999 的整數對象共享池用於對象復用，減少內存占用。

比如執行set 碼哥 18; set 吳彥祖 18; key 等於 「碼哥」 和「吳彥祖」的 value 都指向同一個對象。

如果 value 可以使用整數表示的話儘可能使用整數，這樣即使大量鍵值對的 value 大量保存了 0~9999 範圍內的整數，在實例中，其實只有一份數據。

有兩個大坑需要注意，它會導致對象共享池失效。

Redis 中設置了 maxmemory 限制最大內存占用大小且啟用了 LRU 策略（allkeys-lru 或 volatile-lru 策略）。

❝為啥呀？

因為 LRU 需要記錄每個鍵值對的訪問時間，都共享一個整數 對象，LRU 策略就無法進行統計了。

集合類型的編碼採用 ziplist 編碼，並且集合內容是整數，也不能共享一個整數對象。

❝這又是為啥呢？

使用了 ziplist 緊湊型內存結構存儲數據，判斷整數對象是否共享的效率很低。

4.使用 Bit 比特位或 byte 級別操作

比如在一些「二值狀態統計」的場景下使用 Bitmap 實現，對於網頁 UV 使用 HyperLogLog 來實現，大大減少內存占用。

❝什麼是二值狀態統計呀？

也就是集合中的元素的值只有 0 和 1 兩種，在簽到打卡和用戶是否登陸的場景中，只需記錄簽到(1)或 未簽到(0)，已登錄(1)或未登陸(0)。

假如我們在判斷用戶是否登陸的場景中使用 Redis 的 String 類型實現（key -> userId，value -> 0 表示下線，1 - 登陸），假如存儲 100 萬個用戶的登陸狀態，如果以字符串的形式存儲，就需要存儲 100 萬個字符串，內存開銷太大。

String 類型除了記錄實際數據以外，還需要額外的內存記錄數據長度、空間使用等信息。

Bitmap 的底層數據結構用的是 String 類型的 SDS 數據結構來保存位數組，Redis 把每個字節數組的 8 個 bit 位利用起來，每個 bit 位 表示一個元素的二值狀態（不是 0 就是 1）。

可以將 Bitmap 看成是一個 bit 為單位的數組，數組的每個單元只能存儲 0 或者 1，數組的下標在 Bitmap 中叫做 offset 偏移量。

為了直觀展示，我們可以理解成 buf 數組的每個字節用一行表示，每一行有 8 個 bit 位，8 個格子分別表示這個字節中的 8 個 bit 位，如下圖所示：

8 個 bit 組成一個 Byte，所以 Bitmap 會極大地節省存儲空間。 這就是 Bitmap 的優勢。

(繼續閱讀...)

鑽石舞台 發表在 痞客邦 留言(0) 人氣()