Redis核心原理-簡單動態字元串SDS

SDS簡介

Redis是C語言編寫的,但沒有使用c語言的字元串結構,而是自己實現了一套簡單動態字元串 simple dynamic string 簡稱SDS,SDS兼容C語言的字元串類型,原理類似Java的ArrayList,擴容和縮短長度時可以減少記憶體頻繁分配。

SDS用途

  • 包含字元串的鍵、值底層是用SDS實現
  • 持久化AOF的緩衝區實現

SDS屬性原理

  //記錄buf數組中已使用位元組的數量
  //等於SDS所保存字元串的長度
  int len;
  
  //記錄buf數組中未使用位元組的數量
  int free;
  
  //位元組數組,用於保存字元串
  char buf[];
  

len

表示SDS所保存字元串的長度,獲取字元串長度高效,時間複雜度為O(1)

buf[]

保存字元串的二進位數據,長度 = 字元數量 + 1(空字元)+ free

free

記錄buf數組中未使用位元組的數量,可以減少修改字元串帶來的記憶體重分配次數;優化策略有空間預分配和惰性空間釋放

空間預分配

擴大SDS空間時(比如兩個字元串拼接)使用空間預分配不用隨時分配記憶體,預分配規則為 len 小於 1M 時,free = len; len 大於1M 時 free = 1M

惰性空間釋放

縮短SDS空間時(比如剪切字元串)不立即回收記憶體,使用free來記錄縮短長度,等待將來使用,避免記憶體浪費

Tags: