redis的實現之美其一

來自專欄 折木的筆記

一直使用的redis，也只是知道其用法，了解其常用的數據結構，沒有嘗試去深入閱讀其源碼，差點錯過了一個這麼優美的實現。

redis的源碼相對於其它項目的源碼來說，可以算是相當簡潔的了。推薦閱讀《Redis設計與實現》一書，我也是從這本書中才對redis源碼產生了興趣。對一般用戶來說，只要了解redis的常用數據結構就足夠滿足日常使用了。但俗話說得好，不想造輪子的程序員不是一個好程序員。難道大家就沒有衝動要造一個更好的輪子么？為了造更好的輪子，不應該先看看原來的輪子是怎麼實現的么？

redis的常用數據結構包括字元串（string），哈希（hash），列表（list），set（集合），zset（有序集合）。

這裡先介紹其字元串相關的實現。redis的源碼是使用C語言編寫的，但是，其字元串並沒有使用C語言傳統的表現形式。而是在更符合自身使用的情況下作了一定的優化。

redis中字元串的底層結構為

struct sdshdr { int len;//buf數組中已經被使用的字元串長度 int free;//buf數組中未被使用的位元組的數量 char buf[];//位元組數組，用來保存字元串}

那為什麼要使用這樣的數據結構呢？

1、獲取字元串長度時間複雜度僅為O（1）。傳統的C語言字元串中並沒有保存其長度，每一次執行strlen函數都需要重新計算一遍，其時間複雜度為O（n）。而獲取字元串長度在redis中是極其常見的操作。

2、杜絕緩衝區溢出的問題。因為C語言字元串是不檢查數組越界的，執行strcat函數極容易產生越界的問題，覆寫原本正常的數據。而redis中SDS的數據結構不會，因為其本身就知道free的位元組數，當發現空間不足時，會先擴展至滿足才會執行strcat操作。

3、因為redis很多情況下讀寫都非常頻繁，跟C語言中字元串的場景不太一樣。而寫頻繁非常消耗操作系統資源，因為要經常申請和釋放內存。redis也就這個問題做了一定的優化。優化的方式採用的是預分配與惰性回收。當字元串需要擴展時,遵循如下的公式：

if len < 1M: free = lenelif len >= 1M: free = 1M

給字元串分配本身未被使用的空間。雖然這會比C語言原本的字元串使用更多的空間，但是確實提高了寫的效率。惰性回收就是當redis的字元串縮短的時候，其並不會立即回收，而是用free屬性記錄下來，當系統真正需要的時候再進行回收。

redis的字元串實現確實相當優美，推薦大家也能夠去閱讀源碼，同時極力推薦《Redis設計與實現》一書。

推薦閱讀：