Redis的各種數據結構以及合理使用

Redis的底層數據結構

• 簡單動態字符串sds(Simple Dynamic String)
• 雙端鏈表(LinkedList)
• 字典(Map)
• 跳躍表(SkipList)

redis各種數據類型使用的數據結構

• String, SDS(simple dynamic string) 簡單動態字符串, 包含len(字符串長度), free(空閒的字節數量), buf(字節數組,存儲數據)
• List, 使用壓縮列表(數據集比較少的時候, 列表中單個數據小於64字節或者列表中數據個數少於512個)和雙向循環鏈表, 包含pre, next, value
• hash, 使用壓縮列表(鍵和值的大小小於64字節, 列表中鍵值對個數小於512個)和散列表
• Set, 有序數組
  (個數不超過512)和散列表
• Zset, 壓縮列表(數據小於64字節或者個數小於128個)和跳躍表

用ziplist代替key-value減少80%內存佔用的案例

背景: 因業務原因, 需要大量存儲key-value數據, key和value都為string, 如果存儲1千萬條數據，佔用了redis共計1.17G的內存. 當數據量變成1個億時，實測大約佔用8個G. 但是修改為key(int), value 為ziplist時, 內存佔用為123M, 減少了85%.

步驟:

0. 要將1千萬個鍵值對, 放到N個bucket中, 但是為了防止ziplist變為hashtable, 每個bucket不能超過512個鍵值對, 1千萬 / 512 = 19531. 將所有key hash到所有bucket中, 但由於hash函數的不確定性, 可能出現不均等分配, 可以分配25000個bucket, 或者30000個bucket.
1. 選用hash算法, 決定將key放到哪個bucket. 這裡我們採用高效而且均衡的知名算法crc32. 通過獲取原有md5(key)的crc32後, 再對bucket的數量進行取餘.
2. 第2步確定了外層的key, 內部的field我們選用bkdr哈希算法. public static int BKDRHash(String str) {
   int seed = 131;
   int hash = 0;
   for (int i = 0; i < str.length; i++) {
   hash = (hash * seed) + str.charAt(i);
   }
   return (hash & 0X7FFFFFFF);
   }
3. 測試裝入1000萬條數據, 內存降低了85%; 查詢測試, 查100萬條數據, 對比查詢速度: key-value耗時：10653、10790、11318、9900、11270、11029毫秒 hash-field耗時：12042、11349、11126、11355、11168毫秒

關鍵字: 數據結構 數據 鏈表