Redis 數據結構

來自專欄 Java之鏈

Redis有5種數據結構：String、List、Hash、Set和Sorted Set。

這裡僅僅談String和Hash.

Redis沒有使用C語言傳統的字元串，而是使用了SDS（simple dynamic string）

struct sdshdr { int len; //字元串長度，不含空字元 int free; // 未使用位元組的數量，不含空字元 char buf[]; // 保存字元串，最後一個字元是空字元}

C語言字元串用長度是N+1的字元數組表示長度是N的字元串，字元數組最後一個元素是空字元。這種字元串的長度是靜態的，所以安全性較差，當字元串擴展時容易發生溢出（buffer flow），這樣會覆蓋其他內存。而sds會檢查擴展時的空間是否足夠，所以說sds是一種可以動態擴展的字元串，通過預分配內存來實現擴展：

1）如果擴展之後，sds的長度len小於1M，那麼將分配和len相同的空閑內存，此時buf數組的長度是len + len + 1.

2）如果擴展之後，sds的長度大於等於1M，那麼將分配1M的空閑內存，此時buf數組的長度是len + 1MB + 1.

當sds縮短時不會釋放空閑內存，這樣避免重複分配內存。只有在真正有需要時，才會真正釋放未使用的內存。

C語言字元串只能保存文本數據，不能保存二進位文件的數據，因為二進位文件中可能包含空字元，而sds卻可以自如存取。

sds用途不僅僅是實現字元串，還被用作緩衝區，比如實現AOF緩衝區和客戶端輸入緩衝區。

Hash是一種保存鍵值對（key-value pair）的數據結構，其實現與JDK HashMap類似。

動態數據結構都要考慮擴展的策略。比如Hash，當K-V較多時，會影響性能，這就需要把原來的數據結構擴展，也就是rehash。

負載因子 load_factor = node_size / hash_size （有幾個桶）

當load_factor大於等於1時，會擴展hash，當小於0.1時，會收縮hash。

當擴展時，hash_size 是 第一個大於等於node_size * 2^n

當收縮時，hash_size是 第一個大於等於node_size * 2^n

redis內有兩個hash，互相作為rehash的對象。redis採用的是漸進式rehash，不會一次性、集中式地完成，而是分多次、漸進式地完成。這是因為hash中的元素一般會比較多，這樣做的成本太高，所以要分攤到每次操作中。

在rehash的過程中，hash的操作是在兩個表中進行的，比如查找，如果在第一個表中找不到，會在第一個表中尋找。

2017-12-26再閱：

本文看似簡單，但涉及到不少重要的計算機思想。

1）數據結構大小（所佔內存）動態擴展或者動態收縮，這種擴展策略可能分不同層級

2）C語言字元串的缺點：容易溢出，不能存儲某些特殊字元。

3）批量操作和逐個操作各有利弊，前者勝在一次集中處理，後者勝在多次漸進分攤。

4）2015年，架構中使用AB結構，現在在數據結構這一層次上也看到了這種設計。