redis資料結構實作--簡單動态字元串

1. SDS簡單動态字元串詳解

sds是redis自己實作的一種資料結構，用來作為redis底層預設字元串，與c語言的字元串差別開來。

在redis中c字元串一般用于不需要改變的字元串值，叫做字元串字面量，如：列印日志。

redis中每對鍵值的鍵都是一個sds對象。

傳統c字元串與sds比較：

• sds資料結構中也是用字元數組存儲字元串，但是帶有兩個額外參數：len（記錄字元串長度）和free（未使用空間）
• 想要獲得傳統c字元串的長度不得不周遊整個字元串，然而sds則可直接讀取len值。降低了時間複雜度
• 兩者的字元數組都是以空字元'/0'結尾，在sds中此空字元不計入len中但是也同樣配置設定一個位元組空間，空字元的相關操作都是由sds的API自動完成的，是以對于開發者來說此空字元是透明的。sds保持和c字元串一緻以空字元作為結尾是為了能夠複用c語言的字元串函數庫裡的函數。
• 傳統c字元串如果在對字元串操作沒有注意空間剩餘有可能會出現内場溢出的現象，而sds的API中執行拼接操作的函數sdscat，拼接時會先判斷空間是否足夠，如果不夠則會先執行擴容操作，進而杜絕内場溢出.
• 避免頻繁記憶體重配置設定：傳統c字元串的長度為n+1（空字元），每一次append時需要重新配置設定記憶體，否則記憶體溢出；如果trim字元串，後面不需要的空間也要釋放，否則記憶體洩露。記憶體重配置設定設計複雜算法且可能需要系統排程，不符合redis的速度要求。而sds通過free-未使用空間來解除了底層數組長度與字元串長度間的關聯，sds擁有空間預配置設定與惰性空間釋放兩鐘優化政策。
• 1. 空間預配置設定

     在對sds空間拓展時，先判斷空間是否足夠，如果足夠，則直接使用未使用空間。如果空間不夠則使用空間預配置設定政策
     如果計算得出的sds修改後的長度小于1MB,那麼預配置設定的未使用空間将于已使用的空間一樣長。如果sds修改後的長度大于1MB，
     那麼将配置設定1MB的未使用空間。
     通過這種政策将連續增長N次的sds字元串所需的記憶體重配置設定次數從必定是N次改為最多N次。           

  2. 惰性空間釋放

     在對sds字元串進行縮短操作時，并不立即回收縮短的長度，而是利用free将縮短的字元串記錄起來，以備以後拓展時使用。
     同樣sdsAPI中也提供了真正回收空間的API，是以惰性空間釋放并不會浪費空間。           

  • 二進制安全：c字元串必須得符合某種編碼，且字元串除了尾部中間不能存放空字元，否則被讀取到空字元時忽略後面的字元段。所有c字元串隻能存放文本資訊不能存放二進制資料。而sds的API都是二進制安全（binary-safe）的，buf中存放的就是一系列二進制資料。